Участник:Dmarkin/Алгоритм кластеризации, основанный на минимальном покрывающем дереве

Автор описания: Маркин Дмитрий Валерьевич, группа 611

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

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

Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.

Алгоритм кластеризации на [math]\displaystyle{ k }[/math] кластеров, основанный на построении минимального остовного дерева (MST):

1. По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
2. Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
3. Удаляется k-1 ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

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

Имеем [math]\displaystyle{ N }[/math] объектов [math]\displaystyle{ x }[/math], которые представляют собой элемент метрического пространства с метрикой [math]\displaystyle{ d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}} }[/math].

На первом шаге строим граф [math]\displaystyle{ G=(V,E) }[/math] с множеством вершин [math]\displaystyle{ V }[/math] ([math]\displaystyle{ |V|=N }[/math]) и множеством ребер [math]\displaystyle{ E }[/math] ([math]\displaystyle{ |E|=\frac{N*(N-1)} {2} }[/math]).

На втором этапе строится минимальное покрывающее дерево [math]\displaystyle{ MST(G) }[/math].

На третьем этапе удаляется [math]\displaystyle{ K-1 }[/math] ребро, и дерево распадается на поддеревья [math]\displaystyle{ MST_i }[/math], вершины которых объявляются принадлежащими кластеру с номером [math]\displaystyle{ i }[/math].

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

Алгоритм состоит из трёх независимых шагов:

1. Построение графа и вычисление расстояний. Сложность [math]\displaystyle{ O(N^2) }[/math];
2. Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ( Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима). Сложность [math]\displaystyle{ O(N^2 log(N)) }[/math];
3. Разбиение на кластеры. Сложность в худшем случае [math]\displaystyle{ O(N) }[/math].

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

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

В состав алгоритма входят следующие макрооперации:

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

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

Обозначения

• [math]\displaystyle{ D(i) }[/math] — расстояние от [math]\displaystyle{ i }[/math]-й вершины до построенного дерева;
• [math]\displaystyle{ P(i) }[/math] — предок [math]\displaystyle{ i }[/math]-й вершины, то есть такая вершина [math]\displaystyle{ u }[/math], что [math]\displaystyle{ (u,i) }[/math] легчайшее из всех рёбер, соединяющее [math]\displaystyle{ i }[/math] с вершиной из построенного дерева;
• [math]\displaystyle{ W(i,j) }[/math] — вес ребра [math]\displaystyle{ (i,j) }[/math];
• [math]\displaystyle{ Q }[/math] — приоритетная очередь вершин графа, где ключ — [math]\displaystyle{ D(i) }[/math];
• [math]\displaystyle{ T }[/math] — множество ребер минимального остовного дерева.

Псевдокод

[math]\displaystyle{ T \gets   }[/math] {} 
Для каждой вершины  [math]\displaystyle{  i \in V  }[/math] 
 [math]\displaystyle{ D(i) \gets \infty  }[/math]
 [math]\displaystyle{ P(i) \gets nil }[/math]
 [math]\displaystyle{ D(1) \gets 0 }[/math]
 [math]\displaystyle{ Q \gets V }[/math] 
Пока [math]\displaystyle{ Q  }[/math] не пуста
 [math]\displaystyle{ v \gets\ Extract.min(Q)  }[/math] 
 Для каждой вершины [math]\displaystyle{ u }[/math] смежной с [math]\displaystyle{ v }[/math]
  Если [math]\displaystyle{ u \in Q }[/math] и [math]\displaystyle{ W(v,u) \lt  D(u) }[/math]  
   [math]\displaystyle{ D(u) \gets W(v,u) }[/math]
   [math]\displaystyle{ P(u) \gets v }[/math]
 [math]\displaystyle{ v \gets Extract.Min(Q) }[/math]
 [math]\displaystyle{ T \gets T+(P(v),v) }[/math]

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

Последовательная сложность определяется суммой сложностей трёх основных этапов:

[math]\displaystyle{ T(N) = O(N^2) + O(N^2 log(N)) + O(N) = O(N^2 log(N)) }[/math]

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

Информационный граф параллельного алгоритма построения минимального покрывающего дерева