基于快速傅立叶变换的动态时间序列在线查询算法

基于快速傅立叶变换的动态时间序列在线查询算法摘要：针对时间序列实时分析的需要，给出了一种动态序列的在线相似性查询算法。该算法利用改进的欧氏距离作为模式的相似度量方式，然后利用快速傅立叶变换，实现动态序列与各指定模式的批处理相似性计算。为了缩短在批处理的等待时间，再利用预测模型对未来的值进行预测，通过比较预测序列与特定模式之间的相似性，来实现在线查询的快速响应。模拟实验结果显示，该算法在一定程度上解决了在线查询的准确性与时效性。关键词：动态时间序列数据挖掘快速傅里叶变换相似性查询SimilarSearchAlgorithmofOnlineStreamingTimeSeriesBasedonFastFourierTransformAbstract:Analgorithmononlinesimilarsearchinastreamingtimeseriesisproposed.ThisalgorithmusesimprovedEuclideanDistanceassimilarmeasurement,andthenevaluatesthesimilardistancebetweensteamtimeseriesandfeaturetimeseriesinabatchmodeusingFastFourierTransform.Inordertoshortenwaittime,predictionmodelsareusedtopredictfeaturevalue,andaccomplishfastresponsebycomparisonthesimilaritybetweenpredictionseriesandfeatureseries.Simulationresultsshowthattheproposedalgorithmcanefficientlysolvetheonlinesimilarsearch.Keywords:streamingtimeseries,datamining,fastfouriertransform,searchbasedsimilarity

1引言时间序列相似性查询是时间序列的一个重要分析方法，目的在于从时间序列库中找出与给定查询序列最接近的数据序列[[]ChotiratAnnRatanamahatana,JessicaLin,DimitriosGunopulosetc.,MiningTimeSeriesData,DataMiningandKnowledgeDiscoveryHandbook[]ChotiratAnnRatanamahatana,JessicaLin,DimitriosGunopulosetc.,MiningTimeSeriesData,DataMiningandKnowledgeDiscoveryHandbook2010,Part6,1049-1077图1动态时间序列在线相似性查询对于动态序列的相似性在线查询而言，查询效率是在线查询优先要解决的问题。注意到由于动态序列的长度是不断地增加，因此其不能像静态序列那样可以构造固定的索引结构来提高查询的效率。动态在线查询的工作最早见于Terry和Goldberg等人在1992年对数据库的查询[[]D.Terry.D.Goldberg,D.NicholsandB.Oki.Continuousqueriesoverappend-onlydatabases.InProc.oftheACMSIGMODConf.OnManagementofData,pages321-330,1992.]，这种在线查询模式一旦提交，就会在整个数据库中不断地执行下去。Chen等人把动态在线查询技术运用到项目NiagraCQ中[[]J.Chen,D.J.Dewitt,F.TianandY.Wang.NiagaraCQ:ascalablecontinuousquerysystemforInternetdatabases.InProc.oftheACM.SIGMODConference,pages379-390,2000.]，这种在线查询不在仅限于增量式的数据源。Wang和Gao则把相似性查询运用到流式序列上来，提出了一种带预测值的在线查询算法[[[]D.Terry.D.Goldberg,D.NicholsandB.Oki.Continuousqueriesoverappend-onlydatabases.InProc.oftheACMSIGMODConf.OnManagementofData,pages321-330,1992.[]J.Chen,D.J.Dewitt,F.TianandY.Wang.NiagaraCQ:ascalablecontinuousquerysystemforInternetdatabases.InProc.oftheACM.SIGMODConference,pages379-390,2000.[]LikeGao,X.SeanWangContinuallyEvaluatingSimilarityBasedPatternQueriesonaStreamingTimeSeriesInSIGMODConference,2002.为此，本文提出一种基于规范化的欧氏距离度量。这种相似度量比传统的Euclidean相似性距离度量在振幅上的适应性要强，同时在计算时间上却不会有太大的增加。然后在此基础上，利用快速傅立叶变换对动态序列与各个模式序列之间的距离采用批处理方式进行相似性距离计算。同时为了减少批处理的等待时间，本文还引入了预测模型来提高批处理的效率，从而减少了查询的响应时间。2基本概念和算法2.1动态序列上的在线查询设两时间序列的长度为，那么它们之间的Euclidean距离为：该度量方式虽然可以作为相似度量方式，但是其只能适应幅度取值相似的的情况，对于幅度变化较大，但是变化趋势相似的序列却不能有效地适应。如考虑序列x1=(8,10,8,12,8,6,7,8,9,10,8,7),x2=(10,9,7,6,8,10,7,9,8,7,8,7,8,),x3=(13,15,18,16,19,16,13,15,17,18,19,15,14)，分别见图2中(a)(b)(c)。其中D(x1,x2)=2.23，D(x1,x3)=7.81，这样可能会得出这样的结论x2比x3更相似于x1，但实际上应该是x1与x3更相似。图2三个时间序列但是分别对x1,x2,x3做均值规范化后，即对应的序列分别减去它们的均值(分别为8.23，8，16)，然后再计算它们的距离有，D’(x1,x2)=2，D’(x1,x3)=0.7994，从而得出x3比x2更相似于x1的正确结果。由此有必要对序列进行规范化，利用其均值来实现规范化的度量相似性距离。定义1（规范化的距离）给定两个长度为的序列，它们的规范化距离可以定义如下：其中Mx，My是序列的均值。在本文中，假定长度固定的序列称为模式序列，记为Fi,其长度为Li+1，一个实时系统中含有多个这样的模式序列。称长度无限大的序列为动态序列，记为IS。在某个时刻p,p≥0，其长度为p+1。所谓在线查询就是要在每个时刻p，在IS中查询哪些模式序列Fi与其是最相似或比较相似。定义2（序列间的距离）设Fi是在数据库中的一些模式序列，其长度为li+1，对于给定的某个时刻p，IS与模式序列Fi在p时刻的距离定义为D(IS[p-li,p],Fi)。如果p<li，则令距离为无穷大。定义3（最接近和范围序列）设p≥0是一个整数，给定一个实数，称Fi是在时刻p上距离最接近的模式序列，如果对于其它模式序列Fj(j≠i),有D(IS[p-li,p],Fi)<D(IS[p-lj,p],Fj)；称Fi与IS在p时刻是基于h范围内接近的模式序列，如果有D(IS[p-li,p],Fi)≤h。定义4（两种查询类型）一个在动态序列上的在线查询就是指以下命题：1）在每个时刻p，发现与IS距离最接近的模式序列；2）在每个时刻p，发现与IS的相似距离是小于范围h的模式序列，h是一个大于0实数，是一个阈值。为了研究的方便，要求p≥max{li|Fi}，模式Fi的长度为li+1。2.2批处理计算对于处理在线查询，最原始的方法就是在每个时刻p，分别计算IS与Fi之间的距离。显然这样单个序列处理的计算量是非常大，其查询响应时间很难满足用户的需要。为此，将考虑其他方法来处理对不同序列进行距离计算。考虑D(IS[p-li,p],Fi)的定义，有：(1)其中MIS是序列IS[p-li,p]的移动平均值，MFi是Fi的平均值。与是随着时间变量推移而增加的，因此有关这些项可以通过前一个位置的值增量式地获得计算结果；和等没有时间变量的项，它们是可以提前计算出来；与是关于移动平均项，它们也可以采用增量式计算的方法获得；而关于最后一项，对于乘数IS[p-li+s]，其将时间变量p向前移一时刻变成p+1时，尽管Fi[s]却保持不变，但其仍然要分别和IS[p-li+s]的每个时刻数据要计算它们的乘积。这个计算也是最耗时间的，而且当前乘积的和与上一次计算的结果却没有什么直接关系。因此如何能快速地计算该项结果就成为在线相似性计算的关键。注意到，中的数据项类似于IS和Fi之间的相关系数计算。而对于它，则可以采用快速傅立叶变换来快速计算上述结果。定义5（相关函数）给定无限序列x和长度为l+1的有限序列y，那么它们之间的协相关函数为：其中，d是x和y之间的位移数，也称延迟参数。从上面式子可看出，只有x[d],x[d+1],...,x[d+l]参与了x和y在延迟d上的协相关函数计算。因此，结合（1）其最后一项可以写为。定义6（傅立叶变换与反傅立叶变换）设x和X是两个长度为N+1的时间序列，则有，其中X是x具有(N+1)点的傅立叶变换，x是X具有(N+1)点的反傅立叶变换。定义7（循环协相关序列）设x和X是两个长度为N+1的时间序列，则表示非规范化的循环协相关序列，其可定义为：定理1（循环相关性定理）设x,X,y和Y是两个长度为N+1的时间序列，且，，则有，其中是的复共轭。根据定理1，利用傅立叶变换来获取循环相关系数。思路是：假设N=，其中k为某些正整数，先利用快速傅立叶变换计算序列的傅立叶系数，然后计算它们的乘积，最后根据结果，再利用反傅立叶变换来获取它们的循环相关系数。具体来说，给定序列，，其长度分别是N+1，首先利用FFT计算X和Y，然后生成序列<>，最后再利用反FFT获得它们的循环协相关系数。通过上述循环协相关系数，就可以快速计算动态序列IS与模式序列Fi的协相关系数。3改进的相似性在线查询上述批处理计算方法与传统顺序扫描的方法相比，可以节省大量的计算时间，然而，上述过程不能直接提高相似性查询的响应速度。因此，在这部分中，将探讨提高相似性在线查询响应速度的方法。3.1带预测值的在线查询不难发现，造成批处理计算方式响应时间慢的主要原因是它必须等足N-lmax个动态序列的值后才会进行一次批处理计算。如果选择的N使得N-lmax比较小（也就是说，批处理发起的时间间隔很短），那么该批处理计算不可能会有什么时间节省，事实上还有可能比最原始顺序扫描的方式还要耗时，因此它毕竟还有另外的一些计算开销，如傅立叶变换等。相反，若N-lmax比较大，也就是说发起批处理的时间间隔相对较长，那么其需要等待的响应时间就要很长，这很难适应实际应用在线需求。因此，在批处理等待的时间内，如果根据一些已出现的数值，可以利用一些预测模型来对未来的值进行预测，然后通过预测值来发起批处理，那么这样则大大可以提高算法的响应时间。事实上在许多实际应用中，时间序列是可以采用预测的方法来估计其未来的趋势和模式[[]L.Gyorfi,G.LugosiandG.Morvai.Asimplerandomizedalgorithmforsequentialpredictionofergodictimeseries.IEEETransactionsonInformationTheory,45(7):2642-2650,1999.][[]I.KimandS.R.Lee.Afuzzytimeseriespredictionmethodbasedonconsecutivevalues.InFuzzySystemsConferencesProceedings,Vol.2,703-707][[[]L.Gyorfi,G.LugosiandG.Morvai.Asimplerandomizedalgorithmforsequentialpredictionofergodictimeseries.IEEETransactionsonInformationTheory,45(7):2642-2650,1999.[]I.KimandS.R.Lee.Afuzzytimeseriespredictionmethodbasedonconsecutivevalues.InFuzzySystemsConferencesProceedings,Vol.2,703-707[]S.PolikerandA.Geva.Anewalgorithmfortimeseriespredictionbytemporalfuzzyclustering.InProceedings.15thInternationalConferenceonPatternRecognition,vol.2,728-731,2000[]T.V.Gestel,J.Suykens,D.E.Baestaens,.A.Lamberechts,G.Lanckriet,B.Vandaele,D.B.Moor,andJ.Vandewalle.FinancialtimeseriespredictionusingleastsquaresSuportVectorMachineswithintheevidenceframework.IEEETransactionsonNeuralNetwork,12(4):809-821,2001.利用动态序列的预测值来代替实际真实值后，同样可利用快速傅立叶变换，采用批处理方式计算动态序列与模式序列在一些未来时刻的预测相似性距离。预测的长度取决与实际应用的需要，因为通常预测长度越长，预测的准确性就越差。当实际值到来时，预测误差便可计算出。这样通过预测误差和预测相似性距离获取与动态序列距离接近的模式序列。本文称这种方法为带预测的相似性在线查询（OnlineQueryingwithPrediction），记为OQP。图3预测和批处理过程图3展示了OQP过程。假定当前考虑时刻为ps，即是说在ps-1时刻的在线查询已经完成，ps时刻的数值还没有到来。在这个时刻，利用n步向前预测方法已预测到这个时刻的值。用预测长度来表示最大的预测区间，在ps到来前，利用预测模型获得了在ps,ps+1,...,ps+n-1,的预测值。用PS表示一个包含ps-1实际值，n个预测值和一些未预测值（用0来表示）的动态序列，并称该序列为预测序列，那么此时有：对于PS，仍然可采用前面2.2的算法，按照批处理方法进行相似性距离计算。此外，算法不能在ps+n-1以后的时刻不能获得预测值，因此算法最多只能计算PS与Fi在时刻ps,ps+1,...,ps+n-1上的预测相似性距离。一旦在ps和ps+n-1之间某个时刻的实际值到来，算法可利用预测误差来查询与动态序列相似的模式序列，查询的具体过程取决于查询的类型。由定义4可知，查询类型包含两种，即最接近查询和h-范围查询。3.2最接近的相似性查询算法动态时间序列最接近的相似性在线查询，需要在每个时刻上找出与动态序列相似距离最短的模式序列。即是说，查询算法根据预测距离和预测误差来过滤掉那些与动态序列距离较远的模式序列。考虑在ps和ps+n-1之间某个时刻p，通过3.1中的算法可以获得每个模式序列Fi的预测距离D(IS[p-li,p],Fi)。此外，2.2给出的算法还可以增量式地计算预测序列PS与实际序列IS在p时刻后，长度为li+1的预测误差，即预测误差D(PS[p-li,p],IS[p-li,p])在p时刻到来之前，其所有时刻的值是已知的。根据上述预测距离和预测误差，可以得到实际动态序列与各个模式序列在时刻p上距离的最小和最大边界。事实上，利用Euclidean距离，它们存在如下三角不等式：(3)其中x=PS[p-1i,p],y=IS[p-li,p]，此三角不等式的关系可以用图4来描述。图4三角不等式之间的关系注意到，不等式（3）对于每个模式序列Fi在时刻p都是成立的。为了简单起见，查询算法采用最大预测误差来估算其上边界，即令给定模式序列Fi，D(IS[p-li,p],Fi)+maxD(PSp,ISp)就是其最大边界值，Fi，D(IS[p-li,p],Fi)-maxD(PSp,ISp)就是其最小边界值。下图5给出了在p时列刻，按照预测距离D(IS[p-li,p],Fi)i=0,...,m大小递增排序，各个模式序列所获得的最小和最大边界值。图5最接近的候选序列在图5中，为了叙述简单，对模式序列重新编排下标，并按照它们与动态预测序列的相似性距离大小递增排序，记为<s0,s1,...sm>。因此有：（4）由不等式（3）可知，（4）之中的实际动态序列IS与模式序列Fi在p时刻的实际相似性距离必须也满足上述边界要求。由于算法的目的是要在p时刻找出与动态序列最接近的模式序列，而模式序列Fs0与动态序列是具有最小的预测距离，因此其在全部模式序列中具有最小的上边界距离，见图5中的minUp。3.3h范围的相似性查询算法h-范围的的相似性查询不像前面的最接近查询，其返回结果只有一个，h-范围的查询可能有0个或多个结果返回。注意到前面的不等式(3)中三角不等关系对于每个时刻p都是成立的。因此，查询算法仍然可以利用前面的最上边界和最下边界的方法。首先根据它们与预测序列PS的预测相似性距离进行递增排序，按照图6方式获得其最上边界值和最下边界值。图6h-范围查询的候选序列不像最接近查询一样，其最上边界值可用来过滤掉那些不可能是查询结果的模式序列，而在h-范围查询中，阈值h可以是大于0的任何一个实数，因此，这样就不能简单地仅用最上边界值来过滤一些模式序列。为了查询与动态序列的h-范围的序列，把模式序列分成三种类型：1）模式序列Fi是类型1的，如果h是大于或等于其上边界值；2）模式序列Fi是类型2的，如果h是小于其下边界值；3）模式序列Fi是类型3的，如果h是介于其上边界值和下边界值之间。很明显，类型1中的模式序列与动态序列在h-范围内是相似，因为实际的距离不可能大于h；同样地，类型2中的模式不可能与动态序列在h-范围内相似，因为实际的距离一定大于h；而对于类型3中的模式，我们不能确定，因此也称为候选模式序列，需要通过实际的距离计算还检验其是否是小于h。4模拟实验为了对相似性在线查询算法的效果与效率进行考察，本文将仍然采用文献[4]提供的数据集进行实验。首先，利用随机游走函数（RandomWalk）来生成一个动态时间序列IS，即，其中Randomwalk[0:20219]是一随机游走序列。实验测试的模式序列有4组类型，其的长度分别在300-400，500-600，700-800和300-800之间。它们也是利用上述类似的随机游走函数来生成，以确保模式序列能与动态序列相似。在每组模式序列类型中，共有100个长度不等的模式序列，如在300-400类型中，各模式序列的长度可以为300,301,…399等。图7是一个长度为800的模式序列例子。图7一个长度为800的模式序列实验首先对两种相似性度量方式的效果进行比较分析。我们同样对长度为300-400之间的模式序列进行h=30的范围查询，以序列的基本变化趋势来衡量查询结果的准确性。下面表1给出了本文与文献[4]在相似性度量上的比较。表1两种度量方式的比较距离度量平均准确性平均时间(s)Euclidean65%147.23NormalEuclidean87%176.81从表中可以看出，尽管规范化的欧氏距离在计算时间上要多29.58s，增加16.7%，但是在相似性度量的准确性上却提高了22%。接下来给出基于规范化欧氏距离的一些实验结果。图8是在某一时刻，动态时间序列与长度为300-400之间的模式序列类型中所有模式序列经排序后的Euclidean相似距离。图8300-400类型中的模式距离实验采用的预测模型是一种预测误差与预测步数的平方根（）呈线性变化的预测模型，即，这样的模型如有ARMA预测模型。实验查询类型有2种；其一，在动态时间序列的每个时刻上，在所有的模式序列中查询出相似距离与之最接近的序列；其二，给定查询范围为30的情况下，在每个时刻找出与动态序列相似距离小于该范围的模式序列。图9、图10分别给出了在这两种查询类型下，算法所需的相对查询花费代价，即OQP算法与顺序扫描计算算法在每一时刻上的平均计算时间。从图中可以看出，当预测误差在比较小的情况下，在线查询算法具有比顺序扫描更好的查询性能。这主要归功于算法采用了批处理计算的方式，使得在较长序列的查询中，只需要少量的快速傅立叶变换计算就可完成。相对计算时间预测长度图9Errsqrt相对计算时间预测长度预测长度预测长度相对计算时间图10Errsqrt下h=30范围相似性查询的相对时间5小结本文研究了时间序列在线的相似性查询问题。在线的相似性查询是时间序列相似性查询新的研究重点和方向，它是时间序列的安全监管与实时控制等实际应用问题的关键技术。本文针对文献[4]提出的算法在相似性度量上的不足，给出了一种改进的动态序列相似性在线查询算法。算法采用了一种规范化的相似性度量方式，考虑到了不同序列在振幅上不一致性，利用快速傅立叶变换进行批处理计算方式来达到快速相似性计算；此外，为了提高查询时的响应时间，算法采用预测模型方法对未来值进行预测，最终提高整个算法的查询效率。而且实验结果也显示，该算法在查询的效果与效率具有较好的查询性能。参考文献

论大学生写作能力写作能力是对自己所积累的信息进行选择、提取、加工、改造并将之形成为书面文字的能力。积累是写作的基础，积累越厚实，写作就越有基础，文章就能根深叶茂开奇葩。没有积累，胸无点墨，怎么也不会写出作文来的。写作能力是每个大学生必须具备的能力。从目前高校整体情况上看，大学生的写作能力较为欠缺。一、大学生应用文写作能力的定义那么，大学生的写作能力究竟是指什么呢？叶圣陶先生曾经说过，“大学毕业生不一定能写小说诗歌，但是一定要写工作和生活中实用的文章，而且非写得既通顺又扎实不可。”对于大学生的写作能力应包含什么，可能有多种理解，但从叶圣陶先生的谈话中，我认为：大学生写作能力应包括应用写作能力和文学写作能力，而前者是必须的，后者是“不一定”要具备，能具备则更好。众所周知，对于大学生来说，是要写毕业论文的，我认为写作论文的能力可以包含在应用写作能力之中。大学生写作能力的体现，也往往是在撰写毕业论文中集中体现出来的。本科毕业论文无论是对于学生个人还是对于院系和学校来说，都是十分重要的。如何提高本科毕业论文的质量和水平，就成为教育行政部门和高校都很重视的一个重要课题。如何提高大学生的写作能力的问题必须得到社会的广泛关注，并且提出对策去实施解决。二、造成大学生应用文写作困境的原因：（一）大学写作课开设结构不合理。就目前中国多数高校的学科设置来看，除了中文专业会系统开设写作的系列课程外，其他专业的学生都只开设了普及性的《大学语文》课。学生写作能力的提高是一项艰巨复杂的任务，而我们的课程设置仅把这一任务交给了大学语文教师，可大学语文教师既要在有限课时时间内普及相关经典名著知识，又要适度提高学生的鉴赏能力，且要教会学生写作规律并提高写作能力，任务之重实难完成。（二）对实用写作的普遍性不重视。“大学语文”教育已经被严重地“边缘化”。目前对中国语文的态度淡漠，而是呈现出全民学英语的大好势头。中小学如此，大学更是如此。对我们的母语中国语文，在大学反而被漠视，没有相关的课程的设置，没有系统的学习实践训练。这其实是国人的一种偏见。应用写作有它自身的规律和方法。一个人学问很大，会写小说、诗歌、戏剧等，但如果不晓得应用文写作的特点和方法，他就写不好应用文。（三）部分大学生学习态度不端正。很多非中文专业的大学生对写作的学习和训练都只是集中在《大学语文》这一门课上，大部分学生只愿意被动地接受大学语文老师所讲授的文学经典故事，而对于需要学生动手动脑去写的作文，却是尽可能应付差事，这样势必不能让大学生的写作水平有所提高。（四）教师的实践性教学不强。学生写作能力的提高是一项艰巨复杂的任务，但在教学中有不少教师过多注重理论知识，实践性教学环节却往往被忽视。理论讲了一大堆，但是实践却几乎没有，训练也少得可怜。阅读与写作都需要很强的实践操作，学习理论固然必不可少，但是阅读方法和写作技巧