Что такое алгоритм DBSCAN и density-based clustering

Что проверяют

Понимаете ли вы, чем плотностная кластеризация отличается от разбиения пространства на шары. Вопрос почти всегда продолжается тем, как вы подбирали радиус на своих данных и почему привычный метод центроидов дал бы здесь неверные кластеры.

Как отвечать

DBSCAN собирает кластеры из областей высокой плотности. Параметров два: радиус окрестности eps и минимальное число точек minPts в этой окрестности. Точка называется корневой, если в её окрестности не меньше minPts точек, считая её саму. Кластер растёт только через корневые точки, их окрестности сливаются. Некорневая точка, попавшая в окрестность корневой, становится граничной: в кластер она входит, но дальше его не расширяет. Всё, что не попало никуда, помечается шумом.

Отсюда свойства, которые и стоит назвать. Число кластеров не задаётся заранее. Форма произвольная, а не шарообразная, поэтому вытянутые и вложенные структуры находятся там, где метод центроидов режет их пополам. Шум выделяется явно, что удобно для поиска аномалий. Сложность порядка n log n с пространственным индексом и квадратичная без него.

Подбор параметров: minPts отталкивается от размерности, обычно не меньше числа признаков плюс один; eps ищут по графику расстояния до k-го соседа, в точке перегиба. Признаки перед этим обязательно масштабировать, иначе радиус меряет бессмыслицу.

Где спотыкаются

Не разделяют корневые и граничные точки и потому не могут объяснить недетерминированность. Граничная точка, достижимая из двух кластеров, достанется тому, который обошли раньше, тогда как корневые точки устойчивы к порядку обхода.

Применяют метод к данным с кластерами разной плотности. Единый радиус либо объявит разреженные группы шумом, либо сольёт плотные в одну; это встроенное ограничение, и лечится оно иерархическим вариантом с переменной плотностью.

Тащат метод в пространство большой размерности без её снижения. Расстояния там сближаются, разница между ближним и дальним соседом исчезает, и плотность перестаёт различать точки.