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

Материал из Алговики
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Имеем [math]n[/math] объектов [math]a[/math], которые представляют собой элемент метрического пространства с метрикой [math]d(x^j,x^i)=[/math]

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 Существующие реализации алгоритма

3 Литература