一.目的
時(shí)間序列是數(shù)據(jù)的一種常見表示形式柏卤，對(duì)于處理時(shí)間序列來說县貌，一個(gè)普遍的任務(wù)就是比較兩個(gè)序列的相似性缸夹。但是在實(shí)際問題中痪寻，大部分時(shí)間序列都是不等長的，有的序列可能波形類似虽惭，但是時(shí)間錯(cuò)位橡类。如下圖所示，虛線與實(shí)線波形是類似的趟妥，但是波峰錯(cuò)位猫态，這種情況下，如果直接使用歐式距離來表示時(shí)間序列的相似性顯然不合理。DTW出現(xiàn)的目的很簡單亲雪，就是為了合理的衡量兩條時(shí)間序列的距離（或者說叫相似性）勇凭，而且不要求兩條序列長度相等。
二.簡單理解DTW
簡單來說义辕，DTW就是捏住兩條序列的頭和尾虾标，瘋狂的蹂躪它們，拉伸短的灌砖，壓縮長的璧函，使得它們長度對(duì)齊』裕可是落實(shí)到實(shí)際序列點(diǎn)上怎么才能對(duì)齊呢蘸吓？其實(shí)就是讓序列點(diǎn)間發(fā)生一對(duì)多或者多對(duì)一的對(duì)應(yīng)關(guān)系。如上圖所示撩幽，每個(gè)紅圈點(diǎn)都對(duì)應(yīng)了很多個(gè)點(diǎn)库继，這樣就可以達(dá)到序列對(duì)齊的目的。
現(xiàn)在窜醉，問題就轉(zhuǎn)化成為了宪萄，如何尋找兩條序列上點(diǎn)的對(duì)應(yīng)關(guān)系，且滿足所有對(duì)應(yīng)點(diǎn)間的距離和最小榨惰。這是一個(gè)很明顯的優(yōu)化問題拜英。
三.求解DTW
假設(shè)我們有兩個(gè)時(shí)間序列A和B，他們的長度分別是n和m：
A= a1, a2,…, aj,…, am ;
B = b1, b2,…,bi,…, bn ;
為了對(duì)齊這兩個(gè)序列琅催，我們需要構(gòu)造一個(gè)下圖所示的n x m的矩陣網(wǎng)格居凶，矩陣元素(i, j)表示ai和bj兩個(gè)點(diǎn)的距離dij（也就是序列A的每一個(gè)點(diǎn)和B的每一個(gè)點(diǎn)之間的相似度，距離越小則相似度越高恢暖。）排监，一般采用歐式距離，dij=(ai?bj)**2 杰捂，也可以采用絕對(duì)值距離 Abs（ai-bj）舆床。
現(xiàn)在問題轉(zhuǎn)化成了，從左下角（1,1）位置開始嫁佳，到（n,m）點(diǎn)挨队，找到一條距離和最短的路徑。
那么這條路徑我們怎么找到呢蒿往？哪條路徑才是最好的呢盛垦？
我們把這條路徑定義為規(guī)整路徑，并用W來表示瓤漏，這條路徑不是隨意選擇的腾夯，需要滿足以下幾個(gè)約束：
1. 邊界條件：
因?yàn)槲覀冃枰獙蓷l序列對(duì)齊颊埃，所以路徑的起點(diǎn)必須是（1,1），終點(diǎn)必須是（n,m）蝶俱。
2. 連續(xù)性：
如果路徑W上的節(jié)點(diǎn)wk-1= (a’, b’)班利，那么對(duì)于路徑的下一個(gè)點(diǎn)wk=(a, b)需要滿足 (a-a’) <=1和 (b-b’) <=1。也就是不可能跨過某個(gè)點(diǎn)去匹配榨呆，只能和自己相鄰的點(diǎn)對(duì)齊罗标。這樣可以保證A和B中的每個(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)行的。
結(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)鼓黔。
這是一個(gè)顯然的動(dòng)態(tài)規(guī)劃策略央勒，假設(shè)我們要求到位置(i,j)的最小累計(jì)距離D(i,j)不见，那么它只能由： D(i?1,j) ； D(i,j?1)崔步； D(i,j) 這三個(gè)位置的最小累計(jì)距離中尋找稳吮，也就是：
其中邊界，D（0,0）=0; D（-1,0）=∞井濒，D（0灶似，-1）=∞
四. 舉個(gè)例子
比如說，給定一個(gè)樣本序列X和比對(duì)序列Y：
X：3瑞你，5酪惭，6，7者甲，7春感，1
Y：3，6虏缸，6鲫懒，7，8刽辙，1窥岩，1
DTW首先會(huì)根據(jù)序列點(diǎn)之間的距離(這里使用絕對(duì)距離)，獲得一個(gè)序列距離矩陣 M（序列中任意兩點(diǎn)間的距離都要計(jì)算）宰缤。
然后根據(jù)距離矩陣颂翼，使用DP算法的遞推關(guān)系式晃洒，得到累計(jì)距離矩陣（或稱代價(jià)矩陣）D：
最后，兩個(gè)序列的距離朦乏，由代價(jià)矩陣最后一行最后一列給出锥累，在這里也就是2。
五. 代碼
import numpy as np
def DTW_distance(series_a,series_b):
series_a=np.array(series_a)
series_b=np.array(series_b)
len_a=np.size(series_a)
len_b=np.size(series_b)
#計(jì)算序列間的絕對(duì)距離,距離矩陣M
ABS_distance={}
for i in range(len_a):
for j in range(len_b):
ABS_distance[(i,j)]=np.abs(series_a[i]-series_b[j])
#利用DP算法求解最優(yōu)路徑
#由于數(shù)組從0開始集歇，元素必定從（0,0）位置出發(fā)桶略，初始位置的代價(jià)就是其本身的距離
D={(0,0):ABS_distance[(0,0)]}
#首先求解第一行與第一列的累計(jì)距離（代價(jià)），因?yàn)樗麄兊纳弦徊轿ㄒ淮_定
for i in range(1,len_a):
D[(i,0)]=ABS_distance[(i,0)]+D[(i-1,0)]
for i in range(1,len_b):
D[(0,i)]=ABS_distance[(0,i)]+D[(0,i-1)]
#求解其他位置
for i in range(1,len_a):
for j in range(1,len_b):
D[(i,j)]=ABS_distance[(i,j)]+min(D[(i-1,j),D[(i,j-1),D[(i-1,j-1)])
return D
參考：
https://blog.csdn.net/qq_39516859/article/details/81705010
https://blog.csdn.net/raym0ndkwan/article/details/45614813
