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]

Label -1 — это noise (outlier).

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

DBSCAN vs KMeans

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

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

Outliers. KMeans — assigns каждую точку в кластер. DBSCAN — явно отмечает шум.

Computational cost. KMeans — O(n × k × i). DBSCAN — O(n × log n) с индексом, O(n²) без.

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

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

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

MinPts.

• Минимум: 2 × dimensionality. Для 2D — 4, для 10D — 20.
• Noise tolerance: больше MinPts → больше точек будут noise.
• Обычно 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')
# Локоть на графике — кандидат в ε

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

Geospatial clustering. Группы точек на карте (магазины, инциденты).

Anomaly detection. Outliers → аномалии (fraud, defects).

Customer segmentation. Группы клиентов по многомерным features.

Image segmentation. Группировка пикселей.

Log analysis. Кластеры похожих events или errors.

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

Плюсы DBSCAN

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

Произвольная форма. Находит elongated, ring-shaped, concave кластеры.

Noise handling. Естественно выделяет outliers.

Deterministic. В отличие от KMeans (random initialization), DBSCAN детерминирован (при фиксированном порядке точек).

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

Минусы

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

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

High dimensions. «Проклятие размерности» — distances concentrate в высоких измерениях. Работает плохо на >10-20 features. PCA/UMAP перед применением.

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

Scale-sensitive. Features должны быть нормализованы, иначе одна «доминирует» в distance.

HDBSCAN — улучшение

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

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

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

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

Normalization важна

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

Обязательный preprocessing:

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)

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

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

Оценка качества без ground truth:

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

from sklearn.metrics import silhouette_score

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

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

Calinski-Harabasz. Выше — лучше. Ratio between-cluster / within-cluster variance.

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

Real example: customer segmentation

Данные о покупках клиентов: 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)

Cluster -1 — outliers (unusual customers). Другие кластеры — behavioral segments.

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

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

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

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

Слишком большая размерность. >20 features без reduction — DBSCAN struggles.

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

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

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

FAQ

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

Зависит. KMeans — для сферических равномерных кластеров. DBSCAN — для irregular shapes с outliers.

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

Правило: 2 × количество features. Минимум 4. Больше для noisy data.

Работает ли на Big Data?

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

Можно ли использовать для streaming data?

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