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

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

Link to this sectionОсновные концепции и параметры#

Алгоритм работает путем определения окрестности вокруг каждой точки данных и подсчета того, сколько других точек попадает в эту область. Два основных гиперпараметра управляют этим процессом, требуя тщательной настройки гиперпараметров, чтобы соответствовать специфическим характеристикам данных:

• Epsilon (eps): Этот параметр задает максимальный радиус вокруг точки для поиска соседей. Он определяет дистанцию «досягаемости».
• Минимальное количество точек (minPts): Это значение задает минимальное количество точек данных, необходимое в радиусе Epsilon для формирования плотной области или «ядра».

На основе этих параметров DBSCAN классифицирует каждую точку в наборе данных как один из трех типов:

1. Ядровые точки: Точки, у которых есть как минимум minPts соседей в радиусе eps. Эти точки формируют внутреннюю часть кластера.

2. Граничные точки: Точки, которые находятся в радиусе eps от ядровой точки, но сами имеют меньше minPts соседей. Они образуют края кластера.

3. Шумовые точки: Точки, которые не являются ни ядровыми, ни граничными. По сути, они рассматриваются как выбросы, что полезно для таких задач, как обнаружение выбросов.

Link to this sectionDBSCAN против кластеризации K-Means#

Хотя оба метода являются фундаментальными для машинного обучения (ML), DBSCAN предлагает определенные преимущества перед кластеризацией K-Means в конкретных сценариях. K-Means полагается на центроиды и евклидово расстояние, часто предполагая, что кластеры являются выпуклыми или сферическими. Это может привести к низкой производительности на данных вытянутой или серповидной формы. Напротив, подход DBSCAN, основанный на плотности, позволяет ему следовать естественным контурам распределения данных.

Еще одно существенное различие заключается в инициализации. K-Means требует, чтобы ты заранее указал количество кластеров (k), что может быть затруднительно без предварительных знаний. DBSCAN выводит количество кластеров естественным образом из плотности данных. Кроме того, K-Means чувствителен к выбросам, так как он принудительно включает каждую точку в группу, что потенциально искажает центры кластеров. Способность DBSCAN помечать точки как шум предотвращает загрязнение корректных кластеров аномалиями данных, что обеспечивает более чистые результаты для последующих задач, таких как прогнозное моделирование.

Link to this sectionРеальные приложения#

DBSCAN широко применяется в отраслях, требующих пространственного анализа и надежной обработки шума.

• Геопространственный анализ: В городском планировании и логистике аналитики используют DBSCAN для группировки GPS-координат от парков доставки или сервисов райдшеринга. Определяя зоны высокой плотности высадки, компании могут оптимизировать планирование маршрутов и расположение складов. Например, ИИ в логистике часто включает кластеризацию точек доставки для повышения эффективности.
• Визуальное обнаружение аномалий: В производстве системы визуального контроля, работающие на таких моделях, как YOLO26, могут обнаруживать поверхностные дефекты. DBSCAN может кластеризовать координаты этих дефектов на карте изделия. Изолированные обнаружения могут быть отброшены как шум датчика, тогда как плотные кластеры указывают на систематический производственный брак, что вызывает оповещение для контроля качества.

Link to this sectionПример кода: Кластеризация центроидов обнаружений#

В рабочих процессах компьютерного зрения разработчики часто используют платформу Ultralytics для обучения детекторов объектов, а затем проводят постобработку результатов. Следующий пример демонстрирует, как использовать библиотеку sklearn для кластеризации центроидов обнаруженных объектов. Это помогает группировать пространственно связанные обнаружения, что может помочь в объединении нескольких bounding boxes для одного объекта или при выявлении групп объектов.

import numpy as np
from sklearn.cluster import DBSCAN

# Simulated centroids of objects detected by YOLO26
# [x, y] coordinates representing object locations
centroids = np.array(
    [
        [100, 100],
        [102, 104],
        [101, 102],  # Cluster 1 (Dense group)
        [200, 200],
        [205, 202],  # Cluster 2 (Another group)
        [500, 500],  # Noise (Outlier)
    ]
)

# Initialize DBSCAN with a radius (eps) of 10 and min_samples of 2
# This groups points close to each other
clustering = DBSCAN(eps=10, min_samples=2).fit(centroids)

# Labels: 0, 1 are cluster IDs; -1 represents noise
print(f"Cluster Labels: {clustering.labels_}")
# Output: [ 0  0  0  1  1 -1]

Link to this sectionИнтеграция с глубоким обучением#

Хотя DBSCAN — это классический алгоритм, он эффективно сочетается с современным глубоким обучением. Например, высокоразмерные признаки, извлеченные сверточной нейронной сетью (CNN), могут быть уменьшены с помощью методов снижения размерности, таких как PCA или t-SNE, перед применением DBSCAN. Этот гибридный подход позволяет выполнять кластеризацию сложных изображений на основе семантического сходства, а не просто расположения пикселей. Это особенно полезно в сценариях обучения без учителя, где обучающие данные с разметкой дефицитны, помогая исследователям эффективно организовывать огромные архивы неразмеченных изображений.