DBSCAN

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

Основные понятия

Работа DBSCAN основана на двух глобальных параметрах, задаваемых пользователем: ε (эпсилон) — радиус окрестности, и MinPts — минимальное количество точек, необходимое для формирования плотной области. На основе этих параметров вводятся следующие определения:

• ε-окрестность точки: множество всех точек, расстояние от которых до данной точки не превышает ε.
• Ядровая точка: точка, в ε-окрестности которой содержится не менее MinPts точек (включая саму точку). Такие точки находятся внутри плотных областей.
• Граничная точка: точка, которая не является ядровой, но находится в ε-окрестности хотя бы одной ядровой точки. Она лежит на границе кластера.
• Шумовая точка (выброс): точка, не являющаяся ни ядровой, ни граничной. Она не принадлежит ни одному кластеру.
• Прямая достижимость по плотности: точка p прямо достижима по плотности из точки q, если q является ядровой точкой и p находится в её ε-окрестности.
• Достижимость по плотности: точка p достижима по плотности из точки q, если существует цепочка точек p₁, p₂, ..., pₙ, где p₁ = q, pₙ = p, и каждая следующая точка прямо достижима по плотности из предыдущей.
• Связность по плотности: две точки p и q связны по плотности, если существует такая точка o, что и p, и q достижимы по плотности из o.

Кластер в DBSCAN определяется как максимальное множество точек, связных по плотности.

Алгоритм работы

Процедура кластеризации DBSCAN выполняется следующим образом:

1. Для каждой точки в наборе данных определяется её ε-окрестность.
2. Если точка является ядровой (содержит не менее MinPts точек в своей окрестности), начинается формирование нового кластера. Точка помечается как посещённая и ей присваивается идентификатор кластера.
3. Все точки из ε-окрестности ядровой точки рекурсивно добавляются в тот же кластер. Для каждой из этих точек также проверяется, является ли она ядровой; если да, её окрестность также исследуется и добавляется в кластер. Этот процесс продолжается, пока все достижимые по плотности точки не будут присоединены.
4. Если точка не является ядровой и не может быть присоединена ни к одному кластеру, она помечается как шумовая.
5. Алгоритм завершается, когда все точки в наборе данных обработаны.

Ключевой особенностью является то, что порядок обработки точек не влияет на конечный результат (при условии, что все точки просматриваются). Однако реализация может зависеть от выбора первой точки для расширения кластера.

Выбор параметров

Правильный выбор ε и MinPts критически важен для успешной кластеризации. Эмпирических правил не существует, но есть распространённые подходы:

• MinPts: Минимальное значение — 3. Для двумерных данных часто выбирают 4 или 5. Для многомерных данных рекомендуется выбирать MinPts не меньше, чем размерность пространства плюс один (MinPts ≥ D+1). Более крупные значения делают кластеры более устойчивыми к шуму, но могут привести к тому, что разреженные кластеры будут объединены с шумом.
• ε: Определяется с помощью графика расстояний до k-го ближайшего соседа (k = MinPts). Для каждой точки вычисляется расстояние до её k-го ближайшего соседа, затем эти расстояния сортируются по возрастанию. Оптимальное значение ε соответствует точке на графике, где кривая начинает резко возрастать (так называемая «точка излома» или «локоть»). Это значение отражает порог, за которым точки начинают сильно удаляться друг от друга, переходя в шум.

Преимущества и недостатки

Преимущества:

• Не требует указания количества кластеров.
• Способен находить кластеры произвольной формы (вложенные, вытянутые, кольцевые).
• Устойчив к выбросам и автоматически идентифицирует шумовые точки.
• Требует всего два параметра.
• Имеет детерминированный результат (при фиксированном порядке точек).

Недостатки:

• Чувствителен к выбору параметров ε и MinPts, особенно к ε.
• Плохо работает с данными, имеющими сильно различающуюся плотность кластеров. Алгоритм может объединить разреженный кластер с шумом или разбить плотный кластер на несколько.
• Вычислительная сложность в наивной реализации составляет O(n²), где n — число точек. Однако с использованием пространственных индексов (например, R-деревьев) сложность может быть снижена до O(n log n).
• Неэффективен для очень больших наборов данных без применения оптимизаций.
• Параметр ε фиксирован для всего набора данных, что делает алгоритм непригодным для кластеризации данных с переменной плотностью.

Варианты и модификации

Для преодоления недостатков DBSCAN были разработаны различные модификации:

• OPTICS (Ordering Points To Identify the Clustering Structure) — алгоритм, который не требует явного задания ε, а создаёт расширенную упорядоченность точек, позволяющую визуально определить кластеры различной плотности.
• HDBSCAN (Hierarchical DBSCAN) — иерархическая версия, которая строит дендрограмму кластеризации и автоматически выбирает кластеры с различной плотностью, устраняя основной недостаток DBSCAN.
• ST-DBSCAN — расширение для пространственно-временных данных, учитывающее как пространственные, так и временные расстояния.
• GDBSCAN (Generalized DBSCAN) — обобщение, позволяющее использовать произвольные меры сходства и предикаты соседства.

Применение

DBSCAN широко применяется в различных областях:

• Геоинформационные системы (ГИС): кластеризация географических координат (например, местоположений преступлений, точек интереса, эпицентров землетрясений).
• Анализ изображений: сегментация изображений на основе плотности пикселей в цветовом пространстве.
• Анализ социальных сетей: выделение сообществ и групп пользователей на основе связей.
• Обнаружение аномалий: идентификация выбросов в данных (например, в финансовых транзакциях или сетевом трафике).
• Биоинформатика: кластеризация последовательностей ДНК или белков, анализ экспрессии генов.
• Обработка текстов: кластеризация документов по тематикам на основе векторных представлений (например, TF-IDF).

Источники

• Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96).
• Sander, J., Ester, M., Kriegel, H.-P., & Xu, X. (1998). Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. Data Mining and Knowledge Discovery, 2(2), 169–194.
• Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), 1-21.
• Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD).