Участник: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.5 Схема реализации последовательного алгоритма

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

//----------------Часть 1--------------//
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);        // Запись значения расстояния в массив
  }
}


//----------------Часть 2--------------//
sort(edges, size);        // Сортировка рёбер графа в порядке возрастания
for(int i = 0; i < size; i++) {        // Обходим список рёбер по возрастанию 
	if(find_set(edges[i].first) != find_set(edges[i].second)) {        // Если вершины принадлежат разным подграфам - связываем их
          Union(edges[i].first, edges[i].second);        // Если вершины принадлежат разным подграфам - связываем их
	  MST.push_back(edges[i]);        // Запись использованного ребра в минимальное остовное дерево
	  edges[i]->is_in_MST = true;     // Запись использованного ребра в минимальное остовное дерево
	}
}


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