Основные понятия теории распознавания образов

 

Глава 2. Решающие функции

 

2.1. Общие понятия

 

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

 

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

 

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

Успех описанной  схемы распознавания образов  зависит от двух факторов:

1) вида функции  ,

2) практической  возможности определения ее коэффициентов.

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

 

2.2. Линейные решающие функции

 

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

,                                                                (2.1)

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

Общепринято во все векторы образов вводить  после последней компоненты единицу и представлять (2.1) в виде:

,                                                                                              (2.2)

где и   - пополненные векторы образов и весов соответственно. Будем называть х и w, входящие в формулу (2.2), просто вектором образа и весовым вектором соответственно.

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

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

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

где w_i=(w_i1, w_i2,…, w_in, w_i,n+1) - весовой вектор, соответствующий i-ой решающей функции.

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

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

                       для всех  ;                                                      

кроме того, (рис. 2.3).

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

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

 для всех  ,

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

,

где .

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

 

 

Рис. 2.2. Первый случай разделения на несколько классов

(ОНР - область непринятия  решения)

 

Рис. 2.3. Второй случай разделения на несколько классов

 

 

Рис. 2.4. Третий случай разделения на несколько классов

 

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