Линейные и кусочно-линейные разделяющие функции

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

, (2.18)

где — весовые коэффициенты для класса . Каждый весовой коэффициент относится к определенной составляющей вектора существенных признаков. Для удобства записи вводится весовой коэффициент с нулевым индексом . Это позволяет записать разделяющую функцию в более компактной форме:

(2.18а)

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

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

. (2.19)

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

(2.20)

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

,

где

.

В правильности определения номера класса можно легко убедиться:

следовательно

Особый случай соответствует уравнению поверхности, разделяющей рассматриваемые области. Решение о принадлежности каждой точки этой поверхности принимается произвольно; так, например, можно относить каждую точку этой разделяющей поверхности к классу, имеющему меньший (или больший) индекс, либо использовать какое-нибудь иное правило.

Для случая сепарабельных классов () решение о принадлежности объекта к определенному классу будет устанавливаться решающим правилом вида:

, (2.21)

где — дополнение множества до множества , т.е. .

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

.

Отсюда для решающей функции получим

.

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

(2.22).

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

.

Отсюда для разделяющей поверхности (поскольку разделяющая функция линейна, то такой поверхностью, в общем случае, будет гиперплоскость) получим уравнение

(2.23).

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

, .

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

.

Если это соотношение выполняется, то предъявляемый объект принадлежит первому классу.

Решающая функция в этом случае будет иметь вид

.

Отсюда легко получить решающее правило

.

Разделение пространства существенных признаков на две области соответствующие первому и второму классам приведено на рис. 2.13. Границей классов в этом случае является прямая

.

Для объекта разделяющая функция

,

Следовательно, данный объект принадлежит второму классу.

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

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

Линейной разделяющей функции в многомерном пространстве существенных признаков соответствует гиперплоскость. Уравнение гиперплоскости, проходящей перпендикулярно к отрезку, соединяющему точки соответствующие представителям классов, и через его середину определяет заодно и разделяющую функцию. Следует отметить, что гиперплоскость, удовлетворяющая данным условиям, является единственной.

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

Функция называется выпуклой, если выполняется соотношение

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

Следует отметить, что не редки ситуации, когда разделяющие функции не являются выпуклыми. На рис. 2.14 приведен случай, когда каждый из двух классов состоит из двух областей: , а . Если считать, что каждый из классов состоит из двух подклассов: и , а каждый из них рассматривать как самостоятельный класс, то для построения системы классификации можно использовать линейные разделяющие функции. В этом случае задача классификации сводится к построению кусочно-линейных разделяющих функций. В рамках такого подхода возможны три различных случая [ Р1 ]:

1. Классы разделяются с помощью линейных разделяющих функций. При этом в пространстве образов (пространстве существенных признаков) возникает несколько областей которые не соответствуют ни одному из классов (см. рис. 2.15.а).

2. Каждый класс отделяется от другого, с помощью линейной гиперповерхности, при этом в пространстве образов возникает только одна область, которая не соответствует ни одному из классов (см. рис. 2.15.б).

3.
Пространство образов разделяется только на области соответствующие классам (см. рис. 2.15. в).

Для построения кусочно-линейных разделяющих функций можно воспользоваться процедурой предложенной Аркадьевым и Браверманом. Суть этого метода заключается в следующем.

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

.

Преобразуем его к виду

.

Тогда уравнение перпендикуляра к данной прямой проходящего через точку с координатами , т.е. через середину отрезка , будет иметь вид

.

Это уравнение заодно определяет разделяющую функцию .

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

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

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

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