Участник:Tereshinvs/MST Clusterization: различия между версиями
(Новая страница: « == Структура и свойства алгоритма == === Общее описание алгоритма === === Математическое опис…») |
|||
| Строка 3: | Строка 3: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| + | Кластеризация -- это задача статистического анализа, состоящая в разбиении множества объектов на группы, называемые кластерами, внутри которых объекты обладают похожими свойствами (чаще всего, это означает близость относительно заданной метрики). Изначально группы неизвестны, в зависимости от постановки задачи может быть также известно или неизвестно общее число кластеров. | ||
| + | |||
| + | Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах. | ||
| + | |||
| + | Постановка задачи также может различаться характером входных данных: | ||
| + | # Набор признаков <math> \left\{ v_1, v_2, \ldots, v_N \right\} </math> в некотором метрическом пространстве с метрикой <math> \rho(x, y) </math> | ||
| + | # Матрица отношений между объектами: симметричная матрица вещественных чисел размером <math> N \times N </math> с неотрицательными элементами с нулевой диагональю. | ||
| + | |||
| + | Алгоритмы кластеризации делятся на два вида: иерархические и неиерархические. Иерархические алгоритмы строят большие кластеры из меньших или разделяют большие на меньшие, а неиерархические заключаются в минимизации некоторой функции. Примерами неиерархических алгоритмов являются алгоритм k-средних, PAM, CLOPE, LargeItem и т.д., а иерархических -- CURE, ROCK, Chameleon, BIRCH и рассматриваемый в данной статье алгоритм MST (Minimal spanning tree -- минимальное остовное дерево). | ||
| + | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| Строка 23: | Строка 33: | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| + | |||
| + | == Литература == | ||
Версия 12:10, 15 октября 2016
Содержание
- 1 Структура и свойства алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Структура и свойства алгоритма
1.1 Общее описание алгоритма
Кластеризация -- это задача статистического анализа, состоящая в разбиении множества объектов на группы, называемые кластерами, внутри которых объекты обладают похожими свойствами (чаще всего, это означает близость относительно заданной метрики). Изначально группы неизвестны, в зависимости от постановки задачи может быть также известно или неизвестно общее число кластеров.
Спектр применений кластерного анализа очень широк: его используют в археологии, медицине, психологии, химии, биологии, государственном управлении, филологии, антропологии, маркетинге, социологии и других дисциплинах.
Постановка задачи также может различаться характером входных данных:
- Набор признаков [math] \left\{ v_1, v_2, \ldots, v_N \right\} [/math] в некотором метрическом пространстве с метрикой [math] \rho(x, y) [/math]
- Матрица отношений между объектами: симметричная матрица вещественных чисел размером [math] N \times N [/math] с неотрицательными элементами с нулевой диагональю.
Алгоритмы кластеризации делятся на два вида: иерархические и неиерархические. Иерархические алгоритмы строят большие кластеры из меньших или разделяют большие на меньшие, а неиерархические заключаются в минимизации некоторой функции. Примерами неиерархических алгоритмов являются алгоритм k-средних, PAM, CLOPE, LargeItem и т.д., а иерархических -- CURE, ROCK, Chameleon, BIRCH и рассматриваемый в данной статье алгоритм MST (Minimal spanning tree -- минимальное остовное дерево).
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] -- номера кластеров, в которые определена каждая вершина. При этом, каждый кластер содержит хотя бы одну вершину.
