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

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

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

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

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

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

1. По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
2. Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
3. Удаляется [math]\displaystyle{ K-1 }[/math] ребро минимального остовного дерева с максимальным весом и получаются 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]

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

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

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

Рассмотрим основные свойства задачи:

• Схлопывание фрагментов. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева графа [math]\displaystyle{ G }[/math], а граф [math]\displaystyle{ G' }[/math] получен из [math]\displaystyle{ G }[/math] склеиванием вершин, принадлежащих [math]\displaystyle{ F }[/math]. Тогда объединение [math]\displaystyle{ F }[/math] и минимального остовного дерева графа [math]\displaystyle{ G' }[/math] даёт минимальное остовное дерево исходного графа [math]\displaystyle{ G }[/math].
• Ассоциативность по рёбрам. Пусть [math]\displaystyle{ MSF(E) }[/math] – минимальный остовный лес графа с рёбрами [math]\displaystyle{ E }[/math]. Тогда:[math]\displaystyle{ MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). }[/math]
• Минимальное ребро фрагмента. Пусть [math]\displaystyle{ F }[/math] – фрагмент минимального остовного дерева и [math]\displaystyle{ e_F }[/math] – ребро наименьшего веса, исходящее из [math]\displaystyle{ F }[/math] (т.е. ровно один его конец является вершиной из [math]\displaystyle{ F }[/math]). Если ребро [math]\displaystyle{ e_F }[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.

Ресурс параллелизма основан на следующих возможностях:

1. Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
2. Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
3. Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность [math]\displaystyle{ O(N \log N) }[/math]. Например, Алгоритм GHS (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

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

Входные данные: множество объектов [math]\displaystyle{ x = (x_1,...,x_N) }[/math].

Выходные данные: множество кластеров [math]\displaystyle{ Clust = (Clust_1,...,Clust_K) }[/math], где [math]\displaystyle{ Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l }[/math] и [math]\displaystyle{ m, \sum_{i=1}^K {N_i} = N }[/math].