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

В некоторых задачах сходство между объектами базируется на мере сравнения порядка списков.

Пусть имеется две реализации:

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

l<k.

Расстояние в этом случае вычисляется так:

Если компоненты обоих векторов упорядочены однотипно, то Расстояние между объектами в этом случае равно 0.

Пример: Х₁={0.5, 1, 2}, Х₂={1, 3, 8}.

Тогда расстояние между объектами будет

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

Пусть заданы два списка: m и n могут быть не равны. Задача состоит в нахождении функции, которая выражала бы степень сходства двух списков.

Пример: От ряда АВС перейти к ряду ABDE. Алгоритм перехода включает в себя следующие шаги:

1. сохранить первый и второй символы.

2. Заменить третий символ.

3. Добавить четвертый символ.

Введя пустой символ λ, можно эти три варианта преобразований записать в виде трех операций.

SUB (подстановка)

DES (уничтожение)

CRE (создание)

Каждому преобразованию соответствует своя цена С. Для оценки расстояния между двумя списками вводят понятие полной цены последовательности преобразований как наименьшей из всех возможных цен, которые следует “заплатить” за переход от исходного списка к конечному. Процесс перехода от одного списка к другому может включать в себя три процедуры.

Пусть есть списки Х_i(l) и Х_j(k). Необходимо выполнить преобразование Для перехода от D(l-1, k-1) к D(l,k) l,k – длины списков имеются три возможности.

1. Путем подстановки Х_i(l) и Х_j(k), цена которой соответствует цене SUB(х_il, x_jk) последних элементов в каждом списке.

2. Путем создания последнего элемента в списке j, за что приходится платить цену

3. Если рассмотреть пару Х_i(l-1) и Х_j(k), то цена будет , что соответствует уничтожению последнего элемента в списке i.

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

Х_i = {a,a,b,a,c}; Х_j = {a,b,d}. Тогда, один из возможных путей преобразования следующий

1.

2.

3.

4.

5.

Суммарная цена преобразований равна 2.

15. Метод динамического программирования

Рассмотрим два списка X и Y, состоящие из элементов:

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

Список X называется опорным, а Y – подлежащим сравнению (кандидатом). Количество значений списка X=n, Y=m. В общем случае m не равно n. Например, такая ситуация встречается при записи одного и того же слова, произнесенного с различной скоростью. Аналогичная ситуация возникает при анализе фотоснимков или их частей, выполненных при разных увеличениях. Информационное содержание в каждом из случаев остается неизменным. Таким образом, первая задача состоит в том, чтобы установить оптимальное соответствие между двумя списками. Рассмотрим схему этого процесса на рис. 3.2.

Согласование опорного и предъявляемого сигналов выполняется с помощью функции g, связывающей l и k, l=g(k). Примем g(1)=1; g(m)=n. В качестве первого приближения можно принять линейную зависимость Более качественный способ согласования можно

представить так , где b(k) – к-ая составляющая

вектора Y, которой соответствует g(k)-я составляющая вектора Х.

Рис. 3.2 – Схема метода динамического программирования

Расстояние между этими составляющими вычисляется по одной из формул для расстояния. Функция g(k) должна обеспечивать возможность минимизации в целом расстояния D_с между двумя списками. После того как оба списка исчерпаны, получают величину D^*, позволяющую оценить нормализованное расстояние между списками: Ранее делается предположение, что D^* дает оптимальный результат. Выражение для D_с означает, что т.е. D_c(l,k) – текущее расстояние, накапливаемое от точки l=k=1 до точки с координатами (k, l) (рис. 3.2).