dbscan - 最大簇跨度的设置限制

Question

通过我的DBSCAN的理解,有可能为你指定的,比如说一个小量,100米-因为DBSCAN考虑到密度可达性和不 直接密度可达发现群集时-与群集最终在其中的最大距离任意两点之间> 100米.在更极端的可能性,似乎有可能,你可以设置为100米ε和1公里集群结束: 参见[2] [6]这阵图像从scikit在学习的时候可能发生的例子.(我非常愿意被告知我是一个完全白痴,并且误解了DBSCAN,如果这就是这里发生的事情.)

是否存在基于密度的算法,如DBSCAN,但是考虑到群集中任意两点之间的最大距离的某种阈值？

Answer 1

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

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

我相信,你实际上甚至都没有寻找聚类:聚类是发现数据结构的任务.结构可以更简单(例如k均值)或复杂(例如通过分层聚类和k均值发现的任意形状的聚类).

您可能正在寻找矢量量化 - 将数据集减少到较小的代表集 - 或设置封面 - 找到给定集合的最佳覆盖 - 而不是.

但是,我的印象是你不确定你需要什么以及为什么.

DBSCAN的一个优势在于它具有密度连接组件形式的结构的数学定义.这是一个强大的(除了一些罕见的边界情况)明确定义的数学概念,DBSCAN算法是发现这种结构的最佳效率算法.

然而,直接密度可达性不定义有用的(分区)结构.它只是不将数据分区为不相交的分区.

如果您不需要这种强大的结构(即您不像"结构发现"那样进行聚类,但您只想像在矢量量化中那样压缩数据),那么您可以尝试"冠层预聚类".它可以看作是为聚类设计的预处理步骤.本质上,它就像DBSCAN,除了它使用两个epsilon值,并且不保证结构在任何方面都是最优的,但在很大程度上取决于数据的排序.如果你然后适当地预处理它,它仍然是有用的.除非您处于分布式设置中,否则冠层预聚类至少与完整的DBSCAN运行一样昂贵.由于松散的要求(特别是"簇"可能重叠,并且预期对象属于多个"簇"),因此更容易并行化.

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