DTW算法初步理解
参考文献地址：原文：
https://blog.csdn.net/zouxy09/article/details/9140207
DTW（Dynamic Time Warping ）动态时间规整算法，是一种计算2个时间序列尤其是不同长度序列相似度的一种动态规划算法。主要应用在时序数据上，比如孤立词语音识别、手势识别、数据挖掘以及信息检索等。
一、概述
时间序列是很常见的一种数据存在方式，而在大多数数据挖掘工作中，计算时间序列之间的相似度是经常遇到的任务。而在现实情况下，进行相似度计算的时间序列往往在时间轴上存在大致相似，但具体对应关系不得而知。例如两个人说同一个词，因为每个人的说话的音色，频率不同，所以虽然听起来都是同一个词的发音，但是在同一时刻的对应关系却不一定相同。就像图A所示，a点在形状上来看的话，更应该和b点相似，而不是同一时刻的b'点。假如通过传统的欧式距离进行计算的话，不会考虑时间上的动态变化，很明显会造成极大的误差。
因此，如何计算非等长时间序列的相似度就是一个问题，DTW的出现就是解决这个问题的。先看下经过时间规整后的对应关系就如图B所示，这2个时间序列在时间轴的并不是一一对齐的。
二、DTW如何计算？
DTW算法实质上是一个动态规划算法。假设我们又一个模板序列C、查询序列Q。他们的长度分别是m,n。
假如m=n的话，那可以不需要进行时间规整，直接计算欧式距离就可以计算出2个序列之间的距离。假如不等的话，则需要进行时间规整找出2个序列之间的最短距离。
为了进行对齐操作，我们需要先构造一个n x m的矩阵，矩阵元素（i，j）表示Qi 和Cj两个点之间的距离d(Qi，Cj)，这个距离计算采用的是欧式距离，即d(Qi,Cj) = (Qi-Cj)²。DTW算法就是寻找一条从原点出发到（Qn,Cm）的最短路径。
我们定义路径为W，W的第k个元素定义为Wk = (i,j)k，第K个路径点Q与C的对齐关系。
由于时间序列数据的特点，在寻找路径之前需要有几个限制条件。
1、边界条件：
W1=（1，1）和Wk=（m,n）。任何的时间序列都符合这一条件，即开始和最后时刻的对齐是确定的，路径必须从左下角出发到右上角结束。
2、连续性：
如果Wk-1=（a'，b'），那么对于下一个路径点Wk = （a，b）需要满足：（a-a'）<=1和（b-b'）<=1.即2个时序数据在对齐时，不会出现遗漏，跨越某个点进行对齐。
3、单调性：
如果Wk-1= (a’, b’)，那么对于路径的下一个点Wk=(a, b)需要满足0<=(a-a’)和0<= (b-b’)。这限制W上面的点必须是随着时间单调进行的。以保证图B中的虚线不会相交。
这2个性质在路径上的体现就是下一个路径点的选择必须是右方、上方、右上方。
满足上述约束条件的路径有很多，但是我们需要求的是最短的路径：
分母中的K主要是用来对不同的长度的规整路径做补偿。我们的目的是什么？或者说DTW的思想是什么？是把两个时间序列进行延伸和缩短，来得到两个时间序列性距离最短也就是最相似的那一个warping，这个最短的距离也就是这两个时间序列的最后的距离度量。在这里，我们要做的就是选择一个路径，使得最后得到的总的距离最小。
这里我们定义一个累加距离cumulative distances。从(0, 0)点开始匹配这两个序列Q和C，每到一个点，之前所有的点计算的距离都会累加。到达终点(n, m)后，这个累积距离就是我们上面说的最后的总的距离，也就是序列Q和C的相似度。
累积距离γ(i,j)可以按下面的方式表示，累积距离γ(i,j)为当前格点距离d(i,j)，也就是点qi和cj的欧式距离（相似性）与可以到达该点的最小的邻近元素的累积距离之和：
最佳路径是使得沿路径的积累距离达到最小值这条路径。这条路径可以通过动态规划（dynamic programming）算法得到。