Методы дискриминантных функций

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

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

d (x)= w ₁ x ₁ + w ₂ x ₂ +…+ w_n x_n + w_{n +1} = Wx + w_n

где x - вектор образа, w= (w ₁, w ₂,… w_n) – вектор весовых коэффициентов.

В случае разбиения на два класса X ₁ и X ₂ дискриминантная функция d (x) позволяет осуществить распознавание в соответствии с правилом:

x принадлежит X ₁, если d (x)>0;

x принадлежит X ₂, если d (x)<0.

Если d (x)=0, то имеет место случай неопределенности.

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

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

x принадлежит X ₁, если d ₁(x)>0, d ₂(x)<0, d ₃(x)<0;

x принадлежит X ₂, если d (x)<0, d ₂(x)>0, d ₃(x)<0;

x принадлежит X ₃, если d (x)<0, d ₂(x)<0, d ₃(x)>0.

При этом считается, что для других комбинаций значений d ₁(x), d ₂(x), d ₃(x) имеет место случай неопределенности.

Разновидностью метода дискриминантных функций является метод решающих функций. В нем при наличии m классов предполагается существование m функций d_i (x), называемых решающими, таких, что если x принадлежит X_i, то d_i (x) > d_j (x) для всех j не равных i,т.е. решающая функция d_i (x) имеет максимальное значение среди всех функций d_j (x), j =1,..., n..

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

Будем считать, что задано m классов с эталонами xⁱ = (xⁱ ₁,…, xⁱ_n), i= 1,…, m.

Евклидово расстояние между вектором признаков распознаваемого образа x и вектором эталонного образа определяется формулой || xⁱ ‑ x || = [sum(xⁱ_j ‑ x_j)²]^1/2, j =1,2,… n.

Вектор x будет отнесен к классу i, для которого значение || xⁱ ‑ x^* || минимально.

Вместо расстояния можно сравнивать квадрат расстояния, т.е.

|| xⁱ ‑ x ||² = (xⁱ ‑ x)(xⁱ ‑ x)^т = x x -2 x xⁱ + xⁱ xⁱ

Поскольку величина x x одинакова для всех i, минимум функции || xⁱ ‑ x ||² будет совпадать с максимумом решающей функции

d_i (x) = 2 x xⁱ - xⁱ xⁱ.

то есть x принадлежит X_i, если d_i (x) > d_j (x) для всех j не равных i.

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

d_i (x)= w_{i 1} x ₁ + w_{i 2} x ₂ +…+ w_in x_n + w_{i n +1}

Она может быть наглядно представлена соответствующей структурной схемой.

Для машины, осуществляющей классификацию по минимуму расстояния имеют место равенства: w_ij = -2 xⁱ_j, w_{i n +1} = xⁱ xⁱ.

Эквивалентное распознавание методом дискриминантных функций может быть осуществлено, если определить дискриминантные функции как разности d_ij (x)= d_i (x)‑ d_j (x).

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

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

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

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

Дата добавления: 2014-01-14