DBSCAN 处理大数据崩溃和内存错误

Question

我正在对400K数据点的数据集进行DBSCAN。这是我得到的错误：

Traceback (most recent call last):
  File "/myproject/DBSCAN_section.py", line 498, in perform_dbscan_on_data
    db = DBSCAN(eps=2, min_samples=5).fit(data)
  File "/usr/local/Python/2.7.13/lib/python2.7/site-packages/sklearn/cluster/dbscan_.py", line 266, in fit
    **self.get_params())
  File "/usr/local/Python/2.7.13/lib/python2.7/site-packages/sklearn/cluster/dbscan_.py", line 138, in dbscan
    return_distance=False)
  File "/usr/local/Python/2.7.13/lib/python2.7/site-packages/sklearn/neighbors/base.py", line 621, in radius_neighbors
    return_distance=return_distance)
  File "sklearn/neighbors/binary_tree.pxi", line 1491, in sklearn.neighbors.kd_tree.BinaryTree.query_radius (sklearn/neighbors/kd_tree.c:13013)
MemoryError

我该如何解决这个问题？ DBSCAN 处理大量数据是否有任何限制？

我的例子来源是：http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

我的数据采用 X、Y 坐标格式：

11.342276,11.163416
11.050597,10.745579
10.798838,10.559784
11.249279,11.445535
11.385767,10.989214
10.825875,10.530120
10.598493,11.236947
10.571042,10.830799
11.454966,11.295484
11.431454,11.200208
10.774908,11.102601
10.602692,11.395169
11.324441,11.088243
10.731538,10.695864
10.537385,10.923226
11.215886,11.391537

我应该将数据转换为稀疏 CSR 吗？ 如何？

Answer 1

sklearn的DBSCAN需要O(n*k(内存，其中k是epsilon中的邻居数。对于大型数据集和 epsilon，这将是一个问题。对于一个小数据集，它在Python上更快，因为它在Cython中做更多的工作，而不是慢速解释器。sklearn的作者选择做这种变化。现在，也考虑使用较小的 epsilon。

但这不是最初的DBSCAN所提出的，其他实现，如ELKI的已知可扩展到数百万点。它一次查询一个点，因此只需要 O(n+k( 内存。它还具有光学器件，据报道在坐标上工作得很好。