1. 問題背景
在時間序列中，需要比較相似性的兩段時間序列的長度可能并不相等，在語音識別領(lǐng)域表現(xiàn)為不同人的語速不同。而且同一個單詞內(nèi)的不同音素的發(fā)音速度也不同，比如有的人會把“A”這個音拖得很長，或者把“i”發(fā)的很短。
另外，不同時間序列可能僅僅存在時間軸上的位移，亦即在還原位移的情況下，兩個時間序列是一致的。在這些復(fù)雜情況下，使用傳統(tǒng)的歐幾里得距離無法有效地求的兩個時間序列之間的距離（或者相似性）。
在上圖A中，實線和虛線分別是同一個詞“pen”的兩個語音波形（在y軸上拉開了，以便觀察）。可以看到他們整體上的波形形狀很相似，但在時間軸上卻是不對齊的。例如在第20個時間點的時候，實線波形的a點會對應(yīng)于虛線波形的b’點，這樣傳統(tǒng)的通過比較距離來計算相似性很明顯不靠譜。因為很明顯，實線的a點對應(yīng)虛線的b點才是正確的。而在圖B中，DTW就可以通過找到這兩個波形對齊的點，這樣計算它們的距離才是正確的。
2. DTW詳解
DTW是一類典型的優(yōu)化問題，通常采用動態(tài)規(guī)劃算法求解。
假設(shè)我們有兩個時間序列和
，他們的長度分別為
和
：
首先，我們依然采用兩個序列中每一對“點”之間的距離來計算形似度，即使兩個序列中的點的個數(shù)可能不一樣。
不過，因為可以warping規(guī)整時間軸，所以，我們并不是在兩個序列中依次取一對點來計算距離，而是每個點有可能對應(yīng)于另一個序列中的多個點。
我們需要將連個序列對齊。最簡單的對齊方式就是線性縮放了。把短的序列線性放大到和長序列一樣的長度再比較，或者把長的線性縮短到和短序列一樣的長度再比較。但是這樣的計算沒有考慮到語音中各個段在不同情況下的持續(xù)時間會產(chǎn)生或長或短的變化，因此識別效果不可能最佳。因此更多的是采用動態(tài)規(guī)劃的方法。
為了對其兩個這兩個序列，我們需要構(gòu)造一個的矩陣網(wǎng)格，矩陣元素
表示
和
兩點之間的距離
，每一個矩陣元素
表示
與
對齊。DP算法可以歸納為尋找一條通過此網(wǎng)格中若干格點的路徑。
我們把這條路徑定義為規(guī)整路徑(warping path)，并用來表示：
當(dāng)然這條規(guī)整路徑需要滿足一定要求：
-
邊界條件：
和
, 兩個人分別說了同一個單詞，但是由于語速、語氣、語調(diào)等等各不相同，會導(dǎo)致采樣得到的數(shù)據(jù)無法對齊。但是兩段語音采樣的第一個采樣值和最后一個采樣值肯定是兩兩對應(yīng)的。因此所選的路徑必定是從左下角出發(fā)，在右上角結(jié)束。
-
連續(xù)性：
如果
，那么對于路徑的下一個點
需要滿足
和
。也就是不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證
和
中的每個坐標(biāo)都在
中出現(xiàn)。
-
單調(diào)性：
如果
需要滿足
和
。這限制
由連續(xù)性和單調(diào)性可知，每次格點前進(jìn)方向只有三種：
，
，
。我們的目的是使得下面的規(guī)整代價最小的路徑：
分母中的主要是用來對不同的長度的規(guī)整路徑做補(bǔ)償。因為不同的路徑其長短不同，較長的路徑有較多的“點對”，會有較多的距離累加上去，所以總距離除以
得到單位路徑的距離（還不太理解。。。）
這里我們定義一個累加距離(cumulative distances)。從(0, 0)點開始匹配這兩個序列和
，每到一個點，之前所有的點計算的距離都會累加。到達(dá)終點(n, m)后，這個累積距離就是我們上面說的最后的總的距離，也就是序列
和
的相似度。
示例：
給定一個樣本序列X和對比序列Y:
X：3，5，6，7，7，1
Y：3，6，6，7，8，1，1
試計算X和Y之間的最小路徑。
DTW首先會根據(jù)序列點之間的距離(歐氏距離)，獲得一個序列距離矩陣 M，其中行對應(yīng)X序列，列對應(yīng)Y序列，矩陣元素為對應(yīng)行列中X序列和Y序列點到點的歐氏距離：
| X/Y | 3 | 6 | 6 | 7 | 8 | 1 | 1 |
|---|---|---|---|---|---|---|---|
| 3 | 0 | 3 | 3 | 4 | 5 | 2 | 2 |
| 5 | 2 | 1 | 1 | 2 | 3 | 4 | 4 |
| 6 | 3 | 0 | 0 | 1 | 2 | 5 | 5 |
| 7 | 4 | 1 | 1 | 0 | 1 | 6 | 6 |
| 7 | 4 | 1 | 1 | 0 | 1 | 6 | 6 |
| 1 | 2 | 5 | 5 | 6 | 7 | 0 | 0 |
然后根據(jù)距離矩陣生成損失矩陣(Cost Matrix)或者叫累積距離矩陣，其計算方法如下：
第一行第一列元素為
的第一行第一列元素，在這里就是0；
其他位置的元素
的值則需要逐步計算，具體值的計算方法為
，得到的
如下：
| X/Y | 3 | 6 | 6 | 7 | 8 | 1 | 1 |
|---|---|---|---|---|---|---|---|
| 3 | 0 | 3 | 6 | 10 | 15 | 17 | 19 |
| 5 | 2 | 1 | 2 | 4 | 7 | 11 | 15 |
| 6 | 5 | 1 | 1 | 2 | 4 | 9 |
14 |
| 7 | 9 | 2 | 2 | 1 | 2 | 8 | 14 |
| 7 | 13 | 3 | 3 | 1 | 2 | 8 | 14 |
| 1 | 15 | 8 | 8 | 7 | 8 | 2 | 2 |
最后，兩個序列的距離，由損失矩陣最后一行最后一列給出，在這里也就是2。
import sys
import numpy as np
def cal_dtw(s1, s2):
d = lambda x, y: abs(x - y)
ts_a, ts_b = np.array(s1), np.array(s2)
m, n = len(ts_a), len(ts_b)
cost = sys.maxsize * np.ones((m, n))
# 初始化第一個元素
cost[0, 0] = d(ts_a[0], ts_b[0])
# 計算損失矩陣第一列
for i in range(1, m):
cost[i, 0] = cost[i - 1, 0] + d(ts_a[i], ts_b[0])
# 計算損失矩陣第一行
for j in range(1, n):
cost[0, j] = cost[0, j - 1] + d(ts_a[0], ts_b[j])
# 計算損失矩陣剩余元素
for i in range(1, m):
for j in range(1, n):
choices = cost[i - 1, j - 1], cost[i - 1, j], cost[i, j - 1]
cost[i, j] = min(choices) + d(ts_a[i], ts_b[j])
return cost[-1, -1]
if __name__ == '__main__':
ts_a = [1, 5, 8, 10, 56, 21, 32, 8]
ts_b = [1, 5, 8, 10, 23, 56, 21, 32, 8]
ts_c = [1, 3, 6, 9, 16, 29, 31, 32, 33]
# 調(diào)用cal_dtw_distance計算dtw相似度
dtw_ab = cal_dtw(ts_a, ts_b)
dtw_ac = cal_dtw(ts_a, ts_c)
print(dtw_ab)
print(dtw_ac)
