dtw (version 1.17-1)

dtw: Dynamic Time Warp

Description

Compute Dynamic Time Warp and find optimal alignment between two time series.

Usage

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,...)

Arguments

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

Value

• 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)
• 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.

code

dtw

emph

leading part

concept

• Dynamic Time Warp
• Dynamic programming
• Align timeseries
• Minimum cumulative cost
• Distance

Details

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:

1. ifdist.methodis a string,xandyare passed to thedistfunction in packageproxywith the method given;
2. ifdist.methodis a function of two arguments, it invoked repeatedly on all pairsx[i],y[j]to build the local cost matrix;
3. 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 elementx[i]andy[j]. The distance matrix has thereforen=length(x)rows andm=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}

References

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.

See Also

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.

Examples

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