scikit-learn DBSCAN内存使用情况

问题描述 投票：19回答：5

更新：最后，我选择用于聚类我的大型数据集的解决方案是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
python scikit-learn cluster-analysis data-mining dbscan
5个回答
19
投票

问题显然是scikit-learn中的非标准DBSCAN实现。

DBSCAN不需要距离矩阵。该算法是围绕使用可以加速regionQuery函数的数据库设计的，并且有效地返回查询半径内的邻居（空间索引应该支持O(log n)中的此类查询）。

然而，在scikit中的实现显然计算了完整的O(n^2)距离矩阵，这种代码在内存和运行时都是成本。

所以我看到两个选择：

  1. 您可能想要在ELKI中尝试DBSCAN实现，当与R * -tree索引一起使用时，通常比天真的实现快得多。
  2. 否则，您可能想重新实现DBSCAN，因为scikit中的实现显然不太好。不要害怕：DBSCAN自己实现起来非常简单。一个好的DBSCAN实现最棘手的部分实际上是regionQuery函数。如果你能快速得到这个查询，DBSCAN会很快。而且你也可以将这个功能重用于其他算法。

更新：到目前为止，sklearn不再计算距离矩阵，并且可以例如使用kd树索引。但是，由于“向量化”，它仍然会预先计算每个点的邻居，因此对于大ε的sklearn的内存使用是O（n²），而根据我的理解，ELKI中的版本将仅使用O（n）内存。因此，如果内存不足，请选择较小的epsilon和/或尝试使用ELKI。

12
投票

你可以使用scikit-learn的DBSCAN和hasrsine metric and ball-tree算法来做到这一点。您无需预先计算距离矩阵。

此示例clusters over a million GPS latitude-longitude points与DBSCAN / hasrsine并避免内存使用问题：

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
1
投票

DBSCAN算法实际上确实计算了距离矩阵，所以这里没有机会。对于这么多数据，我建议使用MiniBatchKMeans。您不能在开箱即用的情况下使用曼哈顿指标，但您可以自己实施。也许首先尝试使用欧几里德指标的标准实现。

我不知道许多不执行成对距离的聚类算法。

使用新嵌入的cheat-sheet底部中心：虽然运气好。

1
投票

这里讨论sklearn的这个问题：

https://github.com/scikit-learn/scikit-learn/issues/5275

那里有两种选择;

一种是使用OPTICS（需要sklearn v21 +），这是DBSCAN的替代但密切相关的算法：

https://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html

其他的是预先计算邻接矩阵，或使用样本权重。有关这些选项的更多详细信息，请参阅此处的Notes：

https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

1
投票

当我在sklearn 0.19.1上使用旧版本时遇到了同样的问题，因为复杂度为O（N ^ 2）。

但是现在问题已在新版本0.20.2中解决，并且不再存在内存错误，并且复杂性变为O（n.d），其中d是邻居的平均数量。这不是偶像的复杂性，而是比旧版本更好。

查看此版本中的注释，以避免高内存使用：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.