Участник:Dmitry/Плотностный алгоритм кластеризации: различия между версиями
Dmitry (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показано 29 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
{{Assignment|ASA}} | |||
{{algorithm | |||
| name = Плотностный алгоритм кластеризации DBSCAN | |||
| serial_complexity = <math>O(n \log n)</math> | |||
| input_data = <math>n</math> | |||
| output_data = <math>n</math> | |||
}} | |||
Авторы описания: [[Участник:Dmitry | Титов Д.Е.]] | Авторы описания: [[Участник:Dmitry | Титов Д.Е.]] | ||
| Строка 14: | Строка 22: | ||
<math>dist(X,f_i) \le \varepsilon</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>. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью <span class="plainlinks">[//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского]</span>. | Функция <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>. Это расстояние может вычисляться различными способами, например, как <span class="plainlinks">[//en.wikipedia.org/wiki/Euclidean_distance евклидово расстояние]</span> или с помощью <span class="plainlinks">[//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского]</span>. | ||
Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>. | Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</math>. | ||
| Строка 20: | Строка 28: | ||
Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если: | Точка <math>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если: | ||
<math>M_\varepsilon(X) \ | <math>M_\varepsilon(X) \ge MCP</math> | ||
Это значит, что точка <math>f_i</math>, <math>(i=\overline{1,n})</math> окруженная, если количество «соседствующих» точек выборки <math>D</math> окажется большим, либо равным значению параметра <math>MCP</math> (рис. 1). | Это значит, что точка <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.png|thumb|center|300px|Рис. 1. Окруженная точка при MCP = 5]] | ||
Точка <math>X</math> является прямо достижимой по плотности от точки <math>f</math> (при соответствующих <math>\varepsilon</math> и <math> | Точка <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]] | [[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]] | ||
| Строка 46: | Строка 54: | ||
Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств: | Все объекты из набора данных <math>D</math> представляют собой совокупность подмножеств: | ||
<math>D= \{ G_1, G_2,..., | <math>D= \{ G_1, G_2,..., G_m, N \}</math>, | ||
где <math>G_1, G_2,..., | где <math>G_1, G_2,..., G_m</math> – кластеры, образованные по плотности; <math>N</math> – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств <math>G_1, G_2,..., G_m</math>. | ||
== Вычислительное ядро алгоритма == | == Вычислительное ядро алгоритма == | ||
| Строка 55: | Строка 63: | ||
== Макроструктура алгоритма == | == Макроструктура алгоритма == | ||
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами. | |||
Вычисление расстояния между двумя объектами из выборки <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>. | |||
= Программная реализация алгоритма = | = Программная реализация алгоритма = | ||
| Строка 77: | Строка 147: | ||
== Масштабируемость алгоритма и его реализации == | == Масштабируемость алгоритма и его реализации == | ||
Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++. | |||
Набор и границы значений изменяемых параметров запуска реализации алгоритма: | |||
* число процессоров [1 : 128] с шагом по степеням двойки; | |||
* число входных объектов [1000 : 40000]. | |||
[[Файл:График масштабируемостиv2.png|thumb|center|800px|Рис. 6. График масштабируемости DBSCAN]] | |||
На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы: | |||
* При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности. | |||
* При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется. | |||
* При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая. | |||
[https://github.com/ByDmitryT/DBSCAN Реализация на языке C++] | |||
== Динамические характеристики и эффективность реализации алгоритма == | == Динамические характеристики и эффективность реализации алгоритма == | ||
| Строка 83: | Строка 173: | ||
== Существующие реализации алгоритма == | == Существующие реализации алгоритма == | ||
<span class="plainlinks">[//en.wikipedia.org/wiki/Scikit-learn Scikit-Learn]</span> включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память. | |||
[//www.philippe-fournier-viger.com/spmf/SPMF SPMF] предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида). | |||
<span class="plainlinks">[//en.wikipedia.org/wiki/Apache_Commons Apache Commons Мath]</span> содержит java-реализацию алгоритма выполняющегося за квадратичное время. | |||
<span class="plainlinks">[//en.wikipedia.org/wiki/ELKI ELKI]</span> предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных. | |||
<span class="plainlinks">[//en.wikipedia.org/wiki/Weka_(machine_learning) Weka]</span> содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память. | |||
<span class="plainlinks">[//en.wikipedia.org/wiki/R_(programming_language) GNU R]</span> содержит 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]. | |||
= Литература = | = Литература = | ||
Текущая версия от 07:11, 9 февраля 2017
| Файл:Symbol wait.svg | Эта работа прошла предварительную проверку Дата последней правки страницы: 09.02.2017 Данная работа соответствует формальным критериям. Проверено ASA. |
| Плотностный алгоритм кластеризации DBSCAN | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n \log n) }[/math] |
| Объём входных данных | [math]\displaystyle{ n }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
Авторы описания: Титов Д.Е.
Свойства и структура алгоритма
Общее описание алгоритма
Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации DBSCAN лежит объединение некоторых объектов в соответствии с их внутригрупповым «соединением». Для проведения корректной процедуры кластеризации необходимо указать критерии, по которым объекты будут объединены в кластеры. Прежде всего, необходимо сказать, что кластеры представляют собой плотные области некоторых объектов в пространстве данных, разделенных между собой объектами, плотность которых значительно ниже. Расположение точек в одном кластере обусловлено их соединением, т.е. некоторой связью между собой.
Математическое описание алгоритма
Плотность точек для данной точки [math]\displaystyle{ X }[/math] определяется двумя параметрами. Первым из них является [math]\displaystyle{ \varepsilon }[/math] – радиус «соседства» (приближенности) точки [math]\displaystyle{ X }[/math]. Тогда множество [math]\displaystyle{ M_\varepsilon(X) }[/math] будет включать в себя такие точки [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math], для которых следующее неравенство будет истинно:
[math]\displaystyle{ dist(X,f_i) \le \varepsilon }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math]
Функция [math]\displaystyle{ dist(var1, var2) }[/math] определяет расстояние между объектами выборки [math]\displaystyle{ D }[/math][1]. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.
Вторым параметром определения плотности точек является [math]\displaystyle{ MCP }[/math] – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу [math]\displaystyle{ \varepsilon }[/math].
Точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] будет являться окруженной точкой (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если:
[math]\displaystyle{ M_\varepsilon(X) \ge MCP }[/math]
Это значит, что точка [math]\displaystyle{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] окруженная, если количество «соседствующих» точек выборки [math]\displaystyle{ D }[/math] окажется большим, либо равным значению параметра [math]\displaystyle{ MCP }[/math] (рис. 1).
Точка [math]\displaystyle{ X }[/math] является прямо достижимой по плотности от точки [math]\displaystyle{ f }[/math] (при соответствующих [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]), если точка [math]\displaystyle{ X \in M(X) }[/math], т.е. точка [math]\displaystyle{ X }[/math] – это одна из точек [math]\displaystyle{ f }[/math] для другого окружения (соседства), где [math]\displaystyle{ f }[/math] – окруженная точка (рис. 2).
Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка [math]\displaystyle{ f }[/math] достижима по плотности из точки [math]\displaystyle{ X }[/math], но точка [math]\displaystyle{ X }[/math] не достижима по плотности из точки [math]\displaystyle{ f }[/math] (рис. 3).
Точка [math]\displaystyle{ X }[/math] соединена (связана) по плотности с точкой [math]\displaystyle{ f }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) если существует точка [math]\displaystyle{ e }[/math] такая, что обе точки [math]\displaystyle{ X }[/math] и [math]\displaystyle{ f }[/math] являются достижимыми от точки [math]\displaystyle{ e }[/math] (согласно [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]) (рис. 4).
Кластер, сформированный на основе размещения объектов по плотности должен удовлетворять таким свойствам: максимальность; связность.
В этом случае, под кластером понимается непустое подмножество точек [math]\displaystyle{ G }[/math] из набора данных [math]\displaystyle{ D }[/math], которое удовлетворяет вышеупомянутым свойствам, причем, максимальность интерпретируется таким образом: если [math]\displaystyle{ X \in G }[/math] и [math]\displaystyle{ f }[/math] достижима по плотности от точки [math]\displaystyle{ X }[/math], тогда и [math]\displaystyle{ f \in G }[/math], это значит, что обе точки принадлежат одному кластеру.
Свойство связности гласит, что каждый объект в подмножестве [math]\displaystyle{ G }[/math] соединен по плотности со всеми объектами кластера (при заданных [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math]).
Все объекты из набора данных [math]\displaystyle{ D }[/math] представляют собой совокупность подмножеств:
[math]\displaystyle{ D= \{ G_1, G_2,..., G_m, N \} }[/math],
где [math]\displaystyle{ G_1, G_2,..., G_m }[/math] – кластеры, образованные по плотности; [math]\displaystyle{ N }[/math] – некоторое подмножество, объекты которого не принадлежат ни одному из подмножеств [math]\displaystyle{ G_1, G_2,..., G_m }[/math].
Вычислительное ядро алгоритма
Вычислительным ядром алгоритма является поиск всех "соседствующих" точек для каждой точки [math]\displaystyle{ X }[/math] входного множества [math]\displaystyle{ D }[/math]. Основное время работы алгоритма используется на функцию [math]\displaystyle{ dist(var1, var2) }[/math], определяющую расстояние между объектами выборки [math]\displaystyle{ D }[/math] и сравнение расстояния с заданной [math]\displaystyle{ \varepsilon }[/math] для того, чтобы определить "соседствующие" точки.
Макроструктура алгоритма
Основную часть алгоритма на верхнем уровне составляют множественные вычисления расстояния между объектами.
Вычисление расстояния между двумя объектами из выборки [math]\displaystyle{ D }[/math] осуществляется при помощи различных метрик. В большинстве случаев вычисляется метрика Евклида: [math]\displaystyle{ 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]\displaystyle{ dist(x,y) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{1/p} }[/math].
Схема реализации последовательного алгоритма
Реализация алгоритма DBSCAN может быть разделена на два этапа[2]. В первую очередь из всего набора данных [math]\displaystyle{ D }[/math] необходимо выделить те точки, которые являются окруженными. Затем выполнять следующую процедуру: для каждого объекта [math]\displaystyle{ X }[/math] из набора данных [math]\displaystyle{ D }[/math] определить:
1) принадлежит ли текущий объект к какому-нибудь из кластеров;
2) является ли текущий объект окруженной точкой.
Если текущий объект – окруженная точка, то все объекты, достижимые по плотности от текущего объекта, соединяем в новый кластер. В противном случае, если объект не является окруженной точкой и не достижим по плотности ни от какого объекта, то текущий объект – выброс. Псевдокод алгоритма DBSCAN можно представить следующим образом:
for [math]\displaystyle{ \forall X \in D }[/math] [math]\displaystyle{ \{ }[/math] if [math]\displaystyle{ (X \in G_i, i= \overline{1,n}) }[/math] [math]\displaystyle{ \{ }[/math] if [math]\displaystyle{ (X_i \in M_\varepsilon(X)) }[/math] [math]\displaystyle{ \{ }[/math] find [math]\displaystyle{ X_i \in D }[/math] достижимы по плотности from [math]\displaystyle{ X_i \in M_\varepsilon(X) }[/math] [math]\displaystyle{ \} }[/math] else if [math]\displaystyle{ (X_i \notin M_\varepsilon(X) }[/math] and [math]\displaystyle{ X }[/math] не достижим от любого другого объекта [math]\displaystyle{ ) }[/math] [math]\displaystyle{ \{ }[/math] [math]\displaystyle{ X \in N }[/math] [math]\displaystyle{ \} }[/math] [math]\displaystyle{ \} }[/math]
параметры [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math] задаются пользователем.
Последовательная сложность алгоритма
Сложность алгоритма зависит от поиска всех точек в [math]\displaystyle{ \varepsilon }[/math]-окрестности конкретной точки [math]\displaystyle{ X }[/math] из выборки [math]\displaystyle{ D }[/math]. Из-за поиска "соседствующих" точек алгоритм имеет квадратичную вычислительную сложность [math]\displaystyle{ O(n^2) }[/math] (где n - количество точек). Но если использовать K-мерное дерево, то можно снизить сложность до [math]\displaystyle{ O(\text{n log n}) }[/math].
Информационный граф
Представление алгоритма DBSCAN в виде информационного графа показано на рисунке 4.
- Задаются параметры [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MCP }[/math].
- На входе алгоритма набор данных [math]\displaystyle{ D }[/math] разбивается на множество точек [math]\displaystyle{ X_n }[/math], где [math]\displaystyle{ n }[/math] - количество точек.
- Для каждой точки [math]\displaystyle{ X_n }[/math] из выборки [math]\displaystyle{ D }[/math] с помощью функции [math]\displaystyle{ dist(var1, var2) }[/math] определяется расстояние между остальными точками.
- Далее алгоритм объединяет точки [math]\displaystyle{ X_n }[/math], образуя подмножества [math]\displaystyle{ M_\varepsilon(X_n) }[/math], объекты которого удовлетворяют условию: [math]\displaystyle{ dist(X,f_i) \le \varepsilon }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math].
- Если подмножество [math]\displaystyle{ M_\varepsilon(X_n) }[/math] состоит из [math]\displaystyle{ MCP }[/math] и больше объектов (т. е. [math]\displaystyle{ M_\varepsilon(X_n) \ge MPC }[/math]), то подмножество [math]\displaystyle{ M_\varepsilon(X_n) }[/math] образует кластер [math]\displaystyle{ G_m }[/math].
- Подмножество [math]\displaystyle{ N }[/math] включает в себя все объекты, которые не принадлежат ни одному из подмножеств [math]\displaystyle{ G_1, G_2,..., G_m }[/math].
Ресурс параллелизма алгоритма
Ширина ярусно-параллельной формы алгоритма [math]\displaystyle{ O(m) }[/math][3], где m - количество частей, на которые разбиваются все объекты из набора данных [math]\displaystyle{ D }[/math]. Высотой ярусно-параллельной формы алгоритма является [math]\displaystyle{ O(|X| \log |X|) }[/math], где [math]\displaystyle{ \mid X \mid }[/math] - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм DBSCAN, применяемый к каждой отдельной части разбиения.
Входные и выходные данные алгоритма
Входные данные: множество объектов из набора данных [math]\displaystyle{ D }[/math], для которых задана метрическая функция расстояния [math]\displaystyle{ dist(var1, var2) }[/math]. Объём входных данных: [math]\displaystyle{ n }[/math].
Выходные данные: размеченное множество объектов, где каждому объекту сопоставлен порядковый номер кластера, в который попал данный объект, либо объект отмечается как выброс. Объём выходных данных: [math]\displaystyle{ n }[/math].
Количество кластеров и шума в выходных данных зависят от входных данных и параметров алгоритма. Более компактное расположение объектов, меньшие значения параметра [math]\displaystyle{ MCP }[/math], большие значения параметра [math]\displaystyle{ \varepsilon }[/math] ведут к образования меньшего числа кластеров, вплоть до одного единственного кластера. Если варьировать данные параметры в противоположную сторону, то количество кластеров и выбросов будет расти, вплоть до момента, когда все объекты будут являться выбросом.
Свойства алгоритма
- Число настраиваемых параметров равно двум: [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MPC }[/math].
- Вычислительная сложность алгоритма [math]\displaystyle{ O(\text{n log n}) }[/math].
- Возможность обрабатывать большой объем данных.
- Результат не зависит от порядка ввода данных.
- Не требуется указывать количество кластеров.
- Возможность выделять кластеры в присутствии выбросов.
- Число итераций определено заранее[4].
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Было проведено исследование масштабируемости параллельной реализации алгоритма DBSCAN. Исследование проводилось на суперкомпьютере "Ломоносов". Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI. Распараллеливание проводилось по числу входных объектов. Программа реализована на языке C++.
Набор и границы значений изменяемых параметров запуска реализации алгоритма:
- число процессоров [1 : 128] с шагом по степеням двойки;
- число входных объектов [1000 : 40000].
На рисунке 6 показан график масштабируемости DBSCAN, из которого можно сделать следующие выводы:
- При увеличении размерности системы при фиксированном количестве процессов на области изменений значений параметров наблюдается увеличение эффективности.
- При увеличении числа процессов наблюдается уменьшение эффективности на всей области рассматриваемых значений параметров. При этом с ростом числа процессов снижение эффективности замедляется.
- При одновременном увеличении количества процессов и размерности системы наблюдается уменьшение эффективности. При этом скорость убывания эффективности крайне низкая.
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Scikit-Learn включает в себя реализацию Python для DBSCAN для произвольной метрики Минковского, который может быть ускорен с помощью KD-деревьев и шаровых деревьев, но который использует в худшем случае квадратичную память.
SPMF предлагает GPL-V3 java-реализацию алгоритма DBSCAN с поддержкой KD-дерева (только для параметра расстояние Евклида).
Apache Commons Мath содержит java-реализацию алгоритма выполняющегося за квадратичное время.
ELKI предлагает реализацию DBSCAN, а также GDBSCAN и другие варианты. Эта реализация может использовать различные структуры индексов для поквадратного выполнения и поддерживает произвольное расстояние функции и произвольные типы данных, но это можно обогнать низкоуровневой оптимизацией реализации на небольших наборах данных.
Weka содержит (как дополнительный пакет в последних версиях) базовую реализацию DBSCAN, которая работает за квадратичное время и линейную память.
GNU R содержит DBSCAN в fpc пакете с поддержкой произвольных функций расстояния через матриц. Однако он не имеет поддержки индекса (и, соответственно, имеет квадратичное время выполнения и сложность по памяти) и довольно медленно из-за интерпретации R. Более быстрая версия реализована на языке C++ с использованием KD-деревьев (только когда расстояние Евклидово ) в пакете R dbscan.
Литература
- ↑ Haykin S. Neural Networks. A Comprehensive Foun-dation. – Upper Saddle River, N.1: Prentice Hall, Inc., 1999. – 1104 с.
- ↑ Jiawei Han, Micheline Kamber. Data Mining: Con-cepts and Techniques: – Academic Press, 2001. – Р. 363-370.
- ↑ https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)
- ↑ http://cyberleninka.ru/article/n/algoritmy-klasterizatsii-v-zadachah-segmentatsii-sputnikovyh-izobrazheniy