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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показаны 2 промежуточные версии этого же участника)
Строка 29: Строка 29:
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 +
Пусть имеется множество точек <math> \mathcal{D} = \{p_1, p_2, \dots, p_n\} </math> в d-мерном пространстве, где каждая точка <math> p_i \in \mathbb{R}^d </math> характеризуется d признаками. Определим формально параметры:
  
−
1. '''Определение eps-окрестности''':
+
1. Радиус eps > 0.
  
−
Для точки <math> p \in \mathbb{R}^d </math> её eps-окрестностью называется множество точек, находящихся на расстоянии не более eps от точки p:
+
2. Параметр плотности <math> minPts \in \mathbb{N} </math>, указывающий минимальное количество точек, необходимых для формирования кластера.
−
<math>N_{\text{eps}}(p) = \{ q \in \mathbb{R}^d \mid \text{dist}(p, q) \leq \text{eps} \}</math>
 
−
где <math> \text{dist}(p, q) </math> — расстояние между точками p и q (обычно используется евклидово расстояние).
 
  
−
2. '''Типы точек''':
+
Для каждой точки <math> p_i \in \mathcal{D} </math>, определим её eps-окрестность:
  
−
- ''Основная точка'': Точка p считается основной, если в её eps-окрестности находится как минимум minPts точек, включая её саму:
+
<math>N_{\varepsilon}(p_i) = \{p_j \in \mathcal{D} \mid d(p_i, p_j) \leq \varepsilon\}</math>
−
<math>|N_{\text{eps}}(p)| \geq \text{minPts}</math>
 
  
−
- ''Граничная точка'': Точка p является граничной, если она принадлежит eps-окрестности основной точки, но сама не удовлетворяет условию для основной точки:
+
где <math> d(p_i, p_j) </math> — метрика расстояния, например, Евклидово расстояние.
−
<math>0 < |N_{\text{eps}}(p)| < \text{minPts}</math>
 
  
−
- ''Шумовая точка'': Точка p, которая не является ни основной, ни граничной, то есть для неё выполняется условие:
+
Для определения точек в терминах DBSCAN вводятся следующие условия:
−
<math>|N_{\text{eps}}(p)| < \text{minPts}</math>
 
  
−
3. '''Формирование кластеров''':
+
- Ядровая точка: точка <math> p_i </math> считается ядровой, если <math> |N_{\varepsilon}(p_i)| \geq minPts </math>.
  
−
- Алгоритм начинает с произвольной нерассмотренной точки и проверяет, является ли она основной.
+
- Граничная точка: точка <math> p_j </math> считается граничной, если <math> p_j </math> находится в \eps-окрестности ядровой точки, но сама не является ядровой.
  
−
- Если точка p является основной, то на основе её eps-окрестности начинается формирование нового кластера C.
+
- Шумовая точка: точка <marh> p_k </math> не является ни ядровой, ни граничной, если <math> |N_{\varepsilon}(p_k)| < minPts </math> и она не принадлежит eps-окрестности ни одной из ядровых точек.
  
−
- Все точки из eps-окрестности добавляются в кластер C. Для каждой добавленной основной точки алгоритм рекурсивно включает её соседей, расширяя кластер до тех пор, пока все eps-соседи всех основных точек кластера не будут исчерпаны.
+
Процесс кластеризации:
  
−
- Граничные точки, связанные с основной точкой, добавляются в кластер, но не инициируют дальнейшее расширение.
+
1. Для каждой точки <math> p_i \in \mathcal{D} </math>:
  
−
4. '''Функция принадлежности кластерам''':
+
- Если <math> p_i </math> является ядровой точкой, то создаётся новый кластер C.
  
−
- В результате работы алгоритма получается множество кластеров <math> \{C_1, C_2, \ldots, C_k\} </math>, где каждая точка <math> p \in C_i </math> принадлежит одному из кластеров или считается шумовой (если не включена ни в один кластер).
+
- Все точки в eps-окрестности <math> p_i </math> добавляются в кластер C.
  
−
5. '''Алгоритм завершения''':
+
- Процесс расширения продолжается рекурсивно для всех ядровых точек в окрестности.
  
−
- Алгоритм повторяет шаги кластеризации для всех нерассмотренных точек в выборке, пока все точки либо не будут отнесены к одному из кластеров, либо помечены как шум.
+
2. Граничные точки добавляются в кластеры, если они находятся в окрестности eps хотя бы одной ядровой точки, но не создают новые кластеры.
 +
 
 +
3. Все оставшиеся точки, не принадлежащие ни одному кластеру, считаются шумовыми.
 +
 
 +
Таким образом, DBSCAN создает множество кластеров <math> \{C_1, C_2, \dots, C_k\} </math>, где k — количество обнаруженных кластеров, а точки, не входящие ни в один из <math> C_i </math>, классифицируются как шумовые точки.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Строка 87: Строка 87:
 
== Литература ==
 
== Литература ==
 
1. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, № 7, С. 36-39.
 
1. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, № 7, С. 36-39.
 +
 +
2. https://www.sciencedirect.com/science/article/pii/S0165178123002159#sec0002

Текущая версия на 18:37, 3 ноября 2024

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

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

Алгоритм 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.2 Математическое описание алгоритма

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

1. Радиус eps > 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

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

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

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Даниил_Глазков/Алгоритм_кластеризации_DBSCAN&oldid=29612