動態時間歸整 | DTW | Dynamic Time Warping

引子

高富帥

「今天天氣好好啊」

屌絲

「幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊」

上述案例中,高富帥和屌絲在表達上暴露出了明顯的差別,如何判斷這兩者是在說同一件事情——「今天天氣好」呢?

什麼

DTW是什麼呢?[1]中對其定義爲

Dynamic time warping (DTW) is an algorithm for measuring similarity between two sequences which may vary in time or speed.

舉個例子,兩份原本一樣聲音樣本A、B都說了「你好」,A在時間上發生了扭曲,「你」這個音延長了幾秒。最後A:「你~~~~~~~好」,B:「你好」。DTW正是這樣一種可以用來匹配A、B之間的最短距離的算法。納尼!神碼距離!!!這個距離是具體的、人爲定義的、可度量的(關於ML中常見的距離,可參見[2])。相似性和最短距離呈負相關,最短距離越大,相似性越低,越不相似,反之亦然。在大部分音頻處理的場景中,DTW所謂的最短的第一要義是忽略上時間上發生的扭曲,使得「你好 V.S. 你~~~~~~~好」、「這樣子 V.S. 醬紫」之間匹配的結果是:相似。最好的結果自然是:相同

屌絲vs高富帥

你聽我解釋啊

以上面的例子爲例,簡單起見,我們定義單個字之間的距離函數爲:

distance = lambda a,b : 0 if a==b else 1

如果列成一張表的話:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

上表中,從左上角到右下角的最短路徑所消耗的代價(cost),便是DTW所理解的最短距離。這裏走一步的定義是:→(右),↓(下),↘(右下)三種走法。爲什麼只有這三種走法呢?而不能往上、往左、往左上...呢?因爲時間是不能倒轉的。[3]中稱之爲「局部關係」。透過上表可肉眼可測得屌絲和高富帥兩種表達之間的DTW距離2。這個2的就是屌絲雞婆多說了一句幹啦所付出的代價了。如果不說這兩個字的話,DTW距離就是0了:

1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

綜上所述,Python實現的通用的算法爲:

def dtw(sa,sb):
    '''
    >>>dtw(u"幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊", u"今天天氣好好啊")
    2
    '''
    MAX_COST = 1<<32
    #初始化一個len(sb) 行(i),len(sa)列(j)的二維矩陣
    len_sa = len(sa)
    len_sb = len(sb)
    # BUG:這樣是錯誤的(淺拷貝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
    dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
    dtw_array[0][0] = distance(sa[0],sb[0])
    for i in xrange(0, len_sb):
        for j in xrange(0, len_sa):
            if i+j==0:
                continue
            nb = []
            if i > 0: nb.append(dtw_array[i-1][j])
            if j > 0: nb.append(dtw_array[i][j-1])
            if i > 0 and j > 0: nb.append(dtw_array[i-1][j-1])
            min_route = min(nb)
            cost = distance(sa[j],sb[i])
            dtw_array[i][j] = cost + min_route
    return dtw_array[len_sb-1][len_sa-1]

另外,[1]中還提到了另一種加局部限制(locality constraint)的的DTW實現,[3]提到一種加local/global path constraint的DTW實現,以減少計算量,有興趣的同學可以看看。

參考

  1. Dynamic time warping - Wikipedia
  2. 百度文庫 - 机器学习中的相似度度量
  3. Roger Jang (張智星) - Data Clustering and Pattern Recognition (資料分群與樣式辨認) Dynamic Time Warping

相關代碼


这个是自學的,可能會有理解錯誤的地方,如有誤人子弟之處,歡迎在下面指正!

「Formal education will make you a living; self-education will make you a fortune. 」—— Jim Rohn



关于 McKelvin

a hacker who's interested in `music computing` and `network security`.
此条目发表在 Work 分类目录,贴了 , 标签。将固定链接加入收藏夹。