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