Участник:Даниил Глазков/Алгоритм кластеризации DBSCAN

Свойства и структура алгоритма

Общее описание алгоритма

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

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

Особенности объектов, с которыми работает DBSCAN:

• Входные данные представлены набором точек в пространстве, где каждая точка характеризуется набором признаков. Для двухмерного пространства точки могут быть представлены как (x, y), но алгоритм также применим и для данных с большим числом признаков.

• Алгоритм подходит для плотностных структур, где кластеры имеют разную форму и размеры, что делает его особенно полезным для географических и пространственных данных.

Основные параметры DBSCAN:

• eps — радиус, в пределах которого точки считаются соседними и могут быть включены в один кластер.

• minPts — минимальное количество точек, необходимых для того, чтобы область считалась "плотной" и могла образовать кластер.

Алгоритм выделяет три типа точек:

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

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

Математическое описание алгоритма

Пусть имеется множество точек [math]\displaystyle{ \mathcal{D} = \{p_1, p_2, \dots, p_n\} }[/math] в d-мерном пространстве, где каждая точка [math]\displaystyle{ p_i \in \mathbb{R}^d }[/math] характеризуется d признаками. Определим формально параметры:

1. Радиус eps > 0.
2. Параметр плотности [math]\displaystyle{ minPts \in \mathbb{N} }[/math], указывающий минимальное количество точек, необходимых для формирования кластера.

Для каждой точки [math]\displaystyle{ p_i \in \mathcal{D} }[/math], определим её eps-окрестность:

[math]\displaystyle{ N_{\varepsilon}(p_i) = \{p_j \in \mathcal{D} \mid d(p_i, p_j) \leq \varepsilon\} }[/math]

где [math]\displaystyle{ d(p_i, p_j) }[/math] — метрика расстояния, например, Евклидово расстояние.

Для определения точек в терминах DBSCAN вводятся следующие условия:

• Ядровая точка: точка [math]\displaystyle{ p_i }[/math] считается ядровой, если [math]\displaystyle{ |N_{\varepsilon}(p_i)| \geq minPts }[/math].

• Граничная точка: точка [math]\displaystyle{ p_j }[/math] считается граничной, если [math]\displaystyle{ p_j }[/math] находится в \eps-окрестности ядровой точки, но сама не является ядровой.

• Шумовая точка: точка <marh> p_k </math> не является ни ядровой, ни граничной, если [math]\displaystyle{ |N_{\varepsilon}(p_k)| \lt minPts }[/math] и она не принадлежит eps-окрестности ни одной из ядровых точек.

Процесс кластеризации:

1. Для каждой точки [math]\displaystyle{ p_i \in \mathcal{D} }[/math]:

• Если [math]\displaystyle{ p_i }[/math] является ядровой точкой, то создаётся новый кластер C.

• Все точки в eps-окрестности [math]\displaystyle{ p_i }[/math] добавляются в кластер C.

• Процесс расширения продолжается рекурсивно для всех ядровых точек в окрестности.

2. Граничные точки добавляются в кластеры, если они находятся в окрестности eps хотя бы одной ядровой точки, но не создают новые кластеры.

3. Все оставшиеся точки, не принадлежащие ни одному кластеру, считаются шумовыми.

Таким образом, DBSCAN создает множество кластеров [math]\displaystyle{ \{C_1, C_2, \dots, C_k\} }[/math], где k — количество обнаруженных кластеров, а точки, не входящие ни в один из [math]\displaystyle{ C_i }[/math], классифицируются как шумовые точки.

Вычислительное ядро алгоритма

Основные этапы ядра алгоритма:

1. Разделение данных Набор данных [math]\displaystyle{ D }[/math] разбивается на несколько непересекающихся подмножеств [math]\displaystyle{ D_1, D_2, \ldots, D_k }[/math]. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

Рис.1. Разбиение данных

2. Локальное выполнение DBSCAN На каждом подмножестве [math]\displaystyle{ D_i }[/math] выполняется локальная версия алгоритма DBSCAN:

• Поиск [math]\displaystyle{ \varepsilon }[/math]-соседей для каждой точки в [math]\displaystyle{ D_i }[/math].

• Проверка, является ли точка плотностным ядром в рамках текущего подмножества [math]\displaystyle{ D_i }[/math].

• Формирование локальных кластеров.

Эти операции аналогичны стандартному алгоритму DBSCAN, но выполняются только на локальных подмножествах, что снижает вычислительную сложность в каждом

3. Слияние границ кластеров. После обработки всех подмножеств необходимо объединить кластеры, пересекающие границы [math]\displaystyle{ D_i }[/math] и [math]\displaystyle{ D_j }[/math]. Это достигается путём:

• Если граничная точка [math]\displaystyle{ P \in D_i }[/math] имеет соседей в [math]\displaystyle{ D_j }[/math], то выполняется пересечения кластеров

Рис.2. Объединение кластеров из разных процессов

Макроструктура алгоритма

1. Разбиение данных на подмножества: На этом этапе набор данных [math]\displaystyle{ D }[/math] разбивается на несколько непересекающихся подмножеств [math]\displaystyle{ D_1, D_2, \ldots, D_k }[/math]
2. Кластеризация: Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
3. Слияние кластеров на границах: Если точка [math]\displaystyle{ P \in D_i }[/math] имеет соседей в [math]\displaystyle{ D_j }[/math], то выполняется пересечения кластеров

Схема реализации последовательного алгоритма

Псевдокод для реализации алгоритма DBSCAN

# Инициализация
clusters = []
visited = set()
noise = set()

# Основная итерация
for P in dataset:
    if P in visited:
        continue
    visited.add(P)
    
    # Поиск соседей
    neighbors = find_neighbors(P, epsilon)
    
    if len(neighbors) < MinPts:
        noise.add(P)
        continue
    
    # Создание нового кластера
    cluster = []
    clusters.append(cluster)
    cluster.append(P)
    
    # Расширение кластера
    expand_cluster(P, neighbors, cluster, visited, epsilon, MinPts)

# Возврат результатов
return clusters, noise

Последовательная сложность алгоритма

Разбиение данных на подмножества:

• Функция для разбиения имеет временную сложность O(N), так как она проходит по всем точкам и проверяет их принадлежность к региону.

Кластеризация точек:

• Основная часть алгоритма — это функция кластеризация DBSCAN, которая выполняет поиск соседних точек и расширение кластера. В худшем случае, алгоритм может обрабатывать все точки, что приводит к временной сложности [math]\displaystyle{ O(N^2) }[/math] для одного процесса. Поскольку алгоритм параллельный и точки распределены между процессами, временная сложность для каждого процесса будет [math]\displaystyle{ O((N/P)^2) }[/math], где P — количество процессов.

Объединение пересекающихся кластеров:

• Функция объединения кластеров имеет временную сложность [math]\displaystyle{ O(N^2) }[/math], так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

Общая временная сложность алгоритма для одного процесса составляет [math]\displaystyle{ O(N^2) }[/math]. В параллельной версии с P процессами временная сложность для каждого процесса составляет [math]\displaystyle{ O((N/P)^2) }[/math]. Однако, учитывая накладные расходы на коммуникацию между процессами, общая временная сложность параллельного алгоритма будет примерно [math]\displaystyle{ O(N^2/P) }[/math].

Информационный граф

Информационный граф DBSCAN

Разбиение данных

• Операция: Разделение входного набора данных X на подмножества [math]\displaystyle{ X_1, X_2, ..., X_n }[/math].
• Входные данные: Набор точек X (объем: N точек, где N — общее количество точек в наборе данных).
• Выходные данные: Подмножества [math]\displaystyle{ X_1, X_2, ..., X_n }[/math] (объем: примерно N/n точек на одно подмножество, где n — количество подмножеств).

Применение DBSCAN к подмножествам

• Операция: Применение алгоритма DBSCAN к каждому подмножеству [math]\displaystyle{ X_i }[/math] (где i = 1, 2, ..., n).
• Входные данные: Подмножество [math]\displaystyle{ X_i }[/math] (объем: примерно N/n точек).
• Выходные данные: Кластеризованные подмножества [math]\displaystyle{ C_1, C_2, ..., C_n }[/math] (каждое содержит метки кластеров для точек в [math]\displaystyle{ X_i }[/math], включая -1 для шумовых точек).

Объединение кластеров

• Операция: Объединение кластеров из всех подмножеств в единый набор кластеров.
• Входные данные: Кластеризованные подмножества [math]\displaystyle{ C_1, C_2, ..., C_n }[/math] (общий объем: N меток кластеров).
• Выходные данные: Итоговые кластеризованные данные (объем: N точек с соответствующими метками кластеров, где -1 указывает на шумовые точки).

Зависимости

• Выходные данные этапа "Разбиение данных" используются в качестве входных для каждой операции "Применение DBSCAN к подмножеству".

• Выходные данные всех операций "Применение DBSCAN к подмножеству" используются в качестве входных для операции "Объединение кластеров".

Ресурс параллелизма алгоритма

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

1. Деление на регионы: На этом шаге пространственные данные делятся на подрегионы, что можно выполнить за [math]\displaystyle{ O(\log M) }[/math] шагов, где M — количество подрегионов.
2. Параллельный поиск соседей и кластеризация: Каждый подрегион обрабатывается независимо, что позволяет достичь хорошего параллелизма, поскольку для каждого региона можно запускать отдельные потоки. Это даёт сложность [math]\displaystyle{ O(\log N) }[/math], где N — число точек в каждом
3. Объединение кластеров: Слияние кластеров на границах может быть выполнено с использованием параллельного обмена данными, что также позволяет эффективно использовать параллельные ресурсы.

Таким образом, параллельная сложность алгоритма близка к [math]\displaystyle{ O(\log M) }[/math] для деления и [math]\displaystyle{ O(\log N) }[/math] для обработки данных в каждом подрегионе. Ресурс параллелизма выражается через массовый параллелизм, где каждый процесс работает с отдельным подрегионом, а скошенный параллелизм проявляется в объединении кластеров на границах регионов.

Входные и выходные данные алгоритма

• Входные данные: Множество точек [math]\displaystyle{ X = \{x_1, x_2, \ldots, x_n\} }[/math], где каждая точка [math]\displaystyle{ x_i }[/math] представлена в [math]\displaystyle{ d }[/math]-мерном пространстве. Объем данных: n — количество точек, d — размерность пространства. В типичных задачах n может быть порядка [math]\displaystyle{ 10^3 – 10^6 }[/math], а d — от нескольких единиц до сотен.

• Выходные данные: Размеченное множество точек X, где каждой точке [math]\displaystyle{ x_i }[/math] сопоставлен номер кластера [math]\displaystyle{ C_i }[/math]. Значение [math]\displaystyle{ C_i = -1 }[/math] означает, что точка является шумовой (не принадлежит ни одному кластеру). Объем выходных данных: n меток кластеров, каждая из которых занимает O(1) памяти, что в сумме составляет O(n).

Программная реализация алгоритма

Масштабируемость алгоритма и его реализации

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

• Масштабируемость с точки зрения числа точек - в случае использования пространственных структур (например, KD-деревьев), сложность поиска соседей уменьшается, что улучшает производительность при увеличении числа точек

Таким образом, алгоритм сохраняет свою эффективность при увеличении объема данных и числа вычислительных узлов.

Существующие реализации алгоритма

Краткое описание библиотек с указанием, поддерживают ли они распараллеливание:

1. Scikit-learn (Python):

• Распараллеливание: Нет.
• Описание: Стандартная реализация DBSCAN для малых и средних данных.
• Документация Scikit-learn DBSCAN: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

2. HDBSCAN (Python):

• Распараллеливание: Да.
• Описание: Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.
• Документация HDBSCAN: https://hdbscan.readthedocs.io/en/latest/

3. cuML (GPU-ускоренная библиотека от NVIDIA):

• Распараллеливание: Да, использует GPU для ускорения вычислений.
• Описание: GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.
• Документация cuML DBSCAN: https://docs.rapids.ai/api/cuml/stable/

4. Apache Spark MLlib (Java/Scala/Python):

• Распараллеливание: Да, для распределенной обработки данных в кластере.
• Описание: Распределенная версия DBSCAN для кластеризации на больших данных.
• Документация Spark MLlib: https://spark.apache.org/mllib/

Литература

1. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, № 7, С. 36-39.

2. https://www.sciencedirect.com/science/article/pii/S0165178123002159#sec0002

3. https://oaji.net/articles/2023/3603-1677291405.pdf

4. https://www.researchgate.net/publication/321753740_Research_on_the_Parallelization_of_the_DBSCAN_Clustering_Algorithm_for_Spatial_Data_Mining_Based_on_the_Spark_Platform?_sg=sLsJGr4rRPHH_yKCzJjOA3_NPYQ98BJnaYxptBE7MlNtYNgsfQIEAb5i0EMTloO3iIz4vFp2h0H6HmE&_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6Il9kaXJlY3QifX0