Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
At http://www.speech.zone/exercises/dtw-in-python/ it says
Although it's not really used anymore, Dynamic Time Warping (DTW) is a nice introduction to the key concept of Dynamic Programming.
I am using DTW for signal processing and are a little surprised: What is used instead?
I wouldn't consider DTW to be outdated at all. In 2006 Xi et al. showed that
[...] many algorithms have been proposed for the problem of time series classification. However, it is clear that one-nearest-neighbor with Dynamic Time Warping (DTW) distance is exceptionally difficult to beat.
The results of this paper are summarized in the book "Temporal Data Mining" by Theophano Mitsa as follows:
- In [Che05a], a static minimization–maximization approach yields a maximum error of 7.2%. With 1NN-DTW, the error is 0.33% with the same dataset as in the original article.
- In [Che05b], a multiscale histogram approach yields a maximum error of 6%. With 1NN-DTW, the error (on the same data set) is 0.33%.
- In [Ead05], a grammar-guided feature extraction algorithm yields a maximum error of 13.22%. With 1NN-DTW, the error was 9.09%.
- In [Hay05], time series are embedded in a lower dimensional space using a Laplacian eigenmap and DTW distances. The authors achieved an impressive 100% accuracy; however, the 1NN-DTW also achieved 100% accuracy.
- In [Kim04], Hidden Markov Models achieve 98% accuracy, while 1NN-DTW achieves 100% accuracy.
- In [Nan01], a multilayer perceptron neural network achieves the best performance of 1.9% error rate. On the same data set, 1NN-DTW’s rate was 0.33%.
- In [Rod00], first-order logic with boosting gives an error rate of 3.6%. On the same dataset, 1NN-DTW’s error rate was 0.33%.
- In [Rod04], a DTW-based decision tree gives an error rate of 4.9%. On the same dataset, 1NN-DTW gives 0.0% error. • In [Wu04], a super-kernel fusion set gives an error rate of 0.79%, while on the same data set, 1NN-DTW gives 0.33%.
Please see the original book for a list of the mentioned references.
An important thing to note here is the fact that Xi et al. even managed to beat the performance of an MLP back in 2006. Even though the situation might look a bit different these days (as we have better and faster Deep learning algorithms at hand), I would still consider DTW a valid option to look into when it comes to signal classifications.
I would also like to add a link to a more recent paper called "The Great Time Series Classification Bake Off: An Experimental Evaluation of Recently Proposed Algorithms" from 2016. In this paper, the authors "have implemented 18 recently proposed algorithms in a common Java framework and compared them against two standard benchmark classifiers (and each other)". The following quotes from the paper stress that DTW is (or at least was in 2016) indeed still relevant:
- Many of the algorithms are in fact no better than our two benchmark classifiers, 1-NN DTW and Rotation Forest.
- For those looking to build a predictive model for a new problem we would recommend starting with DTW, RandF and RotF as a basic sanity check and benchmark.
- Received wisdom is that DTW is hard to beat.
Dynamic Time Warping (DTW) has quadratic complexity. There are several other versions of the algorithm, like FastDTW (linear complexity) that decrease the complexity by computing approximations. FastDTW is implemented, for instance, in this Python module.
As far as I know it's mostly about the computational aspect which was improved, so it's still a proper method to measure similarity between sequences.
I recommend this as a good reference, specially section 4.3. Here is the bold part of this section:
A warping path W is a set of contiguous matrix indices defining a mapping between two time series. Even if there is an exponential number of possible warping paths, the optimal path is the one that minimizes the global warping cost. DTW can be computed using dynamic programming with time complexity O(n2) [Ratanamahatana and Keogh 2004a]. However, several lower bounding measures have been introduced to speed up the computation. Keogh and Ratanamahatana [2005] introduced the notion of upper and lower envelope that represents the maximum allowed warping. Using this technique, the complexity becomes O(n). It is also possible to impose a temporal constraint on the size of the DTW warping window. It has been shown that these improve not only the speed but also the level of accuracy as it avoids the pathological matching introduced by extended warping [Ratanamahatana and Keogh 2004b]. The two most frequently used global constraints are the Sakoe-Chiba Band and the Itakura Parallelogram. Salvador and Chan [2007] introduced the FastDTW algorithm which makes a linear time computation of DTW possible by recursively projecting a warp path to a higher resolution and then refining it. A drawback of this algorithm is that it is approximate and therefore ACM Computing Surveys, Vol. 45, No. 1, Article 12, Publication date: November 2012. 12:18 P. Esling and C. Agon offers no guarantee to finding the optimal solution. In addition to dynamic warping, it may sometimes be useful to allow a global scaling of time series to achieve meaningful results, a technique known as Uniform Scaling (US). Fu et al. [2008] proposed the Scaled and Warped Matching (SWM) similarity measure that makes it possible to combine the benefits of DTW with those of US. Other shape-based measures have been introduced such as the Spatial Assembling Distance (SpADe) [Chen et al. 2007b]; it is a pattern-based similarity measure. This algorithm identifies matching patterns by allowing shifting and scaling on both temporal and amplitude axes, thus being scale robust. The DISSIM [Frentzos et al. 2007] distance has been introduced to handle similarity at various sampling rates. It is de- fined as an approximation of the integral of the Euclidean distance. One of the most interesting recent proposals is based on the concept of elastic matching of time series [Latecki et al. 2005]. Latecki et al. [2007] presented an Optimal SuBsequence matching (OSB) technique that is able to automatically determine the best subsequence and warping factor for distance computation; it includes a penalty when skipping elements. Optimality is achieved through a high computational cost; however, it can be reduced by limiting the skipping range.
