scikit-learn DBSCAN 内存使用情况

Question

scikit-learn DBSCAN 内存使用情况

pythonscikit-learncluster-analysisdata-miningdbscan

38

更新： 最终，我选择使用Anony-Mousse在下面建议的一种方法来对我的大型数据集进行聚类。即，使用ELKI的DBSCAN实现而不是scikit-learn的。它可以从命令行运行，并且在适当的索引下，可以在几小时内完成此任务。使用GUI和小样本数据集来确定要使用的选项，然后开始工作。值得一看。无论如何，继续阅读以了解我最初的问题描述和一些有趣的讨论。

我有一个包含约250万个样本的数据集，每个样本具有35个特征（浮点数值），我正在尝试对其进行聚类。我一直在使用scikit-learn的DBSCAN实现，使用曼哈顿距离度量和从数据中随机抽取的一些小样本估计的epsilon值来尝试聚类。到目前为止，一切顺利。（以下是参考代码）

db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata)

我目前的问题是我的电脑内存很容易不够用。(我使用的机器有16GB的RAM)

我的问题是，DBSCAN是否在运行时实时计算成对距离矩阵，导致内存被耗尽？（2.5万^ 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

- JamesT

5个回答

18

你可以使用scikit-learn的DBSCAN算法，结合haversine度量和ball-tree算法来实现。你不需要预先计算距离矩阵。

这个例子使用DBSCAN/haversine算法对超过一百万个GPS经纬度点进行聚类，并避免了内存使用问题：clusters over a million GPS latitude-longitude points。

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

- eos

3

已确认，与v0.17.1相比，sklearn v0.15.2在运行相同的模型拟合时需要的内存要少得多。 - cxrodgers

7

这个问题在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

- Isaac

2

太棒了，我刚试了一下OPTICS算法，用一个含有43000行数据的ndarray，运行了大约2分钟就成功了。而用同样的ndarray运行DBSCAN时，却总是出现内存崩溃错误。 - RonanFelipe

2

我在使用旧版的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

- MMamdouh

1

DBSCAN算法实际上会计算距离矩阵，这里没有机会。对于这么多数据，我建议使用MiniBatchKMeans。你不能直接使用曼哈顿距离度量，但你可以自己实现。也许先尝试使用欧几里得距离的标准实现。我不知道有多少聚类算法不执行成对距离计算。使用新嵌入的cheat-sheet底部中心：祝好运。

- Andreas Mueller

没有办法动态计算它们吗？根据我对DBSCAN的理解，我不清楚为什么不能从随机点开始，计算其到其他某个点的距离，并将其与epsilon进行比较，一遍又一遍地将其排除或添加为邻居... - JamesT

@JamesT：虽然这是可能的，但目前的scikit-learn实现并没有这样做。它不能很好地扩展到大量的样本，因为它需要二次空间和时间。 - Fred Foo

6

错误。DBSCAN 不需要距离矩阵（特别是不需要矩阵）。一个好的实现应该使用空间索引，以显著减少需要的距离计算次数。它应该在 O(n) 的内存和 O(n log n) 的运行时间中实现。 - Has QUIT--Anony-Mousse

3

DBSCAN算法本身不需要计算整个距离矩阵。例如，可以在维基百科上查看基本伪代码 https://en.wikipedia.org/wiki/DBSCAN#Algorithm 。以前版本的scikit依赖于完全计算距离矩阵，但现在不再是这种情况。 - titus

1

根据我的经验，v0.15.2版本运行相同代码所需的内存比v0.17.1版本要少得多。你有什么想法为什么会这样？ - cxrodgers

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Has QUIT--Anony-Mousse · Accepted Answer

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

DBSCAN不需要距离矩阵。该算法是围绕着使用可以加速regionQuery函数的数据库设计的，并且可以高效地返回查询半径内的邻居(空间索引应支持这样的查询，时间复杂度为O(log n))。

然而，在scikit中的实现显然计算了完整的O(n^2)距离矩阵，这会导致内存和运行时成本的双重压力。

所以我看到两个选择：

您可以尝试使用ELKI中的DBSCAN实现，当与R * -tree索引一起使用时，通常比朴素实现快得多。
否则，您可能需要重新实现DBSCAN，因为scikit中的实现似乎不太好。不要害怕：DBSCAN非常容易自己实现。一个好的DBSCAN实现中最棘手的部分实际上是regionQuery函数。如果您可以快速获取此查询，则DBSCAN将很快。您实际上还可以将此功能重用于其他算法。

更新：现在，sklearn不再计算距离矩阵，并且可以使用kd-tree索引。但是，由于“向量化”，它仍然会预先计算每个点的邻居，因此sklearn对于大的epsilon的内存使用量为O（n²），而据我所知，ELKI中的版本只使用O（n）内存。因此，如果您的内存不足，请选择较小的epsilon并/或尝试ELKI。