tslearn.metrics.dtw_limited_warping_length¶

tslearn.metrics.dtw_limited_warping_length(s1, s2, max_length)[source]

Compute Dynamic Time Warping (DTW) similarity measure between (possibly multidimensional) time series under an upper bound constraint on the resulting path length and return the similarity cost.

DTW is computed as the Euclidean distance between aligned time series, i.e., if $$\pi$$ is the optimal alignment path:

$DTW(X, Y) = \sqrt{\sum_{(i, j) \in \pi} \|X_{i} - Y_{j}\|^2}$

Note that this formula is still valid for the multivariate case.

It is not required that both time series share the same size, but they must be the same dimension. DTW was originally presented in [1]. This constrained-length variant was introduced in [2]. Both bariants are discussed in more details in our dedicated user-guide page

Parameters: s1 A time series. s2 Another time series. max_length : int Maximum allowed warping path length. If greater than len(s1) + len(s2), then it is equivalent to unconstrained DTW. If lower than max(len(s1), len(s2)), no path can be found and a ValueError is raised. float Similarity score

dtw
Get the similarity score for DTW
dtw_path_limited_warping_length
Get both the warping path and the similarity score for DTW with limited warping path length

References

 [1] H. Sakoe, S. Chiba, “Dynamic programming algorithm optimization for spoken word recognition,” IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 26(1), pp. 43–49, 1978.
 [2] Z. Zhang, R. Tavenard, A. Bailly, X. Tang, P. Tang, T. Corpetti Dynamic time warping under limited warping path length. Information Sciences, vol. 393, pp. 91–107, 2017.

Examples

>>> dtw_limited_warping_length([1, 2, 3], [1., 2., 2., 3.], 5)
0.0
>>> dtw_limited_warping_length([1, 2, 3], [1., 2., 2., 3., 4.], 5)
1.0