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

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

Основной автор описания: Гилевич В.В.

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

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

Кластеризация — это процедура, упорядочивающая элементы из некоторого множества в сравнительно однородные группы (кластеры). Элементы могут содержать числовые, категориальные или смешанные данные. Плотностные методы выделяют кластеры на основе следующей идеи: кластером считается регион с высокой плотностью объектов, которые разделены разреженными регионами (с низкой плотностью объектов)

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

Алгоритм имеет ряд отличительных свойств:

• Не требуется заранее определять число кластеров
• Может отличать кластеры, которые нельзя разделить прямой линией (плоскостью, для N-мерного пространства), в том числе кластера, частично или полностью окруженные другим кластером.
• Хорошо работает в условиях зашумленных входных данных

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

1.2.1 Исходные данные

Множество [math]X[/math], на котором определена функция расстояния [math]D[/math].

1.2.2 Вычисляемые данные

Множество пар из элемента множества [math]X[/math], и соответствующий ему номер кластера.

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

• [math]\varepsilon[/math] — максимальное расстояние между соседями;
• [math]MinPts[/math] — минимальное количество элементов находящихся [math]\varepsilon[/math]-окрестности данного элемента для создания кластера.

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

• ядровой элемент: элемент [math]p[/math] является ядровым, если количество элементов в [math]\varepsilon[/math]-окрестности, включая сам элемент [math]p[/math] больше или равно [math]MinPts[/math];

• достижимость напрямую элемента [math]p[/math] из элемента q: элемент [math]p[/math] считается достижимым напрямую из элемента [math]q[/math], если элемент [math]q[/math] является ядровым, а элемент [math]p[/math] находится в [math]\varepsilon[/math]-окрестности элемента q;

• достижимость элемента [math]p[/math] из элемента [math]q[/math]: элемент [math]p[/math] достижим из элемента [math]q[/math], если существует путь [math]p_1, \dots, p_n[/math], где [math]p_1 = p[/math] и [math]p_n = q[/math], где [math]p_{i + 1}[/math] напрямую достижим из [math]p_{i}[/math];

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

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

• связанность элемента p и элемента q: элемент [math]p[/math] считается связанным с [math]q[/math], если существует такой элемент [math]o[/math], что [math]p[/math] и [math]q[/math] достижимы из него.

Таким образом кластер должен удовлетворять двум условиям:

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

Рис. 1. Для MinPts = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.

1.2.5 Пошаговое описание алгоритма

1. Выбирается произвольная непосещенный элемент [math]p[/math].
2. Элемент [math]p[/math] помечается как посещенный.
3. Проверяется, является ли элемент [math]p[/math] ядровым.
   • Если элемент [math]p[/math] является ядровым, то:
     • Он становится началом нового кластера или сохраняет номер кластера, который был присвоен элементу ранее;
     • Все элементы из [math]\varepsilon[/math]-окрестности элемента [math]p[/math] добавляются в его кластер (им присваевается номер кластера элемента [math]p[/math]);
     • Процесс продолжается рекурсивно для каждого непосещенного элемента текущего кластера c шага 2.
   • Если элемент [math]p[/math] не является ядровым, то [math]p[/math] объявляется шумом. Алгоритм продолжается с шага 4.
4. Если остались непосещенные точки, то алгоритм продолжается с шага 1.

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

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

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

Алгоритм DBSCAN предполагает использование пространственной структуры данных: такие структуры позволяют найти все элементы в пределах определенного расстояния от текущего за [math]O(\log n)[/math]. Сложность построения таких структур [math]O(n \log n)[/math], таким образом, использование такой структуры не увеличивает сложность всего алгоритма.

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

[math]DBSCAN(X, \varepsilon, MinPts)[/math]
  [math]C = 0[/math]
  for [math]p[/math] in [math]X[/math]:
    if [math]p[/math] is [math]visited[/math]:
      continue
    mark [math]p[/math] as [math]visited[/math]
    [math]neighbours[/math] = [math]\{ o \ | \ \forall o \in X: D(p, o) \le \varepsilon \}[/math]
    if [math]| neighbours | \ge MinPts[/math]:
      [math]C = C + 1[/math]
      add [math]p[/math] to cluster [math]C[/math]
      for [math]q \in neighbours[/math]:
        if [math]q[/math] is not [math]visited[/math]:
          mark [math]q[/math] as [math]visited[/math]
          [math]q\_neighbours[/math] = [math]\{ o \ | \ \forall o \in X: D(q, o) \le \varepsilon \}[/math]
          if [math]| q\_neighbours | \ge MinPts[/math]:
            [math]neighbours[/math] = [math]neighbours \cup q\_neighbours[/math]  
        if [math]q[/math] has no cluster mark:
          mark [math]q[/math] as part of cluster [math]C[/math]
    else:
      mark [math]p[/math] as [math]noise[/math]

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

Для того, чтобы проверить принадлежность элемента множества к кластеру необходимо получить список соседей в его [math]\varepsilon[/math]-окрестности. При использовании пространственной структуры данных данная операция может быть выполнена со сложностью [math]O(\log n)[/math]. Так как для необходимо определить принадлежность к кластеру всех элементов множества, то сложность самого алгоритма [math]O(n \log n)[/math]. При отказе от использования таких сткрутр сложность возрастает до [math]O(n^2)[/math], так как для каждого элемента требуется проверить на нахождение в [math]\varepsilon[/math]-окрестности все остальные элементы множества.

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

Опишем граф алгоритма как аналитически, так и в виде рисунка:

Граф алгоритма состоит из двух групп вершин, расположенных узлах двух областей двумерной размерности.

Первой группе вершин соответствует операция Neighbours. Естественно введённые координаты области таковы:

• [math]i[/math] — меняется от [math]1[/math] до [math]k + f[/math], принимая все целочисленные значения, где [math]k[/math] — число результирующих кластеров, [math]f[/math] — число элементов помеченных, как шум
• [math]j[/math] — меняется от [math]1[/math] до [math]t[/math], принимая все целочисленные значения, где [math]t[/math] — число вершин в кластере [math]i[/math]

Второй группе вершин соответствует операция Check. Естественно введённые координаты области аналогичны предыдущей.

Граф алгоритма DBSCAN

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

Так как в данном алгоритме присутствует параллелизм по данным, ширина ярусно-параллельной формы алгоритма [math]O(w)[/math], где [math]w[/math] — количество частей, на которые разбиваются все входное множество объектов [math]X[/math]. Высотой ярусно-параллельной формы алгоритма является [math]O(|H| \log |H|)[/math], где [math]|H|[/math] — максимальное количество элементов в области среди всех частей разбиения. Именно такую сложность имеет алгоритм PDBSCAN, применяемый к каждой отдельной части разбиения.

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

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

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

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

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

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

• Алгоритм может определять кластера произвольной формы;
• Параллельная реализация при равномерном разбиении сбалансирована по количеству и виду производимых операций;
• Не требуется задание числа кластеров;
• Может выделять кластеры в присутствии шума;
• Не детерминирован относительно граничных точек кластеров.

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

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

• [1]
• [2]
• [3]
• [4]
• [5]

3 Литература

<references \> <references \>

<references \>