_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).doc), страница 3

Глава1. Математические методы распознавания (классификации с учителем) и прогноза.

1.1. Задачи распознавания или классификации с учителем.

Исходной информацией являются описания объектов (ситуаций, предметов, явлений или процессов) S в виде векторов значений признаков для рассматриваемых объектов и значений некоторого «основного свойства» y(S) объекта S. Свойство y(S) принимает конечное число значений. Значения признаков , характеризующих различные стороны-свойства объектов S , для некоторых объектов считаются известными. Предполагается, что существует функциональная связь между признаками и основным свойством (неизвестная пользователю). Задача распознавания (прогноза, идентификации, «классификации с учителем») состоит в определении значения свойства y(S) некоторого объекта S по информации (обучающей или эталонной выборке). Таким образом, задача распознавания может быть представлена как специальная задача экстраполяции функции, зависящей от конечного числа разнотипных переменных – признаков, и заданной в виде таблицы значений в конечном числе точек. Задачу построения алгоритма вычисления значений данной неизвестной функции в новых точках по известной совокупности ее значений в конечном числе точек называют задачей обучения распознаванию (построение распознающего алгоритма), а вычисление значения функции для произвольного нового набора признаков – задачей распознавания. Обычно вместо термина «основное свойство объекта» используют термин «класс объекта». Объекты, имеющие равные значения основного свойства считаются принадлежащими одному множеству (образу, классу объектов), и задача распознавания по прецедентам формулируется как задача отнесения объекта к одному из классов.

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

Формирование системы признаков и определение множества допустимых значений каждой части (признака) практически не поддается формализации. Это - работа эксперта-специалиста или группы экспертов. На этом этапе возможно множество альтернативных решений: можно выделить, например, небольшое число признаков со сложно устроенными множествами значений - изображения, сигналы и т.п., а можно "аппроксимировать" сложные признаки наборами простых. Так, вместо изображения или сигнала часто вводится совокупность его относительно простых характеристик, значения которых и запоминаются при описании ситуации. При этом число признаков увеличивается, но "сложность" отдельной части уменьшается. Так, вместо функции с конечным числом точек разрыва можно запоминать первые коэффициенты разложения в ряд Фурье, вместо полного оттиска пальца - число типовых элементарных локальных конфигураций. Именно проблемы замены сложных признаков - сигналов, изображений - на множество простых числовых признаков вызвали к жизни такие развитые отрасли прикладной математики как обработка сигналов, обработка и распознавание изображений. Если первая отрасль считается традиционной и полностью оформившейся, то вторая быстро развивается именно в последние годы.

Мы будем далее считать, что признаки принимают числовые значения, выражающие степень выраженности какого-то свойства. Случаи простого наличия или отсутствия какого-то свойства (бинарные признаки) будут кодироваться значениями 1 и 0. В случаях, когда признак принимает конечное число значений (к-значные признаки), значения признаков будут кодироваться 0, 1, 2, …, к-1. Бинарные и к-значные признаки будут рассматриваться как частный случай числовых признаков. Данные признаковые описания в виде числовых векторов являются в настоящее время практически общепринятыми и именно они используются в системе «РАСПОЗНАВАНИЕ». Заметим, что этап описания объектов в виде набора числовых признаков обычно успешно решается специалистами соответствующих предметных областей и фактически давно используется при начальной систематизации данных. Обычным в практике является также отсутствие по какой-либо причине информации о значениях части признаков у некоторых объектов. В данных случаях «пробелы» или «пропуски» значений признаков кодируются специальным символом. Алгоритмы распознавания решают задачи распознавания объектов по признакам, значения которых для данного объекта известны. При этом учитывается наличие пропусков и их количество.

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

,

,

…………………………

,

где .

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

(1.1)

Здесь означает отнесение алгоритмом объекта в класс , означает решение алгоритма «объект не принадлежит классу », означает отказ от классификации объекта данным алгоритмом относительно класса .

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

1.2. Алгоритмы распознавания по прецедентам (классификация с учителем).

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

1.2.1. Статистические алгоритмы распознавания.

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

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

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

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

, (1.2)