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

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

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

,

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

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

,

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

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

,

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

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

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

Линейный дискриминант Фишера может быть распространен на случаи большего, чем 2 числа классов.

1.2.2. Алгоритмы распознавания, основанные на построении разделяющих поверхностей.

В основе данных подходов лежат геометрические модели классов. Предполагается, что множеству объектов каждого класса соответствует определенная область в n-мерном признаковом пространстве. Данные области имеют достаточно простую форму и их можно разделить «простой» поверхностью (прежде всего линейной, кусочно-линейной или квадратичной). Рассмотрим примеры данных алгоритмов. Будем считать для простоты, что имеются лишь два класса объектов.

Задача построения линейной разделяющей поверхности (гиперплоскости) состоит в вычислении некоторой линейной относительно признаков функции

(1.3)

и использовании при классификации следующего упрощенного решающего правила:

(1.4)

Здесь означает отнесение объекта в первый класс, - отнесение во второй, - отказ от классификации объекта.

Рис. 1. Безошибочное разделение двух классов гиперплоскостью

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

(1.5)

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

минимальна /19/.

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

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

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

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

, i=1,2,…,k. (1.6)

Условие правильной классификации всех объектов обучающей выборки некоторой функцией из (1.6) записывается в виде системы (1.7)

(1.7)

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

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

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