Note. This work is a part of Zheng Zhang's PhD thesis. It was performed during Zheng's stay at LETG in 2015-2016. I was not directly involved in the supervision Zheng's PhD thesis.
In this section, we present a method to regularize Dynamic Time Warping by setting constraints on the length of the admissible warping paths (Zhang et al., 2017).
Formulation and Optimization
Note. The method is available in tslearn via:
from tslearn.metrics import dtw_limited_warping_length
cost = dtw_limited_warping_length(
x, x_prime,
max_length
)
As discussed above, a common way to restrict the set of admissible temporal distortions for Dynamic Time Warping consists in forcing paths to stay close to the diagonal through the use of Sakoe-Chiba band or Itakura parallelogram constraints. A limitation of these global constraints is that they completely discard some regions of the alignment matrix a priori (i.e. regardless of the involved data).
To alleviate this limitation, we propose Limited warping path length DTW (LDTW) that adds a path length constraint to the DTW optimization problem such that a path is said admissible for our method iff:
- it is an admissible DTW path;
- its length $K$ is lower or equal to a user-defined bound $K_\text{max}$.
We have proposed an algorithm that stores, at each step $(i, j)$, optimal alignment scores for all admissible alignment path lengths. This gives the general LDTW algorithm:
def ldtw(x, x_prime, max_length):
for i in range(n):
for j in range(m):
dist = d(x[i], x_prime[j]) ** 2
C[i, j, :] = inf # Set infinite cost for non-admissible lengths
# The core difference with DTW is the following line:
for l in admissible_lengths(i, j, max_length):
if i == 0 and j == 0:
C[i, j, l] = dist
else:
C[i, j, l] = dist + min(C[i-1, j, l-1] if i > 0
else inf,
C[i, j-1, l-1] if j > 0
else inf,
C[i-1, j-1, l-1] if (i > 0 and j > 0)
else inf)
return sqrt(min(C[n-1, m-1, :]))
%config InlineBackend.figure_format = 'svg'
import matplotlib.pyplot as plt
import numpy
plt.ion()
def plot_matches(ts0, ts1, path, title):
offset = 4.
fig = plt.figure(figsize=(6, 2))
# Plot matches
for (i, j) in path:
plt.plot([i, j], [ts0[i, 0] + offset, ts1[j, 0] - offset],
color="grey")
# Plot series (with pos/neg offset for visu reasons)
plt.plot(numpy.arange(ts0.shape[0]), ts0.ravel() + offset,
color='b', linestyle='-', marker='o', markersize=1.)
plt.plot(numpy.arange(ts1.shape[0]), ts1.ravel() - offset,
color='r', linestyle='-', marker='o', markersize=1.)
plt.xticks([])
plt.yticks([])
plt.gca().axis("off")
plt.tight_layout()
plt.title(title)
First, one can see in the following figure that the resulting alignments effectively limits the number of singularities in the obtained alignments as compared to DTW:
from tslearn.metrics import dtw_path_limited_warping_length, \
dtw_path
from tslearn.datasets import UCR_UEA_datasets
dataset = UCR_UEA_datasets().load_dataset("CBF")[0]
max_length = 150
path, cost = dtw_path_limited_warping_length(dataset[0],
dataset[1],
max_length)
plot_matches(dataset[0], dataset[1], path, "LDTW matches")
path, cost = dtw_path(dataset[0], dataset[1])
plot_matches(dataset[0], dataset[1], path, "DTW matches")
Moreover, our experiments on UCR Time Series Datasets (Bagnall, Lines, Vickers, & Keogh, 2018) show that this similarity measure, when used in a 1-Nearest Neighbor Classifier, leads to a higher accuracy than other constrained DTW variants (Sakoe-Chiba band and Itakura parallelogram).
References
- Zhang, Z., Tavenard, R., Bailly, A., Tang, X., Tang, P., & Corpetti, T. (2017). Dynamic time warping under limited warping path length. Information Sciences, 393, 91–107.
- Bagnall, A., Lines, J., Vickers, W., & Keogh, E. (2018). The UEA & UCR Time Series Classification Repository. Retrieved from www.timeseriesclassification.com