Dynamic Time Warp
Compute Dynamic Time Warp and find optimal alignment between two time series.
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) "print"(x,...)
- query vector or local cost matrix
- reference vector, unused if
xgiven as cost matrix
- pointwise (local) distance function to use. See
distin package proxy
- a stepPattern object describing the
local warping steps allowed with their cost (see
- windowing function. Character: "none", "itakura", "sakoechiba", "slantedband", or a function (see details).
- open.begin, open.end
- perform open-ended alignments
- preserve the cumulative cost matrix, inputs, and other internal structures
- only compute distance (no backtrack, faster)
- an arbitrary R object
- additional arguments, passed to
The function performs Dynamic Time Warp (DTW) and computes the optimal alignment between two time series
y, given as
numeric vectors. The ``optimal'' alignment minimizes the sum of
distances between aligned elements. Lengths of
The local distance between elements of
x (query) and
(reference) can be computed in one of the following ways:
dist.methodis a string,
yare passed to the
distfunction in package proxy with the method given;
dist.methodis a function of two arguments, it invoked repeatedly on all pairs
x[i],y[j]to build the local cost matrix;
- 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
y[j]. The distance matrix has therefore
m=length(y)columns (see note below).
Several common variants of the DTW recursion are supported via the
step.patternargument, which defaults to
symmetric2. Step patterns are commonly used to locally constrain the slope of the alignment function. See
Windowing enforces a global constraint on the envelope of the warping path. It is selected by passing a string or function to the
window.typeargument. 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.typecan also be an user-defined windowing function. See
dtwWindowingFunctionsfor 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
Open-ended alignment, i.e. semi-unconstrained alignment, can be selected via the
open.endswitch. 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.endis 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=TRUEswitch, which skips the backtracking step. The output object will then lack the
is.dtwtests whether the argument is of class
An object of class
- the minimum global distance computed, not normalized.
- distance computed, normalized for path length, if normalization is known for chosen step pattern.
- query and reference length
- the function call that created the object
- matched elements: indices in
- corresponding mapped indices in
stepPatternobject used for the computation
- last element of reference matched, 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)
- 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
keep.internals=TRUE, the cumulative cost matrix
- query, reference
keep.internals=TRUEand passed as the
yarguments, the query and reference timeseries.
dtwwith the following items:
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.
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/ 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 Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing], IEEE Transactions on , vol.26, no.1, pp. 43-49, Feb 1978. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1163055 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 Sakoe, H. Two-level DP-matching--A dynamic programming-based pattern matching algorithm for connected word recognition Acoustics, Speech, and Signal Processing [see also IEEE Transactions on Signal Processing], IEEE Transactions on, 1979, 27, 588-595 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. 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
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 distance matrix, the functions
dist in package proxy,
distance in package analogue,
outer may come handy.
## 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;