基于MR框架的不确定时间序列相似性计算方法

李成为，王 屿，郑迪威

(南京航空航天大学 计算机科学与技术学院，江苏 南京 211106)

0 引 言

不确定时间序列(uncertain time series)是按照时间戳先后顺序排列的记录值的序列，在每个时间戳的序列值都是未知的或者不可预料的。不确定时间序列数据广泛应用于定位服务[1]、医疗数据分析[2]、时序数据库[3]、无线传感器网络[4]等等。不确定性的产生是由于数据采集和环境方面的误差[5]、使用了预测技术[6-7]，以及对于测量属性的多次读取数据[8]等因素。

在不确定时间序列数据处理的诸多任务和问题中，不确定时间序列相似性计算是其很重要的一个部分[9]。对于不确定时间序列相似性计算方法，主要从两个方向进行研究：一个是参考最初为确定性时间序列数据提出的相似性计算算法来进行改造[10-11]；一个是根据不确定时间序列的特性，融合传统的确定性时间序列相似性算法思想，提出专门适用于不确定时间序列的相似性算法[6-7,12-14]。文中主要对第二个方向进行研究。

在传统的确定性时间序列相似性计算方法中，DTW由于不要求两个序列等长，并且两个序列求差值的点可以一对多或多对一，广泛用于计算各种情况的时间序列相似性。文献[8]针对经典DTW算法具有较高计算时间和空间损耗的问题，提出解决流检测问题的ShortestDTW算法；文献[14]通过多次在一些超平面上的投影来组织序列，提出了FastDTW算法，但该算法需要预先知道不同对象之间的距离，属于一种粗犷的过滤方式，会带来许多不相似的噪音；文献[15]基于DTW原理提出了TD算法，对时间跨度较大且体现一个连续、完整过程的时间序列数和时间跨度较小、体现状态点的时间序列数据具有一定的计算效果；文献[16]提出一种将特征提取和降维进行融合的PLA-SDTW算法，可解决高维时间复杂度的问题。

针对时间序列数据具有较大数据量的特点[17]，近年来已有研究工作尝试使用MapReduce计算框架[18]计算时间序列的相似性。文中基于传统DTW算法，通过融入MR计算框架，提出一种不确定时间序列的相似性计算算法。该算法在不确定时间序列计算规模大时，并行计算每个子矩阵的动态时间规整距离，在获得与原DTW同等的匹配效果的同时，可使计算时间复杂度大为缩小。

1 基础知识

1.1 时间序列相似性计算

给定一个收集好的时间序列C={S1,S2,…,SN},其中N表示时间序列的数量，查询函数定义为：RQ(Q,C,ε)={S|S∈C|distance(Q,S)≤ε}，其中ε是使用者提供的距离阈值。

(1)DTW距离。

给定两个时间序列Q和C,它们的长度分别为n和m，将这两个时间序列记为：Q=,C=。它们之间的DTW距离的递归定义为：

其中，φ表示空时间序列；First(Q)表示时间序列Q的第一个元素；Rest(Q)表示时间序列Q除第一个元素外其他元素组成的子序列；dist2(x,y)为两点x和y的距离，通常采用欧氏距离进行计算。DTW的计算复杂度为O(nm)，计算代价较高，所以有研究人员对距离进行了变形处理。

(2)FastDTW距离。

先将两个时间序列粗粒度化，在递归到最底层后寻找最短DTW路径，然后每次细粒度扩展r个单位(r为半径)，即将路径及其周围的点逐步细粒度化，并再次寻找最短DTW路径，最终求出原始序列间的DTW距离。

FastDTW的细粒度化计算过程如图1所示。

图1 FastDTW的细粒度化计算过程

第一幅图表示在递归最底层阶段执行DTW算法。第二幅图表示在递归返回阶段，将第一幅图求得的路径经过的方格进行细分，并且向左右，上下，以及左上右下的斜对角方向扩展r个单位，重新执行DTW算法得到的新路径。以此类推，直到最后求得最终的路径。

1.2 不确定时间序列及其期望距离

不确定时间序列的每个元素x都可以表示为x=r(x)+ε(x)，其中r(x)表示该元素的真实值，ε(x)表示该元素的误差，是服从某一连续型分布函数或某离散型分布的随机变量。不确定时间序列T定义为一系列随机值的集合T=，其中ti是在时间戳i对实数值的随机变量建模。

期望距离[19]可以用来计算两个不确定时间序列数据之间的距离，该算法是用所有可能出现的计算结果的均值加上误差值来代表这两个不确定时间序列之间的距离。期望距离的具体定义如下：两个时间序列X,Y(其中至少有一个是不确定时间序列)的概率分布为f(x)、f(y)，则它们的期望距离为：

其中，pointsdis(x,y)可以用‖x-y‖2表示，即x2+y2-2|xy|，可以推导出：

上述公式即表明了期望距离可以用时间序列中各个时间点之间的距离的期望和方差来表示，由此可以大大减少不确定时间序列之间点与点之间距离的计算量。

2 MR-FastDTW算法

FastDTW算法通过粗细粒度化的变化，在计算路径时，首先计算递归最底层的路径，并在返回阶段，围绕着上一阶段得出的路径拓展相应范围的计算矩阵，减少DTW暴力求解所造成的无用计算带来的损耗。

算法1描述了FastDTW的计算过程：

算法1:FastDTW算法

Input:长度分别为|X|和|Y|的两段时间序列X和Y；

阈值Radius//最粗分辨率的最小值

Output:时间序列X和Y之间的最小DTW距离;X与Y之间的规整路径

1.Integer minTSsize=radius+2

2.IF(|X|≤minTSsize OR |Y|≤minTSsize)

3.RETURN DTW(X,Y)

4.ELSE

5.TimeSeries shrunkX=X.reduceByHalf()

6.TimeSeries shrunkY=Y.reduceByHalf()

7.WarpPath lowResPath=FastDTW(shrunkX, shrunkY,radius)

8.SearchWindow window=Exp[andeResWindow(lowResPath,X,Y,radius)]

9.RETURN DTW(X,Y,window)

针对FastDTW计算方法在递归返回阶段执行到一定程度后，文中采用MR计算框架简化相似性计算，提出了MR-FastDTW算法，以提升运行速度。

对于一个给定的不确定时间序列，在FastDTW算法执到第1步和第12步时，MR-FastDTW算法采用了期望距离来执行不确定性数据的相似性计算。在执行MR计算框架时，对于递归到一定程度后即第12步，对矩阵进行分块处理，分块好的矩阵进行Map处理，产生相应的值对，然后用Reduce对这些生成的键值对进行处理，执行递归细粒度化，并在新的搜索矩阵上面执行上述步骤，以此重复，得到最后的结果。该算法的详细步骤如下：

1.输入采集到的序列A、待检测的确定时间序列B。

2：执行FastDTW算法，DTW计算过程使用期望距离来计算。当粗粒度进行到第n(n>3)次细粒度化时，把细粒度化好的矩阵放入MR计算框架中执行计算。

3：执行MR计算。

(1)由于DTW的计算矩阵是n*m矩阵，将序列X划分为长度分别为[m/p]的p个子序列X0,X1,…,Xp-1，将序列Y划分为长度分别为[n/q]的q个子序列Y0,Y1,…,Yq-1。于是就构造了p*q个子矩阵Mf*g,f[1,p],g[1,q]。每个子矩阵的规模为[m*n]/[p*q]。

(2)每个子矩阵求的路径作为key值，编号作为value值进行排序。

(3)排序过后的值传入Reduce部分，进行路径汇总筛选，并规约在一起得出总的动态规约路径。

算法2描述了MR-DTW的计算过程：

算法2：MR-DTW算法

Input:时间序列X,Y,规约窗口window,p,q

Output:MR-DTW(X,Y,window)//需要加上window参数

1.INTEGERn/q,m/p

2.DTW(n2,m2)

3.MAP://MAP阶段

4.E((1,2,…,n/q),m/p)→HDFS //D1*1最后一行的值

5.E(n/q,(1,2,…,m/p))→HDFS→HDFS//D1*1最后一列

6.HDFS[E((1,2,…,n/q),m/p)]→Matrix((n/q,n/q+1,…,n/q*2),m/p)

7.D(n/q*2,m/p)

8.//读取HDFS中的D1*1最后一行，存入D2*1的第0行

9.HDFS[E(n/q,(1,2,…,m/p))]→Matrix(n/q,(m/p,m/p+1,…,m/p*2))

10.D(n/q*2,m/p*2)

11.//读取HDFS中的D1*1最后一列 ，存入D1*2的第0列

12.E(n/q,(m/p,m/p+1,…,m/p*2))→HDFS

13.E((n/q,n/q+1,…,n/q*2),m/p)→HDFS

14.//将第D1*2的最后一列和D1*2的最后一行存到HDFS

15.//…并行计算子矩阵,中间重复步骤

16.HDFS[E((n*(q-2)/q,n*(q-2)/q+1,n(q-1)/q),m)]→Matrix((n(q-1)/q,n(q-1)/q+1,…,n),m)

17.HDFS[E(n,(m*(p-2)/p,m*(p-2)/p+1,…,m(p-1)/p))]→Matrix(n,(m*(p-1)/p,m*(p-1)/p+1,…,m))

18.D(n,m)

19.//获取子矩阵D(f-1)*g的最后一行以及矩阵Df*(g-1)的最后一列，存入到Df*g的第0行第0列，计算Df*g

20. SORT: //SORT阶段

21.Sort(D(n/q,m/p),…,D(n,m))//对p*q个矩阵的值排序

22.REDUCE://REDUCE阶段

23.Combime(key) according to the sort result

24．//根据sort结果，筛选链接每个小矩阵的值

25.Return DTW(n,m)

把MP-DTW算法与FastDTW算法相结合，得到了基于MR计算框架的MR-FastDTW算法。算法3描述了MR-FastDTW的计算过程：

算法3：MR-FastDTW算法

Input:长度分别为|X|和|Y|的两段不确定时间序列X和Y，FastDTW扩展半径r，起始执行并行算法阈值num

Output:MR-FastDTW动态弯曲矩阵距离

1.Integer minTSsize=radius+2

2.IF(|X|≤minTSsize OR |Y|≤minTSsize)

3.RETURN DTW(X,Y)

4.ELSE

5.TimeSeries shrunkX=X.reduceByHalf()

6.TimeSeries shrunkY=Y.reduceByHalf()

7.WarpPath lowResPath=FastDTW(shrunkX,shrunkY,radius)

8.SearchWindow window=Exp[andeResWindow(lowResPath,X,Y,radius)]

9.IF NUM

10.RETURN DTW(X,Y,window)

11.ELSE

12.RETURN MR-DTW(X,Y,window)

3 实验验证

3.1 测试数据集的选择

从UCR数据集中随机抽取8组数据作为实验测试数据集。8组数据的具体构成见表1。

表1 由UCR数据集构建的不确定时间序列

3.2 算法精确度和复杂度的比较

实验采用4台计算机通过路由器组建Hadoop集群，每台计算机的内存为4 GB，处理器为Intel i5-6500，操作系统为Win7。一台作为主节点，三台作为数据节点。使用表1中的数据集人工合成不确定时间序列，对MR-FastDTW算法与传统的DTW算法和FastDTW算法进行比较。

(1)精确度对比。

精确度是对比不同算法之间准确性的标准，即不同算法检测的结果与实际不确定时间序列的结果相比较的准确程度。由于不确定数据存在误差，所以对每组实验数据测十次，并取均值。再用不同的算法单次读取该数据，并与均值进行比较。DTW算法未对数据进行任何限制处理，所以得到的结果精确度最高；FastDTW算法采用了粒度化的方法对数据集进行了限制处理，精确度略有下降，但仍有较高的准确度；MR-FastDTW算法的精确度与FastDTW算法的精确度基本一致，也表现出较高的准确度。精确度比较如图2所示。

图2 相似性算法的精确度比较

(2)时间复杂度对比。

时间复杂度主要是不同算法执行同组数据所消耗的时间。时间复杂度的比较如图3所示。

图3 相似性算法的时间复杂度比较

从图3可以看出，当数据量很小时，三种算法没有太大的差异。当参与计算的数据量逐步增加时，DTW算法其时间消耗随数据规模的增大开始非线性增长，FastDTW算法和MR-FastDTW算法的时间消耗表现平稳。当数据量规模超过900时，DTW算法时间消耗会急剧增长，FastDTW算法由于是串行计算，时间消耗有所增大，而MR-FastDTW算法由于是并行处理，时间消耗最小。

4 结束语

提出了基于MR计算框架的MR-FastDTW算法，解决了FastDTW在递归返回段执行到一定程度后计算量大的问题，在提高计算速度的同时，提高了计算准确性。

需要指出的是，目前MR-FastDTW算法在执行过程中需要使用阈值，它控制着递归返回段进行到何种程度时再进行MapReduce计算，因此阈值是MR-FastDTW算法实现的一个关键点。但是，阈值的取值目前还没有一个严格的范围标准，当前只是大概取程序在递归返回阶段执行到三分之一时刻的值，这只是经验值，缺乏严格的论证和理论依据。此外，该算法在执行矩阵拆分以及合并计算值时，操作还稍显繁琐。所有这些都将是未来工作中需要改进的地方。