使用這些基本 REST API 最佳實踐構建出色的 API
在應用歐氏距離時，第一個時間序列中的第 i 個點分別與第二個時間序列中的第 i 個點形成一一對應。然而，歐氏距離在某些情況下會出現問題，如下圖 2 所示：
當兩個時間序列的長度不相等時，較長的一個時間序列總會剩下無法被匹配到的點，這種情況如何計算歐氏距離？毫無疑問，此時歐氏距離不再可行。此外，如圖 1 中紅圈所示，兩個時間序列在時間軸上有一定的平移但總體的趨勢是相似的，自然地，當我們想人為對齊圖1中兩個時間序列時，紅圈中的兩個向下凸起的點應該相互對應起來。很顯然，歐氏距離的這種方式按順序點對點的方法無法滿足我們的需求。
綜上，在時間序列間的距離度量上，歐氏距離有以下限制：
（1）只適用于處理等長的時間序列；
（2）在將時間序列對齊時無法考慮?X?軸上的變化，導致有時對齊出現不自然。
特別地，作為一種常見的標準距離度量，歐氏距離是另一種更為廣泛的距離度量——閔式距離（Minkowski distance）當 p 取值為 2 時的特例。閔式距離中 p=1 時和 p=infinity 時，分別對應曼哈頓距離和兩個時間序列點與點之間距離差值的最大值。
針對上文提到的歐氏距離無法處理不等長數據、處理等長數據時對齊不自然的兩個主要問題，為了解決不等長數據的距離度量和匹配問題，上世紀 70 年代，日本學者 Itakura 等人提出了 DTW。在過去的幾十年里，DTW 已經被廣泛應用于孤立詞語音識別、手勢識別、數據挖掘和信息檢索等場景中，DTW 一度是語音識別的主流方法。DTW 的原理此處簡述如下：
對于兩個不等長的時間序列 Q 和 C，長度分別為 n 和 m：
滿足這些條件的 W 還是有很多個，DTW 只尋找能夠最小化 warping cost 的 W：
在上式中，K 是 warping path 的長度，除以 K 可以消除不同長度的 warping path 的影響。
最終，兩個不等長時序數據的對應關系可以通過動態規劃來求解以下遞歸式得到：
盡管 DTW 已經被成功應用到很多領域中，DTW 依然存在缺點：有時 DTW 會在對齊時產生不自然的扭曲/翹曲。如下圖 4 所示：
A 中實線、虛線所展示的是兩條合成信號（均值、方差都相同），B 中展示的是自然的“feature to feature”的對應，而 C 中展示的則是 DTW 的結果。不難發現，DTW 沒能自然地將圖形中的波峰與波峰相對應，反而產生了一個序列中的一個點對應另外一個序列中的多個點的情況，這種情況被稱為“Singularities”。出現這種情況的原因是 DTW 算法試圖通過扭曲 X 軸來解釋 Y 軸上的變化。
為了解決“Singularities”問題，過去的研究提出了很多方案，大致可歸為以下三類：
1-Windowing：歸根結底，出現 singularities 就是因為兩個時間序列上相隔很遠的點僅因為值相同/相近容易被 warping 到一起。可以限制 DTW 在 warping 過程中的能選擇的范圍來解決 singularities，具體可以通過設置一個 warping window 來實現，故稱之為 Windowing方法。數學上可寫作：，?作為 window width 是一個正整數。圖 3 中兩虛線所夾范圍即為經 window 限制后的范圍，此時 warping path 就只能在此區域內。
2-Slope weighting：當傳統 DTW 中的遞歸式改為下式時，即可實現 slope weighting。
不難發現，唯一的區別在于在 min 函數中的后兩項前加了 X ，X 為一個正實數。當對 X 的值進行調整時，可以使得 warping path 的方向（slope）會有一定的調整。X?取較大值時，warping path 的選擇會更多的朝向對角線方向。
3-Step patterns：改變傳統 DTW 中的遞歸式為下式可以實現改變 warping path step。
將傳統 DTW 中的遞歸式和上式分別可視化如下圖 5 中 A、B 所示：
A 所對應的即為傳統 DTW 的遞歸式，下一步只能在距離矩陣中相鄰的三個方格中選取，而 B 中所對應的就是改變了 step 后的遞歸式。相較于 A 中，B 中對于每一個第一步沒有沿著對角線方向走的方格都再朝其所在方格的對角線方向移動一步，這樣即可實現改變 step pattern。
總的來說，以上三類解決方案在一定程度上對解決 singularities 有一定幫助，然而，它們仍然存在以下缺點：
（1）有可能錯過正確的 warping path。以上三類方法都是在沒有任何前提條件的情況下人為地對 warping path 進行限制和調整來減少翹曲，這很有可能會錯過真正正確的 warping path。
（2）參數的選擇沒有明確的指導。在 Windowing 方法中 R 值的選取、Slope weighting 方法中 X 都是人為視具體場景主觀調整、沒有明確標準的。
實際上，DTW 之所以造成“Singularities”，本質上是由于 DTW 算法本身所考慮的特征決定的：DTW 算法只考慮數據點在 Y 軸上的值。
例如：兩個數據點??和??的值相同，但是??位于一個時間序列的上升趨勢部分，而??位于一個時間序列的下降趨勢部分。對于 DTW 而言，很容易將這兩個點匹配在一起，因為它們的值相同。然而，從直覺上來說，我們很難把兩個趨勢相反的部分匹配在一起。為了避免 DTW 只考慮 Y 軸的值造成“Singularities”問題， DDTW 出現了。
DDTW 不考慮數據點的 Y 軸的值，而是考慮更高層次的特征——時序數據的“形狀”。該方法通過計算時序數據的一階導數來獲取與“形狀”相關的信息，所以被稱為 Derivative DTW。
DDTW 本身的概念也很簡單，對于傳統 DTW 而言，距離矩陣中的元素即為兩個點??和??之間的距離；然而對于 DDTW 而言，此時的“距離矩陣”中的元素不再是兩點之間的距離，而是時序數據在兩點處一階導數的差值的平方。盡管有多種方法估計一階導數，出于簡便和拓展性，DDTW 中的一階導數估計采用以下方法：
不難發現，在??點處一階導數的估計就是通過該點和該點左邊點的直線斜率與通過該點左邊點和該點右邊點的直線斜率的平均數。Keogh, E. J., & Pazzani, M. J. 提到，在只考慮兩個數據點的情況下，這種估計方法面對 outliers 更為穩定。
需要注意的是，這種一階導數的估計方法無法計算時序數據的第一個數據點和最后一個數據點的一階導數，在實際操作時可以用第二個數據點和倒數第二個數據點的導數來替代。此外，對于高噪聲的數據集可以在估計一階導數之前先做 exponential smoothing。
上文提到，經典的 DTW 算法在匹配兩個時間序列上的點時僅考慮 Y 軸上的值，而不考慮所匹配的點在 X 軸上的差別，因此會造成時序數據匹配時的“Singularities”問題。
歸根結底，“Singularities”問題在某種程度上就源于只考慮 Y 軸的值，第一個序列上的一個點可以跟第二個序列上的另一個很遠（此處“遠”指的是 X 軸的距離/序數）的點匹配起來，加上 DTW 中 warping path 的連續性、單調性條件，造成了時序數據對齊過程中的各種翹曲/扭曲。
DDTW 通過考慮“形狀”利用估計時序數據的一階導數來解決這個問題，而 WDTW 則采用了不同的思路。簡單來說，WDTW 選擇在計算兩個序列上的兩個點之間歐氏距離時加上一個 weight，而這個 weight 與兩個點之間的 X 軸上的距離有關系。具體如下（p=2）：
綜上，本文從只能處理等長數據且容易造成不自然對齊的歐氏距離出發，我們逐步論述了 DTW 出現的原因和重要性。進一步，我們發現傳統 DTW 算法帶來的 singularities 問題可以在 windowing、slope weighting、step pattern 等方法下得到一定改善。然而，從算法考慮的特征層面出發，為了解決 DTW 算法匹配時序數據時可能存在的 singularities 問題，DDTW 提出考慮更高層次的特征——形狀，并利用估計一階導數來實現。最后，WDTW 顯示出它是一個更大的可以包含歐氏距離、傳統 DTW 的距離度量框架，同時 WDTW 也通過考慮了時序數據匹配過程中的 phase difference 為解決 singularities 問題提供了另一種思路。
源于距離矩陣的構建，DTW 及其變種的算法復雜度是相同的，均為?。此外，本文所述內容并未涉及 DTW 在大規模數據集檢索中的算法加速問題。實際上，在大規模的應用中，過去的研究已經有了很多方法來對 DTW 算法進行加速，如：FastDTW，LB_Keogh 等。
文章轉自微信公眾號@算法進階