This section covers works related to Dynamic Time Warping for time series.
Note. In tslearn
, such time series would be represented as arrays of
respective
shapes (n, p)
and (m, p)
and DTW can be computed using the following code:
Dynamic Time Warping (DTW) (Sakoe & Chiba, 1978) is a similarity measure between time series. Consider two time series x and x′ of respective lengths n and m. Here, all elements xi and x′j are assumed to lie in the same p-dimensional space and the exact timestamps at which observations occur are disregarded: only their ordering matters.
Optimization Problem
In the following, a path π of length K is a sequence of K index pairs ((i0,j0),…,(iK−1,jK−1)).
DTW between x and x′ is formulated as the following optimization problem:
DTW(x,x′)=minwhere \mathcal{A}(\mathbf{x}, \mathbf{x}^\prime) is the set of all admissible paths, i.e. the set of paths \pi such that:
- \pi is a sequence [\pi_0, \dots , \pi_{K-1}] of index pairs \pi_k = (i_k, j_k) with 0 \leq i_k < n and 0 \leq j_k < m
- \pi_0 = (0, 0) and \pi_{K-1} = (n - 1, m - 1)
for all k > 0 , \pi_k = (i_k, j_k) is related to \pi_{k-1} = (i_{k-1}, j_{k-1}) as follows:
- i_{k-1} \leq i_k \leq i_{k-1} + 1
- j_{k-1} \leq j_k \leq j_{k-1} + 1
Here, a path can be seen as a temporal alignment of time series and the optimal path is such that Euclidean distance between aligned (ie. resampled) time series is minimal.
The following image exhibits the DTW path (in white) for a given pair of time series, on top of the cross-similarity matrix that stores d(x_i, {x}^\prime_j) values.
Note. Code to produce such visualization is available in tslearn
's
Gallery of
examples.
Properties
Dynamic Time Warping holds the following properties:
- \forall \mathbf{x}, \mathbf{x}^\prime, DTW(\mathbf{x}, \mathbf{x}^\prime) \geq 0
- \forall \mathbf{x}, DTW(\mathbf{x}, \mathbf{x}) = 0
However, mathematically speaking, DTW is not a valid metric since it satisfies neither the triangular inequality nor the identity of indiscernibles.
Setting additional constraints
The set of temporal deformations to which DTW is invariant can be reduced by imposing additional constraints on the set of acceptable paths. Such constraints typically consist in forcing paths to stay close to the diagonal.
The Sakoe-Chiba band is parametrized by a radius r (number of off-diagonal elements to consider, also called warping window size sometimes), as illustrated below:
The Itakura parallelogram sets a maximum slope s for alignment paths, which leads to a parallelogram-shaped constraint: