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

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. После этого полученные остовные леса объединяются в единое остовное дерево для всего графа.

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 Свойства алгоритма

Важным свойством алгоритма является то, что