近年來，由于計算機技術(shù)的提高，人們的生活和工作中積累了大量數(shù)據(jù)[1]，迫切需要從這些海量的數(shù)據(jù)中提取出有用的信息和知識，以用于相關(guān)領域的發(fā)展。傳統(tǒng)的查詢分析難以滿足需求，數(shù)據(jù)挖掘由此應運而生并得到廣泛應用。自1993年AgrawalR等人發(fā)表關(guān)于時間序列相似性查詢的研究論文[2]以來，時間序列相似性查詢受到廣泛重視，成為理論和應用兩方面的研究熱點。

　　摘要：從應用角度對時間序列數(shù)據(jù)挖掘中的關(guān)鍵技術(shù)-相似性度量-進行了研究。實現(xiàn)了對時間序列的分段線性表示，并將其用于當前主要的幾種時間序列距離度量算法。通過將各距離度量算法用于股票收盤數(shù)據(jù)分析實驗，得出實驗數(shù)據(jù)。通過對實驗結(jié)果的分析并結(jié)合各算法的原理，對各方法的適用情況和執(zhí)行效率進行了分析及比較。通過分析可知，每種算法有自己的特點及適用情況。對于實際應用，應根據(jù)實際需求選擇合適的距離度量算法。

　　關(guān)鍵詞：時間序列,數(shù)據(jù)挖掘,分段線性表示,相似性度量,編輯距離

　　1時間序列的定義及表示

　　1.1時間序列的定義

　　時間序列（TimeSeries）是反映某種特征的一個統(tǒng)計指標按時間先后排列而形成的序列。時間序列反映社會經(jīng)濟現(xiàn)象的發(fā)展變化過程、發(fā)展趨勢和速度，可以用來對發(fā)展變化規(guī)律進行研究，對某些社會經(jīng)濟現(xiàn)象進行預測。

　　時間序列就是按照時間的順序隨機事件變化發(fā)展過程的記錄。下面給出時間序列的完整定義。

　　1.2時間序列的模式表示

　　時間序列的模式表示是一種對時間序列進行抽象和概括的特征表示方法，是在更高層次上對時間序列的重新描述。常用的時間序列模式表示方法主要包括：頻域表示法，分段線性表示法，符號表示法等。分段線性表示法具有易于理解和操作，且提取的特征比較符合原數(shù)據(jù)的特征的特點，因此，在實驗中，采用分段線性表示法。

　　分段線性表示（PiecewiseLinearRepresentation，PLR）的基本思想是用K個直線段來近似替代原來的時間序列。這個思想最早可以追溯到1974年P(guān)avlidis和Horowitz等提出的分段線性分割方法[4]。大致來說，PLR方法通過選取序列中的特殊數(shù)據(jù)點[5]或者視覺重要點（PerceptuallyImportantPoint，PIP）[6-7]來提取原時間序列中的特征。

　　線性回歸表示：直線每一段的通過最小二乘法來擬合，相鄰段之間一般不連續(xù)。

　　線性插補表示：直線每一段只是簡單的開始和結(jié)束兩點之間相連，相鄰段之間收尾相連，因此相鄰段是連續(xù)的。

　　一般來說，前者雖然直線每一段不連續(xù)，但是與原始數(shù)據(jù)更為接近，特征提取更符合數(shù)據(jù)原本面貌。

　　2時間序列的相似性度量方法

　　時間序列的相似性度量：即衡量兩個時間序列的相似程度。它是時間序列數(shù)據(jù)挖掘的基礎，因為幾乎所有時間序列挖掘算法都涉及到計算序列之間的相似性問題。一般提到相似性度量，都是用相似性距離替代。目前時間序列的相似性度量主要采用：歐式距離，動態(tài)時間彎曲距離（DTW），最長公共子序列（LCS），編輯距離等。

　　2.1EuclideanDistance歐式距離

　　2.2動態(tài)時間彎曲距離

　　3.2實驗結(jié)果及分析

　　由于三種算法度量標準不同，故直接比較三種算法的計算結(jié)果不能清晰地說明算法間的不同。為了能夠更直觀的說明問題，我們將相似性度量算法用于相似性搜索中，并對搜索結(jié)果進行效率和準確性兩個方面的比較。效率即比較相同的搜索情況下所用時間長短。時間越短，效率越高。準確性指比較相同的搜索情況下的搜索結(jié)果。度量標準雖不同，但相似度大小關(guān)系應一致。

　　而每個方面，我們采用兩種方式的比較——橫向和縱向。

　　橫向比較是指同一種算法，當移動窗口數(shù)不同時，搜索的效率與準確性的比較。

　　縱向比較是指不同的算法，當移動窗口數(shù)相同是，搜索的效率和準確性的比較。

　　在列出比較結(jié)果之間，首先介紹一下實驗環(huán)境。本實驗采用WindowsXP操作系統(tǒng)，開發(fā)語言為C++，開發(fā)工具為VisualStudio2010，數(shù)據(jù)庫為SQLServer2005。其中，數(shù)據(jù)為近10年的日K線A股股票數(shù)據(jù)。實驗中主要使用股票日期及收盤價。

　　下面列出比較結(jié)果，其中表4.1是三種算法時間比較，所用數(shù)據(jù)庫是浦發(fā)銀行10年收盤價（2000-1-12～2012-4-12），用于搜索的時間序列是其中的一段（2010-4-4～2010-7-7）。

　　從縱向來看，歐式距離由于其算法的簡單性，時間消耗也最少，而且與另外兩種算法比起來，所花時間只有DTW算法的6.7%，LCS算法的3.4%。因此在滿足準確性要求，且用于比較的時間序列具有相同長度的前提下，應該盡可能的使用歐式算法。而DTW算法又比LCS算法用時少，前者大約是后者的50%。

　　從橫向來看，隨著移動窗口數(shù)的增加，每一種算法時間的消耗是逐漸減少的，這符合我們的判斷。并且滿足以下關(guān)系，移動窗口數(shù)每增加一倍，時間變成原來的二分之一。

　　表2是三種算法結(jié)果比較，所用數(shù)據(jù)庫是白云機場10年收盤價（2000-1-12——2012-4-12），而用于搜索的仍然是浦發(fā)銀行中的一段時間序列（2010-4-4——2010-7-7）。

　　4總結(jié)

　　本文實現(xiàn)了當前主要的幾種時間序列距離度量算法，通過對實驗結(jié)果的分析并結(jié)合算法的原理，對各方法的適用情況和執(zhí)行效率進行了分析及比較。通過分析可知：每種算法有自己的特點及適用情況。對于實際應用，應根據(jù)實際需求選擇合適的距離度量算法。對于一元等長序列的距離計算，通過實驗可知，歐式距離具有較大的效率優(yōu)勢，且計算結(jié)果滿足需求。因此，應優(yōu)先考慮選取歐氏距離。

　　對于一元非等長序列的距離計算，歐氏距離無法應用于該領域，DTW距離算法則是當期最有效的距離度量方法。而制約DTW距離算法使用的首要因素為時間效率。根據(jù)實驗結(jié)論可知，歐式距離的時間效率優(yōu)于DTW距離，而LCS距離算法花費時間最長。因此，在實際應用中，應結(jié)合具體數(shù)據(jù)特點，選取合適的下界距離算法，在滿足精確度的前提下，盡量提高DIW距離算法的時間效率。

　　參考文獻：

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

　　[2]AgrawalR，F(xiàn)aloutsosC，SwamiA.Efficientsimilaritysearchinsequencedatabases[C].Chicago，IL：Procofthe4thInt’lConfonFoundationsofDataOrganizationandAlgorithms，1993：69-84.

　　[3]鄧納姆（Dunham，M.H.）.數(shù)據(jù)挖掘教程[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，F(xiàn)eb.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.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiyingyonglw/25766.html