Дуда Р., Харт П. - Распознование образов и анализ сцен, страница 6
Описание файла
DJVU-файл из архива "Дуда Р., Харт П. - Распознование образов и анализ сцен", который расположен в категории "". Всё это находится в предмете "распознавание изображений" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "распознавание изображений" в общих файлах.
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 6 - страница
Так как эти события взаимоисключающие и составляют полное множество событий, то Р (ошибка)=Р(хЕЯ„а,)+Р(х~Я„ае) = = Р (х ч Я, ! ас) Р (а,) + Р (х ч Я, 1 а,) Р (а,) = = $ р(х ~ а,) Р (а,) е(х+ $ р (х(ае) Р (ая) г(х. (18) Ма Ае Этот результат для одномерного случая иллюстрируется рис. 2.6. Два слагаемых в этом выражении, по существу, представляют площади, накрываемые «хвостамн» функций р(х(а,)Р(а,). В силу Га. 2. Байесаеская теорне решений произвольного выбора в», и е!», вероятность ошибки в примере не столь мала, как могла бы быть. Ясно, что, смещая границу области решений влево, можно свести на нет площадь темного «треугольника» и тем самым уменьшить вероятность ошибки.
Вообще, если Р(х!в!)Р(в!))Р(х!в«)Р(в»), то выгоднее иметь х в области и»„ чтобы вклад в интеграл был меньше; именно это и достигается применением байесовского решающего правила. В случае многих классов больше возможностей допустить ошибку, чем оказаться правым, так что проще вычислять вероятность верного решения. Ясно, что Р (отсутствие ошибки) = ~~'.' ,Р(хай!, в!) = с=! с = ~~'., Р(х~йс~в;) Р (в;) = с=! с ~ р(х ) в!) Р(в!) ссх.
с=! ед, (19) Полученный результат остается в силе независимо от способа разбиения пространства признаков на области решений. Вайесовский классификатор делает эту вероятность максимальной за счет выбора областей, для которых интегрируемые величины наибольшие, так что никакое другое разбиение не приведет к меньшей вероятности ошибки. 2РД НОРМАЛЬНАЯ ПЛОТНОСТЬ Структура байесовского классификатора определяется в основном типом условных плотностей Р(х~в!). Из множества исследованных функций плотности наибольшее внимание было уделено многомерной нормальной плотности распределения. Следует признать, что это вызвано в основном удобством ее аналитического вида.
Вместе с тем многомерная нормальная плотность распределения дает подходящую модель для одного важного случая, а именно когда значения векторов признаков х для данного класса в; представляются непрерывнозначными, слегка искаженными версиями единственного типичного вектора, илн вектора-прототипа, р;, Именно этого ожидают, когда классификатор выбирается так, чтобы выделять те признаки, которые, будучи различными для образов, принадлежащих различным классам, были бы, возможно, более схожи для образов из одного и того же класса.
В данном разделе приводится краткое описание свойств многомерной нормальной плотности распределения, причем особое внимание уделяется тем из них, которые представляют наибольший интерес для задач классификации. хя7. Нормальная охотность 33 2.7Л. ОДНОМЕРНАЯ НОРМАЛЬНАЯ ПЛОТНОСТЬ Рассмотрим сначала одномерную нормальную функцию плот- НОСТИ р(х) =- ехр~ — — ~ — ') ~, (20) для которой о Е[х) =. ~ хр(х) йх=)ь о (21) о Е [(х — р)'1 = ) (х — р)* р (х) дх=о'. о (22) 2.7.2, МНОГОМЕРНАЯ НОРМАЛЬНАЯ ПЛОТНОСТЬ Многомерная нормальная плотность распределения в общем виде представляется выражением р (х) = ехр [ — — (х — )я)'Х-' (х — )ь)1, (23) (2я)о'~ 1 2 1 ь а где х есть й-компонентный вектор-столбец, )я есть д-компонентный вектор среднего значения, Х вЂ” ковариационная матрица размера йкд, (х — [я)' — транспоннрованный вектор х — )ь, Х-' — матрица, обратная Х, а [Х [ — детерминант матрицы Х.
Для простоты выражение (23) часто записывается сокращенно в виде р(х) л7([я, Х). Формально можно написать )ь=Е[х[ (24) (26) Х = Е [(х — )ь) (х — 7я) 1, где ожидаемое значение вектора илн матрицы находится поэлементным вычислением математических ожиданий компонент.
Выражаясь конкретнее, если х, есть Ья компонента х, и~ есты-я компонента р, а ам есть (1-7)-я компонента Х, то получаем 1ь~ =Е[хд) (26) Одномерная нормальная плотность распределения полностью определяется двумя параметрами — средним значением р и дисперсией оь. Для простоты уравнение (20) часто записывается в виде р(х) Л'(р, оь), что означает, что величина х распределена нормально со средним значением р и дисперсией оь. Значения нормально распределенной величины группируются около ее среднего значения с разбросом, пропорциональным стандартному отклонению и; при испытаниях примерно 95ьло значений нормально распределенной величины будет попадать в интервал [х — р[(2о.
34 Гя. х. Байгсавснал теория решений ом — — Е((х,— р,) (х) — )з))). (27) Ковариационная матрица Х всегда симметрична и положительно полуопределена. Ограничимся рассмотрением случаев, когда Е положительно определена, так что ее детерминант строго положителен '). Диагональный элемент оы есть дисперсия х,, а недиагональный элемент ом есть ковариация х, и хр Если х~ и хт статистически независимы, то ом — — О. Если все недиагональные элементы равны нулю, то р (х) сводится к произведению одномерных нормальных плотностей компонент вектора х.
Нетрудно показать, что любая линейная комбинация нормально распределенных случайных величин также распределена нормально. В частности, если А есть матрица размера дхп, а у=А'х есть п-компонеитный вектор, то р(у) Л'(А')з, А'ХА). В частном случае, если А есть вектор единичной длины а, то величина у=А'х является скаляром, представляющим проекцию вектора х на направление а. Таким образом, а'х.а есть дисперсия проекции х на а. Вообще знание ковариационной матрицы дает возможность вычислить дисперсию вдоль любого направления. Многомерная нормальная плотность распределения полностью определяется с(+б (д+!)/2 параметрами — элементами вектора среднего значения )з и независимыми элементами ковариационной матрицы Е. Выборки нормально распределенной случайной величины имеют тенденцию попадать в одну область илн кластер (рис. 2,7), Центр кластера определяется вектором среднего значения, а форма — ковариационной матрицей.
Из соотношения (23) следует, что точки постоянной плотности образуют гиперэллипсоиды, для которых квадратичная форма (х †)з)'Х-з(х †)з) постоянна. Главные оси этих гнперэллнпсоидов задаются собственными векторами Х, причем длины осей определяются собственными значениями. Величину г' = (х — )д)' Е-з (х — )з) (28) иногда называют квадратичным махаланобисовым расспюянием от х до )з. Линии постоянной плотности, таким образом, представляют собой гиперэллипсоиды постоянного махаланобисова расстояния до )з. Объем этих гиперэллипсоидов служит мерой разброса выборок относительно среднего значения.
Можно показать, что объем гиперэллипсонда, соответствующего махаланобисову расстоянию г, равен у = 'у'л ~ д' ) з~з гл, (29) з) Если выборки значений нормально распределенной величины принадлежат некоторому линейному подпростраиству, тобах!=О, в р(х) вырождеио.
Зто случается, если, иапример, одна из компоиеит вектора х обладает нулевой дисперсией либо две компоиеиты оказываются идеитичиыми. Мы спепиальио исключаем такие случаи. Ге. 2. Байееаеекая енеария решений где Уе есть объем д-мерной единичной гиперсферы, равный при четном е(, !30) при нечетном и'. й! Таким обрз ом, при заданной размерности разброс выборок изменяется пропорционально величине !Х !ч*, 2.8. РАЗДЕЛЯЮЩИЕ ФУНКЦИИ ДЛЯ СЛУЧАЯ НОРМАЛЬНОЙ ПЛОТНОСТИ Как мы видели в разд. 2.5, классификация с минимальным уровнем ошибки может осуществляться посредством разделяющих функций вида д; (х) =1ояр (х !в;)+ 1опР (в;). (13) Рассмотрим этот результат в некоторых частных случаях.
2.8.1. СЛУЧАЙ 1: 2;=-пЧ Эта простейшая ситуация возникает тогда, когда признаки статистически независимы и имеют одинаковую дисперсию о*. Ковариационная матрица при этом становится диагональной, превращаясь в произведение ое на единичную матрицу /. Выборки при этом попадают внутрь одинаковых гнперсферических кластеров, причем каждый кластер 1-го класса имеет своим центром вектор средних значений )я,. Здесь значительно упрощается расчет определителя и матрицы, обратной Х,; они равны соответственно !Х,!= =оее и Х,.
'= (1/ое)/. В соотношении (31) можно пренебречь несущественными постоянными слагаемыми !Х;! и (й/2)1од 2п, так как их значения не зависят от К В результате разделяющие функции принимают простой вид: а(х)= — !",",' +1КР(ве), (32) Это выражение легко оценивается в случае, когда многомерная плотность Р(х!в,) нормальна. Пусть Р(х!в~) А/(И,Х;). Тогда, согласно выражению (23), имеем й~(х) = — — (х — ре)' Х, ' (х — ре) — — !оя 2п— 2 — ! 1ой ~ Хе ~ + 1од Р (в;). (31) 2.8. Разделяющие функции для случая нормальной плотнослю 37 где ') 1 аз "ьг (35) гвгь — а щь~ + 1од Р (ю1). с (36) Классификатор, основанный на использовании линейных разделяющих функций, называется линейной машиной.
Классификатор ') Читатели, знакоиые с теорией выделения сигналов, узнают здесь корреляционный детектор. Разделяющая функция ял(х) определяет взаимную корреляцию входной величины х и заданного опорного сигнала рп Константой югь учитывается как энергия опорного сигнала, так и априорная вероятность его появлении. где 11 11 — евклидова норма, т. е. 1) х — )ь, 11з = (х — 1ьг)' (х — )з,). (33) Если для всех с классов априорные вероятности Р(ю,) равны, то слагаемое 1оя Р (ю,) также становится несущественной адди. тивной константой, которой можно пренебречь. Оптимальное решающее правило формулируется в этом случае очень просто: чтобы определить класс вектора признаков х, следует измерить евклидово расстояние 11х †)зД от х до каждого из с векторов средних значений и отнести х к классу, соответствующему ближайшему среднему значению.