轉載位址：http://www.cnphp6.com/archives/60574
1、應用
在大部分的學科中，時間序列是資料的一種常見表示形式。對于時間序列處理來說，一個普遍的任務就是比較兩個序列的相似性。
在時間序列中，需要比較相似性的兩段時間序列的長度可能并不相等，在語音識别領域表現為不同人的語速不同。因為語音信号具有相當大随機性，即使同一個人在不同時刻發同一個音，也不可能具有完全的時間長度。而且同一個單詞内的不同音素的發音速度也不同，比如有的人會把'A'這個音拖得很長，或者把’i'這個音發的很短。在這些負責的情況下，使用傳統的歐幾裡得距離無法有效地求出兩個時間序列之間的距離（或者相似性）
例如圖A所示，實線和虛線分貝時同一個詞“pen”的兩個語音波形（在y軸上拉開了，以便觀察）。可以看到他們整體上的波形形狀很相似，單在時間軸卻是不對齊的。例如在第20個時間點的時候，實線波形上的a點對應于虛線波形的b'點，這樣傳統的通過比較距離來計算相似性很明顯不靠譜。因為很明顯，實線的a點對應虛線的b點才是正确的。而在圖B中，DTW就可以通過找到這兩個波形對齊的點，這樣計算它們的距離才是正确的。
也就是說，大部分情況下，兩個序列整體上具有非常相似的形狀，但是這些形狀在x軸上并不是對齊的。是以我們在比較他們的相似度之前，需要将其中一個（或者兩個）序列在時間軸下warping扭曲，已以達到更好的對齊。而DTW就是實作這種warping扭曲的一種有效方法。DTW通過将時間序列進行延伸和縮短，來計算兩個時間序列之間的相似性。
那如何才知道兩個波形是對齊了呢？也就是說怎麼樣的warping才是正确的？直覺上了解，當然是waring一個序列後可以和另一個序列重合recover。這個時候兩個序列中所有對應的距離之和是最小的。是以從直覺上了解，warping的正确性一般指“feature to feature”的對齊。
注明：由B）圖可以看出，模闆序列中的一個點（這裡的點可能是單個數值或是一個向量）可能對應測試序列中的好幾個點（也有可能反過來，模闆中的好幾個點對應測試中的一個點），這正好反映了特征可能的延遲性。比如同一個音素，有的時候發得快，有的時候發的慢。這兩種情況進行比對時，你要把發得快的那個點完全比對到發的慢的那幾個點上。
2、原理
動态時間規整DTW是一個典型的優化問題，它用滿足一定條件得時間規整函數W(n)描述測試模闆和參考模闆的時間對應關系，求解兩模闆比對時累計距離最小所對應的規整函數。
假設我們有兩個時間序列Q和C，他們的長度分别是n和m：（實際語音比對運用中，一個序列為參考模闆，一個序列為測試模闆，序列中的每個點的值為語音序列中每一幀的特征值。例如語音序列Q共有n幀，第i幀的特征值（一個數或者一個向量）是qi。至于取什麼特征，在這裡不影響DTW的讨論。我們需要的是比對這兩個語音序列的相似性，以達到識别我們的測試語音是哪個詞）
Q = q1, q2,…,qi,…, qn ;
C = c1, c2,…, cj,…, cm ;
如果n=m，那麼就用不着折騰了，直接計算兩個序列的距離就好了。但如果n不等于m我 們就需要對齊。最簡單的對齊方式就是線性縮放了。把短的序列線性放大到和長序列一樣的長度再比較，或者把長的線性縮短到和短序列一樣的長度再比較。但是這 樣的計算沒有考慮到語音中各個段在不同情況下的持續時間會産生或長或短的變化，是以識别效果不可能最佳。是以更多的是采用動态規劃（dynamic programming）的方法。
為了對齊這兩個序列，我們需要構造一個 n x m 的矩陣網格，矩陣元素 (i, j) 表示 qi 和 cj 兩個點的距離 d(qi, cj) （也就是序列 Q 的每一個點和 C 的每一個點之間的相似度，距離越小則相似度越高。這裡先不管順序），一般采用歐式距離， d(qi, cj)= (qi-cj)2 （也可以了解為失真度）。每一個矩陣元素 (i, j) 表示點 qi 和 cj 的對齊。 DP 算法可以歸結為尋找一條通過此網格中若幹格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。
那麼這條路徑我們怎麼找到呢？那條路徑才是最好的呢？也就是剛才那個問題，怎麼樣的warping才是最好的。
注明：兩個序列長度不同，不能使用歐氏距離進行比對。使用dtw時，上圖方格中的每個連續的點（開頭（1，1）和結尾（m，n）還是要保證的）構成的曲線都有可能，這是就要找出代價最小的那條曲線，如圖中标出的黑色曲線。
我們把這條路徑定義為warping path規整路徑，并用W來表示， W的第k個元素定義為wk=(i,j)k，定義了序列Q和C的映射。這樣我們有：
1）邊界條件：w1=(1, 1)和wK=(m, n)。任何一種語音的發音快慢都有可能變化，但是其各部分的先後次序不可能改變，是以所選的路徑必定是從左下角出發，在右上角結束。
2）連續性：如果wk-1= (a’, b’)，那麼對于路徑的下一個點wk=(a, b)需要滿足(a-a’) <=1和 (b-b’) <=1。也就是不可能跨過某個點去比對，隻能和自己相鄰的點對齊。這樣可以保證Q和C中的每個坐标都在W中出現。
3）單調性：如果wk-1= (a’, b’)，那麼對于路徑的下一個點wk=(a, b)需要滿足0<=(a-a’)和0<= (b-b’)。這限制W上面的點必須是随着時間單調進行的。以保證圖B中的虛線不會相交。
結合連續性和單調性限制，每一個格點的路徑就隻有三個方向了。例如如果路徑已經通過了格點(i, j)，那麼下一個通過的格點隻可能是下列三種情況之一：(i+1, j)，(i, j+1)或者(i+1, j+1)
滿足上面這些限制條件的路徑可以有指數個，然後我們感興趣的是使得下面的規整代價最小的路徑：
分母中的K主要是用來對不同的長度的規整路徑做補償。我們的目的是什麼？或者說DTW的思想是什麼？是把兩個時間序列進行延伸和縮短，來得到兩個時間序列性距離最短也就是最相似的那一個warping，這個最短的距離也就是這兩個時間序列的最後的距離度量。在這裡，我們要做的就是選擇一個路徑，使得最後得到的總的距離最小。
這裡我們定義一個累加距離cumulative distances。從(0, 0)點開始比對這兩個序列Q和C，每到一個點，之前所有的點計算的距離都會累加。到達終點(n, m)後，這個累積距離就是我們上面說的最後的總的距離，也就是序列Q和C的相似度。
累積距離γ(i,j)可以按下面的方式表示，累積距離γ(i,j)為目前格點距離d(i,j)，也就是點qi和cj的歐式距離（相似性）與可以到達該點的最小的鄰近元素的累積距離之和：
注明：先把模闆序列和測試序列的每個點相對應的距離算出來，構成一個m xn的矩陣。然後根據每個元素的代價計算一條最短路徑。這裡的計算要符合以上三個限制。即，一個點的代價=這個點的值+來自min{下、左、斜下這三個方向的值}。下、左、斜下這三個方向的值可以依次遞歸求得，直到（1，1）點
3、例子
這個例子中假設标準模闆R為字母ABCDEF(6個)，測試模闆T為1234(4個)。R和T中各元素之間的距離已經給出。如下：
既然是模闆比對，是以各分量的先後比對順序已經确定了，雖然不是一一對應的。現在題目的目的是要計算出測試模闆T和标準模闆R之間的距離。因為2個模闆的 長度不同，是以其對應比對的關系有很多種，我們需要找出其中距離最短的那條比對路徑。現假設題目滿足如下的限制：當從一個方格((i-1,j-1)或者 (i-1,j)或者(i,j-1))中到下一個方格(i,j)，如果是橫着或者豎着的話其距離為d(i,j)，如果是斜着對角線過來的則是 2d(i,j).其限制條件如下圖像所示：
其中g(i,j)表示2個模闆都從起始分量逐次比對，已經到了M中的i分量和T中的j分量，并且比對到此步是2個模闆之間的距離。并且都是在前一次比對的結果上加d(i,j)或者2d(i,j),然後取最小值。
是以我們将所有的比對步驟标注後如下
怎麼得來的呢？比如說g(1,1)=4, 當然前提都假設是g(0,0)=0,就是說g(1,1)=g(0,0)+2d(1,1)=0+2*2=4.
g(2,2)=9是一樣的道理。首先如果從g(1,2)來算的話是g(2,2)=g(1,2)+d(2,2)=5+4=9,因為是豎着上去的。
如果從g(2,1)來算的話是g(2,2)=g(2,1)+d(2,2)=7+4=11,因為是橫着往右走的。
如果從g(1,1)來算的話，g(2,2)=g(1,1)+2*d(2,2)=4+2*4=12.因為是斜着過去的。
綜上所述，取最小值為9. 所有g(2,2)=9.
當然在這之前要計算出g(1,1),g(2,1),g(1,2).是以計算g(I,j)也是有一定順序的。
其基本順序可以展現在如下：
計算了第一排，其中每一個紅色的箭頭表示最小值來源的那個方向。當計算了第二排後的結果如下：
最後都算完了的結果如下：
到此為止，我們已經得到了答案，即2個模闆直接的距離為26. 我們還可以通過回溯找到最短距離的路徑，通過箭頭方向反推回去。如下所示：
注明：不管哪個方向，我都隻加上了其本身的數值，即d（i j），沒有x2.得出的路徑是一樣的。