Description Usage Arguments Details Value Note Author(s) References See Also Examples
Compute Dynamic Time Warp and find optimal alignment between two time series.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
x |
query vector or local cost matrix |
y |
reference vector, unused 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). |
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 |
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 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 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.
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 |
index2 |
corresponding mapped indices in |
stepPattern |
the |
jmin |
last element of reference matched, if |
directionMatrix |
if |
stepsTaken |
the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern) |
index1s, index2s |
same as |
costMatrix |
if |
query, reference |
if |
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
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<e2><80><93>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.
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;
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.