Участник:Markin/Алгоритм кластеризации, основанный на минимальном покрывающем дереве
Перейти к навигации
Перейти к поиску
Автор описания: Маркин Дмитрий Валерьевич, группа 611
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
Алгоритм кластеризации на [math]K[/math] кластеров, основанный на построении минимального остовного дерева ([math]MST[/math]):
- По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
- Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: Алгоритм Крускала, Алгоритм Борувки, Алгоритм Прима)
- Удаляется [math]K-1[/math] ребро минимального остовного дерева с максимальным весом и получаются [math]K[/math] компонент связности.