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

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

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

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

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

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

1. Набор признаков [math]\displaystyle{ V = \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] самых длинных рёбер из минимального остовного дерева.

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

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

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

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

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

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

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

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

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

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

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

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

  Ввод: граф V

  Поместить каждую вершину в отдельное дерево леса T
  Пока в T больше одной компоненты связности:
    Для каждой компоненты C из T:
      S -- пустое множество рёбер
      Для каждой вершины v в C:
        Найти кратчайшее ребро с одним концом v, а другим не из C, и поместить его в S
      Добавить кратчайшее ребро из S в T
    Объединить компоненты связности
  T -- MST
  
  Найти W -- вес (K-1)-ого максимального ребра в T
  Удалить из T рёбра с весом большим или равным W

  Пронумеровать компоненты связности

  Вывод: номера компонент связности для каждой вершины

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

1. Нахождение ребер наименьшего веса для всех компонент связности требует [math]\displaystyle{ O(V) }[/math] операций на каждом шаге, где [math]\displaystyle{ V }[/math] -- число рёбер в графе.
2. Добавление новых рёбер в MST требует [math]\displaystyle{ O(N) }[/math] операций за всё время работы алгоритма.
3. При использовании структуры данных система непересекающихся множеств с ранговой эвристикой, объединение деревьев требует примерно , где [math]\displaystyle{ O(N) }[/math] операций.
4. Доказано, что количество шагов алгоритма [math]\displaystyle{ O(\log N) }[/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]

Удаление [math]\displaystyle{ K-1 }[/math] рёбер можно осуществить за [math]\displaystyle{ O(N) }[/math] операций.

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

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

Информационный граф алгоритма кластеризации на основе минимального остовного дерева

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

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

Узким местом является нахождение k-ой порядковой статистики для выделения кластеров, а так же объединение компонент связности. Но всего объединений компонент связности [math]\displaystyle{ N-1 }[/math], поэтому при его реализации с помощью структуры данных система непересекабщихся множеств с ранговой эвристикой общая сложность за всё время работы алгоритма будет близко к [math]\displaystyle{ O(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