Применение метода эталонов к частично пересекающимся образам.

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

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

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

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

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

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

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

Например, пусть пресекаются три эталона , и , относящиеся соответственно к трем образам , и . И пусть эталонные оболочки этих образов состоят из совокупностей эталонов , и .

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

Для областей пересечения решающее правило имеет вид:

Дополнительная минимизация числа признаков.

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

Можно рассмотреть два подхода к дополнительной минимизации признаков.

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

«Общая» совокупность координат пространства признаков для всех эталонов всех образов может быть определена как объединение подмножеств из минимального числа координат, найденных для каждого эталона в отдельности.

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

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

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

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

5.7. АЛГОРИТМ ДИСКРИМИНАНТНАЯ ФУНКЦИЯ

Назначение

— решение задач распознавания в ситуациях, когда в МО представлены объекты образов (), распределенные нормально.

Постановка задачи.

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

Метод решения задачи.

Этот метод основан на предположении, что объекты, составляющие каждый из образов, многомерно нормально распределены. Мы опираемся на эталонные объекты. Теоретически разделяются:

— линейный дискриминантный анализ, когда матрицы ковариации для разных образов равны;

— квадратичный дискриминантный анализ, когда матрицы ковариации для разных объектов различны.

Линейный дискриминантный анализ. 

Рассмотрим случай, когда в МО имеется два образа. Оказывается, что при равных ковариационных матрицах поверхность с одной стороны от которой больше вероятность принадлежности к одному из образов, а с другой к другому (критерий Байеса) является гиперплоскость, т.е. линейная поверхность размерности (— размерность пространства). Уравнение гиперплоскости в общем виде можно записать следующим образом:

.

В данном случае эта поверхность вычисляется следующим образом:

(5.1)

Формула (5.1) называется уравнением линейной дискриминантной функции, где

— -мерный вектор столбец в пространстве свойств ;

— математическое ожидание (среднее) объектов 1-го образа;

— математическое ожидание (среднее) объектов 2-го образа;

— транспонирование;

— матрица коэффициентов ковариации.

Коэффициенты ковариации вычисляются следующим образом:

,

где M — знак математического ожидания.

Коэффициенты ковариации тесно связан с коэффициентом корреляции:

, где

— среднее квадратичное отклонение () -го свойства;

— среднее квадратичное отклонение () -го свойства;

Дисперсия .

Дискриминантная плоскость разбивает все пространство на две части. При этом точки пространства, относимые к 1-му образу, при подставлении своих координат в дискриминантную функцию дадут , а точки 2-го образа — .

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

Значение матриц ковариации вычисляются по формулам:

;

.

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

.

Разбиение тем лучше, чем больше .