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

Автор описания: Маркин Дмитрий Валерьевич, группа 611

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

Общее описание алгоритма

Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.

Алгоритм кластеризации на k кластеров, основанный на построении минимального остовного дерева (MST):

1. По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
2. Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
3. Удаляется k-1 ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

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

Имеем [math]\displaystyle{ N }[/math] объектов [math]\displaystyle{ x }[/math], которые представляют собой элемент метрического пространства с метрикой [math]\displaystyle{ d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}} }[/math].

На первом шаге строим граф [math]\displaystyle{ G=(V,E) }[/math] с множеством вершин [math]\displaystyle{ V }[/math] ([math]\displaystyle{ |V|=N }[/math]) и множеством ребер [math]\displaystyle{ E }[/math] ([math]\displaystyle{ |E|=\frac{N*(N-1)} {2} }[/math]).

Информационный граф

Информационный граф параллельного алгоритма построения минимального покрывающего дерева