Алговики - Вклад [ru]

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

2017-02-08T04:19:26Z

Dmarkin:

{{assignment}}

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

Макроструктура алгоритма описана в пункте 1.3.
Отметим основные макрооперации, которые входят в состав алгоритма:

* Вычисление расстояний между вершинами;
* Добавление ребра в граф;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в [http://portal.tpu.ru/SHARED/a/AXOENOWSW/Publications_rus/Tab3/Tab/Гергель%20В.П.%20-%20Высокопроизводит.pdf книге]. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.

[[Файл:2017-02-08_06-56-11.png|border|мини|центр|1000px|Результаты вычислительных экспериментов для параллельного алгоритма Прима (при использовании двух и четырех вычислительных ядер) ]]

Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
# Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем

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

2017-02-08T04:14:18Z

Dmarkin:

{{assigment}}

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

Макроструктура алгоритма описана в пункте 1.3.
Отметим основные макрооперации, которые входят в состав алгоритма:

* Вычисление расстояний между вершинами;
* Добавление ребра в граф;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в [http://portal.tpu.ru/SHARED/a/AXOENOWSW/Publications_rus/Tab3/Tab/Гергель%20В.П.%20-%20Высокопроизводит.pdf книге]. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.

[[Файл:2017-02-08_06-56-11.png|border|мини|центр|1000px|Результаты вычислительных экспериментов для параллельного алгоритма Прима (при использовании двух и четырех вычислительных ядер) ]]

Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
# Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем

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

2017-02-08T04:13:10Z

Dmarkin: /* Литература */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

Макроструктура алгоритма описана в пункте 1.3.
Отметим основные макрооперации, которые входят в состав алгоритма:

* Вычисление расстояний между вершинами;
* Добавление ребра в граф;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===

Масштабируемость алгоритма Прима исследована на параллельной версии, представленной в [http://portal.tpu.ru/SHARED/a/AXOENOWSW/Publications_rus/Tab3/Tab/Гергель%20В.П.%20-%20Высокопроизводит.pdf книге]. При помощи директив OpenMP алгоритм распараллеливался по ядрам. В данном источнике представлены результаты экспериментов при использовании 2 и 4 вычислительных ядер и изменении объёма входных данных от 100 до 1000. Эксперименты проводились на двухпроцессорном вычислительном узле на базе четырехядерных процессоров Intel Xeon E5320, 1.86 ГГц, 4 Гб RAM под управлением операционной системы Microsoft Windows HPC Server 2008. Разработка программ проводилась в среде Microsoft Visual Studio 2008, для компиляции использовался Intel C++ Compiler 10.0 for Windows.

[[Файл:2017-02-08_06-56-11.png|border|мини|центр|1000px|Результаты вычислительных экспериментов для параллельного алгоритма Прима (при использовании двух и четырех вычислительных ядер) ]]

Из графика видно, что время выполнения увеличивается при увеличении объёма входных данных, но уменьшается при увеличении вычислительных ядер.

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.
# Гергель В.П. Высокопроизводительные вычисления для многоядерных многопроцессорных систем

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

2017-02-08T04:09:05Z

Dmarkin: /* Масштабируемость алгоритма и его реализации */

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

2017-02-08T03:33:22Z

Dmarkin: /* Масштабируемость алгоритма и его реализации */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

Макроструктура алгоритма описана в пункте 1.3.
Отметим основные макрооперации, которые входят в состав алгоритма:

* Вычисление расстояний между вершинами;
* Добавление ребра в граф;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
[[Файл:2017-02-08_06-22-13.png|border|мини|центр|1000px|Время работы параллельного алгоритма Прима в зависимости от числа потоков и объёма входных данных]]

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

Обсуждение участника:Dmarkin

2017-02-07T12:37:50Z

Dmarkin: /* Замечания по тексту */

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

=== Отсутствующие части ===
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)

=== Замечания по тексту ===
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил.
* В разделе 1.5 кроме псевдокода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил
* В разделе 1.9 должны быть оценки объёмов входных и выходных данных. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил

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

2017-02-07T12:37:15Z

Dmarkin: /* Макроструктура алгоритма */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

Макроструктура алгоритма описана в пункте 1.3.
Отметим основные макрооперации, которые входят в состав алгоритма:

* Вычисление расстояний между вершинами;
* Добавление ребра в граф;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

Обсуждение участника:Dmarkin

2017-02-07T12:26:56Z

Dmarkin: /* Замечания по тексту */

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

=== Отсутствующие части ===
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)

=== Замечания по тексту ===
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
* В разделе 1.5 кроме псевдокода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил
* В разделе 1.9 должны быть оценки объёмов входных и выходных данных. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил

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

2017-02-07T12:25:50Z

Dmarkin: /* Псевдокод */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

В состав алгоритма входят следующие макрооперации:

* Добавление ребра в граф;
* Вычисление расстояний между вершинами;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {} //множество ребер минимального остовного дерева объявляется пустым
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math> //расстояние до построенного дерева объявляется максимальным
<math>P(i) \gets nil</math> //вершина не имеет предков из построенного дерева
<math>D(1) \gets 0</math> //включаем вершину с номером 1 в дерево
<math>Q \gets V</math> //записываем в очередь множество всех вершин
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math> //извлекаем из очереди вершину с минимальным расстоянием до построенного дерева
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math> //добавляем выбранное ребро в дерево

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

Обсуждение участника:Dmarkin

2017-02-07T11:36:47Z

Dmarkin: /* Замечания по тексту */

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

=== Отсутствующие части ===
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)

=== Замечания по тексту ===
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
* В разделе 1.5 кроме псевдокода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
* В разделе 1.9 должны быть оценки объёмов входных и выходных данных. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK) . Исправил

Обсуждение участника:Dmarkin

2017-02-07T11:36:24Z

Dmarkin: /* Замечания по тексту */

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

=== Отсутствующие части ===
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)

=== Замечания по тексту ===
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
* В разделе 1.5 кроме псевдокода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
* В разделе 1.9 должны быть оценки объёмов входных и выходных данных. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 11:28, 6 февраля 2017 (MSK)
Исправил

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

2017-02-07T11:35:28Z

Dmarkin: /* Входные и выходные данные алгоритма */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

В состав алгоритма входят следующие макрооперации:

* Добавление ребра в граф;
* Вычисление расстояний между вершинами;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {}
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math>
<math>P(i) \gets nil</math>
<math>D(1) \gets 0</math>
<math>Q \gets V</math>
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math>
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math>

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
'''Входные данные:''' множество объектов <math>x = (x_1,...,x_N)</math>. Объём <math>O(N)</math>.

'''Выходные данные:''' множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>. Объём <math>O(N)</math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

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

2017-02-04T16:49:07Z

Dmarkin:

{{Assignment}}

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

В состав алгоритма входят следующие макрооперации:

* Добавление ребра в граф;
* Вычисление расстояний между вершинами;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {}
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math>
<math>P(i) \gets nil</math>
<math>D(1) \gets 0</math>
<math>Q \gets V</math>
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math>
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math>

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
Входные данные: множество объектов <math>x = (x_1,...,x_N)</math>.

Выходные данные: множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

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

2017-02-04T16:32:30Z

Dmarkin: /* Свойства алгоритма */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

В состав алгоритма входят следующие макрооперации:

* Добавление ребра в граф;
* Вычисление расстояний между вершинами;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {}
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math>
<math>P(i) \gets nil</math>
<math>D(1) \gets 0</math>
<math>Q \gets V</math>
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math>
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math>

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
Входные данные: множество объектов <math>x = (x_1,...,x_N)</math>.

Выходные данные: множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>.

=== Свойства алгоритма ===
* Алгоритм останавливается за конечное число шагов, поскольку на каждом шаге становится по крайней мере на один фрагмент меньше.
* Число фрагментов на каждом шаге уменьшается как минимум вдвое, так что общее число шагов составляет не более <math>\log_2 N</math>.
* Соотношение последовательной и параллельной сложности: <math> \frac{N^2 \log N} {N \log N} = N </math>.
* Вычислительная мощность: <math> \frac {N^2 \log N} {N} = N \log N</math>.
* Алгоритм детерминирован. Если случается, что имеются два ребра <math>(x_i,x_j)</math> и <math>(x_l,x_m)</math>, такие что <math>d(x_i,x_j) = d(x_l,x_m)</math>, то алгоритм должен выбрать ребро, одна из вершин которого имеет минимальный индекс <math>\min(i,j,l,m)</math>, если эти два ребра выходят из одной вершины, индекс которой является минимальным (например, <math>i=l</math> ), то выбирается ребро, вершина которого имеет наименьший индекс из двух других вершин <math>\min(j,m)</math>.

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

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

2017-02-03T12:45:34Z

Dmarkin: /* Литература */

'''Автор описания:''' [[Участник:Dmarkin | Маркин Дмитрий Валерьевич, группа 611]]
== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

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

Алгоритм кластеризации на <math>K</math> кластеров, основанный на построении минимального остовного дерева (<math>MST</math>):
#По исходным данным строится граф. Каждый объект представляется в виде вершины графа, каждые две вершины соединяются ребром. Вычисляется вес ребра при помощи выбранной метрики (например, евклидовой);
#Для полученного графа строится минимальное остовное дерево при помощи одного из алгоритмов (наиболее распространены: [[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]])
#Удаляется <math>K-1</math> ребро минимального остовного дерева с максимальным весом и получаются k компонент связности.

=== Математическое описание алгоритма ===
Имеем <math>N</math> объектов <math>x</math>, которые представляют собой элемент метрического пространства с метрикой <math>d(x_i,x_j)=\sqrt{\sum^{n}_{k=1} {(x_{ik}-x_{jk})^2}}</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>K-1</math> ребро, и дерево распадается на поддеревья <math>MST_i</math>, вершины которых объявляются принадлежащими кластеру с номером <math>i</math>.

=== Вычислительное ядро алгоритма ===

Алгоритм состоит из трёх независимых шагов:

#Построение графа и вычисление расстояний. Сложность <math>O(N^2)</math>;
#Построение минимального покрывающего дерева при помощи одного из наиболее распространенных методов ([[Алгоритм Крускала | Алгоритм Крускала]], [[Алгоритм Борувки | Алгоритм Борувки]], [[Алгоритм Прима | Алгоритм Прима]]). Сложность <math> O(N^2 \log N) </math>;
#Разбиение на кластеры. Сложность в худшем случае <math>O(N)</math>.

Отсюда следует, что вычислительным ядром алгоритма является этап построения минимального покрывающего дерева, поскольку он имеет наибольшую сложность.

=== Макроструктура алгоритма ===

В состав алгоритма входят следующие макрооперации:

* Добавление ребра в граф;
* Вычисление расстояний между вершинами;
* Нахождение минимального покрывающего дерева, что является вычислительным ядром алогоритма;
* Удаление ребра из графа.

=== Схема реализации последовательного алгоритма ===

==== Обозначения ====

* <math>D(i) </math> — расстояние от <math>i</math>-й вершины до построенного дерева;
* <math>P(i) </math> — предок <math>i</math>-й вершины, то есть такая вершина <math>u</math>, что <math>(u,i)</math> легчайшее из всех рёбер, соединяющее <math>i</math> с вершиной из построенного дерева;
* <math>W(i,j)</math> — вес ребра <math>(i,j)</math>;
* <math>Q</math> — приоритетная очередь вершин графа, где ключ — <math>D(i)</math>;
* <math>T</math> — множество ребер минимального остовного дерева.

==== Псевдокод ====

<math>T \gets </math> {}
Для каждой вершины <math> i \in V </math>
<math>D(i) \gets \infty </math>
<math>P(i) \gets nil</math>
<math>D(1) \gets 0</math>
<math>Q \gets V</math>
Пока <math>Q </math> не пуста
<math>v \gets\ Extract.min(Q) </math>
Для каждой вершины <math>u</math> смежной с <math>v</math>
Если <math>u \in Q</math> и <math>W(v,u) < D(u)</math>
<math>D(u) \gets W(v,u)</math>
<math>P(u) \gets v</math>
<math>v \gets Extract.Min(Q)</math>
<math>T \gets T+(P(v),v)</math>

=== Последовательная сложность алгоритма ===

Последовательная сложность определяется суммой сложностей трёх основных этапов:

<math>T(N) = O(N^2) + O(N^2 \log N) + O(N) = O(N^2 \log N)</math>

=== Информационный граф ===
[[Файл:15.png|border|мини|центр|1000px|Информационный граф параллельного алгоритма построения минимального покрывающего дерева]]
=== Ресурс параллелизма алгоритма ===

Рассмотрим основные свойства задачи:
*'''Схлопывание фрагментов'''. Пусть <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>MSF(E)</math> – минимальный остовный лес графа с рёбрами <math>E</math>. Тогда:<math>
MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)).
</math>
*'''Минимальное ребро фрагмента'''. Пусть <math>F</math> – фрагмент минимального остовного дерева и <math>e_F</math> – ребро наименьшего веса, исходящее из <math>F</math> (т.е. ровно один его конец является вершиной из <math>F</math>). Если ребро <math>e_F</math> единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны [[алгоритм Борувки]] и [[алгоритм Прима]].

Ресурс параллелизма основан на следующих возможностях:
# Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
# Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
# Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.

Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую параллельную сложность <math>O(N \log N)</math>. Например, '''[[Алгоритм GHS]]''' (Gallager, Humblet, Spira) является распределённым вариантом алгоритма Борувки. Последующие версии этого алгоритма имеют более низкую параллельную сложность.

=== Входные и выходные данные алгоритма ===
Входные данные: множество объектов <math>x = (x_1,...,x_N)</math>.

Выходные данные: множество кластеров <math>Clust = (Clust_1,...,Clust_K)</math>, где <math>Clust_i = (x_{i,1},..., x_{i, N_i}), x_{i, l} \ne x_{j, m}, i \ne j, \forall l</math> и <math>m, \sum_{i=1}^K {N_i} = N </math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
*[https://github.com/jakevdp/mst_clustering Python: MST Clustering]
*[http://www.boost.org/doc/libs/1_62_0/libs/graph_parallel/doc/html/index.html С++: Parallel boost graph library]
*[http://www.boost.org/doc/libs/1_53_0/libs/graph_parallel/doc/html/dehne_gotz_min_spanning_tree.html C++: Minimum Spanning Tree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/PrimMinimumSpanningTree.html Java: JGraphT PrimMinimumSpanningTree]
*[http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html Java: JGraphT KruskalMinimumSpanningTree]
*[http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html Python: SciPy]
*[https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.mst.html Python: NetworkX]

== Литература ==
# Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.
# Нейский И.М. Классификация и сравнение методов кластеризации
# C. Kingsford. Minimum Spanning Trees & Clustering
# Y. Zhou et al. Clustering with Minimum Spanning Trees
# Gallager, Robert G, P A Humblet, and P M Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (1983): 66–77. doi:10.1145/357195.357200.
# Gafni, Eli. “Improvements in the Time Complexity of Two Message-Optimal Election Algorithms,” 175–85, New York, New York, USA: ACM Press, 1985. doi:10.1145/323596.323612.
# Awerbuch, B. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” 230–40, New York, New York, USA: ACM Press, 1987. doi:10.1145/28395.28421.

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

2017-02-03T12:36:08Z

Dmarkin: /* Существующие реализации алгоритма */

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

2017-02-03T10:18:50Z

Dmarkin: /* Входные и выходные данные алгоритма */

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

2017-02-02T21:44:34Z

Dmarkin: /* Входные и выходные данные алгоритма */

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

2017-02-02T21:16:39Z

Dmarkin: /* Общее описание алгоритма */

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

2017-02-02T21:16:08Z

Dmarkin: /* Вычислительное ядро алгоритма */

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

2017-02-02T21:15:35Z

Dmarkin: /* Последовательная сложность алгоритма */

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

2017-02-02T21:14:54Z

Dmarkin: /* Ресурс параллелизма алгоритма */

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

2017-02-02T21:12:41Z

Dmarkin: /* Ресурс параллелизма алгоритма */

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

2017-02-01T19:28:49Z

Dmarkin: /* Ресурс параллелизма алгоритма */

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

2017-01-31T22:16:45Z

Dmarkin:

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

2017-01-29T08:53:32Z

Dmarkin:

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

2017-01-29T08:52:44Z

Dmarkin:

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

2017-01-29T08:52:20Z

Dmarkin:

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

2017-01-20T13:33:27Z

Dmarkin: /* Последовательная сложность алгоритма */

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

2017-01-20T11:49:52Z

Dmarkin: /* Схема реализации последовательного алгоритма */

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

2017-01-20T02:12:01Z

Dmarkin: /* Псевдокод */

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

2017-01-19T22:07:45Z

Dmarkin: /* Схема реализации последовательного алгоритма */

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

2017-01-19T21:25:21Z

Dmarkin: /* Схема реализации последовательного алгоритма */

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

2017-01-19T19:18:21Z

Dmarkin:

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

2017-01-19T19:14:27Z

Dmarkin:

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

2017-01-19T19:00:25Z

Dmarkin: /* Схема реализации последовательного алгоритма */

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

2017-01-19T18:36:22Z

Dmarkin:

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

2017-01-19T18:24:43Z

Dmarkin:

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

2017-01-19T17:43:40Z

Dmarkin: /* Обозначения */

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

2017-01-19T17:24:38Z

Dmarkin: /* Обозначения */

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

2017-01-19T17:21:10Z

Dmarkin:

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

2017-01-19T17:10:34Z

Dmarkin: /* Обозначения */

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

2017-01-19T17:00:49Z

Dmarkin:

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

2017-01-19T15:07:04Z

Dmarkin:

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

2017-01-19T14:05:47Z

Dmarkin:

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

2017-01-19T14:04:21Z

Dmarkin: /* Вычислительное ядро алгоритма */

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

2017-01-19T13:56:27Z

Dmarkin:

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

2017-01-19T13:53:25Z

Dmarkin:

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

2017-01-19T13:46:24Z

Dmarkin:

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

2017-01-19T13:43:42Z

Dmarkin: