基于时间序列波动性的分段线性表示方法①

李 颖,于 东,胡 毅,刘劲松,张丽鹏

1(中国科学院 沈阳计算技术研究所,沈阳 110168)

2(中国科学院大学,北京 100049)

3(沈阳中科数控技术股份有限公司,沈阳 110168)

1 引言

在这个信息化时代中,随着计算机技术的高速发展,信息的产生、收集和存储能力不断增强,产生了越来越多的数据.数据类型不断增多:图像、文本、音频等.时间序列型数据不仅只在时间上具有前后关系,任何逻辑上具有先后关系且不可改变的数据都是时间序列型数据.所以,时序数据广泛存在于各个数据类型中.因此,时间序列型数据得以在医疗诊断、工业生产与控制、运动检测、生物识别、考古研究等生活的各个领域中应用广泛.但是,通常采集到的时序型数据在一个维度上会不断增加,所以时间序列型数据具有数据维度高、数据量大[1]的特点.若直接使用传统的数据挖掘技术对时间序列数据进行分析不仅需要耗费大量的时间和存储成本[2],还很可能难以分析,得不到结果.

为了在保留时间序列有效特征的前提下,减少数据量,对数据进行压缩,Keogh、Chu和Hart 提出了PLR[3]表示方法.PLR 方法是时间序列的分段线性表示方法.该方法的主要思想是从原始时间序列中提取重要特征点,用这些特征点连接起来的直线段代表原时间序列.这种方法用寻找到的关键点更直观地展示了原始时间序列的特征.Ehmke 等[4]提出了自顶向下的TD 方法寻找关键点.与文献[4]不同,Theodosios等[5]以自底向上的BU 方法寻找关键点.两个方法都是时间序列分段线性表示的经典算法,但都存在时间复杂度较高的问题.为了提高查找效率,Chakrabarti 等[6]引入了滑动窗口,降低了查找的时间复杂度.林意等[7]从时间序列的形态出发,将其与几何图形结合,提出了PLR_WFTP 方法.詹艳艳等[8]则将斜率变化(PLR_SEEP)作为关键点的判断指标.汤晶晶等[9]通过点边界面积(PLR_AP)作为判断点的重要性,以此来作为该点是否能成为关键点的依据.肖辉等[10]提出了基于时态边缘算子的TEO 方法.

本文研究了时间序列的状态,发现了时间序列的波动特性,在结合前人研究的基础上,提出了基于时间序列波动性的分段线性表示方法.该算法将时间序列的趋势分为上、下两层,在此基础上提取关键点,将原来3 点之间的比较扩大为9 个点,很好地保留了时间序列的全局特征.同时,该算法在关键点的提取过程中,忽略了对趋势变化没有贡献的点.在提取连续型趋势段中的关键点时得到的点数更少,结果更精确,有更小的拟合误差.

2 基本定义

定义1.时间序列.X(t)={x(t1),x(t2),x(t3),…,x(tm)}是一个长度为m的有序数据集合.其中x(ti)=＜xi,ti＞,(i=1,2,3,…,m;m∈N+)表示X在ti时刻采集到的数据值为xi,xi可以是单个数据值,也可以是一个数据集合.通常,t1=0,Δt=1,(Δt=ti−ti−1).因此,时间序列X可简单地记为X={x1,x2,xi,…,xm},(m≥1,m∈N+).当数据空间的维度为N时,该时间序列的每个数据项都有n个分量,则X的第i个数据项可表示为:

其中,xij表示xi在第j个维度的分量坐标值.本文只考虑数据空间为一维的情况,即j=n=1.由于时间序列的广义化,采集到的数据值xi可以是多种类型的,如:符号、文本、图像、声音等.本文只考虑xi是实值型数据的情况.

定义2.拟合误差.设原时间序列X={x1,x2,x3,…,xn},分段操作得到的分段点集合为X′={x1′,x2′,x3′,…,xk′},其中x1=x1′,xn=xk′,k＜n.线性插值后得到的新时间序列为XC={xc1,xc2,xc3,…,xcn}.定义新时间序列与原时间序列之间的欧式距离为拟合误差.其公式如下:

定义3.压缩率.原时间序列X={x1,x2,x3,…,xn},经过PLR 算法得到的新时间序列X′={x1′,x2′,x3′,…,xk′}.定义该算法的压缩率如下:

3 基于时间序列波动性的分段线性表示方法

3.1 趋势转折点

研究中,观察到时间序列中的点总是波动的,在整体上呈现出某种趋势和趋势变化.研究发现,时间序列的变化可细分为“上升”、“下降”、“保持”这3 种基本趋势.基于这3 种基本趋势,3 个相邻的时间序列点可呈现出9 种趋势变化[11].其中有6 种发生趋势转折,其余3 种保持趋势不变.基本趋势模式如图1所示.

图1 基本趋势模式

时间序列3 点间的趋势变化模式如图2、图3所示.

图2 6 种趋势转折

图3 4 种趋势保持

3.2 上、下层备选点

研究发现,对时间序列3 点间趋势变化模式的描述可以扩展到整个时间序列.由于序列总是波动的,在某一时间段内才稳定呈现出上升、下降、保持其中一种趋势.将这些时间段中的趋势连接起来,就得到了时间序列整体趋势变化模式.在对时间序列进行分段时,无论是基于斜率[8]的方法还是引入几何中三角形[9,11–13]的方法,都关注于极值点和拐点.从极值点和拐点中提取重要特征点.因此,现有的时间序列分段方法很容易陷入局部最优的状态,从而忽略了时间序列的全局特征.针对现有分段方法忽略了时间序列整体特征这一问题,本文研究了时间序列的发展趋势,发现时间序列的趋势总是由波动点构成的:时间序列中的点总是波动的,不是向上波动就是向下波动.因此可以认为,波动点描述了时间序列的变化趋势.基于此发现,本文提出了时间序列分层的概念,为关键点的选取打下基础.其定义如下:

设有时间序列X(t)={x(t1),x(t2),x(t3),…,x(tn)}.其中x(ti),i=1,2,3,…,n表示该序列在时刻ti的数据值为x(ti),简写为xi.

定义4.(上层备选点).对于时间序列中的任意一点xi,若满足xi＞xi−1或xi＞xi+1,则称xi属于上层备选点.

定义5.(下层备选点).对于时间序列中的任意一点xi,若同时xi＜xi−1或xi＜xi+1,则称xi属于下层备选点.

性质.时间序列的上下两层备选点,分别保留了时间序列上层和下层的重要特征.

3.3 关键点

时间序列分段线性表示方法的主要内容是找到时间序列中的关键点,即时间序列中左右两边趋势发生变化的点.由时间序列3 点间的趋势变化模式可知,只有在趋势转折点处的趋势才发生变化.同时,若一个点不是趋势转折点,则它一定是趋势保持点.所以,时序中的点除趋势保持点以外都是趋势转折点,即关键点.基于此发现,本文分别遍历上、下层备选点,判断其与相邻备选点之间的大小,若满足保持趋势关系,则剔除掉.遍历完成之后得到的剩余点就是关键点.

3.4 算法描述

算法流程图,如图4所示.

图4 算法流程

输入:时间序列X={x1,x2,x3,…,x1}

步骤1.提取备选点

比较xi与其相邻点的大小,若xi＞xi−1则认为该点是上层备选点.将该点的值保存到up_v 数组中,该点的位置信息保存到up_k 数组中;若xi＜xi+1或xi＜xi−1,则认为该点是下层备选点.将该点的值保存到low_v数组中,该点的位置信息保存到low_k 数组中.

步骤2.提取关键点

遍历up_v和up_k 数组,若当前点up_v[i]不满足up_v[i+1]＞up_v[i]＞up_v[i−1],同时不满足up_v[i+1]＜up_v[i]＜up_v[i−1],即当前上层备选点不是趋势保持点,那么当前点是关键点.将该点的数值信息及位置信息保存到up 集合中,以该点的位置信息作为集合的key 值,该点的数值信息作为集合的value 值;遍历low_v和low_k 数组,若当前点low_v[i]不满足low_v[i+1]＞low_v[i]＞low_v[i−1],同时不满足low_v[i+1]＜low_v[i]＜low_v[i−1],即当前下层备选点不是趋势保持点,则当前点是关键点.将该点的数值信息及位置信息保存到low 集合中.同样,以该点的位置信息作为low集合的key 值,该点的数值信息作为low 集合的value 值.

注意到,无论是上层备选点还是下层备选点都不包括连续相邻三点值相等的情况.这是因为,在波动点的提取过程中,忽略了不发生波动的点.然而,这对关键点的提取并没有影响.因为,关键点只在极值点和拐点中包括.

步骤3.将up 集合和low 集合合并,并按照key值排序.将排好序的数据放入关键集合.

步骤4.采用线性插值方法对关键点区间进行拟合.

输出:新的序列.

从以上的算法描述可以看出,该算法主要分成两个部分:第1 部分扫描时间序列,提取备选点;第2 部分从备选点序列中提取关键点.经过优化,PLRGFKP算法只需对时间序列进行一次扫描,其时间复杂度为O(n).

4 实验分析

4.1 实验数据

本文首先对工业时序数据进行分段线性表示,以PCoE 数据集中的铣削数据集为例,该数据集由UC Berkeley 的the BEST lab[14]实验室提供,记录了铣削刀片VB 的磨损程度.

为了验证本文算法的适用性.本文选取了来自不同领域的UCR 公开数据集[15]中的6 条实际时间序列作为实验数据,并用来比较各算法的性能.其数据信息如表1所示.

表1 实验数据集

数据表中显示了6 条时间序列的名称和长度.该数据集中包括了长度较短、长度一般、长度较长的3 种时间序列.HandOutLines (HOL)序列长度最长.其中,RefrigerationDevices (RD) 序列呈周期性变化、UWaveGestureLibraryAll (UWLA)序列变化没有规律、Phoneme 序列斜率变化集中.

4.2 实验方法

本文实验环境为:Windows10 操作系统、Inter-i5处理器、8 GB 内存.开发环境为Python3.8.

在对实验数据进行实验之前,为了保证一致性,本文对数据进行了归一化处理,即对所有数据进行以下操作:

其中,min是该时序数据中的最小值,max是该时序数据中的最大值.该操作将时序数据中所有的值都变换到了[0,1]内.

另外,本文共选取了4 种时间序列分段线性表示算法与本文算法做比较.以原始时间序列作为输入,新的时间序列作为输出.分别比较了通过各算法得到的新序列与原始时间序列之间的拟合误差.本文采用的拟合方式为线性插值法:在每个区间的两个端点间插入有限个点,依次连接相邻两个点得到区间的直线段,从而将区间连接起来得到一整条新序列.

4.3 实验结果及分析

如图5所示,是铣削过程中VB 切片磨损程度的原始时间序列.该数据集中有数据缺失的现象,因为缺失数据对序列没有直接影响,所以,实验过程中对缺失值进行了丢弃处理.图6是经过分段线性表示后的新序列.由图可知,新的序列减少了原始序列中的波动,很好地保留了其主要发展趋势.

图5 VB 磨损原始序列(分段表示前)

图6 VB 磨损PLR 序列(分段表示后)

以UCR 数据集中的ECG 信号数据为例,图7和图8分别是ECG 信号分段线性表示前的序列和ECG信号分段表示后的序列.对比两图可知,该线性分段方法在减少波动的情况下,很好地保留了原始时间序列的发展趋势.

图7 ECG 原始序列(分段表示前)

图8 ECG 的PLR 序列(分段表示后)

4.4 算法对比

拟合误差是评价时间序列分段线性表示算法的一项重要指标[16–19],其计算方式如式(2)所示.一般来说,拟合误差越小,得到的新序列对原始时间序列的拟合程度越高,算法的性能越好.表2展示了在压缩率为80%的情况下,各算法在实验数据上的拟合误差.

表2 80%压缩率下各算法拟合误差

表2中加粗的数据表示最小拟合误差.从表中可以看出,在6 条时间序列中,本文提出的GFKP 在其中4 条时间序列上拟合误差最小,在另外2 条时间序列上的拟合误差与最小拟合误差相差不大.因此,实验表明本算法具有良好的适应性.

压缩率是评价算法的另一项重要指标[20–24],其计算方式如式(3)所示.压缩率越高,对数据的压缩程度越高,得到的分段数目就越小.一般来说,同一个算法的压缩率越高,拟合误差也会随之增加.图9展示了4 种PLR 算法与本文算法对UWLA 序列在不同压缩率下的拟合误差对比.

图9 各算法在不同压缩率下的拟合误差

由图9可知,随着压缩率的增加,拟合误差逐渐增大,但是,GFKP 算法的拟合误差始终较低.因此,GFKP算法对原始序列的拟合度较好.

5 总结与展望

时间序列的线性分段表示方法的主要内容是提取时间序列中的关键点.通常认为关键点来自于极值点和拐点,因此大多数学者只关注于时间序列的局部特征,这不仅容易陷入局部最优的状态,还忽略了时间序列整体的发展趋势[25–28].针对这一问题,本文提出了基于时间序列波动性的分段线性表示方法.该算法首先提取出时间序列的波动点,保留时间序列的发展趋势.在此基础上,找到关键点.依次将找到的若干个关键点用线性插值的方法进行拟合,拟合的结果就是时间序列的GFKP 表示.GFKP 表示算法计算简单、容易实现、时间复杂度O(n).该算法不仅能够在工业时序数据上取得良好的分段效果,与其他分段线性表示算法相比,能够更好地体现出时间序列的发展趋势和全局特征,且有较小的拟合误差和较好的适应性.接下来将研究时间序列的特征转换.时间序列的重要特征信息主要存在于其关键点中.时间序列的特征转换是指在提取到关键点后,转化这些特征,使其可以结合主流的数据挖掘算法进行研究,这是一个有价值的研究方向.