Участник:Guryanovak/Алгоритм кластеризации, основанный на минимальном остовном дереве: различия между версиями
Строка 34: | Строка 34: | ||
int N; // Размер входных данных | int N; // Размер входных данных | ||
int number_of_clusters; // Число кластеров | int number_of_clusters; // Число кластеров | ||
− | int size = N* | + | int size = N*N; // Размер матрицы инцидентности |
Node nodes[N]; // Вершины(точки), заданные начальными условиями | Node nodes[N]; // Вершины(точки), заданные начальными условиями | ||
Edge edges[size]; // Все расстояния между вершинами | Edge edges[size]; // Все расстояния между вершинами | ||
− | vector<Edge> | + | vector<Edge> tree; // Рёбра минимального остовного дерева |
read_data(&nodes, file_name); // Считывание начальных данных | read_data(&nodes, file_name); // Считывание начальных данных | ||
Строка 45: | Строка 45: | ||
double distance = getDistance(node[i], node[j]); // Вычисление расстояния между вершинами | double distance = getDistance(node[i], node[j]); // Вычисление расстояния между вершинами | ||
edges[i*N + j] = Edge(i,j,distance); // Запись значения расстояния в массив | edges[i*N + j] = Edge(i,j,distance); // Запись значения расстояния в массив | ||
+ | edges[j*N + i] = Edge(i,j,distance); | ||
} | } | ||
} | } | ||
Строка 50: | Строка 51: | ||
//----------------Часть 2--------------// | //----------------Часть 2--------------// | ||
− | + | while(components.size > 1) { | |
− | for( | + | for component in components { |
− | + | edge e = findMinimalOutgoingEdge(component, edges) | |
− | + | if (find_set(e.first) != find_set(e.second)) { | |
− | + | connectComponentsWithEdge(component, e) | |
− | + | tree.add(e) | |
− | + | } | |
} | } | ||
− | |||
//----------------Часть 3--------------// | //----------------Часть 3--------------// | ||
− | for(int i = | + | sort(tree) |
− | remove_edge( | + | for(int i = tree.size() - 1; i > tree.size() - 1 - number_of_clusters; i--) { |
+ | remove_edge(tree, i); // Удаление самых длинных рёбер из MST - формирование кластеров | ||
} | } | ||
− | write_data( | + | write_data(tree); // Запись выходных данных |
</source> | </source> | ||
Версия 19:35, 15 октября 2016
Основные авторы описания: Гурьянов Алексей Константинович, Кибитова Валерия Николаевна
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
1 Свойства и структура алгоритмов
1.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.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
int N; // Размер входных данных
int number_of_clusters; // Число кластеров
int size = N*N; // Размер матрицы инцидентности
Node nodes[N]; // Вершины(точки), заданные начальными условиями
Edge edges[size]; // Все расстояния между вершинами
vector<Edge> tree; // Рёбра минимального остовного дерева
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); // Запись значения расстояния в массив
edges[j*N + i] = Edge(i,j,distance);
}
}
//----------------Часть 2--------------//
while(components.size > 1) {
for component in components {
edge e = findMinimalOutgoingEdge(component, edges)
if (find_set(e.first) != find_set(e.second)) {
connectComponentsWithEdge(component, e)
tree.add(e)
}
}
//----------------Часть 3--------------//
sort(tree)
for(int i = tree.size() - 1; i > tree.size() - 1 - number_of_clusters; i--) {
remove_edge(tree, i); // Удаление самых длинных рёбер из MST - формирование кластеров
}
write_data(tree); // Запись выходных данных