Методы функций близости

Методы данной группы основаны на использовании функций, оценивающих меру близости между распознаваемым образом с вектором x^* = (x^*₁,….,x^*_n), и эталонными образами различных классов, представленными векторами xⁱ = (xⁱ₁,…, xⁱ_n), i=1,…,N, где i – номер класса образов.

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

Функция, ставящая в соответствие каждой паре векторов xⁱ, x^* вещественное число как меру их близости, т.е. определяющая расстояние между ними может быть достаточно произвольной. В математике такую функцию называют метрикой пространства. Она должна удовлетворять следующим аксиомам:

r(x,y)= r(y,x);

r(x,y) > 0, если x не равен y и r(x,y)=0 если x=y;

r(x,y) <= r(x,z)+ r(z,y)

Перечисленным аксиомам удовлетворяют, в частности, следующие функции

a_i=[sum(xⁱ_j ‑ x_j^*)²]^1/2, j=1,2,…n.

b_i=sum[abs (xⁱ ‑ x_j^*)], j=1,2,…n.

c_i=max abs (xⁱ ‑ x_j^*), j=1,2,…n.

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

Часто в качестве функции близости выбирают среднеквадратическую разность координат распознаваемого образа x^* и эталона xⁱ, т.е. функцию

d_i = (1/n) sum(xⁱ_j ‑ x_j^*)², j=1,2,…n.

Величина d_i геометрически интерпретируется как квадрат расстояния между точками в пространстве признаков, отнесенный к размерности пространства.

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

В таком случае d_i = (1/n) sum w_j (xⁱ_j ‑ x_j^*)², j=1,2,…n,

где w_j – весовые коэффициенты.

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

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

Группы близких друг другу точек образов (скопления образов) в пространстве признаков называют кластерами, а задачу выделения таких групп – задачей кластеризации.

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

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

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

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

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 - 2x xⁱ + xⁱ xⁱ

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

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

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

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

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

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

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

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

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

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

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

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