黑河学院学报计算机论文范文参考

　　近年来，由于计算机技术的提高，人们的生活和工作中积累了大量数据[1]，迫切需要从这些海量的数据中提取出有用的信息和知识，以用于相关领域的发展。传统的查询分析难以满足需求，数据挖掘由此应运而生并得到广泛应用。自1993年AgrawalR等人发表关于时间序列相似性查询的研究论文[2]以来，时间序列相似性查询受到广泛重视，成为理论和应用两方面的研究热点。

　　摘要：从应用角度对时间序列数据挖掘中的关键技术-相似性度量-进行了研究。实现了对时间序列的分段线性表示，并将其用于当前主要的几种时间序列距离度量算法。通过将各距离度量算法用于股票收盘数据分析实验，得出实验数据。通过对实验结果的分析并结合各算法的原理，对各方法的适用情况和执行效率进行了分析及比较。通过分析可知，每种算法有自己的特点及适用情况。对于实际应用，应根据实际需求选择合适的距离度量算法。

　　关键词：时间序列,数据挖掘,分段线性表示,相似性度量,编辑距离

　　1时间序列的定义及表示

　　1.1时间序列的定义

　　时间序列（TimeSeries）是反映某种特征的一个统计指标按时间先后排列而形成的序列。时间序列反映社会经济现象的发展变化过程、发展趋势和速度，可以用来对发展变化规律进行研究，对某些社会经济现象进行预测。

　　时间序列就是按照时间的顺序随机事件变化发展过程的记录。下面给出时间序列的完整定义。

　　1.2时间序列的模式表示

　　时间序列的模式表示是一种对时间序列进行抽象和概括的特征表示方法，是在更高层次上对时间序列的重新描述。常用的时间序列模式表示方法主要包括：频域表示法，分段线性表示法，符号表示法等。分段线性表示法具有易于理解和操作，且提取的特征比较符合原数据的特征的特点，因此，在实验中，采用分段线性表示法。

　　分段线性表示（PiecewiseLinearRepresentation，PLR）的基本思想是用K个直线段来近似替代原来的时间序列。这个思想最早可以追溯到1974年Pavlidis和Horowitz等提出的分段线性分割方法[4]。大致来说，PLR方法通过选取序列中的特殊数据点[5]或者视觉重要点（PerceptuallyImportantPoint，PIP）[6-7]来提取原时间序列中的特征。

　　线性回归表示：直线每一段的通过最小二乘法来拟合，相邻段之间一般不连续。

　　线性插补表示：直线每一段只是简单的开始和结束两点之间相连，相邻段之间收尾相连，因此相邻段是连续的。

　　一般来说，前者虽然直线每一段不连续，但是与原始数据更为接近，特征提取更符合数据原本面貌。

　　2时间序列的相似性度量方法

　　时间序列的相似性度量：即衡量两个时间序列的相似程度。它是时间序列数据挖掘的基础，因为几乎所有时间序列挖掘算法都涉及到计算序列之间的相似性问题。一般提到相似性度量，都是用相似性距离替代。目前时间序列的相似性度量主要采用：欧式距离，动态时间弯曲距离（DTW），最长公共子序列（LCS），编辑距离等。

　　2.1EuclideanDistance欧式距离

　　2.2动态时间弯曲距离

　　3.2实验结果及分析

　　由于三种算法度量标准不同，故直接比较三种算法的计算结果不能清晰地说明算法间的不同。为了能够更直观的说明问题，我们将相似性度量算法用于相似性搜索中，并对搜索结果进行效率和准确性两个方面的比较。效率即比较相同的搜索情况下所用时间长短。时间越短，效率越高。准确性指比较相同的搜索情况下的搜索结果。度量标准虽不同，但相似度大小关系应一致。

　　而每个方面，我们采用两种方式的比较——横向和纵向。

　　横向比较是指同一种算法，当移动窗口数不同时，搜索的效率与准确性的比较。

　　纵向比较是指不同的算法，当移动窗口数相同是，搜索的效率和准确性的比较。

　　在列出比较结果之间，首先介绍一下实验环境。本实验采用WindowsXP操作系统，开发语言为C++，开发工具为VisualStudio2010，数据库为SQLServer2005。其中，数据为近10年的日K线A股股票数据。实验中主要使用股票日期及收盘价。

　　下面列出比较结果，其中表4.1是三种算法时间比较，所用数据库是浦发银行10年收盘价（2000-1-12～2012-4-12），用于搜索的时间序列是其中的一段（2010-4-4～2010-7-7）。

　　从纵向来看，欧式距离由于其算法的简单性，时间消耗也最少，而且与另外两种算法比起来，所花时间只有DTW算法的6.7%，LCS算法的3.4%。因此在满足准确性要求，且用于比较的时间序列具有相同长度的前提下，应该尽可能的使用欧式算法。而DTW算法又比LCS算法用时少，前者大约是后者的50%。

　　从横向来看，随着移动窗口数的增加，每一种算法时间的消耗是逐渐减少的，这符合我们的判断。并且满足以下关系，移动窗口数每增加一倍，时间变成原来的二分之一。

　　表2是三种算法结果比较，所用数据库是白云机场10年收盘价（2000-1-12——2012-4-12），而用于搜索的仍然是浦发银行中的一段时间序列（2010-4-4——2010-7-7）。

　　4总结

　　本文实现了当前主要的几种时间序列距离度量算法，通过对实验结果的分析并结合算法的原理，对各方法的适用情况和执行效率进行了分析及比较。通过分析可知：每种算法有自己的特点及适用情况。对于实际应用，应根据实际需求选择合适的距离度量算法。对于一元等长序列的距离计算，通过实验可知，欧式距离具有较大的效率优势，且计算结果满足需求。因此，应优先考虑选取欧氏距离。

　　对于一元非等长序列的距离计算，欧氏距离无法应用于该领域，DTW距离算法则是当期最有效的距离度量方法。而制约DTW距离算法使用的首要因素为时间效率。根据实验结论可知，欧式距离的时间效率优于DTW距离，而LCS距离算法花费时间最长。因此，在实际应用中，应结合具体数据特点，选取合适的下界距离算法，在满足精确度的前提下，尽量提高DIW距离算法的时间效率。

　　参考文献：

　　[1]MitraS，PalSK，MitraP.Datamininginsoftcomputingframework：Asurvey[J].IEEETransactionsonNeuralNetworks，2002，13（1）：3-14.

　　[2]AgrawalR，FaloutsosC，SwamiA.Efficientsimilaritysearchinsequencedatabases[C].Chicago，IL：Procofthe4thInt’lConfonFoundationsofDataOrganizationandAlgorithms，1993：69-84.

　　[3]邓纳姆（Dunham，M.H.）.数据挖掘教程[M].郭崇慧，译.北京：清华大学出版社，2005，217-218.

　　[4]Th.Pavlidis，SLHorwitz.SegmentationofPlaneCurves[J].IEEETransactionsonComputer，1974，23（8）：860-870.

　　[5]PerngC-S，WangH，andZhangSR.Landmarks：anewmodelforsimilarity-basedpatternqueryingintimeseriesdatabases[C].Proceedingofthe16thInternationalConferenceonDataEngineering，SanDiego，CA，USA，Feb.28-Mar.3，2000：33-42.

　　[6]FuT，ChungF，LukR，etal.Stocktimeseriespatternmatching：template-basedvs.rule-basedapproaches[J].EngineeringApplicationsofArtificialIntelligence，2007，20（3）：347-364.

　　[7]PhetkingC，SapM，SelamatA.Identifyingzigzagbasedperceptuallyimportantpointsforindexingfinancialtimeseries[C].Proceedingsofthe8thInternationalConferenceonCognitiveInformatics，HongKong，China，Jun.15-17，2009：295-301.