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

Версия 12:49, 15 октября 2016

Содержание

1 Структура и свойства алгоритма
2 Программная реализация алгоритма
- 2.1 Масштабируемость алгоритма и его реализации
- 2.2 Существующие реализации алгоритма
3 Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

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

@@ Строка 23: / Строка 23: @@
 В данной статье рассматривается версия алгоритма с использованием алгоритма Борувки.
-В случае постановки задачи в виде набора признаков в подходящем метрическом пространстве возможна также предварительная подготовка графа, состоящая из построения триангуляции Делонэ. Так как любое минимальное остовное дерево в этом случае принадлежит триангуляции Делоне, это позволяет значительно улучшить ассимптотику алгоритма.
+В случае постановки задачи в виде набора признаков в подходящем метрическом пространстве возможна также предварительная подготовка графа, состоящая из построения триангуляции Делонэ. Так как любое минимальное остовное дерево в этом случае принадлежит триангуляции Делоне, в некоторых случаях это позволяет значительно улучшить ассимптотику алгоритма.
 === Математическое описание алгоритма ===
@@ Строка 31: / Строка 31: @@
 === Последовательная сложность алгоритма ===
 # Для построения триангуляции Делонэ существуют алгоритмы разделяй-и-властвуй, имеющие гарантированную сложность <math>O(N \log N)</math>. Кроме того, если имеется некоторая априорная информация о рассматриваемых объектах, в некоторых случаях имеются алгоритмы со средней сложностью <math>O(N)</math>;
-# Алгоритм Борувки в общем имеет <math>O(\log N)</math> шагов, а каждый шаг требует <math>O(V)</math> операций, где <math>V</math> -- число рёбер в графе. Итого <math>O(V \log N)</math> операций.
+# Алгоритм Борувки в общем имеет <math>O(\log N)</math> шагов, а каждый шаг требует <math>O(V)</math> операций, где <math>V</math> -- число рёбер в графе. Итого <math>O(V \log N)</math> операций. При использовании триангуляции Делонэ <math>V</math> имеет тот же порядок, что и <math>N</math>, поэтому общая сложность <math>O(N \log N)</math>. В общем же случае сложность составляет <math>O(N^2 \log N)</math>
+# Удаление <math>K-1</math> можно осуществить за <math>O(N)</math> операций.
+Итак, общая сложность алгоритма в общем случае <math>O(N^2 \log N)</math>.
 === Информационный граф ===
 === Ресурс параллелизма алгоритма ===