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

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

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

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

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

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

1. Набор признаков $\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.6 Последовательная сложность алгоритма

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

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

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

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

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

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

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