Что такое DBSCAN и в чём его преимущества?

DBSCAN: Плотностный алгоритм кластеризации

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

В отличие от K-means, который предполагает сферические кластеры и требует заранее задавать количество кластеров, DBSCAN находит кластеры самостоятельно на основе локальной плотности распределения точек.

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

Алгоритм опирается на два ключевых параметра:

• eps (epsilon) — радиус окрестности вокруг каждой точки
• min_samples — минимальное количество точек в окрестности eps для образования кластера

Основные шаги

# Псевдокод алгоритма
for каждую точку P:
    if P уже посещена:
        continue
    
    найти соседей P в радиусе eps
    
    if количество соседей < min_samples:
        P — выброс (шум)
    else:
        создать новый кластер
        добавить P и всех соседей в кластер
        рекурсивно добавить соседей соседей (если они плотные)

Пример реализации

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_blobs
import numpy as np

# Сгенерировать данные с произвольной формой
X, y_true = make_blobs(n_samples=300, centers=3, n_features=2, random_state=42)

# Применить DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X)

# labels содержит номера кластеров и -1 для выбросов
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_outliers = list(labels).count(-1)

print(f"Найдено кластеров: {n_clusters}")
print(f"Выбросов: {n_outliers}")

Преимущества DBSCAN

1. Автоматическое определение количества кластеров

В отличие от K-means, не нужно заранее знать K. Алгоритм сам определяет количество кластеров на основе структуры данных.

2. Произвольная форма кластеров

DBSCAN находит кластеры любой формы, а не только сферические:

from sklearn.datasets import make_moons

# Два полукруга
X, y_true = make_moons(n_samples=200, noise=0.05)

# K-means потерпит неудачу на таких данных
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2)
kmeans.fit(X)  # Результат неправильный

# DBSCAN справится хорошо
dbscan = DBSCAN(eps=0.1, min_samples=5)
dbscan.fit(X)  # Результат корректный

3. Встроенное обнаружение выбросов

Точки, которые не входят ни в один кластер (шум), помечаются как -1. Это очень полезно для аномалии детектшена:

labels = dbscan.fit_predict(X)
outliers = X[labels == -1]
inliers = X[labels >= 0]

print(f"Выбросов найдено: {len(outliers)}")

4. Эффективность на больших данных

При правильной индексации (например, KD-Tree) DBSCAN имеет сложность O(n log n), что хорошо для больших датасетов.

5. Нет необходимости в инициализации

В отличие от K-means, нет проблемы с локальными оптимумами или чувствительностью к начальной инициализации центроидов.

Недостатки и ограничения

Чувствительность к параметрам

Выбор eps и min_samples критичен и может потребовать экспериментов:

# Слишком малый eps — слишком много выбросов
dbscan_small = DBSCAN(eps=0.1, min_samples=5)

# Слишком большой eps — все точки в одном кластере
dbscan_large = DBSCAN(eps=10.0, min_samples=5)

# Правильный eps — найти методом перебора или визуализацией
from sklearn.neighbors import NearestNeighbors
neighbors = NearestNeighbors(n_neighbors=5)
neighbors_fit = neighbors.fit(X)
distances, indices = neighbors_fit.kneighbors(X)
distances = np.sort(distances[:, -1], axis=0)
# Найти локоть (elbow) на графике расстояний

Проблема с данными разной плотности

Если в данных кластеры с существенно разной плотностью, один eps может не подойти.

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

• Геопространственные данные: выявление скоплений координат
• Обнаружение аномалий: странные паттерны в данных
• Неизвестное количество кластеров: исследовательский анализ
• Произвольные формы кластеров: социальные сети, данные сенсоров

Выводы

DBSCAN — мощный алгоритм для задач, где K-means неприменим. Его главное преимущество — автоматизация определения количества кластеров, обнаружение выбросов и способность находить кластеры произвольной формы. Главный недостаток — критическая зависимость от параметров eps и min_samples.