DDTW 導數動態時間規整算法

作者：鄭培

Derivative Dynamic Time Warping（DDTW） 是對 Dynamic Time Warping (DTW) 的一種改進。緩解了經典DTW算法所產生的“奇點”（Singularities）問題，本文將從以下幾個方面介紹DDTW算法。

1、算法背景

時間序列是幾乎每一個科學學科中普遍存在的數據形式。時間序列的常見處理任務是將一個序列與另一個序列進行比較，以比較兩個時間序列的相似度。在某些領域，使用非常簡單的距離度量（例如歐式距離）就足夠了。

但是，在大多情況下，兩個序列的總體組成形狀大致相同，但是這些形狀在X軸上并不對齊。（圖1）

為了找到這些序列之間的相似性，或作為對它們進行平均之前的預處理步驟，我們必須“扭曲”一個（或全部兩個）序列的時間軸以實現更好的比對。動態時間規整（DTW）是一種有效實現這種規整的技術。

例如圖A所示，實線和虛線分別是同一個詞“pen”的兩個語音波形（在y軸上拉開了，以便觀察）。可以看到他們整體上的波形形狀很相似，但在時間軸上卻是不對齊的，假設一個序列中的第i個點與另一序列中的第i個點對齊將產生“悲觀差異”（pessimistic dissimilarity）。而在圖B中，DTW就可以通過找到這兩個波形對齊的點，這樣計算它們的距離才是正確的。

（圖1）
因此，DTW顯示出了很好的能力，除了在數據挖掘（Keogh＆Pazzani 2000，Yi et. al.1998，Berndt＆Clifford 1994）上的應用，DTW還被用于手勢識別（Gavrila＆Davis 1995），機器人技術（Schmill et. al 1999），語音處理（Rabiner＆Juang 1993），制造業（Gollmer＆Posten 1995）和醫藥行業（Caiani et. al 1998）。

2、經典動態時間規整算法

假設我們有兩個時間序列Q和C，長度分別為n和m，其中：

為了對齊這兩個序列，我們需要構造一個n x m的矩陣網格，矩陣元素(i, j)表示qi和cj兩個點的距離d(qi, cj)（也就是序列Q的每一個點和C的每一個點之間的相似度，距離越小則相似度越高。這里先不管順序），一般采用歐式距離。每一個矩陣元素(i, j)表示點qi和cj的對齊。有了這個矩陣，我們就能夠對兩個時間序列之間的距離進行計算，并顯示出一條規整路徑warping path（W）。由于有許多不同的對時間軸的“扭曲”方式，因此我們能夠得到很多條規整路徑（W的公式如下），但我們的目標是找到一條最短的規整路徑，以判斷兩條時間序列之間的“距離”也就是相似度，而如何快速地找到這條路徑呢？我們發現動態規劃（Dynamic Programming）可以為我們提供很大的方便。
Dynamic Programming算法可以歸結為尋找一條通過此網格中若干格點的路徑，路徑通過的格點即為兩個序列進行計算的對齊的點。

w的第i個元素為w=(i,j)定義了兩條時間序列的映射。并且，規整路徑一般受到以下幾種約束條件。
1）邊界條件：定義了規整路徑必須在矩陣的對角元素中開始和結束；
2）連續性：這將規整路徑中的允許步驟限制為相鄰的單元（包括對角相鄰的單元）；
3）單調性：這迫使W中的點在時間上單調進行。

結合連續性和單調性約束，每一個格點的路徑就只有三個方向了。例如如果路徑已經通過了格點(i, j)，那么下一個通過的格點只可能是下列三種情況之一：(i+1, j)，(i, j+1)或者(i+1, j+1)。

由上文所述，我們可以通過比較滿足以上條件所有規整路徑找出最短的規整路徑，但是DP為我們提供了一個更好地方法來計算最短路徑。我們首先定義一個累積距離cumulative distance γ，累積距離γ(i,j)為當前格點距離d(i,j)，也就是點qi和cj的歐式距離與可以到達該點的最小的鄰近元素的累積距離之和：

通過動態規劃算法，我們可以較簡單地得到最短的累積距離。

3、動態時間規劃的“奇點”問題

DTW算法最重要的特征就是通過“扭曲”X軸來解釋Y軸變量，以達到使時間序列對齊的目的。但是簡單的通過Y軸的變量值來扭曲X軸會導致“不直觀”（unintuitive）的對齊，其中一個時間序列上的單個點會映射到另一個時間序列的一部分上。我們稱這種我們不期望看到的行為為“奇點”（singularities）。

已經提出了很多臨時的方法來緩解這種奇點問題，這些方法都具有一個共同點，即基本上都限制了可能的“扭曲”。但是，它們造成的缺點是，可能阻止發現“正確的”“扭曲”。
因此，我們引入了Derivative DTW 來改進這種問題。

4、導數動態時間規整算法

如前文所述，DTW算法粗暴地（wildly）根據Y軸變量的值對X軸進行warp，這樣在Y軸變量有細微變動時很容易造成奇點問題，如下圖所示。而最正確的時間序列的對齊應該是特征之間的對應（feature to feature），于是我們考慮比DTW更高一層次的特征選取，根據形狀（shape）來進行對齊。

4.1、DDTW算法細節

那么如何才能獲取關于形狀的信息，我們知道一階導數可以反映斜率，而斜率是我們判斷時間序列形狀的一個指數，因此我們通過考慮序列的一階導數來獲得有關形狀的信息，因此將我們的算法稱為Derivative
Dynamic Time Warping(DDTW)。
如前所述，我們構造了一個n×m矩陣，其中矩陣的（i th，j th）元素包含兩個點q i和c j之間的距離d（q i，c j）。DTW算法根據歐式距離來計算兩個時間序列對應點之間的距離，DDTW則通過qi和cj之間估計導數差值的平方來代替DTW算法的距離公式。在這里我們不去考慮繁瑣精確的一階導數計算公式，反之我們使用簡單的導數估計方法，以增加方法的泛化性。估計導數公式如下：

大家可以看到，該估計值只是通過該點及其左鄰點的直線的斜率以及通過左鄰點和右鄰點的直線的斜率的平均值來得出的。值得注意的是該公式比僅利用兩個數據點對于離群點更具有魯棒性。另外值得注意的是該公式并不包括第一個與最后一個點，反之是運用第二個點與倒數第二個點來代替。

以下是簡單的一個例子。

5、實驗與結果

為了驗證DDTW對于奇點問題的改進，作者設計了兩個實驗分別從正反兩個方面來進行論證。

5.1 錯誤的規整（spurious warping）

作者選取了三類在形狀，噪聲和自相關方面相差很大的三組數據集來進行實驗。這些序列高度相關但不完全相同，特別是它們包含較小的（局部）差異。

為了簡便地對比兩種算法的差異，我們采用較為簡單的K值（規整路徑的長度）來進行計算。其中K的取值范圍在max(m,n)<K<m+n-1。同時由于在該實驗中兩條時間序列的長度相似，因此m ≤ K < 2m-1。于是我們定義W為warp的次數，因此我們得到以下公式：

W可以反映兩種算法warp扭曲的次數，如果算法在兩個序列之間沒有發現扭曲，則W將等于零；扭曲越多，發現W的值越大。對于上文所述三個數據集，我們進行多次實驗并取平均值后得到以下結果：

通過實驗，DTW嘗試粗暴（wild）的通過時間軸的扭曲來糾正序列之間的微小差異。相應的DDTW則因為考慮“更高層次的特征”從而更不容易發現不存在的warp。

在這里值得注意的是，由于這三組時間序列是高度相關但不相同的，并且在Y軸上包含細微的差別，所以對于這三組時間序列分別的warp其實是完全錯誤的（completely spurious）。也就是說兩種算法找到的warp越多，那么他們對于奇點問題的識別排出就越差。因此我們可以看到，DDTW在奇點問題上對于DTW具有很大的提升。

5.2 尋找正確的“扭曲”（find the correct warping）

該實驗是為了驗證兩種算法對于需要warp的時間序列的敏感性。因此作者通過一條時間序列Q與時間序列Q的復制Q’來進行實驗。簡單來說，作者通過對時間序列Q’插入三種不同水平的Gaussian bump以達到對時間序列在Y軸上的細微變化，再通過兩種算法對時間序列Q和Q’進行warp，觀察算法的效果。
與第一個實驗相同，我們設定M為錯誤warp的次數，并且在以下條件下得到公式：

條件中的雙箭頭對應表示時間序列Q與Q’之間正確的對應關系，單箭頭對應表示由算法返回的實際對應關系。當且僅當兩個條件都符合時，我們計算兩條時間序列對應Y軸變量的差值。公示中分母是為了標準化而做的計算。
分析公式8我們可以知道，當時間序列上對應點正確匹配時，差值為零，如果算法產生了很多奇點，那么M的值就會越大，因此我們可以通過該公式比較兩種算法對于尋找正確warp的能力。實驗結果如下：

由以上實驗可知，DDTW可在時間序列之間產生出色的對齊方式；并且DDTW可以更好地找到兩個序列之間的正確變形。

6、參考資料

論文：Eamonn J. Keogh, Derivative Dynamic Time Warping
暫無論文實驗數據，僅提供參考代碼，供大家學習理解：https://momodel.cn/explore/5d837ba0870b9dc68fd13fdc?type=app

關于我們

Mo（網址：https://momodel.cn）是一個支持 Python 的人工智能在線建模平臺，能幫助你快速開發、訓練并部署模型。

---

Mo 人工智能俱樂部?是由網站的研發與產品設計團隊發起、致力于降低人工智能開發與使用門檻的俱樂部。團隊具備大數據處理分析、可視化與數據建模經驗，已承擔多領域智能項目，具備從底層到前端的全線設計開發能力。主要研究方向為大數據管理分析與人工智能技術，并以此來促進數據驅動的科學研究。

目前俱樂部每兩周在杭州舉辦線下論文分享與學術交流。希望能匯聚來自各行各業對人工智能感興趣的朋友，不斷交流共同成長，推動人工智能民主化、應用普及化。

總結

以上是生活随笔為你收集整理的DDTW 导数动态时间规整算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。