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

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

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

DBSCAN определяет кластеры на основе плотности точек данных в заданном пространстве. Он работает с двумя ключевыми параметрами:

• Эпсилон (ε или eps): Этот параметр определяет радиус окрестности вокруг точки данных. Все точки в пределах этого расстояния считаются соседними.
• Minimum Points (MinPts) (Минимальное количество точек): Это минимальное количество точек данных (включая саму точку), необходимое для формирования плотной области или кластера.

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

1. Основные точки: Точка является основной, если у нее есть как минимум MinPts внутри его eps окрестность. Эти точки являются внутренней частью кластера.
2. Граничные точки: Точка является граничной точкой, если она находится внутри eps окрестность основной точки, но не имеет достаточного количества соседей, чтобы быть основной точкой. Эти точки образуют край кластера.
3. Шумовые точки (выбросы): Точка считается шумовой, если она не является ни основной точкой, ни граничной точкой. Это выбросы, которые не принадлежат ни к одному кластеру.

Алгоритм начинается с произвольной точки и извлекает ее окрестность. Если это основная точка, создается новый кластер. Затем алгоритм итеративно расширяет кластер, добавляя к нему все непосредственно достижимые соседние точки, и этот процесс продолжается до тех пор, пока к какому-либо кластеру больше нельзя добавить точки. Вы можете увидеть визуальную реализацию в документации scikit-learn.

Реальные приложения AI/ML

Способность DBSCAN выявлять шум и обнаруживать нелинейные кластеры делает его чрезвычайно ценным в различных областях:

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

DBSCAN и Ultralytics

Экосистема Ultralytics в основном ориентирована на модели обучения с учителем, такие как Ultralytics YOLO для решения задач, включая обнаружение объектов, классификацию изображений и сегментацию экземпляров. Хотя DBSCAN является методом обучения без учителя, его принципы применимы в более широком контексте компьютерного зрения (CV).

Например, после выполнения обнаружения объектов с помощью такой модели, как YOLO11, на видеозаписи оживленной улицы, DBSCAN можно применить к центральным координатам обнаруженных ограничивающих рамок. Этот этап постобработки может сгруппировать отдельные обнаружения пешеходов в отдельные толпы, обеспечивая более высокий уровень понимания сцены. Понимание распределения данных также имеет решающее значение при подготовке наборов данных для обучения. Разведочный анализ данных с использованием DBSCAN может выявить закономерности или аномалии в наборе данных, которыми можно управлять и визуализировать с помощью таких платформ, как Ultralytics HUB.

Отличия от смежных терминов

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