2.2. ЛИНЕЙНЫЕ РЕШАЮЩИЕ ФУНКЦИИ

Простой вариант двумерной линейной решающей функции, введенной в § 2.1, можно легко обобщить на n-мерный случай. Общий вид линейной решающей функции задается формулой

где вектор называется весовым или параметрическим.

Общепринято во все векторы образов вводить после последней компоненты 1 и представлять соотношение (2.2.1) в виде

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

Предполагается, что в случае разбиения на два класса решающая функция обладает следующим свойством:

Рассмотрим случаи разбиения на несколько классов , т. е. предполагается, что объекты принадлежат более чем двум классам.

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

где — весовой вектор, соответствующий решающей функции.

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

Приведем численную иллюстрацию; пусть решающие функции, соответствующие рис. 2.2, а, имеют вид

Следовательно, три разделяющие границы определяются уравнениями

Итак, любой образ, для которого выполняются условия , автоматически зачисляется

(кликните для просмотра скана)

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

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

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

Так как при образ зачисляется в класс .

Случай 2. Каждый класс отделяется от любого другого взятого в отдельности класса «индивидуальной» разделяющей поверхностью, т. е. классы попарно разделимы. В этом случае существует (число сочетаний из М классов по два) разделяющих поверхностей. Решающие функции имеют вид и обладают тем свойством, что если образ принадлежит классу то

кроме того, .

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

Пример. На рис. 2.3, а представлены три класса образов, разделимых согласно случаю 2. Очевидно, что ни один класс нельзя отделить от всех остальных с помощью единственной разделяющей поверхности. Каждая из приведенных на рисунке

(кликните для просмотра скана)

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

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

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

Рассмотрим классификацию объекта, заданного вектором . Подстановка его элементов в выбранные решающие функции лает

Отсюда автоматически следует, что . Так как

и в область неопределенности мы не попали, то рассматриваемый образ зачисляем в класс

Случай 3. Существует М решающих функций , таких, что если образ принадлежит классу то

Эта ситуация является разновидностью случая 2, поскольку можно положить

где . Легко убедиться в что если для всех то для всех т. е. если классы разделимы, как в случае 3, то они автоматически разделимы и как в случае 2. Обратное, сообще говоря, не верно.

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

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

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

Пусть в качестве решающих функций выбраны следующие:

Разделяющие границы для трех классов выглядят при этом так:

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

(кликните для просмотра скана)

В качестве примера классификации рассмотрим обработку образа . Подстановка компонент этого вектора в выбранные решающие функции дает

Поскольку

образ относится к классу .

Если какой-либо из рассмотренных выше вариантов линейной решающей функции обеспечивает классификацию в некоторой заданной ситуации, то соответствующие классы называются линейно разделимыми. Читателю следует четко уяснить, что основная проблема, возникающая после определения набора решающих функций (линейных либо каких-то иных), заключается в отыскании коэффициентов. Как уже указывалось выше, для определения этих коэффициентов обычно используется доступная выборка образов. После того как коэффициенты всех решающих функций определены, можно приступать к построению системы распознавания, как это описано в гл. 1.