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

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

2017-02-08T19:58:19Z

Dmitry: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 5. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1 : 128] с шагом по степеням двойки;
* число входных объектов [1000 : 40000].

[[Файл:График масштабируемостиv2.png|thumb|center|800px|Рис. 6. График масштабируемости DBSCAN]]

На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:

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

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

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

[https://github.com/ByDmitryT/DBSCAN Реализация на языке C++]

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-08T19:46:40Z

Dmitry: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 5. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

* число процессоров [1 : 128] с шагом по степеням двойки;
* число входных объектов [1000 : 40000].

[[Файл:График масштабируемости.png|thumb|center|800px|Рис. 6. График масштабируемости DBSCAN]]

На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:

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

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

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

[https://github.com/ByDmitryT/DBSCAN Реализация на языке C++]

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-07T16:47:58Z

Dmitry: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 5. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

[[Файл:График масштабируемости.png|thumb|center|800px|Рис. 6. График масштабируемости DBSCAN]]

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

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

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

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-07T16:47:35Z

Dmitry: /* Информационный граф */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 5. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

[[Файл:График масштабируемости.png|thumb|center|800px|Рис. 5. График масштабируемости DBSCAN]]

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

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

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

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-07T16:46:43Z

Dmitry: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов.

[[Файл:График масштабируемости.png|thumb|center|800px|Рис. 5. График масштабируемости DBSCAN]]

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

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

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

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-07T16:45:11Z

Dmitry: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

[[Файл:График масштабируемости.png|thumb|center|800px|Рис. 5. График масштабируемости DBSCAN]]

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-07T13:32:45Z

Dmitry: /* Макроструктура алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.

Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-05T12:24:29Z

Dmitry: /* Математическое описание алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-05T12:23:50Z

Dmitry: /* Математическое описание алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MCP</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MCP_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MCP</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:35:18Z

Dmitry:

{{Assignment}}
{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:33:33Z

Dmitry: /* Математическое описание алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math><ref>Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.</ref>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:32:02Z

Dmitry: /* Схема реализации последовательного алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа<ref>Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.</ref>. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:30:25Z

Dmitry: /* Свойства алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее<ref>http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy</ref>.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:27:48Z

Dmitry: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math><ref>https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)</ref>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:24:40Z

Dmitry: /* Существующие реализации алгоритма */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn] включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.

[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).

[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath] содержит java-реализацию алгоритма выполняющегося за квадратичное время.

[//en.wikipedia.org/wiki/ELKI ELKI] предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.

[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka] содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.

[//en.wikipedia.org/wiki/R_(programming_language) GNU R] содержит DBSCAN в [//cran.r-project.org/web/packages/fpc/index.html fpc] пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R [//cran.r-project.org/web/packages/dbscan/index.html dbscan].

= Литература =

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

2017-02-01T19:21:57Z

Dmitry: /* Информационный граф */

{{algorithm
| name = Плотностный алгоритм кластеризации DBSCAN
| serial_complexity = <math>O(n \log n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
}}
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</math>, для которых следующее неравенство будет истинно:

<math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>

Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как [//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние] или с помощью [//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского].

Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>.

Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:

<math>M_\varepsilon(X) \ge MPC</math>

Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1).

[[Файл:Окруженная_точка_при_MPC_=_5.png|thumb|center|300px|Рис. 1. Окруженная точка при MPC = 5]]

Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math>MPC</math>), если точка <math>X \in M(X)</math>, т.е. точка <math>X</math> – это одна из точек <math>f</math> для другого окружения (соседства), где <math>f</math> – окруженная точка (рис. 2).

[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]

Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).

[[Файл:Достижимость_по_плотности.png|thumb|center|300px|Рис. 3. Достижимость по плотности]]

Точка <math>X</math> соединена (связана) по плотности с точкой <math>f</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) если существует точка <math>e</math> такая, что обе точки <math>X</math> и <math>f</math> являются достижимыми от точки <math>e</math> (согласно <math>\varepsilon</math> и <math>MCP</math>) (рис. 4).

[[Файл:Соединение_по_плотности.png|thumb|center|300px|Рис. 4. Соединение по плотности]]

Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.

В этом случае, под кластером понимается непустое подмножество точек <math>G</math> из набора данных <math>D</math>, которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если <math>X \in G</math> и <math>f</math> достижима по плотности от точки <math>X</math>, тогда и <math>f \in G</math>, это значит, что обе точки принадлежат одному кластеру.

Свойство связности гласит, что каждый объект в подмножестве <math>G</math> соединен по плотности со всеми объектами кластера (при заданных <math>\varepsilon</math> и <math>MCP</math>).

Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств:

<math>D= \{ G_1, G_2,..., G_m, N \}</math>,

где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

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

Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки <math>X</math> входного множества <math>D</math>. Основное время работы алгоритма используется на функцию <math>dist(var1, var2)</math>, определяющую расстояние между объектами выборки <math>D</math> и сравнение расстояния с заданной <math>\varepsilon</math> для того, чтобы определить "соседствующие" точки.

== Макроструктура алгоритма ==
Вычисление расстояния между двумя объектами из выборки <math>D</math> осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: <math>dist(u,v)=\sqrt{(u_1-v_1)^2+(u_2-v_2)^2+...+(u_n-v_n)^2} = \sqrt{\sum_{k=1}^n(u_k-v_k)^2}.</math>

Также возможно использование метрики Минковского, что является обобщением евклидова расстояния:

<math>dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p}</math>.

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

Реализация алгоритма DBSCAN может быть разделена на два этапа. В первую очередь из всего набора данных <math>D</math> необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта <math>X</math> из набора данных <math>D</math> определить:

1) принадлежит ли текущий объект к какому-нибудь из кластеров;

2) является ли текущий объект окруженной точкой.

Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:

for <math>\forall X \in D</math>
<math>\{</math>
if <math> (X \in G_i, i= \overline{1,n})</math>
<math>\{</math>
if <math> (X_i \in M_\varepsilon(X))</math>
<math>\{</math>
find <math>X_i \in D</math> достижимы по плотности
from <math>X_i \in M_\varepsilon(X)</math>
<math>\}</math>
else if <math> (X_i \notin M_\varepsilon(X)</math> and <math>X</math> не достижим от любого другого объекта <math>)</math>
<math>\{</math>
<math>X \in N</math>
<math>\}</math>
<math>\}</math>

параметры <math>\varepsilon</math> и <math>MCP</math> задаются пользователем.

== Последовательная сложность алгоритма ==

Сложность алгоритма зависит от поиска всех точек в <math>\varepsilon</math>-окрестности конкретной точки <math>X</math> из выборки <math>D</math>. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность <math>O(n^2)</math> (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до <math>O(\text{n log n})</math>.

== Информационный граф ==

Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.

* Задаются параметры <math>\varepsilon</math> и <math>MCP</math>.
* На входе алгоритма набор данных <math>D</math> разбивается на множество точек <math>X_n</math>, где <math>n</math> - количество точек.
* Для каждой точки <math>X_n</math> из выборки <math>D</math> с помощью функции <math>dist(var1, var2)</math> определяется расстояние между остальными точками.
* Далее алгоритм объединяет точки <math>X_n</math>, образуя подмножества <math>M_\varepsilon(X_n)</math>, объекты которого удовлетворяют условию: <math>dist(X,f_i) \le \varepsilon</math>, <math>(i=\overline{1,n})</math>.
* Если подмножество <math>M_\varepsilon(X_n)</math> состоит из <math>MCP</math> и больше объектов (т. е. <math>M_\varepsilon(X_n) \ge MPC</math>), то подмножество <math>M_\varepsilon(X_n)</math> образует кластер <math>G_m</math>.
* Подмножество <math>N</math> включает в себя все объекты, которые не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>.

[[Файл:DBSCAN.png|thumb|center|800px|Рис. 4. Информационный граф алгоритма DBSCAN]]

== Ресурс параллелизма алгоритма ==

Ширина ярусно-параллельной формы алгоритма <math>O(m)</math>, где m - количество частей, на которые разбиваются все объекты из набора данных <math>D</math>. Высотой ярусно-параллельной формы алгоритма является <math>O(|X| \log |X|)</math>, где <math>\mid X \mid</math> - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.

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

Входные данные: множество объектов из набора данных <math>D</math>, для которых задана метрическая функция расстояния <math>dist(var1, var2)</math>. Объём входных данных: <math>n</math>.

Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: <math>n</math>.

Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра <math>MCP</math>, большие значения параметра <math>\varepsilon</math> ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.

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

* Число настраиваемых параметров равно двум: <math>\varepsilon</math> и <math>MPC</math>.
* Вычислительная сложность алгоритма <math>O(\text{n log n})</math>.
* Возможность обрабатывать большой объем данных.
* Результат не зависит от порядка ввода данных.
* Не требуется указывать количество кластеров.
* Возможность выделять кластеры в присутствии выбросов.
* Число итераций определено заранее.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

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

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

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

= Литература =

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

2017-02-01T19:13:36Z

Dmitry: /* Математическое описание алгоритма */

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

2017-02-01T18:02:45Z

Dmitry: /* Входные и выходные данные алгоритма */

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

2017-02-01T18:01:55Z

Dmitry: /* Входные и выходные данные алгоритма */

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

2017-02-01T17:55:33Z

Dmitry:

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

2017-02-01T17:47:21Z

Dmitry: /* Ресурс параллелизма алгоритма */

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

2017-02-01T17:43:10Z

Dmitry: /* Математическое описание алгоритма */

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

2017-02-01T17:23:27Z

Dmitry: /* Свойства алгоритма */

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

2017-02-01T15:55:23Z

Dmitry: /* Последовательная сложность алгоритма */

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

2017-02-01T15:47:12Z

Dmitry: /* Схема реализации последовательного алгоритма */

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

2017-02-01T15:46:22Z

Dmitry: /* Схема реализации последовательного алгоритма */

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

2017-02-01T15:20:05Z

Dmitry: /* Макроструктура алгоритма */

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

2017-02-01T15:14:55Z

Dmitry: /* Математическое описание алгоритма */

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

2017-02-01T14:44:37Z

Dmitry: /* Вычислительное ядро алгоритма */

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

2017-02-01T14:15:16Z

Dmitry: /* Математическое описание алгоритма */

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

2017-02-01T13:47:59Z

Dmitry:

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

2017-01-20T02:52:21Z

Dmitry:

Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.

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

Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M(X)</math> будет включать в себя такие точки
  n,1i,f
i 
, для которых следующее не-
равенство будет истинно
    n,1i,f,Xdist
i  . (1).
Функция
)2var,1(vardist
определяет расстоя-
ние между объектами выборки
D
. Это расстояние
может вычисляться различными способами,
например, как евклидово расстояние или с помо-
щью метрики Минковского.
Вторым параметром определения плотности
точек является MCP – это минимальное количество
точек, которые расположены ближе всего к данной
точке согласно определенному радиусу .
Точка
  n,1i,f
i 
будет являться окруженной
точкой (согласно

и
MCP
) если

   MCPX . (2)
Это значит, что точка
  n,1i,f
i 
окружен-
ная, если количество «соседствующих» точек вы-
борки
D
окажется большим, либо равным значе-
нию параметра
MCP
(рис. 1).
Точка Х является прямо достижимой по плот-
ности от точки
f
(при соответствующих  и
MCP
), если точка
   XX , т.е. точка Х – это
одна из точек f для другого окружения (соседства),
где f – окруженная точка (рис. 2).

Рис. 1. Окруженная
точка при МСР = 5
Рис. 2. Точка Х прямо достижима
по плотности от точки f
Достижимость по плотности – это транзитив-
ное замыкание прямо достижимой по плотности
точки. Точка
f
достижима по плотности из точки
X
, но точка
X
не достижима по плотности из точ-
ки
f
(рис. 3).

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

Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждой точки входного множества <math>X</math>.

Для решения этой задачи требуется найти расстояния между любыми двумя точками множества <math>X</math> по заданной метрике. Например, если используется расстояние Минковского порядка <math>k</math>, то расстояние между точками <math>p=(p_1,...,p_n) \in X</math> и <math>q=(q_1,...,q_n) \in X</math> вычисляется как <math>D(p, q) = (\sum_{i = 1}^{n}|p_i - q_i|^k)^{1 / k}</math>, частным случаем которой при <math>k = 2</math> является широко распространённая евклидова метрика <math>D(p, q) = \sqrt{\sum_{i = 1}^{n} (p_i - q_i)^2}</math>.

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

Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют вызовы функции <math>request\_neighbours</math> получения <math>\varepsilon</math>-соседей и нахождение расстояний между точками множества <math>X</math>.

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

<math>DBSCAN</math> проходит через все точки множества <math>X</math> и определяет, являются ли они шумом или началом нового кластера.
В последнем случае новому кластеру присваивается уникальный номер и вызывается функция расширения кластера.

<math>DBSCAN(\varepsilon, MinPts)</math>
<math>C = 0</math>
for <math>\forall p \in X</math>
if <math>p</math> is visited then
continue
mark <math>p</math> as visited
<math>neighbours</math> = <math>request\_neighbours(p, \varepsilon)</math>
if <math>| neighbours | < MinPts</math> then
mark <math>p</math> as <math>NOISE</math>
else
<math>C = next\_cluster</math>
<math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>

<math>expand\_cluster</math> рекурсивно проходит через все точки множества <math>neighbours</math> - соседей точки <math>p</math>,
и определяет, принадлежат ли эти точки тому же кластеру <math>C</math>, тем самым расширяя этот кластер.

<math>expand\_cluster(p, neighbours, C, \varepsilon, MinPts)</math>
add <math>p</math> to cluster <math>C</math>
for <math>\forall p' \in neighbours</math>
if <math>p'</math> is not visited
mark <math>p'</math> as visited
<math>neighbours'</math> = <math>request\_neighbours(p, \varepsilon)</math>
if <math>| neighbours' | \ \ge MinPts</math>
<math>neighbours</math> = <math>neighbours \cup neighbours'</math>
if <math>p'</math> is not yet member of any cluster
add <math>p'</math> to cluster <math>C</math>

<math>request\_neighbours</math> возвращает для точки <math>p</math> множество всех её <math>\varepsilon</math>-соседей,
используя функцию расстояния <math>D</math>
<math>request\_neighbours(p, \varepsilon)</math>
return <math>\{ p' \ | \ \forall p' \in X: D(p, p') < \varepsilon \}</math>

== Последовательная сложность алгоритма ==

DBSCAN проходит через каждую точку входного множества, возможно, по несколько раз. Временная сложность зависит в большей степени от вызова функции <math>request\_neighbours</math> (нахождение <math>\varepsilon</math>-соседей для заданной точки). Эта функция вызывается ровно один раз для каждой точки множества <math>X</math>.

Если использовать индексированную структуру данных (например, R-деревья), выполняющую операцию <math>request\_neighbours</math> за <math>O(\log n)</math>, то суммарная сложность алгоритма в среднем составит <math>O(n \log n)</math>, с учётом хорошо подобранного параметра <math>\varepsilon</math>, такого что в среднем <math>request\_neighbours</math> возвращает <math>O(\log n)</math> точек. Без использования ускоряющих структур или на вырожденных данных (таких, что все точки находятся на расстоянии меньшем, чем <math>\varepsilon</math> друг от друга) сложность по времени в худшем случае будет <math>O(n^2)</math>.

Расстояния между точками можно вычислить заранее за <math>O(\frac {n(n - 1)}{2})</math>, например в виде матрицы расстояний, но это потребует <math>O(n^2)</math> памяти. Иначе, расстояния будут вычисляться при каждом запуске функции <math>request\_neighbours</math> за <math>O(n)</math> и потребуют <math>O(n)</math> памяти. Итоговая сложность вычисления расстояний в таком случае составляет <math>O(n^2)</math>. Сложность рассчета расстояний зависит от природы объектов из <math>X</math> и заданной метрики <math>D</math>. Например, если <math>X\subset\mathbb{R}^m</math>, то сложность равна <math>O(m)</math>, но оценка может быть улучшена при использовании векторных операций.

== Информационный граф ==

Опишем граф алгоритма<ref>Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.</ref><ref>Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.</ref><ref>Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.</ref>.

[[File:Dbscan abstract.png |thumb|right|320px| Рис. 2. Внешний цикл алгоритма.]]

На рис. 2 изображен информационный граф внешнего цикла алгоритма, который соответствует коду основной функции <math>DBSCAN</math>:
*Макрооперация ''Init'' заключается в получении множества <math>X</math> и инициирования вспомогательных структур.
*Макрооперация ''Choose'' производит выбор непосещенной точки из <math>X</math>.
*Макрооперация ''Build cluster'' строит кластер, если точка ядровая, или объявляет ее шумом.

Переход от ''Build cluster'' к ''Choose'' заключает в себе зависимость данных о принадлежности некоторых точек к текущему кластеру или шуму и об их посещенности.

[[File:Expand cluster 2.png |thumb|right|600px| Рис. 3. Расширение кластера.]]

На рис. 3 изображен информационный граф алгоритма расширения кластера из начальной точки кластера:
*Макрооперация ''Init'' заключается в создании кластера из его начальной вершины.
*Макрооперация ''Nε'' вычисляет множество <math>\varepsilon</math>-соседей.
*Желтым цветом обозначены узлы, в которых точки из <math>\varepsilon</math>-соседей классифицируются на ядровые, граничные точки и шум. В рамках операции для конкретного соседа вычисляется множество его <math>\varepsilon</math>-соседей.
*Макрооперации ''Ñε'', ''Ňε'', ... производят объединение входных множеств.
*Макрооперация ''Ø'' выполняется тогда, когда объединение входных множеств является пустым.

[[File:N eps 3.png |thumb|right|320px| Рис. 4. Подсчет <math>\varepsilon</math>-соседей.]]

На рис. 4 изображен информационный граф алгоритма вычисления множества <math>\varepsilon</math>-соседей:
*Операция ''D'' - вычисление расстояния между точками.
*Операция ''ε'' - сравнение расстояния с ε.
*Операция ''U'' - объединение результатов.

== Ресурс параллелизма алгоритма ==

Поиск <math>\varepsilon</math>-соседей требует вычисления <math>n</math> расстояний (функция <math>D</math>) и выполнения <math>n</math> сравнений с <math>\varepsilon</math>. Эти операции для каждой пары точек независимы и могут быть выполнены параллельно. Таким образом, при наличии неограниченного числа процессоров сложность поиска составит <math>O(1)</math>. Т.к. поиск выполняется для каждой точки ровно один раз, параллельная сложность всего алгоритма составит <math>O(n)</math>.

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

Вход алгоритма: множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидово расстояние между векторами из <math>\mathbb{R}^n</math>.

Выход алгоритма: размеченное множество точек <math>X</math>, в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из <math>X</math> сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера <math>|X|</math>.

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

Соотношение последовательной и параллельной сложностей алгоритма является линейным (отношение квадратичной к линейной).

При этом вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных линейна.

=== Преимущества алгоритма ===

# не требует указывать число кластеров;
# может определять кластера произвольной формы;
# может определять шум и устойчив к выбросам;
# требует всего два параметра и по в большинстве случаев не чувствителен к порядку заданных точек;
# параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с <math>\varepsilon</math>).

=== Недостатки алгоритма ===

# не детерминирован: граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован. Впрочем, от недетерминизма можно избавиться, если считать все граничные точки шумом (алгоритм DBSCAN*);
# качество алгоритма зависит от используемой функции расстояния <math>D</math>. Наиболее часто используемое Евклидово расстояние в многомерных множествах может оказаться практически бесполезным из-за так называемого "проклятия размерности", значительно затрудняя нахождение подходящего значения <math>\varepsilon</math>;
# не может выделять кластеры, имеющие разную плотность, так как параметры алгоритма не могут быть выбранны отдельно для каждого кластера.

= Программная реализация алгоритма =

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

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

!!! ЭКСПЕРИМЕНТЫ ДО 15 НОЯБРЯ !!!

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

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

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

* [http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html Scikit learn (Python)]
* [https://cran.r-project.org/web/packages/dbscan/dbscan.pdf R-project] ([https://github.com/mhahsler/dbscan github])
* [https://www.mathworks.com/matlabcentral/fileexchange/52905-dbscan-clustering-algorithm Matlab]
* P-DBSCAN (Parallel DBSCAN)<ref>Chen, Min, Xuedong Gao, and HuiFei Li. "Parallel DBSCAN with priority r-tree." Information Management and Engineering (ICIME), 2010 The 2nd IEEE International Conference on. IEEE, 2010.</ref>
* Parallel DBSCAN with MPI<ref>Savvas, Ilias K., and Dimitrios Tselios. "Parallelizing DBSCaN Algorithm Using MPI." Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE), 2016 IEEE 25th International Conference on. IEEE, 2016.</ref>
* PDSDBSCAN (Parallel Disjoint-Set DBSCAN)<ref>Patwary, Md Mostofa Ali, et al. "A new scalable parallel DBSCAN algorithm using the disjoint-set data structure." High Performance Computing, Networking, Storage and Analysis (SC), 2012 International Conference for. IEEE, 2012.</ref>

= Литература =

<references />

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

2016-12-19T15:35:05Z

Dmitry: Новая страница: «Авторы описания: Титов Д.Е. = Свойства и структура алгоритма = == Общее оп…»

Авторы описания: [[Участник:Dmitry | Титов Д.Е.]]

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

== Общее описание алгоритма ==

Участник:Dmitry

2016-12-19T15:20:41Z

Dmitry: Новая страница: «Титов Дмитрий Евгеньевич, студент факультета ВМК МГУ имени М.В. Ломоносова, 619 группа»

Титов Дмитрий Евгеньевич, студент факультета ВМК МГУ имени М.В. Ломоносова, 619 группа