Участник:SenderovichNikita/Алгоритм кластеризации, основанный на построении каркаса: различия между версиями
(создание страницы) |
м |
||
| Строка 1: | Строка 1: | ||
| − | Данный документ содержит описание алгоритма кластеризации, основанного на построении минимального остовного дерева. | + | Данный документ содержит описание алгоритма кластеризации, основанного на построении [[Построение минимального остовного дерева (MST)|минимального остовного дерева]] (каркаса, остова, кратчайшего незамкнутого пути, минимального покрывающего дерева, англ. Minimum Spanning Tree (MST)) - эвристического графового алгоритма построения разбиения множества объектов на такие непересекающиеся подмножества объектов, что объекты, принадлежащие одному подмножеству, схожи по заданной метрике в большей степени, чем объекты, принадлежащие разным группам. |
| + | |||
| + | Как и все алгоритмы кластеризации, данный алгоритм может быть применён для решения задач кластерного анализа, выделения типовых и нетипичных объектов в рассматриваемой выборке объектов. Его достоинствами по сравнению с другими аналогичными алгоритмами машинного обучения являются наглядность, идейная простота, возможность контролировать число кластеров. Главным недостатком является ограниченная применимость: алгоритм лучше всего подходит для выделения кластеров типа сгущений или лент, наличие разреженного фона или узких перемычек между кластерами может приводить к неадекватному с точки зрения аналитика результату<ref>[http://www.ccas.ru/voron/download/Clustering.pdf Воронцов К.В. "Лекции по алгоритмам кластеризации и многомерного шкалирования"]</ref>. Другим недостатком является высокая вычислительная сложность: на выборках более 100 тыс. объектов без применения параллельных вычислений применить алгоритм невозможно. Рассмотрению соответствующих параллельных алгоритмов и посвящена данная статья. | ||
| + | |||
| + | == Свойства и структура алгоритма == | ||
| + | === Общее описание алгоритма === | ||
| + | Рассматривается выборка <math>X = \{x_i\}, i = 1, 2, \ldots, N</math>, состоящая из <math>N</math> объектов в пространстве с заданной симметричной неотрицательной функцией расстояния <math>\rho</math>. Данную выборку можно рассматривать как связный неориентированный взвешенный граф <math>G</math>, множество вершин которого совпадает со множеством объектов выборки, веса рёбер соотвествуют значениям функции расстояния между соответсвующими вершинами. | ||
| + | |||
| + | Также должно быть задано искомое число кластеров <math>K</math>. | ||
| + | |||
| + | Идея рассматриваемого алгоритма кластеризации очень проста: | ||
| + | * с помощью какого-либо алгоритма на определённом выше графе строится [[Построение минимального остовного дерева (MST)| минимальное остовное дерево]] | ||
| + | * из полученного дерева выбрасывается <math>K - 1</math> ребро с наибольшими весами, что приводит к появлению в остовном дереве <math>K</math> компонент связности, каждая из которых объявляется кластером | ||
| + | |||
| + | Оптимальное число <math>K</math> аналитик может также определить не изначально, а подобрать, рассматривая отсоритированную по убыванию последовательность весов рёбер в остовном дереве: если имеется резкое уменьшение весов, то можно удалить все рёбра до него. | ||
| + | |||
| + | Поскольку второй шаг алгоритма достаточно тривиален и алгоритмически прост по сравнению с первым, сосредоточимся далее на алгоритмах построения остовного дерева. Задача построения минимального остовного дерева связного | ||
| + | |||
| + | '''Алгоритм Борувки'''<ref>Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.</ref><ref>Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.</ref> предназначен для решения [[Построение минимального остовного дерева (MST)|задачи о построении минимального остовного дерева]] во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого [[Алгоритм GHS|алгоритма GHS]]. | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
| + | |||
| + | Пусть задан связный неориентированный граф <math>G = (V, E)</math> с весами рёбер <math>f(e)</math>. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру). | ||
| + | |||
| + | Алгоритм Борувки основан на следующих двух свойствах задачи: | ||
| + | * '''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. | ||
| + | * '''Схлопывание фрагментов'''. Пусть <math>F</math> – фрагмент минимального остовного дерева графа <math>G</math>, а граф <math>G'</math> получен из <math>G</math> склеиванием вершин, принадлежащих <math>F</math>. Тогда объединение <math>F</math> и минимального остовного дерева графа <math>G'</math> даёт минимальное остовное дерево исходного графа <math>G</math>. | ||
| + | |||
| + | В начале работы алгоритма каждая вершина графа <math>G</math> является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются. | ||
| + | |||
| + | === Вычислительное ядро алгоритма === | ||
| + | === Макроструктура алгоритма === | ||
| + | === Схема реализации последовательного алгоритма === | ||
| + | === Последовательная сложность алгоритма === | ||
| + | === Информационный граф === | ||
| + | === Ресурс параллелизма алгоритма === | ||
| + | |||
| + | Алгоритму Борувки обладает большим потенциалом параллелизма, так как его основная операция (выбор минимального исходящего ребра во фрагменте) может исполнятся независимо для каждого фрагмента. | ||
| + | |||
| + | === Входные и выходные данные алгоритма === | ||
| + | === Свойства алгоритма === | ||
| + | |||
| + | == Программная реализация алгоритма == | ||
| + | === Особенности реализации последовательного алгоритма === | ||
| + | === Локальность данных и вычислений === | ||
| + | ==== Локальность реализации алгоритма ==== | ||
| + | ===== Структура обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
| + | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Масштабируемость алгоритма ==== | ||
| + | ==== Масштабируемость реализации алгоритма ==== | ||
| + | === Динамические характеристики и эффективность реализации алгоритма === | ||
| + | === Выводы для классов архитектур === | ||
| + | === Существующие реализации алгоритма === | ||
| + | |||
| + | * C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library]; функции <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree dense_boruvka_minimum_spanning_tree]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-then-merge boruvka_then_merge]</code>, <code>[http://www.boost.org/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge boruvka_mixed_merge]</code> сочетают алгоритм Борувки и [[алгоритм Крускала]]. | ||
| + | |||
| + | == Литература == | ||
| + | |||
| + | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
Версия 15:16, 15 октября 2016
Данный документ содержит описание алгоритма кластеризации, основанного на построении минимального остовного дерева (каркаса, остова, кратчайшего незамкнутого пути, минимального покрывающего дерева, англ. Minimum Spanning Tree (MST)) - эвристического графового алгоритма построения разбиения множества объектов на такие непересекающиеся подмножества объектов, что объекты, принадлежащие одному подмножеству, схожи по заданной метрике в большей степени, чем объекты, принадлежащие разным группам.
Как и все алгоритмы кластеризации, данный алгоритм может быть применён для решения задач кластерного анализа, выделения типовых и нетипичных объектов в рассматриваемой выборке объектов. Его достоинствами по сравнению с другими аналогичными алгоритмами машинного обучения являются наглядность, идейная простота, возможность контролировать число кластеров. Главным недостатком является ограниченная применимость: алгоритм лучше всего подходит для выделения кластеров типа сгущений или лент, наличие разреженного фона или узких перемычек между кластерами может приводить к неадекватному с точки зрения аналитика результату[1]. Другим недостатком является высокая вычислительная сложность: на выборках более 100 тыс. объектов без применения параллельных вычислений применить алгоритм невозможно. Рассмотрению соответствующих параллельных алгоритмов и посвящена данная статья.
Содержание
- 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]X = \{x_i\}, i = 1, 2, \ldots, N[/math], состоящая из [math]N[/math] объектов в пространстве с заданной симметричной неотрицательной функцией расстояния [math]\rho[/math]. Данную выборку можно рассматривать как связный неориентированный взвешенный граф [math]G[/math], множество вершин которого совпадает со множеством объектов выборки, веса рёбер соотвествуют значениям функции расстояния между соответсвующими вершинами.
Также должно быть задано искомое число кластеров [math]K[/math].
Идея рассматриваемого алгоритма кластеризации очень проста:
- с помощью какого-либо алгоритма на определённом выше графе строится минимальное остовное дерево
- из полученного дерева выбрасывается [math]K - 1[/math] ребро с наибольшими весами, что приводит к появлению в остовном дереве [math]K[/math] компонент связности, каждая из которых объявляется кластером
Оптимальное число [math]K[/math] аналитик может также определить не изначально, а подобрать, рассматривая отсоритированную по убыванию последовательность весов рёбер в остовном дереве: если имеется резкое уменьшение весов, то можно удалить все рёбра до него.
Поскольку второй шаг алгоритма достаточно тривиален и алгоритмически прост по сравнению с первым, сосредоточимся далее на алгоритмах построения остовного дерева. Задача построения минимального остовного дерева связного
Алгоритм Борувки[2][3] предназначен для решения задачи о построении минимального остовного дерева во взвешенном неориентированном графе. Алгоритм хорошо параллелизуется и является основой для распределённого алгоритма GHS.
1.2 Математическое описание алгоритма
Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Предполагается, что веса всех рёбер различны (если это не так, то можно упорядочить рёбра сначала по весу, а потом по номеру).
Алгоритм Борувки основан на следующих двух свойствах задачи:
- Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву.
- Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].
В начале работы алгоритма каждая вершина графа [math]G[/math] является отдельным фрагментом. На очередном шаге у каждого фрагмента выбирается исходящее ребро минимального веса (если такое ребро существует). Выбранные рёбра добавляются в минимальное остовное дерево, а соответствующие фрагменты склеиваются.
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритму Борувки обладает большим потенциалом параллелизма, так как его основная операция (выбор минимального исходящего ребра во фрагменте) может исполнятся независимо для каждого фрагмента.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- C++, MPI: Parallel Boost Graph Library; функции
dense_boruvka_minimum_spanning_tree,boruvka_then_merge,boruvka_mixed_mergeсочетают алгоритм Борувки и алгоритм Крускала.
3 Литература
- ↑ Воронцов К.В. "Лекции по алгоритмам кластеризации и многомерного шкалирования"
- ↑ Borůvka, Otakar. “O Jistém Problému Minimálním.” Práce Moravské Přírodovědecké Společnosti III, no. 3 (1926): 37–58.
- ↑ Jarník, Vojtěch. “O Jistém Problému Minimálním (Z Dopisu Panu O. Borůvkovi).” Práce Moravské Přírodovědecké Společnosti 6, no. 4 (1930): 57–63.
