# dtw¶

dtw.dtw(x, y=None, dist_method='euclidean', step_pattern='symmetric2', window_type=None, window_args={}, keep_internals=False, distance_only=False, open_end=False, open_begin=False)

Compute Dynamic Time Warp and find optimal alignment between two time series.

Details

The function performs Dynamic Time Warp (DTW) and computes the optimal alignment between two time series `x` and `y`, given as numeric vectors. The “optimal” alignment minimizes the sum of distances between aligned elements. Lengths of `x` and `y` may differ.

The local distance between elements of `x` (query) and `y` (reference) can be computed in one of the following ways:

1. if `dist_method` is a string, `x` and `y` are passed to the scipy.spatial.distance.cdist function with the method given;

2. multivariate time series and arbitrary distance metrics can be handled by supplying a local-distance matrix. Element `[i,j]` of the local-distance matrix is understood as the distance between element `x[i]` and `y[j]`. The distance matrix has therefore `n=length(x)` rows and `m=length(y)` columns (see note below).

Several common variants of the DTW recursion are supported via the `step_pattern` argument, which defaults to `symmetric2`. Step patterns are commonly used to locally constrain the slope of the alignment function. See [stepPattern()] for details.

Windowing enforces a global constraint on the envelope of the warping path. It is selected by passing a string or function to the `window_type` argument. Commonly used windows are (abbreviations allowed):

• `"none"` No windowing (default)

• `"sakoechiba"` A band around main diagonal

• `"slantedband"` A band around slanted diagonal

• `"itakura"` So-called Itakura parallelogram

`window_type` can also be an user-defined windowing function. See [dtwWindowingFunctions()] for all available windowing functions, details on user-defined windowing, and a discussion of the (mis)naming of the “Itakura” parallelogram as a global constraint. Some windowing functions may require parameters, such as the `window_size` argument.

Open-ended alignment, i_e. semi-unconstrained alignment, can be selected via the `open_end` switch. Open-end DTW computes the alignment which best matches all of the query with a leading part of the reference. This is proposed e_g. by Mori (2006), Sakoe (1979) and others. Similarly, open-begin is enabled via `open_begin`; it makes sense when `open_end` is also enabled (subsequence finding). Subsequence alignments are similar e_g. to UE2-1 algorithm by Rabiner (1978) and others. Please find a review in Tormene et al. (2009).

If the warping function is not required, computation can be sped up enabling the `distance_only=True` switch, which skips the backtracking step. The output object will then lack the `index{1,2,1s,2s}` and `stepsTaken` fields.

Parameters:
• x – query vector or local cost matrix

• y – reference vector, unused if x given as cost matrix

• dist_method – pointwise (local) distance function to use.

• step_pattern – a stepPattern object describing the local warping steps allowed with their cost (see [stepPattern()])

• window_type – windowing function. Character: “none”, “itakura”, “sakoechiba”, “slantedband”, or a function (see details).

• open_begin – perform open-ended alignments

• open_end – perform open-ended alignments

• keep_internals – preserve the cumulative cost matrix, inputs, and other internal structures

• distance_only – only compute distance (no backtrack, faster)

• window_args – additional arguments, passed to the windowing function

Return type:

An object of class `DTW`. See docs for the corresponding properties.

Notes

Cost matrices (both input and output) have query elements arranged row-wise (first index), and reference elements column-wise (second index). They print according to the usual convention, with indexes increasing down- and rightwards. Many DTW papers and tutorials show matrices according to plot-like conventions, i_e. reference index growing upwards. This may be confusing.

A fast compiled version of the function is normally used. Should it be unavailable, the interpreted equivalent will be used as a fall-back with a warning.

References

1. Toni Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 1-24. http://www.jstatsoft.org/v31/i07/

2. Tormene, P.; Giorgino, T.; Quaglini, S. & Stefanelli, M. Matching incomplete time series with dynamic time warping: an algorithm and an application to post-stroke rehabilitation. Artif Intell Med, 2009, 45, 11-34. http://dx.doi.org/10.1016/j.artmed.2008.11.007

3. Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, Acoustics, Speech, and Signal Processing, IEEE Transactions on , vol.26, no.1, pp. 43-49, Feb 1978. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163055

4. Mori, A.; Uchida, S.; Kurazume, R.; Taniguchi, R.; Hasegawa, T. & Sakoe, H. Early Recognition and Prediction of Gestures Proc. 18th International Conference on Pattern Recognition ICPR 2006, 2006, 3, 560-563

5. Sakoe, H. Two-level DP-matching–A dynamic programming-based pattern matching algorithm for connected word recognition Acoustics, Speech, and Signal Processing, IEEE Transactions on, 1979, 27, 588-595

6. Rabiner L, Rosenberg A, Levinson S (1978). Considerations in dynamic time warping algorithms for discrete word recognition. IEEE Trans. Acoust., Speech, Signal Process., 26(6), 575-582. ISSN 0096-3518.

7. Muller M. Dynamic Time Warping in Information Retrieval for Music and Motion. Springer Berlin Heidelberg; 2007. p. 69-84. http://link.springer.com/chapter/10.1007/978-3-540-74048-3_4

Examples

```>>> import numpy as np
>>> from dtw import *
```

A noisy sine wave as query

```>>> idx = np.linspace(0,6.28,num=100)
>>> query = np.sin(idx) + np.random.uniform(size=100)/10.0
```

A cosine is for reference; sin and cos are offset by 25 samples

```>>> reference = np.cos(idx)
```

Find the best match

```>>> alignment = dtw(query,reference)
```

Display the mapping, AKA warping function - may be multiple-valued Equivalent to: plot(alignment,type=”alignment”)

```>>> import matplotlib.pyplot as plt;
... plt.plot(alignment.index1, alignment.index2)
```

Partial alignments are allowed.

```>>> alignmentOBE = dtw(query[44:88], reference,
...                      keep_internals=True,
...                      step_pattern=asymmetric,
...                      open_end=True,open_begin=True)
```
```>>> alignmentOBE.plot(type="twoway",offset=1)
```

Subsetting allows warping and unwarping of timeseries according to the warping curve. See first example below.

Most useful: plot the warped query along with reference

```>>> plt.plot(reference);
... plt.plot(alignment.index2,query[alignment.index1])
```

Plot the (unwarped) query and the inverse-warped reference

```>>> plt.plot(query)
... plt.plot(alignment.index1,reference[alignment.index2])
```

A hand-checkable example

```>>> ldist = np.ones((6,6))                    # Matrix of ones
>>> ldist[1,:] = 0; ldist[:,4] = 0;           # Mark a clear path of zeroes
>>> ldist[1,4] = .01;                         # Forcely cut the corner
```
```>>> ds = dtw(ldist);                          # DTW with user-supplied local
```
```>>> da = dtw(ldist,step_pattern=asymmetric)   # Also compute the asymmetric
```

Symmetric: alignment follows the low-distance marked path

```>>> plt.plot(ds.index1,ds.index2)
```

Asymmetric: visiting 1 is required twice

```>>> plt.plot(da.index1,da.index2,'ro')
```
```>>> ds.distance
2.0
>>> da.distance
2.0
```