|
|
Comprehensive implementation of Dynamic Time Warping algorithms in R. Supports arbitrary local (eg symmetric, asymmetric, slope-limited) and global (windowing) constraints, fast native code, several plot styles, and more.
The R Package dtw provides the most complete, freely-available (GPL) implementation of Dynamic Time Warping-type (DTW) algorithms up to date.
The basic DTW algorithm computes the time axis stretch which optimally maps one timeseries (query) onto another (reference); it outputs the remaining cumulative distance between the two, which is widely used e.g. for classification and clustering.
The R implementation in dtw provides:
Multivariate timeseries can be aligned with arbitrary local distance definitions, leveraging the {proxy}dist function. DTW itself becomes a distance function with the dist semantics.
In addition to computing alignments, the package provides:
The best place to learn how to use the package (and a hopefully a decent deal of background on DTW) is the paper Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package, which the Journal of Statistical Software makes available for free.
To have a look at how the dtw package is used in domains ranging from bioinformatics to chemistry to data mining, have a look at the list of citing papers.
If you use this software, you are required to cite it in any
publication reporting results obtained with dtw. Please follow
the directions given in citation("dtw"), i.e. cite:
Toni Giorgino (2009). Computing and Visualizing Dynamic Time Warping Alignments in R: The dtw Package. Journal of Statistical Software, 31(7), 1-24. URL www.jstatsoft.org/v31/i07/.
For partial matching and normalization strategies also cite:
Paolo Tormene, Toni Giorgino, Silvana Quaglini, Mario Stefanelli (2008). Matching Incomplete Time Series with Dynamic Time Warping: An Algorithm and an Application to Post-Stroke Rehabilitation. Artificial Intelligence in Medicine, 45(1), 11-34. doi:10.1016/j.artmed.2008.11.007
This software is distributed under the terms of the GNU General Public License Version 2, June 1991. The terms of this license are in a file called COPYING which you should have received with this software and which can be displayed by RShowDoc("COPYING").
Go to a gallery of sample plots (straight out of the examples in the documentation).
## A noisy sine wave as query
idx<-seq(0,6.28,len=100);
query<-sin(idx)+runif(100)/10;
## A cosine is for template; sin and cos are offset by 25 samples
template<-cos(idx)
## Find the best match with the canonical recursion formula
library(dtw);
alignment<-dtw(query,template,keep=TRUE);
## Display the warping curve, i.e. the alignment curve
plot(alignment,type="threeway")
## Align and plot with the Rabiner-Juang type VI-c unsmoothed recursion
plot(
dtw(query,template,keep=TRUE,
step=rabinerJuangStepPattern(6,"c")),
type="twoway",offset=-2);
## See the recursion relation, as a figure and text
plot(rabinerJuangStepPattern(6,"c"))
rabinerJuangStepPattern(6,"c")
## And much more!
To install the
latest stable
build of the package (hosted at CRAN), issue the following command
in the R console (automated installs require R version > 2.6):
> install.packages("dtw");
To get started, begin from the installed documentation:
> library(dtw)
> ?dtw
> ?plot.dtw
You are also welcome to test the development version, hosted at
R-forge (project summary page):
> install.packages("dtw",repos="http://r-forge.r-project.org")
Alas, most likely you haven't. DTW had been "multidimensional" since its conception. Local distances are computed between N-dimensional vectors; feature vectors have been extensively used in speech recognition since the '70s (see e.g. things like MFCC, RASTA, cepstrum, etc). Don't worry: several other people have "rediscovered" multi-dimensional DTW already. The dtw package supports the numerous types of multi-dimensional local distances that the proxy package does, as explained in section 3.6 of the paper in JSS.I've discovered a "realtime" version of the DTW algorithm!
Alas, most likely you haven't. Real-time recognition of timeseries is based on "unconstrained" DTW (having either one or two free ends) for which, to my knowledge, algorithms had been published as early as 1978 by Rabiner and Juang under the name UE2-1: see e.g. the mini-review in (Tormene and Giorgino, 2008). Feel also free to learn about clever realtime DTW-like algorithms by Sakurai et al (2007); Latecki (2007); Mori et al. (2006); Smith-Waterman (1981); etc. Open-ended alignments (both at one and two ends) are supported by the dtw package, as described in section 3.5 of the JSS paper.Can I use dtw in Python?
Yes. Please see Stefan Novak's version of the quickstart example on Stack Overflow. The mapping is performed through the Python package rpy2, which makes the code natural and readable. It also plays well with numpy and multiprocessing.
Feel free to invite me to give a seminar or talk at your academic institution to enjoy a personalized introduction to dtw and applications. Please indicate available dates, audience type (technical, graduate, undergraduate) and preferred length.
Consultancy services are available for companies.