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

Кластеризация
Последовательный алгоритм
Последовательная сложность	[math]O(N^2\log N)[/math]
Объём входных данных	[math]N[/math]
Объём выходных данных	[math]N[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(\log N)[/math]
Ширина ярусно-параллельной формы	[math]O(N^2)[/math]

Данный документ содержит описание алгоритма кластеризации, основанного на построении минимального остовного дерева (каркаса, остова, кратчайшего незамкнутого пути, минимального покрывающего дерева, англ. Minimum Spanning Tree (MST)) - эвристического графового алгоритма построения разбиения множества объектов на такие непересекающиеся подмножества объектов, что объекты, принадлежащие одному подмножеству, схожи по заданной метрике в большей степени, чем объекты, принадлежащие разным группам.

Как и все алгоритмы кластеризации, данный алгоритм может быть применён для решения задач кластерного анализа, выделения типовых и нетипичных объектов в рассматриваемой выборке объектов. Его достоинствами по сравнению с другими аналогичными алгоритмами машинного обучения являются наглядность, идейная простота, возможность контролировать число кластеров. Главным недостатком является ограниченная применимость: алгоритм лучше всего подходит для выделения кластеров типа сгущений или лент, наличие разреженного фона или узких перемычек между кластерами может приводить к неадекватному с точки зрения аналитика результату. Другим недостатком является высокая вычислительная сложность: на выборках более 100 тыс. объектов без применения параллельных вычислений применить алгоритм невозможно. Рассмотрению соответствующих параллельных алгоритмов и посвящена данная статья.

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

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

Рассматривается выборка [math]X = \{x_i\}, i = 1, 2, \ldots, N[/math], состоящая из [math]N[/math] объектов с заданной симметричной неотрицательной функцией расстояния [math]\rho[/math]. Данную выборку можно рассматривать как связный неориентированный взвешенный граф [math]G[/math], множество вершин которого совпадает со множеством объектов выборки, веса рёбер соотвествуют значениям функции расстояния между соответсвующими вершинами.

Также должно быть задано искомое число кластеров [math]K[/math].

Рис.1. Ключевая идея алгоритма кластеризации на основе построения остовного дерева, разбиение на 3 кластера

Идея рассматриваемого алгоритма кластеризации очень проста:

• с помощью какого-либо алгоритма на определённом выше графе строится минимальное остовное дерево
• из полученного дерева выбрасывается [math]K - 1[/math] ребро с наибольшими весами, что приводит к появлению в остовном дереве [math]K[/math] компонент связности, каждая из которых объявляется кластером

Иллюстрация работы алгоритма приведена на рис. 1. В данном случае рассматриваются 13 объектов на евклидовой плоскости, построено остовное дерево, после чего из него выброшены 2 наиболее длинных ребра и получены три кластера.

Существуют различные модификации описанного алгоритма, связанные с другим алгоритмом конструирования исходного графа или условием выбрасывания рёбер из посроенного остовного дерева. Например, число [math]K[/math] может быть полезно определить не изначально, а подобрать, рассматривая отсортированную по убыванию последовательность весов рёбер в остовном дереве: если имеется резкое уменьшение весов, то можно удалить все рёбра до него. Формализацией такого подхода является алгоритм ZEMST. Однако в дальнейшем ограничимся анализом определённого выше простейшего варианта.

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

Пусть задан связный неориентированный граф на множестве объектов [math]G = (X, E)[/math] с неотрицательными весами рёбер [math]\rho(e) = \rho(x_i, x_j) \geqslant 0[/math].

Наиболее частый используемый на практике сценарий следующий:

• каждый объект описывается [math]d[/math]-мерным вектором в пространстве
• используется функция расстояния [math]\ell_p[/math]

Например, случай, когда в качестве метрики выбирается евклидова метрика [math]\ell_2[/math] в литературе называется EMST - Euclidean Minimum Spanning Tree.

Хотя в некоторых задачах возможна ситуация, когда данный граф не является полным (по каким-то причинам определены не все расстояния между вершинами), но в описанных типовых случаях граф является полным, содержит [math]\frac{N(N - 1)}{2}[/math] рёбер.

Для поиска минимального остовного дерева на практике используется следующие три похожих друг на друга алгоритма и их комбинации:

• Алгоритм Прима.

• Алгоритм Крускала;

• Алгоритм Борувки;

1.2.1 Обзор алгоритмов поиска минимального остова

Кратко опишем принцип работы каждого из этих трёх широко используемых алгоритмов поиска минимального остова. Все они основаны на стратегии жадного добравления в остов. Все они предполагают, что изначально множество рёбер в искомом остовном дереве пусто и отличаются тактикой добваления рёбер.

В алгоритме Прима рассматривается текущее остовное дерево [math]T[/math], образующих дерево. Изначально [math]T[/math] состоит из одной вершины, выбранной произвольно. Далее на каждом шаге отыскивается минимальное ребро, ровно один которого принадлежит [math]T[/math], оно добавляется в [math]T[/math] вместе со вторым своим концом. Алгоритм завершается через [math]N - 1[/math] шаг - ровно столько рёбер в дереве на [math]N[/math] вершинах. Последовательная реализация, при которой минимальное ребро на каждом шаге ищется полным перебором рёбер, исходящих из [math]T[/math], имеет сложность [math]O(N^3)[/math] на полном графе. Алгоритм можно ускорить, если поддерживать двоичное дерево поиска по рёбрам, ровно один которых принадлежит [math]T[/math]. Тогда при добавлении очередной вершины в [math]T[/math] необходимо добавить в дерево не более чем [math]N - 1[/math] новое ребро за [math]O(N \log N)[/math], а выбор минимума осуществляется за [math]O(1)[/math], итоговая сложность [math]O(N^2 \log N)[/math].

В алгоритме Крускала остов [math]T[/math] изначально пуст, и в остов на каждом шаге добавляется вместе со своими концами минимальное ребро, имеющееся в графе, не нарушающее свойства ацикличности уже выбранного на предыдущих шагах леса [math]T[/math]. Через [math]N - 1[/math] шаг лес [math]T[/math] гарантированно станет связным деревом. Если искать минимум полным перебором по [math]O(N^2)[/math] рёбрам полного графа, сложность получится [math]O(N^3)[/math]. Если же предварительно отсортировать все рёбра за [math]O(N^2 \log N^2) = O(N^2 \log N)[/math], то дальше все рёбра искомого остова можно будет добавить в процессе одного прохода по этому массиву рёбер в порядке возрастания - для каждого ребра проверяем, не нарушает ли оно свойство ацикличности [math]T[/math] и добавляем его в [math]T[/math], если не нарушает. Для того чтобы быстро проверять свойство принадлежности обоих концов графа одной из компонент [math]T[/math], используется эффективная структура данных - система непересекающихся множеств. Сложность одной такой проверки [math]O(\alpha(N))[/math], где [math]\alpha(N)[/math] - обратная функция Аккермана, значение которой не превосходит 4 примерно для [math]N \leqslant 10^{600}[/math]. Итоговая сложность такого алгоритма равна сложности сортировки и также составляет [math]O(N^2 \log N)[/math].

В алгориме Борувки, как и в алгоритме Крускала, поддерживается лес [math]T[/math]. Изначально лес состоит из [math]N[/math] изолированных вершин графа. На каждом шаге путём перебора всех рёбер графа для каждого дерева в [math]T[/math] ищется мининмальное ребро, ровно один конец которого принадлежит этому дереву. После этого все найденные рёбра добавляются в [math]T[/math]. Поскольку после каждой итерации число деревьев в лесе [math]T[/math], исходно равное [math]N[/math] уменьшается не менее чем в 2 раза, таких шагов будет произведено не более [math]\log N[/math], поэтому итоговая сложность алгоритма составляет [math]O(N^2\log N)[/math].

Таким образом, каждый из данных алгоритмов имеет сложность [math]O(N^2\log N)[/math], однако с точки зрения параллельной реализации они различаются.

1.8 Ресурс параллелизма алгоритма

Алгоритму Борувки обладает большим потенциалом параллелизма, так как его основная операция (выбор минимального исходящего ребра во фрагменте) может исполнятся независимо для каждого фрагмента.

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Как правило, в библеотеках реализуют не собственно алгоритм кластеризации с использованием остовного дерева, а только алгоритм остовного дерева, предоставляя пользователю возможность самостоятельно реализовать функции построения графа и обработки результатов работы алгоритма.

Параллельная реализация алгоритма MST:

• C++, MPI: Parallel Boost Graph Library; функции dense_boruvka_minimum_spanning_tree, boruvka_then_merge, boruvka_mixed_merge сочетают алгоритм Борувки и алгоритм Крускала.

Последовательные реализации доступны во многих библиотеках:

• NetworkX MST - реализация в библиотеке для работы с графами на Python
• Алгоритм Прима, Алгоритм Крускала - C++ реализация в boost
• Алгоритм Прима, Алгоритм Крускала - Java реализация в JGraphT