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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 37: Строка 37:
 
Выходными данными являются <math> N </math> натуральных чисел от <math> 1 </math> до <math> K </math> -- номера кластеров, в которые определена каждая вершина. При этом, каждый кластер содержит хотя бы одну вершину.
 
Выходными данными являются <math> N </math> натуральных чисел от <math> 1 </math> до <math> K </math> -- номера кластеров, в которые определена каждая вершина. При этом, каждый кластер содержит хотя бы одну вершину.
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
 
+
Чувствителен к выбросам
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 46: Строка 46:
 
== Литература ==
 
== Литература ==
 
# Euclidean minimum spanning tree, https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
 
# Euclidean minimum spanning tree, https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
 +
# Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf

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

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.2 Математическое описание алгоритма

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

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

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

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

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 Литература

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