Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 50
Текст из файла (страница 50)
Если же мысленно для такого отображения т изобразим граф иерархии по правилу, описанному выше, то на этом изображении получим следующий фрагмент (рис. 8.6), где вершина, соответствующая объединению двух подмножеств, лежит по оси ор- деть, но очень наглядно распределение тех же классов 5; по числу элементов в них, хотя речь идет об одной и той же иерархии з. Большое значение для визуального анализа иерархии з имеет такое построение ее графа, при котором множество 5 с з изображается точкой с ординатой т (5), соответствующей значению р (5„5,) для множеств 5, и 5„из объединения которых оно получено. Такие изображения графа называются оцифрованными.
т Возникает задача: пусть з †бинарн иерархия множества Х, полученная агломеративным алгорит- 1 2 3 мом при помощи меры близости р (5,, 5,). Найти индексацию т этой иерархии, такую, что т (5, Ц 5з) = Р (5 „5з). (8.8) динат ниже, чем вершина, соответствующая одному из этих подмножеств. В этом случае говорят, что мера близости имеет инверсии. В 9 8.4 приведены условия на меру близости, обеспечивающие отсутствие инверсий у нее. Ряд важнейших мер близости р (5„5,) этим условиям удовлетворяет (см. теорему 8.1). 8.4.
Приложения общей рекуррентной формулы для мер близости между классами 8.4.1. Расчет матрицы взаимных близостей классов данного уровня иерархии. Рассмотрим более подробно переход от разбиения 5<в — '> к разбиению 5<">, й «и — 1, на й-м шаге агломеративного алгоритма. Имеем 5<в — '> = (5<' — '>, ..., 5<л-'>,). Вычислим матрицу взаимных расстояний р<в — '> между классами разбиения 5<а-» и найдем пару классов (5', 5"), такую, что '(5', 5")=агд <п(п р(5<е — ", 5<» — '>), < .««и — *+< Пусть 5 5<<>-» и 5" = 5<а-<>, где «.1.
Тогда по- ложим 5<,'>=5<' — ", 1-,а1, 1, и — й+1, 5,'"= <>,, 5<е <> 5ы> 5<е-<> () < < а — еь< Следовательно, для получения матрицы взаимных расстоя- ний р«н можно воспользоваться матрицей р<ь — '>, вычислив дополнительно только расстояния р(5«<ь>, 5<в>), 1 за( при фиксированном >. Так как 5<"> = 5<"-'> () 5<" '>, то 4 < для этого оказывается полезной рекуррентная формула Камбю (2481: р(5 5'05")= р(5 5')+пер(5 5")+и.
Р(5' 5")+ + а т (5) + а т (5') + а„т (5") + а, ) р (5, 5') — р (5, 5") <, (8.9) обобщающая формулу Ланса и Вильямса (5.9). 8.4.2. Условия на меру близости, обеспечивающие отсут- ствие инверсий. Эти условия дает результат, полученным Г. Миллиганом [248), Т е о р е м а 8.! . Пусть з — иерархия на множестве Х, полученная при помощи меры близости р (5„5,), для кото- рой верна формула (8.9). Тогда, если а<+ а, + а, > 1, а; )Одля)=1,2, 4,5,6иа, > — пип (а<,аэ), тоото- бражение т: з->-)с<, задаваемое формулой т (5, () 5,)= 260 = р (5„5,) и условием т ((Х )) = О, 1= 1, ..., и, является индексацией. П р и м е р 8.8. Пусть Х = (Х„..., Х„) — набор точек в евклидовом пространстве Ки и р(5„5,) = ~ 1Х вЂ” ~( — ~ 1Х вЂ”.8,Р— хез Оз» хез, — '~' 1Х вЂ” Л,~п, (8.!0) хбз» где 2, 21 и Е, — центры классов 5, () 5ги 5 и 5 .
Тогда верна формула х р(5, 5") —, р(5', 5") л+л'+л" (ср. с формулой (8.10), где а = 15(, а' = 15'1 и л' = = 15" ~. В обозначениях формулы (8.9) имеем: л+л' л+л и ах=, а;= , а,= —, ап= л+л'+л" л+л'+и" л-~-и'+л =О, й=4... 7. Имеем а, + а, + аи —— 1, т. е. все условия теоремы Г.
Мили- гана выполняются и поэтому мера близости (8,10) не имеет инверсий. 3 а м е ч а н и е. Из (8.10) следует, что р(5„5,)=- "'" 1.8,— г,!!', и +и где л, = (5,(, и, = 15,1. Таким образом, введение множите- ля — '' позволяет исправить инверсию меры близости п,+и» р (5„5,) = (~ Я,— г,11' из примера 8.4, которая удовлет- воряет формуле (8.9) с параметрами: и, л, и~и» а~ = » , а, О, л,+и, и +и, (и»+п»)» й=4, ..., 7. Здесь а,+ап+а,=1 — "'"' (1. (л„и л )» 8.4.3.
Алгоритм гибкой стратегии иерархической классифи- кации. Формула Жамбю (8.9) позволяет обобщить гибкую стратггшо Ланса и Вильямса [1801. Пусть исходная информация о классифицируемых объек- тах представлена в форме матрицы взаимных расстояний Р = (ры), ! «~1, / ~ л. В алгоритмах гибкой стратегии расстояние между классами р (5„5,), где )5„~ )5,( -» 1, заранее нефиксируется, как это делается обычно, а настраивается в ходе классификации. Положим рнв =- р.
Пусть, по индуктивному предположению, известны матрица взаимных расстояний ры-'> между классами разбиения 5ы-'>, й = 1, ..., и — 2, и индексирующее отображение т: 5ы-'>— Напомним, что т на 5ио — нулевое отображение. Тогда, подобрав любым способом параметры а„..., а„удовлетворяющие теореме 8.1, получаем возможность при помощи формулы Жамбю вычислить матрицу взаимных расстояний рпо между классами разбиения 5~~>, а при помощи формулы т (5, () 5,)= — р (5„5,) — индексирующее отображение гл 5<м -+ )с' 8.4.4. Процедуры иерархической классификации, использующие пороговые значения. Как уже отмечалось выше, трудности реализации классических алгоритмов иерархической классификации (см.
п. 8.2.2) быстро растут с ростом числа и классифицируемых объектов. Это объясняется тем, что на й-м шаге алгоритма для каждого А = 1, ..., и — 1 приходится искать минимальный элемент в матрице взаимных расстояний ры-'~, т. е. находить минимальный элемент в массиве из Л~„, = (и — А + 1) (и — й)12 чисел. Ясно, что минимальный элемент в матрице ры м достаточно искать среди ее элементов, не превосходящих некоторый порог с, а массив таких элементов при соответствующем выборе порога с содержит элементов намного меньше, чем Ух ,. В связи с этим разрабатываются процедуры иерархической классификации, использующие пороговые значения.
Общая схема подобных процедур следующая: задается или формируется в процессе классификации последовательность порогов с,( с, < ... ( с,. На первом этапе алгоритма попарно объединяются элементы, а затем и классы, меры близости которых не превосходят он На втором этапе — с, и т. д., пока все элементы не объединятся в один класс. Эффективность таких процедур существенно зависит от внутренней структуры исследуемого множества объектов, от выбора последовательности пороговых значений с„..., с, и меры близости р (5„5,) между классами. Сравнительно недавно было показано, что если мера близости р (5м 5,) обладает свойством редуктивности (см.
определение 8.7), то процедуры иерархической классификации, использующие пороговые значения, позволяют построить точно такую иерархию, что и классические агломеративные процедуры, но работают они существенно быстрее последних (2491. Этим вопросам посвящен $8.5. 262 О пишем свойство редуктивности мер близости н способ его проверки. Пусть з = (5<»> с: ... с 5<»-» с 5<»> с: ... ) — бинарная иерархия, полученная агломеративным алгоритмом при помощи меры близости р (5„5,) и 5)~ ", 5)," '> — пара классов, которая объединяется в один класс на й-м уровне иерархии. О и р е д е л е н и е 8.7. Мера близости р (5д, 5») обладает свойством редуктивности (является рейуктивной), если для любого класса 5> б 5>»-», й =: 1, ..., и — 1, и порога с) О, такого, что р (5>~» '>, 5)," '>) ( с, из условий р (5>. 51» ") > с и р (5>, 5~~ ") > с вытекает, что р (5>, 51. () 5).
) > Для мер близости р (5„5,), удовлетворяющих формуле Жамбю (8.9), свойство редуктивности проверяется при помощи следующего теоретического результата: Т е о р е м а 8.2 (Диде). Если параметры а„..., а, меры близости р (5„5,) удовлетворяют условиям а, + а, + (ав 1а»В + ~ 1 >1,а>~ ~— ш(п(а„а»),а>.»0,1=1,2,4, б, 6, то мера близости р (5„5,) является редунтивной. Сравнивая утверждения теорем 8.1 и 8.2, получаем, что для каждой редуктивной меры близости р (5„5») отображение т:з — >.
Ж: т (5 1) 5,) = р (5„5,) является ин, дексацией соответствующей ей иерархии з. П р и м е р 8.6. Для меры близости р (5„5,) из примера а, — (а»1 8.6 имеем: а, + а, + ' = 1, т. е. приращение внутриклассового разброса при объединении классов является редуктивной мерой близости между классами. Другие важные примеры рассмотрены в $ 8.5. 8.8. Быстрый алгоритм иерархической классификации Опишем сначала основной блок алгоритма. Пусть Х == (Х„..., Х„) и р (5„5 ) — некоторая мера близости между подмножествами из Х. Выберем порог с.
Из матрицы взаимных расстояний рх = (ры = р (Х> Х>)) выберем массив )г, = (рн . р»( с). Допустим, что )р, и» я. Шаг А. Найдем р>„;, = щ)п риь %' 263 Объединим точки Х„и Х т, в один класс (Х;., Хт.), которому присвоим обозначение Х„+,. Положим Х'=(К„..., К „..., К~....., К„, К„+т), где . — символ удаления элементов. Сформируем массив %7 из матрицы взаимных расстоя.
ний множества рх,, включив в него: Рм, если РмЕ Ю, и ((, 1) П(г'„1Д= О; р, +э= р(Хь К„+д, если рп.'Е Ф", иля рсу. Е Ф'„ причем р; „+,«с. Таким образом получаем пару (Х', Я7,'). Если У7 -ь Я, то описанный шаг А можно повторить. Итогом работы рассматриваемого блока алгоритма является последовательность пар (х, яг„), (х', ю1), ..., (х', йг',), 1<(а" а — 1, где Х" — множество, полученное из Х»-', й) ), объединением двух каких-либо элементов, )е, — массив, сформированный из матрицы взаимных расстояний множества Хь и )г'~ — пустой массив.
Схема алгоритма 1. Задаем множество Х = (Х„..., К„) и меру близости Р % Зз). 2. Выбираем значение порога се и формируем массив В',. Например, с, выбирается так, чтобы д, 1Х(( ~Я7,~ < (д,~Х~, где д,, д, --- числовые параметры. 3. Применяем к (Х, ЯГ,) процедуру основного блока алгоритма. В результате находим множество Х', для которого )Р',= Я. По построению элементам множества Х' соответствуют непересекающиеся классы из Х, т. е. Х' — разбиение множества Х. 4.
Если 1Х'1) 1, то возвращаемся к шагу 1, заменив Х на Х'. (В алгоритмах гибкой стратегии заменяется и мера близости.) Если 1Х'1 = !, то заканчиваем работу алгоритма. Итогом работы алгоритма является бинарная иерархия на Х, но в общем случае эта иерархия не совпадает с иерархией, получаемой классической агломеративной процедурой при помощи меры близости р (5„5з) ..Соответствующий при- мер нетрудно привести для меры близости р (лм Вх) = ! А— — Е,1(«, где 2„2« — центры классов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
