python - dbscan - 设置最大集群跨度限制

Question

根据我对 DBSCAN 的理解，您可以指定 epsilon，例如 100 米，并且 — 因为 DBSCAN 考虑了密度可达性 而不 < em>direct density-reachability 寻找簇时——最终得到一个簇，其中任意两点之间的最大距离大于 100 米。在更极端的可能性中，您似乎可以将 epsilon 设置为 100 米并最终得到 1 公里的集群: see [2][6] in this array of images from scikit learn有关何时可能发生的示例。 (我非常愿意被告知我是个彻头彻尾的白痴，如果这就是这里发生的事情，我会误解 DBSCAN。)

是否有像 DBSCAN 这样基于密度的算法，但考虑了集群中任意两点之间最大距离的某种阈值？

Answer 1

DBSCAN 确实没有对集群施加总大小限制。

epsilon 值最好解释为分隔两个簇的间隙大小(最多包含 minpts-1 个对象)。

我相信，实际上您甚至不是在寻找聚类:聚类是发现数据结构的任务。结构可以更简单(如k-means)或复杂(如层次聚类和k-means发现的任意形状的聚类)。

您可能正在寻找 vector quantization - 将数据集减少为较小的代表集 - 或 set cover - 寻找给定集合的最佳覆盖 - 而不是。

但是，我也觉得您并不确定自己需要什么以及为什么。

DBSCAN 的一个优势在于它具有密度连通分量形式的结构的数学定义。这是一个强大且(除了一些罕见的边界情况)定义明确的数学概念，DBSCAN 算法是发现这种结构的最有效算法。

Direct 然而，密度可达性并未定义有用的(分区)结构。它只是不会将数据分成不相交的分区。

如果您不需要这种强大的结构(即您不像“结构发现”那样进行聚类，而只想像矢量量化那样压缩数据)，您可以使用“冠层预聚类”一试。它可以看作是为聚类设计的预处理步骤。本质上，它类似于 DBSCAN，只是它使用两个 epsilon 值，并且不保证结构在任何方面都是最优的，而是在很大程度上取决于数据的顺序。如果您随后对其进行适当的预处理，它仍然有用。除非您处于分布式环境中，否则树冠预聚类至少与完整的 DBSCAN 运行一样昂贵。由于需求松散(特别是“集群”可能重叠，对象应该属于多个“集群”)，更容易并行化。

哦，您也可能只是在寻找完全链接层次聚类。如果您在所需高度处切割树状图，则生成的簇在任何两个对象之间都应具有所需的最大距离。唯一的问题是层次聚类通常是 O(n^3)，即它不能扩展到大型数据集。 DBSCAN 在良好的实现中以 O(n log n) 运行(具有索引支持)。