scikit学习DBSCAN内存使用情况

scikit学习DBSCAN内存使用情况

问题显然是的非标准DBSCAN实现

scikit-learn

。

DBSCAN不需要距离矩阵。该算法是围绕使用数据库进行设计的，该数据库可以加速

regionQuery

功能，并有效地返回查询半径内的邻居（空间索引应支持中的此类查询

O(logn)

）。

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。