optimization - sklearn的标准DBSCAN怎么跑的这么快？

Question

我一直在研究用于聚类雷达数据的 DBSCAN 的替代实现(例如基于网格的 DBSCAN)。到目前为止，我一直在使用 sklearn 的标准欧几里德 DBSCAN，它可以在不到一秒的时间内运行 26,000 个数据点。但是，当我指定自己的距离度量时，如下所示:

X = np.column_stack((beam, gate, time_index))
num_pts = X.shape[0]
epsilons = np.array([[beam_eps]*num_pts, [gate_eps] * num_pts, [time_eps] * num_pts]).T

metric = lambda x, y, eps: np.sqrt(np.sum((x/eps - y/eps)**2))
def dist_metric(x, y, eps):
    return np.sqrt(np.sum((x - y)**2))

db = DBSCAN(eps=eps, min_samples=minPts, metric=dist_metric, metric_params={'eps': epsilons}).fit(X)

运行相同数据所需的时间从 0.36 秒减少到 92 分钟。

我在那个代码片段中所做的也可以通过预先转换数据和运行标准欧几里得 DBSCAN 来完成，但我正在尝试实现一个相当快的基于网格的 DBSCAN 版本，水平 epsilon 会根据在离雷达的距离上，所以我无法做到这一点。

上述距离度量的部分缓慢是因为我认为除以 epsilon，因为如果我使用欧几里德距离的“自定义度量”，它只需要大约一分钟的时间来运行:

metric = lambda x, y: np.sqrt(np.sum((x - y)**2))

sklearn 的欧几里德 DBSCAN 如何运行得如此之快？我一直在研究代码，但到目前为止还没有理解它。

Answer 1

因为它使用了索引。

此外，它避免了缓慢且占用大量内存的 Python 解释器，而是在 native 代码(从 Cython 编译)中完成所有工作。这在处理大量原始数据(例如 Python 解释器需要装箱的 double 和整数)时产生巨大差异。

索引对相似性搜索起着至关重要的作用。他们可以将运行时间从 O(n²) 减少到 O(n log n)。

但是虽然球树索引允许自定义指标，但每次距离计算调用 python 解释器的成本非常高，所以如果你真的想要自定义指标，请编辑 cython 源代码并自己编译 sklearn。或者你可以使用 ELKI，因为 Java JVM 可以在必要时将扩展代码编译为 native 代码；它不需要回退到像 sklearn 这样的慢速解释器回调。

在您的情况下，对数据进行预处理可能会好得多。在聚类之前对其进行缩放。