Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску



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


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

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

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

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

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

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

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

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

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

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

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

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

Определения

  • ядровой элемент: элемент [math]\displaystyle{ p }[/math] является ядровым, если количество элементов в [math]\displaystyle{ \varepsilon }[/math]-окрестности, включая сам элемент [math]\displaystyle{ p }[/math] больше или равно [math]\displaystyle{ MinPts }[/math];
  • достижимость напрямую элемента [math]\displaystyle{ p }[/math] из элемента q: элемент [math]\displaystyle{ p }[/math] считается достижимым напрямую из элемента [math]\displaystyle{ q }[/math], если элемент [math]\displaystyle{ q }[/math] является ядровым, а элемент [math]\displaystyle{ p }[/math] находится в [math]\displaystyle{ \varepsilon }[/math]-окрестности элемента q;
  • достижимость элемента [math]\displaystyle{ p }[/math] из элемента [math]\displaystyle{ q }[/math]: элемент [math]\displaystyle{ p }[/math] достижим из элемента [math]\displaystyle{ q }[/math], если существует путь [math]\displaystyle{ p_1, \dots, p_n }[/math], где [math]\displaystyle{ p_1 = p }[/math] и [math]\displaystyle{ p_n = q }[/math], где [math]\displaystyle{ p_{i + 1} }[/math] напрямую достижим из [math]\displaystyle{ p_{i} }[/math];
  • шум: все элементы, недостижимые из какого-либо другого считаются шумом.

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

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

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

  • Все элементы внутри кластера взаимно связанны;
  • Если элемент связан с каким-либо элементом кластера, то он тоже является частью кластера.
Файл:DBSCAN-Illustration.svg
Рис. 1[2]. Для MinPts = 4. Красные элементы соответствуют ядровым, желтые — достижимым, синяя — шуму.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

<references \> <references \> <references \>

  1. ↑ A density-based algorithm for discovering clusters in large spatial database / M. Ester, H.-P. Kriegel, J. Sander, X. Xu // Proc. 1996 Intern. Conf. on Knowledge Discovery and Data Mining. – 1996.
  2. ↑ https://en.wikipedia.org/wiki/DBSCAN Density-based spatial clustering of applications with noise (DBSCAN)
  3. ↑ A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-Set Data Structure \ Md. Mostofa Ali Patwary, Diana Palsetia, Ankit Agrawal, Wei-keng Liao, Fredrik Manne, Alok Choudhary
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Elmon/Плотностный_алгоритм_кластеризации_DBSCAN&oldid=14035