Xreferat.com » Рефераты по математике » Методы распознавания образов

Методы распознавания образов

Размещено на /

Федеральное агентство по образованию

Дальневосточный государственный университет

Институт математики и компьютерных наук

Кафедра процессов управления


Курсовая работа


тема: Методы распознавания образов


Владивосток 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).


Методы распознавания образов


где а – некоторая константа, Методы распознавания образов


Методы распознавания образов,

Методы распознавания образов


Функция непрерывна во всех точках хМетоды распознавания образов,


Методы распознавания образов.


Таким образом, условия теорем выполнены, и оценка является асимптотически несмещенной оценкой величины p(x) (в силу условий (а)-(d)), то есть


Методы распознавания образов

Методы распознавания образов


и состоятельной оценкой (в силу условий (а)-(е)), то есть


Методы распознавания образов


В зависимости от выбора множителя Методы распознавания образов оценки будут принимать различный вид. Графики сравнения оценки с истинным значением функции при различных Методы распознавания образов представлены на рис. 2-5.


Методы распознавания образов

Рис. 2. График сравнения оценки плотности распределения с ее истинным значением при Методы распознавания образов

Методы распознавания образов

Рис. 3. График сравнения оценки плотности распределения с ее истинным значением при Методы распознавания образов


Методы распознавания образов

Рис. 4. График сравнения оценки плотности распределения с ее истинным значением при Методы распознавания образов

Методы распознавания образов

Рис. 5. График сравнения оценки плотности распределения с ее истинным значением при Методы распознавания образов


Наиболее удачная оценка получается при Методы распознавания образов (см. рис. 6)


Методы распознавания образов

Рис. 6. График сравнения оценки плотности распределения с ее истинным значением при Методы распознавания образов

Также вид оценки зависит от повторной выборки. Графики, полученные при изменении значений обучающей выборки при неизменном Методы распознавания образов представленны на рис. 6-8.


Методы распознавания образов

Рис. 7. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (1)


Методы распознавания образов

Рис. 8. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (2)

Таким образом, для каждой новой повторной выборки необходимо подбирать свое Методы распознавания образов, максимально приближающее оценку к истинной плотности распределения.

Заключение


Таким образом, в процессе выполнения курсовой работы мною было исследовано теоретически и на практике построение непараметрических парзеновских оценок. В ходе работы мною сделаны выводы, что хорошо выполненная оценка достаточно достоверно отображает поведение заданной функции и что в результате изменения значений повторной выборки и неотрицательной числовой последовательности Методы распознавания образов можно построить оценку, максимально приближенную к истинному значению функции.

Список литературы


Лиховидов В.Н. Практический курс распознавания образов. – Владивосток: издательство ДВГУ, 1983.

Невельсон М. Б., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание. М.: «Наука», 1972.

Булдаков В. М., Кошкин Г. М. Рекуррентное оценивание условной плотности вероятности и линии регрессии по зависимой выборке. Материалы V научн. конф. По математике, I. Томск, 1974, 135-136.

Воронцов К. В. Лекции по статистическим (байесовским) алгоритмам классификации, 2008.

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: