tslearn.metrics.dtw_path

tslearn.metrics.dtw_path(s1, s2, global_constraint=None, sakoe_chiba_radius=None, itakura_max_slope=None)[source]

Compute Dynamic Time Warping (DTW) similarity measure between (possibly multidimensional) time series and return both the path and the similarity.

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

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

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] and is discussed in more details in our dedicated user-guide page.

Parameters:
s1

A time series.

s2

Another time series. If not given, self-similarity of dataset1 is returned.

global_constraint : {“itakura”, “sakoe_chiba”} or None (default: None)

Global constraint to restrict admissible paths for DTW.

sakoe_chiba_radius : int or None (default: None)

Radius to be used for Sakoe-Chiba band global constraint. If None and global_constraint is set to “sakoe_chiba”, a radius of 1 is used. If both sakoe_chiba_radius and itakura_max_slope are set, global_constraint is used to infer which constraint to use among the two. In this case, if global_constraint corresponds to no global constraint, a RuntimeWarning is raised and no global constraint is used.

itakura_max_slope : float or None (default: None)

Maximum slope for the Itakura parallelogram constraint. If None and global_constraint is set to “itakura”, a maximum slope of 2. is used. If both sakoe_chiba_radius and itakura_max_slope are set, global_constraint is used to infer which constraint to use among the two. In this case, if global_constraint corresponds to no global constraint, a RuntimeWarning is raised and no global constraint is used.

Returns:
list of integer pairs

Matching path represented as a list of index pairs. In each pair, the first index corresponds to s1 and the second one corresponds to s2

float

Similarity score

See also

dtw
Get only the similarity score for DTW
cdist_dtw
Cross similarity matrix between time series datasets
dtw_path_from_metric
Compute a DTW using a user-defined distance metric

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.

Examples

>>> path, dist = dtw_path([1, 2, 3], [1., 2., 2., 3.])
>>> path
[(0, 0), (1, 1), (1, 2), (2, 3)]
>>> dist
0.0
>>> dtw_path([1, 2, 3], [1., 2., 2., 3., 4.])[1]
1.0

Examples using tslearn.metrics.dtw_path