dtw {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, unused if x given as cost matrix |
dist.method |
pointwise (local) distance function to use. See
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). |
open.begin, 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) |
d |
an arbitrary R object |
... |
additional arguments, passed to window.type |
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:
dist.method
is a string, x
and
y
are passed to the dist
function in
package proxy with the method given;
dist.method
is a function of two arguments, it invoked
repeatedly on all pairs x[i],y[j]
to build the local cost matrix;
[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 DTW are supported via the
step.pattern
argument, which defaults to
symmetric2
. Most common step patterns are pre-defined: see
stepPattern
for details.
Open-ended alignment, i.e. semi-unconstrained alignment, can be
selected via the open.end
argument. 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
. Open-begin alignments usually only make sense when
open.end
is enabled, as well (subsequence alignment);
otherwise, it is just as easy to reverse the query
sequence. Subsequence alignments are similar e.g. to UE2-1 algorithm
by Rabiner (1978) and others. Please find a review in Tormene et
al. (2009).
Windowing (enforcing a global constraint) is supported by passing a
string or function window.type
argument. Commonly used windows
are (abbreviations allowed):
"none"
"sakoechiba"
"slantedband"
"itakura"
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.
A native (fast, compiled) version of the function is normally available. If it is not, an interpreted equivalent will be used as a fall-back, with a warning.
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 step patterns) |
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 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.
The partial
argument has been deprecated and renamed
open.end
as of version 1.12.
Toni Giorgino
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
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 URL:
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.
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;