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