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

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

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

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

Таким образом, на начальном этапе решения задачи имеются набор тестовых примеров [math]X=\{x_1...x_n\}[/math], а также функция расстояния между ними [math]w(e)[/math]. При этом метрика выбирается исходя из требований задачи, но наиболее распространенные - это Евклидово расстояние, квадрат Евклидова расстояния, манхэттенская метрика, расстояние Чебышева и степенное расстояние. Далее необходимо применить один из алгоритмов кластеризации, которые можно разделить на две категории: иерархические, состоящие в последовательном поиске кластеров из уже найденных кластеров, а также неирархические, цель которых состоит в минимизации некоторой целевой функции. К последней группе относятся такие алгоритмы, как алгоритм k-средних, алгоритм EM, нечеткие алгоритмы, а также алгоритмы теории графов, к категории которых относится алгоритм, описываемый в данной статье.

Рассмотрим алгоритм кластеризации на k кластеров, основанный на построении минимального остовного дерева (MST) состоит в следующем:

1. По исходным данным строится взвешенный неориентированный граф: каждый объект представляется в виде вершины графа, а вес ребра, связывающего две вершины, есть расстояние между объектами в выбранной заранее метрике
2. Для полученного графа строится минимальное остовное дерево, то есть дерево, содержащее все вершины графа и имеющее минимальный суммарный вес своих ребер
3. Удаляется k-1 ребро минимального остовного дерева с максимальным весом
4. Получаются k компонент связности, которые интерпретируются как кластеры

Для построения минимального остовного дерева могут быть использованы различные алгоритмы, среди которых наиболее распространены:

1. Алгоритм Крускала
2. Алгоритм Борувки
3. Алгоритм Прима

Отметим, что в рамках проведенного исследования использовался алгоритм Крускала, наиболее подробно изучить который можно, пройдя по ссылке [Алгоритм Крускала], поэтому в данной статье его описание не приводится.

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

По исходным данным формируется граф [math]G = (V, E)[/math], являющийся неориентированным, взвешенным, связным и не имеющим кратных ребер. Пусть полученный граф содержит [math] |V|[/math] вершин и [math]|E|[/math] ребер. Предполагая, что каждый объект можно сравнить с каждым, можно считать, что получаемый граф является полным, а значит число ребер может быть оценено следующим образом: [math]|E|=\frac{|V|(|V|-1)}{2} \le \frac{|V|^2}{2}-\frac{|V|}{2} \Rightarrow O(E)=O(V^2)[/math]

Обозначим в виде [math]w(u,v)[/math] вес ребра, соединяющего вершины [math]u[/math] и [math]v[/math]. Тогда граф может быть задан в виде списка ребер, а именно списка троек: [math](u,v,w(u,v))[/math], что является более удобным представлением графа для реализации многих алгоритмов по сравнению с матрицей смежности. Помимо этого, данный способ помогает сэкономить память. Недостатков указанного подхода является только то, что установить, с какими вершинами связана интересующая вершина, а также вес соответствующих ребер является весьма затруднительно. Однако для решения поставленной задачи нам это и не потребуется.

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

1. Построение графа путем задания матрицы связности. В общем случае, когда задано некоторое множество объектов, для построения графа может быть использован алгоритм, позволяющий рассчитать расстояние от каждого объекта до каждого за операций, где число объектов (вообще говоря, данная операция требует операций, где E - число ребер в графе, но в нашем случае число ребер подразумевается равным , D - плотность графа). Однако в рамках данного исследования для тестирования алгоритма использовалась такая технология построения графов, когда в качестве веса каждого ребра назначается некоторое произвольное число из заданного промежутка (например, от 1 до 1000), что также требует
2. Построение минимального остовного дерева на основании полученного ранее графа, для чего может быть использован один из известных и наиболее распространенных алгоритмов (алгоритм Крускала, алгоритм Борувки или алгоритм Прима). Рассмотрим, например, алгоритм Крускала. На начальном этапе имеется граф, состоящий из вершин - объектов исходной выборки и не содержащий ребер, следовательно, каждая из вершин изначально представляет собой компоненту связности и даже дерево. Алгоритм состоит в выборе на каждом шаге ребра с минимальным весом и добавлении его в дерево, если оно соединяет два дерева. Алгоритм будет работать максимально эффективно, если изначально ребра графа, полученного на первом шаге будут отсортированы (например, по возрастанию).
3. Наконец, для получения k необходимо удалить из получившегося минимального остовного дерева k-1 ребро с максимальным весом. В частности, в случае, если на предыдущем шаге мы пользовались алгоритмом Крускала для построения MST, ребра получившегося дерева отсортированы по возрастанию, значит для удаления указанных выше ребер потребуется лишь O(1) операций

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

Приведем здесь псевдокод основной части алгоритма - а именно построения локального минимального остовного дерева при помощи алгоритма Крускала.

Kruskal ( G=(V,E) ):

1. mst = ∅;

2. сортировать E по возрастанию;

3. для каждой вершины v из множества вершин V:

4. MakeSet(v);

5. для каждого ребра e = (u, v) из множества ребер E:

6. if Find(u) ≠ Find(v):

7. mst = mst ∪ { (u,v) };

8. Union(u, v);

9. return mst;

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

Сперва оценим последовательную сложность составных частей алгоритма.

0. O(V): Формирование графа

1. O(1): Инициализация пустого множества.

2. O(E·log(E)): сортировка ребер из множества E.

3. O(V): Инициализация одноточечного множества для каждой вершины из V.

4. ▲ MakeSet за O(1).

5. O(E·log(V)): Операции Union и Find для каждого ребра из E.

6. ▲ Find за O(1).

7. ▲ Присоединение элемента за O(1).

8. ▲ Union за O(log(V)).

9. O(1): Удаление k-1 ребра для получения k компонент связности

10. O(1): Return.

Таким образом, с учетом того, что, получаем:

T( G = (V, E) ) = O(1) + O(E·log(E)) + O(V) + O(E·log(V)) = O(E·log(E)) + O(E·log(V)) = O(E·log(V)) + O(E·log(V))

Итак, оценка сложности алгоритма есть T( G = (V, E) ) = O(E·log(V)) + O(E·log(V))

1.8 Источник параллелизма

Описанный алгоритм позволяет произвести распараллеливание, источник которого будет описан в данном пункте. Прежде всего, необходимо отметить, что данный алгоритм допускает преобразование в гибридную параллельную версию, а именно версию с использованием технологий MPI и OpenMP.

В том случае, когда все объекты заранее известны, и между ними можно рассчитать все попарные расстояния, первый шаг - построение графа - позволяет произвести распараллеливание при помощи обеих вышеуказанных технологий, а именно: разделим объекты между процессами при помощи MPI, а внутри каждой из полученных групп будем рассчитывать попарные расстояния параллельно на нескольких ядрах, использовав технологию OpenMP. Однако в данном исследовании кластеризуемые объекты предполагались заранее неизвестными, так как попарные расстояния между объектами задаются случайным образом, а это означает, что произвести распараллеливание этого шага, которое бы дало хотя бы небольшое ускорение (уменьшение времени работы), не получится.

Если все же объекты заранее были известны, можно сохранить полученную на предыдущем этапе группировку их на отдельные процессы и внутри каждого произвести сортировку расстояний между объектами по возрастанию при помощи алгоритма QSort с использованием технологии OpenMP (в противном случае параллельная структура алгоритма поддерживается начиная с этого шага).

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

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

Оценим вычислительную мощность алгоритма в том случае, когда для его реализации используется процессов. Предположим, что алгоритм реализован при помощи первой стратегии (см. выше) и применяется к графу , тогда:

• Ввод данных: - в среднем столько ребер содержит получаемый каждым процессом связный подграф
• Вывод данных: - каждый из процессов должен вывести посчитанное локальное минимальное дерево, которое содержит указанное количество ребер, так как остальные ребра, изначально входившие в состав подграфа, не будут входит в локальное MST
• Вычисление: для вычисления локального MST каждому из процессов требуется операций

Таким образом, искомое соотношение может быть записано в следующем виде:

На основании полученной формулы можно сделать несколько выводов:

1. так алгоритм сильно зависит от входных данных, с увеличением плотности графа данное соотношение увеличивается, то есть чем более плотным является граф, тем меньшее влияние на время работы алгоритма влияет вычислительная часть
2. следует рационально выбирать количество используемых процессов, так как в случае, если число выбрано слишком большим, время, отводимое на коммуникацию, может превысить время, требуемое для проведение вычислений
3. аналогичное соотношение можно вычислить и в тех случаях, когда применяются вторая и третья описанные выше стратегии. Читателю предлагается самостоятельно вычислить соответствующие соотношения. Заметим только, что исходя из соображений, на основании которых были построены стратегии, время, требуемое для осуществления коммуникаций снизится

Используемые обозначения и структуры данных

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

1. операция MakeSet(v) генерирует дерево (множество) для вершины графа, являющейся корнем искомого дерева
2. операция Find(v) определяет, которому из деревьев принадлежит интересующая вершина . Условимся, что данная операция возвращает ту вершину, которая является корнем искомого дерева
3. операция Union(u,v) объединяет два множества (два дерева, содержащих соответствующие вершины) под одним корнем

КАК ЛУЧШЕ РАЗДЕЛИТЬ ГРАФ:

Наивный подход к разделению графа на подграфы, которые будут обрабатываться различными процессами, а именно обычное разделение входных данных на несколько подгрупп может не дать желаемых результатов в увеличении производительности алгоритма, так как, вообще говоря, при вычислении каждого локального минимального остовного дерева будет удалено незначительное количество ребер (например, потому, что многие ребра будут принадлежать различным компонентам связности, что приведет к отсутствию циклов, а значит и отсутствию необходимости удалять какие-либо ребра).

Правильный подход к разделению графа на подграфы состоит в том, чтобы каждая из подзадач имела в качестве входных данных связный подграф исходного графа, состоящий из вершин и соединяющих их ребер.

Оценка прироста производительности параллельного алгоритма по сравнению с последовательным. Наиболее простой способ оценить прирост производительности – использовать закон Амдала, который гласит, что прирост может быть оценен следующим образом:

Где f – часть алгоритма, которая не может быть распараллелена, p – число процессов.

В наиболее тривиальном случае (первая стратегия распараллеливания) распараллеливанию не подлежит считывание входных данных и их разделение между процессами, а также объединение локальных MST в одно. Поэтому сложность последовательной части программы может быть оценена следующим образом: . Распараллеливанию подлежит инициализация подграфов при помощи операции MakeSet за , сортировка ребер по возрастанию внутри каждой группы за , а также построение локальных минимальных остовных деревьев за аналогичное время. Поэтому сложность параллельной части алгоритма может быть оценена так: . Таким образом, вычислив отношение сложностей частей программы, получаем, что . Устремим число процессов к бесконечности и получим, что максимальное ускорение, которое можно получить путем распараллеливания алгоритма есть 2,27. К сожалению, данная оценка не является точной. Для того, чтобы оценить прирост производительности более качественно, произведем анализ временных диаграмм программы.

Обозначим за – время, которое требуется для того, чтобы разделить граф на подграфы, – суммарное время вычислений, – время обратной пересылки локально полученных результатов, – задержка одной пересылки. Причем можно убедиться в том, что , также известно, что (время выполнения последовательного кода).

Произведем анализ первой (наивной) стратегии распараллеливания программы. На временной диаграмме жирным обозначен критический путь, время выполнения которого может быть вычислено по формуле:

Тогда максимальное ускорение для одного процесса есть:

А в случае n процессов:

Теперь проанализируем вторую стратегию, основная задача которой – уменьшить объем коммуникаций между процессами за счет того, что файл с исходными данными теперь доступен всем процессам. Помимо этого введем в рассмотрение новую величину – время, требующееся на инициализацию множеств вершин. Тогда для одного процесса , а максимальное ускорение в случае n процессов есть:

Наконец, проанализируем третью стратегию, основная цель которой – оптимизировать процесс слияния локальных минимальных остовных деревьев, а также привлечь все активные процессы (включая главный) к процессу построения локального MST. В этом случае время выполнения параллельной части программы с использованием лишь одного процесса: , а суммарное ускорение в общем случае:

На рисунке ниже приведены графики, отражающие зависимость получаемых возможных ускорений в зависимости от числа задействованных процессов, посчитанные с использованием четырех различных подходов.

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

2.3 Возможные способы и особенности параллельной реализации алгоритма

Необходимо отметить, что несмотря на всю простоту идеи распараллеливания алгоритма, описанную выше, существует несколько стратегий реализовать ее на практике. При этом, как будет показано далее, указанные стратегии дают различные приросты в производительности. Перечислим некоторые из них:

1. первая стратегия, наиболее очевидная, состоит в том, чтобы в самом начале главный процесс считал данные о ребрах и распределил считанную информацию между остальными процессами, причем каждый из них не имеет доступа к файлу с данными. Далее каждый из процессов рассчитывает локальное минимальное остовное дерево и передает его обратно главному процессу, который объединяет деревья в одно, глобальное
2. вторая стратегия во многом напоминает первую, но основное различие между ними состоит в том, что во втором случае файл с исходными данными не разделяется между процессами, а является доступным для каждого из них в полном объеме. Таким образом, каждый процесс способен считать данные о ребрах, за которые они отвечают, самостоятельно, что значительно снижает объем коммуникации между процессами. Также еще одно улучшение состоит в том, что теперь главный процесс не простаивает во время работы остальных, а, как и остальные, рассчитывает локальное минимальное остовное дерево
3. наконец, третья стратегия состоит в том, чтобы оптимизировать процесс слияния локальных минимальных остовных деревьев. Предлагается сделать так, чтобы не только главный процесс занимался слиянием, но каждый процесс участвует в процессе слияния. Для того, чтобы добиться максимальной эффективности будем предполагать, что число процессов . В этом случае потребуется шагов, чтобы выполнить слияние. На каждом шаге половина активных процессов пересылает свое локальное дерево процессу с меньшим номером на единицу, а другая половина занимается приемом и слиянием. Таким образом, через шагов главный процесс, который имеет номер 0, будет иметь в своем распоряжении глобальное минимальное остовное дерево.