如何通过距离将地理点列表进行聚类？

Question

如何通过距离将地理点列表进行聚类？

pythoncluster-analysislatitude-longitudespatial-query

9

我有一个点列表P=[p1,...pN]，其中pi=(latitudeI,longitudeI)。

使用Python 3，我想找到一个最小的簇集合（P的不相交子集），使得簇中的每个成员与簇中的其他成员之间的距离不超过20公里。

使用Vincenty方法计算两点之间的距离。

为了更具体一些，假设我有一组点，例如

from numpy import *
points = array([[33.    , 41.    ],
       [33.9693, 41.3923],
       [33.6074, 41.277 ],
       [34.4823, 41.919 ],
       [34.3702, 41.1424],
       [34.3931, 41.078 ],
       [34.2377, 41.0576],
       [34.2395, 41.0211],
       [34.4443, 41.3499],
       [34.3812, 40.9793]])

现在我正在尝试定义这个函数：

from geopy.distance import vincenty
def clusters(points, distance):
    """Returns smallest list of clusters [C1,C2...Cn] such that
       for x,y in Ci, vincenty(x,y).km <= distance """
    return [points]  # Incorrect but gives the form of the output

注意：许多问题涉及地理位置和属性。我的问题仅与位置有关。这是针对纬度/经度，而非欧几里得距离的。有其他相关问题提供了类似的答案，但没有回答我这个问题（很多问题没有解答）：

- Lars Ericson

尝试过使用sklearn进行k-means聚类吗？似乎将其视为分类问题可能会有所帮助。 - vencaslac

1

我不预先知道 K。 - Lars Ericson

好的，不是的，你正在优化k，见下文。 - vencaslac

3个回答

5

这里有一个看起来正确的解决方案，最坏情况下时间复杂度为O(N^2)，但根据数据情况可能会更好:

def my_cluster(S,distance):
    coords=set(S)
    C=[]
    while len(coords):
        locus=coords.pop()
        cluster = [x for x in coords if vincenty(locus,x).km <= distance]
        C.append(cluster+[locus])
        for x in cluster:
            coords.remove(x)
    return C

注意：我没有将这个答案标记为正确，因为我的要求之一是它必须是一个最小的群集。我的第一次尝试很好，但我还没有证明它是最小的集合。

结果（在更大的点集上）可以可视化如下：

- Lars Ericson

1

为什么不使用S2库创建20公里区域，并查看每个点是否在其中？

- APD

区域并非预先确定，而是来自数据分析。我提供的my_cluster例程工作得很好，但据我所知，它不能保证给出最小集合（我说“一个”是因为对于相同点集可能有多个解决方案）。 - Lars Ericson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vencaslac · Accepted Answer

这可能是一个开始。该算法尝试通过迭代k从2到点的数量来k均值聚类点，同时验证每个解决方案。您应该选择最低数量。

它通过对点进行聚类，然后检查每个簇是否遵守约束条件来工作。如果任何一个簇不符合要求，则将该解决方案标记为False，然后我们继续尝试下一个簇的数量。

由于sklearn中使用的K均值算法会陷入局部极小值，因此是否为您所寻找的解决方案是最好的还有待确定，但这可能是其中之一。

import numpy as np
from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist
import math

points = np.array([[33.    , 41.    ],
       [33.9693, 41.3923],
       [33.6074, 41.277 ],
       [34.4823, 41.919 ],
       [34.3702, 41.1424],
       [34.3931, 41.078 ],
       [34.2377, 41.0576],
       [34.2395, 41.0211],
       [34.4443, 41.3499],
       [34.3812, 40.9793]])


def distance(origin, destination): #found here https://gist.github.com/rochacbruno/2883505
    lat1, lon1 = origin[0],origin[1]
    lat2, lon2 = destination[0],destination[1]
    radius = 6371 # km
    dlat = math.radians(lat2-lat1)
    dlon = math.radians(lon2-lon1)
    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) \
        * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = radius * c

    return d

def create_clusters(number_of_clusters,points):
    kmeans = KMeans(n_clusters=number_of_clusters, random_state=0).fit(points)
    l_array = np.array([[label] for label in kmeans.labels_])
    clusters = np.append(points,l_array,axis=1)
    return clusters

def validate_solution(max_dist,clusters):
    _, __, n_clust = clusters.max(axis=0)
    n_clust = int(n_clust)
    for i in range(n_clust):
        two_d_cluster=clusters[clusters[:,2] == i][:,np.array([True, True, False])]
        if not validate_cluster(max_dist,two_d_cluster):
            return False
        else:
            continue
    return True

def validate_cluster(max_dist,cluster):
    distances = cdist(cluster,cluster, lambda ori,des: int(round(distance(ori,des))))
    print(distances)
    print(30*'-')
    for item in distances.flatten():
        if item > max_dist:
            return False
    return True

if __name__ == '__main__':
    for i in range(2,len(points)):
        print(i)
        print(validate_solution(20,create_clusters(i,points)))

一旦建立了基准，就需要更加关注每个聚类，以确定是否可以将其点分配到其他聚类中，而不违反距离约束。

您可以用自己选择的任何距离度量替换cdist中的lambda函数，我在提到的repo中发现了大圆距离。