作者?| 追光者

研究?| 機器學習與時間序列

出品 | AI蝸牛車

1.DTW

1.1 時序相似度

在時間序列數據中，一個常見的任務是比較兩個序列的相似度，作為分類或聚類任務的基礎。那么，時間序列的相似度應該如何計算呢？

“

經典的時間序列相似性度量方法總體被分為兩 類: 鎖步度量(lock-step measures) 和彈性度量(elastic measures) . 鎖步度量是時間序列進行 “一對一”的比 較; 彈性度量允許時間序列進行 “一對多”的比較.

——《時間序列數據挖掘的相似性度量綜述》

”

最簡單的相似度計算方法可能是計算兩個時間序列的歐氏距離。歐氏距離屬于鎖步度量

假設有兩個時間序列，Q和C，如果直接用歐氏距離計算相似度的話，如果存在時間步不對齊，序列長短不一等問題...

如上圖1所示，如果序列長短不一，或時間步不對齊的時候，歐氏距離是無法有效計算兩個時間序列的距離，特別是在峰值的時候。

圖2則是DTW算法，首先將其中一個序列進行線性放縮進行某種“扭曲”操作，以達到更好的對齊效果，可以存在一對多mapping的情況，適用于復雜時間序列，屬于彈性度量

1.2 DTW算法

動態時間規整在60年代由日本學者Itakura提出，用于衡量兩個長度不同的時間序列的相似度。把未知量伸長或縮短(壓擴)，直到與參考模板的長度一致，在這一過程中，未知序列會產生扭曲或彎折，以便其特征量與標準模式對應

首先假設有兩條序列Q和C，他們的長度分別是n和m

用一個矩陣來對比兩個序列，warping路徑會穿越這個矩陣，warping路徑的第k個元素表示為,橫縱代表的是兩個序列對齊的點

約束條件

1）邊界條件：和，表示兩條序列首尾必須匹配，各部分的先后次序匹配。

2）連續性： ? 如果且，則必須滿足且。這條約束表示在匹配過程中多對一和一對多的情況只能匹配周圍一個時間步的的情況，也就是不可能跨過某個點去匹配，只能和自己相鄰的點對齊。這樣可以保證Q和C中的每個坐標都在wraping路徑中出現。

3）單調性： 如果，且，則必須滿足且，表示warping路徑一定是隨時間單調遞增的。

滿足以上約束條件的warping路徑有很多，所以問題的本質是最優化問題——找出最優warping路徑，數學語言表示為：

解法思路是通過動態規劃算法，數學語言描述為：

時間復雜度

單調性與連續性約束直觀上表示為如下三種可能

1.3 優化方法

1.3.1 使用平方距離

原始DTW計算距離使用的是平方根計算，但是在排序任務中，平方或平方根不會對結果有影響，但是平方根計算資源消耗大，所以可以改為平方距離

1.3.2 Lower Bounding

顧名思義，這個優化方法的主要思想是先通過計算LB（lower bounding）處理掉不可能是最有匹配序列的序列，計算LB的主要有LB_Kim 和 LB_keogh等方法，這里只介紹一下LB_keogh，感興趣可自行查閱資料。

首先上公式

如上圖所示，首先找到找到序列的上包絡線U和下包絡線L，計算候選序列超出上下包絡線區域的部分之和作為下界。

1.3.3 Early Abandoning

從 K=0 開始逐步計算DTW并且和K后面的LB_keogh部分累加，判斷距離是否大于目前最好的匹配序列，在這個過程中，一旦發現大于當前最好匹配得距離，則放棄該序列停止DTW

1.3.4 Reordering Early Abandoning

如下圖所示，如果要早停的話，從序列的起點按順序計算不一定可以得到最優的結果。所以可以對序列進行排序先。首先對序列進行z歸一化，

除了以上優化方法，還有計算卷LB_Keogh時轉換Query/Data，級聯下界（Cascading Lower Bounds）等優化方法。

1.4 總結

優點：

1.支持非等長序列

2.支持有斷點序列

缺點：

1.不是一個嚴格的距離度量，因為它不符合三角形不等式，在一個度量空間中，距離必須符合三角形不等式。

2.對噪音敏感，所以需要對DTW的算法進行優化，不然時間復雜度很高

參考

《Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping 》——Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista2 , Brandon Westover1 , Qiang Zhu, Jesin Zakaria, Eamonn Keogh

《時間序列數據挖掘的相似性度量綜述》 ——陳海燕， 劉晨暉，孫 博

《時間序列數據挖掘中的動態時間彎曲研究綜述》——李海林，梁葉，王少春

更多精彩內容（請點擊圖片進行閱讀）

公眾號：AI蝸牛車

保持謙遜、保持自律、保持進步

個人微信

備注：昵稱+學校/公司+方向

如果沒有備注不拉群！

拉你進AI蝸牛車交流群

總結

以上是生活随笔為你收集整理的【时间序列】DTW算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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