Участник: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 Последовательная сложность алгоритма

Среди выделенных в описании частей алгоритма, самую большую сложность для оценивания временной сложности вызывает часть 3, являющаяся реализацией алгоритма Борувки. Однако если заметить, что после выполнения каждого тела внешнего цикла количество компонент связности будет уменьшаться как минимум вдвое (так как одно ребро в списке ребер минимального основного дерева может повториться максимум двое), то можно сделать вывод, что сложность в худшем случае этого блока алгоритма является [math] O (N^2 \log_2 N) [/math].

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

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

Если посчитать размерность пространства входных точек за константу при расчете сложности, то временная сложность выразится как

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