如何按距离对地理位置列表进行聚类？

如何按距离对地理位置列表进行聚类？

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

它通过对点进行聚类，然后检查每个聚类是否遵守约束来工作。如果有任何不符合要求的群集，则将解决方案标记为，

False

然后我们继续下一个群集。

由于sklearn中使用的K均值算法属于局部极小值，因此仍然需要确定这是否是您正在寻找的 最佳 解决方案，但这可能是一个

import numpy as npfrom sklearn.cluster import KMeansfrom scipy.spatial.distance import cdistimport mathpoints = 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 ddef 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 clustersdef 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 Truedef 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 Trueif __name__ == '__main__':    for i in range(2,len(points)):        print(i)        print(validate_solution(20,create_clusters(i,points)))

一旦建立了基准，就必须在每个群集上集中更多的基准，以确定是否可以在不违反距离约束的情况下将其点分配给其他群集。

您可以将cdist中的lambda函数替换为您选择的任何距离指标，我在我提到的仓库中发现了很大的圆距。