Daily Archives: March 14, 2018

时间序列, 智能运维

时间序列的搜索

Leave a comment

在之前的时间序列相似度算法中，时间戳都是一一对应的，但是在实际的场景中，时间戳有可能出现一定的偏移，但是两条时间序列却又是十分相似的。例如正弦函数 \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\times 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}。

DTW1

现在我们需要找到一条路径使得

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

这条路径就是动态规划的解，它满足一个动态规划方程：对于 1\leq i\leq n, 1\leq j\leq 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 1\leq i\leq n, 1\leq j\leq n. 最终的取值 DTW(n,n) 就是我们需要的解，也就是两条时间序列的 DTW 距离。按照上面的算法，DTW 算法的时间复杂度是 O(n^{2})。特别地，

  1. 如果 dist(q_{i},c_{j}) = (q_{i}-c_{j})^{2} 时，则 \sqrt{DTW(n,n)} 表示最后的距离；
  2. 如果 dist(q_{i},c_{j}) = |q_{i}-c_{j}| 时，则 DTW(n,n) 表示最后的距离。
  3. 如果 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 取值范围是：对每一个 1\leq i\leq n，需要 j 满足\max(1,i-w) \leq j\leq \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，对于任意的窗口 r\geq 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 等，以及时间序列数据库的搜索算法。

 

Advertisement