1.2. Методы детерминистской классификации

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

Математически задача классификации может быть сформулирована с помощью разделяющей функции [1].

Пусть оси, обозначают возможных классов образов, подлежащих распознаванию, и пусть

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

Рис. 1.2. Классификатор.

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

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

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

много различных форм для удовлетворяющих условию (1.2). Некоторые важные разделяющие функции будут рассмотрены ниже.

Рис. 1.3. Пример разбиения в двумерном пространстве признаков.

А. Линейные разделяющие функции.

В этом случае в качестве берется линейная комбинация измеренных признаков т. е.

Решающая граница между областями со и в имеет вид

где

и

Рис. 1.4. Вычислитель линейной разделяющей функции.

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

пороговый логический элемент, как показано на рис. 1.5. Полагая из рис. 1.5 получим, что

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

Рис. 1.5. Линейный классификатор двух классов.

При этом комбинации выходных сигналов пороговых логических элементов достаточны для различения классов при Иначе говоря, остаются справедливыми общие схемы рис. 1.2 и 1.4.

В. Классификатор по минимальному расстоянию.

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

где есть расстояние между Расстояние можно определить, например, следующим образом:

где индекс определяет операцию транспонирования вектора. Из (1.8) следует, что

Так как не зависит от то соответствующая разделяющая функция для классификатора по минимальному расстоянию имеет вид

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

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

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

где число опорных векторов множества Определим расстояние между вектором входных признаков следующим образом:

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

Пусть

Тогда

Следует отметить, что является линейной комбинацией признаков. Поэтому классификаторы, использующие (1.12) или (1.14), часто называют кусочно-линейными классификаторами [1]. Примером кусочно-линейного классификатора является -перцептрон, показанный на рис. 1.6.

Рис. 1.6. а-перцептрон.

D. Полиномиальные разделяющие функции.

Полиномиальная разделяющая функция степени может быть представлена в следующем виде:

где является формой

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

Разделяющая функция будет иметь следующий вид:

где

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

Рис. 1.7. Вычислитель квадратичной разделяющей функции.

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