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

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

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

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

Именно проблемы замены сложных признаков - сигналов, изображений на множество простых числовых признаков вызвали к жизни такие развитые отраслиприкладной математики как обработка сигналов, обработка и распознавание изображений.Если первая отрасль считается традиционной и полностью оформившейся, то втораябыстро развивается именно в последние годы.Мы будем далее считать, что признаки принимают числовые значения,выражающие степень выраженности какого-то свойства. Случаи простого наличия илиотсутствия какого-то свойства (бинарные признаки) будут кодироваться значениями 1 и 0.В случаях, когда признак принимает конечное число значений (к-значные признаки),значения признаков будут кодироваться 0, 1, 2, …, к-1.

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

Обычным в практике является также отсутствиепо какой-либо причине информации о значениях части признаков у некоторых объектов.В данных случаях «пробелы» или «пропуски» значений признаков кодируютсяспециальным символом. Алгоритмы распознавания решают задачи распознаванияобъектов по признакам, значения которых для данного объекта известны. При этомучитывается наличие пропусков и их количество.Далее будем считать, что информация S1 , S 2 ,..., S m , y ( S1 ), y ( S 2 ),..., y ( S m ) задана ввиде таблицы обучения Tnml  aij mn , где строки соответствуют признаковым описаниям16объектов длины n, строкам S1 , S 2 ,..., S m1соответствуют значения основного признакаy ( Si )  1 (объекты принадлежат классу K1 ), строкам S m11 , S m12 ,..., S m2соответствуютзначения основного признака y ( Si )  2 (объекты принадлежат классу K 2 ), и т.д. СтрокамS ml 11 , S ml 12 ,..., S mсоответствуют значения основного признака y ( Si )  l(объектыпринадлежат классу K l ), т.е.

S mi 11 , S mi 12 ,..., S mi  K i , i  1,2,..., l , m0  1, ml  m .a11 a12 ... a1na21 a22 ... a2 n....am1 1 am1 2 ... am1n  K1 ,am11,1am12,1.am21  K2 ,am11, 2 ... am11,nam12, 2 ... am12,n...am2 2 ... am2n…………………………aml 11,1aml 12,1.am1aml 11, 2 ... aml 11,naml 12, 2 ... aml 12,n...am 2...amn  Kl ,где aij  x j ( Si ) .Таким образом, для решения задачи распознавания по прецедентам требуется наоснове таблицы обучения Tnml создать алгоритм, который будет правильно определятькласс, которому принадлежит предъявленный к распознаванию объект. Формальноалгоритм распознавания будем записывать в следующем виде:A( S )  (1A ( S ), 2A ( S ),..., lA ( S )), i ( S )  {0,1, }, i  1,2,..., l.(1.1)Здесь  iA ( S )  1 означает отнесение алгоритмом объекта S в класс K i ,  iA ( S )  0означает решение алгоритма «объект S не принадлежит классу K i »,  iA (S )   означаетотказ от классификации объекта S данным алгоритмом относительно класса K i .В заключение параграфа отметим, что здесь не будут рассматриваться случаи сиспользованием других видов обучающей информации (в качестве основной илидополнительной к обучающей выборке).

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

В настоящем параграфе кратко рассматриваютсятакие основные подходы и приводятся ссылки на конкретные алгоритмы. Следуетотметить, что, как правило, по каждому подходу имеются специальные монографии,изучение которых требует специальной подготовки.1.2.1. Статистические алгоритмы распознавания.Предполагается, что объекты обучающей выборки и распознаваемые объектыпринадлежат к одной и той же генеральной совокупности. Считается, что объективносуществует совместное вероятностное распределение элементов данной генеральнойсовокупности по классам и в признаковом пространстве. В случаях, когда такоераспределение известно, существует простое оптимальное решение задачи распознаванияпринадлежности объектов классамK1 ,..., K l . Предположим, что нам необходимоклассифицировать объект S , признаковое описание которого представлено векторомx(S ) .ДлякаждогоизклассовK1 ,..., K lвычисляетсяусловнаявероятностьпринадлежности P( K i | x) .

Объект S относится к тому классу, для которого условнаявероятность принадлежности максимальна. Данное решающее правило минимизируетвероятность ошибочной классификации. В литературе его принято называть байесовскимрешающим правилом или оптимальным байесовским классификатором. К сожалению,байесовское решающее правило не может быть реализовано в подавляющем большинствепрактических задач из-за того, что вероятностное распределение неизвестно.Однако мы можем попытаться оценить условные вероятности принадлежностиP( K i | x) , используя информацию, содержащуюся в обучающей выборке.Метод k -ближайших соседей.

Простым, но достаточно эффективным подходом здесьявляется метод k -ближайших соседей. Оценка условных вероятностей P( K i | x) в методеk -ближайших соседей ведется по ближайшей окрестности Vk точки x(S ) в признаковомпространстве, содержащей по крайней мере kпризнаковых описанийобъектов18обучающей выборки. В качестве оценки P( K i | x) выступает отношениеki, где k i - числоkобъектов из класса K i в окрестности Vk .

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

При этом в качестве оптимального берется точисло ближайшихсоседей, при котором оценка точности распознаваниясиспользованием режима скользящего контроля максимальна. Основным недостаткомметода k -ближайших соседей является снижение его эффективности при малых объемахвыборки и высокой размерности признакового пространства.Аппроксимация с помощью многомерных нормальных распределений. Следуетотметить, что условная вероятность P( K i | x) связана с априорными вероятностямиклассов P ( K1 ),  , P ( K l ) и с плотностями вероятностей f1 (x),  , f l (x) по формуле БайесаP( K i | x) f i (x)P( K i )l f (x)P( K )i 1i,(1.2)iОценки условных вероятностей P( K i | x) могут быть получены по формуле (1.2) из оценоквероятностей P ( K1 ),  , P ( K l ) и плотностей f1 (x),  , f l (x) .