动态时间规整（DTW）算法1
DTW最初用于识别语音的相似性。我们用数字表示音调高低，例如某个单词发音的音调为1-3-2-4。现在有两个人说这个单词，一个人在前半部分拖长，其发音为1-1-3-3-2-4；另一个人在后半部分拖长，其发音为1-3-2-2-4-4。
image
现在要计算1-1-3-3-2-4和1-3-2-2-4-4两个序列的距离（距离越小，相似度越高）。因为两个序列代表同一个单词，我们希望算出的距离越小越好，这样把两个序列识别为同一单词的概率就越大。
先用传统方法计算两个序列的欧几里得距离，即计算两个序列各个对应的点之间的距离之和。
距离之和
= |A(1)-B(1)| + |A(2)-B(2)| + |A(3)-B(3)| + |A(4)-B(4)| + |A(5)-B(5)| + |A(6)-B(6)|
= |1-1| + |1-3| + |3-2| + |3-2| + |2-4| + |4-4|
= 6
image
如果我们允许序列的点与另一序列的多个连续的点相对应（相当于把这个点所代表的音调的发音时间延长），然后再计算对应点之间的距离之和。如下图：B(1)与A(1)、A(2)相对应，B(2)与A(3)、A(4)相对应，A(5)与B(3)、B(4)相对应，A(6)与B(5)、B(6)相对应。
image
这样的话，
距离之和
= |A(1)-B(1)| + |A(2)-B(1)| + |A(3)-B(2)| + |A(4)-B(2)| + |A(5)-B(3)| + |A(5)-B(4)| + |A(6)-B(5)| + |A(6)-B(6)|
= |1-1| + |1-1| + |3-3| + |3-3| + |2-2| + |2-2| + |4-4| + |4-4|
= 0
我们把这种“可以把序列某个时刻的点跟另一时刻多个连续时刻的点相对应”的做法称为时间规整（Time Warping）。
现在我们用一个6*6矩阵M表示序列A（1-1-3-3-2-4）和序列B（1-3-2-2-4-4）各个点之间的距离，M(i, j)等于A的第i个点和B的第j个点之间的距离，即
image.png
image
我们看到传统欧几里得距离里对应的点：
- A(1)-B(1)
- A(2)-B(2)
- A(3)-B(3)
- A(4)-B(4)
- A(5)-B(5)
- A(6)-B(6)
它们正好构成了对角线，对角线上元素和为6。
时间规整的方法里，对应的点为：
- A(1)A(2)-B(1)
- A(3)A(4)-B(2)
- A(5)-B(3)B(4)
- A(6)-B(5)B(6)
这些点构成了从左上角到右下角的另一条路径，路径上的元素和为0。
因此，DTW算法的步骤为：
- 计算两个序列各个点之间的距离矩阵。
- 寻找一条从矩阵左上角到右下角的路径，使得路径上的元素和最小。
我们称路径上的元素和为路径长度。那么如何寻找长度最小的路径呢？
矩阵从左上角到右下角的路径长度有以下性质：
- 当前路径长度 = 前一步的路径长度 + 当前元素的大小
- 路径上的某个元素(i, j)，它的前一个元素只可能为以下三者之一：
a) 左边的相邻元素 (i, j-1)
b) 上面的相邻元素 (i-1, j)
c) 左上方的相邻元素 (i-1, j-1)
假设矩阵为M，从矩阵左上角(1,1)到任一点(i, j)的最短路径长度为Lmin(i, j)。那么可以用递归算法求最短路径长度：
起始条件：
image.png
递推规则：
image.png
递推规则这样写的原因是因为当前元素的最短路径必然是从前一个元素的最短路径的长度加上当前元素的值。前一个元素有三个可能，我们取三个可能之中路径最短的那个即可。
