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

Рис.22. Пример двумерных синдромов. Символами «крестик» отмечены объекты класса, для которого вычисляются синдромы, символами «нолик» - объекты остальных классов. Видно, что доля крестиков в синдроме II значительно превышает долю крестиков в синдромах I , II и III. В то время как доля «крестиков» в синдроме III значительно ниже доли «крестиков» в синдромах I , II и IV. Синдромы I , II III и IV являются множеством всевозможных пересечений пары одномерных синдромов (I II) и (III IV), которые строятся по признаку и пары одномерных синдромов (I III) и (II IV), которые строятся по признаку

Для построения одномерных синдромов используются модели I и II, различного уровня сложности. При этом модель I включает в себя все разбиения области допустимых значений признака с помощью одной граничной точки на две подобласти, а модель II включает в себя все разбиения области допустимых значений признака с помощью двух граничных точек на три подобласти. Пример двумерных синдромов дан на рисунке 22.

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

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

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

.

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

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

, где - вес -ого синдрома, вычисляемый по формуле

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

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

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

3.5. Линейная машина

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

, если

Нахождение неизвестных (n+1)l значений параметров , по обучающим и контрольным данным осуществляется с помощью максимизации стандартного функционала качества распознавания – доли правильно распознанных объектов контрольной выборки.

Условием правильного распознавания объекта будет выполнение системы из l-1 линейных неравенств

: ,

а условием правильного распознавания всех контрольных объектов - выполнение системы из m(l-1) неравенств (3.6).

, (3.6)

где A - матрица коэффициентов объединенной системы , а - вектор-столбец неизвестных параметров линейной машины.

В системе РАСПОЗНАВАНИЕ вместо системы (3.6) осуществляется решение системы

(3.7)

где управляющий параметр >0 - «компоненты правой части» задает ширину зоны, разделяющей классы и используется лишь с целью построения более устойчивой линейной машины: при построении линейной машины находятся такие ее параметры, которые разделяют контрольные объекты с некоторым «запасом».

Поскольку системы неравенств (3.7) как правило несовместны, в качестве «обобщенного» решения несовместной системы (3.7) принимается произвольное решение некоторой ее совместной подсистемы, состоящей из максимального числа систем . Здесь используется следующий релаксационный алгоритм приближенного поиска максимальной совместной подсистемы системы линейных неравенств /24, 46/.

Пусть дана система линейных неравенств

(3.8)

Система (3.8) заменяется ей эквивалентной путем деления i- го неравенства на величину .

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

Построим следующую релаксационную последовательность для поиска решения (3.8):

где , (3.9)

.

Шаг смещения вычисляется по формуле (3.9), либо выбирается равным на протяжении всех итераций.

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

1) выполнено заданное управляющим параметром максимально разрешенное число итераций;

2) сумма смещений за заданное число шагов не превышает некоторого минимального значения;

3) множество невыполненных неравенств пусто.

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

3.6. Линейный дискриминант Фишера

Программа «линейный дискриминант Фишера» (ЛДФ) /63/ является программной реализацией классического метода построения разделяющей гиперплоскости (см. 1.2.1.), существенно расширяющей область его применения.

Рис. 24. Разделение классов с помощью гиперплоскости

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

где I – единичная матрица. Такая процедура называется регуляризацией матрицы внутриклассового разброса. Она позволяет устранить вырожденность матрицы, если та была порождена неоднородностью выборки. Кроме того, регуляризация матрицы может улучшить качество распознавания при малых обучающих выборках. При вычислении матриц разброса особое внимание следует обратить на внедиагональные элементы. Последние существенно зависят от коэффициентов корреляции между признаками. В частности, если признаки независимы, то их коэффициенты корреляции равны нулю. В этом случае соответствующие внедиагональные элементы также должны быть нулевыми. Однако, в связи с конечным объемом выборки, вычислить истинные значения корреляций не представляется возможным. Вместо этого вычисляются их оценки, которые часто оказываются отличными от нуля даже для независимых признаков. Из-за этого получившиеся матрицы разброса могут отражать ложные зависимости между признаками, что, в свою очередь, приводит к перенастройке алгоритма на обучающую выборку и ухудшению качества распознавания. Для устранения данных негативных эффектов используется порог значимости коэффициента корреляции, который можно устанавливать в пределах от нуля до единицы. Если оценка корреляции оказывается по модулю ниже порога, то она считается ложной и игнорируется. Внедиагональные элементы, отвечающие незначимым коэффициентам корреляции, обнуляются. Обычно, порог устанавливают близким к нулю (порядка 0.1 – 0.2), но в некоторых задачах исследователи рекомендуют использовать матрицы разброса только с диагональными элементами. Это соответствует установке порога значимости коэффициента корреляции близкого к единице.