時間序列資料的可衍伸出的應用問題相當多，例如語音辨識及圖像辨識。而其中的關鍵核心就在於相似度比對。用來處理相似度比對的演算法非常多種，一般常用 Euclidean Distance(歐幾里德距離)來計算其距離藉以作為相似度比較的評估。而本單元要介紹的是準確度更高的動態時間扭曲(Dynamic Time Wraping, DTW )演算法。
在時間軸固定的前提下，通常比對兩筆時間序列資料，都是一個資料點對一個資料點的去計算距離(如圖)
在時間軸固定的前提下，一對一比對，為線性。
但有時候，兩筆資料間會有時間上的不匹配，及時間軸的不固定。此時若比照一對一去計算距離的方法，得到的答案將是不準確的。也因此，有了態時間扭曲(Dynamic Time Wraping, DTW )演算法。
時間軸不固定，非線性
DTW的宗旨在於提高時間的彈性空間，使資料能夠透過伸展或壓縮去彌補資料間時間上的不匹配，藉以找到最小誤差的非線性對應。
DTW的做法:
DTW的目標就是要在時間軸不固定的前提下，找出兩個向量間的距離。假設有兩個向量t和r，長度分別是m和n，那麼 DTW 的目標，就是要找到一組路徑 (p1, q1), (p2, q2), ..., (pk, qk)}, 使得經由上述路徑的「點對點」對應距離和為最小，另外，此路徑必須滿足下列條件:
1.(p1, q1) = (1, 1), (pk, qk) = (m, n)。此端點關係代表這是"頭對頭、尾對尾"的
比對
2. 假設最佳路徑上任一點可以表示成 (i, j)，那麼其前一點路徑只有三種可能，
(i-1, j), (i, j-1), (i-1, j-1)。此局部關係定義了路徑的連續性
DTW的目標就是要在時間軸不固定的前提下，找出兩個向量間的距離。假設有兩個向量t和r，長度分別是m和n，那麼 DTW 的目標，就是要找到一組路徑 (p1, q1), (p2, q2), ..., (pk, qk)}, 使得經由上述路徑的「點對點」對應距離和為最小，另外，此路徑必須滿足下列條件:
1.(p1, q1) = (1, 1), (pk, qk) = (m, n)。此端點關係代表這是"頭對頭、尾對尾"的
比對
2. 假設最佳路徑上任一點可以表示成 (i, j)，那麼其前一點路徑只有三種可能，
(i-1, j), (i, j-1), (i-1, j-1)。此局部關係定義了路徑的連續性
接著，將找到此路徑的DTW演算法描述成四個步驟。
1. 目標函數之定義：定義 D(i, j) 是 t(1:i) 和 r(1:j) 之間的 DTW 距離，對應
的最佳路徑是由 (1, 1) 走到 (i, j)。
2. 目標函數之回溯關係：D(i, j) =∣t(i) - r(j)∣+ min{D(i-1, j), D(i-1, j-1), D(i, j-1)}
3. 端點條件：D(1, 1) = ∣t(1) - r(1)∣
4. 最後答案：D(m, n)
1. 目標函數之定義：定義 D(i, j) 是 t(1:i) 和 r(1:j) 之間的 DTW 距離，對應
的最佳路徑是由 (1, 1) 走到 (i, j)。
2. 目標函數之回溯關係：D(i, j) =∣t(i) - r(j)∣+ min{D(i-1, j), D(i-1, j-1), D(i, j-1)}
3. 端點條件：D(1, 1) = ∣t(1) - r(1)∣
4. 最後答案：D(m, n)
在實際運算時，通常會事先建立一個矩陣 D，其維度為 m×n，先根據端點條件來填入 D(1, 1)，然後再利用回溯關係，逐行或逐列算出 D(i, j) 的值，最後得出答案 D(m, n)。
利用回溯找出最佳路徑
DTW在比對演算法中屬於準確度相當高的一種，但由於其空間複雜度為O(mxn)。且每個D矩陣的點都至少要做兩次比較，才能從前面三個點中取得最小值。以至於非常耗費時間。尤其當資料量龐大的情況下，此缺點將更加明顯。因此，在解決不同問題或比對資料時，可能要依狀況來尋求不同模式的演算法來解決這個問題
作者已經移除這則留言。
回覆刪除