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

Пример двумерных синдромов дан на рисунке 22.Оптимальноеразбиениевнутрификсированноймоделиищетсяпутеммаксимизации функционала прогностической силы F p .Предположим, что мы ищем множество одномерных синдромов для класса K j .Пусть Rразбиение областидопустимых значенийнекоторого признака X на L~подобластей q1j ,, qLj ,  0j - доля объектов класса K j во всей обучающей выборке S 0 , mlj ~число объектов S 0 , у которых значение X принадлежит подобласти qlj ,  l j - доля класса~K j в подмножестве объектов S 0 , у которых значение X принадлежит подобласти qlj .76~Тогда значение функционала F p ( R, S 0 , K j ) для разбиения R вычисляется по обучающей~~выборке S 0 в виде суммы: Fp ( R, S0 , K j ) L1( l j  0j ) 2 mlj .jj 0 (1  0 ) l 1В качестве оптимального для класса K j разбиения Roj области допустимыхзначений признака X выбирается разбиение, доставляющее максимум функционалу~F p ( R, S 0 , K j ) .

Для оценки качества распознавания наряду с функционаломпрогностической силы используется также индекс нестабильности, задаваемый какотношение рассчитанной в режиме скользящего контроля средней вариации границразбиений к выборочной дисперсии признака X . Пусть b10 ,  , bL01 - граничные точки,разделяющие соседние подобласти разбиения Roj . Пусть b1k ,  , bLk1 граничные точкиразделяющие соседние подобласти разбиения Rkj , рассчитанные по обучающей выборке~S 0 без k -го объекта, D - выборочная дисперсия признака X . Индекс нестабильности~границ Fs ( S 0 , K j , L) для модели с L подобластями рассчитывается как отношение:n1[D( L  1) k 1~Fs ( S 0 , K j , L) L 1 (bl 1kl bl0 ) 2 ] .Выбор из моделей разбиений I или II в методе СВС регулируется с помощьюпорога  p для функционала прогностической силы F p и порога  s для индексанестабильности Fs .

Каждый раз выбирается модель с большим значением функционалаF p , если ее индекс нестабильности не превышает порог  s . Если ни для одной модели невыполняются условия Fp   p и Fs   s то признак X исключается из рассмотрения.~Пусть Q 0j - множество синдромов для класса K j , построенных на этапе обучения.Предположим, что для некоторого объекта s * вектор описывающих его переменных x *~принадлежит пересечению синдромов q1j ,, qrj из системы Q 0j . Тогда оценка объекта s *за класс K j вычисляется с помощью процедуры статистически взвешенного голосования.r wei jj ( s* ) i 1ri weii 1ijji, где wei i j - вес i -ого синдрома, вычисляемый по формуле77weii j mij 1  j1 j , di  (1  i j ) i j  (1  0j ) 0j - оценка дисперсии индикаторнойjmi  1 dini1(1  0j ) 0j вводится для избежанияjmiфункции класса K j на синдроме qij (слагаемое~обнуления d i j в случае, если в синдроме qij содержатся только объекты из K j  S 0 или~только объекты из CK j  S 0 ).Метод СВС наряду c селекцией признаков по критерию прогностической силы ииндексунестабильностимаксимизирующийвключаетдополнительныйпошаговыйотбор,рассчитываемый в режиме скользящего контроля коэффициент j для класса K j .

Пусть у нас имеется некотораяэффективности распознаванияконтрольнаятакже~S  {s1 , , s m } ,выборкадляобъектовкоторойвычисленыоценки  j ( s1 ),,  j ( s m ) за класс K j . Коэффициент  j вычисляется как коэффициенткорреляции между оценками и индикаторной функцией класса:mj [(s )  (S )][ (s )   (S )]ii 1im, гдеm[(s )  (S )] [ (s )   (S )]2i 1i ( si )  1приsi  K j  ( si )  0при2i 1i~~si  CK j ,  (S ) и  (S ) являются средними значениямииндикаторной функции и~функции оценок на выборке S . Отображая взаимосвязь между оценками и индикаторнойфункцией, коэффициент эффективного распознавания  j является хорошей меройэффективности распознающего оператора, основанного на взвешенном голосованиисогласно формуле (1.20).

Нашей целью является поиска набора признаков, доставляющиймаксимум коэффициенту  j , рассчитанному в режиме скользящего контроля по~обучающей выборке S 0 . Для поиска такого набора в методе СВС используетсяпошаговая процедура. Пусть X prj - предварительный набор признаков для распознаваниякласса K j , отобранных из исходного набора X in с помощью пороговых критериевпрогностической силы и нестабильности границ. На первом шаге из набора X prj винформативный набор выбирается признак, для которого коэффициент эффективногораспознавания  j имеет максимальное значение.

На каждом последующем шаге кинформативномунаборудобавляетсяпризнак,максимальноувеличивающий78коэффициент  j . Процедура завершается, когда ни один из признаков, остающихся внаборе X prj не дает увеличения  j .3.5. Линейная машинаАлгоритм «линейная машина» является известным общим подходом к разделениюклассов гиперплоскостями при числе классов большем двух. С каждым классомсвязывается линейная функция f j (x)  w j x  w0 j , j  1,2,..., l . Решающее правило имеетвид:x  K j , если f j (x)  f k (x), k  1,2,..., l , k  jНахождение неизвестных (n+1)l значений параметров w j , w0 j , j  1,2,..., l , по обучающимTnml  aijmnи контрольнымT ' nqlданным осуществляется с помощью максимизациистандартного функционала качества распознавания – доли правильно распознанныхобъектов контрольной выборки.Рис.

23. Линейная машина для задачи изчетырех классов. Границы областей решений,полученные с помощью линейной машиныУсловием правильного распознавания объектаS 'i  K jбудет выполнение системы iиз l-1 линейных неравенствi : f j ( Si' )  f k ( Si' ), k  1,2,..., l , k  j ,а условием правильного распознавания всех контрольных объектов - выполнениеqсистемы    i из m(l-1) неравенств (3.6).i 1Ay  0, y  {w1w01w 2 w02 ...w l w0l } ,(3.6)79где A - матрица коэффициентов объединенной системы  , а y  {w1w01w 2 w02 ...w l w0l } вектор-столбец неизвестных параметров линейной машины.В системе РАСПОЗНАВАНИЕ вместо системы (3.6) осуществляется решение системыAy   , y  {w1w01w 2 w02 ...w l w0l }(3.7)где управляющий параметр >0 - «компоненты правой части» задает ширину зоны,разделяющей классы и используется лишь с целью построения более устойчивойлинейной машины: при построении линейной машины находятся такие ее параметры,которые разделяют контрольные объекты с некоторым «запасом».Поскольку системы неравенств (3.7) как правило несовместны, в качестве«обобщенного» решения несовместной системы (3.7) принимается произвольное решениенекоторой ее совместной подсистемы, состоящей из максимального числа систем i .Здесь используется следующий релаксационный алгоритм приближенного поискамаксимальной совместной подсистемы системы линейных неравенств /24, 46/.Пусть дана система линейных неравенствa xijj bi , i  1...m, j  1...n,(3.8)jСистема (3.8) заменяется ей эквивалентной путем деления i- го неравенства на величинуai naj 12ij.Считается, что смежные неравенства последовательно объединены в группы по n1 штук.Требуетсянайтирешение,удовлетворяющеемаксимальномуколичествугруппнеравенств.Построим следующую релаксационную последовательностьx ( 0) , x (1) , x ( 2) ,..., x (i ) ,...

для поиска решения (3.8):x(i 1)  x(i )  k i w (i ) ,где w(i )a ,j (b   a xtk ij J ( i )tjtJ ( i )(i )j)j w(ji )2,(3.9)jJ (i )  {t :  atj x j  bt }, t  1...m .jШаг k смещения вычисляется по формуле (3.9), либо выбирается равным на протяжениивсех итераций.80Процесс поиска решения строится следующим образом. Задается произвольнаяначальная точка x ( 0)  ( x1( 0) , x2( 0 ) ,..., xn( 0) ) . В начале каждой итерации подсчитывается числовыполненных групп неравенств.

Если оно максимально относительно всех предыдущихитераций, то текущая точка x (i ) запоминается как самое лучшее на данный моментрешение. После выполнения одного из критериев остановки счета, лучшее на данныймомент решение становится окончательным. В качестве критериев остановки счетаиспользуются следующие:1) выполнено заданное управляющим параметром максимально разрешенное числоитераций;2) сумма смещений за заданное число шагов не превышает некоторогоминимального значения;3) множество невыполненных неравенств J пусто.Для приближенного поиска максимальной совместной подсистемы используетсяправило отбраковки групп неравенств, которые являются «наиболее нарушенными» привыполнении последовательности итераций. На протяжении заданного числа итераций длякаждой группы накапливается сумма величин bi   aij x j , соответствующих неравенствамjиз группы (при невыполнении неравенств).

По прошествии данного числа итерации частьгрупп (образующих необходимый «процент исключаемых объектов»), имеющих самуюбольшую сумму, помечаются как отбракованные и более не включаются в множества J .3.6. Линейный дискриминант ФишераПрограмма «линейный дискриминант Фишера» (ЛДФ) /63/ является программнойреализацией классического метода построения разделяющей гиперплоскости (см. 1.2.1.),существенно расширяющей область его применения.81Рис. 24. Разделение классов с помощью гиперплоскостиНа Рис. 24 представлен пример разделения классов с помощью линейногодискриминанта Фишера. Заметим, что существенным требованием, предъявляемым кпрактической задаче, является невырожденность матрицы внутриклассового разброса. Впротивном случае, классический метод построения ЛДФ неприменим.