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