Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 55
Текст из файла (страница 55)
Х). (10.2) Положим К (з, Х) = з, если Ь (з (Х), Х) = ш!и Л (и, Х); (10,3) К(з, Х) =-з(Ф Х), если дчъз(Х) и юу=агнш!пб(п', Х). Опишем алгоритм равномерного распределения объектов по классам, в котором классификатор К действует по формуле (10.3). В этом алгоритме критерием качества разбиения выборки О на классы О (1), ..., О (й) является сумма попарных внутриклассовых расстояний между объектами (см. п.
5.4.1), т. е. Р (з) = ,"~ Р» (О (д)), где д=! Р,(О(д))= ~ 1Х,— Х»Р. (10.4) х,. х,»о<»> Пусть Ы (О (4)) — статистический разброс класса О (4), У» — центр этого класса и и — число элементов в нем. Заметим, что Г (О(4)) = 2а И (О (и). Пусть классификация з относит данный объект Х с О к классу О (!). Положим О' (1) = О (1) Х .Непосредственно из формул (10.2) и (10.4) получаем: А(су, Х)=2(Н(0(су))+идфХ вЂ” Уч~а), если и-ь1 и Л (1, Х) = 2 (с((0' (1))+ (и, — 1) ~ Х вЂ” У; )а), где У) — центр класса 0' (1). Таким образом„процедуру перехода к новой классификации К (э, Х) можно в этом слу- чае описать следующим образом.
Дана выборка 0' == 0- Х, разбитая на классы 0' (д), д =- 1, ..., й, где 0' (д) = 0 (д), если д чь 1. Поступает на классификацию объект Х, не принадлежащий выборке О'. Рассчитываем для каждого класса 0' (д) его центр г", статистический разброс г1 (О' (д)) и число элементов л'. Ме- ру близости р (Х, 0' (г1)) между элементом Х и классом О' (д) задаем формулой: Р (Х, 0' (су)) =- а (О' (д)) +пе(Х вЂ” Уе)т.
(10.5) Тогда классификация К (з, Х) относит элемент Х к ближай- шему классу в смысле меры близости (10.5). Классификатор К (1О 3) применим и в случае, когда име- ется дополнительная информдция о допустимой принадлеж- ностиэлементов к классам, т е. имеетсяфункция гр: О-ь.2к (см. определение 10.!). Тогда, например в алгоритме рав- номерного распределения объектов классификатор К (з, Х) отнесет элемент Х к ближайшему из классов 0' (д), где д б ~р (Х) с: Л =- (1, ..., к). Рассмотренные выше классификаторы (10.1) и (10.3) действуют только в процедурах последовательного типах. Для построения классификатора в процедурах параллель- ного типа обычно используются функционалы г": Ло х 1.
-е. -ь Я' вида ~ч(Х, 1(,1)), 1 в [х) =е где Р (Х, 1(д)) описывает, насколько объект Х близок ядру 1(д), этом случае классификатор К можно взять в виде: К(а, 1, р)(Х) = /Ч= агош(пРч(Х, 1(9)), ХЕ Р (10.6) (з(Х). ХЕ р. Если функционал г ч (Х, г) не зависит от номера класса д, ' Точнее, только в процедурах последовательного типа можно гарантировать убывание глобального критерии г" (а) при переходе к навоз классификации, по форму,че: Р (з, 1) (д) = агц ш 1п Р (О (д), У).
уеуо П0,7) Таким образом, для вычисления значений О (з, 1) (д) дескриптора 0 необходимо применить некоторую процедуру минимизации функционала Р, (0(д), У) на Уо. Наибольшее распространение получили алгоритмы АК, в которых в качестве тс (О (д), У') используется статистический разброс класса 0 (д) относительно У ~ Уо, так как в этом случае удается получить явное решение задачи минимизации и заменить формулу (10.7) явной формулой расчета ядра д-го класса по элементам этого класса. П р и м е р 10.6. В алгоритме й-средних имеем Уо = =- ттр и тчч (О (д), д) = ~' ЦХ вЂ” Уц'.
ПоэтомУ хе о оп Р(з, 1)(д)= ~~)' Х. 1 (ч) 1 „ о оп П р и м е р 10.7. Опишем алгоритм типологического главного фактора (106). Пусть 0 —.- (Х„..., Х„) с: )ср и 2 = (1„, й). Ядро класса У описывается парой (У, о), Уб 1тр, в 61тр, |~о~~.— "1, а мерой близости от точки Х до ядра У =- (У, и) считается квадрат расстояния от точки Х до прямой, проходящей через точку У с направляющим вектором в, т. е. Р„(Х, У) =1(Х вЂ” У) — и' (Х вЂ” г') в~~.
(10.6) Допустим, что на и-м шаге алгоритма совокупность 0 разбита на й классов 0(1), ..., 0 (й). Статистический разброс то классификатор (10.6) совпадает с функцией назначения д: 7.-э-5о (см. $?.4). 10.1.6. Дескриптор Р. Эта компонента представляет собой оператор из 5о >, Е в 1., называемый дескриптором, поскол ьку с его помощью на основании предыдущего описания 1 выборки 0 и полученной классификации з„,~, вырабатывается новое, более оптимальное описание. Частным случаем оператора О является функция представительства 5о — э-+. й.
В алгоритмах АК, основанных на описании классов ядрами, оператор О строят исходя из функционала Р: 5 х ХŠ— «Р' вида Р(з, 1) = ~', Рч(0(д), 1(д)), ч=- ~ класса О (д) относительно г = (1', п) вычисляется по формуле: Ре(0(д), У) = ~г 1(Х вЂ” У) — о' (Х вЂ” У) о1г. (10.9) хе о оп й(инимиэируя функционал (10.9) на пространстве Ко = = (У =(У, о), )'Е Яе, об )ге, !!о!!=1), получаем, что Х) (э, 1), (д) =-: (У (д), и (д)), где У' (су) — центр класса 0 (д), о (д) — собственный вектор с наибольшим собственным значением ковариационной матрицы класса 0 (д), т.
е. главная компонента этого класса. На (т + 1)-м шаге этого алгоритма применяется классификатор (10.6), т. е. строится минимальное дистанционное разбиение, порождаемое набором ядер ((У' П), о (1)) ..., (У (й), и (й)) ) для меры близости (108). Алгоритм останавливается, если новое разбиение имеет тот же набор ядер, что предыдущее. 10.1.6. Основные понятия и определения, используемые при исследовании математической модели АК. Опираясь на материал п. 10.1 1 — 10.1.5, естественно дать следующие определения. О п р е дел е н и е 10.2.
Моделью алгоритма АК называется набор его компонент (Зо, 1., Р; К, Э, О), наделенных описанной выше структурой. Оп р едел е н не 10.3. Движением алгоритма, отвечающим начальным данным в, Е 5о, (г Е 1. и рг Е Р, называется последовательность (во 1о) (вг 1з) "' (э 1ы) где вт+1 = К (вы~ 1тв~ Рп5 1т+з = гг (вт+и (га)~ Рт+г = =- О (р, в +„1 +„т + 1). О п р е д е л е н и е 10.4. Алгоритм АК называется сходящимся, если для его движения (эм 1г), ..., (в, 1 ), ... последовательность описаний 1„..., 1,, сходится в метрике пространств 1.
к некоторому предельному описанию Алгоритм АК называется стабиливирующимся, если существует номер тю такой, что 1 = 1, для всех т ~ те. О п р е д е л е н и е 10.5. Функционал Р:5о х 1.-+ 1~ж называется интерпретирующим для модели ААК, если Р(з., 1,.)» Р(эта„1,.); (10.10) Р(вэь+д~ 1юю) » Р(эш+х 1ш+ю) (10.11) для всех т, начиная с некоторого т,.
Таким образом, если функционал Р рассматривать как меру потерь при задании выборки 0 в состоянии (классификации) э ее описанием 1, то неравенства (10.10) и (10.! 1) служат объяснением, почему от состояния в при фиксирован- 10.2. Базисная модель алгоритма АК, основанного на описании классов ядрамм Пусть Р а (Х, У) — некоторая мера близости между объектом Х и точкой )' пространства г'л, называемого пространством ядер 4-го класса.
Лля класса 0 (д) с: 0 и точки У саул определим меру близости Рл (О (и), )') формулой Р, (О (4), )') =,г Р,(Х, У). (10.12) Хво <а1 1О Заказ № 291 ном 1 переходим к состоянию з +, — — К (з, 1, р ) и от описания 1„, выборки 0 при фиксированном з +, переходим к 1 +, — — 0 (з„,+,, 1 ). Для данной модели алгоритма АК, очевидно, может существовать много интерпретирующих функционалов, причем роль их при исследовании данного алгоритма может быть различной П р и м е р 10.8. Рассмотрим алгоритм Форель (см. п. 7 2.1), выделяющий в выборке 0 =- (Х„..., Х„) ~ Р' несмещеннУю подвыбоРкУ Оа = (Х с 0: 1Х вЂ” г'а) ( г), где г — парамелр алгоритма, а à — центр класса О„который находится как результат стабилизации последователы ности описаний У„..., У При исследовании этого алгоритма используются два интерпретирующих функционала: Р,(0, У' )= ~ )Х вЂ” У' Р+гз(л — и ); хе о,„ Р,(0, У' )= э ЯХ вЂ” 1' зз — гз)= з К(1 йх — 1' й') хео .С,> га где ( ° )+ (.), если ( ) з О, и ( ° )+ — — О, если (.)( О.
Здесь 0 — класс, выделенный на т-м шаге алгоритма, У с Ка — описание класса (его центр) на этом шаге и л =- 10 Используя Р„получаем, что стабилизнруемость движения алгоритма Форель является следствием легкодоказываемой стабилизируемости движения алгоритма 2-средних (см. (41, 42)). В терминах Р, доказать стабилизируемость труднее (27), но зато, используя этот функционал, получаем, что предельное описание )'а является точкой локального максимума оценки плотности распределения случайного вектора по выборке 0 (см. $7.6).
О п р е д ел е н и е 10.6. Математическая модель АК, в которой 5о ~ (О- с), где л = (1, ..., й) — список имен классов, и классификатор задается формулой К...),„, (Ч=-йш пР,(Х 1(4'И Х~р =О („„) (з (Х), Хе р, а дескриптор — формулой О(з, 1) (д)= агд ш!и Гч(О(д), У), (10.14) е ч где с (О (у), У) имеет вид (10.12), называется базисной моделью алгоритма АК, основанного на описании классов ядрами. Далее для краткости эту модель алгоритма будем называть базисной моделью ядерного алгоритма. Опишем ядерный алгоритм, в модели которого мера близости г" ч (Х, У) между объектом Х и ядром д-го класса У зависит от дополнительной информации об этом классе. П р и м е р 10.9. Пусть О = (Х„. „, Х„) с:.
)1» — классифицируемая совокупность объектов и У= (У„..., У»)с: с:. 1«» — обучающая выборка, где У = (Уч»!, ..., У'„)— представители д-го класса, причем ~" пч «и и не исключач =- ! ется, что множества Уч для некоторых д пустые. Рассмотрим задачу разбиения выборки О на й классов. Так как обучающая выборка У мала, то применить обычные процедуры классификации при наличии обучающих выборок не представляется возможным. Для решения этой задачи можно рекомендовать алгоритм АК, описываемый базисной моделью ядерного алгоритма с г »ч Рч(Х, У)= чз ~!Уч! — Х))'-!- ) (Уч! — Х)», (10,15) 1=1 »= 1 где У = (У „..., У г ) — ядро д-го класса, составленное из точек пространств»1», а Тч — максимально возможное число вводимых эталонов в !Г-м классе, д = 1, ..., Й. Любой алгоритм АК, описываемый базисной моделью ядерного алгоритма, допускает две важные модификации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
