DBSCAN: окрестность, ядро, граница и шум

<h2>Что задает DBSCAN</h2> <p>DBSCAN строит кластеры на основе плотностной связности. У алгоритма есть два главных параметра: радиус окрестности \(\varepsilon\) и минимальное число точек \(MinPts\), которое должно оказаться в этой окрестности. В учебной литературе второй параметр также часто обозначают буквой \(m\).</p> <p>Для объекта \(x\) его \(\varepsilon\)-окрестность задается так:</p> <p>$$U_\varepsilon(x)=\{u \in X: \rho(x,u) \le \varepsilon\}.$$</p> <p>Здесь \(\rho(x,u)\) — расстояние между объектами. Обычно в учебных двумерных примерах используют евклидово расстояние.</p> <h2>Типы точек</h2> <ul> <li><strong>Ядровая точка</strong>: в ее \(\varepsilon\)-окрестности не меньше \(MinPts\) объектов.</li> <li><strong>Граничная точка</strong>: сама не является ядровой, но попадает в окрестность некоторой ядровой точки.</li> <li><strong>Шумовая точка</strong>: не является ни ядровой, ни граничной.</li> </ul> <h2>Как растет кластер</h2> <p>Алгоритм берет ядровую точку и расширяет кластер через ее соседей. Если среди соседей есть другие ядровые точки, их окрестности тоже присоединяются. Так кластер может расти цепочкой и принимать произвольную форму.</p> <h2>Что получается на выходе</h2> <p>Результат DBSCAN — это разбиение части выборки на кластеры и отдельная пометка шумовых объектов. Поэтому метод удобен не только для группировки, но и для поиска выбросов.</p> <h2>Почему этот метод важен</h2> <p>Главное отличие DBSCAN от центроидных методов в том, что кластеру не нужен один центр. Группа может иметь произвольную форму, если ее можно пройти по цепочке плотных соседств. Поэтому DBSCAN естественно продолжает тему сложной геометрии из первого модуля.</p>