Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 49
Текст из файла (страница 49)
Таким образом описан алгоритм нахождения порогового значения а для линейного к.>ассификатора, задаваемого вектором и Е 1<р, <<о<> -= 1. В качестве и обычно берется какой- либо координатный вектор либо собственный вектор корреляционной матрицы множества 5 с: 1тр. Вектор и можно получить также как решение задачи целенаправленного проецирования (см. гл.
19), дающее проекцию Йг-+- Й<, для которой 5 = — (у„..., у ) — наиболее неоднородная чнсповая выборка в смысле некоторого критерия. Алгоритм иерархической классификации множества Х из и элементов состоит из (и — 1) шагов. На вход дивизимного алгоритма подается все множество Х. На Ьм шаге получается разбиение 5"> множества Х на (й+!) непересекающихся множеств (классов) 5', ', ..., 5Д<, называемое разбиением й-го уровня. Итоговая иерархия з представляет собой систему з = л+1 5<">, образованную вложенными разбиениями 5<'>:э ь=! :э 5">:э ...
~ 5<"-'> Здесь 5'" = Х. (Говорят, что разбиение 5<'> = (5<><>, ..., 5",,') вложено в разбиение 5< > = =- (5<<*>, ..., 51 >), если каждый класс из 5<'> является подклассом некоторого класса из 5<'>.) Если на й-м шаге получается разбиение 5<», все классы которого удовлетворяют выбранному критерию однородности, то алгоритм обычно останавливается. 8.2.2. Агломеративные алгоритмы.
На вход агломеративного алгоритма подается разбиение 5<'> = (5(<>...., 5<„'), где 5,"' = (Х<). Разбиение й-го уровня имеет вид 5<ь> = =- (5<я>, ..., 5<"> „) и стр ится из разбиения 5<" — '>, й > 1, путем объединения пары классов (5*„5з), где (5<, 5>)= ага пцп р(5„5,). (8.7) за Фз. з„з,ез<ь- <> 253 Итоговую иерархию з образует система вложенных разбиений 5<'> ~ 5<'> с: ...
с:. 5<" — '> Здесь 5<а — '> = Х Отметим, что иерархическая классификапня при помощи бинарного алгоритма всегда дает бинарную иерархию. 3 а м е ч а н и е. Иногда (см, например, (9!) иерархической классификацией множества Х называют построение системы вложенных разбиений 5<"> ~ 5<'> ~ .. ~ 5<н-'>, где 5<е> =- .Х илп 5<'> с 5<'> с ... с 5< — т> где 5< -т> = = Х. Предыдущие рассуждения показывают эквивалентность такого определения иерархической классификации и данного выше определения 8.4.
Напомним, что наиболее употребительные в агломеративных алгоритмах меры близости р (5„5,) приведены з $ 5.3 Свойства этих мер близости и методы эффективного решения задачи (8.7) обсуждаются ниже. Здесь же только отмстим, что мера близости (8.3) удовлетворяет рекуррентному соотношению (5.10). Как будет видно далее, она обладает рядом важных свойств, которые обеспечивают широкое использование ее при решении задач классификации В то же время ниже показано, что «Расстояние по центрам тяжести» (8.6) не обладает такими свойствами. Графические представления результатов иерархической классификации Алгоритмы иерархической классификации по сравнению, например, с алгоритмамн, описанными в гл. 7, применимы для классификации множеств Х относительно небольшого объема', но зато позволяют в ряде случаев получить более полный анализ структуры исследуемого множества объектов Так, граф классификации дает представление о взаимосвязи между разбиениями 5<' > и 5<' > на разных уровнях, и если принято решение останови~ься на разбиении 5<'> множества Х, то для каждого элемента Х Е Х можно оценить степень его принадлежности к классу 5',"> для некоторого ! при помощи пути (простой цепи, см.
[12, с. 147!), соединяющего вершины графа, соответствующие Х и классу 5<'>. Существенным преимуществом алгоритмов иерархической классификации является возможность наглядной интерпретации проведенного анализа. Имеется большая свобода ' Прн программной реализации алгоритмов иерархической класснфнкацнн требования к объему оператнвной памяти ЭВМ н время счета быстро растут с ростом числа элементов в множестве Х.
з построении на плоскости данного графа иерархии. Изучая различные изображения, согласованные с его ~ груьтурой, можно получить ряд нетривиальных результатов об исследуемом множестве объектов, которые и рассмотрены ниже. 8.3.1. Индексации иерархии. Методы построения на плоскости графа иерархической классификации.
Опишем общую схему построения на плоскости ~ рафа агломеративной классификации Для получения изображения графа дивизимной классификации применимы те же методы, только во всех построениях надо поменять на противоположное направление осп ординат (см. рис. 8.2). О п р е д е л е н и е 8.5 Индексацией ч иерархии называется отображение»: з- й', ставящее в соответствие множеству 5 с з число я (5) таким образом, что: 1) ~ (5) = 0 тогда и только тогда, когда 5 состоит нз одного элемента; 2) х [5') < ч (5)для каждой пары (5', 5) нз з, такой, что 5' ~ 5. О п р е д е л е н и е 8 6 Стро~оп индексацией ч иерархии з называется ее индексация, удовлетворяющая условию: 2') т 15 ) ~ ч (5) для каждой пары (5', 5) из ь, такой, что 5' с: 5 и 5' Ф 5.
Пусть(з,ч) — некоторая индексированная агломеративная иерархия з нз множестве Х = (Х,, ..., Х„), построенная при помощи меры близости р (5,, 5,). Вершины графа этой иерархии, соответствующие мно кествам (Х,), 1 = 1, ..., л, обозначим через о„а вершины, соответствующие множествам 5 с з, (5 ~ ) 1, — через из. Допустим, что вершины из, и оз, нанесены на плоскость, т. е. можно записать в координатах: оз, = (пз„пй,) и из, = (оэ„ий,). Тогда, если 5, () 5, = 5 ~ з, то положим пз = ~ — (оз,+оз,), у (5)) н соединим точки из, и из.
с пз. Далее будем использовать соединение, показанное на рис. 8 3. Начальный шаг построения обеспечивается тем, что, по предположению, вершины о, располагаются на оси абсцисс. На этой оси они упорядочиваются так, чтобы з итоговом изображении графа минимизировать число пересечений ребер графа Например, если ч — строгая индексация, то можно так упорядочить вершины и„! ( 1 < и, что ребра будут соединяться только в вершинах. Таким образом каждая индексация задает изображение графа. До последнего времени в пакетах программ реализовывалось графическое представление агломератнвной иерар- хнн, основанное на строгой индексации т, ставящей в соответствие множеству 5 5 з номер шага, на котором это множествобыловключенов иерархию.
В этом случае индексация т любой иерархии з принимает значения О, 1, ..., (и — !) '. Важные исследования по индексациям иерархий проведены в (248), на результаты (248! опирается изложение этих вопросов в книге. 8.3.2. Оцнфровка нзображення графа иерархической класснфнкацнн. Прн наглядной интерпретации результатов в )з) Рис. 8.4. Конфигурация точек множества Х-(хь ..., хм) нз примера 8.3 Рис. 8.3. Правило соединения вершин при изображении иа плоскости графа иерархической классификации с использованием индексирующего ото. бражеиия т х На распечатках графа иерархии, изображенного с помощью такой индексации, обычно вместо номера уровня выводят значения меры близости р (Зь Зз) между классамн Зх н ды которые иа этом уровне образовали новый класс 3 = 8) Ц Зз. 9 Заказ № 291 классификации большое значение имеет то, какую дополнительную информацию о структуре исследуемой совокупности объектов несет распределение на отрезке (О, П числовой последовательности (т (5)/т (Х), !о'! ~ 1, о 5 з) для выбранной индексации т.
П р н м е р 8.3. Пусть Х = (Х,, ..., Х„) — множество точек на плоскости, изображенное на рнс. 8.4, н з — его агломератнвная иерархия, построенная по мере близости (5.6): р (З„оа) = 1Д вЂ” Хт((х, где Х) — центр класса Я), ) =- 1,2. Здесь Х, = ( — 1, 5, е) н Х, = (1,5, е), где О ( е ~ ( О,!25. Поэтому ~ Хх — Ха!!з =) Хз — Ха)а ) 1+ е'. Из рнс. 8.5 видна роль выбора индексирующего отображення ч. В случае а) наглядна последовательность вхождения классов 5) в иерархию; в случае б) это невозможно увн- С'Ъ СО а ! У хж а ~~ Р) б ) 253 ъв а л а щ ~ рр сц в Ф с а а ~ п см 'О йи 1й 'Ы 1~ Р~ ~с Я о~ М Я оо О. ао $ и~ х ~ д О д Я 3 3 а ФМ до ~ х а Х-*, Ф Я.
'О, ы О) й Ф н сз а Рис 8 6. Инверсии в изображении графа иерархической классификации множества точек нз нрннера 83 Здесь о, (хт), 1 1,2,3 оэ, =(хь хз), оз- (хь х, х,) Так как любое множество 5 Р з однозначно представимо в виде 5' О 5", 5' П 5" = Я для некоторых 5' и 5" из з, то формула (8.8) вместе с условием т ((Х,)) = = — О, Х, Е Х, ( = 1, „п, однозначно задает отображение т на з.
Таким образом, сформулированная задача эквивалентна следующей: для каких мер близости р (5„5,) отображение т, задаваемое формулой (8.8), является индексацией. П р и м е р 8.4. Пусть Х =- (Х„..., Х„) — набор точек в евклидовом пространстве )с' и р (5„5,) — --- 11х,з— — ха)1з, гдето, — центр класса 5, с: Х, 1 = 1, 2. Тогда отображение о, задаваемое формулой (8.8), не является индексацией. Действительно, для точек (Х„..., Хзе) из примера 8.3 имеем в случае 5, = (Х„Х,) и 5, =- (Хз): Яз = ( — 1,8, 1), Лз = Хз и р (5„5з) = (1 — е)', где е ) О. Таким образом, для т (5) =- р (5„5з) получаем: 5, ~ 5 = 5з 0 5з, но т (5) = (! — е)з <т (5,) = -р((Х,), (Х,))=1 — противоречие с определением индексации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
