Jam*_*esT 20 python cluster-analysis data-mining dbscan scikit-learn
更新:最后,我选择用于聚类我的大型数据集的解决方案是Anony-Mousse在下面提出的解决方案.也就是说,使用ELKI的DBSCAN实现我的聚类而不是scikit-learn.它可以从命令行运行,并通过适当的索引,在几个小时内完成此任务.使用GUI和小样本数据集来计算您想要使用的选项,然后前往城镇.值得研究.Anywho,请继续阅读我原始问题的描述和一些有趣的讨论.
我有一个包含大约250万个样本的数据集,每个样本都有35个特征(浮点值),我正在尝试聚类.我一直在尝试使用scikit-learn的DBSCAN实现,使用曼哈顿距离度量和从数据中提取的一些小随机样本估计的epsilon值.到现在为止还挺好.(这里是摘录,供参考)
db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata)
我现在的问题是我很容易耗尽内存.(我目前正在使用16 GB RAM的机器)
我的问题是,DBSCAN是否在运行时动态计算成对距离矩阵,那是什么在吞噬我的记忆？(250万^ 2)*8字节显然是愚蠢的大,我会理解.我应该不使用这种fit()方法吗？更一般地说,有没有办法绕过这个问题,或者我一般在这里咆哮错误的树？
如果答案结果明显,请道歉.我已经困惑了几天.谢谢!
附录:如果有人能更明确地解释我fit(X)和fit_predict(X)我之间的区别,我也会感激 - 我担心我不太明白.
附录#2:可以肯定的是,我只是在一台拥有~550 GB RAM的机器上尝试了这个并且它仍然爆炸,所以我觉得DBSCAN可能会尝试制作成对距离矩阵或者我明显不想要的东西去做.我想现在最大的问题是如何阻止这种行为,或找到更适合我需要的其他方法.谢谢你在这里与我合作.
附录#3(!):我忘了附上追溯,就在这里,
Traceback (most recent call last):
File "tDBSCAN.py", line 34, in <module>
db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict
self.fit(X)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit
**self.get_params())
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan
D = pairwise_distances(X, metric=metric)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances
return func(X, Y, **kwds)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances
D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :])
MemoryError
Ano*_*sse 19
问题显然是一个低质量的DBSCAN实现scikit-learn.
DBSCAN不需要距离矩阵.该算法是围绕使用可以加速regionQuery函数的数据库设计的,并且有效地返回查询半径内的邻居(空间索引应该支持这样的查询O(log n)).
scikit然而,实现显然计算了全O(n^2)距离矩阵,其在内存方面和运行时方面都是成本的.
所以我看到两个选择:
您可能希望尝试在ELKI中使用DBSCAN实现,当与R*-tree索引一起使用时,通常比天真的实现快得多.
否则,你可能想重新实现DBSCAN,因为scikit显然实现不太好.不要害怕:DBSCAN自己实现起来非常简单.一个好的DBSCAN实现中最棘手的部分实际上就是regionQuery函数.如果你能快速得到这个查询,DBSCAN会很快.而且你也可以将这个功能重用于其他算法.
更新:到目前为止,sklearn不再计算距离矩阵,并且可以例如使用kd-tree索引.但是,由于"向量化",它仍然会预先计算每个点的邻居,因此对于大ε的sklearn的内存使用是O(n²),而据我所知,ELKI中的版本将只使用O(n)内存.因此,如果内存不足,请选择较小的epsilon和/或尝试ELKI.
eos*_*eos 12
你可以使用scikit-learn的DBSCAN和hasrsine metric and ball-tree算法来做到这一点.您无需预先计算距离矩阵.
此示例使用DBSCAN/hasrsine 聚集超过一百万个GPS纬度 - 经度点,并避免内存使用问题:
df = pd.read_csv('gps.csv')
coords = df.as_matrix(columns=['lat', 'lon'])
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords))
请注意,这特别使用了scikit-learn v0.15,因为某些早期版本/更高版本似乎需要计算一个完整的距离矩阵,这会快速炸毁你的RAM.但是如果你使用Anaconda,你可以快速设置:
conda install scikit-learn=0.15
或者,为此群集任务创建一个干净的虚拟环境:
conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter
activate clusterenv
这里讨论了 sklearn 的这个问题：
那里有两个选项；
一种是使用 OPTICS（需要 sklearn v21+），这是 DBSCAN 的一种替代但密切相关的算法：
https://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html
其他的是预先计算邻接矩阵，或者使用样本权重。可以在此处的注释下找到有关这些选项的更多详细信息：
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html