tslearn.metrics.dtw_path_limited_warping_length

tslearn.metrics.dtw_path_limited_warping_length(s1, s2, max_length, be=None)[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:
s1array-like, shape=(sz1, d) or (sz1,)

A time series. If shape is (sz1,), the time series is assumed to be univariate.

s2array-like, shape=(sz2, d) or (sz2,)

Another time series. If shape is (sz2,), the time series is assumed to be univariate.

max_lengthint

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.

beBackend object or string or None

Backend. If be is an instance of the class NumPyBackend or the string “numpy”, the NumPy backend is used. If be is an instance of the class PyTorchBackend or the string “pytorch”, the PyTorch backend is used. If be is None, the backend is determined by the input arrays. See our dedicated user-guide page for more information.

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)]