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

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-11T18:06:05Z

Elmon: Баг с блоком {{Assignment}} в конце статьи, переместил в начало

{{Assignment}}

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
Вычислительная мощность алгоритма (отношение числа операций к объему входных и выходных данных) является логарифмической.
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan Параллельная реализация для Python на OpenMP/MPI]
* [https://github.com/propanoid/DBSCAN Параллельная реализация для C++ на Boost и OpenMP с использованием VP-дерева]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary Параллельная реализация для С++ на OpenMP с использованием системы непересекающихся множеств]
* [https://github.com/bwoneill/pypardis Параллельная реализация для многомерных данных для Python на SciPy и NumPy ]
* [https://github.com/mhahsler/dbscan Последовательная реализация для R на С++]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T21:14:29Z

Elmon: Вернул на проверку

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
Вычислительная мощность алгоритма (отношение числа операций к объему входных и выходных данных) является логарифмической.
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan Параллельная реализация для Python на OpenMP/MPI]
* [https://github.com/propanoid/DBSCAN Параллельная реализация для C++ на Boost и OpenMP с использованием VP-дерева]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary Параллельная реализация для С++ на OpenMP с использованием системы непересекающихся множеств]
* [https://github.com/bwoneill/pypardis Параллельная реализация для многомерных данных для Python на SciPy и NumPy ]
* [https://github.com/mhahsler/dbscan Последовательная реализация для R на С++]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]
{{Assignment}}

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T21:10:51Z

Elmon: Переместил референс изображения так, чтобы его было лучше видно.

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T21:06:13Z

Elmon: Добавлено описание ссылок на алгоритмы

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
Вычислительная мощность алгоритма (отношение числа операций к объему входных и выходных данных) является логарифмической.
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan Параллельная реализация для Python на OpenMP/MPI]
* [https://github.com/propanoid/DBSCAN Параллельная реализация для C++ на Boost и OpenMP с использованием VP-дерева]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary Параллельная реализация для С++ на OpenMP с использованием системы непересекающихся множеств]
* [https://github.com/bwoneill/pypardis Параллельная реализация для многомерных данных для Python на SciPy и NumPy ]
* [https://github.com/mhahsler/dbscan Последовательная реализация для R на С++]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T20:53:48Z

Elmon: Добавена вычислительная мощность алгоритма

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
Вычислительная мощность алгоритма (отношение числа операций к объему входных и выходных данных) является логарифмической.
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T20:49:36Z

Elmon: Добавлено описание информационного графа

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px|Рис. 2. Граф алгоритма DBSCAN с отображением входных данных. Element — входные данные, Neighbours — операция поиска соседей, Check — операция проверки условий, добавления вершины к кластеру и выбора новой, Out — результаты.]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T20:39:55Z

Elmon: Добавлены комментарии к схеме реализации последовательного алгоритма

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
# Skipping already visited elements
continue
mark <math>p</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
# Found new cluster
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
# Looking for more neighbors, until none left
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
# If element is visited, then either it was marked as part of other cluster, or as noise
mark <math>q</math> as <math>visited</math>
# [Core operation] Searching for neighbors
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
# We can expand neighbors with new elements from element <math>q</math>
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
# If it's noise — mark as edge-element part of cluster
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px| Граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T20:28:22Z

Elmon: Описаны подробнее пункты 1.3, 1.4 (Вычислительное ядро алгоритма, Макроструктура алгоритма) соотвественно

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию. Основные операции вычислительного ядра алгоритма: нахождение расстояние между элементами множества и сравнение его с порогом для определения того, являются ли один элемент достижимым напрямую из другого.

== Макроструктура алгоритма ==

Алгоритм DBSCAN предполагает использование пространственной структуры данных (структуры, ориентированной на индексацию многомерной информации, такой как географические данные) — такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
continue
mark <math>p</math> as <math>visited</math>
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
mark <math>q</math> as <math>visited</math>
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px| Граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-11-01T20:19:59Z

Elmon: Добавлены свойства алгоритма (пункт 1.1)

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

Алгоритм имеет ряд отличительных свойств:
* Не требуется заранее определять число кластеров
* Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
* Хорошо работает в условиях зашумленных входных данных

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию.

== Макроструктура алгоритма ==
Алгоритм DBSCAN предполагает использование пространственной структуры данных: такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
continue
mark <math>p</math> as <math>visited</math>
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
mark <math>q</math> as <math>visited</math>
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px| Граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]

Участник:Elmon

2016-10-15T20:49:41Z

Elmon: Новая страница: «Гилевич Вячеслав Вячеславович, студент факультета ВМК МГУ имени М.В. Ломоносова, кафедра…»

Гилевич Вячеслав Вячеславович, студент факультета ВМК МГУ имени М.В. Ломоносова, кафедра Алгоритмических языков

Участник:Elmon/Плотностный алгоритм кластеризации DBSCAN

2016-10-15T20:48:52Z

Elmon: Новая страница: «{{Assignment}} {{algorithm | name = Плотностный алгоритм кластеризации DBSCAN | serial_complexity = <math>O(n \log n)…»

{{Assignment}}
{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| pf_height = <math>O(|H| \log |H|)</math>
| pf_width = <math>O(w)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}

Основной автор описания: [[User:Elmon|Гилевич В.В.]]

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

== Общее описание алгоритма ==
Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

Алгоритм 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.</ref> — плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы.

== Математическое описание алгоритма ==

=== Исходные данные ===
Множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

=== Вычисляемые данные===
Множество пар из элемента множества <math>X</math>, и соответствующий ему номер кластера.

=== Параметры алгоритма ===
* <math>\varepsilon</math> — максимальное расстояние между соседями;
* <math>MinPts</math> — минимальное количество элементов находящихся <math>\varepsilon</math>-окрестности данного элемента для создания кластера.

=== Определения ===

* ''ядровой элемент'': элемент <math>p</math> является ядровым, если количество элементов в <math>\varepsilon</math>-окрестности, включая сам элемент <math>p</math> больше или равно <math>MinPts</math>;

* ''достижимость напрямую элемента <math>p</math> из элемента q'': элемент <math>p</math> считается достижимым напрямую из элемента <math>q</math>, если элемент <math>q</math> является ядровым, а элемент <math>p</math> находится в <math>\varepsilon</math>-окрестности элемента q;

* ''достижимость элемента <math>p</math> из элемента <math>q</math>'': элемент <math>p</math> достижим из элемента <math>q</math>, если существует путь <math>p_1, \dots, p_n</math>, где <math>p_1 = p</math> и <math>p_n = q</math>, где <math>p_{i + 1}</math> напрямую достижим из <math>p_{i}</math>;

* ''шум'': все элементы, недостижимые из какого-либо другого считаются шумом.

Так как достижимость не является симметричным отношением (никакой элемент не может быть достижим из неядрового, вне зависимости от расстояния), то предлагается ввести следующее отношение:

* ''связанность элемента p и элемента q'': элемент <math>p</math> считается связанным с <math>q</math>, если существует такой элемент <math>o</math>, что <math>p</math> и <math>q</math> достижимы из него.

Таким образом ''кластер'' должен удовлетворять двум условиям:
* Все элементы внутри кластера взаимно связанны;
* Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.

[[File:DBSCAN-Illustration.svg|thumb|right|400px| Рис. 1<ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>. Для ''MinPts'' = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.]]

=== Пошаговое описание алгоритма ===

#Выбирается произвольная непосещенный элемент <math>p</math>.
#Элемент <math>p</math> помечается как посещенный.
#Проверяется, является ли элемент <math>p</math> ядровым.
#*Если элемент <math>p</math> является ядровым, то:
#**Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
#**Все элементы из <math>\varepsilon</math>-окрестности элемента <math>p</math> добавляются в его кластер (им присваевается номер кластера элемента <math>p</math>);
#**Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
#*Если элемент <math>p</math> не является ядровым, то <math>p</math> объявляется шумом. Алгоритм продолжается с шага 4.
#Если остались непосещенные точки, то алгоритм продолжается с шага 1.

== Вычислительное ядро алгоритма ==

Вычислительным ядром алгоритма является поиск элементов в <math>\varepsilon</math>-окрестности каждого элемента входного множества <math>X</math>. На эту часть алгоритма приходится основное время работы алгоритма, так как для каждого элемента необходимо выполнить эту операцию.

== Макроструктура алгоритма ==
Алгоритм DBSCAN предполагает использование пространственной структуры данных: такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за <math>O(\log n)</math>. Сложность построения таких структур <math>O(n \log n)</math>, таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

<math>DBSCAN(X, \varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>p</math> in <math>X</math>:
if <math>p</math> is <math>visited</math>:
continue
mark <math>p</math> as <math>visited</math>
<math>neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}</math>
if <math>| neighbours | \ge MinPts</math>:
<math>C = C + 1</math>
add <math>p</math> to cluster <math>C</math>
for <math>q \in neighbours</math>:
if <math>q</math> is not <math>visited</math>:
mark <math>q</math> as <math>visited</math>
<math>q\_neighbours</math> = <math>\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}</math>
if <math>| q\_neighbours | \ge MinPts</math>:
<math>neighbours</math> = <math>neighbours \cup q\_neighbours</math>
if <math>q</math> has no cluster mark:
mark <math>q</math> as part of cluster <math>C</math>
else:
mark <math>p</math> as <math>noise</math>

== Последовательная сложность алгоритма ==
Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его <math>\varepsilon</math>-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью <math>O(\log n)</math>. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма <math>O(n \log n)</math>. При отказе от использования таких сткрутр сложность возрастает до <math>O(n^2)</math>, так как для каждого элемента требуется проверить на нахождение в <math>\varepsilon</math>-окрестности все остальные элементы множества.

== Информационный граф ==
Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:
* <math>i</math> — меняется от <math>1</math> до <math>k + f</math>, принимая все целочисленные значения, где <math>k</math> — число результирующих кластеров, <math>f</math> — число элементов помеченных, как шум
* <math>j</math> — меняется от <math>1</math> до <math>t</math>, принимая все целочисленные значения, где <math>t</math> — число вершин в кластере <math>i</math>
Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

[[File:DBSCAN algo graph.png|thumb|center|800px| Граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==
Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма <math>O(w)</math>, где <math>w</math> — количество частей, на которые разбиваются все входное множество объектов <math>X</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|H| \log |H|)</math>, где <math>|H|</math> — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN<ref>[http://www.ece.northwestern.edu/~choudhar/Publications/ANewScalableParallelDBSCANAlgorithmUsingDisjointSetDataStructure.pdf A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary]</ref>, применяемый к каждой отдельной части разбиения.

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

'''Входные данные''': множество <math>X</math>, на котором определена функция расстояния <math>D</math>.

'''Объём входных данных''': <math>n</math> (размерность входящего множества)

'''Выходные данные''': размеченное множество точек <math>X</math>, в котором каждому элементу соответствует номер его кластера.

'''Объём выходных данных''': <math>n</math> (размерность выходящего множества)

== Свойства алгоритма ==
* Алгоритм может определять кластера произвольной формы;
* Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
* Не требуется задание числа кластеров;
* Может выделять кластеры в присутствии шума;
* Не детерминирован относительно граничных точек кластеров.

= Программная реализация алгоритма =
== Особенности реализации последовательного алгоритма ==
== Локальность данных и вычислений ==
== Возможные способы и особенности параллельной реализации алгоритма ==
== Масштабируемость алгоритма и его реализации ==
== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==

* [https://github.com/ContinuumIO/parallel_dbscan]
* [https://github.com/propanoid/DBSCAN]
* [https://github.com/ahbarnett/validspike/tree/master/contrib/dbscan_patwary]
* [https://github.com/bwoneill/pypardis]
* [https://github.com/mhahsler/dbscan]

= Литература =
<references \>
<references \>
<references \>

[[en:DBSCAN]]