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

Question

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

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

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

编辑:算法要查找的聚类数量提前未知。

Answer 1

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

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

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

不过，我不知道 scikit learn 在其索引中如何支持大地距离。 ELKI是我所知道的唯一可以使用 R*-tree 索引来加速大地距离的工具；使此任务非常快(特别是在批量加载索引时)。你应该试一试。

看看 Scikit learn indexing documentation ，并尝试设置 algorithm='ball_tree'。