Графическое представление результатов кластерного анализа

Иерархическая классификация, как уже отмечалось, допускает наглядную интерпретацию. Для того чтобы привязать граф иерархии или дендрограмму к системе прямоугольных координат, введем понятие индексации. Индексацией h иерархии называется отображение h: h®R ¹, ставящее в соответствие множеству K h число h(K) R ¹ таким образом, что

1) h(K) = 0 для одноэлементных множеств K, т.е. ô K ô = 1;

2) h(K´) < h(K) для каждой пары (K´,K) такой, что K´ K, K´≠ K.

Индексация иерархии позволяет алгоритмизировать процесс построения дендрограммы. Пусть (h, ν) – некоторая индексированная иерархия h на множестве О = { O ¹, O ², …,O^N }. Вершины графа иерархии, отвечающие одноэлементным множествам { Oⁱ }, i = 1,2, …, N, обозначим через ν_i, а вершины, соответствующие К (| К | > 1), обозначим ν_К. Введем систему координат с осью абсцисс х и осью ординат η. Вначале на оси х через равные интервалы D размещаются вершины , то есть представляются в виде точек с координатами = (i D, 0). Предположим далее, что вершины и уже нанесены на плоскость в виде точек с координатами и . Тогда кластер K = K_i K_j может быть представлен точкой с координатами с последующим соединением ее с точками и . Напомним, что η _К > max(, ) согласно п.2 определения индексации, так что вершина v_К расположится выше вершин и . Заметим, что построенная таким образом дендрограмма может содержать нежелательные пересечения ребер, поэтому вершины переупорядочиваются так, чтобы ребра соединялись только в вершинах. На рис.9 представлены дендрограммы иерархии с пересечением и без. Заметим также, что традиционно ребра диаграммы изображают в виде вертикальных и горизонтальных отрезков, как на дендрограмме без пересечений (рис.9,б).

а) б)

Рис.9. Дендрограммы иерархии примера из п.9.5.1:

а − с пересечением ребер; б − без пересечения ребер

Способы задания индекса ν могут быть разные. Весьма распространена индексация, ставящая в соответствие множеству K h номер шага, на котором это множество было включено в иерархию. В качестве альтернативы индексом может выступать мощность множества, точнее ν = ô K ô – 1.

Информативность дендрограммы существенно возрастает, если в качестве ординаты кластера K, полученного объединением кластеров K_i и K_j, т.е. K = K_i K_j, выступает расстояние между кластерами d (K_i, K_j). Такое изображение называют оцифрованным.

Одна из проблем иерархического кластерного анализа – определить, какие метрики позволяют провести оцифрование, удовлетворяющее условиям индексации, или иначе, найти индексацию, такую что ν (К_i К_j) = d (К_i,К_j). Так, для евклидовой метрики ответ на этот вопрос – отрицательный, что можно проиллюстрировать следующим примером. Пусть пять двумерных объектов, подлежащих кластеризации, образуют конфигурацию, представленную на рис.10, а.

а)

б)

Рис.10. Пример инверсии для евклидовой метрики:

а − исходная конфигурация; б − инверсия

На первом шаге агломеративной процедуры получаем кластер К ₁=.{ О ¹ ,О ²} c координатами центра тяжести Z (К₁) = (1,5;1). Для кластера К ₁, полученного объединением одноэлементных кластеров { O ¹} и{ O ²}, d (О ¹, О ²) = 1. Ближайшимк К ₁ окажется объект О ³ (точнее одноэлементный кластер К₂ ={ O³ }) с координатами центра тяжести v (К ₂)= (1,5; ). На следующем шаге алгоритма образуется, очевидно, кластер К ₃ =К ₁ К ₂ с d (К ₁, К ₂) = (1 – )², поскольку расстояние между кластерами измеряется по центрам тяжести (квадрат евклидова расстояния). Выходит для кластера К ₃ потенциальный индекс, равный расстоянию (1 – )², оказывается меньше по сравнению с индексом К ₁, равным 1. Налицо инверсия, поскольку нарушено требование 2, предъявляемое к индексам: К ₁ К ₃ ® ν (К ₁) < ν (К ₃)(см. рис.10, б).

Достаточные условия, когда оцифрование является и индексацией, содержатся в теореме Миллигана. Эта теорема опирается на рекуррентную формулу Жамбю, которая позволяет пересчитывать расстояния между имеющимся кластером К и вновь образованным K¢=K_i K_j (K¹K_i, K¹K_j), используя расстояния и индексы, полученные на предыдущих шагах: d (K, K¢) = a ₁ d (K,K_i) +a ₂ d (K,K_j) +a ₃ d (K_i,K_j) +a ₄ ν (K) +

+a ₅ ν (K_i) +a ₆ ν (K_j) +a₇ ½ d (K, K_i) –d (K,K_j)ú,

где a_i – числовые коэффициенты, зависящие от метода определения расстояния между кластерами. Так, при

а ₁ =а ₂ =–а ₇ = 1/2 и а ₃ =а ₄ =а ₅ =а ₆ = 0

приходим к расстоянию, измеренному по принципу «ближайшего соседа», а при

а ₁ =а ₂ =а ₇ = 1/2 и а ₃ =а ₄ =а ₅ =а ₆ = 0 – «дальнего соседа».

Теорема Миллигана. Пусть h – иерархия на О, полученная с использованием метрики d (К ₁ ,К ₂), для которой справедлива формула Жамбю. Тогда, если а ₁ +а ₂ +а ₃ ³ 1, а_j³ 0для j= 1,2,4,5,6 и а ₇³ – min(а ₁ ,а ₂),

то отображение h, задаваемое формулой h(К ₁ К ₂) = =d (К ₁ ,К ₂) и условием ν ({ О ⁱ})=0, i= 1,2, …,N, является индексацией.

В заключение отметим, что если рассечь дендрограмму горизонтальной линией на некотором уровне h *, получаем ряд непересекающихся кластеров, число которых равно количеству «перерезанных» линий (ребер) дендрограммы; состав кластера определяется терминальными вершинами, связанными с данным «перерезанным» ребром.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 11