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

Для устраненияэтого ограничения (а также «почти вырожденных» матриц), используется риджоценивание матрицы разбросаDˆ w  Dw  I ,где I – единичная матрица. Такая процедура называется регуляризацией матрицывнутриклассового разброса. Она позволяет устранить вырожденность матрицы, если табыла порождена неоднородностью выборки. Кроме того, регуляризация матрицы можетулучшить качество распознавания при малых обучающих выборках.

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

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

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

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

Если голос будет зависеть от расстояния до гиперплоскости, определяемойвектором w (т.е. чем дальше объект от гиперплоскости, тем больше степень уверенности впринадлежности объекта классу), то ситуация с равенством голосов станет практическиневероятной. Такой режим называется «мягкой» классификацией. Его использованиетакже позволяет использовать метод ЛДФ для построения коллективных решений.3.7.

Mетод Q ближайших соседейДанный метод распознавания образов основан на использовании функцийрасстояния /8/ и кратко описан в разделе 1.2.1. Выбор функции расстояния являетсяестественным инструментом для введения меры сходства (близости) векторных описанийобъектов, интерпретируемых нами как точки в евклидовом пространстве. Этот методклассификации оказывается весьма эффективным при решении таких задач, в которыхклассы характеризуются значительной степенью зашумленности, когда разделяющаяповерхность сложна, или классы пересекаются («почти пересекаются»).Рассмотрим выборку объектов с известной классификацией {S1 , S 2 ,..., S m } , причемпредполагается, что каждый объект выборки входит в один из классов K1 , K 2 ,..., K l .Можно определить правило классификации, основанное на принципе ближайшего соседа83(БС - правило).

Это правило относит классифицируемый объект S к классу, к которомупринадлежит его ближайший сосед. Объект Si  {S1 , S 2 ,..., S m } называется ближайшимсоседом объекта S , еслиD( Si , S )  min{D( S j , S )}, j  1,2,..., m ,jгдеD - любое расстояние, определение которого допустимо на пространствепризнаковых описаний объектов.Эту процедуру классификации можно назвать 1 – БС – правилом, так как при ееприменении учитывается принадлежность некоторому классу только одного ближайшегососеда объекта S . Аналогично можно ввестиопределениеQQ– БС – правило, предусматривающееближайших к S объектов и зачисление его в тот класс, к которомуотносится наибольшее число объектов, входящих в эту группу.На рис.

25 представлена разделяющая граница для случая двух классов приприменении правила одного ближайшего соседа. Можно заметить, что граница,разделяющая классы, является кусочно-линейной. Участки ее границ представляют собойгеометрические места точек, равноудаленных от прямых, соединяющих объектыразличных классов, находящихся на границе.Можно показать, что в случае, если все расстояния, разделяющие объекты одногокласса, меньше всех расстояний между объектами, принадлежащими различным классам,то 1 – БС – правило работает лучше, чемQ– БС – правило ( Q 1 ).Последнееобстоятельство приводит к практической целесообразности использования одногоближайшего соседа взамен нескольких за исключением, быть может, отдельных случаев,когда исследователь обладает определенными знаниями о специфическом характеревыборки.84Рис.

25. Граница, разделяющая два класса для случая одного ближайшего соседаТакже можно показать, что в случае выборок большого объема (m  ) и привыполнении некоторых благоприятных условий вероятность ошибки 1 – БС – правилазаключена в следующих пределах:pB  pe1  pB (2 гдеpBlpB ) ,l 1- байесовская вероятность ошибки, т.е. наименьшая вероятность, достижимая всреднем.

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

Иными словами, вес объекта увеличивается,если он представляет малый класс и уменьшается в противном случае. Даннуюмодификацию следует использовать в тех случаях, когда важность правильногораспознавания малых классов является существенной.3.8. Метод опорных векторов85Современныйметодопорныхвекторов/62/являетсяразвитиемметода«обобщенный портрет» /11/ на случаи линейно неразделимых классов и позволяет строитьоптимальные линейные или нелинейные разделяющие поверхности.Использование метода опорных векторов для обучения распознаванию объектовдвухклассов,представленных{x j  R n , g j  1, j  1,, N}обучающей( g j  «индикатор» класса), предполагает поисктакого направления в пространстве признаков, выражаемого векторомговоря, произвольной нормывыборкойa  R n , вообще|| a || , чтобы «зазор» между проекциями на него объектовпервого и второго классов был максимальным.

Если при этом выборка является линейнонеразделимой, то «мешающие» объекты сдвигаются к гиперплоскости, причем сумманеобходимых сдвигов должна быть минимальной. Предполагается, что границасуждении в пользу первогоaT x  b  0или второго классаbRaT x  b  0одолжнапроходить ровно посередине зазора между выборками классов, чтобы обеспечить равноеи, следовательно, максимальное удаление крайних точек обеих выборок от разделяющейгиперплоскостиaT x  b  0 , которая в этом случае называется оптимальной. Такаяконцепция приводит к задаче квадратичного программированияNa a  C   j  min,T(3.10)j 1g j (aT x j  b)  1   j ,  j  0, j  1,ЗдесьC,N- коэффициент штрафа за неправильную классификацию «мешающих»объектов.

Задачу (3.10) удобно решать в двойственной форме, используя множителиЛагранжа при каждом из ограничений, то есть при каждом объекте обучающей выборки.NN NTW (1 , N )    j   ( g j g k x j xk ) j k  maxj 1j 1 k 1N g   0,   0, j  1, , Nj jjj 1(3.11)Те из оптимальных значений множителей Лагранжа, которые оказываютсяположительными, непосредственно определяют направляющий вектор оптимальной86разделяющей гиперплоскости как линейную комбинацию векторов обучающей выборки.Данные вектора называются опорными:ag xj:j 0jjj.Заметим, что в задаче обучения (3.11) объекты обучающей выборкитолько в форме скалярных произведенийxiвходятxiT x j .

Это обстоятельство позволяет перенестиметод на случай нелинейной разделяющей функции. Предположим, что мы сначалапреобразовалиданныевнекотороепространство при помощи функции(возможнобесконечномерное)евклидовоÔ : R n  H . Теперь алгоритм обучения зависиттолько от скалярных произведений в пространствеHв формеÔ ( xi )  Ô ( x j ) .Предположим, что в исходном пространстве имеется некоторая «ядровая функция»K : K ( xi , x j )  Ô ( xi )  Ô ( x j ) . Тогда оказывается достаточным использовать функциюKв алгоритме обучения, даже не задумываясь о виде функции преобразованияпространстваÔ.Таким образом, оказывается возможным получение нелинейных разделяющихповерхностей с хорошими дискриминационными свойствами.

На Рис. 26 представлен видтакой поверхности для случая двух классов. Квадратами отмечены опорные вектора.Рис. 26. Разделяющая поверхность для случая двух классов.87В качестве ядровых функций, используемых при решении задачи распознаванияобразов, выступают:1. Полином скалярного произведения K ( x, y )  ( x  y  1) p2.