Редактировать / расстояние Левенштейна с отметкой времени - разные пути с одинаковой (минимальной) стоимостью - PullRequest
Новая
       10

Редактировать / расстояние Левенштейна с отметкой времени - разные пути с одинаковой (минимальной) стоимостью

2 голосов
/ 11 августа 2011

Я использую расстояние Правка / Левенштейна для измерения сходства между словами.В отличие от самой простой реализации, мои письма имеют временные метки, скажем, в образцах с номерами N = 0,1,2, ...

Проблема, с которой я сталкиваюсь, заключается в том, что я могу найти разные пути вдоль матрицы затрат,заканчиваются одинаковыми (минимальными) затратами, и эти разные пути связаны с разными целевыми строками.Например, если я измерил расстояние между исходной строкой aa и целевой строкой bab и предположил, что исходная строка начинается с отметки времени N = 0, то у меня есть 2 пути с одинаковой стоимостью 2 (одно добавлениеи одна подстановка):

  1. Добавьте b при N = -1, оставьте 1-е a как есть и замените 2-е a на b.
  2. Замените 1-е a на b, оставьте 2-е a без изменений и добавьте b при N = 2.

Выровняйте по временной шкале,эти 2 результата различны: 

Time:    ... -1 0 1 2 3 ...
Source:         a a
Target1:      b a b
Target2:        b a b

Мне нужно знать, когда это произойдет, чтобы я мог выбирать между двумя возможными целями на основе некоторых критериев.Есть ли другой способ, кроме отслеживания пути и отслеживания всех возможных путей, которые приводят к минимальной стоимости?

Я рассмотрел использование Dynamic Time Warp вместо этого, поскольку временная шкала является частью модели в первую очередь, но, похоже, что матрица затрат инициализируется в бесконечность (за исключением записи [0,0]), первый шаг всегда будет соответствовать 1-му кадру цели и 1-му кадру источника, в результате чего цель будет начинаться с той же отметки времени, что и источник.В любом случае, используя DTW, мне все равно приходится отслеживать все пути, ведущие к одинаковой минимальной стоимости.

Любая помощь или идеи приветствуются.

1 Ответ

2 голосов
/ 11 августа 2011

Подумав еще немного о вашей проблеме, немного кажется, что есть недопонимание DTW или Levensthein.Оба алгоритма пытаются сжать и расширить последовательности, чтобы сопоставить их друг с другом.Таким образом, в случае DTW ваш пример будет иметь следующие решения: 

Solution1:
  a a
 /| |
b a b

Solution2:
a a
| |\
b a b

Solution3:
a a
|\|\
b a b

Если вы посмотрите на эти решения, вы заметите, что все они имеют стоимость 2, т.е. во всех случаях 2 b s назначается как.Эти примеры означают, что в первой последовательности одна временная метка сжимается вместе по сравнению со второй последовательностью.Например, в первом решении первые две временные метки b a сжимаются, образуя один временной шаг, соответствующий первому a второй последовательности (вторая последовательность только обратная, третье решение более сложное).DTW предназначен для работы с последовательностями, которые воспроизводятся с разной скоростью в определенных частях, отсюда и аналогия с «искажением времени».

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

Примерно так (предполагая, что str2 является более коротким): 

for i = 0 to length( str1 ) - length( str2 ) do
  shift str2 by i to the left
  calculate number of different position between shifted str2 and str1
done
return i with lowest difference

Предполагая, что вам нужно как смещение, так и деформация(возможно, что-то было добавлено в начало, а временные шаги могут не совпадать), затем рассмотрим подпоследовательность DTW.Для этого вам просто нужно ослабить граничные условия.

Предполагая, что вы индексируете свою строку в единицу вместо нуля, вы можете написать DTW следующим образом: 

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = infinity;
cost( *, 0 ) = infinity;
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

DTW-Cost тогда равна cost( length( str1 ), length( str2 ) ) и ваш путь можно проследить оттуда.Для подпоследовательности DTW вы просто изменяете это: 

diff( x, y ) = 1 if str1 at x != str2 at x 
               0 otherwise

cost( 0, 0 ) = 0;
cost( 0, * ) = 0;
cost( *, 0 ) = infinity; // yes this is correct and needed
cost( x, y ) = min( cost( x-1, y-1 ), cost( x-1, y ), cost( y, y-1) ) + diff( x, y )

Затем вы выбираете свою стоимость DTW как min( cost( x, length( str2 ) ) и прослеживаете от argmin( cost( x, length( str2 ) ).Это предполагает, что вы знаете, что одна строка является подстрокой другой.Если вы этого не знаете, и у обоих может быть только общая искривленная середина, вам придется выполнить частичное сопоставление, которое, насколько я знаю, все еще остается открытой темой исследования, поскольку нужно выбрать понятие «оптимальности», которое не может четкобыть определенным.

...