Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Графическое представление результатов кластерного анализаИерархическая классификация, как уже отмечалось, допускает наглядную интерпретацию. Для того чтобы привязать граф иерархии или дендрограмму к системе прямоугольных координат, введем понятие индексации. Индексацией h иерархии называется отображение h: h®R 1, ставящее в соответствие множеству K h число h(K) R 1 таким образом, что 1) h(K) = 0 для одноэлементных множеств K, т.е. ô K ô = 1; 2) h(K´) < h(K) для каждой пары (K´,K) такой, что K´ K, K´≠ K. Индексация иерархии позволяет алгоритмизировать процесс построения дендрограммы. Пусть (h, ν) – некоторая индексированная иерархия h на множестве О = { O 1, O 2, …,ON }. Вершины графа иерархии, отвечающие одноэлементным множествам { Oi }, i = 1,2, …, N, обозначим через νi, а вершины, соответствующие К (| К | > 1), обозначим νК. Введем систему координат с осью абсцисс х и осью ординат η. Вначале на оси х через равные интервалы D размещаются вершины , то есть представляются в виде точек с координатами = (i D, 0). Предположим далее, что вершины и уже нанесены на плоскость в виде точек с координатами и . Тогда кластер K = Ki Kj может быть представлен точкой с координатами с последующим соединением ее с точками и . Напомним, что η К > max(, ) согласно п.2 определения индексации, так что вершина vК расположится выше вершин и . Заметим, что построенная таким образом дендрограмма может содержать нежелательные пересечения ребер, поэтому вершины переупорядочиваются так, чтобы ребра соединялись только в вершинах. На рис.9 представлены дендрограммы иерархии с пересечением и без. Заметим также, что традиционно ребра диаграммы изображают в виде вертикальных и горизонтальных отрезков, как на дендрограмме без пересечений (рис.9,б).
а) б) Рис.9. Дендрограммы иерархии примера из п.9.5.1: а − с пересечением ребер; б − без пересечения ребер
Способы задания индекса ν могут быть разные. Весьма распространена индексация, ставящая в соответствие множеству K h номер шага, на котором это множество было включено в иерархию. В качестве альтернативы индексом может выступать мощность множества, точнее ν = ô K ô – 1. Информативность дендрограммы существенно возрастает, если в качестве ординаты кластера K, полученного объединением кластеров Ki и Kj, т.е. K = Ki Kj, выступает расстояние между кластерами d (Ki, Kj). Такое изображение называют оцифрованным. Одна из проблем иерархического кластерного анализа – определить, какие метрики позволяют провести оцифрование, удовлетворяющее условиям индексации, или иначе, найти индексацию, такую что ν (Кi Кj) = d (Кi,Кj). Так, для евклидовой метрики ответ на этот вопрос – отрицательный, что можно проиллюстрировать следующим примером. Пусть пять двумерных объектов, подлежащих кластеризации, образуют конфигурацию, представленную на рис.10, а.
Рис.10. Пример инверсии для евклидовой метрики: а − исходная конфигурация; б − инверсия
На первом шаге агломеративной процедуры получаем кластер К 1=.{ О 1 , О 2} c координатами центра тяжести Z (К1) = (1,5;1). Для кластера К 1, полученного объединением одноэлементных кластеров { O 1} и{ O 2}, d (О 1, О 2) = 1. Ближайшимк К 1 окажется объект О 3 (точнее одноэлементный кластер К2 ={ O3 }) с координатами центра тяжести v (К 2)= (1,5; ). На следующем шаге алгоритма образуется, очевидно, кластер К 3 =К 1 К 2 с d (К 1, К 2) = (1 – )2, поскольку расстояние между кластерами измеряется по центрам тяжести (квадрат евклидова расстояния). Выходит для кластера К 3 потенциальный индекс, равный расстоянию (1 – )2, оказывается меньше по сравнению с индексом К 1, равным 1. Налицо инверсия, поскольку нарушено требование 2, предъявляемое к индексам: К 1 К 3 ® ν (К 1) < ν (К 3)(см. рис.10, б). Достаточные условия, когда оцифрование является и индексацией, содержатся в теореме Миллигана. Эта теорема опирается на рекуррентную формулу Жамбю, которая позволяет пересчитывать расстояния между имеющимся кластером К и вновь образованным K¢=Ki Kj (K¹Ki, K¹Kj), используя расстояния и индексы, полученные на предыдущих шагах: d (K, K¢) = a 1 d (K,Ki) +a 2 d (K,Kj) +a 3 d (Ki,Kj) +a 4 ν (K) + +a 5 ν (Ki) +a 6 ν (Kj) +a7 ½ d (K, Ki) –d (K,Kj)ú, где ai – числовые коэффициенты, зависящие от метода определения расстояния между кластерами. Так, при а 1 =а 2 =–а 7 = 1/2 и а 3 =а 4 =а 5 =а 6 = 0 приходим к расстоянию, измеренному по принципу «ближайшего соседа», а при а 1 =а 2 =а 7 = 1/2 и а 3 =а 4 =а 5 =а 6 = 0 – «дальнего соседа». Теорема Миллигана. Пусть h – иерархия на О, полученная с использованием метрики d (К 1 ,К 2), для которой справедлива формула Жамбю. Тогда, если а 1 +а 2 +а 3 ³ 1, аj³ 0для j= 1,2,4,5,6 и а 7³ – min(а 1 ,а 2), то отображение h, задаваемое формулой h(К 1 К 2) = =d (К 1 ,К 2) и условием ν ({ О i})=0, i= 1,2, …,N, является индексацией. В заключение отметим, что если рассечь дендрограмму горизонтальной линией на некотором уровне h *, получаем ряд непересекающихся кластеров, число которых равно количеству «перерезанных» линий (ребер) дендрограммы; состав кластера определяется терминальными вершинами, связанными с данным «перерезанным» ребром.
|