Raw File
Tip revision: d51529a8ee2827cd8c1bd7c4a9e0265dd0cc72cf authored by Toni Giorgino on 19 September 2022, 16:36:11 UTC
version 1.23-1
Tip revision: d51529a
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/dtw.R
\title{Dynamic Time Warp}
  y = NULL,
  dist.method = "Euclidean",
  step.pattern = symmetric2,
  window.type = "none",
  keep.internals = FALSE,
  distance.only = FALSE,
  open.end = FALSE,
  open.begin = FALSE,


\method{print}{dtw}(x, ...)
\item{x}{query vector \emph{or} local cost matrix}

\item{y}{reference vector, or NULL if \code{x} given as a local cost matrix}

\item{dist.method}{pointwise (local) distance function to use. See
\code{\link[proxy:dist]{proxy::dist()}} in package \CRANpkg{proxy}}

\item{step.pattern}{a stepPattern object describing the local warping steps
allowed with their cost (see \code{\link[=stepPattern]{stepPattern()}})}

\item{window.type}{windowing function. Character: "none", "itakura",
"sakoechiba", "slantedband", or a function (see details).}

\item{keep.internals}{preserve the cumulative cost matrix, inputs, and other
internal structures}

\item{distance.only}{only compute distance (no backtrack, faster)}

\item{open.begin, open.end}{perform open-ended alignments}

\item{...}{additional arguments, passed to \code{window.type}}

\item{d}{an arbitrary R object}
An object of class \code{dtw} with
the following items:
\item \code{distance} the minimum global distance computed, \emph{not} normalized.
\item \code{normalizedDistance} distance computed, \emph{normalized} for path length, if normalization is known for chosen step pattern.
\item \verb{N,M} query and reference length
\item \code{call} the function call that created the object
\item \code{index1} matched elements: indices in \code{x}
\item \code{index2} corresponding mapped indices in \code{y}
\item \code{stepPattern} the \code{stepPattern} object used for the computation
\item \code{jmin} last element of reference matched, if \code{open.end=TRUE}
\item \code{directionMatrix} if \code{keep.internals=TRUE}, the directions of steps that would be taken at each alignment pair (integers indexing  production rules in the chosen step pattern)
\item \code{stepsTaken} the list of steps taken from the beginning to the end of the alignment (integers indexing chosen step pattern)
\item \verb{index1s, index2s} same as \code{index1/2}, excluding intermediate steps for multi-step patterns like \code{\link[=asymmetricP05]{asymmetricP05()}}
\item \code{costMatrix} if \code{keep.internals=TRUE}, the cumulative cost matrix
\item \verb{query, reference} if \code{keep.internals=TRUE} and passed as the \code{x} and \code{y} arguments, the query and reference timeseries.
Compute Dynamic Time Warp and find optimal alignment between two time
The function performs Dynamic Time Warp (DTW) and computes the optimal
alignment between two time series \code{x} and \code{y}, given as numeric
vectors.  The "optimal" alignment minimizes the sum of distances between
aligned elements. Lengths of \code{x} and \code{y} may differ.

The local distance between elements of \code{x} (query) and \code{y}
(reference) can be computed in one of the following ways:
\item if \code{dist.method} is a string, \code{x} and \code{y} are passed to the \code{\link[proxy:dist]{proxy::dist()}} function in package \CRANpkg{proxy} with the method given;
\item if \code{dist.method} is a function of two arguments, it invoked repeatedly on all pairs \verb{x[i],y[j]} to build the local cost matrix;
\item multivariate time series and arbitrary distance metrics can be handled by supplying a precomputed local cost matrix. Element \verb{[i,j]} of the local cost matrix is understood as the distance between element \code{x[i]} and \code{y[j]}. The distance matrix has therefore \code{n=length(x)} rows and \code{m=length(y)} columns (see note below).

Several common variants of the DTW recursion are supported via the
\code{step.pattern} argument, which defaults to \code{symmetric2}. Step
patterns are commonly used to \emph{locally} constrain the slope of the
alignment function. See \code{\link[=stepPattern]{stepPattern()}} for details.

Windowing enforces a \emph{global} constraint on the envelope of the warping
path. It is selected by passing a string or function to the
\code{window.type} argument. Commonly used windows are (abbreviations
\item \code{"none"} No windowing (default)
\item \code{"sakoechiba"} A band around main diagonal
\item \code{"slantedband"} A band around slanted diagonal
\item \code{"itakura"} So-called Itakura parallelogram

\code{window.type} can also be an user-defined windowing function.  See
\code{\link[=dtwWindowingFunctions]{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 \code{window.size} argument.

Open-ended alignment, i.e. semi-unconstrained alignment, can be selected via
the \code{open.end} switch.  Open-end DTW computes the alignment which best
matches all of the query with a \emph{leading part} of the reference. This
is proposed e.g. by Mori (2006), Sakoe (1979) and others. Similarly,
open-begin is enabled via \code{open.begin}; it makes sense when
\code{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 \code{distance.only=TRUE} switch, which skips the backtracking step. The
output object will then lack the \verb{index\{1,2,1s,2s\}} and
\code{stepsTaken} fields.

\code{is.dtw} tests whether the argument is of class \code{dtw}.
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

## A noisy sine wave as query

## A cosine is for reference; sin and cos are offset by 25 samples
plot(reference); lines(query,col="blue");

## Find the best match

## 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

## Partial alignments are allowed.

alignmentOBE <-

## 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 the (unwarped) query and the inverse-warped reference

## 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


	xlab="Query (noisy sine)",ylab="Reference (cosine)");


## 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


\item Toni Giorgino. \emph{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}
\item Tormene, P.;
Giorgino, T.; Quaglini, S. & Stefanelli, M. \emph{Matching incomplete time
series with dynamic time warping: an algorithm and an application to
post-stroke rehabilitation.} Artif Intell Med, 2009, 45, 11-34.
\item Sakoe, H.;
Chiba, S., \emph{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.
\item Mori, A.; Uchida, S.; Kurazume, R.; Taniguchi, R.; Hasegawa, T. & Sakoe, H.
\emph{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}
\item Sakoe,
H. \emph{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}
\item Rabiner L, Rosenberg A, Levinson
S (1978). \emph{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}
\item Muller M. \emph{Dynamic Time
Warping} in \emph{Information Retrieval for Music and Motion}. Springer
Berlin Heidelberg; 2007. p. 69-84. \doi{10.1007/978-3-540-74048-3_4}
\code{\link[=dtwDist]{dtwDist()}}, for iterating dtw over a set of timeseries;
\code{\link[=dtwWindowingFunctions]{dtwWindowingFunctions()}}, for windowing and global constraints;
\code{\link[=stepPattern]{stepPattern()}}, step patterns and local constraints;
\code{\link[=plot.dtw]{plot.dtw()}}, plot methods for DTW objects.  To generate a local
cost matrix, the functions \code{\link[proxy:dist]{proxy::dist()}},
\code{analogue::distance()}, \code{vegan::vegdist()}, or \code{\link[=outer]{outer()}} may come handy.
Toni Giorgino
\concept{Align timeseries}
\concept{Dynamic Time Warp}
\concept{Dynamic programming}
\concept{Minimum cumulative cost}
back to top