python - 如何按距离对地理点列表进行聚类？

Question

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

我想使用 Python 3 找到一组最小的集群(P 的不相交子集)，使得集群中的每个成员与集群中其他每个成员的距离都在 20 公里以内。

两点之间的距离是使用 Vincenty method 计算的.

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

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

注意:许多问题都集中在地理位置和属性上。我的问题是仅限位置。这是纬度/经度，不是欧氏距离。还有其他问题给出了某种答案但不是这个问题的答案(许多未回答):

• https://datascience.stackexchange.com/questions/761/clustering-geo-location-coordinates-lat-long-pairs
• https://gis.stackexchange.com/questions/300171/clustering-geo-points-and-export-borders-in-kml
• https://gis.stackexchange.com/questions/194873/clustering-geographical-data-based-on-point-location-and-associated-point-values
• https://gis.stackexchange.com/questions/256477/clustering-latitude-longitude-data-based-on-distance
• 还有更多，没有一个能回答这个问题。

Answer 1

这可能是一个开始。该算法尝试通过将 k 从 2 迭代到沿途验证每个解决方案的点数来对点进行 k 均值聚类。您应该选择最小的数字。

它的工作原理是对点进行聚类，然后检查每个聚类是否遵守约束。如果任何集群不合规，解决方案将被标记为 False，然后我们继续处理下一批集群。

因为 sklearn 中使用的 K-means 算法会陷入局部极小值，证明这是否是您正在寻找的解决方案是最佳的解决方案仍有待确定，但它可以成为一个

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 中找到了大圆距离。