Участник:Даниил Глазков/Алгоритм кластеризации 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]. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной 

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]. Это достигается путём:

  - Обмена информации о точках на границах подмножеств между процессами.

  - Слияния пересекающихся кластеров в единый кластер.

Основное вычислительное ядро

С учётом разделения данных вычислительное ядро состоит из двух ключевых частей:

1. Локальный поиск [math]\displaystyle{ \varepsilon }[/math]-соседей и формирование кластеров в каждом [math]\displaystyle{ D_i }[/math]:

  [math]\displaystyle{ 
   N_i(P) = \{ Q \in D_i \mid dist(P, Q) \leq \varepsilon \}
    }[/math]
  где [math]\displaystyle{  dist(P, Q)  }[/math] — метрика расстояния.

2. Слияние кластеров на границах:

  Если точка [math]\displaystyle{  P \in D_i  }[/math] имеет соседей в [math]\displaystyle{  D_j  }[/math], то выполняется проверка пересечения кластеров:
  [math]\displaystyle{ 
   \text{Если } P \text{ и } Q \in D_j \text{ находятся на расстоянии } \leq \varepsilon, \text{ то их кластеры объединяются.}
    }[/math]

Литература

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

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