参考：

  1. 算法笔记-DTW动态时间规整.
  2. 时间序列相似性度量-DTW.

两个时间序列 Q = [ q 1 , q 2 , . . . q n ] Q=[q_1, q_2, ...q_n] Q=[q1​,q2​,...qn​] 和 C = [ c 1 , c 2 , . . . c n ] C=[c_1, c_2, ...c_n] C=[c1​,c2​,...cn​]，长度分别为 n n n 和 m m m；那么 DTW 计算 Q Q Q 和 C C C 相似度的计算过程如下：

S t e p 1. Step 1. Step1. 构建大小为 n × m n × m n×m 的矩阵 D D D，矩阵元素 d i j = d i s t ( q i , c j ) d_{ij}=dist(q_i, c_j) dij​=dist(qi​,cj​)， 其中 d i s t dist dist 表示距离计算函数，通常采用欧几里德距离；

S t e p 2. Step 2. Step2. 在矩阵 D D D 中搜索从 d 11 d_{11} d11​ 到 d n m d_{nm} dnm​ 的最短路径 （通常使用动态规划搜索），在 d i j d_{ij} dij​ 位置，路径搜索方向如下图所示：

S t e p 3. Step 3. Step3. 将矩阵 D D D 中搜索从 d 11 d_{11} d11​ 到 d n m d_{nm} dnm​ 的最短路径作为 Q Q Q 和 C C C 序列的相似度。

总的计算公式如下所示：

D ( i , j ) = D i s t ( i , j ) + m i n [ D ( i − 1 , j ) , D ( i , j − 1 ) , D ( i − 1 , j − 1 ) ] D(i,j) = Dist(i,j) + min[D(i-1, j), D(i, j-1), D(i-1, j-1)] D(i,j)=Dist(i,j)+min[D(i−1,j),D(i,j−1),D(i−1,j−1)]