Участник:Даниил Глазков/Алгоритм кластеризации DBSCAN: различия между версиями
Строка 180: | Строка 180: | ||
* '''Распараллеливание''': Нет. | * '''Распараллеливание''': Нет. | ||
* '''Описание''': Стандартная реализация DBSCAN для малых и средних данных. | * '''Описание''': Стандартная реализация DBSCAN для малых и средних данных. | ||
− | * | + | * Документация Scikit-learn DBSCAN: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html |
2. HDBSCAN (Python): | 2. HDBSCAN (Python): | ||
Строка 186: | Строка 186: | ||
* '''Распараллеливание''': Да. | * '''Распараллеливание''': Да. | ||
* '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными. | * '''Описание''': Расширенная версия DBSCAN, поддерживает параллельную обработку и улучшает работу с разреженными данными. | ||
− | * | + | * Документация HDBSCAN: https://hdbscan.readthedocs.io/en/latest/ |
3. cuML (GPU-ускоренная библиотека от NVIDIA): | 3. cuML (GPU-ускоренная библиотека от NVIDIA): | ||
Строка 192: | Строка 192: | ||
* '''Распараллеливание''': Да, использует GPU для ускорения вычислений. | * '''Распараллеливание''': Да, использует GPU для ускорения вычислений. | ||
* '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных. | * '''Описание''': GPU-ускоренная реализация DBSCAN, подходящая для больших объемов данных. | ||
− | * | + | * Документация cuML DBSCAN: https://rapids.ai/ |
4. Apache Spark MLlib (Java/Scala/Python): | 4. Apache Spark MLlib (Java/Scala/Python): | ||
Строка 198: | Строка 198: | ||
* '''Распараллеливание''': Да, для распределенной обработки данных в кластере. | * '''Распараллеливание''': Да, для распределенной обработки данных в кластере. | ||
* '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных. | * '''Описание''': Распределенная версия DBSCAN для кластеризации на больших данных. | ||
− | * | + | * Документация Spark MLlib: https://spark.apache.org/mllib/ |
== Литература == | == Литература == |
Версия 11:39, 11 декабря 2024
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Алгоритм DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — это алгоритм кластеризации, предназначенный для решения задачи обнаружения плотных областей в пространстве данных и выделения их как кластеров. Этот алгоритм относится к классу алгоритмов плотностной кластеризации, где основным критерием для объединения точек в кластеры является их плотность.
В отличие от алгоритмов, основанных на минимизации расстояний между точками (например, K-средних), DBSCAN автоматически определяет количество кластеров и не требует задания их количества заранее. Кроме того, DBSCAN хорошо справляется с шумами и выбросами, поскольку точки, не принадлежащие к плотным областям, маркируются как шумовые.
Особенности объектов, с которыми работает DBSCAN:
- Входные данные представлены набором точек в пространстве, где каждая точка характеризуется набором признаков. Для двухмерного пространства точки могут быть представлены как (x, y), но алгоритм также применим и для данных с большим числом признаков.
- Алгоритм подходит для плотностных структур, где кластеры имеют разную форму и размеры, что делает его особенно полезным для географических и пространственных данных.
Основные параметры DBSCAN:
- eps — радиус, в пределах которого точки считаются соседними и могут быть включены в один кластер.
- minPts — минимальное количество точек, необходимых для того, чтобы область считалась "плотной" и могла образовать кластер.
Алгоритм выделяет три типа точек:
- Ядровые точки: точки, которые имеют по меньшей мере minPts соседей в радиусе eps. Эти точки образуют ядро кластера.
- Граничные точки: точки, которые находятся в радиусе eps от ядровой точки, но сами не обладают достаточным количеством соседей, чтобы быть ядровыми.
- Шумовые точки: точки, которые не принадлежат ни к одному кластеру, так как не попадают в плотные области.
DBSCAN широко применяется в задачах с нерегулярной структурой данных и особенно полезен в задачах обработки пространственных данных и аномалий.
1.2 Математическое описание алгоритма
Пусть имеется множество точек \mathcal{D} = \{p_1, p_2, \dots, p_n\} в d-мерном пространстве, где каждая точка p_i \in \mathbb{R}^d характеризуется d признаками. Определим формально параметры:
- Радиус eps > 0.
- Параметр плотности minPts \in \mathbb{N} , указывающий минимальное количество точек, необходимых для формирования кластера.
Для каждой точки p_i \in \mathcal{D} , определим её eps-окрестность:
N_{\varepsilon}(p_i) = \{p_j \in \mathcal{D} \mid d(p_i, p_j) \leq \varepsilon\}
где d(p_i, p_j) — метрика расстояния, например, Евклидово расстояние.
Для определения точек в терминах DBSCAN вводятся следующие условия:
- Ядровая точка: точка p_i считается ядровой, если |N_{\varepsilon}(p_i)| \geq minPts .
- Граничная точка: точка p_j считается граничной, если p_j находится в \eps-окрестности ядровой точки, но сама не является ядровой.
- Шумовая точка: точка <marh> p_k </math> не является ни ядровой, ни граничной, если |N_{\varepsilon}(p_k)| \lt minPts и она не принадлежит eps-окрестности ни одной из ядровых точек.
Процесс кластеризации:
1. Для каждой точки p_i \in \mathcal{D} :
- Если p_i является ядровой точкой, то создаётся новый кластер C.
- Все точки в eps-окрестности p_i добавляются в кластер C.
- Процесс расширения продолжается рекурсивно для всех ядровых точек в окрестности.
2. Граничные точки добавляются в кластеры, если они находятся в окрестности eps хотя бы одной ядровой точки, но не создают новые кластеры.
3. Все оставшиеся точки, не принадлежащие ни одному кластеру, считаются шумовыми.
Таким образом, DBSCAN создает множество кластеров \{C_1, C_2, \dots, C_k\} , где k — количество обнаруженных кластеров, а точки, не входящие ни в один из C_i , классифицируются как шумовые точки.
1.3 Вычислительное ядро алгоритма
Основные этапы ядра алгоритма:
1. Разделение данных Набор данных D разбивается на несколько непересекающихся подмножеств D_1, D_2, \ldots, D_k . При этом каждая часть данных обрабатывается независимо, что позволяет эффективно распределить вычисления между узлами параллельной
2. Локальное выполнение DBSCAN На каждом подмножестве D_i выполняется локальная версия алгоритма DBSCAN:
- Поиск \varepsilon -соседей для каждой точки в D_i .
- Проверка, является ли точка плотностным ядром в рамках текущего подмножества D_i .
- Формирование локальных кластеров.
Эти операции аналогичны стандартному алгоритму DBSCAN, но выполняются только на локальных подмножествах, что снижает вычислительную сложность в каждом
3. Слияние границ кластеров. После обработки всех подмножеств необходимо объединить кластеры, пересекающие границы D_i и D_j . Это достигается путём:
- Если граничная точка P \in D_i имеет соседей в D_j , то выполняется пересечения кластеров
1.4 Макроструктура алгоритма
- Разбиение данных на подмножества: На этом этапе набор данных D разбивается на несколько непересекающихся подмножеств D_1, D_2, \ldots, D_k
- Кластеризация: Основной этап алгоритма. Для каждого полученного подмножества применяется алгоритм кластеризации DBSCAN
- Слияние кластеров на границах: Если точка P \in D_i имеет соседей в D_j , то выполняется пересечения кластеров
1.5 Схема реализации последовательного алгоритма
Псевдокод для реализации алгоритма DBSCAN
# Инициализация 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
1.6 Последовательная сложность алгоритма
Разбиение данных на подмножества:
- Функция для разбиения имеет временную сложность O(N), так как она проходит по всем точкам и проверяет их принадлежность к региону.
Кластеризация точек:
- Основная часть алгоритма — это функция кластеризация DBSCAN, которая выполняет поиск соседних точек и расширение кластера. В худшем случае, алгоритм может обрабатывать все точки, что приводит к временной сложности O(N^2) для одного процесса. Поскольку алгоритм параллельный и точки распределены между процессами, временная сложность для каждого процесса будет O((N/P)^2), где P — количество процессов.
Объединение пересекающихся кластеров:
- Функция объединения кластеров имеет временную сложность O(N^2), так как она проходит по всем точкам и проверяет совпадение координат для граничных точек.
Общая временная сложность алгоритма для одного процесса составляет O(N^2). В параллельной версии с P процессами временная сложность для каждого процесса составляет O((N/P)^2). Однако, учитывая накладные расходы на коммуникацию между процессами, общая временная сложность параллельного алгоритма будет примерно O(N^2/P).
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм DBSCAN с параллельной обработкой данных имеет иерархическую структуру параллелизма, которая позволяет эффективно распределить вычисления между несколькими процессами или узлами. В предположении доступности неограниченного числа процессоров, параллельная сложность алгоритма определяется числом шагов, необходимых для обработки данных:
- Деление на регионы: На этом шаге пространственные данные делятся на подрегионы, что можно выполнить за O(\log M) шагов, где M — количество подрегионов.
- Параллельный поиск соседей и кластеризация: Каждый подрегион обрабатывается независимо, что позволяет достичь хорошего параллелизма, поскольку для каждого региона можно запускать отдельные потоки. Это даёт сложность O(\log N) , где N — число точек в каждом
- Объединение кластеров: Слияние кластеров на границах может быть выполнено с использованием параллельного обмена данными, что также позволяет эффективно использовать параллельные ресурсы.
Таким образом, параллельная сложность алгоритма близка к O(\log M) для деления и O(\log N) для обработки данных в каждом подрегионе. Ресурс параллелизма выражается через массовый параллелизм, где каждый процесс работает с отдельным подрегионом, а скошенный параллелизм проявляется в объединении кластеров на границах регионов.
1.9 Входные и выходные данные алгоритма
- Входные данные: Множество точек X = \{x_1, x_2, \ldots, x_n\} , где каждая точка x_i представлена в d -мерном пространстве. Объем данных: n — количество точек, d — размерность пространства. В типичных задачах n может быть порядка 10^3 – 10^6 , а d — от нескольких единиц до сотен.
- Выходные данные: Размеченное множество точек X, где каждой точке x_i сопоставлен номер кластера C_i . Значение C_i = -1 означает, что точка является шумовой (не принадлежит ни одному кластеру). Объем выходных данных: n меток кластеров, каждая из которых занимает O(1) памяти, что в сумме составляет O(n).
2 Программная реализация алгоритма
2.1 Масштабируемость алгоритма и его реализации
Алгоритм DBSCAN в данной реализации обладает хорошей масштабируемостью благодаря использованию параллельной обработки данных с разделением на подрегионы. Каждый регион обрабатывается независимо, что позволяет эффективно распределить вычисления между несколькими процессами или узлами
- Масштабируемость с точки зрения числа точек - в случае использования пространственных структур (например, KD-деревьев), сложность поиска соседей уменьшается, что улучшает производительность при увеличении числа точек
Таким образом, алгоритм сохраняет свою эффективность при увеличении объема данных и числа вычислительных узлов.
2.2 Существующие реализации алгоритма
Краткое описание библиотек с указанием, поддерживают ли они распараллеливание:
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/
3 Литература
1. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, № 7, С. 36-39.
2. https://www.sciencedirect.com/science/article/pii/S0165178123002159#sec0002