36

更新：最后，我选择用于对大型数据集进行聚类的解决方案是下面 Anony-Mousse 建议的解决方案。也就是说，使用 ELKI 的 DBSCAN 实现我的聚类而不是 scikit-learn 的。它可以从命令行运行，并通过适当的索引，在几个小时内执行此任务。使用 GUI 和小样本数据集来制定您想要使用的选项，然后前往城镇。值得研究。任何人，请继续阅读我最初的问题的描述和一些有趣的讨论。

我有一个包含约 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
4

5 回答 5

31

问题显然是scikit-learn.

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

然而，显然，该实现scikit计算了全O(n^2)距离矩阵，这在内存方面和运行时方面都是有代价的。

所以我看到两个选择：

  1. 您可能想尝试使用ELKI中的 DBSCAN 实现，当与 R*-tree 索引一起使用时，它通常比简单的实现快得多。

  2. 否则，您可能需要重新实现 DBSCAN，因为scikit显然它的实现不太好。不要害怕：DBSCAN 自己实现起来非常简单。一个好的 DBSCAN 实现中最棘手的部分实际上是regionQuery函数。如果你能快速得到这个查询，DBSCAN 就会很快。您实际上也可以将此函数重用于其他算法。

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

于 2013-05-05T16:35:55.817 回答
17

您可以使用 scikit-learn 的 DBSCAN 和 hasrsine 度量和球树算法来做到这一点。您不需要预先计算距离矩阵。

此示例使用 DBSCAN/haversine对超过一百万个 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
于 2016-08-02T23:10:50.630 回答
6

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

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

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

于 2018-12-04T10:06:40.237 回答
2

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

但是现在这个问题已经在新版本 0.20.2 中得到解决，不再出现内存错误，复杂度变为 O(nd)，其中 d 是平均邻居数。这不是理想的复杂性，但比旧版本好得多。

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

于 2019-02-18T10:18:41.297 回答
1

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

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

使用新嵌入的备忘单底部中心：虽然很幸运。

于 2013-05-05T14:31:05.357 回答