DTW的作用

Dynamic time warping 简称DTW，用于计算两个时间序列之间的相似性的算法，也可以理解找到两个时间序列之间的最佳匹配。DTW最著名的用途应该是用于语音识别。

Figure 1

DTW为什么会出现呢？

在计算两个序列相似性时，传统的度量方法如欧式距离、曼哈顿距离都会失效，或者说无法真正度量两个序列相似性。其原因是，这些距离度量方式是用一一对应的距离度量。

Figure 2 欧式距离

那么有没有一种根据序列的走势来计算相似性呢，比如序列A上某个点可能和序列B上多个点进行匹配。DTW就可以达到这种效果，如下图：

Figure 3  DTW

DTW算法形式

int DTWDistance(s: array [1..n], t: array [1..m]) {

   DTW := array [0..n, 0..m]

   for i := 1 to n

       DTW[i, 0] := infinity

   for i := 1 to m

       DTW[0, i] := infinity

   DTW[0, 0] := 0

   for i := 1 to n

       for j := 1 to m

           cost:= d(s[i], t[j])

           DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion

                                       DTW[i  , j-1],    // deletion

                                       DTW[i-1, j-1])    // match

   return DTW[n, m]

}

注意，

(1)     这个问题是一个动态规划问题，并且算法中经典问题——求字符串匹配的编辑距离——类似。

(2)     找两个序列的匹配路径，要从最末尾的dtw(n,m)往回找，而不是从dtw(1,1)往前搜。

Reference:

Distance Functions for Sequence Data and Time Series

https://en.wikipedia.org/wiki/Dynamic_time_warping