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

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

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

　　1時(shí)間序列的定義及表示

　　1.1時(shí)間序列的定義

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

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

　　1.2時(shí)間序列的模式表示

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

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

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

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

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

　　2時(shí)間序列的相似性度量方法

　　時(shí)間序列的相似性度量：即衡量兩個(gè)時(shí)間序列的相似程度。它是時(shí)間序列數(shù)據(jù)挖掘的基礎(chǔ)，因?yàn)閹缀跛�有時(shí)間序列挖掘算法都涉及到計(jì)算序列之間的相似性問題。一般提到相似性度量，都是用相似性距離替代。目前時(shí)間序列的相似性度量主要采用：歐式距離，動(dòng)態(tài)時(shí)間彎曲距離（DTW），最長公共子序列（LCS），編輯距離等。

　　2.1EuclideanDistance歐式距離

　　2.2動(dòng)態(tài)時(shí)間彎曲距離

　　3.2實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

　　4總結(jié)

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

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

　　參考文獻(xiàn)：

　　[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].郭崇慧，譯.北京：清華大學(xué)出版社，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