5

我已经在 R 中实现了 DBSCAN 算法，并且我将集群分配与fpc 库的 DBSCAN 实现相匹配。对 fpc 库 dbscan 示例中给出的合成数据进行测试：

n <- 600
x <- cbind(runif(10, 0, 10)+rnorm(n, sd=0.2), runif(10, 0, 10)+rnorm(n, sd=0.3))

使用以下参数进行聚类：

eps = 0.2
MinPts = 5

我正在将 的集群分配fpc::dbscan与我的dbscan. 运行的最大值显示每个点都被两种实现方式相同地分类。

但是在某些情况下，在我的实现中，与 fpc 实现中不同的集群分配了 1 或 2 个点，少数情况下 5 或 6 个点被分配给不同的集群。我注意到只有边界点分类不同。在绘制之后，我看到集群成员在实现中不匹配的点处于这样的位置，这样它就可以分配给它周围的任何集群，这取决于它首先是从哪个集群的种子点被发现的。

我正在显示一个 150 点的图像（以避免混乱），其中 1 点分类不同。请注意，在我的实现中，失配点簇数总是大于 fpc 实现。

聚类图。

顶部插图是 fpc::dbscan，底部插图是我的 dbscan 实现

聚类图。 顶部插图是 fpc::dbscan，底部插图是我的 dbscan 实现

注意我的实现中的不同点标有感叹号（！）我还上传了不匹配部分的缩放图像：

我的 dbscan 实现输出

+是核心点

o是边界点

-是噪声点

!突出不同点

我的 dbscan 实现

fpc::dbscan 实现输出

三角形是核心点 彩色圆圈是边界点 黑色圆圈是噪声点 在此处输入图像描述

另一个例子：

我的 dbscan 实现输出

在此处输入图像描述

fpc::dbscan 实现输出

在此处输入图像描述

编辑

等 xy 缩放示例

根据 Anony-Mousse 的要求

在不同的情况下，有时我的实现似乎正确分类了不匹配点，有时 fpc 实现似乎正确分类了不匹配点。见下文：

fpc::dbscan （带有三角形图）似乎正确分类了不匹配点

在此处输入图像描述

我的 dbscan 实现（带有 + 绘图）似乎正确分类了不匹配点

在此处输入图像描述

问题

  • 我是聚类分析的新手，因此我有另一个问题：这些类型的差异是否允许？

  • 在我的实现中，我从提供的第一个点扫描到最后一个点，并且fpc::dbscan这些点也以相同的顺序扫描。在这种情况下，两个实现都应该!从同一个集群中心发现失配点（用 标记）。此外，我还生成了一些fpc::dbscan将点标记为噪声的情况，但我的实现将其分配给了一些集群。在这种情况下，为什么会出现这种差异？

应要求提供代码段。

4

1 回答 1

5

已知 DBSCAN 与边界点的顺序有关。它们将被分配到首次发现它们的集群。如果一个边界点不密集，而是在来自不同簇的两个密集点附近，则可以将其分配给其中任何一个。

这就是为什么 DBSCAN 经常被描述为“顺序无关，除了边界点”。

尝试改组数据（或反转！），然后重新运行您的算法。结果应该改变。

由于我假设您的实现和 fpc 实现都没有索引支持（以加快范围查询并使算法在其中运行O(n log n)），我猜想其中一种实现是以正序处理点，另一种是以反向顺序处理点。'''更新：索引不应该起太大作用，因为它们不会跨集群改变顺序，只在一个集群内改变'''。

“产生”这种差异的另一种选择是

  • 保持每个点的第一个（非噪声）簇分配（IIRC官方DBSCAN伪代码）
  • 保留每个点的最后一个集群分配（fbc::dbscan似乎这样做）

这些也会对不止一次聚类的边界点的对象产生不同的结果。还有可能将这些点分配给两个集群，这将产生数据集的非严格分区。通常，严格划分的好处比完全确定的结果更重要。

不要误会我的意思：“覆盖”策略fbc::dbscan并不会显着改变结果。我什至可能会自己实现它。

是否有任何非边界点受到影响？

于 2012-06-02T08:25:53.120 回答