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

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Тульский государственный университет»

Кафедра «Математическое моделирование»

Курсовая работа По дисциплине «Информатика»

Тема: Алгоритм и программа Проверила Зотова С.В.

Тула 2015

• Содержание
• Введение
• 1. Основные понятия
• 1.1 Основные задачи, возникающие при разработке систем распознавания образов
• 1.2 Обучаемые классификаторы образов
• 1.2.1 Алгоритм перцептрона и его модификации
• 1.2.2 Градиентные алгоритмы классификации образов
• 1.2.3 Алгоритм наименьшей среднеквадратичной ошибки
• 2. Описание разработанного программного обеспечения
• 2.1 Алгоритм работы программы
• 2.2 Описание программы и инструкции для пользователя
• 2.3 Тестовый пример
• Выводы
• Список литературы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1.1)

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

Второй пример проиллюстрирован на рис. 1.1,6. В этом случае образами служат непрерывные функции переменной t. Если измерение значений функций производится в дискретных точках t₁, t₂ …, t_n, вектор образа можно сформировать, приняв x₁=f (t₁), x₂=f (t₂),… x_n= f (t_n). Векторы образов будут обозначаться строчными буквами, выделенными жирным шрифтом, например х, у и z. Условимся, Рис. 1.1. Две простые схемы порождения вектора образа.

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

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

Соответствующий простой пример приведен на рис. 1.2 для случая двух классов, обозначенных щ₁ и щ₂. В этом примере предполагается, что классы щ₁ и щ₂ представляют соответственно группы футболистов-профессионалов и жокеев. Каждый «образ» характеризуется результатами двух измерений: ростом и весом. Векторы образов имеют, следовательно, вид x = (x₁, х₂)^т где параметр x₁ — рост, а параметр х₂ — вес. Каждый вектор образа можно считать точкой двумерного пространства. Как следует из рис. 1.2, эти два класса образуют непересекающиеся множества, что объясняется характером измерявшихся параметров.

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

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

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

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

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

Пусть эти границы определены, например, решающими функциями d₁(x), d₂(х), … …, d_м(х). Эти функции, называемые также дискриминантными функциями, представляют собой скалярные и однозначные функции образа X. Если d_i(х) > d_j(х) для всех i, j= 1, 2, …, М, j? i, то образ X принадлежит классу щ_i. Другими словами, если i-я решающая функция d_i(x) имеет наибольшее значение, то х є щ_i. Содержательной иллюстрацией подобной схемы автоматической классификации, основанной на реализации процесса принятия решения, служит приведенная на рис. 1.3 блок-схема (на схеме ГРФ означает «генератор решающих функций»).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

если и если .

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

(2.1)

где, и .

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

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

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

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

1.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. алгоритм дробной коррекции Если воспользоваться эквивалентной формой представления алгоритма перцептрона, для чего следует умножить образы одного из классов на -1 (например, класс) в виде

(2.6)

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

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

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

(2.7)

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

при

где: int (?) — наименьшее целое; N — число образов в выборке.

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

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

где (2.8)

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

1.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, а — произвольное значение.

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

1.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, что имеет место при компактном размещении классов, т. е. при наличии кластеров.

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

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

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

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

распознавание образ персептрон среднеквадратический

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

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

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

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

Рис. 3.1

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

Рис. 3.2

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

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

Рис. 3.3

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

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

Дано:

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

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

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

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

Приняв :

Найдём Xw (1):

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

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

Полученная функция: -2•x₁ + 0•x₂ + 1 = 0

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

Рис. 3.4.

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

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

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

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

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

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

Полученная функция: -2•x₁ + 1•x₂ + 1 = 0

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

Рис. 3.5.

Выводы

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

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

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

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

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

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

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