Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 51
Текст из файла (страница 51)
В то же время, как уже отмечалось, для редуктивных мер близости (см. определение 8.7) описанная процедура представляет собой ускоренный вариант классической аг- ломеративной процедуры Приведем важнейшие редуктивиые меры близости. Про- верка опирается на теорему 8.2 и проводится в терминах параметров а„..., а общей рекуррентной формулы для мер близости. (ૠ— ! 11 Положим а, + а, + ~ ! =- Ь и ппп (аь а«) = — «1. Тогда, по теореме 8.2, если параметры а„..., а, таковы, что Ь ) 1, ат О, 1 = 1, 2, 4, 5, 6 и «( ~ а, то определяемая ими мера близости р (о„ 5«) редуктивна. Для краткости указываем только наименование меры близости: 1) «ближайший сосед» (5.4): 1 а,=а = — а«= —, аз=О, 3 <1( б, 2 1 Ь=1, И= — — =л-' фФ 2 2) «дальний соседе (5.5): ! а,=о«=а,= —, аз=О, 3 ( 1< 6, 2' Ь=1, а= — — -и,; ! 2 3) средней связи (5.7): и« л« а«= — ', аз=О, 3 <1< 7, л«+л, л,+л Ь=1 д= — лил(л" л«1 ~Ос л,+л, 4) приращение статистического разброса при объединении классов (см.
примеры (8,5 и 8.6)). выводы 1. Введены понятия иерархии з на множестве объектов Х= = (Х„..., Х„) и графа иерархии. 2. Общая постановка задачи иерархической классификации состоит в требовании построить иерархию з на исследуе- мой совокупности объектов, отражакицую наличие однородных, в определенном смысле, классов и взаимосвязи между этими классами. 3. В основе алгоритмов иерархической классификациилежиттот или иной критерий качества 11 (5„..., 5„) разбиения множества 5 на подмножества 5„...,5„.
Обычно используются бинарные алгоритмы (й= 2). В этом случае 1;1 (5„5,) имеет смысл близости р (5„5 ) между множестврми 5, и 5,. Мера близости р (5„5,) либо фиксирована, либо меняется (настраивается) в ходе алгоритма. В последнем случае говорят о гибкой (адаптивной) стратегии классификации. 4. Алгоритмы иерархической классификации бывают: а) дивизимные, результатом которых является система вложенных разбиений 5">:з 5(М:э ...:з 5("-ы множества Х, где 5нв = Х и 5но =- (5'„м, ..., 5Д~) — разбиение Х на непересекающиеся классы, называемое разбиением й-го уровня. Переход с й-го уровня на (й + 1) осуществляется разбиением некоторого класса 5)*' на подклассы 5(, Я, где (Я, Я) =агя гпах р(5м 5з); з цз =~ю с б) агломеративные, результатом которых является система вложенных разбиений 5пвс5П> ~ ...
с У"-'> множества Х, где 5йв = (Х„..., Х„) и 5по = (5<~~, ..., 5„'~~ ь) — разбиение й-го уровня. Переход с й-го уровня на (й+ 1)-й осуществляется объединением пары классов (5;, 5з), где (Я, Я)= агц пнп р(5п 5з). зоезэ з~. за е зпл б. Существенным преимуществом алгоритмов иерархической классификации является возможность изображения на плоскости графа полученной иерархии, называемого графом классификации.
Имеется большая свобода в построении на плоскости данного графа классификации. Изучая разл ичные изображения, согласованные со структурой этого графа, можно получить ряд тонких результатов об исследуемом множестве объектов. б. Описана общая схема построения на плоскости графа классификации. В основе построения лежит понятие индексации иерархии, которая представляет собой отображение, ставящее в соответствие каждому классу 5 число я (5) таким образом, что ч (5) = 0 тогда и только тогда, когда 5 состоит нз одного элемента, и т (5') ~ т(5), как только 5'~5.
7. Для визуального анализа иерархии а большое значение имеет построение на плоскости такого изображения ее графа, при котором классу 5 Е а соответствует точка с ординатой т (5) = — р (5„5,), где 5, и 5, — классы, из объединения которых получен класс 5. Такие изображения называются оцифрованными. 8. Важнейшие меры близости р (5„5,) описываются общей рекуррентной формулой (8.9).
В терминах параметров а„..., а, из (8.9) а) даны условия, достаточные для существования оцифрованного изображения графа классификации, соответствующего мере близости с этими параметрами; б) описана общая схема построения алгоритмов гибкой стратегии иерархической классификации; в) описана общая схема процедур иерархической классификации, использующих пороговые значения, но дающих тот же результат, что и классические агломеративные процедуры.
В рамках этой схемы описан быстрый алгоритм иерархической классификации, позволяющий получать иерархическую классификацию больших массивов данных на ЭВМ средней мощности, в частности иа персональных компьютерах. Гл а в а й. ПРОЦЕДУРЫ КЛАСТЕР-АНАЛИЗА И РАЗДЕЛЕНИЯ СМЕСЕЙ ПРИ НАЛИЧИИ АПРИОРНЫХ ОГРАНИЧЕНИЙ Разделение смесей при наличии неполных обучающих выборок Здесь н далее в главе рассматриваются процедуры кластер- анализа и разделения смесей распределений, когда у исследователя имеется некоторая априорная информация относительно желаемой классификации, задаваемая в виде тех или иных ограничений. Иногда возникает ситуация, когда исследователю известна принадлежность некоторых объектов из матрицы данных Х к некоторым компонентам смеси или кластерам (классам).
Дальше будем считать без ограничения Мщности, что имеются обучающие выборки (ОВ) (Х)'~1 =-(1,!) для1первых классов и объем такой выборки т7, Суммарный объем таких выбо- 267 рок т = лт/ (( а и не позволяет воспользоваться процедурами дискриминантного анализа. Количество ОВ (!) может быть меньше количества выделяемых классов /г. 9.1.1. Модификация ЕМ-алгоритма. ЕМ-алгоритм для оценки параметров смеси распределений описан в 9 6. 4, Этот алгоритм носит итерационный характер, на каждом шаге 1, в частности, пересчитываются вероятности принадлежности г-го объекта Хг к /ьму классу по формуле (6.9) 2)гг=Р,/(Х,; В,"-") / ч; Р,1(Х,; Е,'-'-"). / /-! (9.1) Р(Х!, Х„)=(Х,— Х,) Х;,(Хг — Х„). (9.2) Пусть теперь )г — вектор размерности и, у которого г'-я компонента равна номеру класса для объекта Хь Приравниваем к нулю компоненты )г, а объектам из ОВ присваиваем соответствующие номера.
Текущее значение числа клас- г Ноьтзг Ю. 97. /г. А согпрзгаз!оп о1 Цегз!!ее Мзх!пгппг Ь!ЬеЬооб Езнее!ез о! !Ье Рогатое!его о1 е М1х! пге о1 Т» о !Чогпгз! О!з!г!ЬпЦоп побег ТЬгее О!1!егеп! Турез о1 Взгпр!е //В!огпе!г!ез. — 1973.— Чо!. 29.— Р. 70! — 700.
Модификация алгоритма при наличии неполных ОВсостоит в том, что для объектов, которые в них содержатся, значения й!)гй корректируются следующим образом 166): если объект Х; принадлежит ОВ для г-го класса, то 2)/о = 0 (/ чь г, / = 1, й) и а''г! = 1. Эффективность использования неполных ОВ весьма велика. Имеются примеры, когда использование ОВ, составляющих примерно 10 еб исходной выборки, приводило к резкому улучшению результата разделения смеси '. 9.1.2. Разделение смеси с неизвестным чнсаом классов.
Рассмотрим случай смеси нормальных распределений с равными матрицами ковариаций, число компонентов й которой неизвестно. Кроме того, имеются неполные ОВ, так же как и в п. 9.1.1. Вычислительная процедура состоит из следующих шагов 166). Шаг 1.
Вычисляются оценки векторов средних значений Х; (/ = 1, 1) и общей матрицы ковариаций Х„г по неполным ОВ. Нижний индекс указывает число степенейсвободы, соответствующее оценке матрицы ковариаций. Далее для измерения расстояния между обьектами Хг и Х, используется расстояние Махаланобиса »»дпах= шах ~». Ьпах=агдшзх ~», т.
е. ~ьпах= 1»„„„. 1~»(и 1~(<и Относительно объекта Х» принимается одно из трех решений: 1) если ~,„,„,) ои то объект Х» относится к классу с номером» „, и проводится корреляция оценки Х»,„и Х: Хх» (т» Х»,„+ Х»)»(т»,„+ 1); (9.3) Х = Х+ — "" (Х, — Х",-,„) (Х, — Х;.',„)' (9.4) Используя формулу Бартлетта!129), получаемскорректи- рованную обратную матрицу д- (х, х,"- ) (х-'(х» — х, ® ))' та (9.5) 1+ '~ (х х"- )' к- ° (х х"- ) та»вам »еа т~щеа+ 1; т = т+ 1» й» Ьпах т) =ч)+ 1; сов л» полагается равным 1. Значение счетчика числа клас» сифицированных объектов т = ~; т;, где т» — объемы ОВ.
» 1 Шаг 2. Обнуляются счетчики числа классификаций объектов »1 и числа случаев образования новых классов $. Проведем пес»»едовательный просмотр неклассифнцированных объектов, т. е. объектов Х,, для которых Ь» — — О. Пусть Х» — такой объект.
Тогда вычисляются расстояния от Х» до центров уже образованных классов»Р (Хы Х»), величины 1» = — »1 Р+ 1 Р (Хо Х») и значения р(т — !) 1т — т) Р Щ) функции Р-распределения с р и т — »и — р + 1степенями свободы от 1». Вычисляется»» — — 1 — Р (»»). При сделанных допущениях (нормальность, равные матрицы ковариаций) величина ~» равна вероятности реализации расстояния от Х» до Х», большего или равного 1) при условии, что Х» действительно принадлежит 1-му классу. Пусть теперь Классификация нри ограничениях на связи между объектами 9.2.
Довольно типичной является ситуация, когда исследова тель желает получить разбиение совокупности объектов О„..., О„на классы, согласованное с матрицей ограничений В = (Ьм), 1 ( 1, 1 ( а, где Ьы —— Ь7„Ьп —— 1 и Ьы =О, ! Ф1, если объекты О, и Оп по априорным сведениям„ являются разнородными, и Ьы = 1, если таких сведений об объектах О, и 07 нет. Например, в задачах формирования нескольких экспертных комиссий для анализа некоторой производственно-экономической системы объектами группировки являются эксперты, описываемые их профессиональными показателями, но при формировании комиссий желательно учитывать особенности взаимоотношений между экспертами.
В ряде задач, где объекты описываются 270 2) если ~„„„( с,, то считается, что объект Х, принадлежит некоторому новому (т + 1)-му классу; счетчик числа классов т увеличивается на 1 [и = и + 1) и полагается, Х = Хь й; = т; $ =- $ + 1; т = т + 1; 3) если выполняются неравенства в, < ~„„„< см то никаких действий не проводится. Если просмотр объектов не окончен, то переходим к просмотру следуюшего объекта. Шаг 3. Проверяется, все ли объекты расклассифицированы, т.
е. равенство т = и. Если оно выполняется, то производится переход на шаг 5, в противном случае на шаг 4. Шаг 4. Проверяются значения счетчиков 7! и $. Если хотя бы один из счетчиков не равен нулю, то переходят на шаг 2. Если одновременно т! == 0 и $ = О, то, следовательно, иа шаге 2 не было образовано ни одного нового класса и не было классификации объектов. Поэтому проводится уменьшение порога с, на величину бс, и увеличение порога с, на величину бс„т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
