5. Расстояние между списками

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

Пусть имеется два списка.

Xi=xi1,xi2,...xin

Xj=xj1,xj2,...,xjn.

Коэффициент сравнения определяется следующим образом:

1 при xil>xik D(i,l,k)= -1 при xil<xik

0 при xil=xik где l<k;

Расстояние по Кендалу вычисляется:

d(Xi,Xj)=1-2/(n'(n-1))E D(i,l,k)*D(j,l,k)

Рассмотрим пример:

Х1=0.5,1,2,

Х2=1,3,8.

В соответствии с приведенными выше формулами имеем: D(i,1,2)= -1 D(i,1,3)= -1 D(i,2,3)= -1 D(j,1,2)= -1

D(j,1,3)= -1

D(j,2,3)=-1 d(Xi,Xj)=1 -2/(3*(3-1 ))*[(-1)*(-1 )]+[(-1)*(-1 )]+[(-1 )*(-1)]]=0

Если вектора упорядочены однотипно, то Е D(i, j, k)*D(j,j,k) равно числу сочетаний из n по два и равно n*(n-1)/2.

Тогда D(i,k,l)=1-2/(n*(n-1))*n*(n-1)/2= 1 - 1=0.

Если компоненты векторов упорядочены в противоположном порядке:

Е D(i, j, k)*D(j, j, k)= - n*(n-1)/2 и D(i,k,l)=1+2/(n*(n-1))*n*(n-1)/2=1+1=2.

Для сопоставления векторов, компоненты которых выражаются не числами, а некоторыми понятиями, можно использовать отношение порядка. Так, если записано а<b, то это означает, что а появляется раньше чем b, b идет вслед за а или под <

подвести иную семантику: например для последовательности:

Хk=большое, красивое, холодное, безобразное, огромное

D(k,1,2)=0; D(k,1,3)=0;

D(k,1,4)=0; D(k,1,5)=-1;

D(k,2,3)=0; D(k,2,4)=1; D(k,2,5)=0; D(k,3,4)=0; D(k.3,5)=0; D(k,4,5)=0;

6. Определение расстояния между списками различной длины

Пусть заданы два списка Xi и Xj:

Xi=xi1, xi2,...,xin и Xj=xj1,xj2,...,xjm

В общем случае n и m не равны друг другу. Очевидно, что одна последовательность может быть преобразована в другую последовательность с использованием следующих операций:

- подстановки xil->xjk ; замена 1-го элемента i последовательности на k элемент j последовательности.

- уничтожения xil->^{^} ; замена 1-го элемента на пустой символ.

- создание ^{^}->xjk ;создание элемента равного xjk Преобразования списка производится последовательно слева направо.

Например, преобразование списка a,b,c,d,e в список f,g,h,i,g,k может быть выполнено за 7 шагов (первоначально l=0,k=0):

1. замена а на f; l =1,k=1;

2. замена b на g; l =2,k=2;

3. уничтожение с; , l =3,k=2;

4. замена d на h; l =4,k=3;

5. создание i; l =4,k=4;

6. замена е на g; l =5,k=5;

7. создание k. l =5,k=6;

l -номер текущего символа в первой строке; k-номер текущего символа во второй строке.

Можно заметить, что значения l и k при выполнении одного шага преобразования изменяют свои значения в зависимости от вида преобразования:

- при замене: увеличиваются l и k на 1; .

- при удалении: увеличивается l на 1, a k не изменяется;

- при создании: l не изменяется, a k увеличивается на 1. Каждому преобразованию соответствует своя цена. Для оценки расстояния между списками вводят понятие полной цены последовательности преобразований, как наименьшей из всех цен, которую необходимо уплатить при переходе от исходного списка к конечному. Расстояние, соответствующее полной цене является минимальным.