Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 21
Текст из файла (страница 21)
Если плотность распределения вблизи х высокая, то ячейка будет относительно небольшой, что приводит к хорошему разрешению. Если плотность распределения невысокая, то ячейка возрастает, но рост приостанавливается вскоре после ее вступления в области более высокой плот- Рис. 4.3, Оценки двух плотностей риспределении, полученные методом й„бли- жайших соседей. л у А=У л а=та' «„=» Рант* що -г о Нортиальааа -г о баыадальлае ыо Гл. 4. Нелираметричеекие методы ности распределения. В любом случае, если мы берем (5) мы хотим, чтобы й„стремилось к бесконечности при стремлении и к бесконечности, так как это гарантирует, что й„/и будет хорошей оценкой'вероятности попадания точки в ячейку объема У„. Однако мы хотим также, чтобы й„росло достаточно медленно для того, чтобы размер ячейки, необходимый для вмещения й„выборок, сжался до нуля.
Таким образом, из формулы (5) видно, что отношение й„/и должно стремиться к нулю. Хотя мы не приводим доказательств, можно показать, что условия 11ш й„=со и 1ип й„/и/ б являются нее -«л Л-~л обходимыми и достаточными для сходимости р„(х) и р (х) по вероятности во всех точках, где плотность р непрерывна. Если взять й„=)/ п и допустить, что рл(х) является хорошей аппроксимацией р(х), то из соотношения (5) следует, что У„=1/(Улр (х)). Таким образом, Ул опять имеет вид УД' и, но начальный объем У, определяется характером данных, а не каким-либо нашим произвольным выбором. Полезно сравнить этот метод с методом парзеновского окна на тех же данных, что были использованы в предыдущих примерах.
С п=1 и й„=)/и = 1 оценка становится 1 21к — к 1 Ясно, что это плохая оценка для р (х), поскольку ее интеграл расходится. Как показано на рис. 4.3, оценка становится значительно лучше по мере увеличения и несмотря на то, что интеграл оценки всегда остается бесконечным. Зтот неприятный факт компенсируется тем, что рл(к) никогда не сведется к нулю просто потому, что в некоторую произвольную ячейку или окно не попадают никакие выборки. Хотя эта компенсация может показаться скудной, в пространствах более высокой размерности она приобретает ббльшую ценность. Как и в методе парзеновского окна, мы можем получить семейство оценок, принимая /е„=й,Уп и выбирая различные значения для К. Однако при отсутствии какой-либо дополнительной информации любой выбор одинаково хорош, и мы можем быть уверены лишь в том, что результаты будут асимптотически правильными. 4.б.
ОЦЕНКА АПОСТЕРИОРНЫХ ВЕРОЯТНОСТЕЙ Рассмотренные в предыдущих разделах методы можно использовать для оценки апостериорных вероятностей Р(в,(х) на основании и помеченных выборок, пользуясь выборками для оценки соответствующих плотностей распределения. Предположим, что мы ем. Правило бликаагигга соггба размещаем ячейку объема У вокруг х и захватываем й выборок, й, из которых оказываются помеченными го!, Тогда очевидной оценкой совместной вероятности р(х, гв!) будет р„(х, гв!) =+.
ьда Таким образом, приемлемой оценкой для Р(гв!(х) будет и~~ ~Рл (". гвг) г=! Иначе говоря, оценка апостериорной вероятности того, что состояние природы есть га„ является просто долей выборок в ячейке, помеченных гв!. Чтобы свести уровень ошибки к минимуму, мы выбираем класс, наиболее часто представляемый в ячейке. Если имеется достаточное количество выборок и если ячейка достаточно мала, то можно показать, что результаты будут в этом случае близки к наилучшим. Если дело доходит до выбора размера ячейки, то можно воспользоваться или методом парзеновского окна, или методом й„ближайших соседей.
В первом случае )г„будет некоторой определенной функцией от и, а именно Р„=( Уп. Во втором случае г'и будет расширяться до тех пор, пока не вместит некоторое определенное число выборок, а именно й=$~ и. В любом случае по мере устремления и к бесконечности в бесконечно малую ячейку будет попадать бесконечное число выборок. Тот факт, что объем ячейки может стать бесконечно малым и все же будет содержать бесконечно большое число выборок, позволяет нам изучать неизвестные вероятности с определенной точностью и, таким образом, постепенно добиваться оптимальных результатов. Довольно интересно, как мы увидим далее, что можно получать сравнимые результаты, основывая наше решение только на метке единственного ближайшего соседа величины х.
4,6, ПРАВИЛО БЛИЖАЙШЕГО СОСЕДА 4.6.1. ОБЩИЕ ЗАМЕЧАНИЯ Пусть Яи=(х„..., х„) будет множеством и помеченных выборок, и пусть х „' Е,$"" будет выборкой, ближайшей к х. Тогда правило ближайшего соседа для классификации х заключается в том, что х присваивается метка, ассоциированная с х'„. Правило ближайшего соседа является почти оптимальной процедурой; его применение обычно приводит к уровню ошибки, превышающему минимально возможный байесовский.
Как мы увидим, однако, при неограниченном количестве выборок уровень ошибки никода не будет хуже байесовского более чем в два раза. Гль 4. Неааралиесричеекие мемеды Прежде чем вдаваться в детали, давайте попытаемся эврнстически разобраться в том, почему правило ближайшего соседа дает такие хорошие результаты. Для начала отметим, что метка В„', ассоциированная с ближайшим соседом, является случайной величиной, а вероятность того, что сс„'=сос, есть просто апостериорная вероятность Р(сос1х„'). Когда количество выборок очень велико, следует допустить, что х„' расположено достаточно близко к х, чтобы Р (сос 1х„')жР (сос1х). В этом случае можем рассматривать правило ближайшего соседа как рандомизированное решающее правило, которое классифицирует х путем выбора класса сос с вероятностью Р(сос1х).
Поскольку это точная вероятность того, что природа находится в состоянии сос, значит, правило ближайшего соседа эффективно согласует вероятности с реальностью. Если мы определяем со (х) как Р (со„~ х) = ш ах Р (сос ~ х), (23) Р(е) = ~ Р(е~х) р(х) с(х. (24) Заметим, что решающее правило Байеса минимизирует Р(е) путем минимизации Р(е1х) для каждого х. Если Р' (е1х) является минимально возможным значеннем Р(е1х), а Р" — минимально возможным значением Р(е), то Рл(е1х) =1 — Р(со 1х) Р'= ~ Р*(е ) х) р (х) с(х. (2б) (26) то байесовское решающее правило всегда выбирает сом.
Когда вероятность Р(со 1х) близка к единице, выбор с помощью правила ближайшего соседа почти всегда будет таким же, как н байесовский, это значит, что когда минимальная вероятность ошибки мала, то вероятность ошибки правила ближайшего соседа также мала. Когда Р (со 1х) близка к 1/с, так что все классы одинаково правдоподобны, то выборы, сделанные с помощью этих двух правил, редко бывают одинаковыми, но вероятность ошибки в обоих случаях составляет приблизительно 1 — 1йь Не нсключая необходимости в более тщательном анализе, эти замечания позволяют меньше удивляться хорошим результатам правила ближайшего соседа.
Наш анализ поведения правила ближайшего соседа будет направлен на получение условной средней вероятности ошибки Р(е1х) при большом количестве выборок, где усреднение производится по выборкам. Безусловная средняя вероятность ошибки будет найдена путем усреднения Р(е1х) по всем х: 4.6. Правило ближайшего соееда пэ 4.6.2. СХОДИМОСТЬ ПРИ ИСПОЛЪЗОВАНИИ МЕТОДА БЛИЖАЙШЕГО СОСЕДА Теперь мы хотим оценить среднюю вероятность ошибки для правила ближайшего соседа. В частности, если Р„(е) есть уровень ошибки с п выборками н если Р=!пп Р„(е), (27) то мы хотим показать, что Начнем с замечания, что при использовании правила ближайшего соседа с конкретным множеством а выборок результирующий ура.
вень ошибки будет зависеть от случайных характеристик выборок. В частности, если для классификации х используются различные множества и выборок, то для ближайшего соседа вектора х будут получены различные векторы х,'. Так как решающее правило зависит от ближайшего соседа, мы имеем условную вероятность ошибки Р„(е(х, х„' ), которая зависит как от х, так и от х„' . Усредняя по х„', получаем Р„(е 1х) = ~ Р„(е1х, х„') р (хв'1х) дх„'. (29) Рэ = ~ р (х') дх'. меэ Таким образом, вероятность попадания всех а независимо взятых выборок за пределы этой гиперсферы будет (1 — Рэ)", стремящейся к нулю по мере устремления л к бесконечности. Итак, х„' сходится к х по вероятности и р (х„'~ х) приближается к дельта функции, как и ожидалось.
Вообще говоря, применяя методы теории ме. Обычно очень трудно получить точное выражение для условной плотности распределения р(х„' 1х). Однако, поскольку х„' по определению является ближайшим соседом х, мы ожидаем, что эта плотность будет очень большой в непосредственной близости от х и очень малой во всех других случаях. Более того, мы ожидаем, что по мере устремления и к бесконечности р (х„'~ х) будет стремиться к дельта. функции с центром в х, что делает оценку, задаваемую (29), тривиальной. Для того чтобы показать, что это действительно так, мы должны допустить, что плотность р для заданного х непрерывна и не равна нулю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
