/>/>/>/>/>Федеральноеагентство по образованию
Дальневосточныйгосударственный университет
Институтматематики и компьютерных наук
Кафедрапроцессов управления
Курсоваяработа
тема: Методыраспознавания образов
Владивосток 2010
Введение
Теория распознаванияобразов является одним из важнейших разделов кибернетики как в теоретическом,так и в прикладном плане. Она является полезнейшим инструментом в научныхисследованиях и в ряде областей практической деятельности. Владение методамираспознавания образов необходимо каждому специалисту по прикладной информатике,занимающемуся обработкой результатов экспериментов, что является востребованнымв последние годы. В данной курсовой работе более подробно будет изучен такойспособ решения задачи распознавания, как непараметрические парзеновские оценкиплотностей.
1. Задача распознавания
Сформулируем задачураспознавания. Пусть имеется несколько классов объектов. Каждый объектхарактеризуется значениями нескольких его параметров – признаков. В результатенекоторого эксперимента можно получить наборы (векторы) признаков дляпоследовательности объектов, при этом известно, из какого класса взят каждыйобъект. Затем появляется новый объект с его описанием, но неизвестно, какомуклассу он принадлежит. Необходимо на основе полученной ранее информации вынестирешение о принадлежности этого объекта.
Так как объектыизображаются векторами в многомерном пространстве (пространстве признаков), томы приходим к геометрической формулировке задачи распознавания: необходимопостроить поверхность, которая разделяет множества, соответствующие впространстве признаков различным классам объектов. Если множества впространстве признаков, описывающие разные классы, не пересекаются, то возможноточное разделение классов; если же они пересекаются, то любое решающее правилонеизбежно будет ошибаться, поэтому необходимо искать правило классификации,доставляющее минимум ошибок.
Информация, которойобладает исследователь до эксперимента – априорная информация – служит длявыбора конкретного типа алгоритма распознавания. Та информация, которую получаютв результате эксперимента (векторы признаков и указания о принадлежностиобъектов классам), называется обучающей выборкой и служит для построениянаилучшего правила классификации.
Сам процесс построенияэтого правила и есть обучение распознающей системы. Возможна и такая ситуация,когда указания о принадлежности объектов обучающей выборки отсутствует, в этомслучае мы имеем дело с задачей самообучения.
1.1 Основныепонятия и определения
Пусть имеется множествообъектов />,элементы которого мы будем обозначать буквами А, В, … (возможно с индексами).Множество /> разбитона М непересекающихся подмножеств />
/>
которые называютсяклассами объектов. Над каждым объектом А/>производится N измерений,результаты которых /> называются признаками данногообъекта. Таким образом, каждый объект изображается вектором признаков /> в N-мерномпространстве, которое называется пространством признаков.
На вход распознающейсистемы поступает последовательность векторов признаков соответствующих наборуобъектов А1, …, Аn,… из />. Последовательность (1.1)называется обучающей последовательностью, или обучающей выборкой.
x1,…xn,…,xk = x(Ak) (1.1)
Задача распознаванияможет быть в общем виде сформулирована следующим образом: необходимо пообучающей выборке построить решающее правило, то есть правило, которое длялюбого объекта А/>(возможно, не совпадающего ни содним из А1, …, Аn) позволяло бы на основе вектора х(А) указать, какому изклассов /> принадлежитобъект А.
Постановку задачи можноеще более детализировать, рассматривая отдельно три случая: детерминированнаязадача распознавания, вероятностная задача распознавания и самообучение(автоматическая классификация). Остановимся подробнее на вероятностной задачераспознавания. 1.2 Вероятностная задача распознавания
Дадим строгуюматематическую формулировку вероятностной задачи распознавания. Пусть навероятностном пространстве /> задана случайная величина />, принимающаяконечное число значений, />. Будем интерпретировать значениеслучайной величины /> как номер класса, которомупринадлежит объект, появившийся на входе распознающей системы. Тогдавероятность /> естьаприорная вероятность />.
Пусть, кроме того,имеется векторная случайная величина />, принимающая значения впространстве признаков />; значение х случайной величины /> есть векторпризнаков объекта, поступившего на вход распознающей системы. Предположим, чтосуществуют условные плотности распределений для каждого из классов, то есть длямножества В/>:
/>
Очевидно, распределениеслучайной величины /> будет иметь плотность:
/>
(этот факт следует изформулы полной вероятности).
Наша задача состоит втом, чтобы наилучшим образом провести классификацию объекта, заданного векторомпризнаков, то есть необходимо построить такое правило, которое по векторупризнаков указывало бы, к какому из классов /> относится соответствующий объект.Слова «наилучшим образом» предполагают, что у нас есть способ количественнойоценки построенного правила классификации. Определим, что мы будем понимать подкачеством классифицирующего правила.
Байесовским решающимправилом называется решающее правило, минимизирующее средний риск отнесенияобъектов k-го класса в i-й класс.
Пусть нам заданавероятностная схема: /> и матрица потерь />, элемент /> которой имеет смыслпотерь, связанных с отнесением объекта, принадлежащего k-му классу, в i-ый класс./> -разбиение пространства /> на М непересекающихся подмножеств.Тогда байесовское решающее правило определяется разбиением:
/>
Рассмотрим один оченьважный частный случай построения оптимального решающего правила. Пусть матрицапотерь имеет вид:
/>
Тогда оптимальноеразбиение состоит из множеств:
/>
что соответствуетрешающему правилу: х относится к/>если
/> для всех /> (1.2)
Итак, мы имеем видрешающего правила, минимизирующего функционал среднего риска.
Однако, при решениизадачи распознавания мы не имеем достаточно информации для использования этогоправила, так как могут быть неизвестны ни плотности />, ни априорные вероятности />. Иначе говоря,мы должны принимать решения, имея неполную априорную информацию. Дляпреодоления этой неопределенности и служит обучающая выборка. При этом возможныдва пути использования эмпирических данных:
- оцениваниеплотностей распределения,
- непосредственноевосстановление параметров оптимального решающего правила.
Рассмотрим в отдельностиоценивание плотностей распределения.
Оценивание плотностейраспределения представляет собой классическую задачу, решаемую в математическойстатистике. А именно, пусть имеется повторная выборка (то есть,последовательность независимых одинаково распределенных случайных величин) /> с плотностьюраспределения p(x). Необходимо построить оценку функции p(x). Известно много методов решения этой задачи, например,метод максимального правдоподобия, байесовские методы оценивания,непараметрические оценки плотностей.
Схема обученияраспознавания в таком случае строится следующим образом. Обучающая выборкаразбивается на подвыборки, соответствующие отдельным классам. Оцениваютсяплотности распределений для каждого класса /> и априорные вероятности классов />. Полученныеоценки подставляются в байесовское решающее правило (1.2), которое ииспользуется для классификации. Рассмотрим подробно такой метод решения задачираспознавания, как парзеновские оценки плотностей.
2.Непараметрические парзеновские оценки плотностей 2.1 Основные понятия, определения, теоремы
Методы оценивания, вкоторых не делается предположений об аналитическом виде неизвестной плотности,называются непараметрическими.
Пусть /> - повторная выборка сплотностью p(x). Парзеновская оценка плотности p(x) есть функция
/>, (2.1)
где k(y) – некоторая заданная функция, называемая ядром оценки (2.1),/> -неотрицательная числовая последовательность.
Если ядро k(y) удовлетворяет условиям
/>
то (2.1) есть плотностьраспределения.
Докажем следующие теоремы:
Теорема (2.1):
Пусть выполнены условияна ядро k и />:
/>
Если функция p(x) непрерывна в точке х, то
геометрическийраспознавание непараметрический парзеновский
/>
Доказательство.
Рассмотрим величину:
/>
Справедлива формула:
/>
Разобьем здесь областьинтегрирования на два множества /> и /> - произвольное положительноечисло.
Первое слагаемое непревосходит величины
/>
а второе не превосходит
/>
Отсюда следует, что
/>
Устремляя n к бесконечности, получаем в силуусловий (2.2)-(2.4) получаем:
/>/>
а так как /> может быть взятопроизвольно малым, то это и означает сходимость />.
Теорема доказана.
Теорема (2.2).
Пусть х – точканепрерывности плотности p(x) и выполнены условия теоремы (2.1).тогда /> -асимптотически несмещенная оценка величины p(x), то есть
/>
Если, кроме того
/>
то /> - состоятельная оценка,то есть
/>
Доказательство.
Соотношение (2.5)непосредственно следует из теоремы (1).
Справедливо равенство
/>
второе слагаемое в правойчасти стремиться к нулю при />.
Введем обозначения:
/>/>;
тогда
/>
а так как /> - независимые одинаковораспределенные случайные величины, то
/>
При больших n:
/>
Так как функция /> удовлетворяетусловиям теоремы (2.1), то
/>
Теорема доказана.
При N=1 следующие функции удовлетворяютусловиям (2.7)
/>
Многомерные ядра могутбыть получены из одномерных следующим образом:
/>/>,
где x – вектор с компонентами />. Условия (2.4),(2.6) выполнены для последовательностей вида
/>
где а – некотораяконстанта.
2.2 Исследование парзеновских оценок плотностей на практике
В данном исследованиибыла поставлена задача смоделировать повторную выборку, соответствующуюплотности распределения
/>
(/>) и применить к ней парзеновскуюоценку, а также сравнить графически найденную оценку с истинной плотностью.
Работа выполняется впакете Microsoft Excel, так как этот пакет один из наиболее пригодных для решенияподобных задач.
На интервале [-4;9] сшагом 0,2 построим графическое изображение истинного значения плотностираспределения по заданной нам функции при />.
Полученный результатпредставлен на рис. 1:
/>
Рис. 1. График заданнойплотности распределения
Для оценивания ее строимповторную (обучающую) выборку, соответствующую данной плотности распределения. Вкачестве ядра k(y) выберем функцию
/>.
Проверим, удовлетворяетли при N=1 функция /> условиям теорем (2.1) и (2.2).
(a) />
где а – некотораяконстанта, />
(b) />,
(c) />
(d) Функциянепрерывна во всех точках х/>,
(e) />.
Таким образом, условиятеорем выполнены, и оценка является асимптотически несмещенной оценкой величиныp(x) (в силу условий (а)-(d)), то есть
/>
/>
и состоятельной оценкой(в силу условий (а)-(е)), то есть
/>
В зависимости от выборамножителя /> оценкибудут принимать различный вид. Графики сравнения оценки с истинным значениемфункции при различных /> представлены на рис. 2-5.
/>
Рис. 2. График сравненияоценки плотности распределения с ее истинным значением при />
/>
Рис. 3. График сравненияоценки плотности распределения с ее истинным значением при />
/>
Рис. 4. График сравненияоценки плотности распределения с ее истинным значением при />
/>
Рис. 5. График сравненияоценки плотности распределения с ее истинным значением при />
Наиболее удачная оценкаполучается при /> (см. рис. 6)
/>
Рис. 6. График сравненияоценки плотности распределения с ее истинным значением при />
Также вид оценки зависитот повторной выборки. Графики, полученные при изменении значений обучающейвыборки при неизменном /> представленнына рис. 6-8.
/>
Рис. 7. График сравненияоценки плотности распределения с ее истинным значением для повторной выборки (1)
/>
Рис. 8. График сравненияоценки плотности распределения с ее истинным значением для повторной выборки (2)
Таким образом, для каждойновой повторной выборки необходимо подбирать свое />, максимально приближающее оценкук истинной плотности распределения.
Заключение
Таким образом, в процессевыполнения курсовой работы мною было исследовано теоретически и на практикепостроение непараметрических парзеновских оценок. В ходе работы мною сделанывыводы, что хорошо выполненная оценка достаточно достоверно отображаетповедение заданной функции и что в результате изменения значений повторной выборкии неотрицательной числовой последовательности /> можно построить оценку,максимально приближенную к истинному значению функции.
Списоклитературы
1. Лиховидов В.Н. Практический курс распознаванияобразов. – Владивосток: издательство ДВГУ, 1983.
2. Невельсон М. Б.,Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание. М.:«Наука», 1972.
3. Булдаков В. М.,Кошкин Г. М. Рекуррентное оценивание условной плотности вероятности и линиирегрессии по зависимой выборке. Материалы V научн. конф. По математике, I.Томск, 1974, 135-136.
4. Воронцов К. В.Лекции по статистическим (байесовским) алгоритмам классификации, 2008.