如何按距离对地理点列表进行聚类?
how do I cluster a list of geographic points by distance?
我有一个点列表 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
注意:许多问题都集中在地理位置 和属性 上。我的问题仅针对 位置 。这是针对 lat/lon、 而不是 欧氏距离。还有其他问题给出了某种答案但不是这个问题的答案(许多未回答):
- 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
- 还有更多,其中 none 回答了这个问题。
这是一个看起来正确的解决方案,并且会根据数据在 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
注意:我没有将此标记为答案,因为我的要求之一是它是最小的 集群集。我的第一遍很好,但我还没有证明它是最小的集合。
结果(在更大的一组点上)可以可视化如下:
为什么不使用 S2 库创建 20 公里的区域并查看每个区域中有哪些点?
这可能是一个开始。该算法尝试通过将 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 中找到了大圆距离。
我有一个点列表 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
注意:许多问题都集中在地理位置 和属性 上。我的问题仅针对 位置 。这是针对 lat/lon、 而不是 欧氏距离。还有其他问题给出了某种答案但不是这个问题的答案(许多未回答):
- 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
- 还有更多,其中 none 回答了这个问题。
这是一个看起来正确的解决方案,并且会根据数据在 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
注意:我没有将此标记为答案,因为我的要求之一是它是最小的 集群集。我的第一遍很好,但我还没有证明它是最小的集合。
结果(在更大的一组点上)可以可视化如下:
为什么不使用 S2 库创建 20 公里的区域并查看每个区域中有哪些点?
这可能是一个开始。该算法尝试通过将 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 中找到了大圆距离。