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

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

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

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

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

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

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

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

Функция веса

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

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

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