Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Решающие (дискриминантные) функции






ОСНОВНЫЕ ПОДХОДЫ К РАСПОЗНАВАНИЮ

 

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

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

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

Евклидово пространство

Одним из широко распространённых подходов к представлению распознаваемых объектов является их представление в виде точек Евклидова пространства, которое строится следующим образом.

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

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

− решающие (дискриминантные) функции;

− функции расстояния;

− функции правдоподобия.

Решающие (дискриминантные) функции

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

 

Рисунок 4.1 – Разделение классов объектов в параметрическом пространстве прямой

 

Очевидно, что для всех объектов x ∈ ω 1 (круги на рисунке) будет выполняться d (x) > 0, а для всех x ∈ ω 2 (квадраты) будет верно d (x) < 0. Таким образом, функцию d (x) можно использовать для формального определения принадлежности того или иного объекта одному из двух классов. Эта функция называется решающей (дискриминантной). В описанном случае решающая функция линейна.

В общем случае n-мерного параметрического пространства линейная решающая функция задаётся выражением

(4.1)

где w0 = (w 1, w 2, …, wn) T весовой (параметрический)вектор решающей функции,

x0 = (x 1, x 2, …, xn) T — вектор описания распознаваемого образа.

Общепринято во все векторы образов после последней компоненты добавлять 1 и записывать выражение (4.1) в виде

d (x) = w T x,

где w = (w 1, w 2, …, wn, wn+ 1) T и x = (x 1, x 2, …, xn, xn+ 1) T пополненные векторы весов и образа соответственно. Подобное пополнение рассматриваемых векторов не затрагивает основных геометрических свойств классов в параметрическом пространстве.

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

Для разбиения пространства на M > 2 классов образов ω 1, ω 2, …, ω M необходимо использование более одной решающей функции. При этом возможны три варианта их задания.

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

(4.2)

 

На рисунке 4.2 приведён пример разделения двумерного пространства на три класса с помощью трёх решающих функций d 1(x), d 2(x) и d 3(x). Области, соответствующие решению об отнесении объекта к тому или иному классу, характеризуются выполнением одного из условий вида (4.2), т.е. выполнением di (x) > 0 ровно для одного значения i.

Рисунок 4.2 – Разделение пространства на несколько классов: случай 1.

На примере присутствуют четыре области, для которых данное условие не выполняется — они отмечены на рисунке буквами «Н».

В трёх из этих областей di (x) > 0 выполняется при двух значениях i, а одна (центральная на рисунке) область характерна невыполнением этого условия при любых значениях i. Эти области соответствуют непринятию какого-либо решения об отнесении объекта к представленным классам.

2. Каждый класс отделяется от любого другого взятого в отдельности класса «индивидуальной» поверхностью.

Для M классов в таком случае потребуется M (M − 1) / 2 поверхностей (число сочетаний из M по 2). Решающие функции имеют вид dij (x) = w ijT x и обладают тем свойством, что если образ x принадлежит классуω i, то выполняется

dij (x) > 0 для всех ji.

Кроме того: dij = − dji.

На рисунке 4.3 приведена иллюстрация использования данного способа разделения параметрического пространства. Каждый класс отделяется от каждого другого отдельной прямой. Так, класс ω 1 отделяется от ω 2 решающей функцией d 12 (x), а от ω 3 — функцией d 13 (x). Область принятия решения об отнесении объекта к классу ω 1 характеризуется выполнением

 

Рисунок 4.3 – Разделение пространства на несколько классов: случай 2

 

В центральной части рисунка находится область неопределённости («Н»). Для неё характерно отсутствие какой-либо пары чисел i и j, которых удовлетворяющих условию случая 2.

3. Существует M решающих функций dk (x) = w kT x k = 1, 2, …, M, таких, что если объект x принадлежит классу ω i, то выполняется

di (x) > dj (x) для всех ji.

Данный случай является разновидностью случая 2, т.к. можно положить

dk (x) = di (x) – dj (x) = (w i - w j) T x = w ijT x

причём w ij = w i - w j.

Если di (x) > dj (x) для всех ji, то dij (x) > 0 для всех ji.

Таким образом, если классы разделимы способом случая 3, то они разделимы и способом случая 2; обратное в общем случае не верно.

На рисунке 4.4 приведён пример разделения пространства на 3 класса описанным способом. Границы, разделяющие области классов ω i и ω j, обладают свойством di (x) = dj (x), или, что эквивалентно, di (x) - dj (x) = 0.

Рисунок 4.4 – Разделение пространства на несколько классов: случай 3.

 

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

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

(4.3)

где { fi (x)}, i = 1, 2, …, K — действительные однозначные функции образа x, fK +1(x) = 1, а K +1 — число членов разложения. Несмотря на то, что приведённая формула может задавать очень сложные решающие функции, применение соответствующего преобразования позволит работать с ними как с линейными. Определим вектор , компонентами которого являются функции fi (x):

(4.4)

С помощью (4.4) выражение (4.3) записывается как

(4.5)

где w = (w 1, w 2, …, wK, wK+ 1) T

Функции { fi (x)}, после того как их значения вычислены для конкретного x, представляют просто набор чисел, а вектор — обычный K -мерный числовой вектор, пополненный единицей. По отношению к новому представлению образов выражение (4.5) представляет собой линейную функцию. Рассмотрение всех исходных образов x в виде преобразованных представлений

превращает задачу в линейную.

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

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.