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

{{Assignment|Zhum}}

{{algorithm
| name              = Алгоритм кластеризации, основанный на минимальном покрывающем дереве
| serial_complexity = <math>O(N^2 \log_2 N)</math>
| input_data        = <math> O(N) </math>
| output_data       = <math> O(N) </math>
}}

'''Автор''': Арсеев С. П., группа 620

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм нацелен на решение задачи кластеризации, то есть, разделения множества объектов на группы, называемые кластерами, так, чтобы внутри одного кластера оказались наиболее похожие (по некоторой метрике) друг на друга объекты, а объекты из разных кластеров как можно сильнее отличались друг от друга.
Сам алгоритм состоит из следующих шагов:
# Сведение набора объектов к графу. Объекты становятся вершинами графа, и каждые две вершины соединяются ребром, вес которого равняется расстоянию между этими объектами по некоторой метрике. Выбор метрики зависит от предметной области и желаемых свойств алгоритма. Например, метрикой может служить евклидово расстояние.
# Построение минимального покрывающего (остовного) дерева в этом графе. Более подробно этот шаг описан в [[Построение_минимального_остовного_дерева_(MST)|соответствующей статье]].
# Кластеризация путём удаления некоторого количества рёбер в этом дереве. В случае, если заранее известно количество кластеров <math>k</math>, достаточно удалить <math>k-1</math> ребро с наибольшей длиной, чтобы получить <math>k</math> связных компонент, которые объявляются кластерами. Если же количество кластеров заранее не известно, удаляются рёбра с длиной больше некоторого порога, задаваемого как параметр алгоритма. Возможны и более сложные стратегии выбора рёбер для отсечения.
=== Математическое описание алгоритма ===
На вход алгоритму подаётся <math>n</math> объектов <math>a</math>, которые нужно кластеризовать. Каждый такой объект можно рассматривать как вектор или элемент некоторого метрического пространства. На пространстве, которому принадлежат <math>a</math>, задана метрика <math>d_{ij}=d(a_i,a_j)</math>. <br>
Первый шаг алгоритма строит граф <math>G=(V,E)</math>, где <math>V</math> - множество вершин графа <math>(|V|=n)</math>, а <math>E</math> - множество его рёбер <math>(|E| = \frac{n*(n-1)}{2})</math>. <br>
На втором этапе строится минимальное покрывающее дерево <math>MST(G)</math>. После удаления рёбер дерево распадается на поддеревья <math>MST_i</math>. Вершины, входящие в <math>i</math>-е поддерево, объявляются принадлежащими кластеру с номером <math>i</math>.
=== Вычислительное ядро алгоритма ===
Алгоритм состоит из трёх этапов:
# Преобразование исходных данных. Сложность <math>O(n^2)</math>.
# Поиск минимального покрывающего дерева. Последовательная сложность всех трёх основных алгоритмов ([[Алгоритм_Борувки|Борувки]], [[Алгоритм_Крускала|Крускала]] и [[Алгоритм_Прима|Прима]]) <math>O(|E|*log(|E|)) = O(n^2*log(n^2)) = O(2*n^2*log(n)) = O(n^2*log(n))</math>.
# Разбиение на кластеры. Вычислительная сложность для простых стратегий разбиения <math>O(n)</math> или <math>O(1)</math> в зависимости от формата выходных данных и отсортированности набора рёбер, получаемого алгоритмом построения минимального покрывающего дерева.
Таким образом, вычислительным ядром алгоритма является алгоритм построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность. Стратегии распараллеливания алгоритма основаны на распараллеливании алгоритма построения минимального покрывающего дерева.
=== Макроструктура алгоритма ===
В состав алгоритма входит алгоритм [[Построение_минимального_остовного_дерева_(MST)|построения минимального покрывающего дерева]], являющийся его вычислительным ядром. Также в отдельную часть можно выделить алгоритм разбиения получившегося покрывающего дерева на кластеры.
=== Схема реализации последовательного алгоритма ===
Описание алгоритма на псевдокоде:
<source lang=cpp>
MST_Cluster(object[n] objects){
    graph = Pairs(objects, metric); //Из набора объектов генерируется граф
    mst = Create_MST(graph); //Алгоритм построения минимального покрывающего дерева строит это дерево для получившегося графа
    parts = Split_MST(mst); //Из дерева удаляются рёбра, в результате чего оно делится на части
    for i in range(parts){
         clusters[i] = parts[i].vertices; //Эти части объявляются кластерами
    }
    return clusters
}

</source>
=== Последовательная сложность алгоритма ===
Последовательная сложность алгоритма определяется самой сложной его частью (см. пункт 1.3) и равна <math>O(n^2*log(n))</math>.
=== Информационный граф ===
[[Файл:MST_cluster.png|thumb|center|1043px|Информационный граф алгоритма. Показана последовательная реализация (большой прямоугольник) и схема распараллеливания алгоритма построения минимального покрывающего дерева.]]
=== Ресурс параллелизма алгоритма ===
Ресурс параллелизма алгоритма основан на свойстве ассоциативности рёбер: <br>
Пусть <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>O(n*log(n))</math> при использовании <math>n</math> вычислительных узлов (то есть, столько же, сколько и вершин в графе), в частности, такой алгоритм был предложен в статье Роберта Галлагера (статья 1). Существуют и другие распределённые алгоритмы построения минимального покрывающего дерева, имеющие более низкую параллельную сложность при использовании <math>n</math> узлов [https://ie.technion.ac.il/~kutten/dblp_30.pdf], но аналитического вывода сложности и времени выполнения распределённых версий даже простых алгоритмов (таких, как алгоритм Крускала) в зависимости от количества вычислительных узлов обнаружить не удалось, обычно она показывается экспериментальными результатами.

=== Входные и выходные данные алгоритма ===
На вход алгоритму подаются объекты <math>(o_1, o_2, ..., o_n)</math>. <br>
Выходом алгоритма является множество непересекающихся кластеров: <math>C=(C_1, C_2, ..., C_k); C_i = (o_{i,1}, o_{i,2}, ..., o_{i, n_i}); o(i, l) \ne o(j, m); i \ne j; \forall l, m; \sum{n_i} = n </math>.
=== Свойства алгоритма ===
Важным свойством алгоритма является то, что при его распараллеливании по описанной выше стратегии важно правильно выбирать количество процессов. При увеличении количества процессов возрастают затраты на фазу слияния деревьев, полученных каждым процессом: растёт число этапов, в которые производится слияние, а следовательно, возрастают затраты на коммуникацию между процессами, и распределение нагрузки становится более неравномерным из-за того, что часть процессов должна проделать значительно большее количество работы по слиянию деревьев. <br>
Вычислительная мощность алгоритма имеет порядок <math>O(n*log(n^2))</math>. <br>
Ещё одним важным свойством алгоритма является его детерминированность в том случае, если для данного набора векторов существует единственное минимальное покрывающее дерево: при использовании детерминированной стратегии разбиения его на поддеревья алгоритм получает единственный результат для каждого набора данных. Свойство ассоциативности рёбер обеспечивает в этом случае детерминированность решения вне зависимости от исходного распределения рёбер по вычислительным узлам в начале работы алгоритма, так как если для графа существует единственное минимальное покрывающее дерево, то оно и будет построено. Однако, время работы может отличаться в зависимости от начального распределения рёбер по процессам. <br>
В случае, если для графа существует несколько различных минимальных покрывающих деревьев (вырожденный случай - граф, у которого веса всех рёбер одинаковы), результат алгоритма недетерминирован (в частности, в описанном выше вырожденном случае разбиение на кластеры произойдёт случайным образом, в зависимости от порядка записи рёбер и их распределения по вычислительным узлам).
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
[[Файл:MST_cluster_time.png|thumb|center|600px|Время работы алгоритма в зависимости от числа процессов и объёма входных данных.]] <br>
[[Файл:Mst_scale2.PNG|thumb|center|600px|Время работы алгоритма при меньшем числе процессов и объёме входных данных.]] <br>
[[Файл:Mst_cluster_efficiency.PNG|thumb|center|600px|Эффективность распараллеливания алгоритма.]] <br>
На первом и втором графике на логарифмической шкале показана зависимость времени работы алгоритма от числа процессов. Приведены измерения для девфти наборов данных, различающихся количеством входных векторов: от 512 до 131072 элементов. Использовалась собственная реализация алгоритма, основанная на [https://github.com/gpiskas/MinSpanTree_Kruskal_MPI_OpenMP сторонней реализации] алгоритма построения минимального покрывающего дерева (без OpenMP-части для более точного измерения масштабируемости описанной выше архитектуры). Изменения относительно приведённой реализации в основном коснулись генерации входных данных для алгоритма построения остовного дерева: в качестве функции расстояния между элементами при генерации графа бралось случайное число от 0 до 1. Изменения времени работы алгоритма при разных запусках (и, соответственно, с другим набором случайных чисел) незначительны. <br>
Первая часть алгоритма - генерация графа - производилась распределением рёбер графа поровну между всеми вычислительными узлами и подсчёта веса каждого путём генерации случайного числа. Коммуникация между вычислительными узлами на этом этапе не производится; получившийся набор рёбер передаётся на вход шагу 2. Таким образом, вычислительная сложность для каждого узла равна <math>O(n^2/m)</math>, где <math>m</math> - количество вычислительных узлов. <br>
Вторая часть алгоритма - построение минимального покрывающего дерева - производилась с помощью приведённого по ссылке выше распределённого алгоритма Крускала, основанного на свойстве ассоциативности рёбер (см. пункт 1.8). Аналитическое вычисление сложности алгоритма для каждого вычислительного узла затруднительно, и подобные расчёты не удалось обнаружить нигде, включая статью про алгоритм Крускала. Существует оценка времени работы для конкретного числа вычислительных узлов, выводящемуся из объёма входных данных, приведённая в [https://stanford.edu/~rezab/classes/cme323/S15/projects/distributed_minimum_spanning_trees_report.pdf статье], но оценок сложности для произвольного количества вычислительных узлов обнаружить не удалось. <br>
Третья часть алгоритма - разбиение на кластеры - имеет в данном случае вычислительную сложность <math>O(1)</math>, так как массив рёбер, получаемый алгоритмом Крускала, отсортирован по длине, и часть этого массива (за исключением последних нескольких рёбер) можно считать уже кластеризованным набором. Эта часть не имеет ресурса параллельности и является в данном случае скорее служебной (потому что на этом этапе не производится никаких вычислений, а просто данные переводятся из одного формата в другой), и поэтому она даже не вошла в предоставленный текст реализации алгоритма, так как она не может оказать никакого влияния на его сложность.
Полный текст изменённой части программы расположен по адресу [http://pastebin.com/5US84UgR]. <br>
Запуск проводился на аппаратной платформе [http://hpc.cmc.msu.ru/bgp IBM BlueGene/P]. Для каждого размера входных данных были проведены четыре теста: на 128, 256, 512 и 1024 вычислительных узлах соответственно. При дальнейшем увеличении объёма данных время выполнения программы превысило доступный предел (15 минут для 128 узлов). <br>
Из первого и второго графиков видно, что время работы алгоритма возрастает с увеличением объёма входных данных с зависимостью, близкой к квадратической, что соответствует теоретической оценке последовательной сложности алгоритма (<math>O(n^2*log(n))</math>). Вычислительная сложность последовательной части алгоритма мала по сравнению со сложностью его параллельной части, что приводит к существенному снижению времени работы алгоритма при увеличении количества вычислительных узлов. <br>
На третьем графике показана зависимость эффективности распараллеливания алгоритма в зависимости от числа вычислительных узлов и объёма входных данных. Видно, что эффективность быстро падает для малого объёма входных данных (из-за возрастающих затрат на обмен информацией) и остаётся высокой на графе из 2048 вершин. При большом объёме входных данных и большом числе вычислительных узлов эффективность распараллеливания начинает снижаться. Это вызвано возрастанием затрат на фазу слияния, приводящим к неравномерной загрузке процессора. График эффективности распараллеливания для объёмов данных, показанных на графике 1, построить невозможно из-за аппаратных ограничений (при выполнении алгоритма на одном процессоре рёбра графа не поместятся в память вычислительного узла, а время выполнения окажется слишком большим), но тенденция снижения эффективности распараллеливания видна на третьем графике. <br>


=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
Основным вычислительным ядром алгоритма является алгоритм построения минимального покрывающего (остовного) дерева, применяющийся для многих задач, и многие библиотеки ограничиваются его реализацией, без реализации основанного на нём алгоритма кластеризации. Примеры реализаций алгоритмов построения MST: 
* С++:  [http://www.boost.org/doc/libs/1_62_0/libs/graph/doc/ Boost graph library] (алгоритмы Борувки и Крускала)
* C++, MPI: [http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html Parallel boost graph library] (алгоритм Борувки)
* Java: [http://jgrapht.org/ JGraphT] (алгоритмы Крускала и Прима)
* Python: [http://docs.scipy.org/doc/scipy-0.15.1/reference/index.html SciPy]
== Литература ==
# R. G. Gallager et al. A Distributed Algorithm for Minimum-Weight Spanning Trees 
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering ([https://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec07a-mst.pdf])
# Y. Zhou et al. Clustering with Minimum Spanning Trees