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

Основные авторы описания: Гурьянов Алексей Константинович, Кибитова Валерия Николаевна

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

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

На вход алгоритму подается набор [math]N[/math] векторов размерности [math]m[/math] : [math](a_{i,1}, a_{i,2}, ..., a_{i,m})[/math], где [math] a_j \in \mathbb {R} \quad \forall j \in [1,m], i \in [1..N] [/math] и количество кластеров [math]K[/math], на которые необходимо разбить множество точек.

На выход алгоритм должен вывести [math]N[/math] чисел от [math]1[/math] до [math]K[/math], показывающих принадлежность входных векторов кластерам.

1.2.1 Основные обозначения

• [math]E[/math] - множество рёбер.
• [math]V[/math] - множество вершин.
• [math]G = (V,E) [/math] - неориентированный граф, заданный множеством вершин [math]V[/math] и множеством рёбер [math]E[/math]
• [math]MST(G)[/math] (Minimum Spanning Tree) - минимальное остовное дерево графа [math][/math]. Остовное дерево — ациклический связный подграф данного связного неориентированного графа, в который входят все его вершины. Минимальное остовное дерево в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

1.2.2 Функция веса

Для решения задачи допускаются различные функции веса, используемые для построения минимального основного дерева. Подобные функции будут влиять на структура построенных кластеров и могут меняться в соответствии с требованиями к решению.

В данной статье будет рассматриваться евклидова метрика:

• [math] | x , y | = \sqrt{\sum_i^m (x_i - y_i)^2} [/math]

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

Работу алгоритма можно разделить на три блока:

• 1: Вычисление расстояний между вершинами и заполнение данных о компонентах связности
• 2: Построение минимального основного дерева
• 3: Разделение на K кластеров

Из них основное время работы алгоритма занимают блоки 1 и 2.

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

В алгоритме используются следующие структуры данных:

• Node - структура данных, описывающая вершину пространства. Включает в себя значения координат точки.
• Edge - структура данных, описывающая узел между двумя вершинами. Включает в себя индексы двух вершин и расстояние между ними
• Components - класс, описывающий состояние компонент связности в промежуточных состояниях графа по мере добавления в него ребер. Включает в себя информацию о том, какой компоненте связности принадлежит каждая точка и о расстоянии между каждой парой компонент связности, которая равна минимальному ребру между двумя вершинами в этих двух компонентах.

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

• 1: getDistance - находит расстояние между двумя вершинами графа как расстояние между соответствующими им точками пространства. (Сложность - O(m))
• 2: initializeComponents - инициализирует состояние класса Components информацией о вершинах и ребрах. В каждую исходную компоненту связности входит одна вершина. (Сложность - (O(N^2))
• 3: findMinimalOutgoingEdge - находит ребро c наименьшей длиной, исходящее из заданной компоненты связности. (Cложность - O(N))
• 4: findComp - возвращает индекс компоненты связности в которой находится вершина (Cложность - O(1))
• 5: connectComponentsWithEdge - соединяет две компоненты связности, связанные поданным на вход ребром. Объединение компонент включает в себя замену ребер инцидентности новой компоненты на минимальные ребра из пары объединяемых компонент. (Сложность - O(N))

Макрооперации 2-5 относятся к последовательной реализации алгоритма Борувки, который был выбран как основа вычислительного ядра алгоритма.

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

int N;        // Размер входных данных
int number_of_clusters;        // Число кластеров
int size = N*N;        // Размер матрицы инцидентности
Node nodes[N];        // Вершины(точки), заданные начальными условиями
Edge edges[size];        // Все расстояния между вершинами 
vector<Edge> tree;        // Рёбра минимального остовного дерева
Components comps;         // Структура компонент связности
read_data(&nodes, file_name);    // Считывание начальных данных

//----------------Вычисление расстояний между вершинами----------------//
for(int i = 0; i < N-1; i++) {
    for(int j = i+1; j < N; j++) {
        double distance = getDistance(node[i], node[j]);        // Вычисление расстояний между вершинами
	edges[i*N + j] = Edge(i,j,distance);        // Запись значения расстояния в массив
        edges[j*N + i] = Edge(i,j,distance);        // Запись значения расстояния в массив
    }
}

//----------------Заполнение данных о компонентах связности--------------//

initializeComponents(&comps, nodes, edges); 

//----------------Построение минимального основного дерева--------------//
while(comps.size > 1) {
    vector<edges> mstedges;
    for component in comps {
        edge e = findMinimalOutgoingEdge(component, comps, edges) // Нахождение минимального ребра инцидентного данной компоненте
        mstedges.add(e)
    }
    for mstedge in mstedges {
        if (findComp(comps, mstedge.first) != findComp(comps, mstedge.second)) { 
             connectComponentsWithEdge(comps, mstedge) // Объединение двух компонент
             tree.add(mstedge) // Добавление ребра в минимальное основное дерево
        }
    } 
}

//-----------------------Разделение на K кластеров--------------------------//
sort(tree)
for(int i = tree.size() - 1; i > tree.size() - 1 - number_of_clusters; i--) {
    remove_edge(tree, i);        // Удаление самых длинных рёбер из MST - формирование кластеров
}
write_data(tree);        // Запись выходных данных

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

Асимптотическую сложность алгоритма можно выразить как сумму временных сложностей четырех выделенных в описании частей:

[math] TC(n) = O(N^2m) + O(N^2 \log_2 N) + O(N^2) + O(N \log_2 N) = O(N^2 (m + \log_2 N) [/math]