1. DTW作用

動態時間規整算法，能夠將兩個代表同一個類型的事物的不同長度序列進行時間上的“對齊”。
比如在語音識別中，同一個字母，由不同人發音，時間長短不一，但信號相似。故需要用一個函數拉長或者縮短其中一個信號，使得它們之間的誤差達到最小。

如圖所示，實線和虛線分別是同一個詞的兩個語音波形。可以看到他們整體上的波形形狀很相似，但在時間軸上卻是不對齊的。
例如在第20個時間點的時候，實線波形的a點會對應于虛線波形的b’點，這樣傳統的通過比較距離來計算相似性很明顯不靠譜。而實際上實線的a點對應虛線的b點才是正確的。

2. DTW實現步驟

假設有兩個序列A={a₁，a₂,a₃,…,a_m} ，B={b₁,b₂,b₃,…,b_n}，維度m > n

用歐式距離計算出這兩個序列間每兩點之間的距離得到 D(a_i, b_j)，其中1 ≤ i ≤m，1 ≤ j ≤ n，得到下表：

D(a₁,b₁)D(a₁,b₂)…D(a₁,b_n)

D(a2,b1)	D(a2,b2)	…	D(a2,bn)
…	…	…	…
D(an,b1)	D(an,b2)	…	D(an,bn)

計算從D(a₁,b₁)到D(a_m,b_n)的最短路徑。過程需滿足：假如當前節點是D(a_i, b_j)，那么下一個節點必須是在D(_i+1, _j)，D(_i, _j+1)，D(_i+1, _j+1)之間選擇

最終再次從起點到終點，計算最短累計距離

例：

已知： 兩個列向量a=[8 9 1]‘，b=[ 2 5 4 6]’
（其中’代表轉置，也就是把行向量轉換為列向量了）

求： 兩個向量利用動態時間規整以后的最短距離

第一步： 計算對應點的歐式距離矩陣 d 得：

6 3 4 2 7 4 5 3 1 4 3 5

其中6是8到2的距離，3是8到5的距離，7是9到2的距離

第二步： 計算累加距離D（從起點6出發到達終點5的累加距離）

6 9 13 15 13 10 14 16 14 14 13 18

計算方法如下：

D(1,1) = D(1,1) = 6

D(1,2) = D(1,1) + D(1,2) = 9

…

D(2,2) = min(D(1,2),D(1,1),D(2,1)) + d(2,2) = 6 + 4 = 10

…

D(m,n) = min(D(m-1,n),D(m-1,n-1),D(m,n-1)) + D(m,n)
在這里插入圖片描述

即每個元素位置的累積距離數值為它左邊，上邊以及左上邊的三個數值中的最小值加上元素本身的數值。

3. Mtalab代碼實現

% 輸入兩段離散序列，輸出兩段序列的總歐式距離 function dist = dtw(t,r) n = size(t,1); m = size(r,1);d = zeros(n,m); for i = 1:nfor j = 1:md(i,j) = (t(i,:)-r(j,:)).^2;end endD = ones(n,m) * realmax; D(1,1) = d(1,1);for i = 1:nfor j = 1:mif i==1&&j==1continue;endif i>1D1 = D(i-1,j);elseD1 = realmax;endif j>1&&i>1D2 = D(i-1,j-1);else D2 = realmax;endif j>1D3 = D(i,j-1);elseD3 = realmax;endD(i,j) = d(i,j) + min([D1,D2,D3]);end end dist = D(n,m);

4. 參考資料

【重大修改】動態時間規整（Dynamic Time Warping）
DTW算法
離散序列的一致性度量方法：動態時間規整（DTW）
DTW(Dynamic Time Warping)動態時間規整——簡單易懂

總結

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

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