Як призначати точки до кластерів?

Основний принцип DBSCAN — досяжність за густиною, саме він визначає призначення точок до кластерів. Точки призначаються до кластерів на основі наступного:

• Безпосередньо досяжна за густиною: точка $p$ є безпосередньо досяжною за густиною від основної точки $q$, якщо $p$ знаходиться в межах ε-радіусу від $q$. Усі точки, безпосередньо досяжні за густиною від основної точки, автоматично належать до того ж кластера, що й основна точка;

• Досяжна за густиною: точка $p$ є досяжною за густиною від основної точки $q$, якщо існує ланцюжок точок $p_1$, $p_2$, ..., $p_n$, де $p_1 = q$, $p_n = p$, і кожна $p_{i+1}$ є безпосередньо досяжною за густиною від $p_i$. Це означає, що навіть якщо точка не знаходиться безпосередньо в ε-радіусі основної точки, вона все одно може належати до того ж кластера, якщо з'єднана з основною точкою через ланцюжок безпосередньо досяжних точок;

• З'єднані за густиною: дві точки $p$ і $q$ є з'єднаними за густиною, якщо існує основна точка $o$, така що і $p$, і $q$ є досяжними за густиною від $o$. Усі з'єднані за густиною точки належать до одного кластера.

Прикордонні точки призначаються до кластера першої основної точки, з якої вони виявляються досяжними. Шумові точки за визначенням не є досяжними за густиною від жодної основної точки, тому не призначаються до жодного кластера. Вони розглядаються як викиди.

По суті, DBSCAN формує кластери шляхом з'єднання основних точок, які є досяжними за густиною одна від одної, а прикордонні точки успадковують кластер основної точки, з якою вони пов'язані.