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

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

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

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

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

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

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

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

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

DBSCAN против кластеризации K-Means#

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

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

Реальные приложения#

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

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

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

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

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]

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

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