35

我一直在寻找这个问题的答案很长一段时间，所以我希望有人能帮助我。我正在使用 R 中 fpc 库中的 dbscan。例如，我正在查看 USArrests 数据集并在其上使用 dbscan，如下所示：

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

在这种情况下，选择 eps 只是通过反复试验。但是我想知道是否有可用于自动选择最佳 eps/minpts 的函数或代码。我知道有些书建议制作到最近邻居的第 k 个排序距离的图。即，x 轴表示“根据与第 k 个最近邻的距离排序的点”，y 轴表示“第 k 个最近邻距离”。

这种类型的绘图有助于为 eps 和 minpts 选择合适的值。我希望我已经提供了足够的信息来帮助我。我想张贴我的意思的图片，但是我还是个新手，所以还不能张贴图片。

4

6 回答 6

30

没有选择 minPts 的通用方法。这取决于你想找到什么。较低的 minPts 意味着它将从噪声中构建更多的集群，因此不要选择太小。

对于 epsilon，有多个方面。它再次归结为选择对这个数据集和这个minPts 和这个距离函数和这个归一化有效的任何东西。您可以尝试做一个 knn 距离直方图并在那里选择一个“膝盖”，但可能没有可见的一个或多个。

OPTICS 是不需要 epsilon 参数的 DBSCAN 的继承者（除了索引支持的性能原因，请参阅 Wikipedia）。它要好得多，但我认为在 R 中实现起来很痛苦，因为它需要高级数据结构（理想情况下，用于加速的数据索引树和用于优先级队列的可更新堆），而 R 完全是关于矩阵运算的。

天真地，可以将 OPTICS 想象为同时处理 Epsilon 的所有值，并将结果放入集群层次结构中。

但是，您需要检查的第一件事 - 几乎独立于您要使用的任何聚类算法 - 是确保您有一个有用的距离函数和适当的数据规范化。如果您的距离退化，则没有聚类算法将起作用。

于 2012-10-15T10:23:24.407 回答
15

管理 DBSCAN 的 epsilon 参数的一种常见且流行的方法是计算数据集的 k 距离图。基本上，您计算每个数据点的 k 最近邻 (k-NN)，以了解不同 k 的数据的密度分布。KNN 很方便，因为它是一种非参数方法。一旦您选择了一个 minPTS（很大程度上取决于您的数据），您将 k 固定为该值。然后，您使用与具有低斜率的 k 距离图（对于您的固定 k）区域相对应的 k 距离作为 epsilon。

于 2013-09-02T09:12:43.887 回答
15

最小分数

正如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 值作为我们的最佳参数。

于 2018-02-01T08:09:58.450 回答
11

有关选择参数的详细信息，请参阅下面第 4 页的论文。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 et al., 1996)
  • 在图中找到“肘部”-> k 距离值是您的 Epsilon 值。
于 2019-01-09T17:03:07.447 回答
1

如果你有资源，你也可以测试一堆epsilon和minPts值，看看有什么用。我使用expand.gridand来做到这一点mapply。

# Establish search parameters.
k <- c(25, 50, 100, 200, 500, 1000)
eps <- c(0.001, 0.01, 0.02, 0.05, 0.1, 0.2)

# Perform grid search.
grid <- expand.grid(k = k, eps = eps)

results <- mapply(grid$k, grid$eps, FUN = function(k, eps) {
  cluster <- dbscan(data, minPts = k, eps = eps)$cluster
  sum <- table(cluster)
  cat(c("k =", k, "; eps =", eps, ";", sum, "\n"))
})
于 2020-06-16T14:12:07.767 回答
0

请参阅此网页，第 5 节：http: //www.sthda.com/english/wiki/dbscan-density-based-clustering-for-discovering-clusters-in-large-datasets-with-noise-unsupervised-machine-learning

它提供了有关如何查找 epsilon 的详细说明。MinPts ...不是那么多。

于 2016-11-29T23:35:13.433 回答