Кластерный анализ

Алгоритм минимального покрывающего дерева

 
Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом. На рисунке изображено минимальное покрывающее дерево, полученное для девяти объектов. 
 
 
 
Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: {А, B, C} и {D, E, F, G, H, I}. Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам. 
 

Послойная кластеризация

 
Алгоритм послойной кластеризации основан на выделении связных компонент графа на некотором уровне расстояний между объектами (вершинами). Уровень расстояния задается порогом расстояния c. Например, если расстояние между объектами  , то  . 
 
Алгоритм послойной кластеризации формирует последовательность подграфов графа G, которые отражают иерархические связи между кластерами: 
 
, 
 
где G^t = (V, E^t) — граф на уровне с^t, 
, 
с^t – t-ый порог расстояния, 
m – количество уровней иерархии, 
G⁰ = (V, o), o – пустое множество ребер графа, получаемое при t⁰ = 1, 
G^m = G, то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t^m = 1. 
 
Контролировать глубину иерархии получаемых кластеров возможно при изменении порогов расстояния {с⁰, …, с^m}, где 0 = с⁰ < с¹ < …< с^m = 1. При этом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.