在python中将500,000个地理空间点聚类

Question

我目前面临的问题是寻找一种在python中将约500,000个纬度/经度对聚类的方法。到目前为止，我已经尝试用numpy计算距离矩阵（以传递到scikit-learn DBSCAN中），但是由于输入量如此之大，它很快会吐出内存错误。

这些点存储在元组中，其中包含该点的纬度，经度和数据值。

简而言之，在python中对大量纬度/经度对进行空间聚类的最有效方法是什么？对于此应用程序，我愿意以速度为名牺牲一些准确性。

编辑：要查找的算法的簇数事先未知。

Answer 1

scikit learning中的旧版本DBSCAN将计算完整的距离矩阵。

不幸的是，计算距离矩阵需要O(n^2)内存，而这可能是内存不足的地方。

scikit Learn的较新版本（您使用哪个版本？）应该能够在没有距离矩阵的情况下工作；至少在使用索引时。对于500.000个对象，您确实希望使用索引加速，因为这会将运行时间从减少O(n^2)到O(n log n)。

我不知道scikit学习如何在其索引中支持大地测量距离。我知道，ELKI是唯一可以使用R * -tree索引来加速大地测量距离的工具。使它非常快地完成此任务（尤其是在批量加载索引时）。您应该尝试一下。

看看Scikit学习索引文档，然后尝试设置algorithm='ball_tree'。

Answer 2

我没有你的数据，所以我只是在三列中生成了 500k 随机数。

import numpy as np
import matplotlib.pyplot as plt
from scipy.cluster.vq import kmeans2, whiten

arr = np.random.randn(500000*3).reshape((500000, 3))
x, y = kmeans2(whiten(arr), 7, iter = 20)  #<--- I randomly picked 7 clusters
plt.scatter(arr[:,0], arr[:,1], c=y, alpha=0.33333);

out[1]:

我对此进行了计时，运行这个 Kmeans2 花了 1.96 秒，所以我认为这与数据的大小无关。将数据放入 500000 x 3 numpy 数组中并尝试 kmeans2。