时间序列的搜索 | 目的地Destination

时间序列的搜索

时间序列的搜索

时间序列的搜索

在之前的时间序列相似度算法中,时间戳都是一一对应的,但是在实际的场景中,时间戳有可能出现一定的偏移,但是两条时间序列却又是十分相似的。例如正弦函数 /sin(x) 和余弦函数 /cos(x) ,只是平移了 /pi/2 个长度而已。本文将会介绍一些基于形状的时间序列的距离算法,并且介绍如何在给定时间序列的情况下,在时间序列数据库中寻找相似的时间序列。

基于动态规划的相似度计算方法

DTW 的经典算法

基于动态规划的相似度计算的典型代表就是 DTW(Dynamical Time Warping )和 Frechet 距离。在这里将会主要介绍 DTW 算法。详细来说,DTW 算法是为了计算语音信号处理中,由于两个人说话的时长不一样,但是却是类似的一段话,欧几里德算法不完全能够解决这类问题。在这种情况下,DTW 算法就被发展出来。DTW 算法是为了计算两条时间序列的最佳匹配点,假设我们有两条时间序列 QC ,长度都是 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}) 。特别地,

  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

对于两条时间序列 QC 而言,可以分别提取它们的四个特征,那就是最大值,最小值,第一个元素的值,最后一个元素的值。这样可以计算出 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 的时间序列 QC ,对于任意的窗口 r/geq 1, 有不等式 LBKeogh(Q,C)/leq DTW(Q,C) 成立。

所以,可以把搜索的算法进行加速:


1
<span></span>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 &lt; best_so_far true_dist = DTW(C_{i},Q) if true_dist &lt; 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
作者:张戎

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

分享

时间序列的搜索:等您坐沙发呢!

Leave your comment