machine-learning - 在 scikit-learn 中，DBSCAN 可以使用稀疏矩阵吗？

Question

运行 scikit 的 dbscan 算法时出现内存错误。我的数据大约是 20000*10000，它是一个二进制矩阵。

（也许DBSCAN不适合用这样的矩阵。我是机器学习的初学者。我只想找到一个不需要初始簇号的簇方法）

无论如何，我发现了 scikit 的稀疏矩阵和特征提取。

但我仍然不知道如何使用它。在 DBSCAN 的规范中，没有关于使用稀疏矩阵的指示。不允许吗？

如果有人知道如何在 DBSCAN 中使用稀疏矩阵，请告诉我。或者你可以告诉我一个更合适的集群方法。

score 8 · Accepted Answer

scikit不幸的是，DBSCAN的实现非常幼稚。它需要重写以考虑索引（球树等）。

到目前为止，它显然会坚持计算一个完整的距离矩阵，这会浪费大量内存。

我可以建议您自己重新实现 DBSCAN。这相当容易，例如在维基百科和原始出版物中都有很好的伪代码。它应该只有几行，然后您就可以轻松地利用您的数据表示。例如，如果您已经有一个稀疏表示的相似图，那么进行“范围查询”通常相当简单（即仅使用满足您的距离阈值的边）

这是scikit-learn github中的一个问题，他们谈论改进实现。一个用户报告他使用球树的版本快了 50 倍（这并不让我感到惊讶，我之前已经看到类似的索引加速 - 当进一步增加数据集大小时它可能会变得更加明显）。

更新：自编写此答案以来，scikit-learn 中的 DBSCAN 版本已获得实质性改进。

score 1 · Accepted Answer

您可以将距离矩阵传递给DBSCAN，因此假设X是您的示例矩阵，以下应该可以工作：

from sklearn.metrics.pairwise import euclidean_distances

D = euclidean_distances(X, X)
db = DBSCAN(metric="precomputed").fit(D)

但是，矩阵D甚至会大于X：n_samples² 条目。对于稀疏矩阵，k-means 可能是最好的选择。

（DBSCAN 可能看起来很有吸引力，因为它不需要预先确定数量的集群，但它会用它换取您必须调整的两个参数。它主要适用于样本是空间点并且您知道距离有多近的设置希望这些点在同一个集群中，或者当你有一个 scikit-learn 不支持的黑盒距离度量时。）

score 1 · Accepted Answer

是的，从 0.16.1 版开始。这是一个测试的提交：

score 0 · Accepted Answer

Sklearn 的 DBSCAN 算法不采用稀疏数组。但是，KMeans和Spectral 聚类可以，您可以尝试这些。有关 sklearns 聚类方法的更多信息：http: //scikit-learn.org/stable/modules/clustering.html

4 回答 4