Теоретическая часть. Постановка задачи дискриминантного распознавания образов

Постановка задачи дискриминантного распознавания образов

В распознавании образов рассматривается вопрос о разделении объектов на классы. При этом требуется по некоторому описанию объекта (такое описание называется образом) определить его отношение к тому или иному классу. В зависимости от способа описания объектов различают дискриминантные, логические и синтаксические методы распознавания. В данной лабораторной работе изучаются простейшие дискриминантные методы.

В дискриминантном распознавании образов объекты представляются в виде векторов. Каждый из компонентов этих векторов рассматривается как признак с вещественным значением, а сам вектор называется вектором признаков.

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

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

В данной работе рассматривается случай двух классов.

Метод эталонных образов

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

Поскольку сходство двух объектов может трактоваться как величина, противоположная расстоянию между ними, то эталон – это объект, для которого минимально среднее расстояние до других объектов.

Пусть в обучающей выборке первому классу соответствует M ₁ элементов , а второму классу – M ₂ элементов . Тогда эталонные образы для каждого из классов могут быть определены как

, . (8)

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

, . (9)

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

. (10)

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

Метод ближайшего соседа

Другой широко распространенный эвристический метод распознавания – метод ближайшего соседа (или его обобщение – метод k -ближайших соседей).

Идея этого метода крайне проста: новый образ относится к тому классу, к которому он ближе. При этом расстояние от образа до класса определяется как расстояние от образа до ближайшего элемента класса.

Тогда на основе обучающей выборки , i =1,…, M, может быть построено следующее решающее правило:

. (11)

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

Дата добавления: 2015-06-27