Может ли алгоритм DBSCAN создать кластер с менее чем minPts?

Question

Я только что написал алгоритм DBSCAN, и мне интересно, может ли алгоритм DBSCAN разрешить кластер, где количество точек в кластере меньше, чем используемый параметр minPts.

Я использовал http://people.cs.nctu.edu.tw/~rsliang/dbscan/testdatagen.html чтобы проверить мою реализацию, и, кажется, она работает нормально, просто столкнувшись с этой проблемой.

Я провожу некоторые симуляции на примере набора данных, и я использую minPts из 3. Алгоритм 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 гарантированно состоит как минимум из одной базовой точки.

Поскольку пограничные точки, которые принадлежат более чем одному кластеру, будут "случайным образом" (обычно: "первым пришел") назначаться одному из кластеров, базовая точка не сможет сохранить / получить всех своих соседей. Таким образом, он может быть меньше, чем 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.

Наиболее близкой вещью к эталонной реализации, вероятно, является реализация DBSCAN в ELKI. Может быть, вы должны проверить, что ваши результаты соответствуют результатам ELKI. Потому что в вашем наборе данных, я полагаю, у вас тоже есть ошибки программирования.