Dynamic Time Warping（DTW）是一種衡量兩個時間序列之間的相似度的方法，主要應用在語音識别領域來識别兩段語音是否表示同一個單詞。
1. DTW方法原理
在時間序列中，需要比較相似性的兩段時間序列的長度可能并不相等，在語音識别領域表現為不同人的語速不同。而且同一個單詞内的不同音素的發音速度也不同，比如有的人會把“A”這個音拖得很長，或者把“i”發的很短。另外，不同時間序列可能僅僅存在時間軸上的位移，亦即在還原位移的情況下，兩個時間序列是一緻的。在這些複雜情況下，使用傳統的歐幾裡得距離無法有效地求的兩個時間序列之間的距離（或者相似性）。
DTW通過把時間序列進行延伸和縮短，來計算兩個時間序列性之間的相似性：
如上圖所示，上下兩條實線代表兩個時間序列，時間序列之間的虛線代表兩個時間序列之間的相似的點。DTW使用所有這些相似點之間的距離的和，稱之為歸整路徑距離(Warp Path Distance)來衡量兩個時間序列之間的相似性。
2. DTW計算方法：
令要計算相似度的兩個時間序列為X和Y，長度分别為|X|和|Y|。
歸整路徑(Warp Path)
歸整路徑的形式為W=w1,w2,...,wK，其中Max(|X|,|Y|)<=K<=|X|+|Y|。
wk的形式為(i,j)，其中i表示的是X中的i坐标，j表示的是Y中的j坐标。
歸整路徑W必須從w1=(1,1)開始，到wK=(|X|,|Y|)結尾，以保證X和Y中的每個坐标都在W中出現。
另外，W中w(i,j)的i和j必須是單調增加的，以保證圖1中的虛線不會相交，所謂單調增加是指：
最後要得到的歸整路徑是距離最短的一個歸整路徑：
最後求得的歸整路徑距離為D(|X|,|Y|)，使用動态規劃來進行求解：
上圖為代價矩陣(Cost Matrix) D，D(i,j)表示長度為i和j的兩個時間序列之間的歸整路徑距離。
3. DTW實作：
matlab代碼：
C++實作：
dtwrecoge.h
View Code
dtwrecoge.cpp
本文轉自阿凡盧部落格園部落格，原文連結：http://www.cnblogs.com/luxiaoxun/archive/2013/05/09/3069036.html，如需轉載請自行聯系原作者