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

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

1. Определение eps-окрестности:

Для точки [math]\displaystyle{ p \in \mathbb{R}^d }[/math] её eps-окрестностью называется множество точек, находящихся на расстоянии не более eps от точки p: [math]\displaystyle{ N_{\text{eps}}(p) = \{ q \in \mathbb{R}^d \mid \text{dist}(p, q) \leq \text{eps} \} }[/math] где [math]\displaystyle{ \text{dist}(p, q) }[/math] — расстояние между точками p и q (обычно используется евклидово расстояние).

2. Типы точек:

- Основная точка: Точка p считается основной, если в её eps-окрестности находится как минимум minPts точек, включая её саму: [math]\displaystyle{ |N_{\text{eps}}(p)| \geq \text{minPts} }[/math]

- Граничная точка: Точка p является граничной, если она принадлежит eps-окрестности основной точки, но сама не удовлетворяет условию для основной точки: [math]\displaystyle{ 0 \lt |N_{\text{eps}}(p)| \lt \text{minPts} }[/math]

- Шумовая точка: Точка p, которая не является ни основной, ни граничной, то есть для неё выполняется условие: [math]\displaystyle{ |N_{\text{eps}}(p)| \lt \text{minPts} }[/math]

3. Формирование кластеров:

- Алгоритм начинает с произвольной нерассмотренной точки и проверяет, является ли она основной.

- Если точка p является основной, то на основе её eps-окрестности начинается формирование нового кластера C.

- Все точки из eps-окрестности добавляются в кластер C. Для каждой добавленной основной точки алгоритм рекурсивно включает её соседей, расширяя кластер до тех пор, пока все eps-соседи всех основных точек кластера не будут исчерпаны.

- Граничные точки, связанные с основной точкой, добавляются в кластер, но не инициируют дальнейшее расширение.

4. Функция принадлежности кластерам:

- В результате работы алгоритма получается множество кластеров [math]\displaystyle{ \{C_1, C_2, \ldots, C_k\} }[/math], где каждая точка [math]\displaystyle{ p \in C_i }[/math] принадлежит одному из кластеров или считается шумовой (если не включена ни в один кластер).

5. Алгоритм завершения:

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

Литература

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