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

При этом в качестве оценокаприорных вероятностей классовP ( K1 ),  , P ( K l ) могут быть взяты доли объектовсоответствующих классов в обучающей выборке. Плотности вероятностей f1 (x),  , f l (x)восстанавливаются исходя из предположения об их принадлежности фиксированномутипу распределения.Наиболее часто используемым видом распределения является многомернаянормальная плотность, которая в общем виде представляется выражениемf ( x) 1(2 )n/2||1/ 2exp  12 (x  μ) t  1 (x  μ) ,где n - размерность признакового пространства, μ - математическое ожидание векторапризнаков x ,  - матрица ковариаций компонент вектора x , |  | - детерминант матрицы . Для построения распознающего алгоритма достаточно оценить вектор математическихожиданий μи матрицу ковариаций для каждого из классов.

Оценкаμ̂ iматематического ожидания вектора x вычисляется как вектор среднеарифметическихзначений компонент вектора x по всем объектам обучающей выборки, принадлежащим19классу K i или μ̂ i = mi 1mi1 x(s ) , гдеmi  mi1 - число объектов класса K i в обучающейjs j K iвыборке.Оценка элемента  ki k  матрицы ковариаций  i вычисляется соответственно поформуле ˆ ki k 1mi mi 1[ x (s )   ][ xs jKikikjk( s j )  ki  ] , k , k  {1,, n} . Матрицу, состоящую изэлементов ˆ ki k  обозначим ̂ i .

В оптимальном байесовском классификаторе объект Sотносится в тот класс, для которого условная вероятность P( K i | x) максимальна.Поскольку знаменатель в правой части формулы (1.2) одинаков для всех классов, томаксимум P( K i | x) (или любой монотонной функции от P( K i | x) ) достигается для тех жесамых классов, для которых достигается максимумf i (x)P( K i ) . Используя вместоплотностей f i ( x) их приближения Nˆ i (x) многомерным нормальным распределением идолюi mi  mi1mвместоP( K i ) ,можнопостроитьраспознающийалгоритм,аппроксимирующий оптимальный байесовский классификатор.

В качестве оценки g i (x)за класс K i удобнее использовать натуральный логарифм произведения Nˆ i (x) и  i :ˆ ( x)]   1 ( x t ˆ i1 x)  w t x  g 0 ,g i (x)  ln[ i Niii20t 1где w i  ˆ i1μˆ i , g i   12 μ i ˆ i μ i  12 ln(| ˆ i |)  ln( i )  n2 ln(2 ) - не зависящее от вектора xслагаемое. Распознаваемый объект S , относится к тому классу, оценка g i [x( S )] закоторый максимальна. Следует отметить, что полученное приближение оптимальногобайесовского решающего правила является квадратичным по признакам для случаев,когда ковариационные матрицы для разных классов отличаются друг от друга. В случае,если ковариационные матрицы для разных классов совпадают, различия между ихоценками стремятся к 0 с ростом объема обучающей выборки.

При этом слагаемое 12 (x t ˆ i1 x) оказывается практически одинаковым для всех классов и рассматриваемаяаппроксимация байесовского классификатора превращается в метод, использующий дляразделенияклассовлинейныеповерхности.Основныминедостаткамиметода,основанного на аппроксимации плотностей распределений классов многомерныминормальными распределениями, является его низкая эффективность при отклонении отнормальности реальных распределений. Особенно эта проблема усугубляется при20высокой размерности n признакового пространства, что связано с необходимостьюоцениванияn(n  1)элементов матрицы  .2Линейный дискриминант Фишера. Большую популярность среди исследователейприобрел метод, предложенный Фишером еще в 1936 году.

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

В качестве меры различий проекций двухклассов K1 и K 2 на направление w было предложено использовать функционалJ (w ) [ y1 (w)  y2 (w)]2,d1 ( w )  d 2 ( w )где yi (w ) - среднее значение проекций векторов описаний объектов обучающей выборкииз класса K i , т.е. yi (w) проекцийвекторов1w t x( s j ) , а d i (w ) - выборочная дисперсия(mi  mi1 ) | w | s jKiописанийобъектовобучающейвыборкиизклассаKi ,tw x( s j )1d i (w) [ yi ]2 , i {1,2} .(mi  mi1 ) s jKi | w |Смысл функционала J (w ) с точки зрения разделения двух классов ясен из егоструктуры. Он возрастает при увеличения отношения квадрата различия между среднимизначениями проекций двух классов к сумме внутриклассовых выборочных дисперсий.Можно показать /19/, что функционал J (w ) достигает своего максимума приw  Dw1 (μˆ 1  μˆ 2 ) , где Dw -матрица разброса внутри классов, μˆ i 1 x( s j ) (mi  mi1 ) s jKiвыборочный центр класса K i , i {1,2} .

Матрица разброса внутри классов определяетсяматрицразбросапокаждому изклассовилиDw  D1  D2 ,каксуммагдеDi 1[x( s j )  μˆ i ][x( s j )  μˆ i ]t . Сравнивая линейный дискриминант Фишера с(mi  mi1 ) s jKiаппроксимацией оптимального байесовского классификатора с помощью многомерныхнормальных распределений, нетрудно увидеть, что оба правила практически идентичныдля случаев, когда мы можем пренебречь различиями ковариационных матриц классов.21Линейный дискриминант Фишера может быть распространен на случаи большего, чем 2числа классов.1.2.2.

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

Рассмотрим примеры данных алгоритмов. Будем считать дляпростоты, что имеются лишь два класса объектов.Задача построениялинейной разделяющей поверхности (гиперплоскости)состоит в вычислении некоторой линейной относительно признаков функцииf (x)  a1 x1  a2 x2  ...  an xn  an1(1.3)и использовании при классификации следующего упрощенного решающего правила: 1, ( S )   , 0,Af ( S )  0,f ( S )  0,f ( S )  0.(1.4)Здесь  A ( S )  1 означает отнесение объекта в первый класс,  A ( S )  0 - отнесение вовторой,  A (S )   - отказ от классификации объекта.K1f(x)>0K2f(x)<0Рис. 1.

Безошибочное разделение двух классов гиперплоскостью22Существуют различные варианты математических постановок критериев выбора f (x) .Основной постановкой является поиск такой функции (т.е. значений неизвестныхкоэффициентов a1 , a2 ,..., an , an 1 , ), для которых число невыполненных неравенств в системеa1 x1 ( S1 )  a2 x2 ( S1 )  ...  an xn ( S1 )  an1a1 x1 ( S 2 )  a2 x2 ( S 2 )  ...  an xn ( S 2 )  an1...a1 x1 ( S m1 )  a2 x2 ( S m1 )  ...  an xn ( S m1 )  an1 0, 0, 0,(1.5)... ... ...a1 x1 ( S m11 )  a2 x2 ( S m11 )  ...

 an xn ( S m11 )  an1  0,a1 x1 ( S m12 )  a2 x2 ( S m12 )  ...  an xn ( S m12 )  an1  0,...a1 x1 ( S m )  a2 x2 ( S m )  ...  an xn ( S m )  an1 0,является минимальным. В данном случае при классификации по решающему правилу(1.4) достигается минимальное число ошибок (т.е. отнесений не в свой класс или отказ отклассификации). Если система (1.5) совместна, тогда достаточно найти произвольное еерешение относительно неизвестныхa1 , a2 ,..., an , an1 , для чего можно использоватьрелаксационные методы решения систем линейных неравенств /24/, метод конечныхприращений /19/, алгоритмы линейного программирования и другие. Однако заранее неизвестно, совместна данная система или нет. Обычно системы (1.5) являются именнонесовместными,т.е.обучающиевыборкиневозможнобезошибочноразделитьгиперплоскостью. Поэтому на методы решения систем (1.5) обычно накладываютследующее естественное ограничение: если система является совместной, тогда методнаходит некоторое ее решение, если система несовместна – находится некоторое«обобщенное» решение системы.

Под обобщенным решением понимают решениенекоторойеемаксимальнойсовместнойподсистемы(находитсятакойнаборa1 , a2 ,..., an , an1 , при котором будет выполнено максимальное число неравенств системы(1.5) ), либо такой набор a1 , a2 ,..., an , an1 , при котором «нарушенность» системы (1.5) будет23минимальна /19/.K1f(x)>0K2f(x)<0Рис. 2.Разделение двух классов гиперплоскостью с минимальным числом ошибок. Черным цветом отмеченыобъекты обучения, на которых оптимальная гиперплоскость совершает ошибкиМетоды классификации с помощью разделяющей гиперплоскости просты иэффективны для относительно простых практических задач.

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

Пусть дана некотораясовокупность линейных функцийf i (x)  ai1 x1  ai 2 x2  ...  ain xn  ai ,n1 , i=1,2,…,k.(1.6)Условие правильной классификации всех объектов обучающей выборки некоторойфункцией из (1.6) записывается в виде системы (1.7)f i ( S j )  ai1 x1 ( S j )  ai 2 x2 ( S j )  ...  ain xn ( S j )  ai ,n1  0,j  1,2,..., m1 ,f i ( S j )  ai1 x1 ( S j )  ai 2 x2 ( S j )  ...  ain xn ( S j )  ai ,n1  0,j  m11 , m12 ,..., m.(1.7)24Совокупность функций (1.6) называется комитетом для системы (1.7) , если каждомунеравенству в системе (1.7) удовлетворяет более половины функций из (1.6) .Пусть для заданной обучающей выборки построен некоторый комитет (1.6).

Тогдарешающее правило может быть записано в следующем виде: 1, A ( S )   , 0,k sign( f (S ))  0,i 1ki sign( f (S ))  0,i 1ki sign( f (S ))  0.i 1iТо есть объект относится в первый класс, если более половины функций положительны иво второй класс, если более половины функций отрицательны. В противном случаепроисходит отказ от распознавания.f3(x)>0f3(x)<0f2(x)>0f2(x)<0K1K1K1f1(x)>0K2K2K2f1(x)<0K2Рис.

3. Разделение двух классов комитетом из трех линейных функцийВ работах /42, 43, 45/ доказано существование комитетов для непротиворечивых таблицобучения, исследованы задачи построения минимальных комитетов, исследованыобобщения комитетов на нелинейные случаи.25Другим примером построения кусочно-линейных разделяющих поверхностейявляются алгоритмы обобщенного портрета /11/.С помощью алгоритмов кластерного анализа исходное пространство признаковыхописаний делится на p «простых» непересекающихся областей таких, что классы линейноразделимы по объектам обучающей выборки для каждой из областей.

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