原帖在這里，這篇是我的閱讀筆記，非原創(chuàng)。

目錄

• 面臨的問(wèn)題
• DTW算法簡(jiǎn)介
• DTW要去解決的問(wèn)題
• DTW存在的問(wèn)題
• 總結(jié)

面臨的問(wèn)題

當(dāng)數(shù)據(jù)在時(shí)間線上不對(duì)齊的時(shí)候聊训，使用傳統(tǒng)的匹配方法，是無(wú)法使用傳統(tǒng)的全局匹配度量法的恢氯。

DTW算法簡(jiǎn)介

兩個(gè)人分別說(shuō)了同一個(gè)單詞带斑，但是由于語(yǔ)速、語(yǔ)氣勋拟、語(yǔ)調(diào)等等各不相同勋磕，會(huì)導(dǎo)致采樣得到的數(shù)據(jù)無(wú)法對(duì)齊。但是兩段語(yǔ)音采樣的第一個(gè)采樣值和最后一個(gè)采樣值肯定是兩兩對(duì)應(yīng)的敢靡。

給出兩個(gè)序列：

image.png

Warping通常采用動(dòng)態(tài)規(guī)劃算法挂滓。為了對(duì)齊這兩個(gè)序列，我們需要構(gòu)造一個(gè)n x m的矩陣網(wǎng)格啸胧，矩陣元素(i, j)表示qi和cj兩個(gè)點(diǎn)的距離d(qi, cj)杂彭，一般采用歐式距離，d(qi, cj)= (qi-cj)2（也可以理解為失真度）吓揪。每一個(gè)矩陣元素(i, j)表示點(diǎn)qi和cj的對(duì)齊。

DP(dynamic programming)算法可以歸結(jié)為尋找一條通過(guò)此網(wǎng)格中若干格點(diǎn)的路徑所计，路徑通過(guò)的格點(diǎn)即為兩個(gè)序列進(jìn)行計(jì)算的對(duì)齊的點(diǎn)柠辞。

有三個(gè)性質(zhì)：

1）邊界條件：w1=(1, 1)和wK=(m, n)。兩個(gè)人分別說(shuō)了同一個(gè)單詞主胧，但是由于語(yǔ)速叭首、語(yǔ)氣、語(yǔ)調(diào)等等各不相同踪栋，會(huì)導(dǎo)致采樣得到的數(shù)據(jù)無(wú)法對(duì)齊焙格。但是兩段語(yǔ)音采樣的第一個(gè)采樣值和最后一個(gè)采樣值肯定是兩兩對(duì)應(yīng)的。因此所選的路徑必定是從左下角出發(fā)夷都，在右上角結(jié)束眷唉。

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

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

由連續(xù)性和單調(diào)性可知饲常，每次格點(diǎn)(i, j)前進(jìn)方向只有三種：(i+1, j)，(i, j+1) 或 (i+1, j+1)狼讨。我們的目的是使得下面的規(guī)整代價(jià)最小的路徑：

image.png

分母中的K主要是用來(lái)對(duì)不同的長(zhǎng)度的規(guī)整路徑做補(bǔ)償贝淤。

這里我們定義一個(gè)累加距離(cumulative distances)。從(0, 0)點(diǎn)開始匹配這兩個(gè)序列Q和C熊楼，每到一個(gè)點(diǎn)霹娄，之前所有的點(diǎn)計(jì)算的距離都會(huì)累加。到達(dá)終點(diǎn)(n, m)后鲫骗，這個(gè)累積距離就是我們上面說(shuō)的最后的總的距離犬耻，也就是序列Q和C的相似度。

示例：

對(duì)于兩個(gè)序列：

X：3执泰，5枕磁，6，7术吝，7计济，1

Y：3，6排苍，6沦寂，7，8淘衙，1传藏，1

有距離矩陣：

X和Y的距離矩陣：

然后根據(jù)距離矩陣生成1損失矩陣(Cost Matrix)或者叫累積距離矩陣 McMc，其計(jì)算方法如下：

1. 第一行第一列元素為 MM 的第一行第一列元素彤守，在這里就是0毯侦；

2. 其他位置的元素 (Mc(i,j)Mc(i,j))的值則需要逐步計(jì)算，具體值的計(jì)算方法為 Mc(i,j)=Min(Mc(i?1,j?1),Mc(i?1,j),Mc(i,j?1))+M(i,j)Mc(i,j)=Min(Mc(i?1,j?1),Mc(i?1,j),Mc(i,j?1))+M(i,j)具垫，得到的McMc如下：

DTW要去解決的問(wèn)題

DTW就是要去解決侈离，普通的歐氏距離，對(duì)不對(duì)齊的兩個(gè)序列無(wú)法進(jìn)行相似度對(duì)比的問(wèn)題筝蚕。解決的方法就是動(dòng)態(tài)規(guī)劃卦碾，但是并沒有生成更加多余的點(diǎn)，而是進(jìn)行了復(fù)制饰及。

DTW存在的問(wèn)題

DTW實(shí)質(zhì)上是通過(guò)對(duì)軌跡點(diǎn)的復(fù)制實(shí)現(xiàn)的對(duì)軌跡局部的拉伸或者縮放蔗坯，下圖展示地非常清楚：

image.png

DTW通過(guò)迭代的方式計(jì)算軌跡之間的距離（找到圖4 b所示的最佳的軌跡），是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題燎含，其算法復(fù)雜度是O(m × n)宾濒，依舊很高。后期必然需要相應(yīng)的修建策略才能達(dá)到好的效果屏箍。

雖然沒有使用映射绘梦，但是由于使用了重復(fù)橘忱，最終的結(jié)果仍然不是嚴(yán)格的metric，無(wú)法使用metric的方法Ｐ斗睢（DTW “l(fā)oosely” satis?es the triangle inequality. It appears that this observation is not true in general, as on average nearly 30% of all the triplets do not satisfy the triangle inequality.）

“復(fù)制“其實(shí)就是在重復(fù)使用某些點(diǎn)钝诚。以此實(shí)現(xiàn)了對(duì)local time shifting的處理。

沒有閾值限制榄棵，其最終目的只有找到最好的路徑凝颇，但是此路徑的總距離大小可能會(huì)很大。假如不對(duì)離群點(diǎn)進(jìn)行處理疹鳄，此算法依舊將會(huì)對(duì)離群點(diǎn)拧略、異常點(diǎn)很敏感。

算法需要第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)是對(duì)應(yīng)的瘪弓。

錯(cuò)誤示例：

（1）沒有設(shè)置閾值

image.png

此處出現(xiàn)了特定的local time shifting垫蛆，會(huì)導(dǎo)致T2和T3明明是一條軌跡，但是最終出現(xiàn)的結(jié)果會(huì)是T1和T3的相似度要比T1和T2差很多腺怯。而且最終的結(jié)果是絕對(duì)的袱饭，即得到的只有一個(gè)絕對(duì)的數(shù)字，但從這個(gè)數(shù)字上是無(wú)法進(jìn)一步消除這個(gè)誤差的呛占。

（2）直接使用的是原有的軌跡點(diǎn)虑乖，重復(fù)使用，且不會(huì)跳過(guò)任何一個(gè)點(diǎn)晾虑，因此對(duì)噪聲點(diǎn)的抑制并不好决左。

image.png

總結(jié)：

DTW方法是歐氏距離方法的改進(jìn)，只改進(jìn)了其不能處理local time shifting的問(wèn)題走贪。沒有引入任何閾值參數(shù)，因此對(duì)時(shí)間上的偏移（噪聲和離群點(diǎn)）的抑制并不好惑芭，且對(duì)時(shí)間上的偏移的適應(yīng)性也不好坠狡。

優(yōu)點(diǎn)：使用動(dòng)態(tài)規(guī)劃的思想，實(shí)現(xiàn)了對(duì)某些點(diǎn)的重復(fù)使用遂跟，確保重復(fù)使用的點(diǎn)達(dá)成的路徑最優(yōu)的逃沿，從而較為高效地解決了數(shù)據(jù)不對(duì)齊的問(wèn)題。

缺點(diǎn)：還是無(wú)法處理離群點(diǎn)幻锁、異常點(diǎn)凯亮，對(duì)于噪聲的抑制沒有進(jìn)行處理。雖然能夠處理local time shifting哄尔，但是對(duì)時(shí)間上的偏移做的也不好假消。算法也不是metric類型的。