新型時間序列相似性度量方法研究

摘要：基于時間序列符號化后的特點，創(chuàng)造性地提出了一種新型相似性度量方法——符號化的統(tǒng)計向量空間法(SAX[1] Statistical Vector Space，SSVS)。將這種度量方法用于SP500指數(shù)的股票數(shù)據(jù)聚類實驗，并與經(jīng)典相似性度量方法比較，結(jié)果表明這種新的方法能夠高效地從整體趨勢的角度度量時間序列的相似性，有很好的實際意義和應(yīng)用前景。

關(guān)鍵詞：時間序列； 相似性度量； 數(shù)據(jù)挖掘； 符號化

中圖分類號：TP391.41文獻標(biāo)志碼：A

文章編號：1001－3695(2007)05－0112－03

近年來，隨著數(shù)據(jù)不斷豐富，人們對強有力的數(shù)據(jù)分析工具的需求增加，數(shù)據(jù)挖掘開始得到廣泛的應(yīng)用[1]。例如對海量數(shù)據(jù)進行分析處理，挖掘其中蘊涵的各種信息，對于揭示事物發(fā)展的規(guī)律，發(fā)現(xiàn)不同的事物發(fā)展之間的相互關(guān)系等具有重要的實際意義。其中，時間序列數(shù)據(jù)會隨著時間的推移規(guī)模不斷擴大。因此針對時間序列數(shù)據(jù)的數(shù)據(jù)挖掘研究一直以來受到了學(xué)術(shù)界和工業(yè)界的廣泛重視，成為了一個具有重要理論和實際價值的熱點研究課題。

時間序列的相似性度量是衡量兩個時間序列的相似程度的方法；它是時間序列分類、聚類、異常發(fā)現(xiàn)等諸多數(shù)據(jù)挖掘問題的基礎(chǔ)，也是時間序列挖掘的核心問題之一。歐氏距離(Euclidean)和動態(tài)時間彎曲(Dynamic Time Warping)是用于時間序列相似性度量的兩種經(jīng)典方法，但是這兩種方法在應(yīng)用到實際的時間序列數(shù)據(jù)挖掘上都有其固有的缺陷。例如在研究股票價格時通常更加關(guān)注股票整體走勢，而股票細(xì)節(jié)處的波動性則是一種干擾因素。歐氏距離則易受股票價格序列波動的干擾；動態(tài)時間彎曲度量雖然能較好地克服歐氏距離度量這方面的不足，但其算法復(fù)雜度限制了其應(yīng)用范圍。

時間序列近似表示是指將長度為n的時間序列近似表示為長度為N（N＜＜n）的序列。符號化表示[2，3]是近幾年提出的時間序列近似表示的方法之一，因其離散化、非實數(shù)表示的特點得到越來越多的關(guān)注。本文基于一種新型符號化方法SAX[4]，利用時間序列符號化后的字符序列特點，提出了一種新型相似性度量方法——符號化的統(tǒng)計向量空間法(SAX Statistical Vector Space，SSVS)。通過對比實驗研究表明，該方法能夠在減小時間代價的同時獲得較好的度量準(zhǔn)確性。

1經(jīng)典的相似性度量方法

歐氏距離和動態(tài)時間彎曲是兩種經(jīng)典的相似性度量方法。

約定：在以下公式中出現(xiàn)的字符意義：

Q表示相似性度量的序列一

C表示相似性度量的序列二

qi表示Q序列在第i個點的取值

cj表示C序列在第j個點的取值

i，n分別表示當(dāng)前點在整個序列的序號和整個序列的長度

d(qi，cj)表示Q序列的第i個點和C序列的第j個點之間的距離

歐氏距離計算公式如下:

從上式可以看出計算歐氏距離要求兩個序列等長，且兩個序列中的值必須是一一對應(yīng)，每一對差值的權(quán)重相同。歐氏距離以其簡單實用被廣泛采用。

動態(tài)時間彎曲用于計算兩個時間序列之間的最大相似性，也即是求最小距離。這種計算方法是時間序列相似性度量所特有的，其計算公式如下:

（2）取兩個序列結(jié)束點的距離r(i， j)為兩個序列的DTW距離。

可以看到計算DTW距離的時間復(fù)雜度為O(n2)，遠高于計算歐氏距離的時間復(fù)雜度O(n)；但是DTW距離不要求兩個序列等長，且兩個序列求差值的點可以一對多或多對一。兩者的對比示意圖如圖1所示。

2符號化的統(tǒng)計向量空間法

符號化的統(tǒng)計向量空間法SSVS由三步組成：

(1)采用SAX對時間序列符號化，得到符號序列；

(2)對符號序列進行特征統(tǒng)計，得到對應(yīng)的特征向量；

(3)計算兩個特征向量的余弦距離為對應(yīng)的兩個時間序列的相似度。

2．1時間序列的符號化

Eammon在分段集成近似(PAA)基礎(chǔ)上提出了一種新型符號化方法(Symbolic Aggregate approXimation，SAX)。其基本思想是利用PAA對長度為n的時間序列降維，得到N維的時間序列，然后將降維后的序列值劃分為m個等概率的區(qū)間，并將處于同一個概率區(qū)間的序列值用同一個符號表示。其示意圖如圖2所示。

這種新型符號化方法SAX與其他符號化方法相比有以下的優(yōu)點：

（1）簡單、易用且算法不依賴于具體實驗數(shù)據(jù)；

（2）在符號化的過程中實現(xiàn)了降維（N＜＜n），能有效解決對高維數(shù)據(jù)進行數(shù)據(jù)挖掘由于維數(shù)過高引起的問題；

（3）保證在符號空間計算出的兩個符號序列的距離滿足實際兩個時間序列的距離下界的要求，即不會出現(xiàn)漏報[5]。

2．2相似性度量

由于符號化后的時間序列是由離散、有限的字符組成，可以作為字符串進行進一步的分析處理。基于對文本進行相似性度量的向量空間模型[6]和時間序列度量的特點，本文設(shè)計了三類統(tǒng)計特征：

（1）統(tǒng)計字符集中單個字符在字符串中出現(xiàn)的頻率。這類特征數(shù)目為字符集的大小m，單個特征權(quán)值為1；

（2）統(tǒng)計字符串中所有兩個連續(xù)字符的三種大小關(guān)系（前＜后，前=后，前＞后）在字符串中出現(xiàn)的頻率，這類特征數(shù)目為3，單個特征權(quán)值為2；

（3）統(tǒng)計字符串中所有三個連續(xù)字符的五種大小關(guān)系（用兩個相鄰字符的關(guān)系表示為==， >>， <<， <>， ><）在字符串中出現(xiàn)的頻率，這類特征數(shù)目為5，單個特征權(quán)值為3。

三類統(tǒng)計特征組成了字符序列的特征向量T=t1，…，ts，s=m+8。將向量作歸一化處理，兩個時間序列的相似度可以通過計算特征向量之間的距離來度量。采用余弦距離計算如下：

3實驗框架

前面給出了兩種度量時間序列相似性的經(jīng)典方法，并詳細(xì)闡述了基于SAX的新型相似性度量方法——符號化的統(tǒng)計向量空間法SSVS。為了對所提出的SSVS進行深入研究，本文結(jié)合經(jīng)典的度量方法，設(shè)計了五種實驗方案對比研究各種相似性度量方法在時間序列數(shù)據(jù)聚類中的特點。方案一：基于原時間序列，采用歐氏距離度量序列的相似性；方案二：采用SAX對原時間序列符號化后，用歐氏距離度量序列的相似性；方案三：基于原時間序列，用動態(tài)時間彎曲度量序列的相似性；方案四：采用SAX對原時間序列符號化后，用動態(tài)時間彎曲度量序列的相似性；方案五：采用符號化的統(tǒng)計向量空間法SSVS度量序列的相似性。

3．1實驗數(shù)據(jù)

實驗數(shù)據(jù)采用標(biāo)準(zhǔn)普爾500指數(shù)股票（Standard and Poor 500 index，縮寫SP500， http://kumo.swcp.com/stocks/）的歷史交易數(shù)據(jù)。該數(shù)據(jù)集在各種數(shù)據(jù)挖掘的研究文獻中作為實驗數(shù)據(jù)。

本文抽取了八支股票連續(xù)2 048個交易日的收盤價格為實驗數(shù)據(jù)，對實際的股票數(shù)據(jù)進行了正規(guī)化的預(yù)處理[7]：

3．3實驗結(jié)果

基于前文的實驗數(shù)據(jù)和評價標(biāo)準(zhǔn)，將五種方案用于聚類實驗，實驗結(jié)果如表1所示。其中n為原時間序列長度，N為符號化后的序列長度。

4分析討論

時間序列數(shù)據(jù)具有波動的特性，直接用歐氏距離度量相似性容易受細(xì)節(jié)波動影響，不能很好地從整體趨勢的角度度量相似性。動態(tài)時間彎曲雖然能很好地從整體趨勢度量相似性，但耗時太長。將這兩種度量方法分別用于SAX符號化后的時間序列能夠在保持度量準(zhǔn)確性的同時較好地降低時間復(fù)雜度。符號化的統(tǒng)計向量空間法SSVS正是利用了時間序列符號化后的特點，提取統(tǒng)計特征，并采用向量空間模型度量相似性。實驗結(jié)果表明這種方法能夠在減小的時間代價的同時提高度量準(zhǔn)確性。

在目前工作的基礎(chǔ)上，SSVS在特征提取方面還可以進行進一步的研究工作，如增加連續(xù)字符的長度進行特征統(tǒng)計以及對非連續(xù)字符的特征進行統(tǒng)計，以取得更好的度量準(zhǔn)確性。目前用于實驗的股票數(shù)據(jù)序列是等長的，未來還可以將SSVS應(yīng)用于非等長的時間序列數(shù)據(jù)研究其度量特點。

參考文獻：

[1]HAN Jiawei， KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，等譯.北京:機械工業(yè)出版社，2001.

[2]李斌，譚立湘，章勁松.面向數(shù)據(jù)挖掘的時間序列符號化方法研究[J].電路與系統(tǒng)學(xué)報，2000，5(2):9－14.

[3]ANDR J H， BADAL D. Using signature files for querying time－series data:proceedings of Principles of Data Mining and Knowledge Discovery，the 1st European Symposium Trondheim[C].Norway:[s.n.]，1997:211－220.

[4]LIN J， KEOGH E， LONARDI S， et al. A symbolic representation of time series， with implications for streaming algorithms:proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery[C].San Diego：[s.n.]，2003:2－11.

[5]李愛國，覃征，賀升平.時間序列數(shù)據(jù)的相似模式抽取[J].西安交通大學(xué)學(xué)報，2002，36(12):1275－1278.

[6]SALTON G， LESK M E. Computer evaluation of indexing and text processing[J].Journal of the ACM，1968，15(1):8－38.

[7]MARTIN G， DRAGOMIR A， PIOTR I， et al. Mining the stock market:which measure is best:proceedings of ACM SIGKDD Int. Confe－rence On Knowledge Discovery and Data Mining[C]. Boston:[s.n.]，2000:487－496.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”