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

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

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

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

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

1. Определение основных параметров:

- eps: радиус окрестности для каждой точки, внутри которого считаются соседние точки.

- minPts: минимальное количество точек, которое должно быть в `eps`-окрестности, чтобы считать точку "основной".

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

- Основная точка: точка, у которой в пределах eps-окрестности находится как минимум minPts точек, включая саму точку.

- Граничная точка: точка, которая находится в eps-окрестности некоторой основной точки, но сама не является основной.

- Шумовая точка: точка, которая не является ни основной, ни граничной. Она не входит ни в один кластер.

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

- Алгоритм случайным образом выбирает не рассмотренную точку из набора данных и проверяет её eps-окрестность.

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

- Если точка граничная, она добавляется в кластер, но не вызывает распространение кластеризации на соседей.

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

4. Завершение алгоритма:

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

- В результате алгоритм возвращает кластеры, которые могут быть произвольной формы, и помечает изолированные точки как шумовые.

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

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.