Time Warp Edit Distance


Time Warp Edit Distance is a distance measure for discrete time series matching with time 'elasticity'. In comparison to other distance measures, or LCS ), TWED is a metric. Its computational time complexity is, but can be drastically reduced in some specific situation by using a corridor to reduce the search space. Its memory space complexity can be reduced to. It was first proposed in 2009 by P.-F. Marteau.

Definition

whereas




Whereas the recursion
is initialized as:







with

Implementations

An implementation of the TWED-Algorithm in C or Matlab can be downloaded from the authors's homepage
A R implementation of TWED has been integrated into the TraMineR, a R-package for mining, describing and visualizing sequences of states or events, and more generally discrete sequence data
Additionally, is a CUDA accelerated implementation of TWED which uses an improved algorithm due to G. Wright. This method is linear in memory and massively parallelized. cuTWED is written in CUDA C/C++, comes with python bindings, and also includes python bindings for Marteau's reference C implementation.
Python

import numpy as np
def Dlp:
cost = np.sum
return np.power
def twed:
# = TWED
# Compute Time Warp Edit Distance for given time series A and B
#
# A := Time series A
# timeSA := Time stamp of time series A
# B := Time series B
# timeSB := Time stamp of time series B
# lambda := Penalty for deletion operation
# nu := Elasticity parameter - nu >=0 needed for distance measure
# Reference :
# Marteau, P.; F.. "Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching".
# IEEE Transactions on Pattern Analysis and Machine Intelligence. 31 : 306–318. arXiv:cs/0703033
# http://people.irisa.fr/Pierre-Francois.Marteau/
# Check if input arguments
if len != len:
print
return None, None
if len != len:
print
return None, None
if nu < 0:
print
return None, None
# Add padding
A = np.array
timeSA = np.array
B = np.array
timeSB = np.array
n = len
m = len
# Dynamical programming
DP = np.zeros)
# Initialize DP Matrix and set first row and column to infinity
DP = np.inf
DP = np.inf
DP = 0
# Compute minimal cost
for i in range:
for j in range:
# Calculate and save cost of various operations
C = np.ones) * np.inf
# Deletion in A
C =
+ nu *
+ _lambda
)
# Deletion in B
C =
+ nu *
+ _lambda
)
# Keep data points in both time series
C =
+ Dlp
+ nu * + abs)
)
# Choose the operation with the minimal cost and update DP Matrix
DP = np.min
distance = DP
return distance, DP

Backtracking, to find the most cost efficient path:

def backtracking:
# = BACKTRACKING
# Compute the most cost efficient path
# DP := DP matrix of the TWED function
x = np.shape
i = x - 1
j = x - 1
# The indices of the paths are save in opposite direction
# path = np.ones) * np.inf;
best_path =
steps = 0
while i != 0 or j != 0:
best_path.append)
C = np.ones) * np.inf
# Keep data points in both time series
C = DP
# Deletion in A
C = DP
# Deletion in B
C = DP
# Find the index for the lowest cost
idx = np.argmin
if idx 0:
# Keep data points in both time series
i = i - 1
j = j - 1
elif idx 1:
# Deletion in A
i = i - 1
j = j
else:
# Deletion in B
i = i
j = j - 1
steps = steps + 1
best_path.append)
best_path.reverse
return best_path

MATLAB

function = twed
% = TWED
% Compute Time Warp Edit Distance for given time series A and B
%
% A := Time series A
% timeSA := Time stamp of time series A
% B := Time series B
% timeSB := Time stamp of time series B
% lambda := Penalty for deletion operation
% nu := Elasticity parameter - nu >=0 needed for distance measure
%
% Code by: P.-F. Marteau - http://people.irisa.fr/Pierre-Francois.Marteau/
% Check if input arguments
if length ~= length
warning
return
end
if length ~= length
warning
return
end
if nu < 0
warning
return
end
% Add padding
A = ;
timeSA = ;
B = ;
timeSB = ;
% Dynamical programming
DP = zeros, length);
% Initialize DP Matrix and set first row and column to infinity
DP = inf;
DP = inf;
DP = 0;
n = length;
m = length;
% Compute minimal cost
for i = 2:n
for j = 2:m
cost = Dlp, B);

% Calculate and save cost of various operations
C = ones * inf;

% Deletion in A
C = DP + Dlp, A) + nu * - timeSA) + lambda;
% Deletion in B
C = DP + Dlp, B) + nu * - timeSB) + lambda;
% Keep data points in both time series
C = DP + Dlp, B) + Dlp, B) +...
nu * - timeSB) + abs - timeSB));

% Choose the operation with the minimal cost and update DP Matrix
DP = min;
end
end
distance = DP;
% Function to calculate euclidean distance
function = Dlp
cost = sqrt);
end
end

Backtracking, to find the most cost efficient path:

function = backtracking
% = BACKTRACKING
% Compute the most cost efficient path
% DP := DP matrix of the TWED function
x = size;
i = x;
j = x;
% The indices of the paths are save in opposite direction
path = ones * Inf;
steps = 1;
while
path = ;

C = ones * inf;

% Keep data points in both time series
C = DP;
% Deletion in A
C = DP;
% Deletion in B
C = DP;

% Find the index for the lowest cost
= min;

switch idx
case 1
% Keep data points in both time series
i = i - 1;
j = j - 1;
case 2
% Deletion in A
i = i - 1;
j = j;
case 3
% Deletion in B
i = i;
j = j - 1;
end
steps = steps + 1;
end
path = ;
% Path was calculated in reversed direction.
path = path;
path = path;
end