r - 集群分配有时在两个 DBSCAN 实现中有所不同

Question

我已经在 R 中实现了 DBSCAN 算法，并且我正在将集群分配与 fpc library 的 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 的实现.运行的最大值显示每个点都被两种实现方式分类相同。
但是在某些情况下，在我的实现中，1 或 2 个点和一些罕见的 5 或 6 个点被分配给了与 fpc 实现中不同的集群。我注意到只有边界点分类不同。绘图后，我看到集群成员在实现中不匹配的点处于这样的位置，因此可以将其分配给其周围的任何集群，具体取决于它首先从哪个集群的种子点被发现。
我展示了一个 150 点的图像(以避免困惑)，其中 1 点分类不同。请注意，在我的实现中，失配点簇数总是大于 fpc 实现。
集群图。
顶部插图是 fpc::dbscan，底部插图是我的 dbscan 实现

注意我的实现中的不同点用感叹号 (!)
我还上传了不匹配部分的放大图像:

我的 dbscan 实现输出 +是核心点 o是边界点 -是噪声点 !突出不同点


fpc::dbscan 实现输出
三角形是核心点
彩色圆圈是边界点
黑圈是噪声点


另一个例子:
我的 dbscan 实现输出


fpc::dbscan 实现输出


编辑
相等的 x-y 缩放示例
根据 Anony-Mousse 的要求
在不同的情况下，有时似乎我的实现正确分类了不匹配点，有时似乎 fpc 实现正确分类了不匹配。见下文:
fpc::dbscan(带有三角形图)似乎已正确分类不匹配点

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

题

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

在我的实现中，我从提供的第一个点到最后一个点进行扫描，也在 fpc::dbscan 中点以相同的顺序扫描。在这种情况下，两个实现都应该发现来自同一个聚类中心的不匹配点(由 ! 标记)。我也产生了一些情况，其中 fpc::dbscan将一个点标记为噪声，但我的实现将其分配给某些集群。在这种情况下，为什么会出现这种差异？

应要求提供代码段。

Answer 1

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

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

尝试打乱数据(或反转!)，然后重新运行您的算法。结果应该改变。

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

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

保留每个点的第一个(非噪声)集群分配(IIRC 官方 DBSCAN 伪代码)

保留每个点的最后一个集群分配(fbc::dbscan 似乎是这样做的)

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

不要误会我的意思: fbc::dbscan 的“覆盖”策略不会实质性地改变结果。我什至可能会自己那样实现它。

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