Методы распознавания образов

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

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

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

Аннотация

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

Содержание

• Введение
• Постановка задачи распознавания. Основные определения и понятия
• Раздел 1. Детерминистские методы решения задач распознавания
• 1.1 Построение решающих правил
• 1.2 Метод построения эталонов
• 1.3 Метод дробящихся эталонов
• 1.4 Линейные решающие правила
• 1.5 Метод ближайших соседей
• 1.6 Метод потенциальных функций
• 1.7 Структурные (лингвистические) методы
• 1.8 Кластерный анализ
• 1.9 Критерии информативности признаков
• 1.10 Отбор информативных признаков
• Раздел 2. Статистические методы распознавания
• 2.1 Метод ближайших соседей
• 2.2 Правило ближайшего соседа
• 2.3 Параметрическое оценивание распределений
• 2.4 Метод максимума правдоподобия
• 2.5 Случай статистически независимых признаков
• 2.6 Распознавание при неизвестных априорных вероятностях образов
• 2.7 Минимаксный критерий
• 2.8 Критерий Неймана-Пирсона
• 2.9 Последовательные процедуры распознавания
• 2.10 Аппроксимационный метод оценки распределений по выборке
• 2.11 Таксономия
• 2.12 Оценка информативности признаков
• 2.13 Иерархические системы распознавания
• Заключение
• Рекомендуемая литература

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на http://www.allbest.ru/

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

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

Как уже отмечалось, методы решения задач распознавания можно условно разделить на детерминистские и статистические. Начнём с детерминистских методов.

детерминистский кластерный образ распределение

Раздел 1. Детерминистские методы решения задач распознавания

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

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

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

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

Итак, для построения решающих правил системе предъявляются объекты, входящие в обучающую выборку.

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

детерминистский кластерный образ

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

,

где =,

- количество объектов данного образа в обучающей выборке,

- номер признака.

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

Рис. 2. Решающее правило "Минимум расстояния до эталона класса":

- эталон первого класса,

- эталон второго класса.

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

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

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

Размещено на http://www.allbest.ru/

Рис. 3. Решающее правило типа “Метод дробящихся эталонов”

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

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

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

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

=.

Размещено на http://www.allbest.ru/

Рис. 4. Линейное решающее правило для распознавания двух образов

Одна граница при этом разделяет области двух образов. Если >2, то требуется несколько линейных функций и граница является, вообще говоря, кусочно линейной. Для наглядности будем считать =2. Если на множестве объектов выполняется условие:

,

если - реализация первого образа,

если - реализация второго образа,

то образы и называют линейно разделимыми.

Существуют различные методы построения линейных решающих правил. Рассмотрим один из них, реализованный в 50-х годах Розенблатом, в устройствах распознавания изображений, названных персептронами (рис. 5).

Пусть

где - некоторый объект одного из образов, .

Размещено на http://www.allbest.ru/

Рис. 5. Упрощённая схема однослойного персептрона

Выбор осуществляется пошаговым образом. Текущее значение заменяется новым после предъявления персептрону очередного объекта обучающей выборки. Эта корректировка производится по следующему правилу:

1. , если и или если и .

2. , если и , .

3. , если и .

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

.

Соответственно в случае (3) .

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

, если ,

, если .

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

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

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

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

Размещено на http://www.allbest.ru/

Рис. 6. Пример линейно неразделимых множеств

Размещено на http://www.allbest.ru/

Рис. 7. Решающее правило "Минимум расстояния до ближайшего соседа"

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

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

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

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

Размещено на http://www.allbest.ru/

Рис. 8. Иллюстрация синтеза потенциальной функции в процессе обучения:

- потенциальная функция, порождаемая одиночным объектом;

- суммарная потенциальная функция, порождённая обучающей последовательностью

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

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

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

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

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

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

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

Рис. 9. Изображение (а) и его иерархическое структурное описание (б)

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

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

Рис. 10. Прямоугольник (а) и его непроизводные элементы (б)

На рис. 11 приведён более сложный пример структурного описания цифры 9.

Рис. 11. Изображение цифры 9 и его структурное описание

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

В качестве примера приведём фрагменты языка описания изображений PDL (Picture Description Language). Определены непроизводные элементы,

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

головная точка примыкает к хвостовой точке ;

хвостовая точка примыкает к хвостовой точке ;

головная точка примыкает к головной точке ;

головная точка примыкает к головной точке и хвостовая точка примыкает к хвостовой точке .

На рис. 12 приведено выражение на языке PDL, описывающее букву .

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

Более детальную информацию о структурном подходе можно почерпнуть в рекомендованной для самостоятельных занятий литературе [9].

Рис. 12. Структурное описание буквы А на языке PDL

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

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

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

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

Мы ограничимся рассмотрением геометрической интерпретации. Остановимся на алгоритме FOREL (рис. 13).

a б

Рис. 13. Иллюстрация алгоритма FOREL: а - процесс перемещения формального элемента по множеству объектов (точек); б - иллюстрация зависимости результатов таксономии по алгоритму FOREL от начальной точки перемещения формального элемента

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

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

При всей своей наглядности и интерпретируемости результатов алгоритм FOREL обладает существенным недостатком: результаты таксономии в большинстве случаев зависят от начального выбора центра гиперсферы радиуса. Существуют различные приёмы, уменьшающие эту зависимость, но радикального решения этой задачи нет. С подробностями можно ознакомиться в рекомендованной литературе [6].

Рис. 14. Иерархическая (двухуровневая) таксономия

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

Факторы, выявленные при "человеческой" таксономии, можно сформулировать следующим образом:

- внутри таксонов объекты должны быть как можно ближе друг к другу (обобщённый показатель );

- таксоны должны как можно дальше отстоять друг от друга (обобщённый показатель );

- в таксонах количество объектов должно быть по возможности одинаковым, то есть их различие в разных таксонах нужно минимизировать (обобщённый показатель );

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

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

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

Рис. 15. Иллюстрация алгоритма KRAB

Мера близости объектов в одном таксоне - это средняя длина ребра

,

где - число объектов в таксоне ,

- длина -го ребра.

Усреднённая по всем таксонам мера близости точек .

Средняя длина рёбер, соединяющих таксоны, .

Мера локальной неоднородности определяется следующим образом.

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

,

где - общее число точек в обучающей выборке.

Определим величину следующим образом:

.

Можно показать, что при фиксированном максимум достигается при .

Теперь можно сформировать интегрированный критерий качества таксономии

.

Чем больше , тем это качество выше. Таким образом, осуществляя таксономию, нужно стремиться к максимизации . Если требуется сформировать таксонов, необходимо оборвать в КНП-графе рёбер, таких, чтобы критерий оказался максимально возможным. Это переборная задача. При большом количестве таксонов и объектов обучающей выборки число вариантов может оказаться неприемлемо большим. Желательно уменьшить вычислительные затраты. Предлагается в качестве примера следующий приём. КНП-граф строится не на множестве точек обучающей выборки, а на множестве центров гиперсфер (таксонов), найденных при помощи алгоритма FOREL. Это может резко сократить количество вершин (а следовательно и рёбер) графа и сделать реализуемым полный перебор вариантов обрыва рёбер. Конечно, при этом не гарантирован глобальный максимум , особенно если вспомнить недостатки, присущие алгоритму FOREL. Данный метод сочетания алгоритмов FOREL и KRAB назван его авторами KRAB 2.

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

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

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

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

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

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

На рис. 16 представлено линейное преобразование координат

.

После преобразования признак не несёт различительной информации и его использование для распознавания не имеет смысла.

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

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

Рис. 16. Линейное преобразование координат с последующим отбрасыванием одного из признаков

Особо выделим следующий тип линейного преобразования:

,

где - диагональная матрица, причём её элементы равны либо 0, либо 1.

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

Оптимальное решение задачи даёт полный перебор. Если исходная система содержит признаков, а нам нужно выбрать наилучшую подсистему, содержащую признаков, то придётся рассмотреть (число сочетаний из элементов по ) возможных в данном случае подсистем. Причём рассмотрение каждой подсистемы состоит в оценке значения критерия информативности, что само по себе является трудоёмкой задачей, особенно если в качестве критерия использовать относительное число ошибок распознавания. Для иллюстрации укажем, что для отбора из 20 исходных признаков пяти наиболее информативных приходится иметь дело примерно с 15,510³ вариантами. Если же количество исходных признаков - сотни, то полный перебор становится неприемлемым. Переходят к разумным процедурам направленного отбора, которые в общем случае не гарантируют оптимального решения, но хотя бы обеспечивают не худший выбор.

Рис. 17. Переход к полярной системе координат с последующим отбрасыванием признака

Рассмотрим некоторые из применяемых процедур.

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

Предполагается, что признаки статистически зависимы. Сначала отбирается самый индивидуально информативный признак (просматривается вариантов). Затем к первому отобранному признаку присоединяется ещё один из оставшихся, составляющий с первым самую информативную пару (просматривается вариантов). После этого к отобранной паре присоединяется ещё один из оставшихся признаков, составляющий с ранее отобранной парой наиболее информативную тройку (просматривается вариантов) и т.д. до получения совокупности из признаков. Здесь число просматриваемых вариантов составляет величину . Для иллюстрации отметим, что для отбора 5 признаков из 20 при данном подходе требуется просмотреть 90 вариантов, что примерно в 170 раз меньше, чем при полном переборе.

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

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

Случайный поиск с адаптацией. Это последовательная направленная процедура, основанная на случайном поиске с учётом результатов предыдущих отборов. В начале процедуры шансы всех исходных признаков на вхождение в подсистему, состоящую из признаков, принимаются равными. Для случайного отбора используется датчик равномерно распределённых в интервале случайных (псевдослучайных) чисел. Этот интервал разбивается на равных отрезков. Первый отрезок ставится в соответствие признаку , второй - и т.д. Длина каждого отрезка равна вероятности включения -го признака в информативную подсистему. Как уже отмечалось, сначала эти вероятности для всех признаков одинаковы. Датчиком случайных чисел выбирается различных отрезков. Для тех признаков из , которые соответствуют этим отрезкам, определяется значение критерия информативности . После получения первой группы из случайно выбранных подсистем определяется и . Адаптация состоит в изменении вектора вероятностей выбора признаков на последующих этапах поиска в зависимости от результатов предыдущих этапов: длина отрезка в интервале , соответствующая признаку, попавшему в самую плохую подсистему, уменьшается (признак "наказывается"), а попавшему в самую хорошую подсистему - увеличивается (признак "поощряется"). Длины отрезков изменяются на величину . После перебора ряда групп вероятность выбора признаков, часто встречающихся в удачных сочетаниях, становится существенно больше других, и датчик случайных чисел начинает выбирать одно и то же сочетание из признаков. Чем больше , тем быстрее сходимость процедуры, но тем ниже вероятность "выхода" на наилучшую подсистему. И наоборот, чем меньше , тем медленнее сходимость, но выше вероятность выбора наилучшей подсистемы. Конкретный выбор значения должен быть таким, чтобы процедура сходилась при общем числе выборов , а вероятность нахождения наилучшей подсистемы или близкой к ней по информативности была бы близка к единице.

Раздел 2. Статистические методы распознавания

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

Здесь - априорная вероятность предъявления к распознаванию объекта -го образа:

.

для каждого

,

при признаках с непрерывной шкалой измерений

,

при признаках с дискретной шкалой измерений

.

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

Распределения, описывающие разные классы, как правило, "пересекаются", то есть имеются такие значения признаков , при которых

.

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

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

Риск потерь определяется двумя компонентами: вероятностью ошибок распознавания и величиной "штрафа" за эти ошибки (потерями). Матрица ошибок распознавания:

,

где - вероятность правильного распознавания;

- вероятность ошибочного отнесения объекта -го образа к -му ().

Матрица потерь

,

где - "премия" за правильное распознавание;

- "штраф" за ошибочное отнесение объекта -го образа к -му ().

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

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

Средний риск при попадании реализаций -го образа в области других образов равен

, .

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

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

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

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

,

где - вероятность ошибки второго рода

.

Средние ошибки

.

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

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

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

Рис. 18. Иллюстрация рандомизированного решающего правила

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

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

Байесовское решающее правило реализуется в компьютерах в основном двумя способами.

1. Прямое вычисление апостериорных вероятностей

,

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

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

2. "Топографическое" определение области , в которую попал вектор значений признаков, описывающих распознаваемый объект.

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

Рис. 19. Байесовское решающее правило для нормально распределённых признаков с равными ковариационными матрицами

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

Если у классов и ковариационные матрицы и не только одинаковы, но и диагональны, то байесовским решением является отнесение объекта к тому классу, евклидово расстояние до эталона которого минимально (рис. 20).

Рис. 20. Байесовское решающее правило для нормально распределённых признаков с равными диагональными ковариационными матрицами (элементы диагоналей одинаковы)

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

Теперь перейдём к методам оценки распределений значений признаков классов. Знание является наиболее универсальной информацией для решения задач распознавания статистическими методами. Эту информацию можно получить двояким образом:

заранее определить (оценить) для всех и ;

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

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

Начнём с локального варианта (определения в окрестности распознаваемого объекта).

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

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