Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 32
Текст из файла (страница 32)
3.3, равна 1,9%. $ 6.2. Метод й ближайших соседей Как следует из предыдущего параграфа, метод Парзена позволяет оценить плотность вероятности. Однако вычисление ядра для каждого объекта требует значительного времени. В этом параграфе мы рассмотрим модификацию оценки Парзена, которая гораздо проще с вычислительной точки зрения.
В частности, когда нас интересуют не оценки плотностей вероятности сами по себе, а только классификация объектов, порож- 1аа 1,'1. 6, ОЦЕНИВАНИК 11ЛОТНОСТИ ВЕРОЯТНОСТИ 6 6.2. метОд л Ближлпших соскдей даемых двумя распределениями, нам достаточно решить лишь вопрос о том, какая из двух плотностей вероятности больше в данной точке. 6.2.1. Асимптотическая несмещенность и состоятельность.
В методе Парзена каждый объект является центром, вокруг которого строится некоторое фиксированное ядро. Похожую оценку можно получить и иначе, а именно следующим образом. Используя выборку, состоящую из 11' объектов, найдем расстояние г от точки Х до й-го ближай11пего к Х объекта (й-го ближайшего соседа). Для измерения «близости» можно воспользоваться любой подходящей метрикой. Тогда в качестве оценки плотности вероятности в точке Х лгон~но принять ° /с — 1 $ Рн(Х) =, А~к,у Х1 (6.53) где А (й, У, Х) — объем множества всех точек, расстояния которых до Х меньше, чем г.
Когда в качестве расстояния иснользуется евклидово расстояние, это многкество представляет собой гипершар радиуса г, объем которого (6.5') Г 2' Величина А является случайной величиной, зависящей от вы- бранного множества У объектов. Если параметр й(Ж), фигури- рующий в (6.53), удовлетворяет условиям 1пп й(Х) = оо 1ип й (Х) /Х = О, Я- ао (6.55) (6;,6) то можно доказать, что р~(Х) является асимптотически несмещенной и состоятельной оценкой плотности вероятности р(Л') [Ловтсгарден, 19651.
Доказательство здесь не приводится. Метод й ближайших соседей позволяет очень просто получить оценку плотности вероятности. Однако, так как при этом предполагается, что внутри гипершара плотность вероятности остается приблизительно постоянной, то расстояние г должно быть достаточно малым. Следовательно, мы вынуждены выбирать й небольшим, и, таким образом, жертвовать точностью оценки, если число наблюдений Х не очень велико. Этот недостаток, серьезный с точки зрения теории оценивания, не является существенным, когда оценивание плотности вероятности является вспомогательной задачей и полученные оценки используются для целей классификации.
(у (у) р (Х(о,) ( ~(Х,~Цр (Х(о11) — э- Х ', (6.58) или, подставляя (6.57) в (6.58), получим ).Х 6- (Оэ., (6.59) Таким образом, решение о принадлежности объекта Х к тому плп другому классу можно принять непосредственно после нахождения й ближайших соседей и сравнения й~ и й2. Решающее правило, основанное па методе й ближайших соседей, является очень простым и не требует знания плотностей вероятности.
Его недостаток заключается в необходимости хранить в памяти машины все объекты и сравнивать каждый из нпх с неизвестным объектом. Посмотрим, какова эффективность этого алгоритма [Ковер, 19671. Рассмотрим вначале простейший случай: й = 1. В этом случае решающее правило называют правилом ближайшего соседа. Вероятность ошибки при использовании ггравила ближайшего соседа. Рассмотрим случай, когда объект Х относится к классу о1;, потому что его ближайший сосед Хл принадлежит классу о1г.
Предположим, что Х~1 о,; тогда, если класс а, не совпадает с о1 то имеет место ошибка. Поэтому условная вероятность ошиб- 11 ки при фиксированных объектах Х и Л„определяется следующим образом: г(Х, Хл) = Рг(очаг Ф о;/Х„Х) = (6.60) = Р(а,/Х„)Р(оэ2/Х) + Р(а2/Х,) Р(а,/Х). 6.2.2. Решающее правило, основанное на методе й ближайших соседей. Оценка (6.53) может использоваться для классификации следующим образом. Когда требуется классифицировать неизвестный объект Х, среди имеющихся У объектов, из которых Х1 объектов принадлежат классу он а У2 объектов — классу о2, находят й ближайших в точке Х объектов.
Пусть й1 и й2 — соответственно числа объектов из класса вг и о2 среди этих й ближаиших соседей. Тогда оценка (6.53) принимает вид лч — 1 1 рг«(Х~" ) =,у А ° г = 1 2. (6.57) Нг ' гу,. Так как й~ и й2 объектов извлечены из одного и того же гипершара, то объем А — один и тот же как для класса он так и для класса о2. Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид 191 190 5 6.2. МЕТОД й БЛИ)КАЙШИХ СОСЕДЕИ Если предположить, что ближайший сосед Х~ очень то можно воспользоваться ством: Х велико, так что объект Х и его близко расположены друг к другу, следующим приблин(енным равен- (6.63) (6.69) 3=-1,2.
е~ = Е 1г~(Х)). (6.66) ГЛ. 6. ОЦЕИИВАНИК ПЛОТ11ОСТП ВЕРОЯТНОСТИ Р(а)/Х~) = Р(а,/Х). (6.61) Тогда условная вероятность ошибки (6.60) примет вид г(Х) ж 2Р(а(/Х)Р(а2/Х) = 2Р(а)/Х) [1 — Р(а)/Х) ] = (6.62) = 2Р(а2/Х) [1 — Р(а2/Х) ], т. е. г(Х) является функцией только объекта Х. Легко показать, что (6.60) сходится' к (6.62) с вероятностью.1, когда /)/-)- оо. С другой стороны, как следует пз (3.1), условная вероятность ошибки байесовского решающего правила г~(Х) (при данном Х) определяется как г('(Х) = ппп[Р(а)/Х), Р(а2/Х)] = = ппп[Р(а(/Х), 1 — Р(а(/Х)].
Таким образом, г(Х) и г~(Х) связаны соотношением г(Х) = 2г~(Х) [1 — г~(Х)]. (6.64) Так как вероятность ошибки е есть математическое ожидание условной вероятности ошибки г(Х), то а Е(г (Х)) = ( г (Х) р (Х) НХ = 2Е (г~ (Х) )! — г~ (Х))) =. У = 2е~ (1 — е~) — 2Уаг ~г~ (Х)] ( 2е~ (1 — е~)„ (6. 65) где,е~ — вероятность ошибки байесовского решающего правила, гонределяемая как математическое ожидание условной вероятно- сти ошибки Следовательно, вероятность ошибки при использовании правила ближайшего соседа в качестве решающего правила меньше, чем удвоенная вероятность ошибки байесовского решающего правила в предположении, что У является достаточно большим для выполнения условия (6.61). В табл.
3.4 было показано, что граница Чернова в примере с нормальными распределениями дает ошибку 4,6% при фактической ошибке 1,9% (т. е. в 2,4 раза больше). Учитывая, что правило ближайшего соседа не требует какой-либо информации го распределении, его можно считать весьма эффективным. Нижнюю границу вероятности ошибки прп использовании правила ближайшего соседа можно получить следующим образом: е = Е [г~(Х) + г~(Х) 11 — 2г~(Х))] = = е')'+Е [г')'(Х) (1 — 2г')'(Х))] ~ е. '(6.67) Последнее неравенство справедливо, так как из (6.63) следует :$ 0,5 ~ г~(Х) ~ О. Таким образом, вероятность ошибки ограничена ..''ек снизу вероятностью ошибки байесовского решающего правила, а равенство между ними имеет место, когда г (Х) /1 — 2 ( ) ) = = 0 почти всюду, т. е. г~(Х) = 0 или г~(Х) = 0,5 почти всюду ':1ггр.
Ер В оятность ошибки при использовании правила А ближайших соседей. Рассмотрение эффективности правила ближайшего соседа легко обобщается на случай правила Й бли)кайших сосвдей. Условная вероятность ошибки при фиксированном объекте Х Р определяется следующим образом: (й — 1)/2 гА(Х) = Р(а /Х) Х . Р(а,/Х)'Р(а,/Х)" '+ 3=0 ! (А — 1)/2 /) ~ + Р(о),IХ) ~", . ! Р(а,/Х) Р(а,/Х)~ ', (6.68~ 1=6 1, где перв первый и второй члены представляют собой соответственно условную вероятность ошибки для Х ее а) и Х ее а2.
Для того. чтобы выражение (6.68) имело смысл, й должно быть нечетным числом. Равенство (6.68) можно переписать следующим образом; (А — 1)/2 /д Р (а1/Х) ~1 — Р (а;/ХЦ + ;=о У + ~1 — Р (а(/Х)],'»~' Р (а(/Х)' ~1 — Р (а1/Х)] ~=(1+ 1)/2 Так как условная вероятность ошибки байесовского решающего правила определяется формулой (6.63), то г,(Х) можно представить как функцию от г~ (Х): (А — 1)/2 ф.
г (Х) = г (Х) »', . г'(Х)' И вЂ” *(Х)] '+ 1=о / , в (Х)] ~~»', г~ (Х) [1 — г~ (Х)] ', (6.70~ Е /=(%+1)/2 / у Д п лучения безусловной вероятности ошибки е~ нужно Х. ли усрвднить условную вероятность ошибки (6.70) ио всем . Для 1 и. б. ОЦЕНИВАН11Е 11ЛОТНООт11 ВЕВОЯТНОст11 этого, однако, нужно знать плотность вероятности г'а(Х) или плотности вероятности Р(о1~/Х) и Р(очаг/Х) для всех Х. Предполагается, что этой информацией мы не располагаем.
Для получения границы вероятности ошибки е„как функции от вероятности ошибки байесовского решающего правила е'а введем функцию ср„(г'а (Х) ) — наименьшую вогнутую функцию, такую, что для всех Х г„(Х) ~ ~р„(г~(Х) ). (6.71) Воспользовавшись неравенством Иенсена, получим е„= Е(г„(Х)) - Е(~р„(г'а(Х))) с гр„(Е(г'а(Х))) = гр„(е'а). (6.72) Так как условная вероятность ошибки г„(Х), определяемая формулой (6.69), монотонно уменьшается с ростом /с, наименьшая вогнутая функция ~р„также монотонно уменьшается с ростом /с.
Поэтому с'а ( е„( гр„(е'а) ( (р„-~ (е'а)... ( ~р~ (е'а) = 2в'а (1 — в'а). (6.73)' соотношение (6.73) дает асимптотическую границу эффективности метода Й ближайших соседей при /у'-~-оо как функцию минимальной вероятности ошибки байесовского классификатора е'а. Подчеркнем, что вероятность ошибки в'а бывает известна в очень редких случаях. Переписав неравенство (6.73) в виде 1р~ (еа) ~ е ~~ еА, (6.74) мы получаем границу вероятности ошибки в'а как функцию от Еа, КОтОРУ1О МО1КПО ЭКСПЕРИМЕНтаЛЬНО ОЦЕНИТЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
