Эта работа ждет рассмотрения преподавателем
Дата последней правки страницы: 26.10.2016
Авторы этой статьи считают, что задание выполнено.

Плотностный алгоритм кластеризации DBSCAN
Последовательный алгоритм
Последовательная сложность	[math]O(n^2)[/math]
Объём входных данных	[math]n[/math]
Объём выходных данных	[math]n[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]-[/math]
Ширина ярусно-параллельной формы	[math]-[/math]

Авторы описания: Вашуров И.М., Шемякин Р.О.

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

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

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

Алгоритм DBSCAN (Density-based spatial clustering of applications with noise)^[1] был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение задачи кластеризации с кластерами произвольной формы. DBSCAN является непараметрическим плотностным алгоритмом кластеризации: для заданного набора точек в некотором пространстве, алгоритм группирует те точки, которые расположены достаточно близко друг к другу (точки с большим количеством соседей), и помечает как выбросы те, что располагаются далеко от ближайших соседей.

Близость в алгоритме определяется заданной в пространстве метрикой. Наиболее часто в качестве метрики используются Евклидово расстояние, квадрат Евклидова расстояния, манхэттенская метрика, расстояние Чебышева или степенное расстояние.

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

Вход алгоритма: множество точек [math]X[/math] из [math]n[/math]-мерного пространства, на котором определена функция расстояния [math]D[/math].

Выход алгоритма: размеченное множество точек [math]X[/math], в котором каждой точке соответствует номер ее кластера.

Параметры алгоритма:

[math]\varepsilon[/math] - максимальное расстояние между соседями;
[math]MinPts[/math] - минимальное количество соседей для создания области связности.

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

Рис. 1. Здесь MinPts = 4. Точка A и другие красные точки - ядровые и образуют единый кластер, так как достижимы друг из друга. Точки B и C не являются ядровыми, но достижимы из A, а значит также принадлежат кластеру. Точка N - не достижима из других точек и является шумом.

Все заданные точки классифицируются на три группы:

ядровые точки: точка [math]p[/math] является ядровой, если количество [math]\varepsilon[/math]-соседей, включая саму точку [math]p[/math], не меньше [math]MinPts[/math]. Под [math]\varepsilon[/math]-соседями точки [math]p \in X[/math] понимается множество точек, расстояние до которых не превышает [math]\varepsilon[/math], т.е. [math]N_\varepsilon(p) = \{ x \in X | D(p, x) \le \varepsilon \}[/math]. Эти точки являются напрямую достижимыми из [math]p[/math];

достижимые точки: точка [math]q[/math] достижима из [math]p[/math], если существует путь [math]p_1, \dots, p_n[/math], где [math]p_1 = p[/math] и [math]p_n = q[/math], для которого выполнено:

[math]\begin{align} p_{i + 1} \in N_\varepsilon(p_i), i = 1, \dots, n-1 \\ | N_\varepsilon(p_{i}) | \ge MinPts, i = 1, \dots, n-1 \\ \end{align}[/math]

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

Так, если [math]p[/math] - ядровая точка, то она образует кластер вместе со всеми точками, достижимыми из неё. Каждый кластер содержит по крайней мере одну ядровую точку; неядровые точки могут быть частью кластера, образуя при этом его "границу", так как они не могут быть использованы для достижения других точек.

Достижимость не является симметричным отношением, так как по определению никакая точка не может быть достижима из неядровой точки, независимо от расстояния. Поэтому в DBSCAN применяется следующий термин связности: две точки [math]p[/math] и [math]q[/math] связанны, если существует такая точка [math]o[/math], что [math]p[/math] и [math]q[/math] достижимы из [math]o[/math]. Такое отношение связности симметрично.

Кластер в таком случае определяется двумя свойствами:

Все точки внутри кластера взаимно связанны;
Если точка достижима из любой точки кластера, она также является частью кластера.

1.2.2 Шаги алгоритма

Выбирается произвольная непосещенная точка [math]p[/math].
Точка [math]p[/math] помечается как посещенная.
У точки [math]p[/math] определяется множество её [math]\varepsilon[/math]-соседей - [math]N_\varepsilon(p)[/math].
- Если точка [math]p[/math] оказалась ядровой - [math]| N_\varepsilon(p) | \ \ge MinPts[/math], то:
  - она становится началом нового кластера или сохраняет номер кластера, который был ей присвоен ранее;
  - все точки из [math]N_\varepsilon(p)[/math] добавляются в её кластер;
  - процесс продолжается рекурсивно для каждой новой добавленной непосещенной точки [math]p' \in N_\varepsilon(p)[/math] c шага 2 (в качестве новой [math]p[/math]).
- Если точка [math]p[/math] оказалась не ядровой, то [math]p[/math] объявляется шумом. Алгоритм продолжается с шага 4.
Если остались непосещенные точки, то алгоритм продолжается с шага 1.

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

Вычислительным ядром алгоритма является нахождение [math]\varepsilon[/math]-соседей каждой точки входного множества [math]X[/math].

Для решения этой задачи требуется найти расстояния между любыми двумя точками множества [math]X[/math] по заданной метрике.

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

Как записано и в описании ядра алгоритма, основную часть метода составляют вызовы функции [math]request\_neighbours[/math] получения [math]\varepsilon[/math]-соседей и нахождение расстояний между точками множества [math]X[/math].

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

[math]DBSCAN(X, \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 | \lt  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(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(p, \varepsilon)[/math]
  return [math]\{ p' \ | \ \forall p' \in X: D(p, p') \lt  \varepsilon \}[/math]

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

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], но оценка может быть улучшена при использовании векторных операций.

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

Опишем граф алгоритма^[2]^[3]^[4].

Рис. 2. Внешний цикл алгоритма.

На рис. 2 изображен информационный граф внешнего цикла алгоритма, который соответствует коду основной функции [math]DBSCAN[/math]:

Макрооперация Init заключается в получении множества [math]X[/math] и инициирования вспомогательных структур.
Макрооперация Choose производит выбор непосещенной точки из [math]X[/math].
Макрооперация Build cluster строит кластер, если точка ядровая, или объявляет ее шумом.

Переход от Build cluster к Choose заключает в себе зависимость данных о принадлежности некоторых точек к текущему кластеру или шуму и об их посещенности.

Рис. 3. Расширение кластера.

На рис. 3 изображен информационный граф алгоритма расширения кластера из начальной точки кластера:

Макрооперация Init заключается в создании кластера из его начальной вершины.
Макрооперация Nε вычисляет множество [math]\varepsilon[/math]-соседей.
Желтым цветом обозначены узлы, в которых точки из [math]\varepsilon[/math]-соседей классифицируются на ядровые, граничные точки и шум. В рамках операции для конкретного соседа вычисляется множество его [math]\varepsilon[/math]-соседей.
Макрооперации Ñε, Ňε, ... производят объединение входных множеств.
Макрооперация Ø выполняется тогда, когда объединение входных множеств является пустым.

Рис. 4. Подсчет [math]\varepsilon[/math]-соседей.

На рис. 4 изображен информационный граф алгоритма вычисления множества [math]\varepsilon[/math]-соседей:

Операция D - вычисление расстояния между точками.
Операция ε - сравнение расстояния с ε.
Операция U - объединение результатов.

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

Поиск [math]\varepsilon[/math]-соседей требует вычисления [math]n[/math] расстояний (функция [math]D[/math]) и выполнения [math]n[/math] сравнений с [math]\varepsilon[/math]. Эти операции для каждой пары точек независимы и могут быть выполнены параллельно. Таким образом, при наличии неограниченного числа процессоров сложность поиска составит [math]O(1)[/math]. Т.к. поиск выполняется для каждой точки ровно один раз, параллельная сложность всего алгоритма составит [math]O(n)[/math].

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

Вход алгоритма: множество точек X из n-мерного пространства, на котором определена функция расстояния D. В наиболее распространенном случае пространственной кластеризации используется Евлидово расстояние между векторами из [math]\mathbb{R}^n[/math].

Выход алгоритма: размеченное множество точек [math]X[/math], в котором каждой точке соответствует номер ее кластера. Обычно каждой точке из [math]X[/math] сопоставляется ее номер, а на выходе алгоритм дает отображение номеров точек в номера соответствующих им кластеров, например в виде вектора размера [math]|X|[/math].

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

Соотношение последовательной и параллельной сложностей алгоритма является линейным (отношение квадратичной к линейной).

При этом вычислительная мощность, как отношение числа операций к суммарному объему входных и выходных данных линейна.

1.10.1 Преимущества алгоритма

не требует указывать число кластеров;
может определять кластера произвольной формы;
может определять шум и устойчив к выбросам;
требует всего два параметра и по в большинстве случаев не чувствителен к порядку заданных точек;
параллельная реализация сбалансирована по количеству и виду производимых операций (вычисление расстояния, сравнение с [math]\varepsilon[/math]).

1.10.2 Недостатки алгоритма

не детерминирован: граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован. Впрочем, от недетерминизма можно избавиться, если считать все граничные точки шумом (алгоритм DBSCAN*);
качество алгоритма зависит от используемой функции расстояния [math]D[/math]. Наиболее часто используемое Евклидово расстояние в многомерных множествах может оказаться практически бесполезным из-за так называемого "проклятия размерности", значительно затрудняя нахождение подходящего значения [math]\varepsilon[/math];
не может выделять кластеры, имеющие разную плотность, так как параметры алгоритма не могут быть выбранны отдельно для каждого кластера.

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

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

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

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

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

!!! ЭКСПЕРИМЕНТЫ ДО 15 НОЯБРЯ !!!

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

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

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

Scikit learn (Python)
R-project (github)
Matlab
P-DBSCAN (Parallel DBSCAN)^[5]
Parallel DBSCAN with MPI^[6]
PDSDBSCAN (Parallel Disjoint-Set DBSCAN)^[7]

3 Литература

↑ Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.
↑ Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.
↑ Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.
↑ Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.
↑ 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.
↑ 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.
↑ 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.

[1] Ester, Martin, et al. "A density-based algorithm for discovering clusters in large spatial databases with noise." Kdd. Vol. 96. No. 34. 1996.

[2] Воеводин В.В. Математические основы параллельных вычислений// М.: Изд. Моск. ун-та, 1991. 345 с.

[3] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ - Петербург, 2002. – 608 с.

[4] Фролов А.В.. Принципы построения и описание языка Сигма. Препринт ОВМ АН N 236. М.: ОВМ АН СССР, 1989.

[5] 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.

[6] 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.

[7] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

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