DTW: dynamic time warping 动态时间规整

Basically, DTW (dynamic time warping) is an algorithm to output cumulative distance of two time sequences, which is widely used e.g. for classification and clustering.

For example, when using k-mean for clustering, we can use DTW as distance function. Here is one of such nice instances (using R: http://www.rdatamining.com/examples/ts-mining)

Relevant information from Anshul's email.  

A review of DTW http://csdl.ics.hawaii.edu/techreports/08-04/08-04.pdf

Code:

Python code: https://mlpy.fbk.eu/

R code: http://dtw.r-forge.r-project.org/

JAVA code: http://java-ml.sourceforge.net/ or http://code.google.com/p/fastdtw/

MATLAB: the samplealign() function in the bioinformatics toolbox does DTW

There is also the global alignment kernel that is faster and more accurate that DTW. It can be used to compute distance between time series to be used in clustering allowing for all possible global alignments. Here is code http://www.iip.ist.i.kyoto-u.ac.jp/member/cuturi/GA.html

Here is an example (in Chinese) from Ckary's blog:

在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离，但是对于一些特殊情况，欧氏距离存在着其很明显的缺陷，比如说时间序列，举个比较简单的例子，序列A：1,1,1,10,2,3，序列B：1,1,1,2,10,3，如果用欧氏距离，也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话，总的距离和应该是128，应该说这个距离是非常大的，而实际上这个序列的图像是十分相似的，这种情况下就有人开始考虑寻找新的时间序列距离的计算方法，然后提出了DTW算法，这种方法在语音识别，机器学习方便有着很重要的作用。这个算法是基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，简单来说，就是通过构建一个邻接矩阵，寻找最短路径和。还以上面的2个序列作为例子，A中的10和B中的2对应以及A中的2和B中的10对应的时候，distance[3]以及distance[4]肯定是非常大的，这就直接导致了最后距离和的膨胀，这种时候，我们需要来调整下时间序列，如果我们让A中的10和B中的10 对应 ，A中的1和B中的2对应，那么最后的距离和就将大大缩短，这种方式可以看做是一种时间扭曲，看到这里的时候，我相信应该会有人提出来，为什么不能使用A中的2与B中的2对应的问题，那样的话距离和肯定是0了啊，距离应该是最小的吧，但这种情况是不允许的，因为A中的10是发生在2的前面，而B中的2则发生在10的前面，如果对应方式交叉的话会导致时间上的混乱，不符合因果关系。接下来，以output[6][6](所有的记录下标从1开始，开始的时候全部置0)记录A，B之间的DTW距离，简单的介绍一下具体的算法，这个算法其实就是一个简单的DP，状态转移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离.

 The C code there is also much helpful in understanding the algorithm.