Участник:Tereshinvs/MST Clusterization

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Для построения триангуляции Делонэ существуют алгоритмы разделяй-и-властвуй, имеющие гарантированную сложность [math]O(N \log N)[/math]. Кроме того, если имеется некоторая априорная информация о рассматриваемых объектах, в некоторых случаях имеются алгоритмы со средней сложностью [math]O(N)[/math];
2. Алгоритм Борувки в общем имеет [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]
3. Удаление [math]K-1[/math] рёбер можно осуществить за [math]O(N)[/math] операций.

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

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 Свойства алгоритма

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

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