Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 20
Текст из файла (страница 20)
4. Непараметричеопие методы конной плотностью распределения. Точнее, если мы потребуем, чтобы <р (п))0 (9) и (12) ~ ~р(п)он=1, (10) и если мы сохраняем отношение У„=Ье, то отсюда сразу же следует что и рп(х) также удовлетворяет этим условиям, Рассмотрим, какое влияние оказывает на р„(х) ширина окна Ь,. Если мы определяем функцию 6„(х) как 6„(х) = „— ер ~,—,), (11) то можем записать р„(х) в виде среднего и рп(х) = — ~ 6„(х — х,).
1=1 Поскольку У„=Ье, то Ь„ влияет как на амплитуду, так и на ширину окна 6„(х). Если Ь„ очень велика, то амплитуда у 6„ мала, и х должно находиться достаточно далеко от хь пока 6„(х — х;) не станет значительно отличаться от 6„(0). В этом случае р„(х) есть наложение и широких, медленно меняющихся функций и служит очень сглаженной «несфокусированной» оценкой р(х).
С другой стороны, если Ь„очень мала, то максимальное значение 6,(х — х ) велико и находится вблизи от х=хь В этом случае рп(х) есть наложение и резких выбросов с центрами в выборках и является ошибочной езашумленной» оценкой функции р(х). Для любого значения Ь„справедливо выражение ) бл(х — х)е(к=~У 'Р( Ь )~(х=~Ч~(в)Й3=1. (13) Таким образом, по мере устремления Ь„к нулю 6„(х — х~) стремится к дельта функции Дирака, центрироваиной в хь и рп(х) стремится к наложению дельта.
функций, центрированных в вйборках. Ясно, что выбор значения Ь„ (или У„) сильно сказывается на р„(х). Если объем У„ слишком велик, оценка будет плохой из-за слишком малой разрешающей способности. Если У„слишком мал, оценка будет плохой в результате слишком большого статистического разброса. При ограниченном количестве выборок самое лучшее решение — пойти на приемлемый компромисс. При неограниченном же количестве выборок можно позволить У„медленно стремиться к нулю по мере увеличения и и заставить рп(оа) сойтись к неизвестной плотности распределения р (х).
Говоря о сходимости, мы должны сознавать, что речь идет о сходимости последовательности случайных величин, так как для любого фиксированного х значение р„(х) зависит от значений слу- 4.д. Г)пресновские окна чайных выборок х„..., х„. Таким образом, рн (х) имеет некоторое среднее р„(х) и некоторую дисперсию ов (х). Будем говорить, что оценка р„(х) сходится к р(х), если ') Вгп р„(х) = р (х) (14) Вгп о'„(х) = О. (15) и н Чтобы доказать сходимость, нужно наложить условия на неиз- вестную плотность распределения р (х), функцию окна ~р(и) и ширину окна )г„. Обычно требуется, чтобы р была непрерывной в х и чтобы выполнялись условия (9) и (10).
Можно доказать, что сходимость обеспечивается при следующих дополнительных условиях: зн гр(и) < в 1нп гр(и) П иг=О, 11вй м г=! !'ппУ„=О, н м 1ип иУ„= оо. (17) (18) (19) Выражения (16) и (17) способствуют хорошему поведению ~р, и этим условиям удовлетворяет большинство плотностей распределения, которые можно взять для функций окна. Уравнения (18) и (19) говорят о том, что объем У„должен стремиться к нулю, но со скоростью, меньшей чем 1/и.
Рассмотрим теперь, почему эти условия — основные условия, обеспечивающие сходимость. 4.3.2. СХОДИМОСТЬ СРЕДНЕГО ЗНАЧЕНИЯ Сначала рассмотрим р„(х) — среднее значение р„(х). Поскольку выборки х, распределены равномерно в соответствии с (неизвестной) плотностью распределения р(х), имеем р„(х) = ~ (рв (х)) = =И' ~ — ' (*="')1= гр( —,) р(») гг» = = ~ б„(х — ») р (») г(». (20) ') Такой ти~ сходнмости называется среднеквадратичной сходиносглью.
Описанпе видов сходвмости последовательности произвольных переменных см. в книге Е. Раггеп, Модегп РгоЬаЫ!ну ТЬеогу апд Из Арр1!са11опз, СЬар1ег 1О ()оьп тйг11еу, Метг Уог)г, 1960). Гл. 4. Налпралемрические .неводы Это уравнение показывает, что ожидаемое значение оценки есть усредненное значение неизвестной плотности распределения, свертка неизвестной плотности распределения и функции окна. Таким образом, р„(х) является сглаженным вариантом для р(х), видимым через усредняющее окно. Но с устремлением У„к нулю 6„(х — у) стремится к дельта. функции с центром в х, Так что если р непрерывна в х, то уравнение (18) гарантирует, что р„(х) будет приближаться к р(х) по мере устремления и к бесконечности ').
4.3.3. СХОДИМОСТЬ ДИСПЕРСИИ Уравнение (20) показывает, что для того, чтобы заставить Р„(х) устремиться к Р(х), не нужно иметь бесконечное число выборок; при любом и достаточно только устремить Уа к нулю. Конечно, для конкретного множества п выборок получающаяся оценка, имеющая всплески, будет бесполезной. Этот факт подчеркивает необходимость рассмотрения дисперсии оценки, Поскольку ра(х) является суммой функций статистически независимых случайных величин, ее дисперсия является суммой дисперсий отдельных членов, и отсюда имеем з о.л(х) =~Е ~(лР Ф( Л ) и Р (х)~ 1 з = — ) — <рз ( — ) Р (у) г/т — — р„(х).
=.У„1 У„'~ И„) и Опуская второй член, ограничивающий ~р, и используя (20), получаем сг' (х) ( (22) я Ясно, что для получения небольшой дисперсии нам нужно большое, а не малое значение У„. Однако, поскольку числительостается конечным при стремлении п к бесконечности, мы можем позволить У„стремиться к нулю и все же получать нулевую дисперсию при условии, что пУ„стремится к бесконечности. Например, мы можем взять У„=Уз/)I п, или Уз/!од и, или любую другую функцию, удовлетворяющую соотношениям (18) и (19).
Это основной теоретический вывод. Но, к сожалению, он ничего не говорит о том, как выбирать ф и У„, чтобы получить хорошие ре- з) Зто не строгий аргумент, но он интуятивно ясен и вполне разумен. Более глубокий анализ показывает, что возникает затруднение, если неизвестная плотность распределения неограничена, как зто бывает, когда р(к) содержит дельта- функции. Условие, добавляемое соознопгеннем (17), устраняет это затруднение. 105 4.3.
Парзеноеекие окна ;д льтаты в случае с конечным числом выборок. Действительно, если у нас не будет другой информации о р(х), помимо той, что она непрерывна, у нас не будет никакого основания для оптимизации результатов при конечном числе выборок. 4.3.4. ДВА ПРИМЕРА Интересно проследить, как метод парзеновского окна проявляется на простых примерах. Рассмотрим сначала случай, где р(х) является одномерной нормальной плотностью распределения с нулевым средним значением и дисперсией, равной единице.
Пусть функция окна будет иметь тот же вид: ! Г 1 ер (и) = = ехр ~ — — ие ~ . =) 2-. И наконец, пусть Ь„=Л,)/ и, где А, — параметр, находящийся в нашем распоряжении. Таким образом, рн(х) есть среднее нормальных плотностей распределения, центрированных в выборках: и р„(х)= — ~„— „(р( „'). ;=1 Нетрудно из соотношений (20) и (21) найти выражения среднего значения и дисперсии для р„(х), но еще интереснее увидеть численные результаты. На рис.
4.! показаны результаты, полученные при вычислении рн(х) с помощью конкретно выбранного множества нормально распределенцых случайных выборок. Эти результаты зависят от п и й,. Для л= 1 функция р„(х) будет просто единственным холмом гауссовского распределения с центром в первой выборке. Для л=16 и Ь,— — 1/4 влияние отдельных выборок ясно различимо, а для Ь, = 1 и 6,=4 — цат.
По маре увелцчения п способность рн отоажать особенности р, возрастает. При этом ро оказывается более чувствительной к локальным нерегулярностям выборок, когда п велико, хотя мы уверены, что рк будет сходиться к сглаженной нормальноц кривой по мере устремлеция п к бесконечности. Ясно, что нельзя судить по одному внешнему виду и что для получения точной оценки требуется много выборок. В качестве другого примера пусть ео(и) и й„будут такими же, а неизвестная плотность распределения пусть будет смесью двуходнородных плотностей 1, — 2,5<х< — 2, Р (х) = 0,25, 0 < х < 2, 0 в противном случае.
На рис. 4.2 показано поведение оценок этой плотности, полученных методом парзеновского окна, й,=о,га п=7 а,! а,ан ш,о аг и 'тб а,аа га л=гаа щ ааа! га ге= о! ааа -г а г -г о г -г о г Рис. 4.!. Опенка нормальной плотности распределения методом парзеновского окна. Гл. 4. Оепаралеаричеаше меподм ~ов Как и прежде, случай с я=1 говорит больше о функции окна, чем о неизвестной плотности распределения. Для п=16 ни одна из оценок не годится, а вот для п=25б и 6,=1 результаты уже кажутся приемлемыми. Эти примеры показывают некоторые достоинства и некоторую ограниченность непараметрическ их методов. Достоинства заключаются в их общности.
Одна и та же процедура использовалась для уиимодального нормального и бнмодального смешанного случаев, При достаточном количестве выборок мы уверены в сходимости к сколь угодно сложной неизвестной плотности распределения. С другой стороны, может потребоваться очень большое количество выборок, намного превышающее то количество, которое нам потребовалось бы, если бы мы знали вид неизвестной плотности распределения.
Нет почти никаких способов уменьшения объема данных, поэтому потребности во времени вычисления и памяти слишком велики. Более того, потребность большего количества выборок растет зкспоненциально с увеличением размерности пррстранства признаков. Этот недостаток непараметрическнх процедур, связанный с явлением, которое Беллман назвал «проклятием размерности», намного ограничивает их практическую применимость. 4.4.
ОЦЕНКА МЕТОДОМ Ф„БЛИЖАЙШИХ СОСЕДЕЙ Одна из проблем, с которой сталкиваются при использовании метода парзеновского окна, заключается в выборе последовательности объемов ячеек У„У„.... Например, если мы берем У„=УД и, то результаты для любого конечного и будут очень чувствительны к выбору начального объема У,.
Если У, слишком мал, большинство объемов будут пустыми и оценка р„(х) будет довольно ошибочной. С другой стороны, если У, слишком велик, то из-зв усреднения по объему ячейки могут быть потеряны важные пространственные отклонения от р(х). Кроме того, вполне может случиться, что объем ячейки, уместный для одного значения х, может совершенно не годиться для других случаев. Один из возможных способов решения этой проблемы — сделать объем ячейки функцией данных, а не количества выборок.
Например, чтобы оценить р(х) на основании п выборок, можно центрировать ячейку вокруг х и позволить ей расти до тех пор, пока она не вместит й„ выборок, где л„ есть некая определенная функция от и. Зти выборки будут й„ближайшими соседями х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
