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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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