Участник:Tereshinvs/MST Clusterization: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 74: Строка 74:
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
 
Основным местом для распараллеливания алгоритма является поиск наименьшего ребра из одной компоненты связности в другие. Так как компоненты связности в данном случае независимы, то отдельные узлы вычислительной системы могут выполнять поиск наименьших рёбер независимо.
 
Основным местом для распараллеливания алгоритма является поиск наименьшего ребра из одной компоненты связности в другие. Так как компоненты связности в данном случае независимы, то отдельные узлы вычислительной системы могут выполнять поиск наименьших рёбер независимо.
 +
 +
Узким местом является нахождение k-ой порядковой статистики для выделения кластеров, а так же объединение компонент связности. Но всего объединений компонент связности <math>N-1</math>, поэтому при его реализации с помощью структуры данных система непересекабщихся множеств с ранговой эвристикой общая сложность за всё время работы алгоритма будет близко к <math>O(N)</math>.
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 
Входными данными являются число <math> N </math> (количество элементов рассматриваемого множества) и матрица вещественных чисел размера <math> N \times N </math> отношений между элементами этого множества. Матрица предполагается симметричной, а её диагональные элементы равными нулю, поэтому её размер можно оценить как <math> \tfrac{N(N-1)}{2} </math>.
 
Входными данными являются число <math> N </math> (количество элементов рассматриваемого множества) и матрица вещественных чисел размера <math> N \times N </math> отношений между элементами этого множества. Матрица предполагается симметричной, а её диагональные элементы равными нулю, поэтому её размер можно оценить как <math> \tfrac{N(N-1)}{2} </math>.

Версия 14:03, 15 октября 2016

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

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

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

Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах.

Постановка задачи также может различаться характером входных данных:

  1. Набор признаков V = \left\{ v_1, v_2, \ldots, v_N \right\} в некотором метрическом пространстве с метрикой \rho(x, y)
  2. Матрица отношений между объектами: симметричная матрица вещественных чисел размером N \times N с неотрицательными элементами с нулевой диагональю.

В данной статье рассматривается постановка с известным количеством кластеров K .

Алгоритмы кластеризации делятся на два вида: иерархические и неиерархические. Иерархические алгоритмы строят большие кластеры из меньших или разделяют большие на меньшие, а неиерархические заключаются в минимизации некоторой функции. Примерами неиерархических алгоритмов являются алгоритм k-средних, PAM, CLOPE, LargeItem и т.д., а иерархических -- CURE, ROCK, Chameleon, BIRCH и рассматриваемый в данной статье алгоритм MST (Minimum spanning tree -- минимальное остовное дерево).

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

Общая схема алгоритма:

  1. Построение минимального остовного дерева одним из известных методов (алгоритмы Крускала, Прима, Борувки и их комбинации; наиболее пригодным для параллельного исполнения считается алгоритм Борувки)
  2. Удаление K-1 самых длинных рёбер из минимального остовного дерева.

В данной статье рассматривается версия алгоритма с использованием алгоритма Борувки.

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

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

Пусть V — множество объектов, Y — множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами \rho(x,y). Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике \rho, а объекты разных кластеров существенно отличались. При этом каждому объекту v_i\in V приписывается номер кластера y_i.

Алгоритм кластеризации — это функция a\colon V\to Y, которая любому объекту v\in V ставит в соответствие номер кластера y\in Y. Множество Y в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

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

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

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

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

Основной алгоритм можно разделить на следующие части:

  1. Нахождение для каждой вершины наименьшего ребра, инциндентного ней
  2. Добавление найденных наименьших вершин в MST
  3. <<Склейка>> компонент связности MST
  4. Нахождение веса W_{K-1} (K-1)-ого наибольшего ребра
  5. Удаление рёбер весом не меньше чем W_{K-1}.

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

 0   Ввод: граф V
 1 
 2   Поместить каждую вершину в отдельное дерево леса T
 3   Пока в T больше одной компоненты связности:
 4     Для каждой компоненты C из T:
 5       S -- пустое множество рёбер
 6       Для каждой вершины v в C:
 7         Найти кратчайшее ребро с одним концом v, а другим не из C, и поместить его в S
 8       Добавить кратчайшее ребро из S в T
 9     Объединить компоненты связности
10   T -- MST
11   
12   Найти W -- вес (K-1)-ого максимального ребра в T
13   Удалить из T рёбра с весом большим или равным W
14 
15   Пронумеровать компоненты связности
16 
17   Вывод: номера компонент связности для каждой вершины

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

  1. Алгоритм Борувки в общем имеет O(\log N) шагов, а каждый шаг требует O(V) операций, где V -- число рёбер в графе. Итого O(V \log N) операций. При использовании триангуляции Делонэ V имеет тот же порядок, что и N, поэтому общая сложность O(N \log N). В общем же случае сложность составляет O(N^2 \log N)
  2. Удаление K-1 рёбер можно осуществить за O(N) операций.

Итак, общая сложность алгоритма в общем случае O(N^2 \log N).

1.7 Информационный граф

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

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

Узким местом является нахождение k-ой порядковой статистики для выделения кластеров, а так же объединение компонент связности. Но всего объединений компонент связности N-1, поэтому при его реализации с помощью структуры данных система непересекабщихся множеств с ранговой эвристикой общая сложность за всё время работы алгоритма будет близко к O(N).

1.9 Входные и выходные данные алгоритма

Входными данными являются число N (количество элементов рассматриваемого множества) и матрица вещественных чисел размера N \times N отношений между элементами этого множества. Матрица предполагается симметричной, а её диагональные элементы равными нулю, поэтому её размер можно оценить как \tfrac{N(N-1)}{2} .

Кроме того, имеется натуральное число K \leqslant N -- требуемое количество кластеров.

Выходными данными являются N натуральных чисел от 1 до K -- номера кластеров, в которые определена каждая вершина. При этом, каждый кластер содержит хотя бы одну вершину.

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

Чувствителен к выбросам

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

2.1 Масштабируемость алгоритма и его реализации

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

3 Литература

  1. Euclidean minimum spanning tree, https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
  2. Нейский И.М. Классификация и сравнение методов кластеризации, http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf