Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
Плотность точек для данной точки <math>X</math> определяется двумя параметрами. Первым из них является
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M(X)</math> будет включать в себя такие точки
<math>\varepsilon</math> – радиус «соседства» (приближенности) точки <math>X</math>. Тогда множество <math>M_\varepsilon(X)</math> будет включать в себя такие точки <math>f_i</math>, <math>(i=\overline{1,n})</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 для другого окружения (соседства),
Функция <math>dist(var1, var2)</math> определяет расстояние между объектами выборки <math>D</math>. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью <span class="plainlinks">[//en.wikipedia.org/wiki/Minkowski_distance метрики Минковского]</span>.
Вычислительным ядром алгоритма является нахождение <math>\varepsilon</math>-соседей каждой точки входного множества <math>X</math>.
Вторым параметром определения плотности точек является <math>MCP</math> – это минимальное количество точек, которые расположены ближе всего к данной точке согласно определенному радиусу <math>\varepsilon</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>f_i</math>, <math>(i=\overline{1,n})</math> будет являться окруженной точкой (согласно <math>\varepsilon</math> и <math>MCP</math>) если:
== Макроструктура алгоритма ==
<math>M_\varepsilon(X) \le MPC</math>
Как записано и в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть метода составляют вызовы функции <math>request\_neighbours</math> получения <math>\varepsilon</math>-соседей и нахождение расстояний между точками множества <math>X</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).
<math>DBSCAN</math> проходит через все точки множества <math>X</math> и определяет, являются ли они шумом или началом нового кластера.
[[Файл:Точка_X_прямо_достижима_по_плотности_от_точки_f.png|thumb|center|300px|Рис. 2. Точка X прямо достижима по плотности от точки f]]
В последнем случае новому кластеру присваивается уникальный номер и вызывается функция расширения кластера.
<math>DBSCAN(\varepsilon, MinPts)</math>
Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка <math>f</math> достижима по плотности из точки <math>X</math>, но точка <math>X</math> не достижима по плотности из точки <math>f</math> (рис. 3).
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>-соседей.
*Макрооперации ''Ñε'', ''Ňε'', ... производят объединение входных множеств.
*Макрооперация ''Ø'' выполняется тогда, когда объединение входных множеств является пустым.
На рис. 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>;
# не может выделять кластеры, имеющие разную плотность, так как параметры алгоритма не могут быть выбранны отдельно для каждого кластера.
= Программная реализация алгоритма =
= Программная реализация алгоритма =
Строка 210:
Строка 60:
== Масштабируемость алгоритма и его реализации ==
== Масштабируемость алгоритма и его реализации ==
!!! ЭКСПЕРИМЕНТЫ ДО 15 НОЯБРЯ !!!
== Динамические характеристики и эффективность реализации алгоритма ==
== Динамические характеристики и эффективность реализации алгоритма ==
* 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>
Под кластеризацией понимается деление заданного множества точек данных (объектов) на подгруппы, каждая из которых, насколько это возможно, однородна. В основе метода кластеризации 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(var1, var2) }[/math] определяет расстояние между объектами выборки [math]\displaystyle{ D }[/math]. Это расстояние может вычисляться различными способами, например, как евклидово расстояние или с помощью метрики Минковского.
Вторым параметром определения плотности точек является [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{ f_i }[/math], [math]\displaystyle{ (i=\overline{1,n}) }[/math] окруженная, если количество «соседствующих» точек выборки [math]\displaystyle{ D }[/math] окажется большим, либо равным значению параметра [math]\displaystyle{ MCP }[/math] (рис. 1).
Рис. 1. Окруженная точка при MPC = 5
Точка [math]\displaystyle{ X }[/math] является прямо достижимой по плотности от точки [math]\displaystyle{ f }[/math] (при соответствующих [math]\displaystyle{ \varepsilon }[/math] и [math]\displaystyle{ MPC }[/math]), если точка [math]\displaystyle{ X \in M(X) }[/math], т.е. точка [math]\displaystyle{ X }[/math] – это одна из точек [math]\displaystyle{ f }[/math] для другого окружения (соседства), где [math]\displaystyle{ f }[/math] – окруженная точка (рис. 2).
Рис. 2. Точка X прямо достижима по плотности от точки f
Достижимость по плотности – это транзитивное замыкание прямо достижимой по плотности точки. Точка [math]\displaystyle{ f }[/math] достижима по плотности из точки [math]\displaystyle{ X }[/math], но точка [math]\displaystyle{ X }[/math] не достижима по плотности из точки [math]\displaystyle{ f }[/math] (рис. 3).
Рис. 3. Достижимость по плотности
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
