dtw (version 1.15)

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

code

dtw

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

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