DB-scan

Краткая идея

• Рассмотрим для каждой точки $\varepsilon$ окрестность. Назовем ядерными точки, в окрестности которых $\geq k$ точек. Назовем граничными - не ядерные точки, в окрестности которых есть ядерная. Назовем шумовыми точки, не являющиеся ни ядерными, ни граничными.
• Построим граф, где вершинами будут ядерные точки, а ребрами соединены точки, находящиеся в окрестности друг друга. Кластера - компоненты связности в этом графе.
• Присоединим граничные точки к тем компонентам, к которым они лучше всего присоединяются
• Соединение ядерных точек - аггломеративная кластеризация, останавливающаяся на расстоянии eps
• Устойчивость к выбросам
• Как и сеточная кластеризация, определяет число кластеров и плохо работает с разными по плотности кластерами.

Подробнее в лекциях

• $O(N^{2}D)$, возможны модификации - $O(N\ln {N})$ для малых $D$, сеточный поиск объектов в области за $O(D)$.

Лекции Китова, с 62-64