Алгоритм распознавания образов

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

Харьковский национальный университет имени В.Н. Каразина

Кафедра математического моделирования и программного обеспечения

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

«Об одном алгоритме распознавания образов»

Научный руководитель:

ассистент кафедры ММ та ПО

Трубицын А.В.

Рецензент: ст. преподаватель кафедры ММ та ПО

Худошин И.Г.

Выполнил: студент 4 курса ММФ

группы МП-41 Бураков К. А.

Харьков 2009

Содержание

  • Введение
  • Постановка задачи распознавания образов
  • Байесовский классификатор
  • Линейный классификатор
  • Алгоритм персептрона
  • НСКО — алгоритм (алгоритм наименьшей средне-квадратичной ошибки)
  • Линейный классификатор в случае нескольких классов
  • Схема Кеслера (обобщение алгоритмов на случай нескольких классов)
  • Метод потенциальных функций
  • Некоторые сведения о сходимости итерационного процесса
  • Примеры работы классификаторов
  • Выводы
  • Список использованной литературы
  • Приложения

Введение

Распознавание образов (а часто говорят — объектов, ситуаций, явлений или процессов) — самая распространенная задача, которую человеку приходится решать практически ежесекундно от первого до последнего дня своего существования.

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

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

Под классом образов понимается некоторая категория, определяющаяся рядом свойств общих для всех ее элементов. Образ — это описание любого элемента как представителя соответствующего класса образов. В случае, когда множество образов разделяется на непересекающиеся классы, желательно использовать для отнесения этих образов к соответствующим классам какое-либо автоматическое устройство.

Автоматическое распознавание образов имеет большое практическое значение. Впервые оно было использовано для машинного считывания рукописных цифр. В настоящее время область его применения существенно расширилась: начиная от измерений, контроля, сортировки и сборки в производственных процессах и кончая анализом изображений, считываемых на расстоянии, диагностикой по медицинским снимкам, качественной оценкой экспериментальных данных, идентификацией человека, автоматическим проектированием, пониманием изображений как функции технического зрения роботов и т. д. Распознавание образов традиционно относят к задачам искусственного интеллекта.

Первые попытки изучения возможностей автоматизации процесса распознавания образов относятся к началу 50-х годов, когда цифровые вычислительные машины постепенно стали общедоступным средством обработки информации. В конце 50-х годов Розенблатт предложил персептронный алгоритм, который представлял собой одну из первых моделей процессов запоминания и организации информации, реализуемых мозгом. Базой для решения задач отнесения объектов к тому или иному классу послужили результаты классической теории статистических решений. В её рамках строились алгоритмы, обеспечивающие на основе экспериментальных измерений параметров (признаков), характеризующих этот объект, а также некоторых априорных данных, описывающих классы, определение конкретного класса, к которому может быть отнесен распознаваемый объект.

К середине 70-х годов определился облик распознавания как самостоятельного научного направления, появилась возможность создания нормальной математической теории распознавания.

Cущественный вклад в дисциплину распознавания образов внесли Ф. Розенблатт, В. М. Глушков, В. С. Михалевич, В. С. Пугачев, Н. П. Бусленко, Ю. И. Журавлев, Я. З. Цыпкин, А. Г. Ивахненко, М. М. Бонгард, В. Н. Вапник, Г. П. Тартаковский, В. Г. Репин, Л. А. Растригин, А. Л. Горелик, В. Л. Матросов, Р. Гонсалес, У. Гренандер, Г. Себестиан, К. Фу, А. Новиков, М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр, Р. Дуда, П. Харт, А. Я. Червоненкис, Э. Патрик.

Постановка задачи распознавания образов

Будем рассматривать некоторое множество объектов определённой природы, которое мы будем называть пространством образов. Признаком будем называть функцию, определённую на. Совокупность признаков, относящихся к одному образу, будем называть вектором признаков.

Задачу распознавания образов можно сформулировать следующим образом.

Дано:

W? — пространство образов (множество объектов распознавания);

щ?ОW? — образ (объект распознавания);

g (щ): W®M, M--=?{1,2,. ,m} — индикаторная функция, разбивающая пространство образов W? на m непересекающихся классов ,. ,;

— пространство признаков;

x (щ): W®?C — вектор признаков;

, i =?1,2. ,m;

, =, =;

{ (,), j =?1,2. ,N} - множество прецедентов.

Требуется, опираясь на множество прецедентов, построить классификатор — оценку для g (щ) на основании x (щ). Критерии построения будут сформулированы ниже, отдельно для каждого метода.

Процесс построения по множеству прецедентов называют обучением, а векторы из множества прецедентов — обучающей выборкой.

распознавание образ алгоритм программа

Часто на пространстве образов вводится топология или метрика, и отображение считают непрерывным.

Областью предпочтения класса называется множество., (). Области предпочтения классов часто определяют при помощи решающих функций ,…, где. Эти функции таковы, что. Классификатор принимает вид.

В случае задачи с двумя классами рассматривают решающую функцию. Значения этой функции отличаются знаком на векторах из и:

В этом случае классификатор имеет вид.

Далее будем считать, что.

Байесовский классификатор

Байесовский подход исходит из статистической природы наблюдений. За основу берется предположение о том, что вектор признаков для каждого класса распределен случайно с некоторой условной плотностью распределения вероятностей, а также существуют вероятности. Этот подход подробно описан в работах [1], [2], [5].

Величина называется апостериорной вероятностью, поскольку задает распределение индекса класса после эксперимента (a posteriori - т. е. после того, как значение вектора признаков x было получено).

Естественно выбрать классификатор таким образом: объект относим к тому классу, для которого апостериорная вероятность выше (т.е. вектор x относим к классу, если для, , выполнено неравенство). Такое правило классификации по максимуму апостериорной вероятности называется байесовским.

Для байесовского решающего правила необходимо получить апостериорные вероятности, i. Это можно сделать с помощью формулы Байеса для плотностей распределения:

, где.

При классификации x сравнение и эквивалентно сравнению и.

Таким образом, =i: p (x|) *P () > p (x|) *P (),j?i. Вероятности и плотности распределения либо считаются известными, либо оцениваются исходя из множества прецедентов методами математической статистики.

Часто считают классы ,., равновероятными, т. е. В случае не равновероятных классов, вероятности появления классов часто оценивают как, где - число прецедентов из класса, - общее число прецедентов.

Областью предпочтения класса в нашем случае будет множество. Будем предполагать, что — борелевские множества.

Обозначим () — вероятность отнесения вектора x к классу, при условии, что на самом деле он принадлежит классу.

Определение. Величина называется ошибкой классификации.

Теорема 1. 1 Байесовский классификатор является оптимальным по отношению к минимизации ошибки классификации.

Доказательство. Рассмотрим вероятность правильной классификации

=

=

=

учитывая формулу Байеса, получим:

.

Для минимизации ошибки классификации необходимо максимизировать вероятность правильной классификации. Очевидно, что максимум достигается, когда для всех x из (). Заменяя в предыдущих выкладках на остальные классы, получаем, что максимум достигается при. ч. т.д.

На практике довольно распространён случай, когда цена ошибок различного типа существенно различается. В этом случае лучше использовать другой критерий качества классификации — минимум среднего риска.

Пусть , j = 1,2,. ,m - области предпочтения классов. Предположим, что вектор x из класса лежит в, , т. е. классификация происходит с ошибкой. Свяжем с этой ошибкой штраф называемый потерями в результате того, что объект из класса был принят за объект из класса.

Определение. Выражение называется риском при классификации объекта класса.

Определение. Выражение называется общим средним риском.

Теперь мы можем поставить задачу о выборе классификатора, минимизирующего этот риск. Преобразуем выражение общего среднего риска:

.

Из этого выражения видно, что риск минимален, когда каждый из интегралов в данной сумме минимален, т. е., если для всех, где

.

Минимизация среднего риска и ошибки классификации часто эквивалентны разделению пространства признаков на m областей. Если области и смежные, то они разделены поверхностью решения в n-мерном пространстве. Для случая минимизации вероятности ошибки поверхность решения задается уравнением.

В данном уравнении приходится оперировать с вероятностями. Часто вместо вероятностей удобнее работать с функцией от вероятности:

,

где функция f монотонно возрастает.

Таким образом, поверхность решения будет задаваться уравнением:

,, .

Распределение Гаусса (нормальное распределение) очень широко используется по причине вычислительного удобства и адекватности во многих случаях. Рассмотрим многомерную плотность нормального распределения:

, i=1,2,…, m, (1. 1)

где = M [x] - математическое ожидание случайной величины x в классе , — матрица ковариации размерности для класса, || - определитель матрицы ковариации.

Здесь x, - это вектора-столбцы, а , - вектора-строки.

Рассмотрим логарифмическую решающую функцию:

, где.

Эта функция представляет собой квадратичную форму.

Следовательно, разделяющая поверхность является гиперповерхностью второго порядка.

=i: lnP () — ->

> lnP () — -,j?i. В случае если

P () =P () =…=P ()

=i: — -> --

,j?i.

Параметры многомерной плотности распределения могут быть оценены, основываясь на множестве прецедентов, по следующим формулам:

, (1. 2)

(или — несмещённая оценка), где — количество прецедентов из класса. Известно ([11]), что при и выборке из совокупности нормально распределенных образов оценка матрицы, определяемая таким образом, с вероятностью 1 обладает обратной матрицей.

Пример. Пусть =,, ,, .

Тогда, ,, .

,

,

.

Таким образом, разделяющая поверхность () имеет вид:

-

эллипс с центром в точке.

Точки, лежащие внутри эллипса относим к классу, вне — к.

Линейный классификатор

Классификация образов с помощью линейной разделяющей гиперплоскости подробно описана в работах [1], [2], [3].

Далее будем рассматривать задачу распознавания образов для двух классов (m=2).

Предположим, что классы и разделимы в с помощью линейной гиперплоскости, а вектор признаков x распределён случайно с некоторой плотностью вероятности p (x), -выборка из распределения случайной величины x. Линейная гиперплоскость задаётся уравнением, где - весовой вектор, - порог.

Введём в рассмотрение функцию

Величину будем называть средним риском, а величину — эмпирическим риском на выборке. Задача состоит в нахождении вектора весов и порога, на которых достигается минимум среднего риска (т.е.). Эту задачу заменим задачей минимизации эмпирического риска (т.е. нужно найти и, такие, что). Известно ([3]), что для заданных, существует число, такое, что при.

Таким образом, необходимо найти такие вектор весов и порог, чтобы

,.

Общепринято переходить к «пополненному» пространству:

,.

Очевидно, что два множества разделимы в гиперповерхностью =0, тогда и только тогда, когда они разделимы в «пополненном» пространстве гиперплоскостью.

Алгоритм персептрона

Необходимо найти вектор весов w, такой что для обучающей выборки было выполнено:

(2. 1)

Пусть — начальный вектор весов, который выбирается произвольно. k-й шаг итерационной процедуры обучения выглядит следующим образом: если и, то, где с>0 — корректирующее приращение; если и ,; в противном случае (и или и) не изменяется, т. е..

Алгоритм вносит изменения в вектор весов w в том и только том случае, если образ, предъявленный на k-м шаге обучения, был при выполнении этого шага неправильно классифицирован с помощью соответствующего вектора весов. Прецеденты предъявляются циклически, т. е. после предъявления последнего снова предъявляется первый. Итерационный процесс завершается при правильной классификации всех векторов-прецедентов с помощью вектора весов.

Пример. Пусть множество прецедентов имеет вид:

=; =; =; =.

Пополним векторы-прецеденты:, .

Положим c=1 и =0. Предъявляя векторы-прецеденты, получим:

,

,

,

.

Положим, ,, .

, ,

,.

Положим, ,, .

, ,

,.

Положим.

.

Таким образом, для всех прецедентом из первого класса и для всех прецедентом из второго класса. Необходимый нам вектор весов найден и итерационная процедура окончена.

Алгоритм персептрона можно представить в другой, эквивалентной форме, умножив пополненные образы класса на (-1). Итерационный процесс персептрона в таком случае принимает вид:

(2. 2)

Теорема 2. 1 (Новиков). Пусть — произвольная бесконечная ограниченная по модулю последовательность векторов из двух непересекающихся множеств и; и пусть существует гиперплоскость, проходящая через начало координат и разделяющая и, т. е. существует единичный вектор, такой, что

для всех ,

для всех и.

Тогда при использовании алгоритма персептрона с начальным вектором весов число коррекций весового вектора не превзойдёт числа

,

где обозначает операцию взятия целой части числа.

Доказательство. Рассмотрим новую последовательность векторов:

.

Будем рассматривать алгоритм персептрона в виде (2. 2). Будем считать для простоты c=1.

Если в момент i+1 происходит коррекция вектора весов (т.е.), то. Учитывая то, что и имеем. Таким образом, если к моменту t произошло ровно k коррекций вектора весов, то

, (2. 3)

поскольку.

По условию теоремы существует единичный вектор w такой, что для всех i.

Оценим величину. В начальный момент. Если в момент i+1 происходит коррекция вектора весов, то

.

Таким образом, если к моменту t произошло ровно k коррекций вектора весов, то.

В силу неравенства Коши и, следовательно, справедливо неравенство

. (2. 4)

Сопоставляя (2. 3) и (2. 4), убеждаемся, что эти неравенства могут одновременно выполнятся только при. Следовательно число коррекций вектора весов не превосходит, после чего все остальные члены последовательности будут опознаваться правильно. ч. т.д.

Введём обозначение

, (2. 5)

где, N-число прецедентов. Очевидно, что система неравенств (2. 1) эквивалентна

. (2. 6)

Можно показать, что алгоритм персептрона является частным случаем метода градиента для нахождения минимума некоторой функции критерия J (w, X). Итерационная схема метода градиента имеет вид

,

где c> 0. Функцией критерия в данном случае можно взять

,

минимум которой достигается при. Другим примером использования метода градиента для нахождения линейной разделяющей гиперплоскости является НСКО — алгоритм (алгоритм Хо — Кашьяпа).

НСКО — алгоритм (алгоритм наименьшей средне-квадратичной ошибки)

Рассмотрим систему линейных неравенств (2. 6). Будем искать векторы w и b, обеспечивающие выполнение равенства Xw = b, где все компоненты вектора b положительны.

Рассмотрим функцию критерия. Функция достигает своего минимума при выполнении условия Xw = b.

Функция минимизируется по обеим переменным w и b. Градиентами в нашей задаче будут и.

Поскольку на вектор весов w не налагается никаких ограничений, можно положить, что приводит к выражению

, (2. 7)

где — объект, который часто называют обобщенным обращением матрицы X. Так как все компоненты вектора b должны быть положительными, его следует изменять только таким образом, чтобы это условие не нарушалось. Последнее можно обеспечить, положив

, (2. 8)

где

, (2. 9)

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

Из (2. 7) и (2. 8) следует, что

.

Положив, приходим к следующему алгоритму:

— произвольный вектор, все координаты которого положительны,

,

,

,

.

Значение также можно определить, используя соотношение.

Если неравенства Xw > 0 имеют решение, данный алгоритм сходится за конечное число шагов при ([1]). Более того, если на любом шаге итерации все компоненты вектора становятся неположительными (но не все — равными нулю), это означает, что заданные классы нельзя разделить с помощью линейной гиперплоскости. Естественно, в тех случаях, когда = 0, вектор является решением, так как из этого следует, что и -положительный вектор. Практически обычно считается, что алгоритм определил вектор решения, если X> 0. Это условие сходимости алгоритма обычно выполняется раньше, чем достигается равенство = 0.

Мы допускали, что (Х’Х) обладает обратной матрицей — это условие выполняется, когда ранг матрицы X равен n+1.

Определение. Множество, состоящее из N точек n-мерного пространства, называют хорошо размещённым, если ни одно из его подмножеств, состоящее из n+1 точек, не лежит на (n-1) — мерной гиперплоскости.

Известно, что если по крайней мере n + 1 образов из использованных при формировании матрицы X обладают хорошим размещением, то матрица X непременно имеет ранг n+1.

Примеры. а) Рассмотрим класс, содержащий образы { (0,0) ', (0,1) '}, и класс, содержащий образы { (1,0) ', (1, 1) '}. Матрица X имеет вид:

.

Обобщенная обратная матрица равна

.

Положив = (l, 1,1,1) ' и с=1 и применяя алгоритм, получим

. Так как ,

то — необходимый нам вектор весов.

б) Рассмотрим множества ={ (0,0) ', (1,1) '} и = { (0, 1) ', (1,0) '}; эти множества не разделимы с помощью линейной гиперплоскости. Положив с = 1 и = (l, 1,1,1) ', получим

, ,

,.

То, что вектор — отрицательный, означает отсутствие решения у неравенства Xw > 0.

Линейный классификатор в случае нескольких классов

Необходимо найти вектора весов, таких, что для выполнено

, при.

Схема Кеслера (обобщение алгоритмов на случай нескольких классов)

Для каждого вектора-прецедента x из построим (m-1) векторов размерности (n+1) m:

, ,

и вектор, где () — координаты вектора x

Если x относится к классу, то, j = 1,2,. ,m,, т.к. и.

Таким образом, задача заключается в нахождении (n +1) m - мерного вектора весов, такого, чтобы для каждого из (m - 1) N векторов было выполнено. Если вектора в исходной задаче разделимы, то это можно сделать с помощью описанных выше алгоритмов.

Метод потенциальных функций

Основополагающей работой для этого метода является [4].

Рассмотрим задачу распознавания двух классов.

Будем искать решающую функцию d (x), такую, что

Если ввести аналогию между точками, представляющими векторы-прецеденты, и некоторым источником энергии, то в любой из этих точек потенциал достигает максимального значения и быстро уменьшается при переходе во всякую точку, отстоящую от точки, представляющей выборочный образ. На основе этой аналогии можно допустить существование эквипотенциальных контуров, которые описываются потенциальной функцией K (x, ). Можно считать, что кластер, образованный выборочными образами, принадлежащими классу, образует «плато», причем выборочные образы размещаются на вершинах некоторой группы холмов. Подобную геометрическую интерпретацию можно ввести и для образов класса. Эти два «плато» разделены «долиной», в которой, как считается, потенциал падает до нуля. На основе таких интуитивных доводов создан метод потенциальных функций, позволяющий при проведении классификации определять решающие функции, выражая их через потенциальные функции K (x, ).

Будем предполагать, что функция d (x) представима в виде

,

где — некоторая бесконечная последовательность функций над пространством признаков (система может быть конечная, т. е. начиная с некоторого номера все). Часто эта система предполагается ортонормированной.

В качестве потенциальной функции K (x, y) рассмотрим функцию вида

,

где коэффициенты удовлетворяют условиям:

1);

2).

Функция K (x, y) предполагается ограниченной при.

Иногда на потенциальную функцию K (x, y) накладываются следующие ограничения: a) K (x, y) > 0 для всех; b) для всех фиксированных функция — монотонно убывающая функция, с максимумом в точке 0.

Наиболее удобны такие ряды, которые можно аналитически просуммировать и записать K (x, y) в свёрнутом виде. Целесообразно иметь в виду полную систему функций с тем, чтобы расширить класс функций d (x), которые могут быть аппроксимированы с помощью метода потенциальных функций.

Практически при использовании метода надо знать лишь свёрнутое выражение K (x, y) и быть уверенными, что решающая функция d (x) представима разложением по системе функций. Фактически знать эту систему и коэффициенты не требуется.

Если, то в качестве потенциальных функций можно взять, например, такие:

,

,

,

где б — положительная константа.

Рассмотрим итерационную процедуру нахождения решающей функции. Каждый шаг состоит в предъявлении очередного вектора-прецедента и коррекции приближения решающей функции. При этом прецеденты предъявляются циклически, т. е. после предъявления последнего снова предъявляется первый. В качестве начального приближения можно взять любую функцию с произвольными коэффициентами, удовлетворяющими условию. В частности этому условию заведомо удовлетворяет функция.

Итерационный процесс имеет вид

,, (3. 1)

где

. (3. 2)

Итерационный процесс завершается, если на некотором шаге

,

для всех векторов-прецедентов. Полученная функция и будет необходимым нам приближением решающей функции.

Пример. Пусть множество прецедентов имеет вид:

.

В качестве потенциальной функции возьмём

.

.

,.

,.

,

.

Положим, ,, ,, .

,.

,

,.

,.

,.

,.

Таким образом, все векторы-прецеденты классифицируются правильно при помощи функции

Некоторые сведения о сходимости итерационного процесса

Теорема 3. 1 Пусть множества и в пространстве X и система функций таковы, что:

1. Существует решающая функция, представимая в виде ,

такая, что, где > 0;

2. Потенциальная функция K (x, y) представлена в виде

и выполнено условие;

3) появление точек обучающей последовательности — независимые случайные события, определяемые плотностью вероятности p (x),

.

Тогда для алгоритма, определяемого соотношениями (3. 1), (3. 2) имеет место

().

Теорема 3. 2 (О скорости сходимости алгоритма.) (А. Новиков)

Пусть — бесконечная последовательность обучающих образов, выбранных из обучающего множества, причем и. Допустим, что выполнены предположения 1 и 2 предыдущей теоремы. Тогда существует целое число, не зависящее от выбора обучающей последовательности, и такое, что при использовании процедуры (3. 1), (3. 2) число коррекций решающей функции не превышает величины R.

Теорема 3. 3 (О свойствах сходимости алгоритма) Пусть выполнены условия 1, 2 теоремы 3. 1 и обучающая выборка образов обладает следующими статистическими свойствами:

(а) точки обучающей последовательности появляются независимо с одной и той же плотностью распределения вероятности;

(б) если на k-м шаге алгоритма обучения решающая функция не обеспечивает правильной классификации всех образов, ,.,, то с положительной вероятностью будет предъявлен образ, корректирующий ошибку.

Тогда с вероятностью 1 можно определить конечное число шагов R, таких, что приближение решающей функции на R-м шаге

.

Другими словами, последовательная аппроксимация решающей функции с вероятностью 1 сходится к решающей функции за конечное число предъявлений образов обучающей выборки.

Обобщение на случай нескольких классов.

Необходимо построить решающие функции, такие что для выполнено

, при.

Для удобства будем считать, что начальные приближения решающих функций, ,., в начале процесса обучения равны нулю. Пусть на (k+1) — м шаге итерации предъявляется выборочный образ, принадлежащий классу. Если для всех выполняется условие, то значения решающих функций изменению не подвергаются, т. е.

, i=1,2,…, m.

Если же для некоторого l, то производятся следующие коррекции:

,

,, .

Примеры работы классификаторов

Частным случаем задачи распознавания образов является задача распознавания изображений. Примером распознавания изображений может служить опознавание по фотографиям людей, изображённых на них.

В этом случае:

W — множество цифровых фотографий людей;

w?ОW? — конкретная фотография;

— координаты пикселей фотографии.

w (t): TR - функция яркости в точке;

— класс фотографий определённого человека;

x (w): W®? — совокупность некоторых численных измерений фотографии;

{ (,), j =?1,2. ,N} - предъявленные фотографии, с указанием, кто на них изображён.

Задача состоит в опознании человека, изображённого на предъявляемой фотографии.

Иногда для удобства считают. Это позволяет заменить суммирование на интегрирование и т. п.

Примеры. Рассмотрим задачу распознавания двух людей по их фотографиям. Объектами фотографирования любезно согласились быть одногруппники. Возьмем в качестве признаков следующие величины: — расстояние между глазами, -высота лба, -ширина подбородка, -высота лица.

Имеется по 10 фотографий каждого человека.

1) Данные измерений для фотографий из приложения 1:

;;

;;

;;

;;

;;

;;

;;

;;

;;

;.

Используем векторы для обучения классификатора, а векторы для проверки его работы.

а) Построение классификатора на основе байесовской теории решений.

Будем предполагать, что векторы признаков распределены по многомерному нормальному закону (1. 1).

Оценим величины и по формулам (1. 2):

;;

;

.

Вычислим детерминанты матриц, а также обратные к ним матрицы:

;;

;.

Появление людей на фотографиях считаем равновероятным, т. е..

Теоретическая ошибка классификации равна =0. 0244.

Обозначим =--. Наблюдаемый вектор x относим к классу, если >, и к классу, если <.

Подставим векторы:

=-13. 7849, = - 27. 0273,, т. е.;

=-9. 35 022, =-18. 9911,, т. е.;

=-11. 0102, =-33. 5553,, т. е.;

=-12. 8537, =-34. 3044,, т. е.;

=-13. 5589, =-24. 5123,, т. е.;

=-13. 354, =-31. 6996,, т. е.;

=-13. 0978, =-15. 2439,, т. е.;

=-12. 7515, =-46. 3663,, т. е.;

=-10. 1776, =-32. 9693,, т. е.;

=-26. 301, =-38. 5459,, т. е.;

=-22. 8981, =-9. 35 568,, т. е.;

=-16. 1023, =-14. 3213,, т. е.;

=-34. 484, =-10. 4302,, т. е.;

=-36. 475, =-13. 6736,, т. е.;

=-35. 1632, =-14. 4313,, т. е.;

=-37. 1126, =-13. 4194,, т. е.;

=-32. 0896, =-13. 4305,, т. е.;

=-30. 1409, =-25. 8602,, т. е.;

=-68. 9038, =-35. 879,, т. е.;

=-17. 3442, =-22. 8997,, т. е. (ошибка).

Таким образом векторы классифицированы правильно, а на векторе допущена ошибка.

b) Линейный классификатор.

Вычислим вектор весов и порог с помощью НСКО-алгоритма:

(0. 529 709 0. 15 517 — 0. 716 574 — 0. 608 297), =15. 4855.

Решающая функция имеет вид.

Подставим векторы:

2. 47 118>0, т. е.; 2. 28 195>0, т. е.;

2. 46 052>0, т. е.; -2. 1 917<0, т. е.;

-4. 87 448<0, т. е.; -0. 240 255<0, т. е..

Таким образом все векторы классифицированы правильно.

c) Метод потенциальных функций.

Решающая функция имеет вид:

Подставим векторы:

5. 24289e-022>0, т. е.; 7. 58256e-010>0, т. е.;

2. 78947e-010>0, т. е.; -5. 52109e-042<0, т. е.;

-1. 97228e-108<0, т. е.; -2. 17052e-029<0, т. е..

Таким образом все векторы классифицированы правильно.

2) Данные измерений для фотографий из приложения 2:

;;

;;

;;

;;

;;

;;

;;

;;

;;

;.

Используем векторы для обучения классификатора, а векторы для проверки его работы.

a) Классификатор на основе байесовской теории решений.

Оценим векторы математических ожиданий и ковариационные матрицы, а также вычислим детерминанты ковариационных матриц и обратные к ним матрицы:

;

;;

;

;

;;

.

Теоретическая ошибка классификации равна =0. 0055.

Подставим векторы:

=-17. 9806, = - 29. 2829,, т. е.;

=-17. 1097, = - 110. 493,, т. е.;

=-14. 4975, = - 148. 414,, т. е.;

=-17. 4039, = - 129. 954,, т. е.;

=-16. 0859, = - 54. 5774,, т. е.;

= - 18. 4397, = - 97. 438,, т. е.;

=-17. 8703, = - 76. 7529,, т. е.;

=-14. 0773, = - 33. 8104,, т. е.;

=-14. 0588, = - 25. 814,, т. е.;

=-15. 737, = - 28. 7365,, т. е.;

=-27. 3696, = - 12. 8693,, т. е.;

=-21. 126, = - 13. 3989,, т. е.;

=-19. 4231, = - 11. 2735,, т. е.;

=-19. 3067, = - 11. 7294,, т. е.;

=-22. 7384, = - 11. 949,, т. е.;

=-22. 6172, = - 10. 4187,, т. е.;

=-32. 8185, = - 11. 1672,, т. е.;

=-24. 9424, = - 118. 715,, т. е. (ошибка);

=-19. 7379, = - 19. 077,, т. е.;

=-21. 262, = - 17. 569,, т. е..

Таким образом, векторы классифицированы правильно, а на векторе допущена ошибка.

b) Линейный классификатор.

Вычислим вектор весов и порог с помощью НСКО — алгоритма:

(0. 301 486 — 0. 170 882 0. 223 493 0. 577 138), =-9. 49 176.

Подставим векторы:

0. 817 191>0, т. е.;

0. 386 565>0, т. е.;

0. 691 381>0, т. е.;

-0. 324 593<0, т. е.;

-0. 612 653<0, т. е.;

-0. 596 915<0, т. е..

Таким образом, все векторы классифицированы правильно.

c) Метод потенциальных функций.

Решающая функция имеет вид:

.

Подставим векторы:

8. 85477e-070>0, т. е.;

3. 66582e-077>0, т. е.;

3. 48111e-057>0, т. е.;

-1. 19836e-070<0, т. е.;

-3. 97545e-031<0, т. е.;

-1. 15482e-017<0, т. е..

Таким образом, все векторы классифицированы правильно.

Выводы

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

Были написаны программы, реализующие эти методы, а также программа, вычисляющая теоретическую ошибку классификации для байесовского классификатора.

Работа классификаторов была проверена на практике. Для этого было сделано по 10 фотографий 4 людей и рассмотрено две задачи распознавания двух людей по их фотографиям. При этом 14 фотографий было использовано для обучения классификатора, а 6 — для проверки его работы. Получены следующие результаты:

линейный классификатор и метод потенциальных функций правильно классифицировали все проверочные фотографии;

байесовский классификатор совершил одну ошибку в каждой рассмотренной задаче.

Список использованной литературы

1. Р. Дуда, П. Харт Распознавание образов и анализ сцен, М.: «Мир», 1976 — 512 с. ;

2. Дж. Ту, Р. Гонсалес Принципы распознавания образов, М.: «Мир», 1978 — 411 с. ;

3. В. Н. Вапник, А. Я. Червоненкис Теория распознавания образов. Статистические проблемы обучения, М.: «Наука», 1974 — 416 с. ;

4. М. А. Айзерман, Э. М. Браверман, Л. И. Розоноэр Метод потенциальных функций в теории обучения машин, М.: «Наука», 1970 — 384 с. ;

5. Э. Патрик Основы теории распознавания образов, М.: «Советское радио», 1980 — 408 с.

6. Б. В. Анисимов, В. Д. Курганов, В. К. Злобин Распознавание и цифровая обработка изображений, М.: «Высшая школа», 1983 — 295 с. ;

7. А. Л. Горелик, В. А. Скрипкин Методы распознавания, М.: «Высшая школа», 1989 — 232 с. ;

8. В. С. Файн Опознавание изображений. Основы непрерывно-групповой теории и её приложения, М.: «Наука», 1970 — 299 с. ;

9. Н. Г. Загоруйко Методы распознавания и их применение, М.: «Советское радио», 1972 — 208 с. ;

10. У. Гренандер Лекции по теории образов: в 3 т., М.: «Мир», 1979;

11.Т. Андерсон Введение в многомерный статистический анализ, М.: Наука, 1963. — 500с. ;

12. А. С. Потапов Распознавание образов и машинное восприятие, М.: «Политехника», 2007 — 552 с.

Приложения

Приложение 1

Приложение 2

Приложение 3

Программа на C++, реализующая байесовский классификатор:

#include < stdio. h>

#include < stdlib. h>

#include < iostream. h>

#include < fstream. h>

#include < math. h>

int num_of_cl, num_of_pr;

struct s{

double *d;

s *next;

}*root;

class clas{

double *m;

double *d;

double det;

~clas () {

delete m;

delete d;

}

public:

void learn (int i) {

m=new double [num_of_pr];

for (int j=0; j< num_of_pr; j++) m [j] =0;

int n=0;

s* st=root;

while (st! =NULL) {

if (st->d [0] ==i) {

n++;

for (j=0; j< num_of_pr; j++) m [j] =m [j] +st->d [1+j];

}

st=st-> next;

}

for (j=0; j< num_of_pr; j++) m [j] /=n;

double *a=new double [num_of_pr*num_of_pr];

for (j=0; j< num_of_pr; j++)

for (int k=0; k< num_of_pr; k++) a [j*num_of_pr+k] =0;

st=root;

while (st! =NULL) {

if (st->d [0] ==i) {

for (j=0; j< num_of_pr; j++) {

for (int k=0; k< num_of_pr; k++) {

a [j*num_of_pr+k] =a [j*num_of_pr+k] +

(st->d [1+j] - m [j]) * (st->d [1+k] - m [k]);

}

}

}

st=st-> next;

}

for (int z=0; z< num_of_pr*num_of_pr; z++) a [z] /=n;

d=new double [num_of_pr*num_of_pr];

det=1;

for (int u=0; u< num_of_pr; u++) {

for (int j=0; j< num_of_pr; j++) {

d [u*num_of_pr+j] = (u==j)? 1. 0: 0. 0;

}

}

for (int k=0; k< num_of_pr; k++) {

int max=k;

for (u=k+1; u< num_of_pr; u++)

if (fabs (a [u*num_of_pr+k]) > fabs (a [max*num_of_pr+k])) max=u;

if (a [max*num_of_pr+k] ==0. 0) {

cout< <"Matrix haven’t invertn";

return;

}

if (max! =k) {

double buf;

for (u=k; u< num_of_pr; u++) {

buf=a [max*num_of_pr+u];

a [max*num_of_pr+u] =a [k*num_of_pr+u];

a [k*num_of_pr+u] =buf;

}

for (u=0; u< num_of_pr; u++) {

buf=d [max*num_of_pr+u];

d [max*num_of_pr+u] =d [k*num_of_pr+u];

d [k*num_of_pr+u] =buf;

}

}

double akk=a [k*num_of_pr+k];

det*=fabs (akk);

for (u=k; u< num_of_pr; u++) a [k*num_of_pr+u] /=akk;

for (u=0; u< num_of_pr; u++) d [k*num_of_pr+u] /=akk;

for (u=0; u< num_of_pr; u++) {

if (u==k) continue;

double aik=a [u*num_of_pr+k];

for (int j=k; j< num_of_pr; j++)

a [u*num_of_pr+j] - =a [k*num_of_pr+j] *aik;

for (j=0; j< num_of_pr; j++)

d [u*num_of_pr+j] - =d [k*num_of_pr+j] *aik;

}

}

}

double p (double *x) {

double *q=new double [num_of_pr];

for (int i=0; i< num_of_pr; i++) {

q [i] =0;

for (int j=0; j< num_of_pr; j++)

q [i] +=d [i*num_of_pr+j] * (x [j] - m [j]);

}

double s=0;

for (i=0; i< num_of_pr; i++) s-= (x [i] - m [i]) *q [i];

delete q;

s-=log (det);

return s;

}

};

void main () {

ifstream f («data. txt», ios: in);

if (! f) cout< <"can't open file";

f> >num_of_cl;

f> >num_of_pr;

s* nov=root,*st=NULL;

while (! f. eof ()) {

nov=new s;

if (st! =NULL) st-> next=nov;

else root=nov;

nov-> d=new double [num_of_pr+1];

for (int i=0; i< =num_of_pr; i++) f> >d [i];

nov-> next=NULL;

st=nov;

}

clas *cs=new clas [num_of_cl];

for (int i=0; i< num_of_cl; i++) cs [i]. learn (i+1);

double *x=new double [num_of_pr];

while (1) {

for (i=0; i< num_of_pr; i++) cin> >x [i];

double maxp=cs [0]. p (x), p;

int maxn=0;

cout< <"p [1] = «< <p<<endl;

for (i=1; i< num_of_cl; i++) {

p=cs [i]. p (x);

cout< <"p ["< <i+1<<"] = «< <p<<endl;

if (p> maxp) {

maxp=p;

maxn=i;

}

}

cout< <"class = «< <maxn+1<<endl;

};

}

Приложение 4.

Программа в Matlab, вычисляющая ошибку классификации для Байе-совского классификатора:

m1= [37; 69. 8571; 64. 8571; 131. 286]

D1= [0. 956 543 — 0. 310 397 — 0. 26 775 — 0. 123 935;

0. 310 397 0. 240 828 0. 182 033 — 0. 866 612;

0. 26 775 0. 182 033 0. 259 473 — 0. 544 607;

0. 123 935 — 0. 866 612 — 0. 544 607 0. 725 479]

det1=4582. 13

m2= [42. 5714; 72. 8571; 67. 1429; 136. 571]

D2= [0. 50 731 — 0. 835 164 0. 116 121 — 0. 474 793;

0. 835 164 0. 162 212 0. 311 001 — 0. 122 388;

0. 116 121 0. 311 001 0. 824 619 — 0. 171 865;

0. 474 793 — 0. 122 388 — 0. 171 865 0. 14 854]

det2=6143. 35

bound= [30 64 57 124; 50 80 74 144]

in=0. 5*quad (@fdep1,bound (1,4), bound (2,4),

1e-8,0,m1,m2,D1,D2,det1,det2,bound)

m1= [41. 1429; 81. 2857; 73. 8571; 150. 857]

D1= [0. 471 952 0. 482 967 — 0. 408 458 — 0. 181 512;

0. 482 967 0. 288 192 0. 488 604 — 0. 437 212;

0. 408 458 0. 488 604 0. 305 891 0. 87 409;

0. 181 512 — 0. 437 212 0. 87 409 0. 104 613]

m2= [31. 5714; 58. 7143; 65. 4286; 120. 429]

D2= [0. 217 634 0. 445 519 0. 143 652 — 0. 154 782;

0. 445 519 0. 188 156 0. 196 888 — 0. 251 078;

0. 143 652 0. 196 888 0. 478 629 — 0. 414 925;

0. 154 782 — 0. 251 078 — 0. 414 925 0. 474 784]

det1=467 570

det2=2513. 47

bound= [27 54 61 116; 46 86 78 155]

in=0. 5*quad (@fdep1,bound (1,4), bound (2,4),

1e-8,0,m1,m2,D1,D2,det1,det2,bound)

function f=fdep1 (x, m1, m2,c1,c2,det1,det2,bound)

n=size (x);

n=n (2);

for i=1: n

f (i) =quadl (@fdep2,bound (1,3), bound (2,3), 1e-8,0,x (i), m1, m2,c1,c2,det1,det2,bound);

end;

function ff=fdep2 (x1,x2,m1,m2,c1,c2,det1,det2,bound)

n=size (x1);

n=n (2);

for i=1: n

ff (i) =quadl (@fdep3,bound (1,2), bound (2,2), 1e-8,0,x1 (i), x2, m1,m2,c1,c2,det1,det2,bound);

end;

function ff=fdep3 (x1,x2,x3,m1,m2,c1,c2,det1,det2,bound)

n=size (x1);

n=n (2);

for i=1: n

ff (i) =quadl (@fdep4,bound (1,1), bound (2,1), 1e-8,0,x1 (i), x2, x3,m1,m2,c1,c2,det1,det2);

end;

function ff=fdep4 (x0,x2,x3,x4,m1,m2,c1,c2,det1,det2)

n=size (x0);

n=n (2);

for i=1: n

x1=x0 (i);

x= [x1; x2; x3; x4];

p1= ((4* (pi2) *sqrt (det1)) ^ (-1)) *exp (-0. 5* (x-m1) '*c1* (x-m1));

p2= ((4* (pi2) *sqrt (det2)) ^ (-1)) *exp (-0. 5* (x-m2) '*c2* (x-m2));

ff (i) =min (p1,p2);

end;

Приложение 5

Программа на C++, реализующая НСКО-алгоритм:

#include < stdio. h>

#include < stdlib. h>

#include < iostream. h>

#include < fstream. h>

#include < math. h>

struct s{

double *d;

s *next;

}*root;

void main () {

ifstream f («data. txt», ios: in);

if (! f) cout< <"can't open file";

int num_of_cl, num_of_pr;

f> >num_of_cl;

num_of_cl=2;

f> >num_of_pr;

s* nov=root,*st=NULL;

int n=0;

while (! f. eof ()) {

nov=new s;

if (st! =NULL) st-> next=nov;

else root=nov;

nov-> d=new double [num_of_pr+1];

for (int i=0; i< =num_of_pr; i++) f> > (nov->d [i]);

nov-> next=NULL;

st=nov;

n++;

}

double *x=new double [n* (num_of_pr+1)];

st=root;

for (int i=0; i< n; i++, st=st-> next) {

int ms=st->d [0] ==1? 1: — 1;

for (int j=0; j< num_of_pr; j++) x [i* (num_of_pr+1) +j] =ms*st->d [j+1];

x [i* (num_of_pr+1) +num_of_pr] =ms;

}

double *a=new double [ (num_of_pr+1) * (num_of_pr+1)];

for (i=0; i< =num_of_pr; i++) {

for (int j=0; j< =num_of_pr; j++) {

double q=0;

for (int pi=0; pi< n; pi++)

q+=x [pi* (num_of_pr+1) +i] *x [pi* (num_of_pr+1) +j];

a [i* (num_of_pr+1) +j] =q;

}

}

num_of_pr++;

double *d=new double [num_of_pr*num_of_pr];

for (int u=0; u< num_of_pr; u++) {

for (int j=0; j< num_of_pr; j++) {

d [u*num_of_pr+j] = (u==j)? 1. 0: 0. 0;

}

}

for (int k=0; k< num_of_pr; k++) {

int max=k;

for (u=k+1; u< num_of_pr; u++)

if (fabs (a [u*num_of_pr+k]) > fabs (a [max*num_of_pr+k])) max=u;

if (a [max*num_of_pr+k] ==0. 0) {

cout< <"Matrix haven’t invertn";

return;

}

if (max! =k) {

double buf;

for (u=k; u< num_of_pr; u++) {

buf=a [max*num_of_pr+u];

a [max*num_of_pr+u] =a [k*num_of_pr+u];

a [k*num_of_pr+u] =buf;

}

for (u=0; u< num_of_pr; u++) {

buf=d [max*num_of_pr+u];

d [max*num_of_pr+u] =d [k*num_of_pr+u];

d [k*num_of_pr+u] =buf;

}

}

double akk=a [k*num_of_pr+k];

for (u=k; u< num_of_pr; u++) a [k*num_of_pr+u] /=akk;

for (u=0; u< num_of_pr; u++) d [k*num_of_pr+u] /=akk;

for (u=0; u< num_of_pr; u++) {

if (u==k) continue;

double aik=a [u*num_of_pr+k];

for (int j=k; j< num_of_pr; j++)

a [u*num_of_pr+j] - =a [k*num_of_pr+j] *aik;

for (j=0; j< num_of_pr; j++)

d [u*num_of_pr+j] - =d [k*num_of_pr+j] *aik;

}

}

double *xti=new double [num_of_pr*n];

for (i=0; i< num_of_pr; i++) {

for (int j=0; j< n; j++) {

xti [i*n+j] =0;

for (int w=0; w< num_of_pr; w++)

xti [i*n+j] +=d [i*num_of_pr+w] *x [j*num_of_pr+w];

}

}

double *w=new double [num_of_pr];

double *e=new double [n];

double *b=new double [n];

int eb0=0,em0=0,bul=1;

for (i=0; i< n; i++) b [i] =1;

for (i=0; i< num_of_pr; i++) {

w [i] =0;

for (int j=0; j< n; j++) w [i] +=xti [i*n+j] *b [j];

}

for (i=0; i< n; i++) {

e [i] =0;

for (int j=0; j< num_of_pr; j++) e [i] +=x [i*num_of_pr+j] *w [j];

}

for (i=0; i< n; i++) {

if (e [i] < =0) bul=0;

e [i] - =b [i];

}

for (i=0; i< n; i++) {

if (e [i] > 0) eb0++;

if (e [i] < 0) em0++;

}

int count=0;

while (bul==0) {

if ((em0> 0) & & (eb0==0)) {

cout< <"mnozhestva ne razdelimin";

return;

}

for (i=0; i< n; i++) e [i] =e [i] +fabs (e [i]);

for (i=0; i< num_of_pr; i++) {

for (int j=0; j< n; j++) w [i] +=xti [i*n+j] *e [j];

b [i] +=e [i];

}

for (i=0; i< n; i++) {

e [i] =0;

for (int j=0; j< num_of_pr; j++) e [i] +=x [i*num_of_pr+j] *w [j];

}

bul=1;

for (i=0; i< n; i++) {

if (e [i] < =0) bul=0;

e [i] - =b [i];

}

eb0=em0=0;

for (i=0; i< n; i++) {

if (e [i] > 0) eb0++;

if (e [i] < 0) em0++;

}

count++;

};

double *v=new double [--num_of_pr];

while (1) {

for (i=0; i< num_of_pr; i++) cin> >v [i];

double d=w [num_of_pr];

for (int j=0; j< num_of_pr; j++) d+=v [j] *w [j];

cout< <d<<endl;

if (d> 0) cout< <"1 classn";

else if (d< 0) cout< <"2 classn";

else cout< <"unknown classn";

};

}

Приложение 6.

Программа на C++, реализующая алгоритм метода потенциальных функций:

#include < stdio. h>

#include < stdlib. h>

#include < iostream. h>

#include < fstream. h>

#include < math. h>

struct s{

double *d;

s *next;

}*root;

double *xk;

int num_of_cl, num_of_pr,*c, n=0;

double Kk (double *x, int k) {

double q=0;

for (int i=0; i< num_of_pr; i++)

q+= (x [i] - xk [k* (num_of_pr+1) +i+1]) * (x [i] - xk [k* (num_of_pr+1) +i+1]);

return exp (-q);

}

double K (double *x) {

double q=0;

for (int i=0; i< n; i++) if (c [i]! =0) q+=c [i] *Kk (x, i);

return q;

}

void main () {

ifstream f («data. txt», ios: in);

if (! f) cout< <"can't open file";

f> >num_of_cl;

num_of_cl=2;

f> >num_of_pr;

s* nov=root,*st=NULL;

while (! f. eof ()) {

nov=new s;

if (st! =NULL) st-> next=nov;

else root=nov;

nov-> d=new double [num_of_pr+1];

for (int i=0; i< =num_of_pr; i++) f> > (nov->d [i]);

nov-> next=NULL;

st=nov;

n++;

}

xk=new double [n* (num_of_pr+1)];

c=new int [n];

st=root;

for (int i=0; i< n; i++, st=st-> next) {

for (int j=0; j< =num_of_pr; j++) xk [i* (num_of_pr+1) +j] =st->d [j];

c [i] =0;

}

int bul;

do{

bul=0;

for (i=0; i< n; i++) {

double q=K (& (xk [i* (num_of_pr+1) +1]));

if (xk [i* (num_of_pr+1)] ==1) {

if (q< =0) {

c [i] +=1;

bul=1;

}

}else{

if (q> =0) {

c [i] - =1;

bul=1;

}

}

}

}while (bul);

double *x=new double [num_of_pr];

while (1) {

for (i=0; i< num_of_pr; i++) cin> >x [i];

double q=K (x);

cout< <q<<endl;

if (q> =0) cout< <"1 class"< <endl;

else cout< <"2 class"< <endl;

};

}

Аннотация

В данной работе рассматривается три метода распознавания образов (классификатора): байесовский классификатор, линейный классификатор, метод потенциальных функций. На основе указанных методов была разработана программа распознавания человека по его фотографиям. Были получены экспериментальные результаты о точности работы рассмотренных методов.

Анотація

У даній роботі розглядається три методи розпізнавання образів (кла-сифікатора): байесовський класифікатор, лінійний класифікатор, метод потенційних функцій. На основі зазначених методів була розроблена програма розпізнавання людини за його фотографіями. Були отримані експериментальні результати про точність роботи розглянутих методів.

Annotation

Three methods of recognition of patterns (classifier) are considered in this work: Bayes classifier, linear classifier, method of potential functions. On the basis of the indicated methods was developed the program of recognition of man on his pictures. Experimental results about exactness of work of the considered methods were obtained.

ПоказатьСвернуть
Заполнить форму текущей работой