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

Файл:Symbol wait.svg

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

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

Основные авторы описания: Малахова Е.С. (1.2,1.4-1.8,2.7), Сагиолданова Ж. (1.1-1.3,1.9-1.10,3)

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

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

Кластеризация – это процесс разбиения множества с [math]\displaystyle{ N }[/math] элементами [math]\displaystyle{ x_1, x_2, ... , x_n (x_n }[/math] имеет размерность [math]\displaystyle{ m }[/math]) на [math]\displaystyle{ K }[/math] кластеров, так, чтобы в каждом кластере все элементы были схожи в каком-то смысле. [math]\displaystyle{ x_i }[/math] могут быть числовыми, категориальными или смешанными данными. В плотностных методах кластеры рассматриваются как регионы пространства данных с высокой плотностью объектов, которые разделены регионами с низкой плотностью объектов.

Алгоритм DBSCAN (Density Based Spatial Clustering of Applications with Noise) –плотностной алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и их коллегами в 1996 году как решение проблемы разбиения (изначально пространственных) данных на кластеры произвольной формы.

Большинство алгоритмов, производящих плоское разбиение, создают кластеры по форме близкие к сферическим, так как минимизируют расстояние точки до центра кластера.

Авторы DBSCAN экспериментально показали, что их алгоритм способен распознать кластеры различной формы. Идея, положенная в основу алгоритма, заключается в том, что внутри каждого кластера плотность точек (объектов) заметно выше, чем плотность снаружи кластера, а также плотность в областях с шумом ниже плотности любого из кластеров. Еще точнее, для каждой точки кластера ее окрестность в диапазоне заданного радиуса должна содержать не менее некоторого числа точек, которое задается пороговым значением.

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

Рис. 1. Пример ядровых, граничных и шумовых точек алгоритма

Исходные данные: объекты, которые нужно кластеризовать, параметры [math]\displaystyle{ MinPts, \ \varepsilon }[/math] . Между объектами можно считать расстояния.

Вычисляемые данные: разбиение объектов по кластерам. Количество кластеров зависит от исходных данных.

Для построения оценки плотности, на основе соседства точек вводятся понятия достижимости и связности. Под [math]\displaystyle{ \varepsilon }[/math] -соседями точки [math]\displaystyle{ x \in X }[/math] понимается множество точек, расстояние до которых не превышает [math]\displaystyle{ \varepsilon }[/math], т. е.

[math]\displaystyle{ N_\varepsilon (x) = \{y \in X | D(x, y) \le \varepsilon\} }[/math].

Тогда точка [math]\displaystyle{ y }[/math] достижима из точки [math]\displaystyle{ x }[/math], если существует последовательность точек [math]\displaystyle{ x^{(1)}=x, x^{(2)},... , x^{(p-1)}, x^{(p)}=y }[/math], для которой выполнено:

[math]\displaystyle{ \begin{align} x^{(i+1)} \in N_\varepsilon (x^{(i)}), i=1,... ,p-1 \\ \mid N_\varepsilon (x^{(i)}) \mid \ge MinPts, i=1,... ,p-1 \end{align} }[/math]

Здесь значение [math]\displaystyle{ MinPts }[/math] задаётся пользователем и регулирует порог «шума». Согласно второму условию, у точек, находящихся внутри кластера, должно быть не менее [math]\displaystyle{ MinPts \ \varepsilon }[/math] -соседей. Такие точки называются «ядрами». Остальные точки разделяются на граничные (имеющие менее [math]\displaystyle{ MinPts \ \varepsilon }[/math] -cоседей, но достижимые из какого-либо «ядра») и шумовые. Две точки связны, если существует «ядро», из которого они обе достижимы. При такой постановке задачи, под кластером понимается максимальное связное подмножество множества [math]\displaystyle{ X }[/math] . Точки, не попавшие в какой-либо кластер (не принадлежащие [math]\displaystyle{ \varepsilon }[/math] -окрестности какого-либо «ядра»), относятся к классу «шум».

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

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

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

Алгоритм DBSCAN использует пространственную структуру данных для определения соседних объектов. Это может быть R*-дерево или kd-дерево. Такие структуры данных позволяют найти все объекты в пределах определенного расстояния от текущего объекта. Сложность построения таких структур [math]\displaystyle{ O(n \log n) }[/math], и использование такой структуры не увеличит сложность всего алгоритма (если сложность самого алгоритма [math]\displaystyle{ O(n \log n) }[/math]). Также для построения таких деревьев нужно уметь находить расстояния между объектами [math]\displaystyle{ \rho(u,v) }[/math], это расстояние можно вводить разными способами. Например, если [math]\displaystyle{ \rho(u,v) }[/math] - метрика в евклидовом пространстве, [math]\displaystyle{ u=(u_1,...,u_n) }[/math] и [math]\displaystyle{ (v_1,...,v_n) }[/math], то расстояние вычисляется следующим образом: [math]\displaystyle{ \rho(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{ DBSCAN(X, \varepsilon, MinPts) }[/math]
//Изначально все объекты в [math]\displaystyle{ X }[/math]не кластеризованы
   [math]\displaystyle{ FORALL }[/math]  objects  [math]\displaystyle{ x }[/math] in [math]\displaystyle{ X\  DO }[/math]
      [math]\displaystyle{ IF\  x }[/math] is unclassified
        call function [math]\displaystyle{ expand\_cluster }[/math] to construct a cluster wrt. [math]\displaystyle{ \varepsilon }[/math] and [math]\displaystyle{ MinPts }[/math] containing [math]\displaystyle{ x }[/math]

// Вспомогательная функция, которая строит кластер на основе одной точки
[math]\displaystyle{ FUNCTION\ expand\_cluster(x,X,\varepsilon, MinPts): }[/math]
   [math]\displaystyle{ retrive\_\varepsilon neighborhood(x, \varepsilon) }[/math];
   [math]\displaystyle{ IF \mid N_{\varepsilon}(x) \mid \lt  MinPts }[/math] //т.е. [math]\displaystyle{ x }[/math] - не ядровой объект
      mark [math]\displaystyle{ x }[/math] as [math]\displaystyle{ noise }[/math]  and [math]\displaystyle{ RETURN }[/math];
   [math]\displaystyle{ ELSE }[/math]//т.е. [math]\displaystyle{ x }[/math] - ядровой объект
      select a new cluster-id and mark all objects in [math]\displaystyle{ N_{\varepsilon}(x) }[/math] with this current [math]\displaystyle{ cluster-id }[/math]; 
      push all objects from [math]\displaystyle{ N_{\varepsilon}(x) }[/math]\[math]\displaystyle{ (x) }[/math] onto the stack seeds;
      [math]\displaystyle{ WHILE\ NOT }[/math] seeds.empty() [math]\displaystyle{ DO }[/math] 
        [math]\displaystyle{ currentObject }[/math] := seeds.top();
        seeds.pop();
        [math]\displaystyle{ retrive\_\varepsilon neighborhood(currentObject, \varepsilon) }[/math];
        [math]\displaystyle{ IF \mid N_{\varepsilon}(currentObjects) \mid \ge MinPts }[/math]
          select all objects in [math]\displaystyle{ N_{\varepsilon}(currentObject) }[/math] not yet classified or marked as [math]\displaystyle{ noise }[/math],
          push the unclassified objects onto seeds and mark all of these objects with current [math]\displaystyle{ cluster-id }[/math];
    [math]\displaystyle{ RETURN }[/math]

// Вспомогательная функция, для определения [math]\displaystyle{ \varepsilon }[/math]-соседей для объекта
[math]\displaystyle{ FUNCTION\ retrive\_\varepsilon neighborhood(x, \varepsilon) }[/math] //функция возвращает соседей на основе пространственной структуры данных
  return [math]\displaystyle{ \{ x' \ | \ \forall x' \in X: \rho(x, x') \lt  \varepsilon \} }[/math]

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

Для того, чтобы алгоритм мог кластеризовать все объекты, необходимо пройти по каждому из них хотя бы один раз. Если использовать R*-дерево или kd-дерево для определения соседних объектов со сложностью [math]\displaystyle{ O(\log n) }[/math], то сложность алгоритма [math]\displaystyle{ O(n \log n) }[/math]. Если не использовать эти структуры, то в худшем случае алгоритм будет иметь сложность [math]\displaystyle{ O(n^2) }[/math], так как придется считать полную матрицу расстояний между объектами.

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

В настоящем алгоритме осуществляется параллелизм по данным. Ниже представлена общая структура данного алгоритма.

Рис.1. Общая информационная структура алгоритма

Разбиение данных происходит с помощью пространственной структуры данных (R*-дерево, kd-дерево), которая разбивает все множество объектов [math]\displaystyle{ X }[/math] на [math]\displaystyle{ m }[/math] частей: [math]\displaystyle{ X_1,X_2,...,X_m }[/math].

Рис.2. Пример разбиения объектов на части на основе пространственной структуры

На каждой части объектов применяется алгоритм PDBSCAN (каждая часть использует пространственную структуру данных, которая распределяется вместе с каждой частью данных). Данный алгоритм отличается от общего алгоритма DBSCAN тем, что применяется к части объектов и для каждой из этих частей определяет кандидатов на слияние. Если для ядрового объекта части [math]\displaystyle{ X_i }[/math] в [math]\displaystyle{ \varepsilon }[/math]-окрестности находится объект из другой части [math]\displaystyle{ X_j }[/math], то такие объекты становятся кандидатами на слияние.

Само слияние осуществляется следующим образом: для каждой пары кандидатов на слияние, объединяем кластеры, соответствующие этим кандидатам в один общий кластер.

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

Как видно из общей структуры графа алгоритма, ширина ярусно-параллельной формы алгоритма [math]\displaystyle{ O(m) }[/math], где m - количество частей, на которые разбиваются все входное множество объектов [math]\displaystyle{ X }[/math]. Высотой ярусно-параллельной формы алгоритма является [math]\displaystyle{ O(|X| \log |X|) }[/math], где [math]\displaystyle{ \mid X \mid }[/math] - максимальное количество среди числа объектов в каждой части разбиения. Именно такую сложность имеет алгоритм PDBSCAN, применяемый к каждой отдельной части разбиения.

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

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

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

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

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

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

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

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

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

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

• не может выделять кластеры сложной структуры, например, имеющие разную плотность, так как параметры алгоритма не могут быть выбраны отдельно для каждого кластера;
• не может построить иерархическую структуру кластеров;
• не детерминирован, так как граничные точки, достижимые из более, чем одного кластера, могут быть частью любого из них в зависимости от порядка обрабатываемых данных. Однако такая ситуация возникает редко, а относительно ядровых точек и шума DBSCAN детерминирован.
• плохо работает на кластерах, которые имеют небольшое пересечение между собой.

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

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

• Scikit learn (Python, последовательная реализация)
• Northwestern University (C++, параллельная реализация kd-tree)
• github/ContinuumIO (Python, параллельная реализация)
• github/propanoid (C++, последовательная реализация VP tree)
• github/dparks1134 (С++, последовательная реализация)
• Disjoint-Set Data Structure based Parallel DBSCAN (C++ параллельная реализация kd-tree)
• github/bwoneill (Spark/Python параллельная реализация kd-tree)
• github/alitouka (Spark/Scala параллельная реализация)
• CRAN (R, последовательная реализация)

Литература

<references \> <references \>(A Fast Parallel Clustering Algorithm for Large Spatial Databases, JOCHEN JAGER, HANS-PETER KRIEGEL) <references \>(АЛГОРИТМЫ КЛАСТЕРИЗАЦИИ В ЗАДАЧАХ СЕГМЕНТАЦИИ СПУТНИКОВЫХ ИЗОБРАЖЕНИЙ, Пестунов Игорь Алексеевич, Синявский Юрий Николаевич)