tslearn.metrics.dtw_path_limited_warping_length

tslearn.metrics.dtw_path_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 path as well as 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 variants 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.

Returns:
list of integer pairs

Optimal path

float

Similarity score

See also

dtw_limited_warping_length
Get the similarity score for DTW with limited warping path length
dtw_path
Get both the matching path and the similarity score for DTW

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

>>> path, cost = dtw_path_limited_warping_length([1, 2, 3],
...                                              [1., 2., 2., 3.], 5)
>>> cost
0.0
>>> path
[(0, 0), (1, 1), (1, 2), (2, 3)]
>>> path, cost = dtw_path_limited_warping_length([1, 2, 3],
...                                              [1., 2., 2., 3., 4.], 5)
>>> cost
1.0
>>> path
[(0, 0), (1, 1), (1, 2), (2, 3), (2, 4)]