Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Подготовка учащихся общеобразовательных школ к успешной сдаче единого государственного экзамена по-прежнему остаётся одной из важных задач в работе об...полностью>>
'Документ'
Методика анализа информации о результатах образовательной деятельности в процедуре оценки профессионализма и продуктивности педагогического труда соис...полностью>>
'Документ'
огурцы солёные, томат) 100 75-00 Гарниры Греча рассыпчатая 150 1 -00 Макароны отварные 150 10-00 Капуста тушёная 150 30-00 Рис отварной 150 10-00 Пюре...полностью>>
'Документ'
6.3. Регулярно и систематически опрашивать, выставляя оценки своевременно, не допуская скопления оценок в конце четверти, когда ученик уже не имеет во...полностью>>

Главная > Реферат

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Содержание

Введение 2

1. Основные понятия 4

1.1. Основные задачи, возникающие при разработке систем распознавания образов 7

1.2. Краткое описание концепций 14

1.2.1. Принцип перечисления членов класса 14

1.2.2. Принцип общности свойств 15

1.2.3. Принцип кластеризации 16

1.3. Краткое описание методов 17

1.3.1. Эвристические методы 17

1.3.2. Математические методы 17

1.3.3. Лингвистические (синтаксические) методы 18

2. Обучаемые классификаторы образов 21

2.1. Алгоритм перцептрона и его модификации 22

2.2. Градиентные алгоритмы классификации образов 24

2.3. Алгоритм наименьшей среднеквадратичной ошибки 26

3. Описание разработанного программного обеспечения 29

3.1. Алгоритм работы программы 29

3.2. Описание программы и инструкции для пользователя 30

3.3. Тестовый пример 32

Выводы 35

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

Приложение Б. Листинг программы 38

Введение

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

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

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

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

1. Основные понятия

Способность «распознавать» считается основным свойством человеческих существ, как, впрочем, и других живых организ­мов. Образ представляет собой описание объекта. В каждое мгновение нашего бодрствования мы совершаем акты распозна­вания. Мы опознаем окружающие нас объекты и в соответствии с этим перемещаемся и совершаем определенные действия. Мы можем заметить в толпе друга и понять, что он говорит, можем узнать голос знакомого, прочесть рукопись и идентифицировать отпечатки пальцев, можем отличить улыбку от злобной гримасы. Человеческое существо представляет собой очень сложную ин­формационную систему—в определенной степени это опре­деляется чрезвычайно развитыми у человека способностями распознавать образы.

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

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

В задачах распознавания образов можно выделить два основных направления.

Изучение способностей к распознаванию, которыми обла­дают человеческие существа и другие живые организмы.

Развитие теории и методов построения устройств, пред­назначенных для решения отдельных задач распознавания обра­зов в определенных прикладных областях.

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

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

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

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

1.1. Основные задачи, возникающие при разработке систем распознавания образов

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

(1.1)

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

Второй пример проиллюстрирован на рис. 1.1,6. В этом слу­чае образами служат непрерывные функции (типа звуковых сигналов) переменной t. Если измерение значений функций про­изводится в дискретных точках t1, t2 ..., tn, вектор образа можно сформировать, приняв x1=f(t1), x2=f(t2),... xn= f (tn).

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

Рис. 1.1. Две простые схемы порождения вектора образа.

что эти векторы везде будут вектор-столбцами, как в уравнении (1.1). Эквивалентная запись x = (x1, х2 ..., xn )т.

Векторы образов содержат всю поддающуюся измерению информацию об образах. Процесс измерения, которому подвер­гаются объекты определенного класса образов, можно рассмат­ривать как процесс кодирования, заключающийся в присвоении каждой характеристике образа символа из множества элементов алфавита {хi}. Когда измерения приводят к информации, пред­ставленной действительными числами, часто оказывается полез­ным рассматривать векторы образов в качестве точек n-мерного евклидова пространства. Множество образов, принадлежащих одному классу, соответствует совокупности точек, рассеянных в некоторой области пространства измерений. Соответствующий простой пример приведен на рис. 1.2 для случая двух классов, обозначенных ω1 и ω2. В этом примере предполагается, что классы ω1 и ω2 представляют соответственно группы футболи­стов-профессионалов и жокеев. Каждый «образ» характери­зуется результатами двух измерений: ростом и весом. Векторы образов имеют, следовательно, вид x = (x1, х2)т где параметр x1 - рост, а параметр х2 - вес. Каждый вектор образа можно считать точкой двумерного пространства. Как следует из рис. 1.2, эти два класса образуют непересекающиеся множества, что объясняется характером измерявшихся параметров.

Рис. 1.2. Два непересекающихся класса образов.

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

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

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

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

Пусть эти границы опреде­лены, например, решающими функциями d1(x), d2(х), ... ..., dм(х). Эти функции, называемые также дискриминантными функциями, представляют собой скалярные и однозначные функ­ции образа X. Если di(х) > dj(х) для всех i, j= 1, 2, ..., М, j ≠ i, то образ X принадлежит классу ωi. Другими словами, если i-я решающая функция di(x) имеет наибольшее значение, то х є ωi. Содержательной иллюстрацией подобной схемы автома­тической классификации, основанной на реализации процесса принятия решения, служит приведенная на рис. 1.3 блок-схема (на схеме ГРФ означает «генератор решающих функций»).

Рис. 1.3. Блок-схема системы классификации образов.

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

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

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

Рис. 1.4. Блок-схема адаптивной системы распознавания образов.

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

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

1.2. Краткое описание концепций

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

1.2.1. Принцип перечисления членов класса

Задание класса перечислением образов, входящих в его состав, предполагает реализацию процесса автоматического распознавания образов посредством сравнения с эталоном. Множество образов, принадлежащих одному классу, запоминается системой распознавания. При предъявлении системе незнакомых (новых) образов она последовательно сравнивает их с хранящимися в ее памяти. Система распознавания образов относит новый образ к тому классу, к которому принадлежал находящийся в памяти системы образ, совпавший с новым. Так, например, если в память системы распознавания введены литеры различных наборных шрифтов, то подход, основанный на перечислении членов класса, позволяет распознавать соответствующие буквы, но только в тех случаях, когда их изображения не искажены шумом, связанным с размазыванием или плохим нанесением краски, пористостью бумаги и т. п. Несомненно, это несложный метод, однако он позволяет строить недорогие системы распознавания, которые в отдельных прикладных областях вполне справляются со своими задачами. Метод перечисления членов класса работает удовлетворительно, если выборка образов близка к идеальной.

1.2.2. Принцип общности свойств

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

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

1.2.3. Принцип кластеризации

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

1.3. Краткое описание методов

Для реализации рассмотренных выше основных принципов построения автоматических систем распознавания образов существуют три основных типа методологии: эвристическая, математическая и лингвистическая (синтаксическая). Нередко системы распознавания создаются на основе комбинации этих методов.

1.3.1. Эвристические методы

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

1.3.2. Математические методы

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

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

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

1.3.3. Лингвистические (синтаксические) методы

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

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

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

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

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

2. Обучаемые классификаторы образов

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

Решение задачи о разделении на два класса эквивалентно решению системы линейных неравенств. Так, если задано два множества образов и , то решение ищется в виде вектора весов , обладающих следующими свойствами:

если и если .

Если образы класса умножить на –1, то условие становится общим для всех образов. Если обозначить через N общее количество пополненных выборочных образов обоих классов, то данную задачу можно свести к нахождению (определению) вектора весов , удовлетворяющих системе неравенств:

(2.1)

где , и .

Если вектор весов , удовлетворяющий условию (2.1) существует, то неравенства называются совместными, в противном, несовместными, что соответствует случаю разделимых и неразделимых классов.

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

  1. алгоритмы конструируются независимо от каких-либо предложений о статистических свойствах классов образов;

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

2.1. Алгоритм перцептрона и его модификации

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

Эта схема легко распространяется на случай разделения на несколько классов путем увеличения числа входящих в нее первичных элементов, т.е. если имеем , то:

- решающие функции (2.2)

и , если .

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

Модель перцептрона вида (2.2) сводится к следующему алгоритму: Пусть заданы два обучающих множества из классов и ; а - начальный вектор весов, выбранный произвольно.

Тогда k-й шаг обучения будет иметь вид:

1. Если и , то вектор весов заменяется:

(2.3)

где: С – корректирующее приращение.

2. Если и , то заменяется вектором:

(2.4)

3. В противном случае не изменяется, т.е.:

(2.5)

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

Очевидно, что алгоритм перцептрона является процедурой типа «подкрепление-наказание», и поощрением является, по сути, отсутствие наказания. Таким образом:

  1. если образ классифицирован правильно, то система подкрепляется тем, что в вектор не вносится никаких изменений.

  2. если образ классифицирован неправильно и , когда должно быть > 0, то система «наказывается» увеличением значения весов на величину, пропорциональную .

  3. если , когда оно должно быть < 0, то система наказывается противоположным образом.

Сходимость алгоритма наступает при правильной классификации всех образов с помощью некоторого вектора весов.

Изменяя в (2.3), (2.4) способ выбора корректирующего приращения С можно получить несколько модификаций алгоритма перцептрона среди которых выделяют:

  1. алгоритм фиксированного приращения

  2. алгоритм коррекции абсолютной величины

  3. алгоритм дробной коррекции

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

(2.6)

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

  1. коэффициент С=const >0, т.е. алгоритм фиксированного приращения

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

(2.7)

Одним из способов, обеспечивающих выполнение (2.7) является выбор С согласно следующему соотношению:

при

где:

int(·) – наименьшее целое;

N – число образов в выборке.

Это дает в итоге алгоритм коррекции абсолютной величины.

коэффициент С выбирается согласно соотношению, что делает алгоритм дробной коррекции:

, где (2.8)

что обеспечивает правильную классификацию образов после каждой коррекции коэффициентов весов.

2.2. Градиентные алгоритмы классификации образов

Применимость градиентных алгоритмов к классификации образов основана на том, функция штрафа (целевая функция) выбирается таким образом, чтобы она достигала минимальное значение при выполнении условия , где - i-я строка матрицы Х размерности N·(n+1) системы неравенства вида:

(2.9)

т.е. - матрица образов,

- вектор коэффициентов весов.

Тогда нахождение минимума функции штрафа для эквивалентно решению указанной системы неравенств.

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

(2.10)

Если неравенства (2.9) совместны и функция задана надлежащим образом, то алгоритм (2.10) дает решение данной задачи.

  1. Пусть функция штрафа задана в виде:

(2.11)

Тогда

(2.12)

где:

(2.13)

Подставив (2.55) в (2.53) получим:

(2.14)

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

Если теперь воспользоваться соотношением (2.13), то получим известный алгоритм перцептрона:

где: С > 0, а - произвольное значение.

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

2.3. Алгоритм наименьшей среднеквадратичной ошибки

Алгоритм перцептрона и его модификации сходятся в тех случаях, когда заданные классы можно разделить поверхностью заданного типа. Если разделимость классов образов отсутствует, то рассмотренные алгоритмы не сходятся. Поскольку при наличии разделимости невозможно заранее рассчитать число шагов необходимое для сходимости алгоритма, то значит нельзя оценить наличие или отсутствие линейной разделимости заданных классов по наличию или отсутствию длинной обучающей последовательности. Поэтому актуальным является построение алгоритмов классификации, которые дают информацию о разделимости классов. Одним из таких алгоритмов и есть данный алгоритм НСКО.

По-прежнему, рассматривая постановку задачи распознавания образов в виде системы линейных неравенств (2.9), переформулируем ее следующим образом: вместо выполнения соотношения (2.9) потребуем выполнение равенства вида:

(2.15)

где , и .

Вводим целевую функцию вида:

(2.16)

где - модуль вектора .

Очевидно, что функция достигает минимума при выполнении условий (2.15), и поскольку минимизация проводится по обеим переменным и , то градиентный алгоритм первого порядка дает:

(2.17)

Т.к. на вектор не накладывается никаких ограничений, то приравняв первое из уравнений (2.60) нулю (т.е. используя необходимое условие экстремума) получим: систему нормальных уравнений:

(2.18)

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

(2.19)

где

(2.20)

где: i – индекс компонент вектора;

с – коэффициент пропорциональности > 0.

Уравнение (2.20) в векторной форме запишется:

(2.21)

где: - вектор, составленный их абсолютных значений каждой компоненты вектора .

Из (2.18) и (2.19) следует, что:

(2.22)

Положив, что

(2.23)

приходим к заключительной форме алгоритма НСКО:

(2.24)

При этом:

  1. Если неравенства имеют решение, то данный алгоритм сходится при , что имеет место, если , а вектор является решением задачи.

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

Высокая скорость сходимости алгоритма НСКО следует из того, что:

  1. Изменение обеих векторов и производится на каждом шаге.

  2. Процедура, определяемая соотношением (2.67) является адаптивной, т.к. на каждом шаге итерации учитывается информация о всех образах обоих классов.

К недостаткам следует отнести сложность вычислительной схемы, т.к. необходимо обращать матрицу (ХТХ). Данная матрица имеет обратную матрицу, если ранг матрицы Х равен n+1, что имеет место при компактном размещении классов, т.е. при наличии кластеров.

3. Описание разработанного программного обеспечения

3.1. Алгоритм работы программы

Алгоритм работы программы может быть представлен в виде следующей блок-схемы:

3.2. Описание программы и инструкции для пользователя

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

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

Приступив к работе с программой, пользователь в первую очередь задаёт общее количество образов (счётчик на рис. 3.1).

Далее вводятся координаты образов и определяется их принадлежность к классам (таблицы на рис. 3.1)

Рис. 3.1

После нажатия на кнопку «Расчет» в соответствующее поле выводятся коэффициенты решающей функции (рис. 3.2.)

Рис. 3.2

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

После получения решающей функции можно проверить принадлежность произвольного образа классу. Для этого используются соответствующие поля ввода (рис. 3.3).

Рис. 3.3

3.3. Тестовый пример

Рассмотрим работу представленной программы на следующем небольшом примере.

Дано:

образы обучающей выборки:

класс 1 – (0, 0), (0, 1)

класс 2 – (1, 0), (1, 1)

Необходимо построить решающую функцию.

Приняв :

Найдём Xw(1):

w(1) и есть решение. Вектор ошибки равен нулю:

Результаты работы программы.

Полученная функция: -2∙x1 + 0∙x2 + 1 = 0

График полученной функции представлен на рис 3.4.

Рис. 3.4.

Пример 2. Дано:

образы обучающей выборки:

класс 1 – (0, 0)

класс 2 – (1, 0), (2, 2)

Необходимо построить решающую функцию.

Результаты работы программы.

Полученная функция: -2∙x1 + 1∙x2 + 1 = 0

График полученной функции представлен на рис 3.5.

Рис. 3.5.

Выводы

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

Метод НСКО имеет свои преимущества и недостатки.

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

Кроме того, метод НСКО обладает более высокой сходимостью по сравнению с аналогичными методами (например, алгоритмом перцептрона).

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

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

  1. Дж. Гу, Дж. Гонсалес Р. «Принципы распознавания образов».

  1. Шлезингер М.Ч. «Математические методы распознавания образов»,
    К., Наукова думка, 1989.



Похожие документы:

  1. Пособие для учителей общеобразовательных учреждений удк 372. 8: 004

    Документ
    ... работе с программой, ... пользователя владения навыком выбора имен для ... Примером рассматриваемой технологии может служить проект «Я умею», описанный выше. Учащиеся работают ... 2930 ... 32 – 33 Буквы Ц, Щ 34 – 35 ... алгоритмы. ... для разработки должностных инструкций ...
  2. Контрольно-оценочные средства по профессиональному модулю пм. 01 Разработка программных модулей программного обеспечения компьютерных систем для специальности

    Документ
    ... указания 29 Ход работы: 30 Цель: Разработка кода модуля, содержащего обработку сообщения WM_COMMAND для вывода ... для пользователя, демонстрационные версии, примеры документов, создаваемых при помощи данного программного продукта, обучающие программы ...
  3. Образовательная программа основного общего образования Муниципального бюджетного общеобразовательного учреждения

    Образовательная программа
    ... языке Паскаль алгоритмы, заданные словесным описанием. Уметь структурно писать программы, разделять их ... для формирования портфолио обучающегося. С инструкцией ознакомлен/а/: ДОЛЖНОСТНАЯ ИНСТРУКЦИЯ ЗАМЕСТИТЕЛЯ ДИРЕКТОРА ПО УЧЕБНО-ВОСПИТАТЕЛЬНОЙ РАБОТЕ ...
  4. Программа учебного предмета «технология» (2)

    Программа
    ... процессов; • приведение примеров, подбор аргументов, формулирование выводов по обоснованию технико- ... 28 урок 15 29-30 урок 16 31-32 урок Тема ... работе с программой в режиме Справки, а также систему простых визуальных подсказок. Банки тестовых заданий для ...
  5. Основная образовательная программа начального общего образования моу

    Основная образовательная программа
    ... по его описанию, находить в тексте примеры, подтверждающие приведённое утверждение); - работать с несколькими ... выполнения действий,составлять инструкции (простые алгоритмы) в несколько действий, строить программы для компьютерного исполнителя с ...

Другие похожие документы..