DBSCAN++：比 DBSCAN 更快且可扩展的替代方案

DBSCAN++: A Faster and Scalable Alternative to DBSCAN

非参数无监督算法在工业界被广泛用于分析大型数据集。这是因为在许多实际应用中，获取真实标签相当困难或不可行。

在这种情况下：

• 要么由数据团队给数据打标签，而这有时在实践中几乎是不可能的；
• 要么使用无监督方法来识别其中的模式。

虽然 KMeans 因其作为聚类算法的简洁与有效而在此被广泛使用，但正如我们在上一章也讨论过的，它有许多局限：

• 它不考虑簇的协方差。
• 它只能产生球形的簇。如下图所示，即使数据中存在非圆形的簇，它依然会产生圆形的簇。而像 DBSCAN 这样的基于密度的算法能相当有效地弥补这些局限。DBSCAN 的核心思想是根据“密度”来对数据点进行分组，即把在高密度区域中彼此接近的数据点归为一类，并由较低密度的区域将它们分开。

但遗憾的是，使用 DBSCAN 时我们再次遇到一个被忽视的问题。让 DBSCAN 有时难以使用的原因之一是它的运行时间。直到最近，人们还认为 DBSCAN 的运行时间是 O(nlogn)，但已证明其最坏情况为 O(n²)。事实上，这一点也可以从下图中得到验证。它描绘了 DBSCAN 的运行时间随样本数量的变化：

可以清楚地看到，DBSCAN 与数据集大小呈二次关系。因此，越来越需要建立更高效的 DBSCAN 版本。DBSCAN++ 是迈向快速且可扩展（scalable）的 DBSCAN 的重要一步。

简单来说，DBSCAN++ 基于这样一个观察：我们只需对给定数据集中“n”个数据点的一个子集“m”计算密度估计，其中“m”可以远小于“n”即可正确聚类。DBSCAN++ 的有效性从这张图中可以明显看出。

如上所示，在一个包含 6 万个数据点的数据集上：

• DBSCAN++ 比 DBSCAN 快 20 倍。
• DBSCAN++ 产生了比 DBSCAN 更好的聚类得分。