DBSCAN: кластеризация на основе плотности

Что такое DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — алгоритм кластеризации, который находит группы плотно расположенных точек и отмечает изолированные как шум.

В отличие от KMeans, не требует задавать число кластеров заранее и хорошо находит кластеры произвольной формы.

Придуман в 1996 (Ester, Kriegel, Sander, Xu). Получил награду SIGKDD Test of Time Award в 2014.

Как работает DBSCAN

Два параметра:

• ε (eps) — радиус поиска соседей.
• MinPts — минимальное число точек в радиусе, чтобы точка считалась «плотной».

Классификация точек:

Core point. Имеет не менее MinPts соседей в радиусе ε. Это ядро кластера.

Border point. В радиусе ε от какого-то core point, но сам имеет менее MinPts соседей.

Noise. Не core, не border. Выброс.

Алгоритм:

1. Выбираем случайную точку.
2. Находим соседей в радиусе ε.
3. Если соседей ≥ MinPts → это core, формируем кластер.
4. Расширяем кластер, добавляя density-reachable точки.
5. Переходим к следующей необработанной точке.

Повторяем пока все точки не классифицированы.

Пример на Python

from sklearn.cluster import DBSCAN
import numpy as np

# Данные: координаты клиентов
X = np.array([[1, 1], [1, 2], [2, 1], [8, 8], [8, 9], [9, 8], [25, 80]])

dbscan = DBSCAN(eps=2, min_samples=2)
labels = dbscan.fit_predict(X)
print(labels)
# [0, 0, 0, 1, 1, 1, -1]

Метка -1 — это шум (выброс).

Два кластера: {(1,1), (1,2), (2,1)} и {(8,8), (8,9), (9,8)}. Точка (25, 80) — выброс.

DBSCAN vs KMeans

Число кластеров. KMeans — нужно знать заранее (гиперпараметр). DBSCAN — определяется автоматически.

Форма кластеров. KMeans — сферические (евклидово расстояние). DBSCAN — произвольная форма.

Выбросы. KMeans присваивает каждую точку в кластер. DBSCAN явно отмечает шум.

Вычислительная сложность. KMeans — O(n × k × i). DBSCAN — O(n × log n) с индексом, O(n²) без.

Когда что. KMeans — для равномерных, сферических кластеров. DBSCAN — для кластеров разной формы с выбросами.

Выбор параметров

Это самая сложная часть. Плохие параметры → плохие кластеры.

MinPts.

• Минимум: 2 × размерность. Для 2D — 4, для 10D — 20.
• Устойчивость к шуму: больше MinPts → больше точек попадёт в шум.
• Обычно 3-5 для стандартных случаев.

ε (eps).

• Подобрать с помощью k-distance graph.
• Для каждой точки вычислить расстояние до k-го ближайшего соседа.
• Отсортировать и построить график.
• «Локоть» на графике — хороший ε.

Пример выбора ε через k-distance:

from sklearn.neighbors import NearestNeighbors
import matplotlib.pyplot as plt

k = 5  # MinPts
neighbors = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = neighbors.kneighbors(X)
distances = np.sort(distances[:, k-1])

plt.plot(distances)
plt.xlabel('Points sorted by distance')
plt.ylabel(f'{k}-th nearest neighbor distance')
# Локоть на графике — кандидат в ε

Типичные применения

Гео-кластеризация. Группы точек на карте (магазины, инциденты).

Выявление аномалий. Выбросы → аномалии (фрод, дефекты).

Сегментация клиентов. Группы клиентов по многомерным признакам.

Сегментация изображений. Группировка пикселей.

Анализ логов. Кластеры похожих событий или ошибок.

В продуктовой аналитике часто используется для нахождения паттернов поведения пользователей без предположений о форме кластеров.

Плюсы DBSCAN

Не нужно задавать k. Важное преимущество при разведочном анализе.

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

Обработка шума. Естественно выделяет выбросы.

Детерминированность. В отличие от KMeans (случайная инициализация), DBSCAN детерминирован при фиксированном порядке точек.

Только два параметра. Простой в освоении.

Минусы

Чувствительность к параметрам. Неправильные ε и MinPts → плохие результаты. Требуется итерация.

Разная плотность. Плохо справляется с кластерами разной плотности. Для таких — HDBSCAN.

Высокая размерность. «Проклятие размерности» — расстояния концентрируются в высоких измерениях. Работает плохо на >10-20 признаков. PCA/UMAP перед применением.

Граничные точки могут быть неоднозначны. Точка на границе двух кластеров — в каком кластере? Зависит от порядка обработки.

Чувствительность к масштабу. Признаки должны быть нормализованы, иначе один «доминирует» в расстоянии.

HDBSCAN — улучшение

HDBSCAN (Hierarchical DBSCAN) — современное развитие:

• Не нужен ε. Только MinPts.
• Находит кластеры разной плотности.
• Иерархическая структура — можно выбирать степень детализации.
• Устойчив к выбросам и шуму.

import hdbscan
clusterer = hdbscan.HDBSCAN(min_cluster_size=5)
labels = clusterer.fit_predict(X)

Для большинства современных задач HDBSCAN предпочтительнее DBSCAN.

Нормализация важна

DBSCAN использует евклидово расстояние. Если признаки на разных шкалах (age 20-80 и income 1000-100000), расстоянием доминирует income.

Обязательный препроцессинг:

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Теперь DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X_scaled)

Кластеризация и обучение без учителя — мощные техники для сегментации. В тренажёре Карьерник есть задачи по ML и сегментации пользователей.

Метрики качества

Оценка качества без разметки:

Silhouette Score. От -1 до 1. Чем выше, тем лучше разделены кластеры.

from sklearn.metrics import silhouette_score

# Исключаем шум (-1) перед расчётом
mask = labels != -1
score = silhouette_score(X[mask], labels[mask])

Davies-Bouldin Index. Ниже — лучше. Измеряет компактность относительно разделения.

Calinski-Harabasz. Выше — лучше. Отношение межкластерной и внутрикластерной дисперсии.

Эти метрики не всегда работают для DBSCAN (предпочитают сферические формы), но дают базовый сигнал.

Пример: сегментация клиентов

Данные о покупках клиентов: recency, frequency, monetary (RFM).

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN

df = pd.read_csv('customers.csv')
features = df[['recency_days', 'frequency', 'monetary']]

scaler = StandardScaler()
X = scaler.fit_transform(features)

dbscan = DBSCAN(eps=0.5, min_samples=20)
df['cluster'] = dbscan.fit_predict(X)

# Анализ кластеров
summary = df.groupby('cluster').agg({
    'recency_days': 'mean',
    'frequency': 'mean',
    'monetary': 'mean',
    'customer_id': 'count'
})
print(summary)

Кластер -1 — выбросы (необычные клиенты). Другие кластеры — поведенческие сегменты.

Типичные ошибки

Не нормализовать признаки. Самая частая ошибка. Результат: один признак доминирует, кластеризация бессмысленна.

Слишком маленький ε. Всё становится шумом. Нет кластеров.

Слишком большой ε. Всё в одном кластере.

Слишком большая размерность. >20 признаков без снижения размерности — DBSCAN плохо справляется.

Игнорировать выбросы. Метка -1 — важная информация. Анализируйте, что это за точки.

Читайте также

• K-means кластеризация
• RFM-анализ клиентов
• Feature scaling в ML
• Unsupervised learning

FAQ

DBSCAN или KMeans — что лучше?

Зависит. KMeans — для сферических равномерных кластеров. DBSCAN — для произвольных форм с выбросами.

Как выбрать MinPts?

Правило: 2 × количество признаков. Минимум 4. Больше — для зашумлённых данных.

Работает ли на больших данных?

DBSCAN — O(n²) наивно, O(n log n) с индексом. До 100K-1M точек работает. Выше — HDBSCAN или mini-batch подходы.

Можно ли использовать для потоковых данных?

Классический DBSCAN — нет. Есть варианты (Incremental DBSCAN, DBSCAN++), но сложнее в реализации.