?作者 | 黃春喜

單位 | 香港科技大學

研究方向 |?智能交通

摘要

根據(jù)時間序列本身的不同特點，時間序列相似度的衡量（時間序列間距離的度量）存在多種方法。本文從歐氏距離出發(fā)，進一步延伸至 Dynamic Time Warping（DTW）、一些 DTW 存在的缺點和相關的解決辦法以及 DTW 的兩個變種 Derivative Dynamic Time Warping（DDTW）和 Weighted Dynamic Time Warping（WDTW）。

前言/背景

在眾多廣泛的科研領域中，時間序列是一種無處不在的數(shù)據(jù)格式。對于時間序列相關的研究而言，其中一種最常見的需求就是比較兩個時間序列是否相似。有效地比較時間序列間的相似度在很多科學/工程任務中非常必要且關鍵，如：分類/聚類/語音識別/步態(tài)識別等。

以某個生產制造環(huán)節(jié)中針對產成品某項（些）特征所收集到的時間序列數(shù)據(jù)為例。首先，所收集到的代表良品和次品的時序數(shù)據(jù)中在某些特定特征上有區(qū)別，且這些區(qū)別具有與領域知識相關的特定物理含義；其次，由于生產制造過程中的本身特性，所收集到的時序數(shù)據(jù)長度是不相等的；再而言，次品的產生存在多種原因，換句話說，產成品不只可以進行二分類成良品和次品兩個種類，而是可以進一步區(qū)分為良品、次品種類 1、次品種類 2、次品種類 3 等多種類；最后，跟很多實際生產制造中的數(shù)據(jù)一樣，良品數(shù)據(jù)量遠大于次品數(shù)據(jù)量，次品繼續(xù)細分的各種類次品數(shù)據(jù)更是少之甚少，整體存在嚴重的數(shù)據(jù)不平衡問題。

為了在正常生產制造過程中實現(xiàn)良品和不同種次品的多分類任務，比較所收集到的時間序列間的相似度是重要的一步。從直覺上不難理解，比較時間序列的相似度等同于計算時間序列間的“距離”，兩個時間序列之間的“距離”越大，二者的相似度則越小，反之同理。

故本文基于此從歐氏距離出發(fā)，進一步延伸至 Dynamic Time Warping（DTW）、一些 DTW 的缺點和相關的解決辦法以及 DTW 的兩個變種 Derivative Dynamic Time Warping（DDTW）和 Weighted Dynamic Time Warping（WDTW）。鑒于關于 DTW 的細節(jié)已經有很多優(yōu)質博文介紹，故本文只闡述基本概念、更多關注不同方法間的區(qū)別、過渡的邏輯以及不同方法所適用的問題。

歐氏距離

提到衡量時間序列之間的距離，歐氏距離（Euclidean Distance）是最直接的方法，它概念簡單，在此不贅述。當應用歐氏距離來比較兩個時間序列時，序列與序列之間的每一個點按順序建立起了一對一的對應關系，根據(jù)點與點之間的對應關系計算其歐氏距離作為兩個時間序列之間的距離度量（相似度）。如下圖 1 所示：

▲ 圖1. 兩個等長時間序列間的歐氏距離

在應用歐氏距離時，第一個時間序列中的第 i 個點分別與第二個時間序列中的第 i 個點形成一一對應。然而，歐氏距離在某些情況下會出現(xiàn)問題，如下圖 2 所示：

▲ 圖2. 兩個不等長時間序列間的歐氏距離是否可行？

當兩個時間序列的長度不相等時，較長的一個時間序列總會剩下無法被匹配到的點，這種情況如何計算歐氏距離？毫無疑問，此時歐氏距離不再可行。此外，如圖 1 中紅圈所示，兩個時間序列在時間軸上有一定的平移但總體的趨勢是相似的，自然地，當我們想人為對齊圖1中兩個時間序列時，紅圈中的兩個向下凸起的點應該相互對應起來。很顯然，歐氏距離的這種方式按順序點對點的方法無法滿足我們的需求。

綜上，在時間序列間的距離度量上，歐氏距離有以下限制：（1）只適用于處理等長的時間序列；（2）在將時間序列對齊時無法考慮?X?軸上的變化，導致有時對齊出現(xiàn)不自然。

特別地，作為一種常見的標準距離度量，歐氏距離是另一種更為廣泛的距離度量——閔式距離（Minkowski distance）當 p 取值為 2 時的特例。閔式距離中 p=1 時和 p=infinity 時，分別對應曼哈頓距離和兩個時間序列點與點之間距離差值的最大值。

DTW (Dynamic Time Warping)

針對上文提到的歐氏距離無法處理不等長數(shù)據(jù)、處理等長數(shù)據(jù)時對齊不自然的兩個主要問題，為了解決不等長數(shù)據(jù)的距離度量和匹配問題，上世紀 70 年代，日本學者 Itakura 等人提出了 DTW。在過去的幾十年里，DTW 已經被廣泛應用于孤立詞語音識別、手勢識別、數(shù)據(jù)挖掘和信息檢索等場景中，DTW 一度是語音識別的主流方法。DTW 的原理此處簡述如下：

對于兩個不等長的時間序列 Q 和 C，長度分別為 n 和 m：

要使用 DTW 來對齊兩個不等長的時間序列，需要構建一個 n*m 的距離矩陣，矩陣中的第 i 行第 j 列所對應的元素代表的就是序列中點 和點 的距離 ，通常情況下這里會使用歐氏距離，所以 ?？蓞⒁娤聢D 3：

▲ 圖3. DTW中的warping path示意圖

上圖所示為 n*m 的矩陣，每一個方格代表矩陣中的每一個元素。對于兩個時間序列而言，DTW 拋開了歐氏距離的限制，其本意是要尋找到一個連續(xù)的包含兩個時間序列中所有點互相對應的一個匹配關系（這種匹配可以是第 個點對應第 個點，），這些匹配關系的集合共同構成了圖 3 中的黑色實線 warping path W：

要進行 DTW 匹配，warping path W 需滿足以下條件：

1-邊界性（Boundary conditions）： 和 ，簡而言之，兩個經 DTW 對齊的時間序列應該首對首、尾對尾相連，反映到距離矩陣中就是 warping path 應從一個角落出發(fā)、在對角線方向上的另一個角落停止。

2-連續(xù)性（Continuity）：每次 warping path 向下一步移動必須是連續(xù)的，反映到距離矩陣中就是下一步只能在原方格的相鄰方格中選取（方向需滿足對角線方向）。數(shù)學上可寫成：對于 ，，需滿足 ， 。

3-單調性（Monotonicity）：兩個時間序列間的對應必須按照順序進行，warping path不能有交叉。數(shù)學上可寫成：，，需滿足 ，。

滿足這些條件的 W 還是有很多個，DTW 只尋找能夠最小化 warping cost 的 W：

在上式中，K 是 warping path 的長度，除以 K 可以消除不同長度的 warping path 的影響。

最終，兩個不等長時序數(shù)據(jù)的對應關系可以通過動態(tài)規(guī)劃來求解以下遞歸式得到：

其中， 是到距離矩陣第 行第 列時所積累的 warping path 的總距離。

DTW面臨的問題及其解決方案

盡管 DTW 已經被成功應用到很多領域中，DTW 依然存在缺點：有時 DTW 會在對齊時產生不自然的扭曲/翹曲。如下圖 4 所示：

▲ 圖4. 合成數(shù)據(jù)中DTW在對齊時產生的Singularities

A 中實線、虛線所展示的是兩條合成信號（均值、方差都相同），B 中展示的是自然的“feature to feature”的對應，而 C 中展示的則是 DTW 的結果。不難發(fā)現(xiàn)，DTW 沒能自然地將圖形中的波峰與波峰相對應，反而產生了一個序列中的一個點對應另外一個序列中的多個點的情況，這種情況被稱為“Singularities”。出現(xiàn)這種情況的原因是 DTW 算法試圖通過扭曲 X 軸來解釋 Y 軸上的變化。

為了解決“Singularities”問題，過去的研究提出了很多方案，大致可歸為以下三類：

1-Windowing：歸根結底，出現(xiàn) singularities 就是因為兩個時間序列上相隔很遠的點僅因為值相同/相近容易被 warping 到一起?？梢韵拗?DTW 在 warping 過程中的能選擇的范圍來解決 singularities，具體可以通過設置一個 warping window 來實現(xiàn)，故稱之為 Windowing方法。數(shù)學上可寫作：， 作為 window width 是一個正整數(shù)。圖 3 中兩虛線所夾范圍即為經 window 限制后的范圍，此時 warping path 就只能在此區(qū)域內。

2-Slope weighting：當傳統(tǒng) DTW 中的遞歸式改為下式時，即可實現(xiàn) slope weighting。

不難發(fā)現(xiàn)，唯一的區(qū)別在于在 min 函數(shù)中的后兩項前加了 X ，X 為一個正實數(shù)。當對 X 的值進行調整時，可以使得 warping path 的方向（slope）會有一定的調整。X 取較大值時，warping path 的選擇會更多的朝向對角線方向。

3-Step patterns：改變傳統(tǒng) DTW 中的遞歸式為下式可以實現(xiàn)改變 warping path step。

將傳統(tǒng) DTW 中的遞歸式和上式分別可視化如下圖 5 中 A、B 所示：

▲ 圖5. 兩種不同step pattern的遞歸式的可視化

A 所對應的即為傳統(tǒng) DTW 的遞歸式，下一步只能在距離矩陣中相鄰的三個方格中選取，而 B 中所對應的就是改變了 step 后的遞歸式。相較于 A 中，B 中對于每一個第一步沒有沿著對角線方向走的方格都再朝其所在方格的對角線方向移動一步，這樣即可實現(xiàn)改變 step pattern。

總的來說，以上三類解決方案在一定程度上對解決 singularities 有一定幫助，然而，它們仍然存在以下缺點：

（1）有可能錯過正確的 warping path。以上三類方法都是在沒有任何前提條件的情況下人為地對 warping path 進行限制和調整來減少翹曲，這很有可能會錯過真正正確的 warping path。

（2）參數(shù)的選擇沒有明確的指導。在 Windowing 方法中 R 值的選取、Slope weighting 方法中 X 都是人為視具體場景主觀調整、沒有明確標準的。

Derivative Dynamic Time Warping (DDTW)

實際上，DTW 之所以造成“Singularities”，本質上是由于 DTW 算法本身所考慮的特征決定的：DTW 算法只考慮數(shù)據(jù)點在 Y 軸上的值。

例如：兩個數(shù)據(jù)點 和 的值相同，但是 位于一個時間序列的上升趨勢部分，而 位于一個時間序列的下降趨勢部分。對于 DTW 而言，很容易將這兩個點匹配在一起，因為它們的值相同。然而，從直覺上來說，我們很難把兩個趨勢相反的部分匹配在一起。為了避免 DTW 只考慮 Y 軸的值造成“Singularities”問題， DDTW 出現(xiàn)了。

DDTW 不考慮數(shù)據(jù)點的 Y 軸的值，而是考慮更高層次的特征——時序數(shù)據(jù)的“形狀”。該方法通過計算時序數(shù)據(jù)的一階導數(shù)來獲取與“形狀”相關的信息，所以被稱為 Derivative DTW。

DDTW 本身的概念也很簡單，對于傳統(tǒng) DTW 而言，距離矩陣中的元素即為兩個點 和 之間的距離；然而對于 DDTW 而言，此時的“距離矩陣”中的元素不再是兩點之間的距離，而是時序數(shù)據(jù)在兩點處一階導數(shù)的差值的平方。盡管有多種方法估計一階導數(shù)，出于簡便和拓展性，DDTW 中的一階導數(shù)估計采用以下方法：

不難發(fā)現(xiàn)，在 點處一階導數(shù)的估計就是通過該點和該點左邊點的直線斜率與通過該點左邊點和該點右邊點的直線斜率的平均數(shù)。Keogh, E. J., & Pazzani, M. J. 提到，在只考慮兩個數(shù)據(jù)點的情況下，這種估計方法面對 outliers 更為穩(wěn)定。

需要注意的是，這種一階導數(shù)的估計方法無法計算時序數(shù)據(jù)的第一個數(shù)據(jù)點和最后一個數(shù)據(jù)點的一階導數(shù)，在實際操作時可以用第二個數(shù)據(jù)點和倒數(shù)第二個數(shù)據(jù)點的導數(shù)來替代。此外，對于高噪聲的數(shù)據(jù)集可以在估計一階導數(shù)之前先做 exponential smoothing。

Weighted Dynamic Time Warping (WDTW)

上文提到，經典的 DTW 算法在匹配兩個時間序列上的點時僅考慮 Y 軸上的值，而不考慮所匹配的點在 X 軸上的差別，因此會造成時序數(shù)據(jù)匹配時的“Singularities”問題。

歸根結底，“Singularities”問題在某種程度上就源于只考慮 Y 軸的值，第一個序列上的一個點可以跟第二個序列上的另一個很遠（此處“遠”指的是 X 軸的距離/序數(shù)）的點匹配起來，加上 DTW 中 warping path 的連續(xù)性、單調性條件，造成了時序數(shù)據(jù)對齊過程中的各種翹曲/扭曲。

DDTW 通過考慮“形狀”利用估計時序數(shù)據(jù)的一階導數(shù)來解決這個問題，而 WDTW 則采用了不同的思路。簡單來說，WDTW 選擇在計算兩個序列上的兩個點之間歐氏距離時加上一個 weight，而這個 weight 與兩個點之間的 X 軸上的距離有關系。具體如下（p=2）：

如上式，p=2 時為計算兩個序列上的兩個點 和 的歐氏距離。此處的 即為與兩個點在 X 軸上的距離（phase difference）相關的 weight。WDTW 通過計算兩點歐氏距離時添加一個 weight 的方法，為解決“Singularities”問題提供了新的思路：weighted DTW 本質上是一種 penalized-based DTW，當 的值較大（兩個點在 X 軸上距離較大）時，通過賦予一個較大的 值，則可避免算法將兩個距離較大的點匹配在一起。

針對 WDTW，Jeong, Y. S., Jeong, M. K., & Omitaomu, O. A. 等人還提出了一個 logistic weight function 來賦予權重，感興趣的讀者可自行查閱原文。值得一提的是，當 是一個常數(shù)的時候，此時的 WDTW 不會對于 X 軸上距離不同的點的懲罰是相同的，所以等同于傳統(tǒng)的 DTW；當 的值極大時，此時的 WDTW 對于 X 軸上距離不同的點懲罰也極大，甚至第 i 個點和第 i-1 個點的匹配也不行，此時的 WDTW 即對應傳統(tǒng)的歐氏距離。

總結與補充

綜上，本文從只能處理等長數(shù)據(jù)且容易造成不自然對齊的歐氏距離出發(fā)，我們逐步論述了 DTW 出現(xiàn)的原因和重要性。進一步，我們發(fā)現(xiàn)傳統(tǒng) DTW 算法帶來的 singularities 問題可以在 windowing、slope weighting、step pattern 等方法下得到一定改善。然而，從算法考慮的特征層面出發(fā)，為了解決 DTW 算法匹配時序數(shù)據(jù)時可能存在的 singularities 問題，DDTW 提出考慮更高層次的特征——形狀，并利用估計一階導數(shù)來實現(xiàn)。最后，WDTW 顯示出它是一個更大的可以包含歐氏距離、傳統(tǒng) DTW 的距離度量框架，同時 WDTW 也通過考慮了時序數(shù)據(jù)匹配過程中的 phase difference 為解決 singularities 問題提供了另一種思路。

源于距離矩陣的構建，DTW 及其變種的算法復雜度是相同的，均為 。此外，本文所述內容并未涉及 DTW 在大規(guī)模數(shù)據(jù)集檢索中的算法加速問題。實際上，在大規(guī)模的應用中，過去的研究已經有了很多方法來對 DTW 算法進行加速，如：FastDTW，LB_Keogh 等。

參考文獻

Keogh, E., & Ratanamahatana, C. A. (2005). Exact indexing of dynamic time warping.Knowledge and information systems,7(3), 358-386.?
Keogh, E. J., & Pazzani, M. J. (2001, April). Derivative dynamic time warping. InProceedings of the 2001 SIAM international conference on data mining(pp. 1-11). Society for Industrial and Applied Mathematics.?
Jeong, Y. S., Jeong, M. K., & Omitaomu, O. A. (2011). Weighted dynamic time warping for time series classification.Pattern recognition,44(9), 2231-2240.
維基百科.

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優(yōu)質內容以更短路徑到達讀者群體，縮短讀者尋找優(yōu)質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優(yōu)質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。

📝?稿件基本要求：

? 文章確系個人原創(chuàng)作品，未曾在公開渠道發(fā)表，如為其他平臺已發(fā)表或待發(fā)表的文章，請明確標注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發(fā)送，要求圖片清晰，無版權問題

? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內具有競爭力稿酬，具體依據(jù)文章閱讀量和文章質量階梯制結算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請備注即時聯(lián)系方式（微信），以便我們在稿件選用的第一時間聯(lián)系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現(xiàn)在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的衡量时间序列相似度的方法：从欧氏距离到DTW及其变种的全部內容，希望文章能夠幫你解決所遇到的問題。

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