dtw  R Documentation 
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) ## S3 method for class 'dtw' print(x, ...)
x 
query vector or local cost matrix 
y 
reference vector, or NULL if 
dist.method 
pointwise (local) distance function to use. See

step.pattern 
a stepPattern object describing the local warping steps
allowed with their cost (see 
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 openended alignments 
... 
additional arguments, passed to 
d 
an arbitrary R object 
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:
if dist.method
is a string, x
and y
are passed to the proxy::dist()
function in package proxy with the method given;
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;
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"
Socalled Itakura parallelogram
window.type
can also be an userdefined windowing function. See
dtwWindowingFunctions()
for all available windowing functions,
details on userdefined 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.
Openended alignment, i.e. semiunconstrained alignment, can be selected via
the open.end
switch. Openend 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,
openbegin is enabled via open.begin
; it makes sense when
open.end
is also enabled (subsequence finding). Subsequence
alignments are similar e.g. to UE21 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
.
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 multistep 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.
Cost matrices (both input and output) have query elements arranged rowwise (first index), and reference elements columnwise (second index). They print according to the usual convention, with indexes increasing down and rightwards. Many DTW papers and tutorials show matrices according to plotlike conventions, i.e. reference index growing upwards. This may be confusing.
Toni Giorgino
Toni Giorgino. Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 124. doi: 10.18637/jss.v031.i07
Tormene, P.; Giorgino, T.; Quaglini, S. & Stefanelli, M. Matching incomplete time series with dynamic time warping: an algorithm and an application to poststroke rehabilitation. Artif Intell Med, 2009, 45, 1134. doi: 10.1016/j.artmed.2008.11.007
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. 4349, Feb 1978. doi: 10.1109/TASSP.1978.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, 560563 doi: 10.1109/ICPR.2006.467
Sakoe, H. Twolevel DPmatchingâ€“A dynamic programmingbased pattern matching algorithm for connected word recognition Acoustics, Speech, and Signal Processing, IEEE Transactions on, 1979, 27, 588595 doi: 10.1109/TASSP.1979.1163310
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), 575582. doi: 10.1109/TASSP.1978.1163164
Muller M. Dynamic Time Warping in Information Retrieval for Music and Motion. Springer Berlin Heidelberg; 2007. p. 6984. doi: 10.1007/9783540740483_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.
## 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 multiplevalued ## Equivalent to: plot(alignment,type="alignment") plot(alignment$index1,alignment$index2,main="Warping function"); ## Confirm: 25 samples offdiagonal alignment lines(1:10025,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 inversewarped 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 handcheckable 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 usersupplied local # cost matrix da<dtw(ldist,step=asymmetric); # Also compute the asymmetric plot(ds$index1,ds$index2,pch=3); # Symmetric: alignment follows # the lowdistance marked path points(da$index1,da$index2,col="red"); # Asymmetric: visiting # 1 is required twice ds$distance; da$distance;
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.