基于分数微分的时间序列相似性度量及其应用.pdf

年月四川大学学报(自然科学版)J u l 第 卷第期J o u r n a l o fS i c h u a nU n i v e r s i t y(N a t u r a lS c i e n c eE d i t i o n)V o l N o 基于分数微分的时间序列相似性度量及其应用闫汶朋,汪志涛,袁晓(四川大学电子信息学院,成都 )摘要:时间序列的相似性度量是时间序列聚类、分类以及其他相关时间序列分析的基础传统基于距离的相似性度量方法,忽视了时间序列可能存在的时间上的联系,而将时间序列看作一系列孤立点的集合对于序列间可能存在的前后联系,基于分数阶微分的遗传特性和记忆特性,提出一种新的时间序列聚类的相似性度量根据时间序列的分数阶微分计算新序列间的点距离,将其作为聚类算法的输入对时间序列进行聚类仿真实验结果表明,与基于原始序列矢量距离的聚类结果相比,新的分数阶相似性度量方法表现更好关键词:时间序列;聚类;相似性度量;分数阶微分中图分类号:T P 文献标识码:AD O I:/j 收稿日期:作者简介:闫汶朋(),男,四川南江人,硕士研究生,主要研究领域为信号与信息处理、分数阶微积分理论与应用通讯作者:袁晓 E m a i l:y u a n x i a o s c u e d u c o mT i m e s e r i e s s i m i l a r i t ym e a s u r e m e n tb a s e do nf r a c t i o n a l d i f f e r e n t i a l a n d i t sa p p l i c a t i o nY AN W e n P e n g,WANGZ h i T a o,Y U AN X i a o(C o l l e g eo fE l e c t r o n i c sa n dI n f o r m a t i o nE n g i n e e r i n g,S i c h u a nU n i v e r s i t y,C h e n g d u ,C h i n a)A b s t r a c t:S i m i l a r i t ym e a s u r e so ft i m es e r i e sa r et h eb a s i sf o rt i m es e r i e sc l u s t e r i n g,c l a s s i f i c a t i o na n do t h e r r e l a t e dt i m es e r i e sa n a l y s i s T h e t r a d i t i o n a l d i s t a n c e b a s e ds i m i l a r i t ym e a s u r e i g n o r e s t h ep o s s i b l et e m p o r a l c o n n e c t i o n so f t i m e s e r i e s a n d t r e a t s t i m e s e r i e s a s a s e r i e so f i s o l a t e dp o i n t s e t s F o r t h ep o s s i b l eb a c k w a r da n df o r w a r dc o n n e c t i o n sb e t w e e ns e q u e n c e s,an e ws i m i l a r i t ym e a s u r e f o r t i m e s e r i e s c l u s t e r i n g i sp r o p o s e db a s e do nt h eg e n e t i ca n dm e m o r yp r o p e r t i e so ff r a c t i o n a lo r d e rd i f f e r e n t i a t i o n T h ep o i n td i s t a n c e sb e t w e e nt h en e ws e q u e n c e sa r ec a l c u l a t e db a s e do nt h e f r a c t i o n a l o r d e rd i f f e r e n t i a t i o no ft h e t i m e s e r i e s,a n d t h e na r eu s e da s t h e i n p u t o f t h e c l u s t e r i n ga l g o r i t h mt oc l u s t e r t h e t i m e s e r i e s T h es i m u l a t i o ne x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wf r a c t i o n a l o r d e rs i m i l a r i t ym e a s u r ep e r f o r m sb e t t e rc o m p a r e dw i t ht h ec l u s t e r i n gr e s u l t sb a s e do nt h eo r i g i n a l d i s t a n c e s K e y w o r d s:T i m es e r i e s;C l u s t e r;S i m i l a r i t ym e a s u r e;F r a c t i o n a l d i f f e r e n t i a l引言时间序列作为一种随时间顺序变化的数据序列,通常具有数据量大、维度高、无限递增、结构复杂等特点近年来,面对日益庞大的时间序列数据集,人工标记的成本日益增加,属于无监督、半监督学习的时间序列聚类引起了越来越多研究者的兴趣,并被广泛应用于金融学、医疗诊断,、工业生产控制和生物学等聚类通过将相似的数据放入相关或同质的组中,将具有最小相似性的对象放入其他组中,已成为一种有用的数据分析方法对于时间序列的相似性研究,很多采用了欧几里德距离或其演变,但基于矢量的欧式距离及其演 第 卷四川大学学报(自然科学版)第期变单纯的将时间序列看做孤立点的集合,忽视了时间序列可能存在的时间上的联系和关键点信息,对于序列在时间轴上的偏移也非常敏感,不具备形态识别能力针对这些问题,国内外学者们相继提出了众多的解决方法:广泛应用于语音识别领域的D TW距离,通过把两个时间序列进行延伸和缩短,找到距离最短的扭曲距离;隐马尔可夫模型,利用时间序列隐含的属性(马尔可夫性)提高聚类精度近年来,王瑞等根据分段序列的斜率变化,划分形态模式,把时间序列转换成字符串序列李海林等提出动态时间弯曲与符号距离结合的时间序列距离度量方法,反映了时间序列数值分布和形态特征 S o l e i m a n i等定义了两个相似性阈值并确定它 们的值,提出 了发展的最 长公共子 序列(D e v e l o p e d L o n g e s t C o mm o n S u b s e q u e n c e,D L C S S),解决了L C S S很难确定正确的相似度阈值,导致结果较差的问题甄远婷等 基于中心C o u p l e函数捕获时间序列的动态相依结构,采用C r a m e r v o nM i s e s统计量构造了一种新的相似性度量本文提出一种基于分数阶微分的时间序列相似性度量,利用分数阶微分的遗传效应和记忆特性,对原始时间序列数据进行分数阶微分计算,再根据传统的点与点距离公式计算得到相似度,最后将其作为聚类算法的输入完成时间序列的聚类分数阶微分理论基础分数阶微积分作为一个重要的数学分支,近年来,已不断在科学、工程等领域得到了广泛的应用,并被引入控制论、流体力学、信号处理及图像处理等领域 对于某些特定的应用,整数阶微分并不能进行很好的描述,需要借助分数阶微分以达到更精确的描述,如:流变本构方程、分数阶控制系统等相对于整数阶微分,分数阶微分可以提供比整数阶微分更丰富的信息 G L分数阶导数的定义分数阶微分有多种不同的定义形式,适合于数值计算 的G r n w a l d L e t n i k o v(G L)分数阶导数定义为G LaDtf(t)l i mA()f(t),ta,b()A()f(t)jg()jf(tj)()g,gjjgj,j,()式()和式()中,D为分数阶微分算子;(可取分数)为运算阶数;t表示时间序列当前时刻;是采样步长;g()j为二项式系数,可通过式()递推求出可以看出,在计算分数微分时,要用到时刻t之前所有的历史数据,被加项数目变得非常大对于时间序列,随着数据量的增大,考虑所有历史数据,分数阶微分的计算速度会随之受到影响,因此,在实际计算中,根据分数微分加权系数具有的较快衰减特性,使用短时记忆法则,只考虑时间序列当前时刻近来的过去,即在区间tL,t的行为G LaDtf(t)tLDtf(t),taL()式()中,L是记忆长度根据公式,具有下限a的分数导数可用具有移动下限tL的分数导数来逼近但是,这样的简化,在计算精度上会受到某些惩罚,对于atb,若存在函数f(t)M,则可利用式(),由短时记忆原理所引起的误差,建立估计()G LaDtf(t)tLDtf(t)M L(),aLtb()该不等式可以用来确定给定精度情况下的记忆长度L,有LM()()A()f(t)Jjg()jf tj()()式()中,JtJ()表示计算t时刻序列点分数阶导数使用的非局域记忆点数,使用短时记忆原理,不考虑全部历史数据G L定义适用于和的微分与积分,且当时,有Dif i()f i(),在时间序列处理中,可将初始时刻a看为 G L分数阶微分的数值计算式()也可写为:G LaDtf(t)A()f(t)o(),当选择的采样步长足够小时,式()中的求极限操作可以忽略,G L定义的分数阶导数便可以由G LaDtf(t)A()f(t)直接计算,再结合短时记忆原理,减少计算过程与传统的整数阶微分只使用当前和前几个有限步长内的函数值相比,分数阶微分具有遗传特性和记忆特性,涉及到t时刻序列点的前J个非局域记忆点序列值,可以捕捉时间序列的前后关系,与其他未将时间序列做相应计算,把各序列点看作孤立存在的方法相比,分数阶微分(如图)考虑了时间序列的时间顺序,使时间序列相似性的刻画具有 第期闫汶朋,等:基于分数微分的时间序列相似性度量及其应用第 卷非局域的记忆特性对于精度损失的问题,对比了通过分数导数逼近式()与运用短时记忆原理计算式()计算结果的区别(C B F训练集,设置为 ),如图所示可以看出,利用短时记忆原理,在不同记忆点数J的情况下,分数阶导数计算结果与逼近式计算结果接近完全重合,误差可忽略不计(a)原始时间序(b)不同阶次分数微分图原始时间序列及不同阶次分数阶微分F i g R a wt i m es e r i e sa n df r a c t i o n a l o r d e rd i f f e r e n t i a t i o no fd i f f e r e n to r d e r s图短时记忆与逼近式计算结果F i g S h o r t t e r m m e m o r ya n da p p r o x i m a t ec a l c u l a t i o nr e s u l t s基于分数阶微分的时间序列相似性度量给定两个长度为n的时间序列x、y,传统的欧式距离dE(x,y)ni(xiyi)()/是时间序列聚类中最常用的相似度量有研究表明,在时间序列分类精度上,欧式距离具有惊人的竞争力,在诸多算法中都有广泛的应用时间序列由于具有先后顺序,把时间序列各点看做孤立的存在并不合理,因此,需要考虑时间序列中可能存在的时间上的联系,以达到更好的聚类效果基于分数阶微分的时间序列相似度,对原始时间序列的每一点求其分数阶微分,可以看做计算一段序列的加权累计值由于分数阶微分计算结果中某些数值较大,对其进行标准化处理,通过将所有数据与数据最小值的绝对值相加来转换数据,使数据的最小值变为,其他所有数据变为正数,再使用Z S c o r e标准化处理数据DxiDxi()式(),xi表示时间序列的第i点数据;Dxi表示时间序列各时间点的阶分数微分;表示分数阶微分时间序列的均值;表示标准差;Dxi表示分数阶微分时间序列各点标准化后的值算法描述了具体过程输入为时间序列各个时刻的函数值构造的向量,第()行设定初始化步长,()()行递推计算二项式系数,()()根据相应的非局域记忆点数J计算给定时间序列的分数阶微分值,最后,标准化返回结果算法伪代码:分数阶微分输入:原始时间序列Tit,t,tn输出:标准化的分数微分时间序列()初始化()f o rj;jl e n(t);jd o()C a l c u l a t e W e i g h t s(,)e n d()f o ri;il e n(t);id o()i fiJt h e n()yC a l F r a D i f f(,f,h,)()e l s e()yC a l F r a D i f f(,f,h,)第 卷四川大学学报(自然科学版)第期e n d()r e t u r nS t a n d a r d i z a t i o n(y)再通过处理后的序列计算欧式距离得到相似度,定义如下dF(x,y)(ni(DaxiDayi)/(ni(AxiAyi)/()式(),Axi和Ayi为时间序列各时间点的阶分数微分计算表达式(式);Axi和Axi表示对其进行标准化;dF(x,y)为最终计算得到的相似度实验编译工具P y t h o n ,操作系统W i n d o w ,C P U/AMDR y z e n H w i t hR a d e o nG r a p h i c s,主频 GH z,内存 G B,固态硬盘容量 G 实验数据与实验方法本文实验中用到的时间序列数据集为U C R时间序列数据库 中收集的标准时间序列数据集,每个数据集包含一个训练集和一个测试集,具体信息如表表U C R标准时间序列数据集T a b U C Rs t a n d a r dt i m es e r i e sd a t a s e tD a t an a m eKLNMC o f f e C r i c k e t_X C B F E C G E C G F i v e D a y s S y m b o l s F a c e F o u r F I S H S c r e e n T y p e M e d i c a l I m a g e T r a c e _w o r d s S y n t h e t i c_c o n t r o l S w e d i s hL e a f MA L L A T A d i a c G u nP o i n t P l a n e W o r d sS y n o n y m s O S U L e a f D i a t o m 表中,K为聚类的数目;L为时间序列的长度;N为数据集的训练集数目;M为数据集的测试集数目对于分数微分计算后的序列,在训练集上比较计算序列间欧式距离与改进的D TW距离L B_K e o g h作为聚类输入的聚类准确度与时间消耗,如图所示(a)E D与L B_K e o g h距离聚类结果(b)E D与L B_K e o g h距离运行时间图E D与L B_K e o g h距离对比实验F i g E Da n dL B_K e o g hd i s t a n c ec o m p a r i s o ne x p e r i m e n t可以看出,计算两个序列间的欧式距离作为K M e a n s聚类的输入到完成聚类过程所需的时间远远小于L B_K e o g h距离作为聚类输入所需的时间,且随着时间序列数据量的增大,时间差异更加明显在聚类准确度方面,两种距离互有优劣,因此,综合考量时间与准确度因素,选择欧氏距离作为计算处理后序列间相似度的距离公式实验总体采用不同的距离度量,并通过K M e a n s聚类算法实现对时间序列的聚类,同时也采用了层次聚类与基于u s h a p e l e t s的时间序列聚类算法 进行相关实验,最后对所得结果进行对比分析分数微分欧式(F r a c t i o n a lD i f f e r e n t i a t i o n 第期闫汶朋,等:基于分数微分的时间序列相似性度量及其应用第 卷E u c l i d e a n,F D E)距离首先对数据集中的时间序列进行阶分数微分运算,将其标准化后,再根据运算后序列的欧式距离计算得到两个时间序列的相似度,以此作为聚类算法的输入完成聚类,并使用R(R a n dI n d e x)评价聚类质量Radabcd()式()中,a为在实际类别中为同一类且在聚类结果中也为同一类的数据点对数;d为在实际类别中不为同一类且在聚类结果中也不属于同一类的数据点对数;b为在实际类别中为同一类但在聚类结果中不属于同一类的数据点对数;c为在实际类别中不为同一类但在聚类结果中属于同一类的数据点对数计算相似度时,记忆点数J和阶数的不同将会影响距离度量,并最终影响聚类质量图给出了单独的不同J、分别对于聚类质量评价的影响通过将式()计算得到的距离作为聚类算法 的输入,获得了两个变量J、对聚类质量的影响(如图)(a)不同J对于R的影响(b)不同对R的影响图不同的J或对R的影响F i g E f f e c t so fd i f f e r e n tJo ro nR为了确定最佳J、值,本文通过在训练集中,观察不同J和对于聚类质量评价R的影响,再在测试集中,利用训练集得到的最佳J、进行多次实验取均值得到最终结果图不同J、对于R的影响F i g E f f e c t so fd i f f e r e n tJa n do nR 实验结果分析 准确度对比对基于L B_K e o g h距离、欧式距离、余弦距离、P e a r s o n相关系数的K均值聚类、层次聚类、基于u s h a p e l e t s的时间序列聚类结果比较如表所示,其中,J、分别为获得的最佳记忆点数与分数阶导数的阶数,W i n一行标明了采用种不同的距离度量和聚类算法在 个数据集上取得最佳效果的数量从表可知,在 个时间序列数据集中,本文提出的F D E距离分别在 个数据集、个数据集、个数据集、个数据集上优于基于余弦距离、L B_K e o g h距离、欧氏距离、P e a r s o n相关系数的K M e a n s聚类,在 个数据集上优于层次聚类的结果,个数据集上优于基于u s h a p e l e t s的时间序列聚类实验表明,虽然在不同的数据集上,基于各种距离的K M e a n s聚类、层次聚类和基于u s h a p e l e t s的时间序列聚类算法都能或多或少取得最佳的聚类效果,但是本文所提出的方法整体效果最佳 运行时间对比欧式距离、D TW距离是常用的基于距离来衡量相似性的指标 F D E在欧氏距离的基础上,增加了分数微分的计算过程,对比F D E与此两种距离作为K M e a n s聚类算法的输入,并比较了层次聚类与基于u s h a p e l e t s的时间序列聚类算法在 个时间序列数据集上完成聚类操作所需的时间结果如表所示,可以看出,F D E在运行时间上逊于基于欧几里得距离的K m e a n s聚类与层次聚类,大幅优于基于L B_K e o g h距离的k m e a n s聚类和基于u s h a p e l e t s的时间序列聚类,具有更高的时间效率 第 卷四川大学学报(自然科学版)第期表聚类实验准确度对比T a b C o m p a r i s o no f t h ea c c u r a c yo f c l u s t e r i n ge x p e r i m e n t s数据集JK M e a n s算法聚类结果评价指标RR指标F D E余弦距离L B_K e o g h欧式距离P e a r s o n层次聚类u s h a p e l e t sC o f f e C r i c k e t_X C B F E C G E C G F i v e D a y s S y m b o l s F a c e F o u r F I S H S c r e e n T y p e M e d i c a l I m a g e T r a c e _w o r d s S y n t h e t i c_c o n t r o l S w e d i s hL e a f MA L L A T A d i a c G u nP o i n t P l a n e W o r d sS y n o n y m s O S U L e a f D i a t o m W i n表聚类实验运行时间对比T a b C o m p a r i s o no f r u n n i n gt i m e s f o rc l u s t e r i n ge x p e r i m e n t s数据集运行时间/sF D E欧式距离L B_K e o g h层次聚类u s h a p e l e t sC o f f e C r i c k e t_X C B F E C G E C G F i v e D a y s S y m b o l s F a c e F o u r F I S H S c r e e n T y p e M e d i c a l I m a g e T r a c e _w o r d s S y n t h e t i c_c o n t r o l S w e d i s hL e a f MA L L A T A d i a c G u nP o i n t P l a n e W o r d sS y n o n y m s O S U L e a f D i a t o m 第期闫汶朋,等:基于分数微分的时间序列相似性度量及其应用第 卷结论为了解决传统的基于距离的相似性度量方法将时间序列矢量看作孤立点存在的问题,本文提出利用时间序列的分数阶微分构造新的时间序列,用构造的新序列间的欧式距离计算相似度作为K M e a n s聚类算法的输入完成聚类过程通过与基于传统距离度量的K M e a n s聚类、层次聚类以及基于u s h a p e l e t s的聚类结果进行比较,可以得出,本文方法相对于欧式距离简单快速的实现方式,牺牲了一些计算速度,在一定程度上提高了聚类准确度后续研究中,我们可考虑以下两个方面:()对于时间序列先计算分数阶微分,再计算点距离计算时间较长的问题,可考虑第二次计算过程使用符号聚合近似、主成分分析等数据降维和特征表示方式来计算相似度,减少计算过程,以加快计算速度;()利用深度学习,对获得的新序列进行特征提取、距离矩阵计算的自适应权重等方式,以得到的更好的聚类结果参考文献:R u i zEJ,H r i s t i d i sV,C a s t i l l oC,e t a l C o r r e l a t i n gf i n a n c i a lt i m es e r i e s w i t h m i c r o b l o g g i n g a c t i v i t yCP r o c e e d i n g o ft h ef i f t h A CM I n t e r n a t i o n a lC o n f e r e n c eo n W e bS e a r c ha n dD a t a M i n i n g N e wY o r k:A CM,:L iG,B r a e y s yO,J i a n gL,e t a l F i n d i n gt i m es e r i e sd i s c o r db a s e do nb i tr e p r e s e n t a t i o nc l u s t e r i n gJK n o w l B a s e dS y s t,:T a v e n a r dR,M a l i n o w s k i S C o s t a w a r e e a r l yc l a s s i f i c a t i o no f t i m es e r i e sC/J o i n tE u r o p e a nC o n f e r e n c eo nM a c h i n eL e a r n i n ga n dK n o w l e d g eD i s c o v e r yi nD a t a b a s e s C h a m:S p r i n g e r,Z a l e w s k iW,S i l v aF,M a l e t z k eA G,e t a l E x p l o r i n gs h a p e l e t t r a n s f o r m a t i o nf o r t i m es e r i e sc l a s s i f i c a t i o ni nd e c i s i o nt r e e sJK n o w l B a s e d S y s t,:J i a n gD,P e i J,R a m a n a t h a nM,e t a lM i n i n gg e n e s a m p l e t i m em i c r o a r r a yd a t a:ac o h e r e n tg e n ec l u s t e rd i s c o v e r ya p p r o a c hJK n o w l I n fS y s t,:S a l v a d o rS,C h a nP T o w a r da c c u r a t ed y n a m i c t i m ew a r p i n g i n l i n e a r t i m ea n ds p a c eJ I n t e l lD a t aA n a l,:王瑞,贾瑞玉基于形态模式的时间序列相似性度量算法J计算机应用与软件,:李海林,梁叶基于数值符号和形态特征的时间序列相 似 性 度 量 方 法 J控 制 与 决 策,:S o l e i m a n iG,A b e s s iMD L C S S:an e ws i m i l a r i t ym e a s u r ef o rt i m es e r i e sd a t am i n i n gJ E n gA p p lA r t i f I n t e l,:甄远婷,冶继民,李国荣基于中心C o p u l a函数相似性度量的时间序列聚类方法J陕西师范大学学报:自然科学版,:袁晓分数微积分理论基础与应用导论M北京:电子工业出版社,H u a n gJ,L iH,C h e nY Q,e t a lR o b u s tp o s i t i o nc o n t r o l o fPM S Mu s i n g f r a c t i o n a l o r d e r s l i d i n gm o d ec o n t r o l l e rC/A b s t r a c ta n d A p p l i e d A n a l y s i s H i n d a w i:s n ,伍小二一类无界变差函数的分数阶微积分及其分形维数D南京:南京理工大学,徐明瑜,谭文长中间过程、临界现象分数阶算子理论、方法、进展及其在现代力学中的应用J中国科学G辑:物理学 力学 天文学,:蒲亦非,袁晓,廖科,等现代信号分析与处理中分数阶微积分的五种数值实现算法J四川大学学报:工程科学版,:杨柱中,周激流,晏祥玉,等基于分数阶微分的图像增强J计算机辅助设计与图形学学报,:陈卫卫,王卫星,闫迪基于分数阶微分F r a n g i的夜间车道线检测J四川大学学报:自然科学版,:彭朝霞,蒲亦非基于分数阶微分的卷积神经网络的人脸识别J四川大学学报:自然科学版,:薛定宇分数阶微积分学与分数阶控制M北京:科学出版社,周宇,袁晓,张月荣基于I F F T的L u b i c h数字分数微分器系数的快速算法J太赫兹科学与电子信息学报,:L k h a g v aB,Y uS,K a w a g o eK N e wt i m e s e r i e sd a t ar e p r e s e n t a t i o n E S A X f o rf i n a n c i a la p p l i c a t i o n sC/I n t e r n a t i o n a lC o n f e r e n c eo nD a t aE n g i n e e r i n gW o r k s h o p s A t l a n t a:I E E E C o m p u t e r S o c i e t y,D a u H A,K e o g hE,K a m g a rK,e ta lT h eu c rt i m es e r i e sc l a s s i f i c a t i o na r c h i v eE B/O L h t t p s:/w ww c s u c r e d u/e a m o n n/t i m e s e r i e sd a t a 余思琴,闫秋艳,闫欣鸣基于最佳u s h a p e l e t s的 第 卷四川大学学报(自然科学版)第期时 间 序 列 聚 类 算 法 J计 算 机 应 用,:李海林,张丽萍时间序列数据挖掘中的聚类研究综述J电子科技大学学报,:陈美云时间序列聚类分析中几种算法的研究及应用D徐州:中国矿业大学,引用本文格式:中文:闫汶朋,汪志涛,袁晓基于分数微分的时间序列相似性度量及其应用J四川大学学报:自然科学版,:英文:Y a nWP,W a n gZT,Y u a nX T i m e s e r i e s s i m i l a r i t ym e a s u r e m e n t b a s e do n f r a c t i o n a l d i f f e r e n t i a l a n d i t s a p p l i c a t i o nJ JS i c h u a nU n i v:N a tS c iE d,: