2024-05-06 02:10:09 发布
网友
我目前面临的问题是如何在python中集群大约500000个经纬度对。到目前为止,我已经尝试用numpy(传递到scikit learn DBSCAN)计算一个距离矩阵,但是输入这么大,它很快就会抛出一个内存错误。
这些点存储在包含纬度、经度和该点的数据值的元组中。
简而言之,在python中,在空间上集群大量经纬度对的最有效方法是什么?对于这个应用程序,我愿意以速度的名义牺牲一些准确性。
编辑: 算法要查找的簇数提前未知。
scikit learn中旧版本的DBSCAN将计算一个完整的距离矩阵。
不幸的是,计算距离矩阵需要O(n^2)内存,这可能是内存不足的地方。
O(n^2)
较新版本(您使用哪个版本?)of scikit learn应该能够在没有距离矩阵的情况下工作;至少在使用索引时是这样。对于500.000个对象,您需要使用索引加速,因为这会将运行时从O(n^2)减少到O(n log n)。
O(n log n)
我不知道scikit learn在其索引中对大地距离的支持程度。ELKI是我所知道的唯一一个可以使用R*-tree索引来加速大地测量距离的工具;这使得执行此任务非常快(特别是在批量加载索引时)。你应该试一试。
看看Scikit learn indexing documentation,然后尝试设置algorithm='ball_tree'。
algorithm='ball_tree'
我没有你的数据,所以我只是把500个随机数分成三列。
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秒,所以我认为这与数据的大小无关。将数据放入500000x 3 numpy数组并尝试kmeans2。
scikit learn中旧版本的DBSCAN将计算一个完整的距离矩阵。
不幸的是,计算距离矩阵需要
O(n^2)
内存,这可能是内存不足的地方。较新版本(您使用哪个版本?)of scikit learn应该能够在没有距离矩阵的情况下工作;至少在使用索引时是这样。对于500.000个对象,您需要使用索引加速,因为这会将运行时从
O(n^2)
减少到O(n log n)
。我不知道scikit learn在其索引中对大地距离的支持程度。ELKI是我所知道的唯一一个可以使用R*-tree索引来加速大地测量距离的工具;这使得执行此任务非常快(特别是在批量加载索引时)。你应该试一试。
看看Scikit learn indexing documentation,然后尝试设置
algorithm='ball_tree'
。我没有你的数据,所以我只是把500个随机数分成三列。
我给它计时,运行Kmeans2用了1.96秒,所以我认为这与数据的大小无关。将数据放入500000x 3 numpy数组并尝试kmeans2。
相关问题 更多 >
编程相关推荐