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

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

3.7. Mетод Q ближайших соседей

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

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

,

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

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

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

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

Рис. 25. Граница, разделяющая два класса для случая одного ближайшего соседа

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

,

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

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

3.8. Метод опорных векторов

Современный метод опорных векторов /62/ является развитием метода «обобщенный портрет» /11/ на случаи линейно неразделимых классов и позволяет строить оптимальные линейные или нелинейные разделяющие поверхности.

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

(3.10)

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

(3.11)

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

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

Таким образом, оказывается возможным получение нелинейных разделяющих поверхностей с хорошими дискриминационными свойствами. На Рис. 26 представлен вид такой поверхности для случая двух классов. Квадратами отмечены опорные вектора.

Рис. 26. Разделяющая поверхность для случая двух классов.

В качестве ядровых функций, используемых при решении задачи распознавания образов, выступают:

1. Полином скалярного произведения

2. Гауссиана

3. Тангенс гиперболический .

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

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

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

3.9. Многослойный перцептрон

Многослойный перцептрон /57/ является нейронной сетью с несколькими слоями нейронов: входным, возможно несколькими промежуточными (скрытыми) и выходным слоями. Каждый нейрон промежуточного слоя соединён синапсами со всеми нейронами предшествующего и последующего слоев (рис. 10). Сеть в системе РАСПОЗНАВАНИЕ может содержать один, два или три скрытых слоев. Также допускается отсутствие скрытых слоев, в этом случае каждый выходной нейрон соединен непосредственно с каждым элементом входного слоя (слоем нейронов-рецепторов).