時間序列的搜索

08-18

時間序列的搜索

來自專欄數學人生73 人贊了文章

時間序列的搜索

在之前的時間序列相似度演算法中，時間戳都是一一對應的，但是在實際的場景中，時間戳有可能出現一定的偏移，但是兩條時間序列卻又是十分相似的。例如正弦函數 $sin(x)$ 和餘弦函數 $cos(x)$ ，只是平移了 $pi/2$ 個長度而已。本文將會介紹一些基於形狀的時間序列的距離演算法，並且介紹如何在給定時間序列的情況下，在時間序列資料庫中尋找相似的時間序列。

基於動態規劃的相似度計算方法

DTW 的經典演算法

基於動態規劃的相似度計算的典型代表就是 DTW（Dynamical Time Warping ）和 Frechet 距離。在這裡將會主要介紹 DTW 演算法。詳細來說，DTW 演算法是為了計算語音信號處理中，由於兩個人說話的時長不一樣，但是卻是類似的一段話，歐幾里德演算法不完全能夠解決這類問題。在這種情況下，DTW 演算法就被發展出來。DTW 演算法是為了計算兩條時間序列的最佳匹配點，假設我們有兩條時間序列 $Q$ 和 $C$ ，長度都是 $n$ ，並且 $Q:{q_{1},q_{2},cdots,q_{n}}$ 和 $C:{c_{1},c_{2},cdots,c_{n}}$ 。首先我們可以建立一個 $n imes n$ 的矩陣， $(i,j)$ 位置的元素是 $dist(q_{i},c_{j})$ ，這裡的 dist 可以使用 $L^{1}, L^{2}, L^{p}, L^{infty}$ 範數。其次，我們想找到一條路徑，使得這個矩陣的累積距離最小，而這條路則是兩條時間序列之間的最佳匹配。在這裡，我們可以假設這條路徑是 $W: {w_{1},cdots,w_{K}}$ ，其中 $W$ 的每個元素表示時間序列 $Q$ 中的第 $i$ 個元素和時間序列 $C$ 中的第 $j$ 個元素之間的距離. i.e. $w_{k}=(q_{i}-c_{j})^{2}$ 。

現在我們需要找到一條路徑使得

$W^{*} = argmin_{W}(sqrt{sum_{k=1}^{K}w_{k}}).$

這條路徑就是動態規劃的解，它滿足一個動態規劃方程：對於 $1leq ileq n, 1leq jleq n$ ，有

$DTW(i,j)= dist(q_{i},c_{j}) + min(DTW(i-1,j-1), DTW(i-1,j), DTW(i,j-1)).$

其初始狀態是 $DTW(0,0)=0, DTW(i,0)=infty, DTW(0,j)=infty,$ $forall 1leq ileq n, 1leq jleq n.$ 最終的取值 $DTW(n,n)$ 就是我們需要的解，也就是兩條時間序列的 DTW 距離。按照上面的演算法，DTW 演算法的時間複雜度是 $O(n^{2})$ 。特別地，

如果 $dist(q_{i},c_{j}) = (q_{i}-c_{j})^{2}$ 時，則 $sqrt{DTW(n,n)}$ 表示最後的距離；
如果 $dist(q_{i},c_{j}) = |q_{i}-c_{j}|$ 時，則 $DTW(n,n)$ 表示最後的距離。
如果 $dist(q_{i},c_{j}) = |q_{i}-c_{j}|^{p}$ 時，則 $(DTW(n,n))^{1/p}$ 表示最後的距離。

Remark.

DTW 演算法不滿足三角不等式。例如： $x={0}, y={1,2}, z={1,2,2},$ 則

$DTW(x,z)=5>DTW(x,y)+DTW(y,z) = 3 + 0 =3.$

DTW 的加速演算法

某些時候，我們可以添加一個窗口長度的限制，換言之，如果要比較 $q[i]$ 與 $c[j]$ 的話，i 與 j 需要滿足 $|i-j|leq w,$ 這裡的 $w$ 表示窗口長度。因此演算法的描述如下：

初始條件和之前一樣。

$DTW(i,j) = dist(q_{i},c_{j}) + min(DTW(i-1,j-1), DTW(i-1,j), DTW(i,j-1)),$

這裡的 $j$ 取值範圍是：對每一個 $1leq ileq n,$ 需要 $j$ 滿足 $max(1,i-w) leq jleq min(m,i+w).$

相似時間序列的搜索

相似的時間序列的搜索問題一般是這樣的：

Question 1. 給定一條時間序列 $Q$ 和一個時間序列的資料庫 $D={C_{i}}_{i=1}^{infty}.$ 通過某種相似度或者距離計算方法，計算出給定的時間序列 $Q$ 與時間序列資料庫中 $D$ 中最相似的時間序列。

Question 2. 給定一條時間序列 $Q$ 和一個時間序列的資料庫 $D={C_{i}}_{i=1}^{infty},$ 以及正整數 $K.$ 從資料庫 $D$ 中尋找與給定的時間序列 $Q$ 最相似的 $K$ 條時間序列。

DTW 演算法的下界 LB_Kim

對於兩條時間序列 $Q$ 和 $C$ 而言，可以分別提取它們的四個特徵，那就是最大值，最小值，第一個元素的值，最後一個元素的值。這樣可以計算出 LB_Kim

$LBKim(Q,C) = max{|max(Q)-max(C)|,|min(Q)-min(C)|,|First(Q)-First(C)|,|Last(Q)-Last(C)| }.$

可以證明 $LBKim(Q,C)leq DTW(Q,C).$

DTW 演算法的下界 LB_Yi

有學者在 LB_Kim 的基礎上提出了一種下界的計算方法，那就是 LB_Yi，有興趣的讀者可以參見：efficient retrieval of similar time sequences under time warping，1998.

DTW 演算法的下界 LB_Keogh

但是，如果是基於 DTW 的距離計算方法，每次都要計算兩條時間序列的 DTW 距離，時間複雜度是 $O(n^{2})$ 。於是就有學者研究是否存在 DTW 距離的下界表示，也就是說找到一個合適的下界，Lower Bound of DTW。每次判斷 Lower Bound of DTW 是否小於當前的最小距離，如果下界高於最小距離，就不需要進行 DTW 的計算；否則開始計算 DTW 的值。如果下界的計算速度足夠快，並且下界足夠精準的話，可以大量的壓縮搜索的時間。於是，Keogh 提出了下界的計算方法。

（1）首先定義時間序列 $Q$ 的上下界。i.e. $Q:{q_{1},cdots,q_{n}},$ 給定一個窗口的取值 $r,$ 得到 $U_{i}=max(q_{i-r},q_{i+r}),$ $L_{i} = min(q_{i-r},q_{i+r}).$

（2）定義公式：

$LBKeogh(Q,C)= sqrt{sum_{i=1}^{n}(c_{i}-U_{i})^{2}I_{{c_{i}>U_{i}}} + sum_{i=1}^{n}(c_{i}-L_{i})^{2}I_{{c_{i}<L_{i}}}}.$

其中，LBKeogh 滿足性質：

對於任意兩條長度為 $n$ 的時間序列 $Q$ 和 $C$ ，對於任意的窗口 $rgeq 1,$ 有不等式 $LBKeogh(Q,C)leq DTW(Q,C)$ 成立。

所以，可以把搜索的演算法進行加速：

Lower Bounding Sequential Scan(Q) best_so_far = infinity for all sequences in database LB_dist = lower_bound_distance(C_{i},Q) if LB_dist < best_so_far true_dist = DTW(C_{i},Q) if true_dist < best_so_far best_so_far = true_dist index_of_best_match = i endif endif endfor

在論文 Exact Indexing of Dynamic Time Warping 裡面，作者還嘗試將 Piecewise Constant Approximation 與 LB_Keogh 結合起來，提出了 LB_PAA 的下界。它滿足條件 $LBPAA(Q,C)leq LBKeogh(Q,C)leq DTW(Q,C).$

總結

本文初步介紹了 DTW 演算法以及它的下界演算法，包括 LB_Kim, LB_Keogh 等，以及時間序列資料庫的搜索演算法。