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

DBSCAN (Пространственная кластеризация приложений с шумом на основе плотности) — мощный алгоритм обучения без учителя, используемый для выявления отдельных групп в данных на основе плотности. В отличие от традиционных методов кластеризации, которые предполагают наличие сферических кластеров или требуют заранее заданного количества групп, DBSCAN находит области высокой плотности, разделённые областями низкой плотности. Благодаря этому алгоритм может обнаруживать кластеры произвольной формы и размера, что делает его особенно эффективным для анализа сложных наборов данных из реального мира, где внутренняя структура неизвестна. Важное преимущество этого алгоритма — встроенное обнаружение аномалий: он автоматически классифицирует точки в областях низкой плотности как шум, а не принудительно относит их к кластеру.

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

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

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

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

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

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

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

DBSCAN и кластеризация K-Means#

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

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

Практические применения#

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

• Геопространственный анализ: В городском планировании и логистике аналитики используют DBSCAN для группировки GPS-координат парков доставки или сервисов совместных поездок. Выявляя зоны высадки с высокой плотностью, компании могут оптимизировать планирование маршрутов и расположение складов. Например, AI в логистике часто включает кластеризацию остановок доставки для повышения эффективности.
• Обнаружение аномалий на основе компьютерного зрения: В производстве системы визуального контроля на базе таких моделей, как 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. Такой гибридный подход позволяет кластеризовать сложные изображения на основе семантического сходства, а не только положения пикселей. Это особенно полезно в сценариях обучения без учителя, где размеченных данных для обучения мало, помогая исследователям эффективно организовывать обширные архивы неразмеченных изображений.