Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 22
Текст из файла (страница 22)
При таких условиях вероятность попадания любой выборки в гиперсферу 5 с центром в х есть некое положительное число 114 Ге. 4. Неаараметричеекие мееиаде! ры, можно получить более убедительные (и более строгие) доказа- тельства сходимости х„' к х, но для наших целей достаточно получен- ного результата. Р(0, 0„'~х, х„') = Р(0~х) Р(0„'~х„'). (30) Теперь, если применяется решающее правило ближайшего соседа, мы совершаем ошибку всякий раз, когда 0чь0„'. Таким образом, условная вероятность ошибки Р„(е ~ х, х„') задается в виде е Р„(е~х, х„') = — 1 — ~, Р(0=ао 0„'=а;)х, х„') е=! с = 1 —,~~ Р (а; 1х) Р (а! ) х„').
е=! (31) Чтобы получить Р„(е), надо подставить это выражение в (29) вместо Р„(е ~ х), а затем усредннть результат по х. Вообще это очень трудно сделать, но, как мы уже замечали ранее, интегрирование в (29) становится тривиальным по мере устремления и к бесконечности, а р (х„' ~ х) к дельта-функции. Если Р (а; ~ х) непрерывна в х, получаем е и е.и! !=1~! — х !.,! )е!.,!;1е! — ма;- л-~а =1 — ~ Ре(а;~х), (32) е=! Так что асимптотический уровень ошибки правила ближайшего соседа, если можно поменять местами интегрирование и переход 4.6.3.
УРОВЕНЬ ОШИБКИ ДЛЯ ПРАВИЛА БЛИЖАЙШЕГО СОСЕДА Обратимся теперь к вычислению условной вероятности ошибки Р„(е ~ х, х„'). Чтобы избежать недоразумений, необходимо поставить задачу более тщательно, чем это делалось до сих пор. Когда мы говорим, что у нас имеется и независимо сделанных помеченных выборок, то мы имеем в виду и пар случайных переменных (х„0,), (х„ О,),...„(х„, 0„), где 0; может быть любым из с состояний природы а„... а,. Мы полагаем, что эти пары получались путем выбора состояния природы а! для 0е с вероятностью Р (а>), а затем путем выбора х, в соответствии с вероятностным законом р (х ~ а,), причем каждая пара выбирается независимо.
Положим теперь, что природа выбирает пару (х, О) и что х„', помеченное 0„', есть ближайшая к х выборка. Поскольку состояние природы при выборе х„' не зависит от состояния при выборе х, то 4.6. Правило ближайсиего сосо)а к пределу'), задается выражением Р = 1пп Р (е) = ь-~ Ф =!пп ~ Ра(е[х) р(х) с(х= (33) 4.6А. ГРАНИЦЫ ОШИБКИ Хотя уравнение (ЗЗ) дает точный результат, еще показательнее получить границы для Р, выраженные посредством байесоаского уровня Р*. Очевидной нижней границей для Р является сам уро- вень Р'. Кроме того, можно показать, что при любом Р* существует множество условных и априорных вероятностей, для которых эта граница достигается. Так что в этом смысле это точная нижняя гра- ница. Еще интереснее задача определения точной верхней границы.
Следующее соображение позволяет надеяться на низкую верхнюю границу: если байесовскнй уровень небольшой, то Р (ю,(х) близка к единице для некоторого (, скажем (=пт. Таким образом, подынте- гральное выражение в (33) будет приближенно 1 — Рз(ю !х)ж яп2 (1 — Р (оэ„[х)), и поскольку Р*(е[х) =1 — Р(ю„[х), (34) то интегрирование по х может дать уровень, в два раза превышающий байесовский, но являющийся все еще низким. Чтобы получить точ- ную верхнюю границу, мы должны определить, насколько большим может стать уровень Р ошибки правила ближайшего соседа для за- данного байесовского уровня Р*. Таким образом, выражение (33) вынуждает нас задаться вопросом, насколько малой может стать чРРз(со,!х) для заданной Р(оз [х).
Записав е ~ Рз (со! [ х) = Ре (ю„[ х) + ~~Р ~Р з (ю; [ х), С 4Ы мы можем получить границу этой суммы, минимизируя второй член при следующих ограничениях: 1) Р (юг (х)вО; 2) к. Р (озг)х)= 1 — Р (оз„!х)=Р* (е)х). г~м ') Читатели, знакомые с теорией меры, знают, что теорема мажорированной сходимости позволяет производить подобную замену.
Если существуют области, где р(х) тождественна нулю, то уравнение (32) является недействительным для атих значений х. (Почему?) Такие области, однако, можно исключить из интег- рирования выражения (33). ыа Гл. е. Непарааеа!ричеише мел!оди Несколько поразмыслив, мы видим, что Х Р'(е!!1х) минимизиру- ,Ь-! ется, если все апостериорные вероятности, кроме ш-й, равны, и второе ограничение дает — !~л!, Р(!з;~ х)= с — ! 1 — Р'(е1х), ! =л!. (35) Таким образом, с ~ Р' (!э! ~ х) ~ (1 — Р* (е ~ х))'+ —, !=! 1 — ~ Р'(в!1х)(2Р'(е~х) —,, Р" (е~х). (36) !=! Сразу же видим, что Р(2Р', поэтому можем подставить этот результат в (33) и просто опустить второй член выражения. Однако более точную границу можно получить на основании Уаг ~( Р' (е ~ х)1 = ~ (Р' (е ~ х) — Р*]' р (х) !(х = ~ Р" (е ) х) р (х) пх — Р" -в О, так что ~ Р" ' (е ~ х) р (х) дх ) Р*', причем равенство сохраняется тогда и только тогда, когда диспер- сия Р" (е!х) равна нулю. Пользуясь этим результатом и подставляя соотношение (ЗБ) в (33), получаем желаемые границы Р'(Р(Р'(2 — — ', Р*) (28) Легко показать, что такая верхняя граница достигается в случае так называемой нулевой информации, в котором плотности распределения р (х!!е!) тождественны, так что Р (а! 1х)=Р (в!) и Р'" (е!х) не зависит от х.
Таким образом, границы, заданные (28), являются максимально близкими в том смысле, что для любой Р* существуют условные и априорные вероятности, для которых эти границы достигаются. На рис. 4.4 графически представлены эти границы. Байесовский уровень Р' может находиться в любом месте между О и (с — 1)/с. Границы сходятся в этих двух крайних точках. Когда байесовский уровень мал, верхняя граница превышает его почти в два раве. В общем значение ошибки правила ближайшего соседа должно находиться в заштрихованной области. Поскольку Р всегда меньше или равна 2Р*, то, если имеется бесконечный набор данных и используется сложное решающее пра- 4.7. Йрааила й блихайшил гашдей вило, можно по крайней мере в два Р раза сократить уровень ошибки.
В этом смысле по крайней мере половина классифицирующей информации бесконечного набора данных находится по соседству. Естественно задаться вопросом, насколько хорошо правило ближайшего соседа в случае конечного числа выборок и как быстро результат сходится к асимптотическому значению. К сожалению, от- с-г веты для общего случая неблаго- с приятны. Можно показать, чтосхо- Рлс. 4,4. Грааяаы ашабка правидимость может быть бесконечно ла ближайшего соседа. медленной и уровень ошибки Р„(е) даже не должен монотонно убывать с ростом л.
Так же, как это происходит с другими непараметрическими методами, трудно получить какие-либо еще результаты, кроме асимптотических, не делая дальнейших допущений о вероятностных свойствах. 4.7. ПРАВИЛО Ф БЛИЖААших сОСЕДСА Явным расширением правила ближайшего соседа является правила л ближайших соседей. Как видно из названия, зто правило классифицирует х, присваивая ему метку, наиболее часто представляемую среди й ближайших выборок; другими словами, решение принимается после изучения меток й ближайших соседей.Мы не будем подробно анализировать это правило.
Однако можно получить некоторме дополнительные представления об этих процедурах, рассмотрев случай с двумя классами при нечетном числе й (чтобы избежать совпадений). Основным поводом к рассмотрению правила й ближайших соседей послужило сделанное нами ранее наблюдение о согласовании вероятностей с реальностью. Сначала мы заметили, что если й фиксировано и количеству выборок и позволить стремиться к бесконечности, то нсе й ближайших соседей сойдутся к х.
Следовательно, как и в случае с единственным ближайшим соседом, меткамн каждого из й ближайших соседей будут случайные величины, независимо принимающие значение га, с вероятностью Р(ш~~х), (=1, 2. Если Р(ш ~х) является самой большой апостериорной вероятностью, то решающее правило Байеса всегда выбирает ш . Правило единственного ближайшего соседа выбирает ш с вероятностью Р(га ~х). Правило Ф ближайших соседей выбирает ш„, если большинство из Ге. 4. Нелораееешричеекее методы 1!8 й ближайших соседей имеют метку ш, с вероятностью (; ) Р (ш ~ х)е (! — Р (ш„~ хЯ" '. В общем чем больше значение й, тем больше вероятность, что будет выбрана ш„. Мы могли бы проанализировать правило й ближайших соседей так же, как мы анализировали правило единственного ближайшего Се(0) 0е0 080 Р" Рис.
4.5. Границы уровня ошибки иравила й ближайшая соседей. соседа. Однако ввиду того, что здесь потребуются более сложные рассуждения, которые мало что проясняют, мы удовлетворимся только констатацией результатов. Можно показать, что при нечетном й величина ошибки в случае с двумя классами и большим количе. ством выборок для правила й ближайших соседей ограничивается сверху функцией С,(Р"), где С» по определению есть наименьшая вогнутая функция от Р', большая, чем (Е-1ня, йк ( . ) ИРе)е+е(1 Рэ)е-е+(ре)а-!(] Ре)1+а) с=о Теперь совершенно ясно, что очень мало можно увидеть, глядя на приведенную функцию, разве что только можно отметить ее род- 4.д. Аппрояеиииции прими раэложения в ряд 119 ство с биномиальным распределением.
К счастью, можно легко вычислить С (Р*) и изучить результаты. На рис. 4.5 показаны границы уровней ошибок правила й ближайших соседей для нескольких значений й. Случай с 1=1 соответствует случаю с двумя классами нз рис. 4.4. С возрастанием й верхние границы все более приближаются к нижней границе, уровню Байеса. В пределе, когда й стремится к бесконечности, две границы встречаются и правило й ближайших соседей становится оптимальным. Рискуя произвести впечатление, что мы повторяемся, закончим снова упоминанием о ситуации с конечным числом выборок, встречаемой на практике.
Правило й ближайших соседей можно рассматривать как еще одну попытку оценить апостериорные вероятности Р(ев, 1х) на основании выборок. Чтобы получить надежную оценку, нам желательно использовать большое значение Й. С другой стороны, мы хотим, чтобы все й ближайших соседей х' были очень близки к х с тем, чтобы быть уверенными, что Р (а; 1х') приблизительно такая же, как Р(еи;1х). Это заставляет нас выбрать среднее значение й, являющееся небольшой частью всего количества выборок, Только в пределе при устремлении й к бесконечности можем мы быть уверены в почти оптимальном поведении правила й ближайших соседей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
