在两个DBSCAN实现中,群集分配有时会有所不同
pho*_*xis 5 r cluster-analysis data-mining dbscan
我在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.最大运行显示两个实现都对每个点进行了相同的分类.
但是在某些情况下,在我的实现中,1或2个点以及一些罕见的5或6个点被分配给不同的集群,而不是fpc实现中的集群.我注意到只有边界点分类不同.在绘图之后,我已经看到在实现中集群成员资格不匹配的点处于这样的位置,使得它可以被分配给其周围的任何集群,这取决于首先发现它的集群的种子点.
我正在显示150点的图像(以避免混乱),其中1点分类不同.请注意,我的实现中的不匹配点簇数始终大于fpc实现.
集群的情节.
顶部插入是fpc :: dbscan,底部插入是我的dbscan实现
注意我的实现中不同的点标有感叹号(!)我还上传了不匹配部分的缩放图像:
我的dbscan实现输出
+ 是核心要点
o 是边境点
- 是噪音点
! 突出了不同点
fpc :: dbscan实现输出
三角形是核心点,彩色圆圈是边界点,黑色圆圈是噪点
另一个例子:
我的dbscan实现输出
fpc :: dbscan实现输出
编辑
等于xy缩放的例子
按照Anony-Mousse的要求
在不同的情况下,有时似乎我的实现已正确地对错配点进行了分类,有时似乎fpc实现已正确地对错配进行了分类.见下文:
fpc :: dbscan(带有三角形图)似乎已正确地对错配点进行了分类
我的dbscan实现(带有+ plot)实际上似乎已正确地对错配点进行了分类
题
我是集群分析的新手,因此我有另一个问题:这些类型的差异是否允许？
在我的实现中,我正在扫描从第一点到最后一点,因为它是以
fpc::dbscan相同的顺序扫描的.在这种情况下,两个实现都应该!从同一个集群中心发现不匹配点(标记为).此外,我已经生成了一些fpc::dbscan将点标记为噪声的情况,但我的实现将其分配给某些集群.在这种情况下,为什么会出现这种差异？
根据要求提供代码段.
众所周知,DBSCAN是依赖于边界点的顺序.它们将被分配到首次发现它们的集群.如果边界点不密集,但是在来自不同聚类的两个密集点的密度中,则可以将其分配给任一个.
这就是为什么DBSCAN经常被描述为"除了边界点之外的顺序无关".
尝试改组数据(或反转!),然后重新运行算法.结果应该改变.
因为我假设你和fpc实现都没有索引支持(加速范围查询并使算法运行O(n log n)),我猜其中一个实现是按正向顺序处理点,另一个是按向后顺序处理.'''更新:索引不应该扮演很大的角色,因为它们不会跨群集更改顺序,只能在一个群集内'''.
"产生"这种差异的另一个选择是
- 保持每个点的第一个(非噪声)簇分配(IIRC官方DBSCAN伪代码)
- 保持每个点的最后一个簇分配(
fbc::dbscan似乎这样做)
这些也会对作为多个集群的边界点的对象生成不同的结果.还有可能将这些点分配给两个cluter,这将产生数据集的非严格分区.通常,进行严格分区的好处比具有完全确定性的结果更重要.
不要误会我的意思:"覆盖"策略fbc::dbscan并没有实质性地改变结果.我甚至可能会以这种方式实现它.
是否有任何非边境点受到影响？