machine-learning - DBSCAN 算法可以创建少于 minPts 的簇吗？

Question

我刚刚编写了 DBSCAN 算法，我想知道 DBSCAN 算法是否可以允许簇中的点数小于所使用的 minPts 参数的簇。

我一直在使用http://people.cs.nctu.edu.tw/~rsliang/dbscan/testdatagen.html验证我的实现，它似乎工作正常，只是遇到了这个问题。

我正在针对示例数据集运行一些模拟，并且我一直使用 3 的 minPts。DBSCAN 算法通常会从数据集中创建 2 个点(但从来不是 1 个)的簇。这是设计使然还是我搞砸了实现？

一些示例数据，eps = 0.1，minPts = 3。

 0.307951851891331 0.831249445598223
 0.0223402371734102 0.352948855307395
 0.780763753587736 0.691021379870838
 0.950537940464233 0.849805725668467
 0.66559538881555 0.603627873865714
 0.983049284658883 0.320016804300256
 0.710854941844407 0.646746252033276
 0.404260418566065 0.610378857986247
 0.740377815785062 0.899680181825385
 0.430522446721104 0.597713506593236
 0.0365937198682659 0.109160974206944
 0.378702778545536 0.115744969861463
 0.765229786171219 0.568206346858389
 0.760991609078362 0.59582572271853
 0.970256112036414 0.480310371834929
 0.110018607280226 0.541528500403058
 0.679553015939683 0.951676915377228
 0.730563320094051 0.806108465793593
 0.30542559935964 0.500680956757013
 0.740971321585109 0.670210885196091
 0.877572476806851 0.221948942738561
 0.882196086404005 0.674841667374057
 0.808923079077584 0.740714808339586
 0.935197343553974 0.438659039064617
 0.283511740287539 0.271373094185895
 0.0740317893559261 0.602333299630477
 0.30702819223843 0.0683579570932118
 0.31839294653311 0.198790877684388
 0.452546667052687 0.906595267311947
 0.587719069136176 0.212557406729347
 0.930029770792476 0.354712217745703
 0.879549613632052 0.185285016980621
 0.493609266585488 0.441520784255825
 0.640463788360573 0.759178026467179
 0.916182931939225 0.598151952772472

输出集群:

(Cluster: 1 { 0.780763753587736,0.691021379870838 }, { 0.66559538881555,0.603627873865714 }, { 0.710854941844407,0.646746252033276 }, { 0.765229786171219,0.568206346858389 }, { 0.760991609078362,0.59582572271853 }, { 0.740971321585109,0.670210885196091 }, { 0.882196086404005,0.674841667374057 }, { 0.808923079077584,0.740714808339586 }, { 0.916182931939225,0.598151952772472 })
(Cluster: 2 { 0.983049284658883,0.320016804300256 }, { 0.970256112036414,0.480310371834929 }, { 0.935197343553974,0.438659039064617 }, { 0.930029770792476,0.354712217745703 })
(Cluster: 3 { 0.404260418566065,0.610378857986247 }, { 0.430522446721104,0.597713506593236 })
(Cluster: 4 { 0.740377815785062,0.899680181825385 }, { 0.679553015939683,0.951676915377228 }, { 0.730563320094051,0.806108465793593 })
(Cluster: 5 { 0.378702778545536,0.115744969861463 }, { 0.30702819223843,0.0683579570932118 })
(Cluster: 6 { 0.110018607280226,0.541528500403058 }, { 0.0740317893559261,0.602333299630477 })
(Cluster: 7 { 0.877572476806851,0.221948942738561 }, { 0.879549613632052,0.185285016980621 })
(Cluster: 8 { 0.283511740287539,0.271373094185895 }, { 0.31839294653311,0.198790877684388 })

Answer 1

是的。

DBSCAN 中的集群仅保证由至少 1 个核心点组成。

由于属于超过 1 个簇的边界点将被“随机”(通常:先到)分配给其中一个簇，因此核心点可能无法保留/获取它的所有邻居。因此，它可能小于 minPts。

一维示例:minPts=4，epsilon=1:

0.0 0.5 1.0     2.0     3.0 3.5 4.0
 |-------X-------|                   Core point at 1.0, Cluster 1.
                 |-------X-------|   Core point at 3.0, Cluster 2.

所有其他点都不是核心点。由于点 2.0 不是核心点，因此它不连接两个集群。其中一个集群将有 4 个成员，另一个集群只有 3 个成员。

最接近引用实现的可能是 ELKI 中的 DBSCAN 实现。也许您应该检查您的结果是否与 ELKI 的结果匹配。因为在您的数据集中，我相信您也有一些编程错误。