Участник: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] с неотрицательными элементами с нулевой диагональю.

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

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

Входными данными являются число [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] -- номера кластеров, в которые определена каждая вершина. При этом, каждый кластер содержит хотя бы одну вершину.