为DBSCAN(R)选择eps和minpts？

Question

我一直在寻找这个问题的答案,所以我希望有人可以帮助我.我在R中的fpc库中使用dbscan.例如,我正在查看USArrests数据集,并在其上使用dbscan,如下所示:

library(fpc)
ds <- dbscan(USArrests,eps=20)

在这种情况下,选择eps仅仅是通过反复试验.但是,我想知道是否有可用于自动选择最佳eps/minpts的功能或代码.我知道有些书建议制作一个与最近邻居的第k个分类距离的图.也就是说,x轴表示"根据到第k个最近邻居的距离排序的点",并且y轴表示"第k个最近邻居距离".

这种类型的绘图有助于为eps和minpts选择合适的值.我希望我已经为某人提供了足够的信息来帮助我.我想张贴一张我的意思,但我仍然是新手,所以暂不发布图像.

Answer 1

没有选择minPts的一般方法.这取决于你想要找到什么.低minPts意味着它将从噪声中构建更多的簇,因此不要选择它太小.

对于epsilon,有各个方面.它再次归结为选择适用于此数据集和此 minPts和此距离函数以及此规范化的任何内容.你可以尝试做一个knn距离直方图并在那里选择一个"膝盖",但可能没有可见的或多个.

OPTICS是DBSCAN的后继者,不需要epsilon参数(除了索引支持的性能原因,请参阅Wikipedia).它更好,但我相信在R中实现是一件痛苦的事情,因为它需要高级数据结构(理想情况下,加速的数据索引树和优先级队列的可更新堆),R是关于矩阵运算的.

天真地,人们可以想象OPTICS同时执行Epsilon的所有值,并将结果放在集群层次结构中.

然而,您需要检查的第一件事 - 几乎与您将要使用的任何聚类算法无关 - 是确保您具有有用的距离函数和适当的数据规范化.如果距离退化,则无法使用聚类算法.

Answer 2

管理DBSCAN的epsilon参数的一种常见且流行的方法是计算数据集的k距离图.基本上,您为每个数据点计算k-最近邻居(k-NN),以了解不同k的数据密度分布.KNN很方便,因为它是一种非参数方法.选择minPTS(强烈依赖于您的数据)后,将k固定为该值.然后使用与距离较低的k距离图(对于固定k)对应的k距离作为epsilon.

Answer 3

MinPts

正如Anony-Mousse所解释的那样,"一个低的minPts意味着它将从噪声中构建更多的集群,所以不要选择它太小." .

minPts最好由熟悉数据的领域专家设置.不幸的是,很多情况下我们不了解领域知识,特别是在数据规范化之后.一种启发式方法是使用ln(n),其中n是要聚类的点的总数.

小量

有几种方法可以确定它:

1)k距离图

在minPts = k的聚类中,我们期望核心点和边界点的k距离在一定范围内,而噪声点可以具有更大的k距离,因此我们可以在k距离图中观察到拐点. .然而,有时可能没有明显的膝盖,或者可能有多个膝盖,这使得很难做出决定

2)DBSCAN扩展,如OPTICS

OPTICS生成层次化集群,我们可以通过目视检查从层次集群中提取重要的平面集群,OPTICS实现在Python模块pyclustering中可用.DBSCAN和OPTICS的原作者之一也提出了一种自动提取扁平簇的方法,无需人为干预,您可以阅读本文.

3)灵敏度分析

基本上我们想要选择一个半径,它能够聚集更真实的常规点(与其他点类似的点),同时检测出更多的噪声(离群点).我们可以绘制一定比例的常规点(点属于一个簇)VS. epsilon分析,我们将不同的epsilon值设置为x轴,将相应的常规点百分比设置为y轴,希望我们能够发现一个段,其中常规点值的百分比对epsilon值更敏感,并且我们选择上限epsilon值作为我们的最优参数.

Answer 4

有关选择参数的详细信息，请参阅下面第 10 页的论文。11：

Schubert, E.、Sander, J.、Ester, M.、Kriegel, HP 和 Xu, X.（2017 年）。重新审视 DBSCAN，重新审视：为什么以及如何（仍然）使用 DBSCAN。ACM 数据库系统事务 (TODS)，42(3)，19。

• 对于二维数据：使用默认值 minPts=4 (Ester et al., 1996)
• 对于超过 2 个维度：minPts=2*dim (Sander et al., 1998)

一旦您知道要选择哪些 MinPts，您就可以确定 Epsilon：

• 用 k=minPts 绘制 k 距离（Ester 等人，1996 年）
• 找到图中的“肘部”--> k 距离值是您的 Epsilon 值。