Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 34
Текст из файла (страница 34)
ее оценку макси- мального правдоподобия 1 Х =- У пт%т, и !=! убеждаемся в эквивалентности задачи оценивании (по методу максимального правдоподобия) параметра 0 и задачи поиска разбиения наблюдений Х, на классы, наилучтпего в смысле функпионала качества Яз (5); если ковариационные матрицы исследуемых генеральных совокупностей не равны между собой и не известны, то, подстав.тяя в (5.25) вместо 2 т их оценки максимального правдоподобии %т, убеждаемся в эквивалентности задачи оценивании по методу максимального правдо|юдобиа параметра 0 и задачи поиска разбиении наблюдении Х, на классы, наилучшего в смысле функционала качества (),(5). В !303) авторы пытаются конструировать алгоритмы, реала тующие идею пол1чення оценок максимального правдоподобия для параметра О.
Однако, ням представляется, главная ценность подобного подхода лишь в его методологической, качественной стороне, в том, что он позволяет строго осмыслить и формализовать некоторые функционалы качества разбиения, введенные ранее чисто эвристически. Конструктивная же сторона подобного подхода упираетси в трудно преодолимые препятствия вычислительного плана, связанные с колоссальным количеством переборов вариантов уже при сравнительно небольших размерностях р и объемах выборки. Рольфункционалов качества разбиения в построении общей теории автоматической классификации и разнообразные примеры функционалов качества, используемых в конкретных (распространенных в статистической практике) алгоритмах автоматической классификации, описаны в гл.
10. 171 5.4.7. Функционалы качества классификации как показатели степени аппроксимации данных. Поскольку формируемая классификационная структура является приближенным представленкем имеющихся данных, естественно возникает идея формализации задачи классификации как задачи аппроксимации матрицы данных матрицей, характеризующей искомую классификацию. Для реализации этой идеи необходимо тем или иным образом выбрать, во-первых, матричный способ представления классификации и, во-вторых, меру близости между матрицами, соответствующими исходным данным и искомым классификациям. Рассмотрим некоторые' возникающие при этом задачи для ситуаций, когда классификация рассматривается как а) иерархия классов, б) разбиение, в) совокупность непустых (возможно, пересекающихся) подмножеств, а в качестве меры близости матриц используется обычная евклидова метрика— сумма квадратов разностей их соответствующих элементов.
В одной из первых версий аппроксимационная постановка задачи была рассмотрена для классификации, представленной иерархической системой кластеров, т. е. совокупностью разбиений 5', 5',..., 5'" множества объектов О, такой, что каждое последующее разбиение 5' получается из предыдущего разбиения 5'-' объединением некоторых его классов (1 = 1,2, ..., лг), причем последнее разбиение 5м состоит из единственного класса, совпадающего со всем множеством 0'.
Разбиение 5' соответствует 1-му уровню иерархии, характеризуемому также индексом уровня и,, монотонно зависящим от 1 (обычно полагают и, =1). Такая иерархическая система порождает, в частности, матрицу расстояний между объектами 0„0; по следующему правилу: расстояние й (1, 1) между ними равно индексу уровня и, того разбиения 5', в котором они впервые попадают в один н тот же класс. Мера близости й (1, 1) является ультриметрикой, т. е. удовлетворяет усиленному неравенству треугольника: й (1, 1) и щах (й (й /г), й (1, й)) для любых й =-- 1, ..., и.
Имеет место и обратное утверждение: всякая ультраметрика порождает иерархическую систему кластеров, индексами уровня которой служат различающиеся значения ультраметрики. Такимобразом, иерархические системы кластеров эквивалентно представимы ультраметрическимн матрицами близости. Это позволяет формулировать задачу построения иерархической системы кластеров как задачу аппроксимации заданной матрицы расстояний ры с помощью ультраметрических матриц (250!. Ока- 172 ' Иерархичесхим процедурам классификации посвихцеиа гл.
Я. залось, что если искомая ультраметрика удовлетворяет априорному ограничению и' (й () ( р„., а критерий аппроксимации — сумма квадратов (или других монотонных функций) от разностей г( (с, у) — п,л то оптимальной будет система кластеров, получаемая по методу <ближайшего соседа». Иными словами, ультраметрическое расстояние <( (Ц) есть не что иное, как минимальное значение р, при кото,ром р-граф Г„= ((~', /):ры < р) содержит последовательность ребер, соединяющую объекты О, и От (или, что то же самое, максимальное ребро на тои части кратчайшего незамкнутого пути, которая соединяет эти объекты). Из сказанного вьпекает следующее свойство «компактности» оптимальных кластеров: любое «внутреннее» расстояние ры для объектов Оь О; принадлежащих одному и тому же кластеру 5, меньше любого расстояния и' (й, 1) «во вне», т.
е. при любых О, из 5 и Оь не принадлежащих 5. Задача аппроксимации с противоположным ограничением й (~',() > р;, приводит к методу «дальнего соседа»с аналогичными свойствами. Задача аппроксимации матрицы близости с помощью иерархической системы кластеров без ограничений не рассматривалась практически в литературе, в отличие от задач аппроксимации с помощью разбиений и подмножеств (задаваемых, впрочем, специальными типами ультраметрик). Рассмотрим некоторые результаты, полученные в (92] применительно к ситуации, когда элементы матрицы характеризуют не расстояние, а сходство (связь) между объектами.
Разбиение 5 =- (5,, ..., 5„) множества объектов О представим матрицей связи вида (Хзц), где зо = 1, если Оь О, содержатся в одном и том же классе разбиения 5, и зы = 0 в противном случае, а Х вЂ” вещественное число, характеризующее уровень связи между объектами «внутри» классов 5. Нетрудно видеть, минимизация суммы квадратов разностей величин ры — Ха„при заданном ) ) 0 эквивалентна задаче отыскания такого разбиения 5, которое максимизирует суммарные внутренние связи ~ (5, и) = ~я~~~ ~ч»', (р;; — и) = ~ ',Р рм — л~ч»', и).
(5.26) »=1цгез, »= 1 ь/ез» ! Величина»« = Х/2 играет здесь, с одной стороны, роль порога существенности связей ры, поскольку при рп ) и выгодно поместить О, и О; в один и тот же класс (р„. — и ) О), а прн р»з ~ л, напротив, зто невыгодно, и, с другой стороны, роль параметра компромисса двух противоречивых 173 критериев — максимума суммы внутренних связей Е Хр„- 1 1уез~ =-1(5) и минимума меры концентрации — Еп~* — — Я, (5). л» с Оптимальное по данному критерию разбиение 5 = (5„ „,, 5„) компактно в том смысле, что средняя связь р (5,) ==- = - Х рц1п в каждом из его классов 5, не меньше, чем сред- и Iез, няя связь р (5„5,) во вне и чем средняя связь между лю- быми классами р (5ь 5,).
Точнее, для любых 1, д, 1 справед- ливо неравенство р (5ь 5~), р (5«, 5,) ( л ( р (5,). Разбиение, удовлетворяющее дайному свойству, может быть найдено с помощью локально-оптимального агломера- тивного алгоритма, на каждом шаге которого объединяются те классы 5„5«, для которых сумма связей Х Х (ры — и) г~=л', »в максимальна и положительна.
Процесс объединейий пре. крашается, когда такие суммы для всех 1 ~эп становятся неположительными. Таким образом, данная задача приво. дит к сумме всех связей (за вычетом порога) как мере бли- зости классов. В том случае, когда величина Х не фиксирована заранее, а подбирается в соответствии с квадратичным критерием ап- проксимации, се оптимальное значение (при данном 5) рав- но среднему значению внутренних связей » » Х(5) = '~' ~' рм ~ пу. 1 ьге5~ 1= 3 В этой ситуации необходимое условие оптимальности 5 может быть уточнено следующим образом: средняя внут- ренняя связь Х (5) по крайней мере вдвое превышает сред- ние связи между любыми двумя классами (р (5„5«)) или во вне (р (5о 5~)).
Данное условие также может исполь- зоваться в качестве критерия оптимизации и остановки в агломеративном методе последовательного объединения классов. К достоинствам рассмотренной аппроксимационной за- дачи классификации относится то, что, во-первых, она до- пускает интерпретацию в терминах порога существенности (он же показатель компромисса) и; во-вторых, приводит к «компактным» в указанном смысле кластерам, число кото- рых не задается заранее, и, в-третьих, при некоторых кон- кретных способах расчета связей ры эквивалентна другим аппроксимационным критериям многомерной классифика- ции по матрице «объект — свойство», содержащей как коли- чественные, так и номинальные признаки [111!, Особенно- 174 стью данного критерия являегся наличие единого порога существенности для всех классов, что неудобно в тех не- редких ситуациях, когда струк»ура данных отражает нали- чие кластеров различных «диаметровм Этот недостаток в значительной мере преодолевается в методике последоватечьной аппроксимации матрипы связи с помощью отдельных подмножеств множества объектов О.
Подмножество 5 «=' О характеризуется (п \'и)-матрипей ()|а„), где а„( прп О|, О; с 5 и з;; = (| в противном слу- чае. Прп фиксированном значении Х ) 0 задача квадратич- ной аппроксимации матрицы (р,з) в множестве матриц тако- го вида эквивалентна задаче максимизации суммы внутрен- них связей /(5, п)= ~ (р;,— и) == ~ р„— ллх, Г,па |./еа что представ.|нет собой часть критерия (5.26), соответст- вующую одному классу. Здесь и =.
Х/2, а пз — число объектов в 5. Необходимое условие оптимальности здесь принимает следующий вид. Оптимальное множество 5 являешься и- кластером в том смысле, что для всякого обьекта О| ~ 5 его средняя связь р (|', 5) = Х /|м/ла с 5 не меньше, чем и, гь тогда как для О, «г= 5 р (|', 5)~ и. Это свойство позволяет формировать локально-оптимальный п-кластер путем пос- ледовательного присоединения к 5, начиная с 5 = К, объ- ектов, име|ощпх с «текущим» 5 максимальную среднюю связь р (/.
5), если р (|', 5) = п. В том случае, ко| да величина Х или и =- Х/2 заранее не задана, ее выбор можно также подчинить аппроксимацион- ному критерию, который, каь нетрудно убедиться, равен в этом случае й» (5), где а(5)== Х рм/и --пар(5), (5.27) | ~еа причем р (5) =- Х рм/п,' — не что иное, как оптимальс | ея ное значение А, равное средней внутренней связи.
Оптимальное по данному критерию множество 5 являет- ся «сильным» кластером в том смысле, что его средняя внут- ренняя связь р (5) по крайней мере вдвое превышает сред- ню|о связь р (|', 5) с 5 любого объекта О| гд 5. Отсюда выте- кает алгоритм построения локально-оптимального сильно- го кластера 5с помощью последовательных присоединений к «текущему» 5 тех О|, для которых р (/, 5) максимально (по | (К 5), если /| (|, 5) ) р (5)/2. Подобные алгоритмы формирования отдельных кластеров развиваются в литера- (75 (8.28) п„=Л,+Л,з'!+Л»з',/+ ...
+Л»3«у+ам* где вы — минимизируемые невязки модели. Согласно методу последовательного исчерпания сначала определяется и вычитается из р„оптимальное Л, равное среднему значению рм, затем матрица ры — Л, аппроксимируется матрицей вида (Л,зЯ; после этого остаточная матрица ры — Л» — Л,з"ы аппроксимируется матрицей (Л«зы») и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
