Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 49
Текст из файла (страница 49)
Как указывалось в гл. 6, число Й должно удовлетворять условиям, гарантирующим сходнмость (9.102) к истинному распределению при Ж[ — )-оо, т. е. 0(й(05. (9.103) Поэтому интеграл произведения двух плотностей вероятности можно приближенно записать в видв С р(Х(и,) р(Х(и,) А» ~ Же Жа ,~, (])е у ) — 1 ~ ~~~) ~ (2 ) — ~ (/[/ д )1]][ ] т, ] — 1/2 ] ~ ] — 1/2 2=1]=1 У + л' д '(х — х,) х (х — х,)] ах = — 1 Х1 ~~ (2 ~) — п]2(/)/ у ) ] Лр2 ии2 + а'р1 Х1 [ Х (де 1и а 2) 2=1] 1 с ,, ) [р(ад~ )Х, е[~~иих,] '(Х,.— ХД].
Х ехр 2 Р 2» "-) (9.104) и (9.104) представляет собой выборочное средо опарнь х сстоя ий ностей ве оятности п нев нормальных плотнос 2д»е — 2](]еп)~ 1д»е — ' и ~ + -2ЛИ ) между кла классами с весом 1 1 2 а и актике, поскольку ольши б ие значения (Х, — Х,) дают ный вклад в (9.104), при вычислении границы ве- незначительный вклад в и ки используют лишь объекты с небольшими в б ана таким образом чтобы в не по- рования должна быть выбрана таким о непа аметрических критериев разделимости ъекты обоих классов. в можно вывести неравенства типа классов мо ие ядра «гиперсфера радиуса и» .
В частности, использование ядер. ите ию который вычисляется следую- приводит к простому критерию, аж ого Х; (Х,~()1,) подсчитать число объектов Х„ 2) Вычислить среднее всех чисел, полу (9.104) и к ите ия аналогичен выводу критерия Вывод этого критерия а Этот критерий будет исв качестве упражнения. тот оставляется в р методов автоматичвской клас- пользован д. ля непа аметрических метод в гл.
11, и его свойства у будут подробно изучены. е мето получения верхней границы веРассмотренпый1 выше метод получен ни э, е ффективиости полученной границы рассм дредедени1е, где иаи ~ [р ( (и,) р ( пределе1 ", Х 19 Х/со2))1]2дх,, нормальных распределе1 1!2 итически: так и р(хйо)) р( ю, С р (Х(ие) р(Х]и,) ШХ = [(2д) "[ Х,] Иа]Х,[ а ] Х М ) Х вЂ” '(Х вЂ” М ) -[- (Х вЂ” Ма)'Хе '(Х вЂ” Ма)]]еи 2 , (22Т) — (2 ]~,+ ',р ] — 1]2 ехр — —.
(М1 — ~[~2)'(~1+ ~А'2) (~1 2) (9.105) 288 289 'ь );. 1-й член ив (9.58) 2-й член иа (9.58) (9.109) при а=З (9.58) (9.106) 1,27 1,08 0,90 2,35 2,17 а+Ь а+с (а+Ы -(а+с) 0,096 0,114 (9.110) Рис. 9,2. Выбор радиусов г,. 1 — 1п (9. 109) (9.11З) 10 к, Фукунага ГЛ, 9, СЛУЧЛй МНОГИХ РЛ('ПРЕИЕЛЕНИй — 1п [А )' Р (Х)и,) р (Х1и ) АХ) ме 2 ~ 4 и (9.106) Сравнивая (9Л06) с (9.58), видим что эт ычислим А как объем эллин построенного на собственных векторах матриц Х! и р . псоида, р2-мерного эллипсоида с радиусами г! г ... г равен иусами г), г2, ..., г„по главным осям А = (2г)г2... г„л"'2)! [пГ(п/2) ~. (9Л07) П е р дполагая, что плотности нормальных асппе е брежимо малы на р с на расстояниях, больших ап можн льных расппеделений прене- следующим образом: б, можно выбрать г, г, = а(1+ )(!),,).
(9Л08) На рис. 9.2 показано, как выбираютс . Н я г апомним что пос- ле одновременной диагонализации 1 и ',!3, и',~ 1 являются стандартными отклонениями соответственно класса 1 и кж„2 и 1+1 — ~~ 1п 1+2 р'7), +7~. 4 а~ + ро" е (9 58) (9 1061 стандартных данных ю = 1, 2 приведены в табл. 9.2. ) для $9.3.
ГРЛНИЦА ЧЕРНОВЛ И РАССТОЯНИЕ ВХЛТАЧЛРИЯ 9.3.4. Случай многих классов. Как уже говорилось в связи с дискриминантным анализом, ни один из критериев, взятых в отдельности, не является особенно хорошим индикатором разделимости в случае многих классов. Однако процедуру вычисления верхней границы вероятности ошибки можно обобщить на случаи многих классов [Лайниотис, 19691.
Пусть,е и ея, Таблица 92 !(ачество оценки, найденной с помощью неравенства, Иенсена ~, 7 = 1, 2, ..., ЛХ вЂ” общая вероятность ошибки и вероятность ошибки при разделении классов 1 и 7'. В таком случае е м м Е~~ ~А ~А Е(;. 1)! 9=! Так как верхняя граница еи определяется границей Чернова или границей Бхатачария, то комбинация этих границ и (9.110) дает верхнюю границу е в виде м м е( ~ ~ Р(и,)' "еи Р(иА"~ (р(Х!иА' "' р(Х)иА"'АХ, (9.111) (>1)=! Р где оптимальные значения гп определяются соответствующими парами классов, но для простоты можно использовать гп — — 0,5, 2,~=1,2,...,ЛХ. Воспользовавшись неравенством [Р ((о,.) Р (оэ,)1(~2 ( — „ (9.112) можно определить верхнюю границу вероятности ошибки е следующим образом: м м е( — ~~ ~ ) (р(Х/и;) р(Х/и;))'~еАХ. (>1 )=! у 290 ГЛ.
9. СЛУЧАЙ МНОГИХ РАСПРЕДЕЛЕНИЙ $9.4. ДИВЕРГЕНЦИЯ 291 5 9.4. Дивергенция Дивергенция представляет собой меру разделимости классов, аналогичную расстоянию Бхатачария. В распознавании образов одной из ключевых характеристик является отношение правдоподобия или — 1п 1Р (Х/1о ! ) /Р (Х/о2) ), где Р(Х/о!) и Р(Х/о2) — плотность вероятностей классов о! и св2. Поэтому, если бы мы имели возможность оценить плотности или функции распределения вероятностей для классов 1о! и о2, это было бы почти эквивалентно оцениванию вероятности ошибки. К сожалению, это нелегкая задача. Простейший вариант этого метода заключается в том, чтобы использовать математическое ожидание отношения правдоподобия для классов о! и о!2 и оценивать разделимость классов по разности математических ожиданий.
Таким образом, дивергенция определяется следующим образом: Р Р Рис. 9.3 иллюстрирует это определение. Так как при вычислении дивергенцин рассматриваются только математические ожи- %~ ~ Ьг Рис. )),3. Плотности вероятности отношения правдоподооия.
дания, нельзя ожидать близкой связи между дивергенцией и вероятность!о ошибки. Более близкую связь можно получить, включив в выражение для дивергенции моменты более высокого порядка, но в этом случае критерий становится очень сложным. Из того, что говорилось в отношении границы Чернова (см. (9.63) — (9.78)), ясно, что дивергенция Р (9.114) пе зависит от системы координат и аддитивна относительно независимых переменных, а также удовлетворяет всем свойствам метрики. Если плотности р(Х/о!), 1 =. 1, 2, нормальны, то выражение для дивергепции принимает вид — и 2 )п )р ~ ]!)2л) — »1~ /2,) '" ехр ~ — — )Х вЂ” ЛХ,) т7')Х вЂ” М,)]— 2 (2л) — ")2] Х ] — !)2 ехр — — (Х вЂ” ЛХ )' Х! ' (Х вЂ” ЛХ2) АХ = —, (М, — М,) (Х ! + Х2 ) (М, — М,) + ! 2 + 2 1г (Х! 2'2+ Х2 Х, — 21).
(9.115) Если ковариационные матрицы одинаковы, т. е. Х! = Х2 — — Х, то (Л~! Л~2) ~' Я1 Л~2) ° (9.116) Сравнивая (9 116) с (9 55) и (9 58) видим что в случае равных ковариационпых матриц Р = 8р()/2), т. е. в этом случае дивергенция и расстояние Бхатачария совпадают с точностью до постоянного множителя. Кроме того, так как (9.116) совпадает с 2т~ из (3.34), то дивергенция в случае равных ковариационных матриц однозначно связана с вероятностью ошибки.
Это же утверждение справедливо и для границы Чернова и расстояния Бхатачария. Выражение для верхней границы вероятности ошибки в зависимости от дивергенции неизвестно. Для случая многомерного нормального распределения эта зависимость была найдена экспериментально методом Монте-Карло ~Мэрил, 1963~ (рис. 9.4). Для данного значения дивергенции вероятность правильного распознавания (т. е.
единица минус вероятность ошибки) находится между двумя показанными на рисунке кривыми. Верхняя кривая показывает зависимость между вероятность!о правильного распознавания и дивергенцией для случая многомерного нормального распределения при равных ковариационных матрицах. Нижняя кривая показывает эту же зависимость для одномерного случая. Процедура выбора признаков с использованием дивергенцип в случае нормальных распределений почти такая же, как и при использовании расстояния Бхатачария, и заключается в следующем: $0'РР— (Х вЂ” ЛХ,) Х (Х ЛХ,) (Х вЂ” ЛХ) Х (Х вЂ” ЛХ)— 293 5 9.4.
ДИВЕРГЕНЦПЯ 292 з ! 6 )1! 8,41 111! — 1!9! 3,86 .0 11,6 32,1 0,12 0,22 0,84 0,84 28,2 31,4 78,1 87,0 2,73 0,01 36,1 100,0 12,06 3,10 21,9 60,7 1,49 1,64 33,8 93,6 1,77 1,08 34,8 96,4 0,35 0,26 35,6 98.7 % Фактическая ошибка, оо 4,7 3,8 1,9 2,5 13,9 6,0 2,2 2,0 Процедура б) Р7 ' ~~-г ~-~ ~~в ~~~ ~г ~~г ,Дамир гею~~ия Соответствующее 79! из а) Р„.о,о+)„. -о, 9)9 .0 5,10 4,34 36 О 36,1 99,6 100,0 )16 10,42 33,5 92,6 791 14,14 10,53 27,2 31,0 75,2 85,9 114 6,77 34,8 96,3 791 5,21 35,4 98 1 22,5 62,2 %9 (9 120)' -4М' ГЛ. 9. СЛУЧАЙ МНОГИХ РАСПРЕДЕЛЕН!1Й 1. Для пврвого члвна (9 115) оптимальный признак опрвдвлявтся слвдующим образом: 7),1 = (ЛХ, — ЛХ,)' (Х! + Х2 ) (ЛХ, — ЛХ,)„(9.117) 7),2 = 7),з = ° ° .- — — 7),„= О, (9 118) Ф~!' = (Х1 '+12 ') (ЛХ1 — ЛХ )/[(ЛХ,— ЛХ,)' (Х! '+Х2 ') (ЛХ1 — ЛХ,)]' (9.119) Этот вдинстввнный признак являвтся достаточным. Пврвый члвн Рис.
9.4. Границы вероятности правильного распознавания в зависимости от дивергенции [Мэрил, 19631. првдставлявт собой диввргвнцию, обусловлвнную различивм срвдних значвний. 2. Второй члвн првдставлявт собой диввргвнцию, обусловленную различивм ковариационных матриц, а оптимальными признаками являются собственные ввкторы матрицы Х! Х2. Наиболвв важныв т признаков опрвдвляются путвм упорядочвния собстввнных значвний слвдующим образом: Это можно первписать как (7),1~'~+ 7),~ ~'~) > (7),~2'~+ 7),2 ~'~) ) ) (7),"' + 7), ~д)'. (9.121) Порядок (9.121) совпадавт с порядком (9.92) при 8 = 0,5.
Слвдоватвльно, дивергвнция и расстоянив Бхатачария приводят к выбору одних и твх жв признаков для второго члвна, 9 ) ь 9 3. Если трвбувтся найти оптимальныв признаки, то, поскольку мы не располагавм аналитичвской процвдурой, приходится использовать числвнныв мвтоды поиска ~Тоу, 1967]. Однако, если нв трвбовать строгой оптимальности, то для выбора признаков можно использовать слвдующив процвдуры. а) Можно взять в качвствв приближвнно оптимальных признаков признаки для второго члвна, т. в. собственныв ввкторы матрицы г.~ ~Х„в надвждв, что пврвый члвн Р можно выразить нвТаблица 9.3 Выбор признаков для максимизации дивергенция Процедура а) большим числом этих признаков. Выбор признаков производится в слвдующвм порядкв: ((1 ~- 1Р,,) (а„4,) 2+ 7, + 1Р ) >...
...> ((1 -)- 1/7),„) (д)„— а29)'+ 7),„+ 1/Х„), '(9.122) где (д)1 — д21) опрвдвлвно в (9.96). Если таким образом выбра ны т признаков, то 19) Р = 1 ~ И1~-1)1,)),)„— а„)')-1,-91)1; — 2!. (9.123) 1=1 295 294 ЗАДАЧИ К задаче 9.1. ЗАДАЧИ ГЛ. 9, СЛУЧАИ МНОГИХ РАСПРЕДЕЛЕНИИ б)' Если доминирующим являвтся пврвый члвн О, то собстввнный ввктор Ф) (9.119) — наиболвв эффвктивный признак. По- (1) этому сначала выбирают Ф) х а остальныв т — 1 выбирают из ($) числа признаков для второго члвна 1л. В этом случав признак Ф1 ()) нвортогоналвн к другим признакам.
П р и мор 9.6. В табл. 9.3 приввдвны рвзультаты вычислвния диввргвнции и выбора признаков для стандартных данных г = 1, 2. Признаки отбирались и упорядочивались в соотввтствии с процвдурами а) и б). ЗАДАНИЕ НА СОСТАВЛЕНИЕ ПРОГРАММ Составьте следующие программы. 9Л. Программы выбора признаков методами дискриминантного анализа с использованием критериев 1ь 12, Уз и 14. Используйте матрицы рассеяния Яьп Я и Я Исходные данные: а) стандартные данные ( = 1, 2, 3, 4 для задачи со многими классами; б) стандартные данные ( = 1, 2 для задачи с двумя классами.
9.2. Программы выбора признаков для максимизации расстояния Бхатачария с использованием следующих признаков: а) собственные векторы матрицыХ~ ~Х,. Г 1 1 — $ б) комбинация ~ 2 (Х1+ Х2)~ (М1 — М2) и собственных векторов матрицы Х~ Хз. в) исходные переменные. Исходные данные: стандартные данные ( = 1, 2. 9.3. Постройте график зависимости границы Чернова от з и найдите оптимальное значение з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
