DTW可以計(jì)算兩個(gè)時(shí)間序列的相似度，尤其適用于不同長度敏弃、不同節(jié)奏的時(shí)間序列（比如不同的人讀同一個(gè)詞的音頻序列）笛辟。DTW將自動(dòng)warping扭曲 時(shí)間序列（即在時(shí)間軸上進(jìn)行局部的縮放），使得兩個(gè)序列的形態(tài)盡可能的一致宫患，得到最大可能的相似度刊懈。

DTW采用了動(dòng)態(tài)規(guī)劃DP（dynamic programming）的方法來進(jìn)行時(shí)間規(guī)整的計(jì)算，可以說娃闲，動(dòng)態(tài)規(guī)劃方法在時(shí)間規(guī)整問題上的應(yīng)用就是DTW虚汛。

下面測(cè)試程序顯示了 6組時(shí)間序列 的DTW結(jié)果，左上和右下的兩組相似度較高皇帮，其DTW計(jì)算的距離（Warping Distance）也確實(shí)比較小卷哩。

本文以下內(nèi)容絕大部分轉(zhuǎn)載自 http://blog.csdn.net/zouxy09/article/details/9140207

Dynamic Time Warping（DTW）誕生有一定的歷史了（日本學(xué)者Itakura提出），它出現(xiàn)的目的也比較單純属拾，是一種衡量?jī)蓚€(gè)長度不同的時(shí)間序列的相似度的方法将谊。應(yīng)用也比較廣冷溶，主要是在模板匹配中，比如說用在孤立詞語音識(shí)別（識(shí)別兩段語音是否表示同一個(gè)單詞）瓢娜，手勢(shì)識(shí)別挂洛，數(shù)據(jù)挖掘和信息檢索等中。

一眠砾、概述

在大部分的學(xué)科中虏劲，時(shí)間序列是數(shù)據(jù)的一種常見表示形式。對(duì)于時(shí)間序列處理來說褒颈，一個(gè)普遍的任務(wù)就是比較兩個(gè)序列的相似性柒巫。

在時(shí)間序列中，需要比較相似性的兩段時(shí)間序列的長度可能并不相等谷丸，在語音識(shí)別領(lǐng)域表現(xiàn)為不同人的語速不同堡掏。因?yàn)檎Z音信號(hào)具有相當(dāng)大的隨機(jī)性，即使同一個(gè)人在不同時(shí)刻發(fā)同一個(gè)音刨疼，也不可能具有完全的時(shí)間長度泉唁。而且同一個(gè)單詞內(nèi)的不同音素的發(fā)音速度也不同，比如有的人會(huì)把“A”這個(gè)音拖得很長揩慕，或者把“i”發(fā)的很短亭畜。在這些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離無法有效地求的兩個(gè)時(shí)間序列之間的距離（或者相似性）迎卤。

例如圖A所示拴鸵，實(shí)線和虛線分別是同一個(gè)詞“pen”的兩個(gè)語音波形（在y軸上拉開了，以便觀察）蜗搔【⒚辏可以看到他們整體上的波形形狀很相似，但在時(shí)間軸上卻是不對(duì)齊的樟凄。例如在第20個(gè)時(shí)間點(diǎn)的時(shí)候聘芜，實(shí)線波形的a點(diǎn)會(huì)對(duì)應(yīng)于虛線波形的b’點(diǎn)，這樣傳統(tǒng)的通過比較距離來計(jì)算相似性很明顯不靠譜缝龄。因?yàn)楹苊黠@厉膀，實(shí)線的a點(diǎn)對(duì)應(yīng)虛線的b點(diǎn)才是正確的。而在圖B中二拐，DTW就可以通過找到這兩個(gè)波形對(duì)齊的點(diǎn)，這樣計(jì)算它們的距離才是正確的凳兵。

也就是說百新，大部分情況下，兩個(gè)序列整體上具有非常相似的形狀庐扫，但是這些形狀在x軸上并不是對(duì)齊的饭望。所以我們?cè)诒容^他們的相似度之前仗哨，需要將其中一個(gè)（或者兩個(gè)）序列在時(shí)間軸下warping扭曲，以達(dá)到更好的對(duì)齊铅辞。而DTW就是實(shí)現(xiàn)這種warping扭曲的一種有效方法厌漂。DTW通過把時(shí)間序列進(jìn)行延伸和縮短，來計(jì)算兩個(gè)時(shí)間序列性之間的相似性斟珊。

那如果才知道兩個(gè)波形是對(duì)齊了呢苇倡？也就是說怎么樣的warping才是正確的？直觀上理解囤踩，當(dāng)然是warping一個(gè)序列后可以與另一個(gè)序列重合recover旨椒。這個(gè)時(shí)候兩個(gè)序列中所有對(duì)應(yīng)點(diǎn)的距離之和是最小的。所以從直觀上理解堵漱，warping的正確性一般指“feature to feature”的對(duì)齊旺隙。

二仇参、動(dòng)態(tài)時(shí)間規(guī)整DTW

動(dòng)態(tài)時(shí)間規(guī)整DTW是一個(gè)典型的優(yōu)化問題，它用滿足一定條件的的時(shí)間規(guī)整函數(shù)W(n)描述測(cè)試模板和參考模板的時(shí)間對(duì)應(yīng)關(guān)系，求解兩模板匹配時(shí)累計(jì)距離最小所對(duì)應(yīng)的規(guī)整函數(shù)审丘。

假設(shè)我們有兩個(gè)時(shí)間序列Q和C，他們的長度分別是n和m：（實(shí)際語音匹配運(yùn)用中订讼，一個(gè)序列為參考模板浮定，一個(gè)序列為測(cè)試模板，序列中的每個(gè)點(diǎn)的值為語音序列中每一幀的特征值岛杀。例如語音序列Q共有n幀阔拳，第i幀的特征值（一個(gè)數(shù)或者一個(gè)向量）是q_i。至于取什么特征类嗤，在這里不影響DTW的討論糊肠。我們需要的是匹配這兩個(gè)語音序列的相似性，以達(dá)到識(shí)別我們的測(cè)試語音是哪個(gè)詞）

Q= q₁, q₂,…,q_i,…, q_n ;
C= c₁, c₂,…, c_j,…, c_m ;

首先遗锣，我們依然采用兩個(gè)序列中每一對(duì)“點(diǎn)”之間的距離來計(jì)算形似度货裹，即使兩個(gè)序列中的點(diǎn)的個(gè)數(shù)可能不一樣。不過精偿，因?yàn)榭梢詗arping規(guī)整時(shí)間軸弧圆，所以，我們并不是在兩個(gè)序列中依次取一對(duì)點(diǎn)來計(jì)算距離笔咽，而是每個(gè)點(diǎn)有可能對(duì)應(yīng)于另一個(gè)序列中的多個(gè)點(diǎn)搔预。從上面圖B可以看到這種一對(duì)多的情況。

當(dāng)然叶组，這種warping有一定要求拯田，每個(gè)點(diǎn)都必須用到，不可跳過甩十，要按照原始的次序船庇，點(diǎn)對(duì)不可交叉吭产。即要滿足下面描述的 邊界條件、連續(xù)性鸭轮、單調(diào)性臣淤。

關(guān)于每一對(duì)點(diǎn)的距離計(jì)算，這個(gè)距離的算法并無規(guī)定窃爷，依賴于每個(gè)“點(diǎn)”的性質(zhì)來選擇邑蒋，一個(gè)“點(diǎn)”可以是單個(gè)數(shù)值，也可以是一個(gè)多維向量吞鸭。在簡(jiǎn)單的情況下寺董，可以計(jì)算兩個(gè)點(diǎn)的歐氏距離作為這一對(duì)點(diǎn)的距離。

理論上可以窮舉兩個(gè)序列的所有可能的warping 形式刻剥，逐一計(jì)算兩者距離遮咖，距離最小的就是所要求的warping，但這樣計(jì)算量太大造虏，所以采用動(dòng)態(tài)規(guī)劃的方法來高效的完成計(jì)算御吞。

我們需要將連個(gè)序列對(duì)齊。最簡(jiǎn)單的對(duì)齊方式就是線性縮放了漓藕。把短的序列線性放大到和長序列一樣的長度再比較陶珠，或者把長的線性縮短到和短序列一樣的長度再比較。但是這樣的計(jì)算沒有考慮到語音中各個(gè)段在不同情況下的持續(xù)時(shí)間會(huì)產(chǎn)生或長或短的變化享钞，因此識(shí)別效果不可能最佳揍诽。因此更多的是采用動(dòng)態(tài)規(guī)劃（dynamic programming）的方法。

為了對(duì)齊這兩個(gè)序列栗竖，我們需要構(gòu)造一個(gè)n x m的矩陣網(wǎng)格暑脆，矩陣元素(i, j)表示q_i和c_j兩個(gè)點(diǎn)的距離d(q_i, c_j)（也就是序列Q的每一個(gè)點(diǎn)和C的每一個(gè)點(diǎn)之間的相似度，距離越小則相似度越高狐肢。這里先不管順序）添吗，一般采用歐式距離，d(q_i, c_j)= (q_i-c_j)²（也可以理解為失真度）份名。每一個(gè)矩陣元素(i, j)表示點(diǎn)q_i和c_j的對(duì)齊碟联。DP算法可以歸結(jié)為尋找一條通過此網(wǎng)格中若干格點(diǎn)的路徑，路徑通過的格點(diǎn)即為兩個(gè)序列進(jìn)行計(jì)算的對(duì)齊的點(diǎn)僵腺。

那么這條路徑我們?cè)趺凑业侥乩鸱酰磕菞l路徑才是最好的呢？也就是剛才那個(gè)問題辰如，怎么樣的warping才是最好的普监。

我們把這條路徑定義為warping path規(guī)整路徑，并用W來表示， W的第k個(gè)元素定義為w_k=(i,j)_k鹰椒，定義了序列Q和C的映射。這樣我們有：

首先呕童，這條路徑不是隨意選擇的漆际，需要滿足以下幾個(gè)約束：

1）邊界條件：w₁=(1, 1)和w_K=(m, n)。任何一種語音的發(fā)音快慢都有可能變化夺饲，但是其各部分的先后次序不可能改變奸汇，因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束往声。

2）連續(xù)性：如果w_k-1= (a’, b’)擂找，那么對(duì)于路徑的下一個(gè)點(diǎn)w_k=(a, b)需要滿足 (a-a’) <=1和 (b-b’) <=1。也就是不可能跨過某個(gè)點(diǎn)去匹配浩销，只能和自己相鄰的點(diǎn)對(duì)齊贯涎。這樣可以保證Q和C中的每個(gè)坐標(biāo)都在W中出現(xiàn)。

3）單調(diào)性：如果w_k-1= (a’, b’)慢洋，那么對(duì)于路徑的下一個(gè)點(diǎn)w_k=(a, b)需要滿足0<=(a-a’)和0<= (b-b’)塘雳。這限制W上面的點(diǎn)必須是隨著時(shí)間單調(diào)進(jìn)行的。以保證圖B中的虛線不會(huì)相交普筹。

結(jié)合連續(xù)性和單調(diào)性約束败明，每一個(gè)格點(diǎn)的路徑就只有三個(gè)方向了。例如如果路徑已經(jīng)通過了格點(diǎn)(i, j)太防，那么下一個(gè)通過的格點(diǎn)只可能是下列三種情況之一：(i+1, j)妻顶，(i, j+1)或者(i+1, j+1)。

滿足上面這些約束條件的路徑可以有指數(shù)個(gè)蜒车，然后我們感興趣的是使得下面的規(guī)整代價(jià)最小的路徑：

分母中的K主要是用來對(duì)不同的長度的規(guī)整路徑做補(bǔ)償讳嘱。因?yàn)椴煌穆窂狡溟L短不同，較長的路徑有較多的“點(diǎn)對(duì)”醇王，會(huì)有較多的距離累加上去呢燥，所以總距離除以K得到單位路徑的距離。

我們的目的是什么寓娩？或者說DTW的思想是什么叛氨？是把兩個(gè)時(shí)間序列進(jìn)行延伸和縮短，來得到兩個(gè)時(shí)間序列性距離最短也就是最相似的那一個(gè)warping棘伴，這個(gè)最短的距離也就是這兩個(gè)時(shí)間序列的最后的距離度量寞埠。在這里，我們要做的就是選擇一個(gè)路徑焊夸，使得最后得到的總的距離最小仁连。

這里我們定義一個(gè)累加距離cumulative distances。從(0, 0)點(diǎn)開始匹配這兩個(gè)序列Q和C，每到一個(gè)點(diǎn)饭冬，之前所有的點(diǎn)計(jì)算的距離都會(huì)累加使鹅。到達(dá)終點(diǎn)(n, m)后，這個(gè)累積距離就是我們上面說的最后的總的距離昌抠，也就是序列Q和C的相似度患朱。

累積距離γ(i,j)可以按下面的方式表示，累積距離γ(i,j)為當(dāng)前格點(diǎn)距離d(i,j)炊苫，也就是點(diǎn)q_i和c_j的歐式距離（相似性）與可以到達(dá)該點(diǎn)的最小的鄰近元素的累積距離之和：

最佳路徑是使得沿路徑的積累距離達(dá)到最小值這條路徑裁厅。這條路徑可以通過動(dòng)態(tài)規(guī)劃（dynamic programming）算法得到。

具體搜索或者求解過程的直觀例子解釋可以參考：

http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html

三侨艾、DTW在語音中的運(yùn)用

假定一個(gè)孤立字（詞）語音識(shí)別系統(tǒng)执虹，利用模板匹配法進(jìn)行識(shí)別。這時(shí)一般是把整個(gè)單詞作為識(shí)別單元唠梨。在訓(xùn)練階段袋励，用戶將詞匯表中的每一個(gè)單詞說一遍，提取特征后作為一個(gè)模板姻成，存入模板庫插龄。在識(shí)別階段，對(duì)一個(gè)新來的需要識(shí)別的詞科展，也同樣提取特征均牢，然后采用DTW算法和模板庫中的每一個(gè)模板進(jìn)行匹配，計(jì)算距離才睹。求出最短距離也就是最相似的那個(gè)就是識(shí)別出來的字了徘跪。

四、參考資料

[1] http://baike.baidu.com/view/1647336.htm

[2] http://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html

[3] http://www.cnblogs.com/luxiaoxun/archive/2013/05/09/3069036.html (有matlab/C++ code)

[4] Eamonn J. Keogh, Derivative Dynamic Time Warping

[5]趙立《語音信號(hào)處理》