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

Эта работа прошла предварительную проверку Дата последней правки страницы: 15.11.2016 Данная работа соответствует формальным критериям. Проверено Zhum.

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

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

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

Данный алгоритм нацелен на решение задачи кластеризации, то есть, разделения множества объектов на группы, называемые кластерами, так, чтобы внутри одного кластера оказались наиболее похожие (по некоторой метрике) друг на друга объекты, а объекты из разных кластеров как можно сильнее отличались друг от друга. Сам алгоритм состоит из следующих шагов:

1. Сведение набора объектов к графу. Объекты становятся вершинами графа, и каждые две вершины соединяются ребром, длина которого равняется расстоянию между этими объектами по некоторой метрике. Выбор метрики зависит от предметной области и желаемых свойств алгоритма. Например, метрикой может служить евклидово расстояние.
2. Построение минимального покрывающего (остовного) дерева в этом графе. Более подробно этот шаг описан в соответствующей статье.
3. Кластеризация путём удаления некоторого количества рёбер в этом дереве. В случае, если заранее известно количество кластеров [math]k[/math], достаточно удалить [math]k-1[/math] ребро с наибольшей длиной, чтобы получить [math]k[/math] связных компонент, которые объявляются кластерами. Если же количество кластеров заранее не известно, удаляются рёбра с длиной больше некоторого порога, задаваемого как параметр алгоритма. Возможны и более сложные стратегии выбора рёбер для отсечения.

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

На вход алгоритму подаётся [math]n[/math] объектов [math]a[/math], которые нужно кластеризовать. Каждый такой объект можно рассматривать как вектор или элемент некоторого метрического пространства. На пространстве, которому принадлежат [math]a[/math], задана метрика [math]d_{ij}=d(a_i,a_j)[/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]MST_i[/math]. Вершины, входящие в [math]i[/math]-е поддерево, объявляются принадлежащими кластеру с номером [math]i[/math].

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

Алгоритм состоит из трёх этапов:

1. Преобразование исходных данных. Сложность [math]O(n^2)[/math].
2. Поиск минимального покрывающего дерева. Последовательная сложность всех трёх основных алгоритмов (Борувки, Крускала и Прима) [math]O(|E|*log(|E|)) = O(n^2*log(n^2))[/math].
3. Разбиение на кластеры. Вычислительная сложность [math]O(n)[/math] для простых стратегий разбиения.

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

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

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

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

Описание алгоритма на псевдокоде:

MST_Cluster(object[n] objects){
    g = Pairs(objects, metric);
    mst = Create_MST(graph);
    parts = Split_MST(mst);
    for i in range(parts){
         clusters[i] = parts[i].vertices;
    }
    return clusters
}

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

Последовательная сложность алгоритма определяется самой сложной его частью (см. пункт 1.3) и равна [math]O(n^2*log(n^2))[/math].

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

Информационный граф алгоритма. Показана последовательная реализация (большой прямоугольник) и схема распараллеливания алгоритма построения минимального покрывающего дерева.

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

Ресурс параллелизма алгоритма основан на свойстве ассоциативности рёбер:
Пусть [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]

Параллельная схема вычисления устроена следующим образом:

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

Сложность параллельного алгоритма зависит от соотношения объёма входных данных и числа процессов. Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую сложность [math]O(n*log(n))[/math]. Эта же оценка будет выполняться и для всего алгоритма кластеризации.

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

На вход алгоритму подаются объекты [math](o_1, o_2, ..., o_n)[/math].
Выходом алгоритма является множество непересекающихся кластеров: [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].

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

Важным свойством алгоритма является то, что при его распараллеливании по описанной выше стратегии важно правильно выбирать количество процессов. При увеличении количества процессов возрастают затраты на фазу слияния деревьев, полученных каждым процессом: растёт число этапов, в которые производится слияние, а следовательно, возрастают затраты на коммуникацию между процессами, и распределение нагрузки становится более неравномерным из-за того, что часть процессов должна проделать значительно большее количество работы по слиянию деревьев.
Вычислительная мощность алгоритма имеет порядок [math]O(n*log(n^2))[/math].
Ещё одним важным свойством алгоритма является его детерминированность в том случае, если для данного набора векторов существует единственное минимальное покрывающее дерево: при использовании детерминированной стратегии разбиения его на поддеревья алгоритм получает единственный результат для каждого набора данных. Однако, время работы может отличаться в зависимости от начального распределения рёбер по процессам.

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

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

Время работы алгоритма в зависимости от числа процессов и размера получающегося графа.

На графике на логарифмической шкале показана зависимость времени работы алгоритма от числа процессов. Приведены измерения для трёх наборов данных, различающихся размером получаюшегося графа: 4, 8 и 30 миллиардов рёбер соответственно. Как видно из графика, при большом объёме данных алгоритм хорошо масштабируется. Однако, существует предел возможностей распараллеливания: если количество процессов будет сопоставимо с размером набора данных (не показано на графике), время работы может начать расти с увеличением количества процессов, потому что ускорение за счёт распараллеливания будет нивелироваться возрастающими затратами на обмен данными между процессами.

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

Основным вычислительным ядром алгоритма является алгоритм построения минимального покрывающего (остовного) дерева, применяющийся для многих задач, и многие библиотеки ограничиваются его реализацией, без реализации основанного на нём алгоритма кластеризации. Примеры реализаций алгоритмов построения MST:

• С++: Boost graph library (алгоритмы Борувки и Крускала)
• C++, MPI: Parallel boost graph library (алгоритм Борувки)
• Java: JGraphT (алгоритмы Крускала и Прима)
• Python: SciPy

3 Литература

1. Нейский И.М. Классификация и сравнение методов кластеризации
   
2. C. Kingsford. Minimum Spanning Trees & Clustering ([1])
3. Y. Zhou et al. Clustering with Minimum Spanning Trees