# dtw: Dynamic Time Warp In dtw: Dynamic Time Warping Algorithms

## Description

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

## Usage

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17``` ```dtw( x, y = NULL, dist.method = "Euclidean", step.pattern = symmetric2, window.type = "none", keep.internals = FALSE, distance.only = FALSE, open.end = FALSE, open.begin = FALSE, ... ) is.dtw(d) ## S3 method for class 'dtw' print(x, ...) ```

## Arguments

 `x` query vector or local cost matrix `y` reference vector, or NULL if `x` given as a local cost matrix `dist.method` pointwise (local) distance function to use. See `proxy::dist()` in package proxy `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). `keep.internals` preserve the cumulative cost matrix, inputs, and other internal structures `distance.only` only compute distance (no backtrack, faster) `open.begin, open.end` perform open-ended alignments `...` additional arguments, passed to `window.type` `d` an arbitrary R object

## 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 `proxy::dist()` function in package proxy with the method given;

2. if `dist.method` is a function of two arguments, it invoked repeatedly on all pairs `x[i],y[j]` to build the local cost matrix;

3. multivariate time series and arbitrary distance metrics can be handled by supplying a precomputed local cost matrix. Element `[i,j]` of the local cost 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.

`is.dtw` tests whether the argument is of class `dtw`.

## Value

An object of class `dtw` with the following items:

• `distance` the minimum global distance computed, not normalized.

• `normalizedDistance` distance computed, normalized for path length, if normalization is known for chosen step pattern.

• `N,M` query and reference length

• `call` the function call that created the object

• `index1` matched elements: indices in `x`

• `index2` corresponding mapped indices in `y`

• `stepPattern` the `stepPattern` object used for the computation

• `jmin` last element of reference matched, if `open.end=TRUE`

• `directionMatrix` if `keep.internals=TRUE`, the directions of steps that would be taken at each alignment pair (integers indexing production rules in the chosen step pattern)

• `stepsTaken` the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern)

• `index1s, index2s` same as `index1/2`, excluding intermediate steps for multi-step patterns like `asymmetricP05()`

• `costMatrix` if `keep.internals=TRUE`, the cumulative cost matrix

• `query, reference` if `keep.internals=TRUE` and passed as the `x` and `y` arguments, the query and reference timeseries.

## Note

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.

Toni Giorgino

## References

1. Toni Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 1-24. doi: 10.18637/jss.v031.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. doi: 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. doi: 10.1109/TASSP.1978.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 doi: 10.1109/ICPR.2006.467

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 doi: 10.1109/TASSP.1979.1163310

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. doi: 10.1109/TASSP.1978.1163164

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

`dtwDist()`, for iterating dtw over a set of timeseries; `dtwWindowingFunctions()`, for windowing and global constraints; `stepPattern()`, step patterns and local constraints; `plot.dtw()`, plot methods for DTW objects. To generate a local cost matrix, the functions `proxy::dist()`, `analogue::distance()`, `vegan::vegdist()`, or `outer()` may come handy.
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90``` ```## A noisy sine wave as query idx<-seq(0,6.28,len=100); query<-sin(idx)+runif(100)/10; ## A cosine is for reference; sin and cos are offset by 25 samples reference<-cos(idx) plot(reference); lines(query,col="blue"); ## Find the best match alignment<-dtw(query,reference); ## Display the mapping, AKA warping function - may be multiple-valued ## Equivalent to: plot(alignment,type="alignment") plot(alignment\$index1,alignment\$index2,main="Warping function"); ## Confirm: 25 samples off-diagonal alignment lines(1:100-25,col="red") ######### ## ## Partial alignments are allowed. ## alignmentOBE <- dtw(query[44:88],reference, keep=TRUE,step=asymmetric, open.end=TRUE,open.begin=TRUE); plot(alignmentOBE,type="two",off=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 plot(reference) lines(query[alignment\$index1]~alignment\$index2,col="blue") ## Plot the (unwarped) query and the inverse-warped reference plot(query,type="l",col="blue") points(reference[alignment\$index2]~alignment\$index1) ######### ## ## Contour plots of the cumulative cost matrix ## similar to: plot(alignment,type="density") or ## dtwPlotDensity(alignment) ## See more plots in ?plot.dtw ## ## keep = TRUE so we can look into the cost matrix alignment<-dtw(query,reference,keep=TRUE); contour(alignment\$costMatrix,col=terrain.colors(100),x=1:100,y=1:100, xlab="Query (noisy sine)",ylab="Reference (cosine)"); lines(alignment\$index1,alignment\$index2,col="red",lwd=2); ######### ## ## An hand-checkable example ## ldist<-matrix(1,nrow=6,ncol=6); # Matrix of ones ldist[2,]<-0; ldist[,5]<-0; # Mark a clear path of zeroes ldist[2,5]<-.01; # Forcely cut the corner ds<-dtw(ldist); # DTW with user-supplied local # cost matrix da<-dtw(ldist,step=asymmetric); # Also compute the asymmetric plot(ds\$index1,ds\$index2,pch=3); # Symmetric: alignment follows # the low-distance marked path points(da\$index1,da\$index2,col="red"); # Asymmetric: visiting # 1 is required twice ds\$distance; da\$distance; ```