Фукунага - Введение в статистическую теорию распознования образов (1033985), страница 33
Текст из файла (страница 33)
Пример 6.2. Для правила ближайшего соседа имеем г~(Х) = 2г'а(Х) [1 — г'а(Х)1. (6.75) Условная вероятность ошибки г~ (Х) является вогнутой функцией, и, следовательно, ее можно использовать в качестве гр~ (г'а(Х) ) в неравенстве (6.71). Применяя неравенство (6.72), получим е'а < е~ < 2в'а(1 — е'а).
(6.76) Обращая это неравенство, имеем ['1 — (1 — 2е,) "У]/2 ( е'а ( в,. (6.77) Таким образом, неравенство (6.77) дает границы вероятности ошибки байесовского решающего правила в виде функций от асимптотической вероятности ошибки метода ближайшего соседа. 6.2.3. Обобщение на случай нескольких классов. Метод й блиясайших соседей легко обобщается на случай нескольких классов. Выбирая й ближайших соседей объекта Х, подсчитаем число 5 6.2.
метод к БлнжАиших соседеи (6.78) Для простоты ограничимся исследованием эффективности этого решающего правила в случае, когда используется правило ближайшего соседа, т. е. /с = 1 [Ковер, 19671. Как и в случае двух классов, эффективность увеличивается с увеличением /.".
Условну1о вероятность ошибки при фиксированном объекте Х можно представить следу1ощим образом: м м г(Х) = Р (о1/Х) ~~ Р (о,/Х) + ... + Р (ом/Х) ~', Р (о1,/Х). (6.79) 1=1 1=1 1Ф1 1~м Первый член вырансения (6.79) дает условную вероятность ошибки для Х ~ о1н второй — для Х ~ о1~ и т. д. Воспользовавп1ись тем, что Р(о1~)+...+Р(гааг) = 1, перепишем (6.79) в видо м г(Х) = 1 ~ Р2(о,/Х). (6.80) С другой стороны, условная вероятность ошибки байесовского решающего правила (при фиксированном Х) равна г'а (Х) = 1 — шах (Р (о11/Х)) = 1 — Р (о1/Х),, (6.81) где Р(1й1/Х) = шах(Р (о11/Х)), 1 = 1, ..., ЛХ.
Воспользовавшись неравенством Шварца, получим м м 2 (ЛХ вЂ” 1) Х Р2(о1;/Х)) Х РМХ) ~=1 7=1 1~1 )+г =(1-~ (ю,/Х)Р=" (Х). (6.82) Прибавляя (М вЂ” 1) Р (со~/Х) к левой и правой частям (6.82), получаем м (М 1) '~', Р2 (н,/Х) ) г*'(Х) + (ЛХ вЂ” 1) [1 — г'а (Х)]', (6.83) 1=1 Комбинируя (6.83) и (6.80), имеем г(Х) ~ 2г'а(Х) — [М/(М вЂ” 1) ~г*'(Х). (6.84) Взяв математическое ожидание от левой и правой частей (6.84), 7 к. Фукунага объектов каждого класса.
Пусть /сн /сг, °, айаг — число объектов, принадлежащих соответственно классам о1н ..., ааг. Тогда, согласно критерию Байеса для многих классов, реша1ощее правило будет иметь вид й,; = шах(/с~... /с ) — э-Х ~ ось ГЛ. 6. ОЦЕНИВЛНИЕ ПЛОТНОСТИ ВЕРОЯТНОСТИ 5 а.з. метод ГистОГРАмм 195 получаем (6.85) е ( 2е'л [Я/(М вЂ” 1)]е "2, Таким образом, и в случае нескольких классов вероятпостт ошибки е меньше, чем удвоенная вероятность ошибки байесовского решающего правила. В случае М = 2 неравенство (6.85) переходит в (6.65). ') В оригинале: сопдепаед й-пеагеа1 11ес1а1оп гп1е.
(При.м, р«д.) 6.2.4. Модифицированное правило й ближайших соседей. Недостаток решающего правила 7с бли~кайгших соседей закл1очаетсд. в необходимости помнить все объекты и сравнивать неизвестный объект со всеми этими объектами. Этот недостаток был бы не таким существенным, если бы удалось исключить часть из этих объектов, оставив лишь сравнительно небольшое число представителей. Объекты, находящиеся вблизи границы байесовског1л решающего правила, сильно влияют на результат иряменения метода й ближайших соседей, но объекты, далекие от границы, пе влияют на решение.
Поэтому систематическое искл1оченпе этих «невлияющих» объектов позволяет уменьшить как врел11г вычислений, так и требования к памяти. Соответствующая процедура получила название модифицированного правила Й ближайших соседей л) [Харт, 1968]. Для простоты приведем метод исключения невлияющих объектов в случае й = 1 (т. е. для правила ближайшего соседа). Метод мон;но легко модифицировать для общего случая. В приведенном ниже описании метода слова ПАМЯТЬ и ОТСЕВ являются идентификаторами двух разных массивов памяти. 1.
Первый объект заносится в ПАМЯТЬ. 2. Каждый следующий объект классифицируется с помощью правила ближайшего соседа; при этом использу1отся только те объекты, которые находятся в массиве ПАМЯТЬ. Если классификация произведена правильно, объект выбрасывают в ОТСЕВ. Если объект класспфицирован неправильно, его заносят в ПАМЯТЬ. 3.
Эта процедура повторяется, пока не будут просмотрены все У объектов. ' 4. После того как все объекты просмотрены, снова применяют описанную выше процедуру, но лишь к объектам, находящимся в массиве ОТСЕВ, и повторяют ее до тех пор, пока не оказывается, что в процессе просмотра пи .один из объектов не переходят из массива ОТСЕВ в массив ПАМЯТЬ. В работе [Харт, 1968] приведены два примера, иллюстрирующие эффективность описанного выше метода. 1.
Множеств из 482 двумерных объектов, представляющих два класса (искусственно генерированное), после четырех итераций уменьшилось до 40 представителей. Все 40 представителей были расположены вдоль границы, разделяющей классы. 2. Мнонсество из 6295 машинописных символов (25 классов в 96-мерном пространстве) после четырех итераций было представлено 197 объектами. ~ 6 3 Метод гистограмм Рассматривая й и А в выражении (6.53)' как свободные параметры, можно получать различные оценки плотности вероятности, известные под названием гистограмм. В этом параграфе будут рассмотрены два часто встречающихся вида гистограмм. м 6.3.1.
Ячеики одинакового размера. Разобьем пространство па ВЗаИМНО НЕПЕрЕСЕКаЮщИЕСя яЧЕйКИ Г1, ..., Глг, раЗМЕрЫ КОтОрЫХ одинаковы. Тогда плотность вероятности можно приближенно охарактеризовать числом объектов, попавших в кангдую ячейку. Пример,для одномерного случая показан на рис. 63. Метод гистограмм не требует информации о распределении, и, если использовать регулярную сетку для построения ячеек Г~ Рис 63 Гистограмма с одина1 овыми ячеиками Гь то выбор нУжной ячейки производится непосредственно Од.
пако большим недостатком этого метода является то, что и требует слишком большой памяти: например, при наличии гл переменных и при ЛХ градациях по каждой переменной требуется М" ячеек. Поэтому большинство предлагавшихся лгодифика ций этого метода имело своей целью уменьшение чистка ячеек. 6.3,2. Ячейки неодинакового размера. Число ячеек мон1но уменьшить, используя ячейки неодинакового размера. Пример для одномерного случая показан на рис. 6.4. Если известны число объектов в канадой ячейке, размер ячейки и ее местонахождение, то формулу (6.53) по-прежнему молкно использовать в качестве оценки плотности вероятности. Для реализации этой идеи на практике нужен метод для определения числа объектов и размера каждой ячейки.
Ниже приводится одно из многих возможных решений [Себестпан, 1966]. 1. Пусть имеется т ячеек Г1, ..., Г, каждая из которых характеризуется координатами центра Х„дисперсиями по каждой 7* 197 (6.92) (6. 93) ,ц,.(Й,) =(И;,) ~;Х,Д. (6.88) (6.89) (6.90) ~11с,. ~2. 1 — т ~-1 (6.94) ГЛ. 6, ОЦЕНИВАНИЕ ПЛОТНОСТИ ВЕРОЯТНОСТИ из и переменных (пн, ..., п1а), и числом объектов, попавших 2 2 внутрь ячейки Й;. При предъявлении нового объекта Х вычисляется расстояние между Х и центром каждой ячейки Х; пэ формуле д (Х, Х;) = ~ (х, — х1,)2!и';;, 1= 1, 2,..., т.
(6.86) з=! Находится ближайшая ячейка, т. е. выбирается Х„, такое, что Рис. 6.4. Гистограмма с неодинаковыми ячейками, а (Х, Х„) = пнп с! (Х, Х;). Тогда объект Х классифицируется следующим образом: И(Х, Х,) ( т-э-Х относится к ячейке Г с1(Х, Л„) ~ О,-э-Х создается новая ячейка с центром Х (О ) 1). В остальных случаях вопрос о 1гринадлелсности объекта Х остается нерешенным. Здесь т и Π— свободные параметры, определяющие число ячеек и точность аппроксимации. 2. Когда новый объект попадает в 1-ю ячейку, параметры ячейки пересчптыва!отся следующим образом.
а) Увеличивается на единицу число объектов в ячейке. Пусть Й, — новое число объектов. б) Вычисляется новый вектор математического ожидаппя ЛХ! (Й;) (новый центр ячейки): в) Вычисляются новые дисперсии по формулам и;;(Й,) = шах[о';;(О), г;,(Й1)1 А; г;, (Й1) = (1/Й1) ~', [х11 (1) — т;; (Й;) ) 2. ! 1 Величина г,; (Й1) в (6.90) — дисперсия 7-й переменной в 1-!1 ячейке, подсчитанная по Й! объектам. Величина п;,(О) — перво- $6.4. РАЗЛОЖЕНИЕ ПО БАЗИСНЫМ ФУНКЦИЯМ начальное заданное значение дисперсии. Только в том случае, когдаз1; (Й1) превышает о;, (О), п;; (О) заменяется наг!;(Й;).
3. Первый объект всегда становится центром новой ячейки. Второй объект классифицируется в соответствии с п. 1 и т. д. После того как все объекты расклассифицированы или среднее число объектов в ячейке достигает некоторого заданного значения, объекты, по которым не было принято решение, распределяются по ближайпшм ячейкам, и параметры этих ячеек пересчитываются в соответствии с п.
2. 2 Свободные параметры т, О и п;;(О) можно подобрать путем повторения описанного выше процесса для одного и того же множества объектов. ~ 6.4. Разложение по базисным функциям 6.4.1. Разложение плотности вероятности, Другой метод аппроксимации плотности вероятности состоит в разложении ее по базисным функциям 1р;(Х): Р (Х) = Х с11р! (Х) ° (6.
91) 1=1 Если базисные функции удовлетворяют услощно ~ с1Х! д, 1Х! р 1Х! с~Х = сс„, У то говорят, что функции ср1(Х) ортогональны с весом Й(Х). Функции ср; (Х)' являются комплексно сопряженными относительно 1р,(Х) и равны 1р;(Х), если 1р;(Х) — действительные функции. Если базисные функции ортогональны с весом Й(Х), то коэффициенты разложения (6.91) определяются следующим образом: А,с, = ~ Й (Х) р (Х),р,'.
(Х) гх У Если в разложении '(6.91) ограничиться первыми т членами, то среднеквадратичная ошибка т т * с' = (lс1Х! Р1Х! — ~У с,~Р 1Х! Р1Х! — ~ с,д,.1Х! ссгс— У 1 — 1 1=1 — ~ р(х! ( Х сл,(х!)~ Х с1, 1х) ах=- (6.99) (6.100) (6.103) с(гр) (х) 1=0 (6.95) (6,96) 198 ГЛ, О, ОЦЕНИВАНИЕ ПЛОТНОСТИ ВЕРОЯТНОСТИ Таким образом, Л(~ с(~ 2 — ошибка, обусловленная исключением 1-го члена разложения. Это означает, что если удается найти систему базисных функций, таких, что значения Л(~ с()2 быстро убывают с ростом 1, то эта система даст экономное представление плотности вероятности. В общем многомерном случае процедура для нахождения системы базисйых функций неизвестна. Поэтому рассмотрим только частныв случаи, копда базисные функции хорошо определены. Примерами разложения по базисным функциям являются ряды Фурье и преобразованив Фурье.
Характеристическая функция плотности вероятности является преобразованием Фурье и, таким образом, представляет собой один из видов разложения плотности вероятности. Ниже рассматривается разложение более простого вида. Одномерный случай. Когда плотность вероятности является одномерной, можно воспользоваться многими хорошо известными системами базисных функций, такими, как ряды Фурье, полиномы Лежандра, Гегенбауэра, Якоби, Эрмита и Лагерра (Дейч, 19691.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
