Алговики - Вклад [ru]

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

2024-12-11T08:48:15Z

Даниил Глазков: /* Информационный граф */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

'''Зависимости'''

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

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

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

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

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

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

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

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

* '''Выходные данные''': Размеченное множество точек X, где каждой точке <math> x_i </math> сопоставлен номер кластера <math> C_i </math>. Значение <math> 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

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

2024-12-11T08:47:36Z

Даниил Глазков: /* Информационный граф */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

'''Зависимости'''

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

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

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

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

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

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

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

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

* '''Выходные данные''': Размеченное множество точек X, где каждой точке <math> x_i </math> сопоставлен номер кластера <math> C_i </math>. Значение <math> 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

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

2024-12-11T08:41:20Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

* '''Выходные данные''': Размеченное множество точек X, где каждой точке <math> x_i </math> сопоставлен номер кластера <math> C_i </math>. Значение <math> 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

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

2024-12-11T08:39:24Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

* '''Выходные данные''': Размеченное множество точек X, где каждой точке <math> x_i </math> сопоставлен номер кластера <math> C_i </math>. Значение <math> 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://rapids.ai/

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

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

2024-12-11T08:38:25Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Scikit-learn (Python):

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

2. HDBSCAN (Python):

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

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.
* [Документация cuML DBSCAN](https://rapids.ai/)

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

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

2024-12-11T08:37:42Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Scikit-learn (Python):

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

2. HDBSCAN (Python):

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

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.
* [Документация cuML DBSCAN](https://rapids.ai/)

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

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

2024-12-11T08:29:16Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

* '''Выходные данные''': Размеченное множество точек X, где каждой точке <math> x_i </math> сопоставлен номер кластера <math> C_i </math>. Значение <math> 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://rapids.ai/)

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

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

2024-12-11T08:26:03Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-11T08:25:20Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-10T14:35:26Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

* Входные данные: множество точек X

* Выходные данные: размеченное входное множество точек, где каждой точке сопоставлен номер кластера (-1 означает, что точка шумовая)

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-10T14:35:06Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

* Входные данные: множество точек X

* Выходные данные: размеченное входное множество точек, где каждой точке сопоставлен номер кластера (-1 означает, что точка шумовая)

Программа трестировалась на датасете make_circles из 50000 точек

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-06T20:00:35Z

Даниил Глазков: /* Ресурс параллелизма алгоритма */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

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

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

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

* Входные данные: множество точек X

* Выходные данные: размеченное входное множество точек, где каждой точке сопоставлен номер кластера (-1 означает, что точка шумовая)

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-06T19:56:58Z

Даниил Глазков: /* Масштабируемость алгоритма и его реализации */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

* Входные данные: множество точек X

* Выходные данные: размеченное входное множество точек, где каждой точке сопоставлен номер кластера (-1 означает, что точка шумовая)

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

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

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

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

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-06T19:54:55Z

Даниил Глазков: /* Масштабируемость алгоритма и его реализации */

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

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

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

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

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

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

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

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

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

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

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

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

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

# Радиус eps > 0.
# Параметр плотности <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)| < 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. Разделение данных
Набор данных <math> D </math> разбивается на несколько непересекающихся подмножеств <math> D_1, D_2, \ldots, D_k </math>. При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной

[[Файл:Разбиение данных.png|300px|thumb|center|Рис.1. Разбиение данных]]

2. Локальное выполнение DBSCAN
На каждом подмножестве <math> D_i </math> выполняется локальная версия алгоритма DBSCAN:

* Поиск <math> \varepsilon </math>-соседей для каждой точки в <math> D_i </math>.

* Проверка, является ли точка плотностным ядром в рамках текущего подмножества <math> D_i </math>.

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

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

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

* Если граничная точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

[[Файл:Объединение в кластеры.png|thumb|center|Рис.2. Объединение кластеров из разных процессов]]

=== Макроструктура алгоритма ===
# '''Разбиение данных на подмножества''': На этом этапе набор данных <math>D</math> разбивается на несколько непересекающихся подмножеств <math>D_1, D_2, \ldots, D_k</math>
# '''Кластеризация''': Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
# '''Слияние кластеров на границах''': Если точка <math> P \in D_i </math> имеет соседей в <math> D_j </math>, то выполняется пересечения кластеров

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

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

<pre>
# Инициализация
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
</pre>

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

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

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

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

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

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

* Функция объединения кластеров имеет временную сложность <math>O(N^2)</math>, так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.

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

=== Информационный граф ===
[[Файл:Снимок экрана 2024-12-06 в 22.36.56.png|600px|мини|центр|Информационный граф DBSCAN]]

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

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

* Входные данные: множество точек X

* Выходные данные: размеченное входное множество точек, где каждой точке сопоставлен номер кластера (-1 означает, что точка шумовая)

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

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

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

# '''Горизонтальная масштабируемость:''' Разделение на подрегионы позволяет легко увеличивать количество вычислительных узлов, так как каждый подрегион может обрабатываться отдельно без значительных затрат на синхронизацию.
# '''Масштабируемость с точки зрения числа измерений:''' С увеличением числа измерений сложность поиска соседей и обработки точек может возрасти, однако правильное деление пространства помогает снизить эти затраты.

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

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

1. Scikit-learn (Python):

* '''Распараллеливание''': Нет.
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных.

2. HDBSCAN (Python):

* '''Распараллеливание''': Да.
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными.

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

* '''Распараллеливание''': Да, использует GPU для ускорения вычислений.
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных.

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

* '''Распараллеливание''': Да, для распределенной обработки данных в кластере.
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных.

== Литература ==
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

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

2024-12-06T19:51:28Z

Даниил Глазков: /* Существующие реализации алгоритма */

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

2024-12-06T19:42:59Z

Даниил Глазков: /* Информационный граф */

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

2024-12-06T19:42:34Z

Даниил Глазков: /* Информационный граф */

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

2024-12-06T19:40:35Z

Даниил Глазков: /* Информационный граф */

Файл:Снимок экрана 2024-12-06 в 22.36.56.png

2024-12-06T19:38:15Z

Даниил Глазков:

Информационный граф распараллеленного алгоритма DBSCAN

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

2024-12-06T19:17:34Z

Даниил Глазков: /* Математическое описание алгоритма */

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

2024-12-06T19:16:33Z

Даниил Глазков: /* Математическое описание алгоритма */

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

2024-12-06T19:15:14Z

Даниил Глазков: /* Общее описание алгоритма */

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

2024-12-06T19:14:34Z

Даниил Глазков: /* Свойства и структура алгоритма */

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

2024-12-06T19:12:36Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T19:12:00Z

Даниил Глазков: /* Последовательная сложность алгоритма */

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

2024-12-06T19:11:35Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

2024-12-06T19:10:54Z

Даниил Глазков: /* Входные и выходные данные алгоритма */

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

2024-12-06T18:47:48Z

Даниил Глазков: /* Литература */

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

2024-12-06T18:45:35Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

Файл:Объединение в кластеры.png

2024-12-06T18:44:05Z

Даниил Глазков:

Иллюстрация объединения кластеров из разных процессов

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

2024-12-06T18:38:57Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T18:36:16Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

Файл:Разбиение данных.png

2024-12-06T18:35:36Z

Даниил Глазков:

Иллюстрация разбиения данных по процессам

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

2024-12-06T18:22:06Z

Даниил Глазков: /* Литература */

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

2024-12-06T18:07:36Z

Даниил Глазков: /* Последовательная сложность алгоритма */

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

2024-12-06T18:07:03Z

Даниил Глазков: /* Последовательная сложность алгоритма */

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

2024-12-06T18:06:14Z

Даниил Глазков: /* Последовательная сложность алгоритма */

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

2024-12-06T18:05:22Z

Даниил Глазков: /* Последовательная сложность алгоритма */

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

2024-12-06T17:51:57Z

Даниил Глазков: /* Схема реализации последовательного алгоритма */

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

2024-12-06T17:46:39Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T17:46:12Z

Даниил Глазков: /* Макроструктура алгоритма */

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

2024-12-06T17:32:55Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T17:30:04Z

Даниил Глазков: /* **Вычислительное ядро алгоритма** */

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

2024-12-06T17:26:57Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T17:22:04Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-12-06T17:20:17Z

Даниил Глазков: /* Вычислительное ядро алгоритма */

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

2024-11-03T15:37:05Z

Даниил Глазков: /* Литература */

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

2024-11-03T15:36:49Z

Даниил Глазков: /* Литература */

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

2024-11-03T15:34:49Z

Даниил Глазков: /* Математическое описание алгоритма */

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

2024-11-03T15:28:26Z

Даниил Глазков: /* Свойства и структура алгоритма */