Участник:Sarseev/Алгоритм кластеризации, основанный на минимальном покрывающем дереве: различия между версиями
Перейти к навигации
Перейти к поиску
Sarseev (обсуждение | вклад) (Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === === Математическое описа…») |
Sarseev (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| + | Данный алгоритм нацелен на решение задачи кластеризации, то есть, разделения множества объектов на группы, называемые кластерами, так, чтобы внутри одного кластера оказались наиболее похожие (по некоторой метрике) друг на друга объекты, а объекты из разных кластеров как можно сильнее отличались друг от друга. | ||
| + | Сам алгоритм состоит из следующих шагов: | ||
| + | # Сведение набора объектов (векторов) к графу. Объекты становятся вершинами графа, и каждые две вершины соединяются ребром, длина которого равняется расстоянию между этими объектами по некоторой метрике. Выбор метрики зависит от предметной области и желаемых свойств алгоритма. Например, метрикой может служить евклидово расстояние. | ||
| + | # Построение минимального покрывающего (остовного) дерева в этом графе. Более подробно этот шаг описан в [[Построение_минимального_остовного_дерева_(MST)|соответствующей статье]]. | ||
| + | # Кластеризация путём удаления некоторого количества рёбер в этом дереве. В случае, если заранее известно количество кластеров <math>k</math>, достаточно удалить <math>k-1</math> ребро с наибольшей длиной, чтобы получить <math>k</math> связных компонент, которые объявляются кластерами. Если же количество кластеров заранее не известно, удаляются рёбра с длиной больше некоторого порога, задаваемого как параметр алгоритма. Возможны и более сложные стратегии выбора рёбер для отсечения. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | На вход алгоритму подаётся <math>n</math> объектов <math>a</math>, которые нужно кластеризовать. На пространстве, которому принадлежат <math>a</math>, задана метрика <math>d_{ij}=d(a_i,a_j)</math>. <br> | ||
| + | Первый шаг алгоритма строит граф <math>G=(V,E)</math>, где <math>V</math> - множество вершин графа <math>(|V|=n)</math>, а <math>E</math> - множество его рёбер <math>(|E| = \frac{n*(n-1)}{2})</math>. <br> | ||
| + | На втором этапе строится минимальное покрывающее дерево <math>MST(G)</math>. После удаления рёбер дерево распадается на поддеревья <math>MST_i</math>. Вершины, входящие в <math>i</math>-е поддерево, объявляются принадлежащими кластеру с номером <math>i</math>. | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | Алгоритм состоит из трёх этапов: | ||
| + | # Преобразование исходных данных. Сложность <math>O(n^2)</math>. | ||
| + | # Поиск минимального покрывающего дерева. Последовательная сложность всех трёх основных алгоритмов ([[Алгоритм_Борувки|Борувки]], [[Алгоритм_Крускала|Крускала]] и [[Алгоритм_Прима|Прима]]) <math>O(|E|*log(|E|)) = O(n^2*log(n^2))</math>. | ||
| + | # Разбиение на кластеры. Вычислительная сложность <math>O(n)</math> для простых стратегий разбиения. | ||
| + | Таким образом, вычислительным ядром алгоритма является алгоритм построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность. Стратегии распараллеливания алгоритма основаны на распараллеливании алгоритма построения минимального покрывающего дерева. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| + | В состав алгоритма входит алгоритм [[Построение_минимального_остовного_дерева_(MST)|построения минимального остовного дерева]], являющийся его вычислительным ядром. Также в отдельную часть можно выделить алгоритм разбиения получившегося остовного дерева на кластеры. | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| + | Описание алгоритма на псевдокоде: | ||
| + | <source lang=cpp> | ||
| + | MST_Cluster(object[n] objects){ | ||
| + | g = Pairs(objects, metric); | ||
| + | mst = Create_MST(graph); | ||
| + | parts = Split_MST(mst); | ||
| + | for i in range(parts){ | ||
| + | clusters[i] = parts[i].vertices; | ||
| + | } | ||
| + | return clusters | ||
| + | } | ||
| + | |||
| + | </source> | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Последовательная сложность алгоритма определяется самой сложной его частью (см. пункт 1.3) и равна <math>O(n^2*log(n^2))</math>. | ||
=== Информационный граф === | === Информационный граф === | ||
| − | [[Файл:MST_cluster.png]] | + | [[Файл:MST_cluster.png|thumb|center|1043px|Информационный граф алгоритма. Показана последовательная реализация (большой прямоугольник) и схема распараллеливания алгоритма построения минимального покрывающего дерева.]] |
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| Строка 15: | Строка 43: | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Локальность данных и вычислений === | === Локальность данных и вычислений === | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
Версия 20:39, 15 октября 2016
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 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 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Данный алгоритм нацелен на решение задачи кластеризации, то есть, разделения множества объектов на группы, называемые кластерами, так, чтобы внутри одного кластера оказались наиболее похожие (по некоторой метрике) друг на друга объекты, а объекты из разных кластеров как можно сильнее отличались друг от друга. Сам алгоритм состоит из следующих шагов:
- Сведение набора объектов (векторов) к графу. Объекты становятся вершинами графа, и каждые две вершины соединяются ребром, длина которого равняется расстоянию между этими объектами по некоторой метрике. Выбор метрики зависит от предметной области и желаемых свойств алгоритма. Например, метрикой может служить евклидово расстояние.
- Построение минимального покрывающего (остовного) дерева в этом графе. Более подробно этот шаг описан в соответствующей статье.
- Кластеризация путём удаления некоторого количества рёбер в этом дереве. В случае, если заранее известно количество кластеров [math]k[/math], достаточно удалить [math]k-1[/math] ребро с наибольшей длиной, чтобы получить [math]k[/math] связных компонент, которые объявляются кластерами. Если же количество кластеров заранее не известно, удаляются рёбра с длиной больше некоторого порога, задаваемого как параметр алгоритма. Возможны и более сложные стратегии выбора рёбер для отсечения.
1.2 Математическое описание алгоритма
На вход алгоритму подаётся [math]n[/math] объектов [math]a[/math], которые нужно кластеризовать. На пространстве, которому принадлежат [math]a[/math], задана метрика [math]d_{ij}=d(a_i,a_j)[/math].
Первый шаг алгоритма строит граф [math]G=(V,E)[/math], где [math]V[/math] - множество вершин графа [math](|V|=n)[/math], а [math]E[/math] - множество его рёбер [math](|E| = \frac{n*(n-1)}{2})[/math].
На втором этапе строится минимальное покрывающее дерево [math]MST(G)[/math]. После удаления рёбер дерево распадается на поддеревья [math]MST_i[/math]. Вершины, входящие в [math]i[/math]-е поддерево, объявляются принадлежащими кластеру с номером [math]i[/math].
1.3 Вычислительное ядро алгоритма
Алгоритм состоит из трёх этапов:
- Преобразование исходных данных. Сложность [math]O(n^2)[/math].
- Поиск минимального покрывающего дерева. Последовательная сложность всех трёх основных алгоритмов (Борувки, Крускала и Прима) [math]O(|E|*log(|E|)) = O(n^2*log(n^2))[/math].
- Разбиение на кластеры. Вычислительная сложность [math]O(n)[/math] для простых стратегий разбиения.
Таким образом, вычислительным ядром алгоритма является алгоритм построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность. Стратегии распараллеливания алгоритма основаны на распараллеливании алгоритма построения минимального покрывающего дерева.
1.4 Макроструктура алгоритма
В состав алгоритма входит алгоритм построения минимального остовного дерева, являющийся его вычислительным ядром. Также в отдельную часть можно выделить алгоритм разбиения получившегося остовного дерева на кластеры.
1.5 Схема реализации последовательного алгоритма
Описание алгоритма на псевдокоде:
MST_Cluster(object[n] objects){
g = Pairs(objects, metric);
mst = Create_MST(graph);
parts = Split_MST(mst);
for i in range(parts){
clusters[i] = parts[i].vertices;
}
return clusters
}
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма определяется самой сложной его частью (см. пункт 1.3) и равна [math]O(n^2*log(n^2))[/math].
