Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN: различия между версиями
ASA (обсуждение | вклад) |
|||
| (не показано 65 промежуточных версий 6 участников) | |||
| Строка 1: | Строка 1: | ||
| + | {{Assignment|Sleo|Dexter}} | ||
| + | |||
{{algorithm | {{algorithm | ||
| name = Плотностный алгоритм кластеризации DBSCAN | | name = Плотностный алгоритм кластеризации DBSCAN | ||
| Строка 8: | Строка 10: | ||
}} | }} | ||
| − | Основные авторы описания: [[Участник:Elena777mc|Малахова Е.С.]], [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]] | + | Основные авторы описания: [[Участник:Elena777mc|Малахова Е.С.]] (1.2, 1.4-1.8, 2.4, 2.7), [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]] (1.1-1.3, 1.9-1.10, 3) |
= Свойства и структура алгоритмов = | = Свойства и структура алгоритмов = | ||
| Строка 16: | Строка 18: | ||
в каком-то смысле. <math>x_i</math> могут быть числовыми, категориальными или смешанными данными. В плотностных методах кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов. | в каком-то смысле. <math>x_i</math> могут быть числовыми, категориальными или смешанными данными. В плотностных методах кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов. | ||
| − | Алгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise) –плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. | + | Алгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise) <ref>A density-based algorithm for discovering clusters in large spatial database / M. Ester, H.-P. Kriegel, |
| + | J. Sander, X. Xu // Proc. 1996 Intern. Conf. on Knowledge Discovery and Data Mining. – 1996. – P. 226 – | ||
| + | 231.</ref> –плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы. | ||
| − | Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние точки до центра кластера | + | Большинство алгоритмов, производящих плоское разбиение (то есть разбиение объектов на плоскости на непересекающиеся множества/кластеры), создают кластеры по форме близкие к сферическим, так как минимизируют расстояние точки до центра кластера. |
Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы. | Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы. | ||
| Строка 25: | Строка 29: | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| − | [[File: | + | [[File:Dbscan_picture.png|thumb|right|500px| Рис. 1. Пример ядровых, граничных и шумовых точек алгоритма. Точка A - ядровая, точки B и С - граничные, N - шум. В данном примере MinPts = 4, Eps равен радиусу окружности <ref>https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/DBSCAN-Illustration.svg/400px-DBSCAN-Illustration.svg.png</ref>]] |
Исходные данные: объекты, которые нужно кластеризовать, параметры <math>MinPts, \ \varepsilon</math> . Между объектами можно считать расстояния. | Исходные данные: объекты, которые нужно кластеризовать, параметры <math>MinPts, \ \varepsilon</math> . Между объектами можно считать расстояния. | ||
| − | Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных. | + | Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных. <ref>"Xu, X. A fast parallel clustering algorithm for large spatial databases / X. Xu, M. Ester, H.-P. Kriegel // Proc. 1999 Intern. Conf. on Knowledge Discovery and Data Mining. – 1999. – Vol. 3, is. 3. – P. 263 – 290.</ref> |
Для построения оценки плотности, на основе соседства точек вводятся понятия | Для построения оценки плотности, на основе соседства точек вводятся понятия | ||
| − | достижимости и связности. Под <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>\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> | :<math> | ||
\begin{align} | \begin{align} | ||
| Строка 46: | Строка 52: | ||
| − | Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждого объекта входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как требуется найти всех соседей для каждого объекта заданного множества. | + | Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждого объекта входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как требуется найти всех соседей для каждого объекта заданного множества. Основные операции, которые применяются в вычислительном ядре алгоритма: нахождение расстояние между объектами и сравнение расстояния с порогом для определения того, являются ли данные объекты <math>\varepsilon</math>-соседями. |
== Макроструктура алгоритма == | == Макроструктура алгоритма == | ||
| − | Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов | + | Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Сложность построения таких структур <math>O(n \log n)</math>, и использование такой структуры не увеличит сложность всего алгоритма (если сложность самого алгоритма <math>O(n \log n)</math>). Также для построения таких деревьев нужно уметь находить расстояния между объектами <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> |
== Схема реализации последовательного алгоритма == | == Схема реализации последовательного алгоритма == | ||
Последовательная реализация алгоритма может быть представлена следующим псевдокодом: | Последовательная реализация алгоритма может быть представлена следующим псевдокодом: | ||
| + | // Основная функция, которая реализует алгоритм кластеризации | ||
<math>DBSCAN(X, \varepsilon, MinPts)</math> | <math>DBSCAN(X, \varepsilon, MinPts)</math> | ||
//Изначально все объекты в <math>X</math>не кластеризованы | //Изначально все объекты в <math>X</math>не кластеризованы | ||
| Строка 60: | Строка 67: | ||
call function <math>expand\_cluster</math> to construct a cluster wrt. <math>\varepsilon</math> and <math>MinPts</math> containing <math>x</math> | 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>FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts):</math> | ||
<math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>; | <math>retrive\_\varepsilon neighborhood(x, \varepsilon)</math>; | ||
| − | <math>IF \mid N_{\varepsilon}(x) \mid < MinPts</math> //т.е. <math>x</math> - не | + | <math>IF \mid N_{\varepsilon}(x) \mid < MinPts</math> //т.е. <math>x</math> - объект, не являющийся ядром |
mark <math>x</math> as <math>noise</math> and <math>RETURN</math>; | mark <math>x</math> as <math>noise</math> and <math>RETURN</math>; | ||
| − | <math>ELSE</math>//т.е. <math>x</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>; | 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; | push all objects from <math>N_{\varepsilon}(x)</math>\<math>(x)</math> onto the stack seeds; | ||
| Строка 76: | Строка 84: | ||
<math>RETURN</math> | <math>RETURN</math> | ||
| + | // Функция, для определения <math>\varepsilon</math>-соседей для объекта | ||
<math>FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)</math> //функция возвращает соседей на основе пространственной структуры данных | <math>FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)</math> //функция возвращает соседей на основе пространственной структуры данных | ||
return <math>\{ x' \ | \ \forall x' \in X: \rho(x, x') < \varepsilon \}</math> | return <math>\{ x' \ | \ \forall x' \in X: \rho(x, x') < \varepsilon \}</math> | ||
== Последовательная сложность алгоритма == | == Последовательная сложность алгоритма == | ||
| − | Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать | + | Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать R*-дерево или kd-дерево для определения соседних объектов со сложностью <math>O(\log n)</math>, то сложность алгоритма <math>O(n \log n)</math>. Если не использовать эти структуры, то в худшем случае алгоритм будет иметь сложность <math>O(n^2)</math>, так как придется считать полную матрицу расстояний между объектами. |
== Информационный граф == | == Информационный граф == | ||
В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма. | В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма. | ||
| − | [[File: | + | [[File:Dbscan_schema.jpg|1000px|thumb|center|Рис.1. Общая информационная структура алгоритма]] |
Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>. | Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов <math>X</math> на <math>m</math> частей: <math>X_1,X_2,...,X_m</math>. | ||
| − | + | На каждой части объектов применяется алгоритм PDBSCAN. PDBSCAN - это последовательный алгоритм DBSCAN, применяемый только к одной части объектов, и для каждой из этих частей он определяет кандидатов на слияние. PDBSCAN использует пространственную структуру, которая распределяется вместе с данными. | |
| − | + | Если для ядрового объекта части <math>X_i</math> в <math>\varepsilon</math>-окрестности находится объект из другой части <math>X_j</math>, то такие объекты становятся кандидатами на слияние. | |
| − | |||
| − | |||
Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер. | Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер. | ||
| + | |||
| + | [[File:dbscan_clusters_partitions.png|500px|thumb|center|Рис.2. Пример разбиения объектов на части на основе пространственной структуры. Каждый прямоугольник соответствует части данных, каждая из которых подается на вход алгоритму PDBSCAN <ref>https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png</ref>]] | ||
== Ресурс параллелизма алгоритма == | == Ресурс параллелизма алгоритма == | ||
| Строка 99: | Строка 108: | ||
'''Входные данные''': множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидова метрика между векторами из <math>{R}^n</math>. | '''Входные данные''': множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидова метрика между векторами из <math>{R}^n</math>. | ||
| − | '''Объём входных данных''': | + | |
| + | '''Объём входных данных''': n (размерность входящего множества) | ||
'''Выходные данные''': размеченное множество точек X, в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из X сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера |X| | '''Выходные данные''': размеченное множество точек X, в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из X сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера |X| | ||
| − | '''Объём выходных данных''': | + | '''Объём выходных данных''': n (размерность выходящего множества) |
== Свойства алгоритма == | == Свойства алгоритма == | ||
| − | Вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных | + | Вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных логарифмическая. |
''' Преимущества алгоритма ''' | ''' Преимущества алгоритма ''' | ||
| − | + | * алгоритм может обрабатывать большой объем данных и не зависит от порядка ввода данных; | |
| − | + | * может определять кластера произвольной формы; | |
| − | + | * параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с <math>\varepsilon</math>); | |
| − | + | * не требуется задание числа кластеров; | |
| − | + | * может выделять кластеры в присутствии «шума»и выбросов <ref>АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ | |
| − | + | СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ/ И. А. Пестунов, Ю. Н. Синявский// Вестник Кемеровского государственного университета. – 2012. – P. 263– | |
| + | 299.</ref>; | ||
| + | * число итераций определяется заранее. | ||
''' Недостатки алгоритма ''' | ''' Недостатки алгоритма ''' | ||
| − | + | * не может выделять кластеры сложной структуры, например, имеющие разную плотность, так как параметры алгоритма не могут быть выбраны отдельно для каждого кластера; | |
| − | + | * не может построить иерархическую структуру кластеров; | |
| − | + | * не детерминирован, так как граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован. | |
| + | * плохо работает на кластерах, которые имеют небольшое пересечение между собой. | ||
= Программная реализация алгоритма = | = Программная реализация алгоритма = | ||
| + | |||
| + | == Особенности реализации последовательного алгоритма == | ||
| + | == Локальность данных и вычислений == | ||
| + | == Возможные способы и особенности параллельной реализации алгоритма == | ||
== Масштабируемость алгоритма и его реализации == | == Масштабируемость алгоритма и его реализации == | ||
| + | Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN . Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов, поэтому исследование масштабируемости проводилось для числа входных объектов. Алгоритм тестировался на известном датасете для кластеризации: [https://archive.ics.uci.edu/ml/datasets/Individual+household+electric+power+consumption Machine Learning Repository] | ||
| + | |||
| + | Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма: | ||
| + | |||
| + | * число процессоров [1 : 128] с шагом по степеням двойки; | ||
| + | * число входных объектов [1000 : 40000]. | ||
| + | |||
| + | На следующих рисунках приведены графики производительности и эффективности распараллеливания алгоритма DBSCAN в зависимости от изменяемых параметров запуска. | ||
| + | [[File:Dbscan_perfomance.png|800px|thumb|center|Рис.1. Изменение производительности в зависимости от числа процессов и числа входных данных]] | ||
| + | [[File:Dbscan_efficiency.png|800px|thumb|center|Рис.2. Изменение эффективности распараллеливания в зависимости от числа процессов и числа входных данных]] | ||
| + | |||
| + | Построим оценки масштабируемости протестированной параллельной реализации алгоритма DBSCAN: | ||
| + | |||
| + | '''По числу процессов''' - при увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется. | ||
| + | |||
| + | '''По размеру задачи''' - При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности. | ||
| + | |||
| + | '''При одновременном увеличении количества процессов и размерности системы''' наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая. | ||
| + | |||
| + | [https://github.com/elena777mc/dbscan/tree/master Исследованная параллельная реализация на языке C++] | ||
| + | |||
| + | == Динамические характеристики и эффективность реализации алгоритма == | ||
| + | == Выводы для классов архитектур == | ||
== Существующие реализации алгоритма == | == Существующие реализации алгоритма == | ||
Текущая версия на 14:56, 3 декабря 2016
 | Эта работа успешно выполнена Преподавателю: в основное пространство, в подстраницу Данное задание было проверено и зачтено. Проверено Dexter и Sleo. |
| Плотностный алгоритм кластеризации DBSCAN | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n \log n)[/math] |
| Объём входных данных | [math]n[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(|X| \log |X|)[/math] |
| Ширина ярусно-параллельной формы | [math]O(m)[/math] |
Основные авторы описания: Малахова Е.С. (1.2, 1.4-1.8, 2.4, 2.7), Сагиолданова Ж. (1.1-1.3, 1.9-1.10, 3)
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация – это процесс разбиения множества с [math]N[/math] элементами [math]x_1, x_2, ... , x_n (x_n[/math] имеет размерность [math]m[/math]) на [math]K[/math] кластеров, так, чтобы в каждом кластере все элементы были схожи в каком-то смысле. [math]x_i[/math] могут быть числовыми, категориальными или смешанными данными. В плотностных методах кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов.
Алгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise) [1] –плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы.
Большинство алгоритмов, производящих плоское разбиение (то есть разбиение объектов на плоскости на непересекающиеся множества/кластеры), создают кластеры по форме близкие к сферическим, так как минимизируют расстояние точки до центра кластера.
Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы. Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера плотность точек (объектов) заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Еще точнее, для каждой точки кластера ее окрестность в диапазоне заданного радиуса должна содержать не менее некоторого числа точек, которое задается пороговым значением.
1.2 Математическое описание алгоритма
Исходные данные: объекты, которые нужно кластеризовать, параметры [math]MinPts, \ \varepsilon[/math] . Между объектами можно считать расстояния.
Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных. [3]
Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [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]\varepsilon[/math]-соседей каждого объекта входного множества [math]X[/math]. На эту часть алгоритма приходится основное время работы алгоритма, так как требуется найти всех соседей для каждого объекта заданного множества. Основные операции, которые применяются в вычислительном ядре алгоритма: нахождение расстояние между объектами и сравнение расстояния с порогом для определения того, являются ли данные объекты [math]\varepsilon[/math]-соседями.
1.4 Макроструктура алгоритма
Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Сложность построения таких структур [math]O(n \log n)[/math], и использование такой структуры не увеличит сложность всего алгоритма (если сложность самого алгоритма [math]O(n \log n)[/math]). Также для построения таких деревьев нужно уметь находить расстояния между объектами [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]\varepsilon[/math]-соседей для объекта [math]FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon)[/math] //функция возвращает соседей на основе пространственной структуры данных return [math]\{ x' \ | \ \forall x' \in X: \rho(x, x') \lt \varepsilon \}[/math]
1.6 Последовательная сложность алгоритма
Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать R*-дерево или kd-дерево для определения соседних объектов со сложностью [math]O(\log n)[/math], то сложность алгоритма [math]O(n \log n)[/math]. Если не использовать эти структуры, то в худшем случае алгоритм будет иметь сложность [math]O(n^2)[/math], так как придется считать полную матрицу расстояний между объектами.
1.7 Информационный граф
В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма.
Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов [math]X[/math] на [math]m[/math] частей: [math]X_1,X_2,...,X_m[/math]. На каждой части объектов применяется алгоритм PDBSCAN. PDBSCAN - это последовательный алгоритм DBSCAN, применяемый только к одной части объектов, и для каждой из этих частей он определяет кандидатов на слияние. PDBSCAN использует пространственную структуру, которая распределяется вместе с данными. Если для ядрового объекта части [math]X_i[/math] в [math]\varepsilon[/math]-окрестности находится объект из другой части [math]X_j[/math], то такие объекты становятся кандидатами на слияние.
Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.
1.8 Ресурс параллелизма алгоритма
Как видно из общей структуры графа алгоритма, ширина ярусно-параллельной формы алгоритма [math]O(m)[/math], где m - количество частей, на которые разбиваются все входное множество объектов [math]X[/math]. Высотой ярусно-параллельной формы алгоритма является [math]O(|X| \log |X|)[/math], где [math]\mid X \mid[/math] - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм PDBSCAN, применяемый к каждой отдельной части разбиения.
1.9 Входные и выходные данные алгоритма
Входные данные: множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидова метрика между векторами из [math]{R}^n[/math].
Объём входных данных: n (размерность входящего множества)
Выходные данные: размеченное множество точек X, в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из X сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера |X|
Объём выходных данных: n (размерность выходящего множества)
1.10 Свойства алгоритма
Вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных логарифмическая.
Преимущества алгоритма
- алгоритм может обрабатывать большой объем данных и не зависит от порядка ввода данных;
- может определять кластера произвольной формы;
- параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с [math]\varepsilon[/math]);
- не требуется задание числа кластеров;
- может выделять кластеры в присутствии «шума»и выбросов [5];
- число итераций определяется заранее.
Недостатки алгоритма
- не может выделять кластеры сложной структуры, например, имеющие разную плотность, так как параметры алгоритма не могут быть выбраны отдельно для каждого кластера;
- не может построить иерархическую структуру кластеров;
- не детерминирован, так как граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован.
- плохо работает на кластерах, которые имеют небольшое пересечение между собой.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN . Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов, поэтому исследование масштабируемости проводилось для числа входных объектов. Алгоритм тестировался на известном датасете для кластеризации: Machine Learning Repository
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [1 : 128] с шагом по степеням двойки;
- число входных объектов [1000 : 40000].
На следующих рисунках приведены графики производительности и эффективности распараллеливания алгоритма DBSCAN в зависимости от изменяемых параметров запуска.
Построим оценки масштабируемости протестированной параллельной реализации алгоритма DBSCAN:
По числу процессов - при увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.
По размеру задачи - При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.
При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.
Исследованная параллельная реализация на языке C++
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Scikit learn (Python, последовательная реализация)
- Northwestern University (C++, параллельная реализация kd-tree)
- github/ContinuumIO (Python, параллельная реализация)
- github/propanoid (C++, последовательная реализация VP tree)
- github/dparks1134 (С++, последовательная реализация)
- Disjoint-Set Data Structure based Parallel DBSCAN (C++ параллельная реализация kd-tree)
- github/bwoneill (Spark/Python параллельная реализация kd-tree)
- github/alitouka (Spark/Scala параллельная реализация)
- CRAN (R, последовательная реализация)
3 Литература
<references \> <references \>(A Fast Parallel Clustering Algorithm for Large Spatial Databases, JOCHEN JAGER, HANS-PETER KRIEGEL)
<references \>(АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ, Пестунов Игорь Алексеевич, Синявский Юрий Николаевич)
- ↑ A density-based algorithm for discovering clusters in large spatial database / M. Ester, H.-P. Kriegel, J. Sander, X. Xu // Proc. 1996 Intern. Conf. on Knowledge Discovery and Data Mining. – 1996. – P. 226 – 231.
- ↑ https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/DBSCAN-Illustration.svg/400px-DBSCAN-Illustration.svg.png
- ↑ "Xu, X. A fast parallel clustering algorithm for large spatial databases / X. Xu, M. Ester, H.-P. Kriegel // Proc. 1999 Intern. Conf. on Knowledge Discovery and Data Mining. – 1999. – Vol. 3, is. 3. – P. 263 – 290.
- ↑ https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png
- ↑ АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ/ И. А. Пестунов, Ю. Н. Синявский// Вестник Кемеровского государственного университета. – 2012. – P. 263– 299.
