【參考資料】
【1】《基于DTW距離的時序相似性方法提取水稻遙感信息》
【2】《動態時間規整—DTW算法》 https://blog.csdn.net/qq_39516859/article/details/81705010
【3】《DTW算法Python實現》 https://www.cnblogs.com/ningjing213/p/10502519.html
【4】《動態規劃講解+例子》https://wenku.baidu.com/view/29ffed3e974bcf84b9d528ea81c758f5f61f2989.html#

1. 算法描述

DTW主要用戶評價不同長度的時序序列相似度。

1.1 假設存在

長度為n的序列 $S=\{s_1,s_2,\dots s_n\}$
長度為m的序列 $T=\{t_1,t_2,\dots t_m\}$
其中 $n=m$

1.2 構造距離矩陣

$A_{n\times m}$，矩陣A的每個元素$a_{ij}=d(s_i,t_j)$代表兩個序列對應點的距離。這個距離計算的方法通常就是歐式距離。

構造這個矩陣的目的實際上是未來尋求兩個不長度曲線的最佳匹配。如下圖所示：

如果時間長度序列一樣這一次匹配各點歐式距離即可得到相似度。但如果時序長度不同

這需要存在一種匹配關系，比如在上圖的例子中紅色序列的第一個點同時匹配綠色序列的二三兩個點。

備注：這張圖由于繪制的時候由于時間間隔畫比較大所以不那么直觀。

那么這種匹配關系的查找在算法中可以體現為在矩陣A中尋找一條路徑從$a_{1}1$移動到$a_{n}m$，然后根據這個匹配原則計算距離，使得距離和最小【最佳匹配】。

下圖中的紅、黑、藍軌跡實際就代表三種匹配規則。

1.3 算法邏輯

DTW算法的本質是用動態規劃的思路去搜索這個最佳匹配。從這個角度講應該用什么算法是無所謂的，只要能搜索到這個最佳匹配 😃

動態規劃算法備注：

動態規劃是每一輪都基于上一輪的最優解，dijkstra的最短路徑算法應該是最經典的，需要注意的是，如上圖所示。

在計算B輪的時候，并不因為$\{C_1,D_1,E\}$是最有解，就只搜索$\{B_1,C_1\}$、$\{B_2,C_1\}$、$\{B_3,C_1\}$ 而是搜索全部從B到C的9條可選路徑，只是對于上一輪,如果從$C_1$出發這取上一輪$C_1$的最優解，同理$C_2$、$C_3$

DTW算法備注：

2. python代碼實現

s = [1,2,3,4,5] t = [1,1,2,3,4,5]#構筑矩陣 # [[0, 1, 4, 9, 16], [0, 1, 4, 9, 16], [1, 0, 1, 4, 9], # [4, 1, 0, 1, 4], [9, 4, 1, 0, 1], [16, 9, 4, 1, 0]]def _get_min_in_three(x,y,z):min = x if x < y else ymin = min if min < z else zreturn mindef _do_dtw(s, t):#1. 構筑距離矩陣AA = [[0 for i in range(len(s))] for j in range(len(t))]for i in range(len(s)):for j in range(len(t)):A[j][i] = abs(s[i] - t[j])#2. 采用動態規劃所搜最短路徑#移動的路徑是從矩陣的左上角移動到右下角D = [[0 for i in range(len(s))] for j in range(len(t))]for i in range(len(s)):for j in range(len(t)):if 0 == i and 0 == j:D[j][i] = 0elif j == 0: # 貼列D[j][i] = A[j][i] + D[j][i - 1]elif i == 0: #貼行D[j][i] = A[j][i] + D[j - 1][i]else:# D[j-1,i-1] D[j-1, i]# D[j,i-1] D[j, i ]# 這里 D[j, i ] 為 D[j-1][i-1] D[j-1[i] D[j[i-1] 中最小值 + A[j][i]D[j][i] = _get_min_in_three(D[j-1][i-1],D[j-1][i],D[j][i-1]) + A[j][i]return A, DA, D = _do_dtw(s, t)

總結

以上是生活随笔為你收集整理的【语音信号处理四】DTW算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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