SH專區 - Dynamic Time Warping(動態時間規劃) 2

在這一篇文章中，我們介紹兩個基本的方式來改進DTW的速度和準確性：warping constraint 和 z-normalization。

以及在金融數據上pattern的辨識與預測的簡單應用。

• Warping constrain

首先，讓我們先定義 warping constraint： 所謂的warping constraint就是我們的DTW路徑允許偏離對角線的程度。如下圖所示，warping constraint w = r/n （或是可以直接定義成 w = r）

Sakoe-Chiba Band

Source: Abdullah Mueen, Eamonn J. Keogh: Extracting Optimal Performance from Dynamic Time Warping. KDD 2016: 2129-2130

這個 w 有兩個作用：1. 加速整個演算法，2. 增加準確性

SH專區 - Dynamic Time Warping(動態時間規劃) 1

在接下來的一系列文章裡，我們希望能討論一個演算法：Dynamic Time Warping (動態時間規劃）以及其在金融交易中可能的應用。

這一系列的文章，都是我們的自學筆記，所以如果有理解錯誤或是疏漏的地方，請大家不吝告訴我們。

好了，進入主題吧。第一篇文章中，我們先簡單介紹一下DTW算法。

---

• 什麼是Dynamic Time Warping？

Dynamic Time Warping (動態時間規劃）本質上是一個 dynamic optimization 的問題，所尋找的是兩個序列之間的「最近距離」。

距離，不就只是 這樣？

是的，這就是我們一般常用的Euclidean distance。那麼，我們為什麼還需要DTW?