А А Федоров, Ю В Лопухин, А Ю Скобликов - Задание метрики в задачах классификации объектов различной природы - страница 1

Страницы:
1  2 

УДК 658.012.102

А.А. ФЕДОРОВ, Ю.В. ЛОПУХИН, А.Ю. СКОБЛИКОВ

ЗАДАНИЕ МЕТРИКИ В ЗАДАЧАХ КЛАССИФИКАЦИИ ОБЪЕКТОВ РАЗЛИЧНОЙ ПРИРОДЫ

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

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

Целью исследования является разработка меры близости для объектов, заданных числовым вектором. Классификации объектов различной природы, как правило, выполня­ется с помощью ЭВМ, что требует наличия четкого и достаточно простого алгоритма. В научных и прикладных сферах при классификации объектов или измерений используют коэффициенты сходства различных исследователей Рао, Хаммана, Дейка, Танимото [1,4]. Оперировать с коэффициентами сходства несложно, но эффективней применять меру бли­зости [3,4]. Для решения конкретных задач классификации, чтобы определить, являются ли два объекта близкими между собой, необходимо дать количественное определение меры близости. Это достигается введением функции, измеряющей близость на множестве рас­сматриваемых объектов или измерений. Понятие близости является одним из основных в таких задачах и поэтому требует не интуитивного представления, а математически кор­ректного.

2. Выбор меры близости классифицируемых объектов

Наиболее употребительной в настоящее время является евклидова мера, хотя она имеет существенный недостаток - не учитывает возможной неравномерности осей про­странства. Обобщением евклидовой метрики является мера Махаланобиса, которая инва­риантна относительно аффинных преобразований

d = {(Xi - Xj)T W-1 (Xi - Xj)}S, (1) где W-1 - матрица, обратная матрице рассеяния; Xi, Xj - числовые векторы измерений признаков, характеризующие соответственно i-й и j-й элементы множества объектов.

Выбор меры близости в значительной степени зависит от особенностей классифицируе­мых объектов. Так, для рассматриваемого в [2] множества элементов X = {Xj}, характе­ризующихся структурой отношений

Xj nXj *0,Xj й Xj,|XjHXj|,i Ф j, (2)

Xj = {gik},gik є {0,1},i, j = 1,n,k = 1,m , в качестве меры близости использовалось выражение на основе коэффициента сходства Рао:

d1 = 1 -

Xj n Xj

(3)

С точки зрения практических приложений для рассматриваемого выше множества элементов X, признаки которых являются двоичными переменными, могут оказаться полезными следующие метрики:

Xi nXj d2 = 1 j

(4)

2Xj nXj

Для общего случая, когда gjp є {0, 1, 2, k}, в качестве меры для группирования можно использовать выражение

m

N+|Xj

p [а     если gipgjp =o,

где ОС- = >

ij  [gip+g если gipgjp Ф 0.

Чтобы выражение (6) использовалось в качестве меры близости, необходимо проверить выполнение аксиом Фреше.

Так как для любой пары XiXj справедливо (2), то очевидно, что 0 < dij < 1, dij = dji. Необходимо проверить справедливость аксиомы треугольника

1 - Xi n Xj < 1 - |Xi n Xk +1 - Xk n Xj

Xi u Xj        Xiu Xk       Xk u Xj . (7)

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

Обозначим взаимные пересечения множества признаков, характерные для объектов, представленных на рисунке:

ai =|Xi\[(Xi nXj) u (Xi n Xk)]|, (8) aj =|Xj\[(Xj n Xi) u (Xj n Xk)]|, (9)

ak =| Xk \[(Xk n Xi) u (Xk n Xj)]| , (10)

где ai , aj ak - признаки, присущие соответственно только i-му, j-му, k-му объекту:

aij =|Xi n Xj\[(Xi n Xj n Xk)]|, (11) здесь aij - признаки, одновременно присущие i-му и j-му объектам:

aik =|Xi n Xk\[(Xi n Xj n Xk)]|, (12) aik - признаки, одновременно присущие i-му и k-му объектам:

ajk =|Xj n Xk\[(Xi n Xj n Xk)]|, (13)где ajk - признаки, одновременно присущие j-му и k-му объектам:

aijk =|Xi n Xj n Xk|, (14) aijk - признаки, одновременно присущие i-му, j-му и k-му объектам:

X =| Xi u Xj u Xk |= ai + aj + ak + ay + aik + ajk + aijk . (15) Согласно взаимным пересечениям, из рисунка и с учетом выражений (8)-(15) неравен­ство (7) примет вид:

aij + aijk   aik + aijk   a jk + aijk

—-— +-------— < 1. (16)

X - ak X - a j X - ai

3. Исследование выполнимости меры близости

Для проверки выполнимости неравенства (16) воспользуемся теоремой о необходимых условиях экстремума функции, заданной в виде неравенства [5]. Обозначим:

U = aij + aijk + aik + aijk - a jk + aijk

= X - ak      X - aj       X - ai   . (17) Составим функцию Лагранжа

F = -MaX+* + ^iX+* -- *<I ae - X) -IXeae, e = {ij,k,ij,ikjk,ijk},

(18)

где X0, X и Xe - множители Лагранжа, согласно [5] не все равны нулю, при условии, что

Iae -X = 0, (19)

e

ae > 0 . (20) Так как ограничения (19) линейны, то из [3] следует, что

X0 =1. (21)

Тогда (18) будет иметь вид:

a jk + aijk   aij + aijk   aik + aijk

F

-----лі   7   і ; і      —   лі

X(I(ae - X) -lXeae) (22) X - ai       X - ak       X - aj        ^ e . (22)

Продифференцируем (22) по aij, aik, akj, aijk, ak, aj, ai, X и приравняем производные нулю:

- X-ak"-X-Xij=0, (23)

- X-a~~^~/4k-v' (24)

1

X - Xik = 0

X - X kj = 0, (25)

X-ai

aij + aijk (X - ak)2

- X - Xijk = 0, (27)

■ - X - Xk = 0,

(26)

+

X - ak     X - a j     X - ai

--ail-2-x-x k = 0,

(X-ak)2

aik - aijk (X - aj)2

X-X j = 0,

(28) (29)

1

akj + aijk

(X

ai)2

- x - xi = 0,

aij + aijk aik + aijk + akj + aijk + x = 0 (X - ak)2    (X - aj)2    (X - ai)2 '

Из (23) видно, что

1

0, Xij > 0,

следовательно,

Из (25) и (33) следует, что

Из (30) и (34) следует, что Предположим, будто бы

X-ak

x< 0. xkj > 0 akj = 0. xi > 0, ai = 0.

aj > 0, xj = 0. Тогда с учетом (21) выражение (27) примет вид

Xij

a

X(X - aj)

- Xijk = 0.

Так как то из (37) следует

Из (29) и (37) выводим

Xijk > 0,

Xij > 0, aijk = 0.

x

aik + aijk (X - aj)2'

Из (31) в соответствии с (34), (39), (40) получаем

aijk     - aijk (X - ak)2 X2

Страницы:
1  2 


Похожие статьи

А А Федоров, Ю В Лопухин, А Ю Скобликов - Задание метрики в задачах классификации объектов различной природы