Участник:Dmarkin/Алгоритм кластеризации, основанный на минимальном покрывающем дереве
Эта работа прошла предварительную проверку Дата последней правки страницы: 08.02.2017 Данная работа соответствует формальным критериям. Проверено ASA. |
Автор описания: Маркин Дмитрий Валерьевич, группа 611
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
Алгоритм кластеризации на [math]K[/math] кластеров, основанный на построении минимального остовного дерева ([math]MST[/math]):
- По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
- Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
- Удаляется [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 Вычислительное ядро алгоритма
Алгоритм состоит из трёх независимых шагов:
- Построение графа и вычисление расстояний. Сложность [math]O(N^2)[/math];
- Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ( Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима). Сложность [math] O(N^2 \log N) [/math];
- Разбиение на кластеры. Сложность в худшем случае [math]O(N)[/math].
Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.
1.4 Макроструктура алгоритма
Макроструктура алгоритма описана в пункте 1.3. Отметим основные макрооперации, которые входят в состав алгоритма:
- Вычисление расстояний между вершинами;
- Добавление ребра в граф;
- Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
- Удаление ребра из графа.
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] //включаем вершину с номером 1 в дерево [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 Ресурс параллелизма алгоритма
Рассмотрим основные свойства задачи:
- Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].
- Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда:[math] 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]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.
Ресурс параллелизма основан на следующих возможностях:
- Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
- Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
- Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.
Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность [math]O(N \log N)[/math]. Например, Алгоритм GHS (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.
1.9 Входные и выходные данные алгоритма
Входные данные: множество объектов [math]x = (x_1,...,x_N)[/math]. Объём [math]O(N)[/math].
Выходные данные: множество кластеров [math]Clust = (Clust_1,...,Clust_K)[/math], где [math]Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l[/math] и [math]m, \sum_{i=1}^K {N_i} = N [/math]. Объём [math]O(N)[/math].
1.10 Свойства алгоритма
- Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
- Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более [math]\log_2 N[/math].
- Соотношение последовательной и параллельной сложности: [math] \frac{N^2 \log N} {N \log N} = N [/math].
- Вычислительная мощность: [math] \frac {N^2 \log N} {N} = N \log N[/math].
- Алгоритм детерминирован. Если случается, что имеются два ребра [math](x_i,x_j)[/math] и [math](x_l,x_m)[/math], такие что [math]d(x_i,x_j) = d(x_l,x_m)[/math], то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс [math]\min(i,j,l,m)[/math], если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, [math]i=l[/math] ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин [math]\min(j,m)[/math].
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в книге. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.
Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер.
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Python: MST Clustering
- С++: Parallel boost graph library
- C++: Minimum Spanning Tree
- Java: JGraphT PrimMinimumSpanningTree
- Java: JGraphT KruskalMinimumSpanningTree
- Python: SciPy
- Python: NetworkX
3 Литература
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
- Нейский И.М. Классификация и сравнение методов кластеризации
- C. Kingsford. Minimum Spanning Trees & Clustering
- Y. Zhou et al. Clustering with Minimum Spanning Trees
- Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
- Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
- Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
- Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем