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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5.1 Обозначения

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

1.5.2 Псевдокод

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

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

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

[math]T(N) = O(N^2) + O(N^2 log(N)) + O(N) = O(N^2 log(N))[/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература