Уровень алгоритма

Участник:Elena777mc/Плотностный алгоритм кластеризации DBSCAN: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 138 промежуточных версий 6 участников)
Строка 1: Строка 1:
 +
{{Assignment|Sleo|Dexter}}
 +
 
{{algorithm
 
{{algorithm
 
| name              = Плотностный алгоритм кластеризации DBSCAN
 
| name              = Плотностный алгоритм кластеризации DBSCAN
−
| serial_complexity = <math>-</math>
+
| serial_complexity = <math>O(n \log n)</math>
−
| pf_height        = <math>-</math>
+
| pf_height        = <math>O(|X| \log |X|)</math>
−
| pf_width          = <math>-</math>
+
| pf_width          = <math>O(m)</math>
−
| input_data        = <math>-</math>
+
| input_data        = <math>n</math>
−
| output_data      = <math>-</math>
+
| output_data      = <math>n</math>
 
}}
 
}}
  
−
 
+
Основные авторы описания: [[Участник:Elena777mc|Малахова Е.С.]] (1.2, 1.4-1.8, 2.4, 2.7), [[Участник:Жаннат_Сагиолданова|Сагиолданова Ж.]] (1.1-1.3, 1.9-1.10, 3)
  
 
= Свойства и структура алгоритмов =
 
= Свойства и структура алгоритмов =
  
 
== Общее описание алгоритма ==
 
== Общее описание алгоритма ==
 +
Кластеризация – это процесс разбиения множества с <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) <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 экспериментально показали, что их алгоритм способен распознать кластеры различной формы.
 +
Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера плотность точек (объектов) заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Еще точнее, для каждой точки кластера ее окрестность в диапазоне заданного радиуса должна содержать не менее некоторого числа точек, которое задается пороговым значением.
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
 +
 +
[[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> . Между объектами можно считать расстояния.
 +
 +
Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных.  <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>. Тогда точка y достижима из точки x, если существует последовательность точек <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}
Строка 26: Строка 48:
 
Здесь значение <math>MinPts</math> задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее <math>MinPts \  \varepsilon</math> -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее <math>MinPts \  \varepsilon </math> -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы.
 
Здесь значение <math>MinPts</math> задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее <math>MinPts \  \varepsilon</math> -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее <math>MinPts \  \varepsilon </math> -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы.
 
При такой постановке задачи, под кластером понимается максимальное связное подмножество множества <math>X</math> . Точки, не попавшие в какой-либо кластер (не принадлежащие <math>\varepsilon</math> -окрестности какого-либо «ядра»), относятся к классу «шум».
 
При такой постановке задачи, под кластером понимается максимальное связное подмножество множества <math>X</math> . Точки, не попавшие в какой-либо кластер (не принадлежащие <math>\varepsilon</math> -окрестности какого-либо «ядра»), относятся к классу «шум».
 +
 +
== Вычислительное ядро алгоритма ==
 +
 +
 +
Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждого объекта входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как требуется найти всех соседей для каждого объекта заданного множества. Основные операции, которые применяются в вычислительном ядре  алгоритма: нахождение расстояние между объектами и сравнение расстояния с порогом для определения того, являются ли данные объекты <math>\varepsilon</math>-соседями.
 +
 +
== Макроструктура алгоритма ==
 +
Алгоритм 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>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 < 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') < \varepsilon \}</math>
 +
 +
== Последовательная сложность алгоритма ==
 +
Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать R*-дерево или kd-дерево для определения соседних объектов со сложностью <math>O(\log n)</math>, то сложность алгоритма <math>O(n \log n)</math>. Если не использовать эти структуры, то в худшем случае алгоритм будет иметь сложность <math>O(n^2)</math>, так как придется считать полную матрицу расстояний между объектами.
 +
 +
== Информационный граф ==
 +
В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма.
 +
[[File:Dbscan_schema.jpg|1000px|thumb|center|Рис.1. Общая информационная структура алгоритма]]
 +
Разбиение данных происходит с помощью пространственной структуры данных (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>]]
 +
 +
== Ресурс параллелизма алгоритма ==
 +
Как видно из общей структуры графа алгоритма, ширина ярусно-параллельной формы алгоритма <math>O(m)</math>, где m - количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм PDBSCAN, применяемый к каждой отдельной части разбиения.
 +
 +
== Входные и выходные данные алгоритма ==
 +
 +
'''Входные данные''': множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидова метрика между векторами из <math>{R}^n</math>.
 +
 +
'''Объём входных данных''': n (размерность входящего множества)
 +
 +
'''Выходные данные''': размеченное множество точек 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++]
 +
 +
== Динамические характеристики и эффективность реализации алгоритма ==
 +
== Выводы для классов архитектур ==
 +
== Существующие реализации алгоритма ==
 +
 +
* [http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html Scikit learn (Python, последовательная реализация)]
 +
* [http://cucis.ece.northwestern.edu/projects/Clustering/download_code_dbscan.html Northwestern University (C++, параллельная реализация kd-tree)]
 +
* [https://github.com/ContinuumIO/parallel_dbscan github/ContinuumIO (Python, параллельная реализация)]
 +
* [https://github.com/propanoid/DBSCAN github/propanoid (C++, последовательная реализация VP tree)]
 +
* [https://github.com/dparks1134/DBSCAN github/dparks1134 (С++, последовательная реализация)]
 +
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary Disjoint-Set Data Structure based Parallel DBSCAN (C++ параллельная реализация kd-tree)]
 +
* [https://github.com/bwoneill/pypardis github/bwoneill (Spark/Python параллельная реализация kd-tree)]
 +
* [https://github.com/alitouka/spark_dbscan github/alitouka (Spark/Scala параллельная реализация)]
 +
* [https://github.com/mhahsler/dbscan CRAN (R, последовательная реализация)]
 +
 +
= Литература =
 +
<references \>
 +
<references \>[https://pdfs.semanticscholar.org/a3f8/a3948e5999def4a0819d0dbaef2ae05e1599.pdf (A Fast Parallel Clustering Algorithm for Large Spatial Databases, JOCHEN JAGER, HANS-PETER KRIEGEL)]
 +
<references \>[http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy (АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ, Пестунов Игорь Алексеевич, Синявский Юрий Николаевич)]
 +
 +
[[en:Cholesky decomposition]]
 +
 +
[[Категория:Законченные статьи]]

Текущая версия на 14:56, 3 декабря 2016

Symbol confirmed.svgЭта работа успешно выполнена
Преподавателю: в основное пространство, в подстраницу
Данное задание было проверено и зачтено.
Проверено 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 Общее описание алгоритма

Кластеризация – это процесс разбиения множества с [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 Математическое описание алгоритма

Рис. 1. Пример ядровых, граничных и шумовых точек алгоритма. Точка A - ядровая, точки  B и С - граничные, N - шум. В данном примере MinPts = 4, Eps равен радиусу окружности [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 Информационный граф

В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма.

Рис.1. Общая информационная структура алгоритма

Разбиение данных происходит с помощью пространственной структуры данных (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], то такие объекты становятся кандидатами на слияние.

Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.

Рис.2. Пример разбиения объектов на части на основе пространственной структуры. Каждый прямоугольник соответствует части данных, каждая из которых подается на вход алгоритму PDBSCAN [4]

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 в зависимости от изменяемых параметров запуска.

Рис.1. Изменение производительности в зависимости от числа процессов и числа входных данных
Рис.2. Изменение эффективности распараллеливания в зависимости от числа процессов и числа входных данных

Построим оценки масштабируемости протестированной параллельной реализации алгоритма DBSCAN:

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

По размеру задачи - При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.

При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.

Исследованная параллельная реализация на языке C++

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

<references \> <references \>(A Fast Parallel Clustering Algorithm for Large Spatial Databases, JOCHEN JAGER, HANS-PETER KRIEGEL)

<references \>(АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ, Пестунов Игорь Алексеевич, Синявский Юрий Николаевич)

  1. ↑ 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.
  2. ↑ https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/DBSCAN-Illustration.svg/400px-DBSCAN-Illustration.svg.png
  3. ↑ "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.
  4. ↑ https://github.com/bwoneill/pypardis/blob/master/plots/median_search_split/clusters_partitions.png
  5. ↑ АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ/ И. А. Пестунов, Ю. Н. Синявский// Вестник Кемеровского государственного университета. – 2012. – P. 263– 299.
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Elena777mc/Плотностный_алгоритм_кластеризации_DBSCAN&oldid=19974