动态时间扭曲简介

Created: November-22, 2018

动态时间扭曲（DTW）是用于测量两个时间序列之间的相似性的算法，其可以在速度上变化。例如，即使一个人比另一个人走得快，或者在观察过程中有加速度和减速度，也可以使用 DTW 检测步行的相似性。它可用于将示例语音命令与其他命令匹配，即使该人说话的速度比预先录制的样本语音更快或更慢。DTW 可以应用于视频，音频和图形数据的时间序列 - 实际上，可以使用 DTW 分析可以变成线性序列的任何数据。

通常，DTW 是一种计算具有某些限制的两个给定序列之间的最佳匹配的方法。但是，让我们坚持这里更简单的观点。假设我们有两个语音序列 Sample 和 Test ，我们想检查这两个序列是否匹配。此处语音序列是指你的语音转换后的数字信号。可能是你的声音的幅度或频率表示你说的话。我们假设：

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

我们想找出这两个序列之间的最佳匹配。

首先，我们定义两个点之间的距离， d(x, y) 其中 x 和 y 代表两个点。让，

d(x, y) = |x - y|     //absolute difference

让我们使用这两个序列创建一个 2D 矩阵表。我们将计算每个 Sample 点与每个 Test 点之间的距离，并找出它们之间的最佳匹配。

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   1  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |      |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

这里，如果我们考虑到样本[i] 和测试[j] 的序列，考虑到我们之前观察到的所有最佳距离，表[i] [j] 表示两个序列之间的最佳距离。 **** ****

对于第一行，如果我们不从 Sample 中取值，则此值与 Test 之间的距离将为无穷大。所以我们把无限放在第一行。第一列也是如此。如果我们没有从 Test 中取值，那么这个和 Sample 之间的距离也将是无穷大。并且 0 到 0 之间的距离将仅为 0 。我们得到了，

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   2  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   3  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   5  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+
|   6  |  inf |      |      |      |      |      |      |
+------+------+------+------+------+------+------+------+

现在，对于每个步骤，我们将考虑所关注的每个点之间的距离，并将其添加到我们到目前为止找到的最小距离。这将为我们提供两个序列到该位置的最佳距离。我们的公式将是，

Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])

对于第一个， d（1,1） = 0 ，表[0] [0] 表示最小值。因此表[1] [1]的值将为 0 + 0 = 0 。对于第二个， d（1,2） = 0 。表[1] [1] 表示最小值。该值为： 表[1] [2] = 0 + 0 = 0 。如果我们继续这种方式，在完成后，表格将如下所示：

+------+------+------+------+------+------+------+------+
|      |   0  |   1  |   1  |   2  |   2  |   3  |   5  |
+------+------+------+------+------+------+------+------+
|   0  |   0  |  inf |  inf |  inf |  inf |  inf |  inf |
+------+------+------+------+------+------+------+------+
|   1  |  inf |   0  |   0  |   1  |   2  |   4  |   8  |
+------+------+------+------+------+------+------+------+
|   2  |  inf |   1  |   1  |   0  |   0  |   1  |   4  |
+------+------+------+------+------+------+------+------+
|   3  |  inf |   3  |   3  |   1  |   1  |   0  |   2  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |   7  |   7  |   4  |   4  |   2  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  11  |  11  |   7  |   7  |   4  |   0  |
+------+------+------+------+------+------+------+------+
|   5  |  inf |  15  |  15  |  10  |  10  |   6  |   0  |
+------+------+------+------+------+------+------+------+
|   6  |  inf |  20  |  20  |  14  |  14  |   9  |   1  |
+------+------+------+------+------+------+------+------+

在值表[7] [6] 表示这两个给定序列之间的最大距离。这里 1 表示 Sample 和 Test 之间的最大距离为 1 。

现在，如果我们从最后一点回溯，一直回到起点 （0,0） 点，我们得到一条水平，垂直和对角线移动的长线。我们的回溯程序将是：

if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
    i := i - 1
    j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
    i := i - 1
else
    j := j - 1
end if

我们将继续这一直到达到 （0,0） 。每一步都有自己的含义：

水平移动表示删除。这意味着我们的测试序列在此间隔内加速。
垂直移动表示插入。这意味着在此间隔期间测试序列减速。
对角线移动表示匹配。在此期间，测试和样品是相同的。 https://i.stack.imgur.com/2Bfjj.jpg

我们的伪代码将是：

Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
    Table[i][0] := infinity
end for
for i from 1 to m
    Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
    for j from 1 to m
        Table[i][j] := d(Sample[i], Test[j])
                       + minimum(Table[i-1][j-1],      //match
                                 Table[i][j-1],        //insertion
                                 Table[i-1][j])        //deletion
    end for
end for
Return Table[n + 1][m + 1]

我们还可以添加局部性约束。也就是说，我们要求如果 Sample[i] 与 Test[j] 匹配，则|i - j|不大于窗口参数 w 。

复杂：

计算 DTW 的复杂性是 O（m * n） ，其中 m 和 n 表示每个序列的长度。更快的计算 DTW 的技术包括 PrunedDTW，SparseDTW 和 FastDTW。

应用：

口语识别
相关功率分析