时间序列的搜索

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

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

$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})$ 。特别地，

如果 $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$ 取值范围是：对每一个 $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 等，以及时间序列数据库的搜索算法。

来源：知乎 www.zhihu.com

作者：张戎

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载