Искажение времени Редактировать расстояние

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти вопросы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения ) В этой статье недостаточно контекста для тех, кто не знаком с предметом . Пожалуйста, помогите улучшить статью , предоставив читателю больше контекста . ( ноябрь 2016 г. ) ( узнайте, как и когда удалять это шаблонное сообщение ) Эта статья может быть слишком технической для большинства читателей . Пожалуйста , помогите улучшить его , чтобы он был понятен неспециалистам , не удаляя технические детали. ( ноябрь 2016 г. ) ( узнайте, как и когда удалять это шаблонное сообщение ) Эта статья является сиротой , так как никакие другие статьи не ссылаются на нее . Пожалуйста , введите ссылки на эту страницу из связанных статей ; попробуйте инструмент «Найти ссылку» для предложений. ( сентябрь 2016 г. ) ( Узнайте, как и когда удалить это шаблонное сообщение )

Time Warp Edit Distance (TWED) — это мера сходства (или несходства) для дискретных временных рядов, совпадающих с « эластичностью » времени . По сравнению с другими мерами расстояния (например, DTW ( динамическая деформация времени ) или LCS ( самая длинная общая проблема подпоследовательности )), TWED является метрикой . Его вычислительная временная сложность составляет , но может быть значительно уменьшена в некоторых конкретных ситуациях с помощью коридора для уменьшения пространства поиска. Его сложность пространства памяти может быть уменьшена до . Впервые он был предложен в 2009 г. П.-Ф. Марто.${\ Displaystyle О (п ^ {2})}$ ${\ Displaystyle О (п)}$

Определение

${\ displaystyle \ delta _ {\ lambda, \ nu} (A_ {1} ^ {p}, B_ {1} ^ {q}) = Min {\ begin {case} \ delta _ {\ lambda, \ nu} (A_ {1} ^ {p-1}, B_ {1} ^ {q}) + \ Gamma (a_ {p} ^ {'} \ to \ Lambda) & {\ rm {delete \ in \ A}} \\\ дельта _ {\ lambda, \ nu} (A_ {1} ^ {p-1}, B_ {1} ^ {q-1}) + \ Gamma (a_ {p} ^ {'} \ to b_ {q} ^ {'}) & {\ rm {совпадение \ или \ замена}} \\\ delta _ {\ lambda, \ nu} (A_ {1} ^ {p}, B_ {1} ^ {q- 1})+\Gamma (\Lambda \to b_{q}^{'})&{\rm {delete\ in\ B}}\end{cases}}}$
в то время как

${\displaystyle \Gamma (\alpha _{p}^{'}\to \Lambda )=d_{LP}(a_{p}^{'},a_{p-1}^{'})+\nu \cdot (t_{a_{p}}-t_{a_{p-1}})+\lambda }$
${\displaystyle \Gamma (\alpha _{p}^{'}\to b_{q}^{'})=d_{LP}(a_{p}^{'},b_{q}^{'})+d_{LP}(a_{p-1}^{'},b_{q-1}^{'})+\nu \cdot (|t_{a_{p}}-t_{b_{q}}|+|t_{a_{p-1}}-t_{b_{q-1}}|)}$
${\displaystyle \Gamma (\Lambda \to b_{q}^{'})=d_{LP}(b_{p}^{'},b_{p-1}^{'})+\nu \cdot (t_{b_{q}}-t_{b_{q-1}})+\lambda }$

Принимая во внимание, что рекурсия инициализируется как: with${\displaystyle \delta _{\lambda ,\nu }}$
${\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{0})=0,}$
${\displaystyle \delta _{\lambda ,\nu }(A_{1}^{0},B_{1}^{j})=\infty \ {\rm {{for\ }j\geq 1}}}$
${\displaystyle \delta _{\lambda ,\nu }(A_{1}^{i},B_{1}^{0})=\infty \ {\rm {{for\ }i\geq 1}}}$
${\displaystyle a'_{0}=b'_{0}=0}$

Реализации

Реализация алгоритма TWED на C с оболочкой Python доступна по ссылке ^{[1] .}

Реализация TWED на R была интегрирована в TraMineR, пакет R для интеллектуального анализа данных, описания и визуализации последовательностей состояний или событий и, в более общем плане, дискретных данных последовательности . ^[2]

Кроме того, cuTWED представляет собой CUDA -ускоренную реализацию TWED, в которой используется улучшенный алгоритм, разработанный Г. Райтом (2020). Этот метод линейен в памяти и массово распараллелен. cuTWED написан на CUDA C/ C++ , поставляется с привязками Python, а также включает привязки Python для эталонной реализации Marteau на C.

питон

импортировать  numpy  как  npdef  dlp ( A ,  B ,  p = 2 ):  стоимость  =  np . сумма ( np . мощность ( np . абс ( A  -  B ),  p ))  вернуть  np . мощность ( стоимость ,  1  /  п )def  twed ( A ,  timeSA ,  B ,  timeSB ,  nu ,  _lambda ):  # [distance, DP] = TWED( A, timeSA, B, timeSB, lambda, nu )  # Вычислить расстояние редактирования Time Warp (TWED) для данного временного ряда A и B  #  # A := Временной ряд A (например, [ 10 2 30 4])  # timeSA := Отметка времени временного ряда A (например, 1:4)  # B := Временной ряд B  # timeSB := Отметка времени временной ряд B  # lambda := Штраф за операцию удаления  # nu := Параметр эластичности - nu >=0, необходимый для измерения расстояния  # Ссылка: # Марто, П.; Ф. (2009). «Расстояние редактирования временной деформации с корректировкой жесткости для сопоставления временных рядов» .  # IEEE Transactions по анализу образов и машинному интеллекту. 31 (2): 306–318. arXiv:cs/0703033  # http://people.irisa.fr/Pierre-Francois.Marteau/ # Проверяем входные аргументы  if  len ( A )  !=  len ( timeSA ):  print ( "Длина A не равна длине timeSA" )  return  None ,  None if  len ( B )  !=  len ( timeSB ):  print ( «Длина B не равна длине timeSB» )  return  None ,  None если  nu  <  0 :  напечатать ( "nu отрицательно" )  вернуть  None ,  None # Добавить отступ  A  =  np . массив ([ 0 ]  +  список ( A ))  timeSA  =  np . массив ([ 0 ]  +  список ( timeSA ))  B  =  np . массив ([ 0 ]  +  список ( B ))  timeSB  =  np . массив ([ 0 ]  +  список ( timeSB )) n  =  len ( A )  m  =  len ( B )  # Динамическое программирование  DP  =  np . нули (( п ,  м )) # Инициализировать матрицу DP и установить первую строку и столбец на бесконечность  DP [ 0 ,  :]  =  np . inf  DP [:,  0 ]  =  np . инф  ДП [ 0 ,  0 ]  =  0 # Вычислить минимальную стоимость  для  i  в  диапазоне ( 1 ,  n ):  для  j  в  диапазоне ( 1 ,  m ):  # Вычислить и сохранить стоимость различных операций  C  =  np . единицы (( 3 ,  1 ))  *  np . inf  # Удаление в A  C [ 0 ]  =  (  DP [ i  -  1 ,  j ]  +  dlp ( A[ i  -  1 ],  A [ i ])  +  nu  *  ( timeSA [ i ]  -  timeSA [ i  -  1 ])  +  _lambda  )  # Удаление в B  C [ 1 ]  =  (  DP [ i ,  j  -  1 ]  +  dlp ( В [ j  -  1 ],  B [ j ])  +  ню  * ( timeSB [ j ]  -  timeSB [ j  -  1 ])  +  _lambda  )  # Хранить точки данных в обоих временных рядах  C [ 2 ]  =  (  DP [ i  -  1 ,  j  -  1 ]  +  dlp ( A [ i ],  B [ j ])  +  dlp ( A [ i  -  1 ],  B [ j  -  1])  +  nu  *  ( abs ( timeSA [ i ]  -  timeSB [ j ])  +  abs ( timeSA [ i  -  1 ]  -  timeSB [ j  -  1 ]))  )  # Выбираем операцию с минимальной стоимостью и обновляем DP Matrix  DP [ я ,  j ] знак  равно  нп . минимальное ( C )  расстояние  =  DP [ n  - 1 ,  м  -  1 ]  дальность возврата  , ДП 

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

def  backtracking ( DP ):  # [best_path ] = BACKTRACKING ( DP )  # Вычислить наиболее экономичный путь  # DP := матрица DP функции TWED х  =  нп . форма ( ДП )  я  =  х [ 0 ]  -  1  j  =  х [ 1 ]  -  1 # Индексы путей сохраняются в обратном направлении  # path = np.ones((i + j, 2 )) * np.inf;  лучший_путь  =  [] steps  =  0  , в то время как  i  !=  0  или  j  !=  0 :  best_path . добавить (( я  -  1 ,  j  -  1 )) С  =  нп . единицы (( 3 ,  1 ))  *  np . инф # Сохранить точки данных в обоих временных рядах  C [ 0 ]  =  DP [ i-  1  , j  -  1  ] #  Удаление в A  C [ 1 ]  =  DP [ i-  1  , j  ] #  Удаление в B  C [ 2 ]  =  DP [ я ,  дж  -  1 ] # Найдите индекс наименьшей стоимости  idx  =  np . аргмин ( С ) if  idx  ==  0 :  # Сохранить точки данных в обоих временных рядах  i  =  i  -  1  j  =  j  -  1  elif  idx  ==  1 :  # Удаление в A  i  =  i  -  1  j  =  j  else :  # Удаление в B  i  =  i  j  =  j  -  1  шагов  =  шагов  +  1 лучший_путь . добавить (( я  -  1 ,  j  -  1 )) лучший_путь . reverse ()  вернуть  лучший_путь [ 1 :]

МАТЛАБ

функция [расстояние, DP] = twed ( A, timeSA, B, timeSB, lambda, nu )  % [расстояние, DP] = TWED( A, время SA, B, время SB, лямбда, nu ) % Вычислить расстояние редактирования Time Warp (TWED) для заданных временных рядов A и B % % A := Временной ряд A (например, [10 2 30 4]) % timeSA := Отметка времени временного ряда A (например, 1:4) % B := Временной ряд B % timeSB := Отметка времени временного ряда B % lambda := Штраф за операцию удаления % nu := Параметр эластичности - nu >=0 требуется для измерения расстояния % % Код: П.-Ф. Марто - http://people.irisa.fr/Pierre-Francois.Marteau/  % Проверить, являются ли входные аргументы если длина ( A ) ~= длина ( timeSA )    предупреждение ( «Длина A не равна длине timeSA» ) возвращение конец  если длина ( B ) ~= длина ( timeSB )    предупреждение ( «Длина B не равна длине timeSB» ) возвращение конец  если ню < 0    предупреждение ( 'nu отрицательное' ) возвращение конец % Добавить отступ А = [ 0 А ];    время СА = [ 0 время СА ];    В = [ 0 В ];    времяSB = [ 0 времяSB ];     % Динамическое программирование DP = нули ( длина ( A ), длина ( B ));     % Инициализировать матрицу DP и установить первую строку и столбец на бесконечность ДП ( 1 , :) = инф ;    ДП (:, 1 ) = инф ;    ДП ( 1 , 1 ) = 0 ;     n = длина ( timeSA );   m = длина ( timeSB );   % Вычислить минимальную стоимость для я = 2 : п    для j = 2 : м    стоимость = Dlp ( A ( i ), B ( j ));     % Рассчитать и сохранить стоимость различных операций C = единицы ( 3 , 1 ) * inf ;       % удаление в A C ( 1 ) = DP ( i - 1 , j ) + Dlp ( A ( i - 1 ), A ( i ) ) + nu * ( timeSA ( i ) -timeSA ( i - 1 )) + лямбда ;                     % удаления в B C ( 2 ) = DP ( i , j - 1 ) + Dlp ( B ( j - 1 ), B ( j ) ) + nu * ( timeSB ( j ) -timeSB ( j - 1 )) + лямбда ;                     % Сохранить точки данных в обоих временных рядах C ( 3 ) = DP ( i - 1 , j - 1 ) + Dlp ( A ( i ), B ( j )) + Dlp ( A ( i - 1 ), B ( j - 1 )) + ...                    nu * ( абс ( время СА ( i ) - время SB ( j )) + абс ( время СА ( i - 1 ) - время SB ( j - 1 )));              % Выбрать операцию с минимальной стоимостью и обновить матрицу DP DP ( i , j ) = мин ( С );    конец конец  расстояние = DP ( n , м );     % Функция для расчета евклидова расстояния функция  [стоимость] = Dlp ( A, B )   стоимость = sqrt ( сумма (( A - B ) .^ 2 , 2 ));        конец конец

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

функция  [путь] = поиск с возвратом ( DP )   % [ путь ] = ОБРАТНЫЙ ОТСЛЕЖИВАНИЕ ( DP ) % Вычислить наиболее экономичный путь % DP := матрица DP функции TWED  х = размер ( DP );   я = х ( 1 );   j = х ( 2 );    % Индексы путей сохраняются в обратном направлении путь = единицы ( я + j , 2 ) * Inf ;         шаги = 1 ;   в то время как ( я ~= 1 || j ~= 1 )        путь ( шаги , :) = [ i ; дж ];      C = единицы ( 3 , 1 ) * inf ;       % Сохранить точки данных в обоих временных рядах C ( 1 ) = DP ( i- 1 , j - 1 ) ;        % удаление в A C ( 2 ) = DP ( i- 1 , j ) ;      % удаления в B C ( 3 ) = DP ( i , j- 1 ) ;       % Найти индекс для самой низкой стоимости [ ~ , idx ] = мин ( C );     переключить idx  случай 1  % Сохранить точки данных в обоих временных рядах я = я - 1 ;     дж = дж - 1 ;     случай 2  % удаление в A я = я - 1 ;     дж = дж ;   случай 3  % удаления в B я = я ;   дж = дж - 1 ;     конец шаги = шаги + 1 ;     конец путь ( шаги , :) = [ i j ];      % Путь рассчитан в обратном направлении. путь = путь ( 1 : шаги , :);    путь = путь ( конец : - 1 : 1 , :);      конец

использованная литература

• Марто, П.; Ф. (2009). «Расстояние редактирования временной деформации с корректировкой жесткости для сопоставления временных рядов» . IEEE Transactions по анализу образов и машинному интеллекту . 31 (2): 306–318. архив : cs/ 0703033 . doi : 10.1109/TPAMI.2008.76 . PMID 19110495 .