Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN
| Плотностный алгоритм кластеризации DBSCAN | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]-[/math] |
| Объём входных данных | [math]-[/math] |
| Объём выходных данных | [math]-[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]-[/math] |
| Ширина ярусно-параллельной формы | [math]-[/math] |
Основные авторы описания: Малахова Е.С., Сагиолданова Ж.
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация – это процесс разбиения множества с 𝑁 элементами 𝑥1,𝑥2, . . . , 𝑥𝑛 (𝑥𝑖 имеет размерность 𝑚) на 𝐾 кластеров, так, чтобы в каждом кластере все элементы были схожи в каком-то смысле. 𝑥𝑖 могут быть числовыми, категориальными или смешанными данными. В плотностных методах кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов.
Алгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise) –плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы.
Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние точки до центра кластера
Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы. Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера плотность точек (объектов) заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Еще точнее, для каждой точки кластера ее окрестность в диапазоне заданного радиуса должна содержать не менее некоторого числа точек, которое задается пороговым значением.
1.2 Математическое описание алгоритма
Исходные данные: объекты, которые нужно кластеризовать, параметры [math]MinPts, \ \varepsilon[/math] . Между объектами можно считать расстояния.
Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных.
Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [math]\varepsilon [/math] -соседями точки [math]x \in X[/math] понимается множество точек, расстояние до которых не превышает [math]\varepsilon [/math], т. е. [math]N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\}[/math]. Тогда точка [math]y[/math] достижима из точки [math]x[/math], если существует последовательность точек [math]x^{(1)}=x, x^{(2)},... , x^{(p-1)}, x^{(p)}=y[/math], для которой выполнено:
- [math] \begin{align} x^{(i+1)} \in N_\varepsilon (x^{(i)}), i=1,... ,p-1 \\ \mid N_\varepsilon (x^{(i)}) \mid \ge MinPts, i=1,... ,p-1 \end{align} [/math]
Здесь значение [math]MinPts[/math] задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее [math]MinPts \ \varepsilon[/math] -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее [math]MinPts \ \varepsilon [/math] -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. При такой постановке задачи, под кластером понимается максимальное связное подмножество множества [math]X[/math] . Точки, не попавшие в какой-либо кластер (не принадлежащие [math]\varepsilon[/math] -окрестности какого-либо «ядра»), относятся к классу «шум».
1.3 Вычислительное ядро алгоритма
Вычислительное ядро последовательной версии метода Холецкого можно составить из множественных (всего их [math]\frac{n (n - 1)}{2}[/math]) вычислений скалярных произведений строк матрицы:
- [math]\sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]
в режиме накопления или без него, в зависимости от требований задачи. Во многих последовательных реализациях упомянутый способ представления не используется. Дело в том, что в них вычисление сумм типа
- [math]a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]
в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений
- [math]a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp}[/math]
в режиме накопления или без него.
Тем не менее, в популярных зарубежных реализациях точечного метода Холецкого, в частности, в библиотеках LINPACK и LAPACK, основанных на BLAS, используются именно вычисления скалярных произведений в виде вызова соответствующих подпрограмм BLAS (конкретно — функции SDOT). На последовательном уровне это влечёт за собой дополнительную операцию суммирования на каждый из [math]\frac{n (n + 1)}{2}[/math] вычисляемый элемент матрицы [math]L[/math] и некоторое замедление работы программы (о других следствиях рассказано ниже в разделе «Существующие реализации алгоритма»). Поэтому в данных вариантах ядром метода Холецкого будут вычисления этих скалярных произведений.
1.4 Макроструктура алгоритма
Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Это может быть R*-дерево или k-d дерево. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Также для построения этих деревьев нужно уметь находить расстояние между объектами [math]\rho(u,v)[/math], в, это расстояние можно вводить разными способами. Например, если [math]\rho(u,v)[/math] - метрика в евклидовом пространстве, [math]u=(u_1,...,u_n)[/math] и [math](v_1,...,v_n)[/math], то расстояние вычисляется следующим образом: [math]\rho(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}[/math]
1.5 Схема реализации последовательного алгоритма
Последовательная реализация алгоритма может быть представлена следующим псевдокодом:
[math]DBSCAN(X, \varepsilon, MinPts)[/math] //Изначально все объекты в [math]X[/math]не кластеризованы [math]FORALL[/math] objects [math]x[/math] in [math]X\ DO[/math] [math]IF\ x[/math] is unclassified call function [math]expand\_cluster[/math] to construct a cluster wrt. [math]\varepsilon[/math] and [math]MinPts[/math] containing [math]x[/math]
[math]FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):[/math] [math]retrive\_\varepsilon neighborhood(x, \varepsilon)[/math]; [math]IF \mid N_{\varepsilon}(x) \mid \lt MinPts[/math] //т.е. [math]x[/math] - не ядровой объект mark [math]x[/math] as [math]noise[/math] and [math]RETURN[/math]; [math]ELSE[/math]//т.е. [math]x[/math] - ядровой объект select a new cluster-id and mark all objects in [math]N_{\varepsilon}(x)[/math] with this current [math]cluster-id[/math]; push all objects from [math]N_{\varepsilon}(x)[/math]\[math](x)[/math] onto the stack seeds; [math]WHILE\ NOT[/math] seeds.empty() [math]DO[/math] [math]currentObject[/math] := seeds.top(); seeds.pop(); [math]retrive\_\varepsilon neighborhood(currentObject, \varepsilon)[/math]; [math]IF \mid N_{\varepsilon}(currentObjects) \mid \ge MinPts[/math] select all objects in [math]N_{\varepsilon}(currentObject)[/math] not yet classified or marked as [math]noise[/math], push the unclassified objects onto seeds and mark all of these objects with current [math]cluster-id[/math]; [math]RETURN[/math]
[math]FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)[/math] //функция возвращает соседей на основе структуры R*-дерево return [math]\{ x' \ | \ \forall x' \in X: \rho(x, x') \lt \varepsilon \}[/math]
1.6 Последовательная сложность алгоритма
Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать специальную пространственную структуру данных для определения соседних объектов со сложностью [math]O(n)[/math], то сложность алгоритма [math]O(nlogn)[/math]. Если не использовать пространственную структуру данных, то в худшем случае алгоритм будет иметь сложность [math]O(n^2)[/math], так как придется считать полную матрицу расстояний между объектами.
1.7 Информационный граф
В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма.
Разбиение данных происходит с помощью структуры R*-дерево, которая разбивает все множество объектов [math]X[/math] на [math]m[/math] частей: [math]X_1,X_2,...,X_m[/math]. Далее на каждой части объектов применяется алгоритм PDBSCAN, структура которого представлена ниже.
Данный алгоритм отличается от общего алгоритма DBSCAN тем, что применяется к части объектов и для каждой этой части определяет кандидатов на слияние. Это осуществляется...
Слияние...
