Дуда Р., Харт П. - Распознование образов и анализ сцен, страница 7

Такой классификатор называют классификатором по мйнимуму расстояния. Если каждый из векторов средних значений считать идеальным прототипом или эталоном для образов своего класса, то зто по существу будет процедура сравнения с эталоном. Если априорные'вероятности не равны, то, согласно соотношению (32), квздрат расстояния 11х — )зь11з должен быть нормирован по дисперсии о' и смещен на величину !оя Р'(ю,); поэтому в случае, когда х одинаково близок к двум различным векторам средних значений, при принятии решения следует предпочесть класс, априорно более вероятный. На самом деле нет необходимости вычислять расстояние в каждом из этих случаев. Раскрытие квадратичнойформы (х — )з;)г(х — )зь) приводит к выражению д; (х) = — —, (хгх — 2р,'.и+ рг()ьг) -1- 1оя Р (юг), являющемуся квадратичной функцией х. Вместе с тем квадратичный член хгх, неизменный для любого(, представляет собой постоянное слагаемое, и им можно пренебречь.

В результате получаем эквивалентную линейную разделяющую функцию вида у; (х) = зч,'к+гпгто (34) Гл. 2. Байесаасиая америк решений Гранина иуаааааи ааш саад а ФФ/(у Рнс. 2.8. Гранкам областей решений прн нспольвоввнни клвсскфкквтора по мнкнмуму расстояния. а — ввдачв для двух классов, б — ввдача для четырех классов. (37) (38) где этого типа обладает многими свойствами, интересными с теоретической точки зрения; некоторые из ннх будут подробно обсуждаться в гл, 5.

Здесь же заметим просто, что поверхности решений в случае линейной машины явятся частями гиперплоскостей, определяемых линейными уравнениями д~(х)=дт(х). Для данного частного случая это уравнение можно записать в виде тя'(х — х,) =О, 2.д. Разделяющие функции длл случая нормальной плотности 39 х, = — (1ь;,' )зу) —, 1оя — ' (1зг — )з ). (39) ! о' Р (ыг) 11 рй — ру 11' Р (ыу) Это уравнение определяет ортогональную вектору ти гипер.

плоскость, проходящую через точку х,. Поскольку чч=1зь — 1ьл гиперплоскость, разделяющая А, и Ял будет ортогональна прямой, соединяющей средние значения. Если Р(го,)=-Р(взь), то точка х, находится посередине между средними значениями, а гиперплоскость проходит через середину отрезка, соединяющего средние значения перпендикулярно ему (рис. 2.8). Этого следовало бы ожидать по той причине, что классификатор в данном случае есть классификатор по минимуму расстояния.

Если Р(озг)МР(озг), то точка х, смещается, удаляясь от более вероятного среднего значения. Вместе с тем следует заметить, что если дисперсия оз мала по сравнению с квадРатом РасстоЯниЯ ~))ьг — 1ьфь, то положение гРаницы областей решений сравнительно мало зависит от точных значений априорных вероятностей. 2.8.2. СЛУЧАЙ 2: Хг=д В другом простом случае ковариационные матрицы для всех классов одинаковы. Геометрически это соответствует ситуации, при которой выборки попадают внутрь гиперэллипсоидальных областей (кластеров) одинаковых размеров и формы, " вектором средних значений в центре каждой. Не зависящими от 1 слагаемыми ~Х,1 и (42)1од2я в соотношении(31) можно пренебречь. В результате получаем разделяющие функции вида йг(х) = — — (х — 1з,) Х '(х — )зг)+1одР(озг).

(40) 1 Если априорные вероятности Р(озг) для всех с классов равны, то слагаемым 1ойР(вьг) можно пренебречь. Оптимальное решающее правило в этом случае снова оказывается очень простым: для классификации вектора признаков следует определить квадратичное махаланобисово расстояние (х — )зг)'2-'(х — )лг) от х до каждого из й векторов средних значений и отнести х к классу, соответствующему ближайшему среднему значению '). Как и прежде, в случае неравных априорных вероятностей, при принятии решения несколько большее предпочтение отдается классу, априорно более вероятному. В К зльтернвтнвной интерпретяпни можно прияти, подвергая координзты признаков линейному преобрязоваивю с таким изменением мзсштабов и поворотом осей, при котором гиперзллипсоиды постоянного мзхзлзнобисова расстояния превратятся в гнперсферы. Такое преобразование упрощает зздачу, сводя ее к случаю, ряссмотренному в предыдущем разделе„ я позволяя махвлзнобнсово расстояние рассматривать в преобразованном пространстве кзк евклидова.

40 Гл. 2. Бааееаеекая амарал реимнаа При раскрытии квадратичной формы (х — )ь,)'Х-'(х — р;) обнаруживается, что квадратичное слагаемое х'Х-'х ие зависит от 1. Исключая его, снова получим линейные разделяющие функции вида аг аз(х) =ти)х+ие„(4!) где тие = Х-')ь,. (42) тт'(х — хе) = О, ти = Х ' ()а, — )4 ) (44) где (45) 1оа— Р (мз) 1 Р (соу) х, = — ()ае+ )ьу) — ), ( ) ()ье — )еу).

(46) Так как направление вектора тн=Х-'(111 — )ае) в общем случае не совпадает с направлением р,— )ьь то гиперплоскость, разделяющая в)1 и Ял вообще говоря, не ортогональна отрезку, соединяющему средние значения. Вместе с тем в случае равных априорных вероятностей она пересекает этот отрезок в точке х„находящейся посередине между средними значениями. При неравных априорных вероятностях граничная гиперплоскость смещается, удаляясь от более вероятного среднего значения.

2.8.3. СЛУЧАЙ 3: ПРОИЗВОЛЬНЫЕ 21 В общем случае многомерного нормального распределения ковариационные матрицы для каждого класса различны. В выражении (3!) можно пренебречь только слагаемым (1(/2))од 2п, так что получаемые разделяющие функции оказываются существенно квадратичными: я1 (Х) = Х')й 1Х+ ти',Х+ нзеа, (47) аа Граница обааапеи решении Рнс. 2як Граница областей решений при использовании классификатора по миниму- му махаланобнсова расстояния. нм= — )4)Х 'р;+!ояР(шз). 1 (43) Так как разделяющие фунКции линейны, границы областей решений в этом случае становятся гиперплоскостямн (рис. 2.9). Для смежных Яз и Ж1 граница между ними описывается уравне- нием 2Я. Разделяющие функции для случая нормальной ялояшосши 4! где 2 и;=-~Г'И ° айв= — — 1агХ, '1дг — — 1од ~ Хг ~+ 1он Р(шг).

Границы областей решений представляют собой гилерквадрмки и могут принимать любую из общих форм — гиперплоскостей, Рис, 2.10. Виды границ областей решений в общем случае двумерного нормаль. ного распределения. а — круг, б — вллипс, е — парабола, е — гипербола, д — прямые. гиперсфер, гиперзллипсоидов, гиперпараболоидов или разного вида гипергиперболоидов. То, каким образом могут возникнуть эти различные виды гиперквадрик, изображено для двумерного случая Фг () О (48) (49) (50) Гя.

2. Байееоееная теория решений на рис. 2.10. Так как переменные х„х, независимы для фиксированного класса, их ковариационные матрицы диагональны. Поверхности решений различаются исключительно из-за различия междудисперсиями. Сами дисперсии обозначены пронумерованными контурами постоянной плотности вероятности.

На рис. 2.10 (а) дисперсии для р(х1в,) меньше, чем для р(х1в,). Поэтому более вероятно, что выборки, принадлежащие классу 2, окажутся вблизи среднего значения для этого класса, а из-за центральной симметрии граница решения образует окружность, внутри которой лежит ме. При растяжении осн х„как показано иа рис. 2.10 (б), граница решения вытягивается в эллипс. Рис. 2. 1О (в) иллюстрирует случай, когда обе плотности имеют одинаковые дисперсии в направлении х„ но в направлении х, дисперсия для р(х~в1) больше, чем для р(хиве).

Таким образом, выборки с большим х„вероятнее, принадлежат классу 1, а граница решения представляет собой параболу. С ростом х, дисперсия для р (х1в,) меняется как на рис. 2.10 (г) н граница превращается в гиперболу. Наконец, Особый случай симметрии, когда гиперболическая граница вырождается в пару прямых, приведен на рнс. 2.!О (д). 2.9. БАЙЕСОВСКАЯ ТЕОРИЯ РЕШЕНИЙ вЂ” ДИСКРЕТНЫЙ СееУЧАЙ До сих пор предполагалось, что вектор признаков х может быть любой точкой д-мерного евклидова пространства. На практике компоненты вектора х часто оказываются бинарными или тернариыми переменными, так что х может принять одно из т дискретных значений т„ ..., т„.

Функция плотности р(х~вг) в таких случаях становится сингулярной, а интегралы вида ) р(х~в~)е1х превращаются в суммы ,,'~~ Р (тя ~ в.), где Р (те~в~) — условная вероятность того, что х=тя при условии, что состояние природы есть вп Байесовское правило принимает вид Р(в ~х) =,~ (51) где Р(х) = ~ Р(х~в~) Р(в~). Определение условного риска ег(еее1х) при этом не изменяется, так что основное байесовское решающее правило остается прежним: для того чтобы общий риск был наименьшим, следует выбирать такое действие ееь для которого )г (ае!х) минимален. Основное пра- 43 2.Ю.

Незаеисиаые бинарн»«е признаки вило минимизации уровня ошибки посредством максимизации апостериорной вероятности также не изменяется, так что, пользуясь правилом Вайеса, получим следующие эквивалентные разделяющие функции; я, (х) = Р (а, ) х), (53) д1(х) =Р(х[а;) Р(а1), (54) й1 (х) = 1оя Р (х ~ е;) +1оя Р (аг). (55) Для случая двух классов часто более удобны разделяющие функции вида я (х) = Р (а, ) х] — Р (е, ~ х), (56) (57) 2.10. НЕЗАВИСИМЫЕ БИНАРНЫЕ ПРИЗНАКИ В качестве примера типичной задачи классификации при дискретных значениях признаков рассмотрим случай двух классов, в каждом из которых компоненты вектора бинарны и условно независимы, Пусть для определенности х=(х„..., х,)«, где компоненты вектора х равны либо 1, либо О, причем р1 — — Рг (х1 —— 1 ~а,) и «71 =Рг(х« — — 11а»). Это модель задачи классификации, в которой каждый из признаков несет ответ типа «д໠— «нет».

В случае р1)д, следует ожидать, что 1-й признак будет чаще давать ответ «да» при состоянии природы а„нежели при е,. В предположении условной независимости можно записать Р(х1а1) в виде произведения вероятностей для компонент х. Записать это удобнее следующим образом: Р(х(а«) = П р«'(1 — р1) 1=1 Р (х ~ а,) = П д",' (1 — д1) ' 1=! Отношение правдоподобия при этом определяется выражением = (-)( — ) а из (57) получим выражение для разделяющей функции д(х) =~ ~х1 1оя — '+(1 — х1) 1оя "'1+ 1ое — ф. 1=1 44 Г«.

2. Бай««««с«аа теория решений Видно, что данное уравнение линейно относительно х,. Таким образом, можно написать а()=Х; «+~., где ччП Рй « ш« =~„1оя — + 1оя —. ! — р! р (ш1) «' р (ш«) Посмотрим, к каким выводам можно прийти на основании полученных результатов.

Напомним прежде всего, что в случае д(х))0 принимается решение «э„а в случае д(х)(0 — решение в». Мы уже убедились, что д(х) представляет собой взвешенную комбинацию компонент вектора х. Величиной веса в, измеряется значимость ответа «да» для х; при классификации. Если р;=до то величина х, не несет информации о состоянии природы, так что нь=0. В случае р;>д~ имеем 1 — р,~! — до так что вес ш; положителен. Следовательно, в этом случае ответ «да» для х, дает ш~ голосов в пользу шо Кроме того, прн любом постоянном д;(1, чем больше рь тем больше и нч.

С другой стороны, при р«~д, величина в, становится отрицательной, и ответ «да» дает 1в;1 голосов в пользу ш«. Величины априорных вероятностей Р(«э,) проявляются в выражении разделяющих функций только через так называемый пороговый вес «э,. Увеличение Р (ш,) приводит к увеличению «р„склоняя решение к «»ь тогда как уменьшение Р(е»,) оказывает противоположное действие. Геометрически векторы ч» можно представить вершинами «1-мерного гиперкуба. Поверхность решения, определяемая уравнением д(х)=0, представляет собой гнперплоскость, отделяющую вершины в, от вершин ш«. Положение этой гиперплоскости в дискретном случае можно, очевидно, изменять множеством способов, не пересекая вершин и не изменяя вероятности ошибки. Каждая из этих гнперплоскостей представляет оптимальную разделяющую поверхность, обеспечивая оптимальный образ действия. 2,)Е СОСТАВНАЯ БАЙЕСОВСКАЯ ЗАДАЧА ПРИНЯТИЯ РЕШЕНИЙ И КОНТЕКСТ Вернемся к ранее рассмотренному примеру разработки классификатора для сортировки двух видов древесины — ясеня и березы.

Первоначально было принято, что последовательность видов древесины настолько непредсказуема, что состояние природы представляется чисто случайной переменной. Не отказываясь от этого, предположим, что последовательные состояния природы могут и 2.11. Соснсавнан байесовснан энднна нринннснн ренсгний лэ не быть статистически независимыми. Например, если даже априорные вероятности для ясеня и березы оказываются равными, то может оказаться, что при появлении некоторого куска древесины более вероятно, что несколько последующих кусков будут того жесамого вида. В этом случае последовательные состояния природы находятся в некоторой зависимости, которую можно использовать для улучшения образа действия.