dtw算法主要針對序列匹配提出的，尤其是當序列出現一定的飄移，歐氏距離度量就會失效。dtw常用在語音匹配當中，在圖像處理里面也有一定的應用。
現在有兩個序列X,Y.
X=[2,3,4,7,9,2,1,2,1],Y=[1,1,1,1,2,3,3,4,7,8,9,1,1,1,1]
繪制在坐標軸上如下圖

我們可以看到，兩個序列的歐氏距離很大，因為兩個序列存在橫軸上的飄移。dtw算法就是為了解決此類問題，簡單的說dtw算法就是將兩個序列在某些時點上壓縮，實現兩個序列之間的“距離”最小，這里這個距離一般使用歐氏距離。
dtw算法本質是尋找一條從X[0],Y[0]到X[N],Y[M]的最短的路徑。對于上面給出的序列X,Y。找到的壓縮路徑是[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 5), (1, 6), (2, 7), (3, 8), (4, 9), (4, 10), (5, 11), (6, 11), (6, 12), (6, 13), (6, 14), (7, 14), (8, 14)]。對應的壓縮關系繪制成圖（有點丑，將就看吧）

說了結果，下面我們來找這個壓縮路徑。

這個算法有幾個約束，但簡而言之就是得從X[0],Y[0]走到X[N],Y[M]，即從上圖中的左下角走到右上角。
貪心算法，并不能求得全局最優解，剛開始把這個問題做成了貪心算法，后來想想不太對，就去惡補了動態規劃。下面是貪心算法的錯誤求解。
每走一步，都是選擇距離增加最少的走，并且只有三個方向，向上，向右，向斜對角。這樣就保證不會往回走已經走過的路徑。假設X,Y構成的N*M的矩陣是距離矩陣D，如上圖。那么我們從D[0][0]點走到D[9][14]（有9列，14行（這里以列為主序）)。那么我們開始計算前幾步該如何走，D[0][0]=abs(Y[0]-X[0])=1,，下一步有三個方向，向上D[0][1]=D[0][0]+abs(Y[1]-X[0])=2,向右D[1][0]=D[0][0]+abs(Y[0]-X[1])=3,向斜對角D[1][1]=D[0][0]+abs(Y[1]-X[1])=3。取距離最小，所以選擇向上，依次類推，最后得到上圖的結果，這就是壓縮路徑，最終兩個序列之間的距離是7。ps:中間可能會遇到向上，向右，像斜上方的距離相等的情況，那么隨便選擇一個方向即可，路徑不一樣，但是最終的距離都是相等的。
按照自己思路寫出dtw算法如下，時間復雜度是O(N+M)。

def Distance(x,y):return abs(x-y) def Dtw(X,Y):Lx=len(X)Ly=len(Y)D=[[sys.maxint for i in range(Lx)]for j in range(Ly)]minD=0j=0k=0path=[(0,0)]for i in range(Lx+Ly):if (j == Ly-1) and (k == Lx-1):breakelif (j==Ly-1) and (k != Lx-1):k += 1D[j][k]=D[j][k-1]+Distance(Y[j],X[k])elif (j != Ly-1) and (k == Lx-1):j += 1D[j][k]=D[j-1][k]+Distance(Y[j],X[k])else:if j==0 and k==0:D[j][k]=Distance(Y[j],X[k])D[j+1][k]=Distance(Y[j+1],X[k])+D[j][k]D[j][k+1]=Distance(Y[j],X[k+1])+D[j][k]D[j+1][k+1]=Distance(Y[j+1],X[k+1])+D[j][k]if(D[j+1][k]<D[j][k+1]):minD=D[j+1][k]if(minD>D[j+1][k+1]):j += 1k += 1else:j += 1else:minD=D[j][k+1]if(minD>D[j+1][k+1]):j += 1k += 1else:k += 1path.append((k,j))minD=D[j][k]return minD,path

動態規劃
仔細分析，其實該過程的最優解用dp可以實現，狀態轉換方程為
D(i,j)=M[i][j]+min(D[i-1][j],D[i][j-1],D[i-1][j-1])。

def dtw(X,Y):Lx=len(X)Ly=len(Y)path=[]M=[[Distance(X[i],Y[j]) for i in range(Lx)]for j in range(Ly)]D=[[0 for i in range(Lx+1)]for j in range(Ly+1)]D[0][0]=0for i in range(1,Lx+1):D[0][i]=sys.maxintfor j in range(1,Ly+1):D[j][0]=sys.maxintfor i in range(1,Ly+1):for j in range(1,Lx+1):D[i][j]=M[i-1][j-1]+min(D[i-1][j],D[i-1][j-1],D[i][j-1])minD=D[Ly][Lx]return minD

總結

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

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