DBSCAN

Коротко

Definition

DBSCAN — это плотностный алгоритм кластеризации, который объединяет точки в области высокой плотности и помечает разреженные точки как шум.

DBSCAN расшифровывается как Density-Based Spatial Clustering of Applications with Noise.

Главная идея:

• кластер — это область, где точки расположены достаточно плотно;
• точки в разреженных областях считаются шумом;
• количество кластеров не нужно задавать заранее;
• кластеры могут иметь произвольную форму.

В отличие от k-means, DBSCAN не ищет центроиды и не предполагает, что кластеры должны быть компактными и округлыми.

Интуиция

Представим карту точек. Если в какой-то области много точек рядом друг с другом, это плотная область. DBSCAN считает такую область кластером.

Если точка стоит далеко от остальных, она не похожа на часть плотной группы. DBSCAN может пометить её как шум.

Алгоритм работает примерно так:

1. Найти точку.
2. Посмотреть, сколько соседей есть рядом с ней.
3. Если соседей достаточно много, начать новый кластер.
4. Расширять кластер через соседние плотные точки.
5. Всё, что не принадлежит плотным областям, пометить как шум.

Поэтому DBSCAN хорошо находит не только круглые кластеры, но и вытянутые, изогнутые или неправильные формы.

Формальное описание

У DBSCAN есть два главных параметра:

• $\epsilon$ или eps — радиус окрестности;
• min_samples — минимальное число точек в окрестности, чтобы точка считалась ядровой.

Для точки $p$ её $\epsilon$-окрестность:

$$N_{\epsilon }(p)=\{q\mid d(p,q)\le \epsilon \}$$

где $d(p,q)$ — выбранная метрика расстояния.

DBSCAN делит точки на три типа.

Тип точки	Описание
Core point	Ядровая точка: в её $\epsilon$-окрестности есть минимум min_samples точек
Border point	Пограничная точка: сама не ядровая, но находится рядом с ядровой точкой
Noise point	Шум: не является ни ядровой, ни пограничной

Кластер строится как связная область ядровых точек вместе с достижимыми от них пограничными точками.

Метки кластеров обычно имеют вид:

$$\{-1,0,1,\dots ,K-1\}$$

где $-1$ означает шум.

Входы и выходы

Компонент	Описание
Вход	Матрица признаков объектов
Выход	Номер кластера для каждого объекта или метка шума
Тип задачи	Кластеризация
Тип обучения	Обучение без учителя
Целевая переменная	Отсутствует
Метка шума	Обычно $-1$

Примеры задач:

• поиск групп объектов в пространственных данных;
• обнаружение выбросов;
• кластеризация экспериментов по похожести;
• поиск плотных групп материалов по свойствам;
• группировка точек на двумерных или многомерных признаках;
• первичный анализ данных, где число кластеров заранее неизвестно.

Как обучается

DBSCAN не обучается как параметрическая модель с весами. Он строит кластеры напрямую по расстояниям между объектами.

Алгоритм:

1. Выбрать непосещённую точку $p$.
2. Найти все точки в радиусе $\epsilon$ от $p$.
3. Если соседей меньше min_samples, временно пометить $p$ как шум.
4. Если соседей достаточно, создать новый кластер.
5. Добавить в кластер точку $p$ и её соседей.
6. Для каждого нового соседа проверить, является ли он ядровой точкой.
7. Если сосед тоже ядровой, добавить его соседей в тот же кластер.
8. Повторять, пока кластер больше не расширяется.
9. Перейти к следующей непосещённой точке.

Важная особенность: точка, сначала помеченная как шум, позже может стать пограничной точкой некоторого кластера.

Функция потерь

У DBSCAN нет функции потерь в привычном смысле, как у линейной регрессии, логистической регрессии или нейросетей.

Алгоритм не минимизирует MSE, cross-entropy или другую дифференцируемую функцию. Вместо этого он применяет правило плотностной достижимости:

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

Поэтому качество DBSCAN оценивают не по training loss, а по метрикам кластеризации и смысловой интерпретации результата.

Гиперпараметры

Главные гиперпараметры DBSCAN:

Гиперпараметр	Что контролирует
eps	Радиус окрестности
min_samples	Минимальная плотность для ядровой точки
metric	Метрика расстояния
algorithm	Способ поиска соседей
leaf_size	Технический параметр для некоторых алгоритмов поиска соседей

Интерпретация eps:

• слишком маленький eps — многие точки станут шумом;
• слишком большой eps — разные кластеры могут слиться в один.

Интерпретация min_samples:

• маленький min_samples — алгоритм легче создаёт кластеры, но может принять шум за структуру;
• большой min_samples — нужны более плотные области, больше точек может стать шумом.

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

Когда использовать

DBSCAN стоит использовать, когда:

• число кластеров заранее неизвестно;
• ожидаются кластеры произвольной формы;
• в данных есть шум и выбросы;
• важно отделить плотные группы от одиночных точек;
• данные можно осмысленно сравнивать через выбранную метрику расстояния;
• k-means даёт слишком искусственные округлые кластеры.

DBSCAN особенно полезен для exploratory data analysis, когда нужно быстро понять, есть ли в данных плотные группы.

Когда не использовать

DBSCAN плохо подходит, если:

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

Если кластеры имеют разную плотность, можно рассмотреть HDBSCAN. Если нужны простые центроиды и фиксированное число групп, можно использовать k-means.

Метрики оценки

Для DBSCAN используют метрики кластеризации:

• silhouette score;
• Davies–Bouldin index;
• Calinski–Harabasz index;
• Adjusted Rand Index, если есть истинные метки;
• Normalized Mutual Information, если есть истинные метки;
• доля точек, помеченных как шум.

Подробнее: Метрики качества кластеризации.

Важно: silhouette score может быть неидеален для DBSCAN, потому что он хуже отражает кластеры сложной формы и наличие шума. Поэтому результат нужно проверять не только численно, но и содержательно.

Типичные ошибки понимания

Ошибка 1. Думать, что DBSCAN всегда лучше k-means

DBSCAN лучше k-means для кластеров сложной формы и данных с шумом, но он не универсален. Если кластеры компактные, хорошо разделены и нужно фиксированное $K$, k-means может быть проще и удобнее.

Ошибка 2. Не масштабировать признаки

DBSCAN основан на расстояниях. Если признаки имеют разные масштабы, eps будет работать некорректно.

Ошибка 3. Считать шум ошибкой алгоритма

Метка шума — не обязательно плохой результат. Часто это полезная часть DBSCAN: алгоритм явно показывает объекты, которые не принадлежат плотным группам.

Ошибка 4. Подбирать eps случайно

eps сильно влияет на результат. Его лучше подбирать осмысленно: через k-distance plot, перебор вариантов и проверку интерпретируемости кластеров.

Ошибка 5. Ожидать обычного predict для новых объектов

DBSCAN в классической форме не строит явную функцию предсказания. Чтобы отнести новый объект к кластеру, нужно дополнительно сравнивать его с уже найденными core points или использовать другую модель поверх меток DBSCAN.

Минимальный пример

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
 
X = np.array([
    [1.0, 1.1],
    [1.1, 0.9],
    [0.9, 1.0],
    [5.0, 5.1],
    [5.2, 4.9],
    [20.0, 20.0],
])
 
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
 
model = DBSCAN(
    eps=0.5,
    min_samples=2,
)
 
labels = model.fit_predict(X_scaled)
 
print(labels)

В этом примере DBSCAN ищет плотные группы объектов. Точка, которая находится далеко от остальных, может получить метку -1, то есть быть распознана как шум.

Связанные понятия

Что знать перед этим

• Предобработка данных
• Задачи кластеризации