新型時間序列相似性度量方法研究
2007-01-01 00:00:00劉懿鮑德沛楊澤紅趙雁南賈培發王家欽
計算機應用研究 2007年5期
摘要：基于時間序列符號化后的特點，創造性地提出了一種新型相似性度量方法——符號化的統計向量空間法(SAX[1] Statistical Vector Space，SSVS)。將這種度量方法用于SP500指數的股票數據聚類實驗，并與經典相似性度量方法比較，結果表明這種新的方法能夠高效地從整體趨勢的角度度量時間序列的相似性，有很好的實際意義和應用前景。
關鍵詞：時間序列； 相似性度量； 數據挖掘； 符號化
中圖分類號：TP391.41文獻標志碼：A
文章編號：1001－3695(2007)05－0112－03
近年來，隨著數據不斷豐富，人們對強有力的數據分析工具的需求增加，數據挖掘開始得到廣泛的應用[1]。例如對海量數據進行分析處理，挖掘其中蘊涵的各種信息，對于揭示事物發展的規律，發現不同的事物發展之間的相互關系等具有重要的實際意義。其中，時間序列數據會隨著時間的推移規模不斷擴大。因此針對時間序列數據的數據挖掘研究一直以來受到了學術界和工業界的廣泛重視，成為了一個具有重要理論和實際價值的熱點研究課題。
時間序列的相似性度量是衡量兩個時間序列的相似程度的方法；它是時間序列分類、聚類、異常發現等諸多數據挖掘問題的基礎，也是時間序列挖掘的核心問題之一。歐氏距離(Euclidean)和動態時間彎曲(Dynamic Time Warping)是用于時間序列相似性度量的兩種經典方法，但是這兩種方法在應用到實際的時間序列數據挖掘上都有其固有的缺陷。例如在研究股票價格時通常更加關注股票整體走勢，而股票細節處的波動性則是一種干擾因素。歐氏距離則易受股票價格序列波動的干擾；動態時間彎曲度量雖然能較好地克服歐氏距離度量這方面的不足，但其算法復雜度限制了其應用范圍。
時間序列近似表示是指將長度為n的時間序列近似表示為長度為N（N＜＜n）的序列。符號化表示[2，3]是近幾年提出的時間序列近似表示的方法之一，因其離散化、非實數表示的特點得到越來越多的關注。本文基于一種新型符號化方法SAX[4]，利用時間序列符號化后的字符序列特點，提出了一種新型相似性度量方法——符號化的統計向量空間法(SAX Statistical Vector Space，SSVS)。通過對比實驗研究表明，該方法能夠在減小時間代價的同時獲得較好的度量準確性。
1經典的相似性度量方法
歐氏距離和動態時間彎曲是兩種經典的相似性度量方法。
約定：在以下公式中出現的字符意義：
Q表示相似性度量的序列一
C表示相似性度量的序列二
qi表示Q序列在第i個點的取值
cj表示C序列在第j個點的取值
i，n分別表示當前點在整個序列的序號和整個序列的長度
d(qi，cj)表示Q序列的第i個點和C序列的第j個點之間的距離
歐氏距離計算公式如下:
從上式可以看出計算歐氏距離要求兩個序列等長，且兩個序列中的值必須是一一對應，每一對差值的權重相同。歐氏距離以其簡單實用被廣泛采用。
動態時間彎曲用于計算兩個時間序列之間的最大相似性，也即是求最小距離。這種計算方法是時間序列相似性度量所特有的，其計算公式如下:
（2）取兩個序列結束點的距離r(i， j)為兩個序列的DTW距離。
可以看到計算DTW距離的時間復雜度為O(n2)，遠高于計算歐氏距離的時間復雜度O(n)；但是DTW距離不要求兩個序列等長，且兩個序列求差值的點可以一對多或多對一。兩者的對比示意圖如圖1所示。
2符號化的統計向量空間法
符號化的統計向量空間法SSVS由三步組成：
(1)采用SAX對時間序列符號化，得到符號序列；
(2)對符號序列進行特征統計，得到對應的特征向量；
(3)計算兩個特征向量的余弦距離為對應的兩個時間序列的相似度。
2．1時間序列的符號化
Eammon在分段集成近似(PAA)基礎上提出了一種新型符號化方法(Symbolic Aggregate approXimation，SAX)。其基本思想是利用PAA對長度為n的時間序列降維，得到N維的時間序列，然后將降維后的序列值劃分為m個等概率的區間，并將處于同一個概率區間的序列值用同一個符號表示。其示意圖如圖2所示。
這種新型符號化方法SAX與其他符號化方法相比有以下的優點：
（1）簡單、易用且算法不依賴于具體實驗數據；
（2）在符號化的過程中實現了降維（N＜＜n），能有效解決對高維數據進行數據挖掘由于維數過高引起的問題；
（3）保證在符號空間計算出的兩個符號序列的距離滿足實際兩個時間序列的距離下界的要求，即不會出現漏報[5]。
2．2相似性度量
由于符號化后的時間序列是由離散、有限的字符組成，可以作為字符串進行進一步的分析處理。基于對文本進行相似性度量的向量空間模型[6]和時間序列度量的特點，本文設計了三類統計特征：
（1）統計字符集中單個字符在字符串中出現的頻率。這類特征數目為字符集的大小m，單個特征權值為1；
（2）統計字符串中所有兩個連續字符的三種大小關系（前＜后，前=后，前＞后）在字符串中出現的頻率，這類特征數目為3，單個特征權值為2；
（3）統計字符串中所有三個連續字符的五種大小關系（用兩個相鄰字符的關系表示為==， >>， <<， <>， ><）在字符串中出現的頻率，這類特征數目為5，單個特征權值為3。
三類統計特征組成了字符序列的特征向量T=t1，…，ts，s=m+8。將向量作歸一化處理，兩個時間序列的相似度可以通過計算特征向量之間的距離來度量。采用余弦距離計算如下：
3實驗框架
前面給出了兩種度量時間序列相似性的經典方法，并詳細闡述了基于SAX的新型相似性度量方法——符號化的統計向量空間法SSVS。為了對所提出的SSVS進行深入研究，本文結合經典的度量方法，設計了五種實驗方案對比研究各種相似性度量方法在時間序列數據聚類中的特點。方案一：基于原時間序列，采用歐氏距離度量序列的相似性；方案二：采用SAX對原時間序列符號化后，用歐氏距離度量序列的相似性；方案三：基于原時間序列，用動態時間彎曲度量序列的相似性；方案四：采用SAX對原時間序列符號化后，用動態時間彎曲度量序列的相似性；方案五：采用符號化的統計向量空間法SSVS度量序列的相似性。
3．1實驗數據
實驗數據采用標準普爾500指數股票（Standard and Poor 500 index，縮寫SP500， http://kumo.swcp.com/stocks/）的歷史交易數據。該數據集在各種數據挖掘的研究文獻中作為實驗數據。
本文抽取了八支股票連續2 048個交易日的收盤價格為實驗數據，對實際的股票數據進行了正規化的預處理[7]：
3．3實驗結果
基于前文的實驗數據和評價標準，將五種方案用于聚類實驗，實驗結果如表1所示。其中n為原時間序列長度，N為符號化后的序列長度。
4分析討論
時間序列數據具有波動的特性，直接用歐氏距離度量相似性容易受細節波動影響，不能很好地從整體趨勢的角度度量相似性。動態時間彎曲雖然能很好地從整體趨勢度量相似性，但耗時太長。將這兩種度量方法分別用于SAX符號化后的時間序列能夠在保持度量準確性的同時較好地降低時間復雜度。符號化的統計向量空間法SSVS正是利用了時間序列符號化后的特點，提取統計特征，并采用向量空間模型度量相似性。實驗結果表明這種方法能夠在減小的時間代價的同時提高度量準確性。
在目前工作的基礎上，SSVS在特征提取方面還可以進行進一步的研究工作，如增加連續字符的長度進行特征統計以及對非連續字符的特征進行統計，以取得更好的度量準確性。目前用于實驗的股票數據序列是等長的，未來還可以將SSVS應用于非等長的時間序列數據研究其度量特點。
參考文獻：
[1]HAN Jiawei， KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，等譯.北京:機械工業出版社，2001.
[2]李斌，譚立湘，章勁松.面向數據挖掘的時間序列符號化方法研究[J].電路與系統學報，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]李愛國，覃征，賀升平.時間序列數據的相似模式抽取[J].西安交通大學學報，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.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
