面臨的問題

當數據在時間線上不對齊的時候，使用傳統的匹配方法，是無法使用傳統的全局匹配度量法的。DTW是一種衡量兩個時間序列之間的相似度的方法，主要應用在語音識別領域來識別兩段語音是否表示同一個單詞。

?

DTW原理

(Dynamic Time Warping, DTW) 動態時間歸整
DTW通過把時間序列進行延伸和縮短，來計算兩個時間序列性之間的相似性。
如下圖所示，上下兩條實線代表兩個時間序列，時間序列之間的虛線代表兩個時間序列之間的相似度，虛線的兩端代表兩個相似的點。

DTW使用所有這些相似點之間的距離的和，稱之為歸整路徑距離(Warp Path Distance)來衡量兩個時間序列之間的相似度。

給出兩個序列：

Warping通常采用動態規劃算法。為了對齊這兩個序列，我們需要構造一個n x m的矩陣網格，矩陣元素(i, j)表示qi和cj兩個點的距離d(qi, cj)，一般采用歐式距離，（也可以理解為失真度）。每一個矩陣元素(i, j)表示點qi和cj的對齊。

DP(dynamic programming)算法可以歸結為尋找一條通過此網格中若干格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。

有三個性質：

• 邊界條件：w1=(1, 1)和wK=(m, n)。兩個人分別說了同一個單詞，但是由于語速、語氣、語調等等各不相同，會導致采樣得到的數據無法對齊。但是兩段語音采樣的第一個采樣值和最后一個采樣值肯定是兩兩對應的。
• 連續性：如果wk-1= (a', b')，那么對于路徑的下一個點wk=(a, b)需要滿足 (a-a') <=1和 (b-b') <=1。也就是不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證Q和C中的每個坐標都在W中出現。
• 單調性：如果wk-1= (a', b')，那么對于路徑的下一個點wk=(a, b)需要滿足0<=(a-a’)和0<= (b-b’)。這限制W上面的點必須是隨著時間單調進行的。以保證上圖中的虛線不會相交。

由連續性和單調性可知，每次格點(i, j)前進方向只有三種：(i+1, j)，(i, j+1) 或 (i+1, j+1)。我們的目的是使得下面的規整代價最小的路徑：

分母中的K主要是用來對不同的長度的規整路徑做補償。

這里我們定義一個累加距離(cumulative distances)。從(0, 0)點開始匹配這兩個序列Q和C，每到一個點，之前所有的點計算的距離都會累加。到達終點(n, m)后，這個累積距離就是我們上面說的最后的總的距離，也就是序列Q和C的相似度。

示例：

對于兩個序列：

X：3,5,6,7,7,1

Y：3,6,6,7,8,1,1

X和Y的距離矩陣如下

然后根據距離矩陣生成損失矩陣(Cost Matrix)或者叫累積距離矩陣 ，其計算方法如下：

• 第一行第一列元素為 的第一行第一列元素，在這里就是0；

• 其他位置的元素 的值則需要逐步計算，具體值的計算方法為 ，得到的如下：

?最后，兩個序列的距離，由損失矩陣最后一行最后一列給出，在這里也就是2。

給定了距離矩陣，如何找到一條從左上角到右下角的路徑，使得路徑經過的元素值之和最小。

?

python 代碼實現

?代碼里用到的sys.maxsize，需要python3支持

import sysdef distance(a,b):return abs(a-b)def Min(a,b,c):return min(a,min(b,c))def dtw(X, Y):M = [[distance(X[j], Y[i]) for i in range(len(Y))] for j in range(len(X))]l1 = len(X)l2 = len(Y)D = [[0 for i in range(l2+1)] for i in range(l1+1)]D[0][0] = 0for i in range(1, l2 + 1):D[0][i] = sys.maxsizefor j in range(1, l1 + 1):D[j][0] = sys.maxsizefor j in range(1, l2+1):for i in range(1, l1+1):D[i][j] = M[i - 1][j - 1] + Min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])return D[l1][l2]if __name__ == '__main__':X = [3,5,6,7,7,1]Y = [3,6,6,7,8,1,1]Z = [2,5,7,7,7,7,2]value = dtw(X, Y)print(value)value = dtw(X, Z)print(value)

DTW雖然使用線性規劃可以快速的求解，但是在面對比較長的時間序列是，O(N2)的時間復雜度還是很大。已經有很多改進的快速DTW算法，比如FastDTW等。

DTW常用加速手段

? 常用的DTW加速手段:

(1). 限制。亦即減少累積距離矩陣的搜索空間，下圖中陰影部分為實際的探索空間，空白的部分不進行探索。

?(2). 數據抽象。亦即把之前長度為N的時間序列規約成長度為M(M<N)表述方式：

?

?(3). 索引。索引是在進行分類和聚類時減少需要運行的DTW的次數的方法，并不能加速一次的DTW計算。

?FastDTW

? FastDTW綜合使用限制和數據抽象兩種方法來加速DTW的計算，主要分為三個步驟：

? (1).?粗粒度化。亦即首先對原始的時間序列進行數據抽象，數據抽象可以迭代執行多次1/1->1/2->1/4->1/16，粗粒度數據點是其對應的多個細粒度數據點的平均值。

? (2).?投影。在較粗粒度上對時間序列運行DTW算法。

? (3).?細粒度化。將在較粗粒度上得到的歸整路徑經過的方格進一步細粒度化到較細粒度的時間序列上。除了進行細粒度化之外，我們還額外的在較細粒度的空間內額外向外(橫向，豎向，斜向)擴展K個粒度，K為半徑參數，一般取為1或者2.

? FastDTW算法的具體執行流程如下圖所示:

? 第一個圖表示在較粗粒度空間(1/8)內執行DTW算法。第二個圖表示將較粗粒度空間(1/8)內求得的歸整路徑經過的方格細粒度化，并且向外(橫向，豎向，斜向)擴展一個(由半徑參數確定)細粒度單位后，再執行DTW得到的歸整路徑。第三個圖和第四個圖也是這樣。

? 由于采取了減少搜索空間的策略，FastDTW并不一定能夠求得準確的DTW距離，但是FastDTW算法的時間復雜度比較低，為O(N)。

?

參考：

https://blog.csdn.net/raym0ndkwan/article/details/45614813

https://www.cnblogs.com/kemaswill/archive/2013/04/18/3028610.html

https://www.cnblogs.com/kemaswill/archive/2013/04/18/3029078.html

總結

以上是生活随笔為你收集整理的DTW 动态时间规整的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。