Logo GenDocs.ru


Поиск по сайту:  


Лекции - Методы распознавания образов - файл Metody_raspoznovaniya.doc


Лекции - Методы распознавания образов
скачать (264.6 kb.)

Доступные файлы (1):

Metody_raspoznovaniya.doc2920kb.06.12.2009 21:23скачать

содержание

Metody_raspoznovaniya.doc

  1   2   3   4   5   6   7   8   9
Реклама MarketGid:

МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ


(конспект лекций)


Автор: Волошин Г.Я.

Редактор: Ильин А.А.


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

Содержание:


ВВЕДЕНИЕ 4

Постановка задачи распознавания.
Основные определения и понятия 6

^ РАЗДЕЛ 1. ДЕТЕРМИНИСТСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАСПОЗНАВАНИЯ 9

Построение решающих правил 9

Метод построения эталонов 9

Метод дробящихся эталонов 10

Линейные решающие правила 12

Метод ближайших соседей 14

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

Структурные (лингвистические) методы 18

Кластерный анализ 22

Критерии информативности признаков 28

Отбор информативных признаков 29

^ РАЗДЕЛ 2. СТАТИСТИЧЕСКИЕ МЕТОДЫ РАСПОЗНАВАНИЯ 34

Метод ближайших соседей 41

Правило ближайшего соседа 44

Параметрическое оценивание распределений 44

Метод максимума правдоподобия 46

Случай статистически независимых признаков 48

Распознавание при неизвестных априорных вероятностях
образов 49

Минимаксный критерий 50

Критерий Неймана-Пирсона 52

Последовательные процедуры распознавания 53

Аппроксимационный метод оценки распределений
по выборке 56

Таксономия 63

Оценка информативности признаков 65

Иерархические системы распознавания 68

Заключение 73

^ РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА 74

ВВЕДЕНИЕ


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

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

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

Показательным в этом отношении является выдержка из монографии А.М. Берлянта «Геоиконика»: «...использование карт, дешифрирование снимков, анализ экранных видеоизображений – это всегда распознавание и анализ графических образов, их измерение, преобразование, сопоставление и т.п. Отсюда следует, что распознавание графических образов, то есть создание системы решающих правил для их идентификации, классификации и интерпретации – это одна из главных задач геоиконики".

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


Статистический подход опирается на фундаментальные результаты математической статистики (теория оценок, последовательный анализ, стохастическая аппроксимация, теория информации).

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

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

Предлагаемый курс лекций рассчитан на 35-40 академических часов.

^

Постановка задачи распознавания.
Основные определения и понятия


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

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

Введём следующие обозначения:

 – множество распознаваемых образов (классов), называемое иногда алфавитом;

 – признаковое (выборочное) пространство;

 – размерность признакового пространства (количество признаков, характеризующих распознаваемые объекты);

 – множество решающих правил, по которым осуществляется отнесение распознаваемого объекта (реализации) к тому или иному образу;

 – риск потерь при распознавании.

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

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

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

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

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

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







Рис. 1. Множество прямоугольников и их представление
в признаковом пространстве

Итак, можно представить как некоторое пространство раз­мерности с определённой в этом пространстве метрикой. Любой объект (реализация) представляется в виде точки (вектора) в этом пространстве. Проекция этой точки на ю ось координат соответствует значению го признака. Например, множество прямоугольников со сторонами, параллельными осям координат, можно представить множеством точек в двухмерном признаковом пространстве (см. рис. 1) с евклидовой метрикой, где  – длина го­ризонтальной стороны,  – длина вертикальной стороны. Если нам нужно распознавать два образа – вертикально и горизонтально вытянутые прямоугольники, то решающее правило в виде биссектрисы угла в начале координат эту задачу выполняет. Все точки (объекты), лежащие выше – левее , относятся к образу "вертикально вытянутые прямоугольники", ниже – правее – "горизонтально вытянутые прямоугольники".

Как уже отмечалось, методы решения задач распознавания можно условно разделить на детерминистские и статистические. Начнём с детерминистских методов.
  1   2   3   4   5   6   7   8   9

Реклама:





Скачать файл (264.6 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru