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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 2: Строка 2:
 
== Свойства и структура алгоритмов ==
 
== Свойства и структура алгоритмов ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
 +
 +
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.
 +
Алгоритм кластеризации на k кластеров, основанный на построении минимального остовного дерева (MST):
 +
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
 +
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]],  [[Алгоритм Борувки | Алгоритм Борувки]],  [[Алгоритм Прима | Алгоритм Прима]])
 +
#Удаляется k-1 ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.
 +
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 +
Имеем <math>n</math> объектов <math>a</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x^j,x^i)=</math>
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===

Версия 20:45, 17 января 2017

Автор описания: Маркин Дмитрий Валерьевич, группа 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 Литература