基于趋势的时间序列相似性度量方法

基于趋势的时间序列相似性度量方法

0基于时间序列趋势的相似性度量时间序列是时间序列之后的几名实物的序列，反映了时间序列中实体属性的函数。时间序列匹配在位置定位(locationbasedservice,LBS)系统、环境监测、物联网等领域中有广泛的应用。由于时间序列(确定时间序列和不确定时间序列)的长度很大,并且不确定时间序列在每个观察点的观察值具有不确定性,导致了维度灾难和庞大的可能世界,使得时间序列相似性度量和聚类挖掘的时间代价过高。本文提出了基于时间序列变化趋势的相似性度量方法和聚类方法,其中基于趋势的相似性度量方法首先对时间序列进行区间划分和区间内的趋势判断,生成短的趋势符号序列,然后计算各趋势符号的一阶连接性指数,最后通过计算两序列中各趋势符号一阶连接性指数的塔尼莫特系数完成相似性度量。基于趋势的聚类方法通过定义趋势高度,迭代判断趋势符号序列的趋势变化,并构建趋势树完成聚类。1相关工作1.1基于时间序列聚类分析的精度改进时间序列相似性问题最早是由Agrawal等人提出的,将该问题定义为:在大规模的时间序列数据库里,通过一定的相似性匹配方式,查询出和已知序列相匹配的时间序列集合,相似是基于距离函数来衡量的。Agrawal率先使用等长时间序列的欧氏距离度量时间序列间的相似度,欧氏(Euclid)距离是最基本的,而明考夫斯基(Mikowski)距离则是对欧氏距离的推广。Berndt等人在文献中引入了在语音识别中被广泛使用的DTW(dynamictimewarping)距离作为时间序列的相似性度量距离。文献[3,4]阐述了这种基于非线性规整技术的算法可以获得很高的识别和匹配精度,尤其对时间序列在时间轴上的形状扭曲有非常优秀的辨识能力。但是DTW的计算复杂度较高,并且DTW不满足距离的三角不等式。Keogh在文献中分析了DTW距离的特性,针对时间序列索引和查询提出了基于时间序列边界的DLB_Keogh距离。这是目前最好的时间序列度量距离,但是DLB_Keogh距离不是一种对称的时间序列距离度量,所以并不适合直接应用于时间序列的聚类。编辑距离(editdistance)是计算两字符串符号序列距离的一种度量,它的定义是将一字符串转换为另一字符串所需的最小编辑(插入、删除、改变)步数。该方法充分利用了字符串匹配等成熟计算方法,但是需要将时间序列转换成相应的字符串,精度不高。文献[6,7]使用了ARMA模型表示时间序列数据,并通过定义基于两个模型的距离公式进行相似性度量。Wang等人将HMM模型应用到时间序列数据聚类研究中,并在公共数据集上进行了测试,获得了良好的效果。其他相似性度量方式,如Swale模型、SpADe距离等在时间序列相似性度量领域也得到了广泛的应用。1.2时间序列差异度公式MacQue在1967年提出的K-means算法,是一种被广泛应用于科学研究和工业应用中的经典聚类算法。K-means算法的核心思想是把一个数据对象划分为k个聚类,使每个聚类中的数据点到该聚类中心的平方和最小。Huang等人在文献[11,12]中为克服K-means算法仅适合于数值属性数据聚类的局限性,提出了一种适合于分类属性数据聚类的K-modes算法,并证明了经过有限次迭代,K-modes算法收敛于局部最小值。文献为了刻画时间序列趋势的内在规律特征,在K-means算法的基础上提出了基于划分的K_SC算法,并给出了新的时间序列差异度公式,保证任意两个时间序列的相似性只与它们的趋势走向有关,而与它们的峰值数值以及在何时达到峰值无关。时间序列聚类是一种完全根据数据自身所提供的信息进行分类的一种方法,根据相似性度量方式不同,时间序列的聚类主要分为基于距离的时间序列聚类、基于特征的时间序列聚类和基于模型的时间序列聚类三种。1990年,Kosmelj等人提出了relocation聚类算法,该算法采用欧氏距离进行距离度量,可以对多变量等长时序数据进行聚类分析。Golay等人将模糊C-均值方法应用到磁共振数据(单变量等长数据)中,对人脑行为进行分析,采用欧氏距离作为距离度量方法。文献对模糊C-均值聚类方法进行了改进,该方法使用STS距离度量,被应用于DNA序列检测。Fu等人在文献中沿时间轴使用一个连续的滑动窗口,通过自组织映射方法提取序列中关键的时间点。最终,用多个关键点来代替整个时间序列,使用改进的SOM聚类算法进行聚类。Owsley等人提出了序列集群细化算法(SCRA),通过模式匹配发现大批量数据信号的代表性数据,最终形成一个高分辨率的有代表性的部分数据集合。文献通过寻找时间序列的关键点,利用改进的FCM算法完成时间序列的动态聚类。2各时间序列的描述确定时间序列表示为每个时间点上有一个确定采样值的有序序列;不确定时间序列的不确定性表示为每个时间点的样本观测值的集合,每一个时间点的取值用一个随机变量来表示,不确定时间序列是具有时间特性的随机变量的有序序列。定义1时间序列。长度为n的时间序列由一条包含n个元素的序列组成,时间序列记为TS={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}。其中,ti代表第i个时间点,每条元组中的属性用变量Xt和Pt表示,Xt代表第t时刻观察值的集合,记为Xt={xt,1,xt,2,…,xt,s};Pt代表第t时刻观察值取值概率的集合,记为Pt={pt,1,pt,2,…,pt,s},s为集合Xt的基数即样本观察值的个数。当s=1时,TS表示确定时间序列,且Pt={1.0}。确定时间序列数据集如表1所示。当s≠1时,TS表示不确定时间序列。不确定时间序列的数据集如表2所示。3基于序列趋势的相似性测量3.1tdd结果与区间趋势定义2序列区间。给定长度为n的时间序列T和分割的区间长度L(L≥3),将时间序列T分割为k=n/L个等长且连续的区间,称为k个序列区间,分别记为i1,i2,…,ik。如果n≠k×L,则舍弃k×L+1到n的序列部分。区间ij(1≤j≤k)的区间范围为[(j-1)×L,j×L],区间ij(1≤j≤k)的下边界记为low(ij),上边界记为high(ij),则L=high(ij)-low(ij),并且对于区间ij(1≤j<k),high(ij)=low(ij+1)。定义3区间趋势。给定长度为n的时间序列T和分割后的k个序列区间i1,i2,…,ik,时间序列在区间ij(1≤j≤k)内的变化趋势为区间趋势,记为tdj,tdj∈{tdup,tddw,tdst,tdpk,tdth}。其中:tdup为时间序列在分割区间内呈现上升趋势;tddw为时间序列在分割区间内呈现下降趋势;tdst为时间序列在分割区间内呈现平缓趋势;tdpk为时间序列在分割区间内取得峰值;tdth为时间序列在分割区间内取得谷值。五种区间趋势tdup,tddw,tdst,tdpk,tdth如表3所示,并且区间趋势与趋势符号一一对应,与此对应的趋势符号为tsup,tsdw,tsst,tspk,tsth。对长度为n的时间序列T进行序列区间分割和各区间趋势判断,具体步骤如下:a)计算序列T的期望序列Texp。如果T为确定时间序列,则Texp=T;如果T为不确定时间序列,则Texp={(t1,X1P1),(t2,X2P2),…,(tn,XnPn)},其中XiPi=xi,1×pi,1+xi,2×pi,2+…+xi,s×pi,s(1≤i≤n)。b)根据分割的区间长度L,将期望序列Texp分割为k个序列区间,分别记为i1,i2,…,ik。记录Texp在区间ij(1≤j≤k)内的区间开始点、区间中间点和区间结束点的取值V1、V2、V3,以及在该区间内的最大取值Vmax和最小取值Vmin。根据表4(α为趋势系数)所示的判断条件判断区间ij内的时间序列趋势,即序列区间ij的区间趋势。定义4趋势符号序列。给定长度为n的时间序列T,在分割为k个序列区间并判断每个序列区间内的区间趋势后,每个序列区间与一个区间趋势对应,同样每个序列区间与一个趋势符号对应,将趋势符号从左向右依次连接后形成的序列称为时间序列T的趋势符号序列,记为SL(T)={(i1,ts1),(i2,ts2),…,(ik,tsk)},其中tsj∈{tsup,tsdw,tsst,tspk,tsth}(1≤j≤k)。3.2时间序列的相似度通过引入在化学分子结构研究和基因序列相似性研究中普遍使用的一阶连接性指数,以及塔尼莫特系数完成时间序列的相似性度量。定义5趋势位置信息。给定长度为k的趋势符号序列SL(T),比较趋势符号ts(ts∈{tsup,tsdw,tsst,tspk,tsth})和SL(T)中的每一个趋势符号tsj(1≤j≤k且tsj∈{tsup,tsdw,tsst,tspk,tsth}),如果ts=tsj,则ts在位置j的信息为j/k;通过遍历SL(T)得到趋势符号ts在SL(T)的全部信息,并将其按照从左向右的顺序组织为序列,称该序列为ts在T中的趋势位置信息,记为LT(ts)=(LT,1(ts),LT,2(ts),…,LT,l(ts))。其中l是在SL(T)中满足ts=tsj的tsj个数。给定趋势符号ts在趋势符号序列SL(T)中的趋势位置信息LT(ts),则ts在T中的一阶连接性指数为IdT(ts)=(LT,1(ts)×LT,2(ts))-0.5+(LT,2(ts)×LT,3(ts))-0.5+…+(LT,l-1(ts)×LT,l(ts))-0.5,其中ts∈{tsup,tsdw,tsst,tspk,tsth}。例1给定SL(T1)={(i1,tspk),(i2,tsst),(i3,tsup),(i4,tsdw),(i5,tsh),(i6,tsst),(i7,tsup),(i8,tsdw),(i9,tsh),(i10,tspk),(i11,tsst),(i12,tsup),(i13,tsdw),(i14,tsth),(i15,tsst)}。tsdw在T1中的趋势位置信息LT1(tsdw)=(4/15,8/15,13/15),tsdw在时间序列T1中的一阶连接性指数IdT1(tsdw)=(4/15×8/15)-0.5+(8/15×13/15)-0.5=4.12。时间序列T1中五种趋势符号的一阶连接性指数对应为IdT1(tsup),IdT1(tsdw),IdT1(tsst),IdT1(tspk),IdT1(tsth);时间序列T2中五种趋势符号的一阶连接性指数对应为IdT2(tsup),IdT2(tsdw),IdT2(tsst),IdT2(tspk),IdT2(tsth),则时间序列T1和T2的相似度通过塔尼莫特系数ST1,T2(ST1,T2∈[0,1])来衡量。如果ST1,T2>ε,则时间序列T1和T2相似,否则两序列不相似。其中ε为相似性阈值,ST1,T2如式(1)所示。3.3基于趋势的时间复杂度分析基于趋势的时间序列相似性匹配算法输入:时间序列Q,时间序列集合D={T1,T2,…,Tm},其中m是序列集合的尺寸,Ti={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}(1≤i≤m);序列区间分割子程序Div_Sl;区间趋势判断和趋势符号序列生成子程序Td_Sl;趋势位置信息及一阶连接性指数计算子程序CN_ID;塔尼莫特系数计算子程序CA_MT;相似性阈值ε。输出:匹配的时间序列集合S。基于趋势的时间序列相似性匹配算法的时间复杂度分析如下(首先讨论不确定时间序列的情况):a)步骤1的时间复杂度为O(1)。b)步骤2~4计算时间序列Q中五种趋势符号的一阶连接性指数。首先步骤2计算Q的期望序列,该步骤需要遍历时间序列的每个观察值,该步骤的时间复杂度为O(ns),s为时间序列观察点的观察值个数;然后步骤3对期望序列进行序列区间划分和区间趋势判断,并生成趋势符号序列,该步骤需要遍历期望序列的每个观察点,该步骤的时间复杂度为O(n);步骤4计算趋势符号序列中五种趋势符号的一阶连接性指数,该步骤的时间复杂度为O(5k),其中k为趋势符号序列的长度。由于k<n,步骤2~4的时间复杂度为O(ns)。c)同理,步骤6~8的时间复杂度为O(ns)。d)步骤9计算两时间序列五种趋势符号的塔尼莫特系数,该步骤的时间复杂度为O(1);步骤5~11需要遍历数据库中的m条时间序列,并进行相似性度量,则步骤5~11的时间复杂度为O(mns)。综上所述,对不确定时间序列进行基于趋势的相似性匹配,时间复杂度为O(mns);同理可得对确定时间序列进行基于趋势的相似性度量,时间复杂度为O(mn)。4基于序列趋势的集群4.1生成趋势符号序列定义6趋势高度。给定趋势符号ts(ts∈{tsup,tsdw,tsst,tspk,tsth}),ts对应唯一的数值,称ts对应的唯一数值为趋势高度,记为th。ts与th(th∈[0,1])的对应关系记为(ts,th),则五种趋势符号和其趋势高度的对应关系表示为{(tsup,0.25),(tsdw,0.75),(tsst,0.5),(tspk,0),(tsth,1.0)},该对应关系保证趋势类型越相近,趋势之间趋势高度差越小。根据定义6,每个趋势符号与唯一的数值对应,则趋势符号序列SL1(T)可转换为每个时间点有一个确定观察值的时间序列,记为TL1(T),其中SL1(T)=SL(T)。将TL1(T)中每三个观察点划分为一个区间,并根据观察值进行趋势判断,生成新的趋势符号序列SL2(T)。对SL1(T)进行i次上述过程的迭代处理后,生成的趋势符号序列记为SLi+1(T),其中i≤log3k,并且SLi+1(T)对应的确定时间序列记为TLi+1(T),进行m=log3k次迭代后,生成的趋势符号序列SLm+1(T)=ts,其中ts∈{tsup,tsdw,tsst,tspk,tsth}。由TLi(T)(1≤i≤m)确定SLi+1(T)的步骤如下:a)SLi+1(T)的第j(1≤j≤k/3i)个趋势符号由TLi(T)中的观察点3j-2到观察点3j的观察值确定,三个观察值分别记为th1,th2,th3。b)根据表5所示的判定条件判定SLi+1(T)的第j个趋势符号。定义7趋势树。给定趋势符号序列SL(T),如果满足以下条件则根据SL(T)构建的树为趋势树tree(T),其中SL(T)长度为k,tree(T)的高度为h,k=3h-1。a)tree(T)的第1层的k个叶子节点对应SL(T)的k个趋势符号。b)tree(T)的第i(1<i<h)层的中间节点对应SLi(T)(SLi(T)的长度为k/3i-1)中的k/3i-1个趋势符号。c)tree(T)的第h层只有一个节点,即根节点,并且根节点为趋势符号ts=SLh(T)。例2设SL(T2)={(i1,tspk),(i2,tsst),(i3,tsup),(i4,tsdw),(i5,tsth),(i6,tsst),(i7,tsup),(i8,tsdw),(i9,tsth),(i10,tspk),(i11,tsst),(i12,tsup),(i13,tsdw),(i14,tsth),(i15,tsst),(i16,tsup),(i17,tsdw),(i18,tsth),(i19,tsst),(i20,tspk),(i21,tsdw),(i22,tsup),(i23,tsst),(i24,tsth),(i25,tsst),(i26,tsdw),(i27,tspk)},构建趋势树如图1所示,其中k=27,h=4,根节点为tsup。定义8聚类类别。给定tree(T),根据tree(T)根节点表示的不同趋势类型,共五种聚类类别,分别记为Cup,Cdw,Cst,Cpk,Cth。聚类类别Ci∈{Cup,Cdw,Cst,Cpk,Cth}与SLh(T)表示的趋势类型对应,即Cup,Cdw,Cst,Cpk,Cth分别对应tsup,tsdw,tsst,tspk,tsth。Ci为聚集到该类的时间序列集合,该集合内的时间序列趋势树根节点表示的趋势类型相同,不同聚类类别内的时间序列其趋势树根节点表示的趋势类型不同,其中Ci∈{Cup,Cdw,Cst,Cpk,Cth}(1≤i≤5)。4.2基于趋势的时间序列聚类算法基于趋势的时间序列聚类算法输入:时间序列集合D={T1,T2,…,Tm},其中m是序列集合的尺寸,Ti={(t1,X1,P1),(t2,X2,P2),…,(tn,Xn,Pn)}(1≤i≤m);序列区间分割子程序Div_Sl;区间趋势判断和趋势符号序列生成子程序Td_Sl;趋势树生成子程序tree_Td。输出:聚类类别集合{Cup,Cdw,Cst,Cpk,Cth}。基于趋势的时间序列聚类算法的时间复杂度分析如下(首先讨论不确定时间序列的情况):a)步骤2计算时间序列的期望序列,需要遍历时间序列的所有观察值,步骤2的时间复杂度为O(ns),s为时间序列观察点的观察值个数。b)步骤3对期望序列进行序列区间划分和区间趋势判断,并生成趋势符号序列,该步骤需要遍历期望序列的每个观察点,步骤3的时间复杂度为O(n)。c)步骤4对趋势符号序列进行迭代趋势判断,并生成趋势树,步骤4的时间复杂度为O(3+32+…+3h-1)=O(0.5×3h),其中h为趋势树的高度。d)步骤5~8根据趋势树根节点表示的趋势类型进行聚类。该步骤的时间复杂度为O(1)。e)步骤1需要遍历数据库中的m条时间序列并进行步骤2~8的计算。由于k<0.5×3h<n,其中k为趋势符号序列SL(T)的长度,n为时间序列T的长度,则步骤2~8的时间复杂度为O(ns),该算法的时间复杂度为O(nms);同理对确定的时间序列集合D={T1,T2,…,Tm}进行基于趋势聚类的时间复杂度为O(nm),其中m为D的尺寸。5实验5.1实验环境本次实验的环境为:Windows732位操作系统;英特尔酷睿i3-370处理器;NVIDIAGeforceGT330M显卡。5.2不确定时间序列1)不确定时间序列数据实验数据是来自钢厂轧钢过程中一卷钢板的凸度值变化情况。在实际钢厂轧钢过程中,将每一卷钢板作为一个周期,每一卷的检测数据是按时间顺序变化的,每一时隙的变化是不确定的,形成一个不确定的时间序列。假定检测过来的原始数据与数据库中时间范围是相同周期的,每一卷检测值是一个时间序列,每一条元组都是一个2-tuple〈ti,vi〉,循环读取这组检测数据中的每一个二元组,与数据库中对应时刻的值进行比较,更新数据库中的值,统计出每一时刻所出现的观察值的频率。本文主要通过统计每一组值来找到这样的经验值。具体做法是:将原始检测数据通过统计计算,得到每个时刻的样本可能出现值和可能值的概率,实际每个周期大概是150个时间点,这样形成了一条不确定的时间序列数据。最后得到1000条不确定时间序列,每条时间序列的时间点都是150。2)确定时间序列数据通过统计钢板凹凸值变化得到不确定时间序列后,将该序列的期望序列作为实验中的确定时间序列数据,则最后得到1000条确定时间序列,每条时间序列的时间点都是150。5.3测定一阶连接性指数法对2000条时间序列(1000条确定时间序列和1000条不确定时间序列)分别计算五种趋势符号的一阶连接性指数,然后对每一条时间序列分别计算与其余序列趋势符号的塔尼莫特系数。实验结果表明在2000条时间序列集合中,没有两序列的塔尼莫特系数等于1,即2000条时间序列中,没有两条时间序列的趋势符号的一阶连接性指数完全相等,所以可以使用五种趋势符号的一阶连接性指数唯一地表示一条时间序列。5.4查询结果的相关性分析本文通过查全率和查准率两种参数来进行相似性度量的结果分析。查全率(召回率)是衡量从不确定性时间序列数据库中查询出与给定的查询序列相似成功度的一项指标,即查询出的相关序列与数据库中全部不确定时间序列的百分比。查准率(精度)是衡量查询出的相似性序列的准确度的一项指标,即查询出的相关序列中真正满足相似的序列与全部查询出的相关序列的百分比。5.4.1对于相似性匹配结果任意给定一个查询序列Q,对1000条确定的期望时间序列分别基于欧氏距离(ED)、DTW、序列趋势(TD)三种度量方式进行相似性匹配。相似性匹配结果如表6所示。使用基于序列趋势的度量方式,查全率最高,但是查准率与基于欧氏距离的相似性度量方式接近,并低于基于DTW的相似性度量方式。三种度量方式的匹配效率如图2所示,基于序列趋势的度量方式匹配效率介于其余两者之间,并且基于DTW的度量方式匹配效率最低。以上数据表明,对于确定时间序列,基于趋势的相似性度量方式是有效的。5.4.