Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 45
Текст из файла (страница 45)
1 — 3. Если пользователь решил изменить значение параметров ~р или ф, то переход к п. 1, если ~г и «р не меняется, то переход к 2. 5. После прохождения 7 циклов полученный набор центров е' = (е,', ..., а«,)объявляетсянабором эталонов классов и используется для классификации последующих наблюдений по методу минимального дистанционного разбиения. Выбор значений параметров признается удачным (удовлетворительным), если получаемая в результате классификация оптимальна или с точки зрения экспертов, или в смысле принятых функционалов качества разбиения.
7.4. Алгоритмы метода динамических сгущений Изложим, следуя в основном (106), один общий подход к статистической обработке данных, предложенный Э. Диде и его сотрудниками и названный «методом динамических сгущений» вЂ” МДС (Методе без (к(цеез Р(паш(«(цез— М(к(Р). Этот подход хотя и формулируется в терминах общей задачи классификации, но, по существу, при соответствующем подборе управл яющих параметров индуцирует разнообразные методы решения следующего широкого класса задач: 1) разбиение данной совокупности объектов или признаков на некоторое число (известное заранее или нет) однородных классов — собственно проблема автоматической классификации; 2) снижение размерности (числа анализируемых показателей) массива исходных данных, отбор наиболее информативных показателей; 3) статистический анализ предпочтений, задача их типологизации и агрегирования; 4) статистический анализ линейных моделей регрессионного типа; 5) оптимальная (в рамках решаемой конкретной задачи) оцифровка анализируемых переменных; 6) статистический анализ «двухвходовых» таблиц сопряженности.
Основная идея МДС, являющаяся далеким обобщением идеи метода й-средних (см. и. 7.2.1, 7.2.2), достаточно отчетливо выражена словами Э. Диде: «Среди всех разбиений на й классов следует найти разбиение, относительно каждого 2ЗО класса которого заданное «ядро» оказалось бы наиболее представительным. Понятие ядра ...
имеет самый широкий смысл: ядро класса (т. е. группы точек) может быть подгруппой !очек, центром тяжести, осью, случайной переменной и т. дм !106, с. 25! (курсив наш. — В. Б.). 7.4.1. Основные понятия иобщая схема метода. Пусть Х = == (Х,, ..., Х„) — исследуемое множество объектов, каждый из которых характеризуется р-мерным вектором признаков, т.
е. Х! ='= (хр, ..., х! ). и! (а! Пространством й покрытий Б» называется множество, каждый эчемент которого Б = (Бг, ..., Б») представляетсобои систему подмножеств (классов) элементов Х, удовлетворяющих заданной структуре классов. На практике встречак>тся обычно следующие типы структур классов: разбиения, покрытия, иерархии. Пространством представителей Е называется множество, каждый элемент которого может служить представителем (ядром) класса элементов Х.
Выбирается мера сходства Р (Х, 1)между объектом Х Е Х и представителем ! 5 Е. Например: а а) Б =- гсе, тогда ! 5 Ка и Р (Х, 1) = ~ (х' — р)' — квад!=! рат стандартного евклидова расстояния; б) Б ==- гтах М, где М вЂ” некоторое семейство расстояний (см. $ 5.2). Тогда ! = (е, й), е Е !!», й Е М и Р (Х, 1) =— = д (Х, е).
Семейство М обычно задается в параметрическом виде, например: 1) М == (М): д (Х, е) = (Х вЂ” е)'с ММ (Х вЂ” е) — семейство махаланобисского типа, где М— положительно определенная, симметрическая матрица; а 2) М = (Л =- (Лг, ..., Ла) Е )та, Л!» О, П Л! = ! ): й (Х, е) = !=1 Р = ХЛ!!х! — ег! — семейство «сити блок» (СИу В!оск) '. Пространством й предстоеительсте Е» для пространства покрытий Я» называется множество наборов ! = (1„..., 1»), 1! б ~.. Для построения представительства 1 покрытия В = = (о ". о»): 1) выбирается пространство представителей Б и мера сходства Р (Х, !); 2) выбирается 4ункция предстаеителасп!ео л', относя- ' В литературе ивогда мстрвав этого семейства ааэываютса маахэттенскими.
щая к классу 5; представителя 1ь т. е. й (ЗД = 1;. Напри- мер, о (5«) =- ага ппп ~' Р (Х, 1). х-э, Для построения покрытия 5 -- (5„..., 5»), отвечающего представительству 1= (1м ..., 1„): !) выбирается пространство покрытий 5"; 2) выбираешься функция назначения), с помощью которой каждый объект Х получает «назначенне» в тот или инон класс, т. е. 1 (1) = 5. Например, 1 (1) — минимальное ди- станционное разбиение выборки Х, порожденное набором 1 — — (1,, ..., 1») относительно меры сходства Р (Х, 1).
Метод динамических сгущений состоит из следующих частей (этапов): !. Выбор пространства покрытий 5". 2. Выбор пространства представителей Е и меры сходст- ва Р (Х, 1). 3. Выбор оптимизируемого критерия Ю' (5, !), позволя- ющего, используя Р (Х, 1), измерить «степень адекватности» между всяким покрытием 5 с 5" н всяким представитель- ством этого покрытия 1Е 1. Критерий )Р' строится обычно так, чтобы он принимал только неотрицательные значения. 4. Постановка задачи минимизации критерия (Р'; вы- бор функции представительства д и функции назначения 1, позволяющих решать эту задачу.
5. Построение алгоритма динамических сгущений (АРС), состоящего в последовательном итеративном использовании функций ! и и, начиная с некоторого покрытия 5пп с 5» или представительства 1<м с й». 6. Изучение свойств сходнмости алгоритма динамиче. скнх сгущений. 7.4.2. Алгоритмы классификации. Основная цель настоя- щего раздела — изложить подход МДС к построению алго- ритмов автоматической классификации. Подробное описа- ние, практические рекомендации и примеры применения этих алгоритмов содержатся в! !06).
У всех рассматриваемых ниже алгоритмов одинаковыми явл яютс я: пространство й покрытий 5» — множество всех разби- ений 5 = (5„..., Зх) совокупности Х на й непересекающихся классов; еид оптимизируемого критерия В' (5, 1): Ф" (5, !) = 'Я Р(Зм 1»), с где 5= (Зм ..., Зь), 1= (1м ..., 1ь), Р (Зн 1«) = „'Р Р (Х 1«) хмэ« — разброс 1-го класса 5~ относительно представителя (ядра) 1, и Р (Х, 1,) — некоторая мера сходства между объектом Х и представителем 1,; способ построения функции назначения 1.
При выбранных ядрах классов (1„..., 1„) и мерах сходства Р (Х, 1,) объект Х относится к 1-му классу по правилу минимального дистанционного разбиения; 1(1м " 1»)=(5м ". ° 5») где 5» =(Х б Х: Р (Х, 1») = пп(п Р (Х, 1»)) ья/~ » /-~ 5/= Х~ Х ) 1.) 5~: Р(Х, 1/) = ппп Р(Х, 1~), 2(1(й; с з /с/.- д способ построения функции представительства д. При выбранном пространстве представителей 1. задается пространство представительств 1' как подмножество наборов (1,, ..., 1») с Ь х .. х 1, = ((.)», выделяемое в (1.)» некоторыми условиями. Тогда для заданного разбиения 5 = = (5„..., 5») его представительство д (5) находится как решение задачи условной минимизации критерия й' (5, 1), т.
е. у (5) = агй пип Ф'(5, 1). и ь»с~т» В наиболее важном частном случае, когда Ь»= (1.)», представительство у (5) находится'как решение задачи безусловной минимизации на 1.: у(5) =-(у(5»), " у(5»)) где у(5,)=агат(п Р(5п 1). сес Схема алгоритма 1. Выберем начальное разбиение 5» = (5',, ..., 5»). 2. Пусть построено т-е разбиение 5"' = (5,, ..., 5 ).
Найдем т-е представительство (набор ядер) 1"' = у (5"'). 3. Найдем (т + !)-е разбиение 5"'+' =1(1'"), 4. Если 5"'+»чь 5"', то переходим к 2, заменив т на т + 1. Если 5»' = 5, то полагаем 5 = 5» и заканчиваем работу алгоритма. ,г(ля получении конкретного варианта алгоритма клас- сификации по приведенной схеме достаточно опнсать только следующие его компоненты: а) пространство представителей 1.; б) меру сходства 11(Х, 1), Х Е Х, 1 Е 1,; в) условия, выделяющие пространство представительств » а ( ~ ) В приведенных ниже алгоритмах будем использовать терминологию н, по возможности, обозначении из [106).
Пусть П (Х) — множество подмножеств исследуемой со- вокупцостн объектов Х =- (Х,, ..., Х„). Лля Р с П (Х) обо- значим через )Р ~ число элементов (мощность) множества Р. Предположнм, что на Х задана положнтельная нормн- рованная мера (распределение массы) 1», т. е. функция р(Х))0, ХЕ Х, такая, что ~' 1»(Х) =1. хех Опишем сначала компоненты а, б, в алгорнтмов, в кото- рых представителями классов являются подмножества то- чек классифицируемой совокупности Х, т. е. 1. с: — П (Х).
1. Метод ядерного разбиения а) Ь=П(Х); б) 11(Х, Р)= ~', 1»(Х)р(1')й(Х, г'), УЕРС:Х где й (Х, У) — некоторая мера близости между объектами нз Х; ,)' Ь» =. (ц», 2. Метод, использующий ядра фиксированной мощности а) 1 й(т)=(Р»;П(Х):[Р(=т); б) (г(Х, Р) ~~~~ р(Х) -ц~ — 1- й(Х, г'); УЕР~Х в) Е»=(1. (т))'. 3. Метод, использующий ядра переменной мощности а) 1.=».(р)=-(РЕ П(Х):р(Р) ~ 1»»), где р (Р) =- ~' р (г") н р, — фиксированный уровень Уее массы ядра; б) 1у(Х, Р) = ~~~ р(Х) -"-~-')-й(Х, у); УЕРСХ в) 1.» = (1.(1»))». Следующая группа алгоритмов нспользует в качестве ядер точки пространства признаков (формальные объекты). 234 Будем считать, что пространством признаков является )с», т. е. Х с )г».
1. Метод центра тяжести а) 1 =»г»; б) Р (Х, 1) = р (Х) д (Х,!), где й (Х, !) =- (Х вЂ” 1) М (Х вЂ” !) — квадрат расстояния махаланобисского типа и М вЂ” фиксированная симметри- ческая положительно определенная матрица. Разброс 1-го класса 5' относительно ядра Е с )х» в этом слу- чае имеет вид Р (5', 1,) = ~ р. (Х) (Х вЂ” 1,)' М (Х вЂ” 1;); хез' в) Е»=()г»)» Когда р (Х) = 1!и, где и = (Х! и М вЂ” единичная матрица, то этот алгоритм представляет собой алгоритм А-средних параллельного типа. 2.
Мепюд адаптивных расстояний а) Е = — Р'хРЫ, где Р!з! — некоторое семейство мер сходства в Я»; б) 0 (Х, 1) = д (Х, е), где 1 = (е, д), е с»х», д с РЫ; в) 1.» с: (Е.)». В (10б! исследуются отдельно варианты с квадратичны- ми и неквадратичными расстояниями. Квадратичные расстояния. В этом случае РЫ = (М): : с( (Х, е) = (Х вЂ” е)' М (Х вЂ” е) — семейство махалано- бисского типа. 1.
Независимый выбор меры сходства для каждого клас- са, т. е. Е" = (1.)', и представитель (ео М~) 1-го класса 5; находится как решение задачи: (е», М!)= — агя пнп ~ч' (Х вЂ” е)' М(Х вЂ” е), »ея» хез мео и где РЫ, — подмножество в Р!з1, составленное из матриц с определителем, равным 1. Решая эту задачу, получаем (см. гл. 1!) е~ — — Х (5Д— центр класса 5о М, — !Х»!Н»Х-,', где Х~ — ковариационная матрица элементов 1-го класса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
