DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (пространственная кластеризация приложений с шумом на основе плотности) — алгоритм обучения без учителя, который объединяет близко расположенные точки в кластеры, а точки в разреженных областях помечает как шум. Мартин Эстер, Ханс-Петер Кригель, Йёрг Зандер и Сяовэй Сюй представили алгоритм на конференции KDD в 1996 году. Алгоритму не нужно заранее задавать число кластеров, он находит кластеры любой формы — например, кольца, полумесяцы или извилистые дороги, — а пометка «шум» служит простым вариантом обнаружения аномалий. Алгоритм целиком задается двумя параметрами: радиусом окрестности и числом точек, необходимым для признания окрестности плотной.

Ядровые точки, граничные точки и шум#

DBSCAN рассматривает окрестность каждой точки — множество точек на расстоянии eps от нее — и подсчитывает число ее элементов:

• Ядровая точка: в ее окрестности находится не менее min_samples точек; в реализации scikit-learn учитывается и сама точка. Ядровые точки образуют плотную внутреннюю область кластера.
• Граничная точка: у нее слишком мало соседей, чтобы считаться ядровой, но она находится на расстоянии не более eps от ядровой точки. Граничные точки образуют края кластера.
• Точка шума: не относится ни к одной из этих категорий, поэтому не принадлежит кластеру и получает метку -1.

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

Выбор eps и min_samples#

Радиус eps важнее всего и зависит от масштаба данных, поэтому сначала признаки обычно стандартизируют. Если радиус слишком мал, большинство точек останется шумом; если слишком велик — соседние кластеры сольются в один. Обычно расстояние от каждой точки до ее k-го ближайшего соседа сортируют, задавая k равным min_samples, а eps выбирают в точке перегиба кривой, где расстояния начинают быстро расти. Более высокие значения min_samples повышают устойчивость кластеризации к шуму и часто используются для больших или зашумленных наборов данных. В пространствах высокой размерности, например в пространстве эмбеддингов изображений, расстояния между точками становятся похожими друг на друга, поэтому перед запуском DBSCAN специалисты часто применяют снижение размерности, например метод главных компонент (PCA).

DBSCAN, K-Means и HDBSCAN#

Для кластеризации методом k-средних нужно заранее задать число кластеров; алгоритм относит каждую точку к ближайшему центроиду, поэтому отдает предпочтение компактным круглым кластерам и принудительно включает выбросы в какую-либо группу. DBSCAN определяет число кластеров по плотности и оставляет выбросы за их пределами. Слабое место алгоритма — единое значение eps: если плотность кластеров сильно различается, одним радиусом не удается отделить разреженные кластеры от шума, а плотные кластеры — друг от друга. HDBSCAN решает эту проблему, по сути запуская DBSCAN при всех значениях eps и сохраняя наиболее стабильные кластеры. Оба алгоритма, а также связанный с ними OPTICS, входят в модуль кластеризации scikit-learn.

В этом примере кластеризуются два пересекающихся полумесяца с 20 добавленными случайными выбросами, а результаты сравниваются с истинными группами с помощью скорректированного индекса Рэнда, где 1.0 соответствует идеальному совпадению:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Скрипт выводит 2 кластера и 15 шумовых точек для DBSCAN, а скорректированный индекс Рэнда равен 0.97 для DBSCAN и 0.20 для k-средних. DBSCAN выделяет оба полумесяца и отделяет от них попавшие в другие области выбросы, тогда как k-средних делит полумесяцы прямой границей, хотя алгоритму задали правильное число кластеров.

Примеры применения в реальных условиях#

• Обработка данных LiDAR: в конвейерах автономных транспортных средств и робототехники точки земли удаляют из скана LiDAR, а оставшиеся точки в 3D объединяют в отдельные препятствия. Часто выбирают кластеризацию на основе плотности, поскольку число объектов заранее неизвестно.
• Постобработка результатов обнаружения: центры рамок обнаружений YOLO26, доступные как result.boxes.xywh, можно кластеризовать с помощью DBSCAN, чтобы находить группы людей в толпе или повторяющиеся места дефектов на производственной линии; отдельные обнаружения при этом отбрасываются как шум.
• Мониторинг мошенничества и датчиков: Транзакции или показания с меткой -1 находятся далеко от всех плотных групп нормального поведения и становятся кандидатами на проверку.
• Геопространственный анализ: Компании доставки и заказа поездок группируют точки GPS, чтобы находить часто посещаемые места и популярные точки посадки. DBSCAN в Scikit-learn принимает metric="haversine" для широты и долготы в радианах; в этом случае eps — это угол на единичной сфере, поэтому радиус в 100 метров равен eps = 0.1 / 6371 при среднем радиусе Земли 6 371 км.