時間序列數據挖掘綜述

摘要：在綜合分析近年來時間序列數據挖掘相關文獻的基礎上，討論了時間序列數據挖掘的最新進展，對各種學術觀點進行了比較歸類，并預測了其發展趨勢。內容涵蓋了時間序列數據變換、相似性搜索、預測、分類、聚類、分割、可視化等方面，為研究者了解最新的時間序列數據挖掘研究動態、新技術及發展趨勢提供了參考。

關鍵詞：時間序列； 數據挖掘； 相似性搜索； 模式發現

中圖分類號：TP311.13文獻標志碼：A

文章編號：1001-3695(2007)11-0015-04

數據挖掘是知識發現過程中的一個步驟。它主要是利用某些特定的知識發現算法，在一定的運算效率限制下，從數據中挖掘出有價值的知識[1]。原則上講，數據挖掘可以應用于任何類型的信息源。這包括關系數據庫、數據倉庫、事務數據庫、其他高級數據庫系統、平面文件（flat files）和WWW上的數據[2]。在這些數據集之中，有一類數據集的數據之間存在著時間上的關系，這類數據被稱為時間序列。在對時間序列進行數據挖掘的過程中，必須考慮數據集之中數據間存在的時間關系，這類數據挖掘稱為時間序列數據挖掘（time series data mi￣ning，TSDM）。Keogh[1]認為時間序列是普遍存在的，圖像數據、文本數據、影像數據、手寫體數據、腦掃描數據等都可看做是時間序列。研究如何有效地從這些復雜的海量時間序列中挖掘潛在的有用知識，具有重要的理論價值和現實意義。因此TSDM已成為數據挖掘研究的一個重要分支。

對時間序列進行聚類的算法有基于相似性（或距離）[35]、基于特征[36，37]、基于模型[38]和基于分割的聚類分析[7，39]。其中，在基于相似性的方法中，一種常用的距離度量是歐氏距離或者在此基礎上的一些改進作為相似性測度。由于歐氏距離測度針對的是確定性向量空間，而時間序列的長度通常是變化的、對時間變化敏感，并且不能高效地表示為有限維空間的一個點。傳統的聚類分析大多是基于向量的，它們不能很好地解決時間序列聚類問題。近年來對時間序列的聚類研究更多地使用基于模型的聚類分析，如基于HMM的時間序列聚類[40]。近年來，時間序列數據挖掘中的聚類技術發展很快，取得了很多研究成果。

時間序列分類就是給定一個未知類別的時間序列，將其劃分到某些預定義的類別之中。許多分類算法在時間序列中都有應用，如決策樹、神經網絡、貝葉斯分類器等。近年來用分類器融合對時間序列進行分類成為了一個熱門研究方向。

2．4時間序列數據可視化

時間序列可視化挖掘是TSDM一個較新的研究領域，也是一個有廣闊應用前景的研究領域。所謂時間序列數據可視化挖掘就是利用圖形圖像技術、虛擬現實技術以及數據挖掘技術，將復雜的時間序列以人們易于理解的、直觀的和圖形化的方式呈現出來。時間序列可視化是一個應用前景廣闊的研究方向[41~44]。目前國外研究較多，也開發出了相應的可視化工具，如time series spirals、theme river、time searcher、vizTree、time series bitmaps等。國內這方面的研究成果較少。

2．5時間序列分割與模式發現

模式發現是TSDM的重要研究內容之一，并出現了大量的研究成果。針對不同的應用目的，人們試圖從時間序列數據庫中發現的模式也各不相同，如特定模式、頻繁模式、周期模式、感興趣模式、驚奇模式、異常模式、例外模式等。為了從一個時間序列中抽取模式，需要某種算法將一個長時間序列分割為若干個相對短的子序列，以便對這些子序列進行聚類/分類分析[45，46]、檢測時間序列中的變化點[47]、對分割后的時間序列建立動態模型[48，49]。

時間序列分割主要有兩個應用：系統模型變化檢測，即當產生時間序列的系統的模型（或參數）發生變化時，應用分割算法可以檢測到這種變化是何時發生的；應用分割算法創建時間序列的高級數據表示，以便對時間序列進行索引、聚類和分類[1]。因此，研究時間序列分割算法具有重要的理論價值和現實意義，并已成為時間序列數據挖掘研究的主要研究內容之一。

2．6時間序列預測

時間序列預測一直是眾多科學領域感興趣的問題。由于研究對象的高度一致性，TSDM研究中關心的時間序列預測問題與時間序列分析理論中關心的時間序列預測問題在許多方面是相同的。時間序列預測根據時間序列型數據，由歷史的和當前的數據推測未來的數據，也可以認為是以時間為關鍵屬性的關聯知識。時間序列預測技術大體可分為：

a）傳統的線性時間序列預測技術。1968年Box和Jenkins提出了一套比較完善的時間序列建模理論和分析方法。這些經典的數學方法通過建立隨機模型，如自回歸模型、自回歸滑動平均模型、求和自回歸滑動平均模型和季節調整模型等進行時間序列的預測。

b）非線性時間序列預測技術。這類方法主要采用嵌入空間法或神經網絡等方法，特別是混沌時間序列預測[50]和基于神經網絡的時間序列預測[51，52]。

混沌時間序列預測是建立在Takens[53]提出的嵌入定理和相空間重構理論基礎上的。其目的是試圖在高維相空間中恢復混沌吸引子。時間序列預測的神經網絡模型包括模糊神經網絡、徑向基函數（RBF）網絡、小波神經網絡以及積單元神經網絡等。

c）其他技術，如滑動窗口二次自回歸模型[7]、基于云模型的時間序列預測[54]等。

2．7TSDM應用研究

時間序列數據廣泛存在于現實世界的各個領域，因此TSDM的應用十分廣泛。典型的應用包括股票預測、機電系統診斷、醫學診斷、生物信息學、營銷指導、運動圖像分析、生產過程監測等。

在每一篇時間序列數據挖掘論文中都給出了實際應用，但其中許多文章介紹的思想到底能不能用于實際令人懷疑。研究者應將更多的注意力放在那些真實的、有實際價值的應用上。

3未來的研究方向

下面羅列出時間序列挖掘研究中尚待解決的問題及未來的研究方向，雖不能概括所有的尚待解決的問題及方向，但可供研究者們參考。它們是：

a）海量時間序列數據查詢。

傳統的時間序列數據庫通常按照數據來源或時間關系進行索引。這樣的索引結構在基于相似查詢場合，其效率極其低下，特別是對海量時間序列數據庫更是不可行的。因此需要建立針對海量時間序列數據的索引結構，以便在其之上對海量數據作相似性查詢，從而獲得較高的查詢效率。

b）主題發現。

與相似性搜索相比，主題發現（motif disco￣very）有更廣的應用性。但現有的主題發現算法往往得到太多的無意義的主題，因此如果能夠給出評價主題的規則，讓系統在眾多主題中自動不遺漏地提取更有意義的主題是筆者進一步研究的目標。

c）聚類時間序列流。

在進行時間序列聚類時，一般先將時間序列分割成子序列，然后對子序列進行聚類。這樣有可能意義不大。能不能直接在時間序列流上進行更有意義的聚類是今后時間序列聚類研究的一個方向。

d）有效的時間序列分類算法。

目前有很多時間序列分類算法，如決策樹、神經網絡、貝葉斯分類器等，但所有的這些方法都不如基于DTW的1鄰近算法。DTW是很有效的線性方法，然而1鄰近需要訪問每個屬性，效率很低。因此研究更有效的時間序列分類算法是亟待解決的問題。

e）海量時間序列可視化。

最好的數據挖掘和模式識別工具就是人的眼睛。那么能不能將海量的時間序列中隱含的知識，如規則、孤立點、異常事例等，以人們易于理解的方式可視化，是人們普遍關心的問題。

f）多時間粒度的數據挖掘與知識發現。

在不同時間尺度研究系統或現象的行為，有助于加深人們對該系統或現象的認識。因此，多時間粒度的數據挖掘與知識發現是目前研究的熱點問題。

g）新的TSDM算法。

在相似性搜索時，給定兩個時間序列，如果事先不將子序列標準化，找到所有相似的子序列是很容易的，但這是沒有意義的。問題在于不是追求速度，而是以何種方式搜索相似更有意義。

在進行分類聚類時，有時結果意義不大甚至是無意義的。給定兩個聚類（或分類）在一起的時間序列，如果能自動構建對為什么把它們放在一起的解釋那將會更有意義。

因此，研究新的TSDM算法以更有意義的方式進行挖掘，是研究者們致力解決的問題。

參考文獻：

[1]KEOGH E. Data mining and machine learning in time series database[C]//Proc of the 5th Industrial Conference on Data Mining (ICDM). Leipzig:[s.n.]，2005.

[2]HAN Jia－wei， KAMBER M.Data mining: concepts and techniques[M].New York:Morgan Kaufmann Publishers，2000:7-9.

[3]LIN Wei－qiang， ORGUN M A， WILLIAMS G J. An overview of temporal data mining[C]//Proc of the 1st Australian Data Mining Workshop.Canberra:University of Technology.2002:83-90.

[4]KEOGH E， KASETTY S. On the need for time series data mining benchmarks: a survey and empirical demonstration[C]//Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press， 2002:102－111.

[5]HETLAND M L. A survey of recent methods for efficient retrieval of similar time sequences[EB/OL].(2001). http://citeseer.nj.nec.com/hetland01survey.html.

[6]HOPPNER K. Time series abstraction methods:a survey[C]//Proc of GI Jahrestagung Informatik，Workshop on Knowledge Discovery in Databases. Dortmund:[s.n.]，2002:777-786.

[7]李愛國.時間序列數據分割與時態模式挖掘研究[D].西安：西安交通大學，2003：2-4.

[8]LAXMAN S， SASTRY P S.A survey of temporal data mining[J].Sādhanā Academy Proceedings in Engineering Sciences，2006，31(2):173－198.

[9]AGRAWAL R， FALOUTSOS C， SWAMI A. Efficient similarity search in sequence databases[C]//Proc of the 4th International Conference on Foundations of Data Organization and Algorithms.London:Springer－Verlag，1993:69-84.

[10]FALOUTSOS C， RANGANATHAN M， MANOLOPOULOS Y. Fast subsequence matching in time－series databases[C]//Proc of the ACM SIGMOD International Conference on Management of Data.Mineapolis:ACM Press，1994:419-429.

[11]RAFIEI D， MENDELZON A O. Querying time series data based on similarity[J]. IEEE Trans on Knowledge and Data Engineering， 2000，12(5):675-693.

[12]WANG Chang－zhou， WANG Xiao－yang. Multilevel filtering for high dimensional nearest neighbor search[C]//Proc of ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Disco￣very. Dallas:ACM Press，2000:37-43.

[13]HUHTALA Y， KRKKINEN J， TOIVONEN H. Mining for simila￣rities in aligned time series using wavelets[C]//Proc of Data Mining and Knowledge Discovery: Theory， Tools， and Technology. Orlando:[s.n.]，1999:150-160.

[14]STRUZIK Z R， SIEBES A. Measuring time series’ similarity through large singular features revealed with wavelet transformation[C]//Proc of the International Workshop on Database and Expert Systems Application. Florence: IEEE Computer Society Press，1999:162-166.

[15]POPIVANOV I， MILLER R J. Similarity search over time－series data using wavelets[C]//Proc of the 18th International Conference on Data Engineering.San Jose:IEEE Computer Society Press，2002:212-221.

[16]張海勤，蔡慶生.基于小波變換的時間序列相似模式匹配[J].計算機學報，2003，26(3)：373-377.

[17]AGRAWAL R， LIN K I， SAWHNEY H S， et al. Fast similarity search in the presence of noise，scaling，and translation in time－series databases[C]//Proc of the 21st Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann，1995:490-501.

[18]KEOGH E. Exact indexing of dynamic time warping[C]//Proc of the 28th International Conference on Very Large Databases. Hong Kong:Morgan Kaufmann，2002:406-417.

[19]RATH T M， MANMATHA R. Lower－bounding of dynamic time warping distances for multivariate time series， Technical Report MM－40[R].Amherst:Center for Intelligent Information Retrieval Technical Report， University of Massachusetts，2003.

[20]CHIU S， KEOGH E， HART D， PAZZANI M. Iterative deepening dynamic time warping for time series[C]//Proc of the 2nd SIAM International Conference on Data Mining. Baltimore:SIAM Press，2002:148-156.

[21]KEOGH E， PAZZANI M J.Derivative dynamic time warping[C]//Proc of the 1st SIAM International Conference on Data Mining. Chicago: SIAM Press，2001:209-211.

[22]KEOGH E， CHAKRABARTI K， PAZZANI M， et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Journal of Knowledge and Information Systems， 2001，3(3):263-286.

[23]KEOGH E， CHAKRABARTI K， PAZZANI M. et al. Locally adaptive dimensionality reduction for indexing large time series databases[J].ACM Transactions on Database Systems， 2002，27(2):188－228.

[24]GE X， SMYTH P. Deformable markov model templates for time－series pattern matching[C]//Proc of the 6th ACM SIGKDD Int’l Confere￣nce on Knowledge Discovery and Data Mining.Boston:ACM Press，2000:81－90.

[25]FERHATOSMANOGLU H， TUNCEL E， AGRAWAL D， et al. Approximate nearest neighbor searching in multimedia databases[C]//Proc of the 17th IEEE Int’l Conference on Data Engineering.Heidelberg:IEEE Computer Society Press，2001:503－511.

[26]KAHVECI T， SINGH A， GUREL A. An efficient index structure for shift and scale invariant search of multi－attribute time sequences[C]//Proc of the 18th Int’l Conference on Data Engineering.San Jose:IEEE Computer Society Press，2002.

[27]LOH W， KIM S， WHANG K.Index interpolation: an approach to subsequence matching supporting normalization transform in time－series databases[C]//Proc of the 9th ACM CIKM Int’l Conference on Information and Knowledge Management. McLean:ACM Press，2000:480-487.

[28]WU Y， AGRAWAL D， ABBADI A E. A comparison of DFT and DWT based similarity search in time－series databases[C]//Proc of the 9th ACM CIKM Int’l Conference on Information and Knowledge Management.McLean:ACM Press，2000:488-495.

[29]CARA－VALENTE J P， LOPEZ－CHAVARRIAS I. Discovering similar patterns in time series[C]//Proc of the 6th ACM SIGKDD Int’l Conference on Knowledge Discovery and Data Mining. Boston:ACM Press，2000:497-505.

[30]SHIM K， SRIKANG R， AGRAWAL R. High－dimensional similarity joins[J]. IEEE Trans on Knowledge and Data Engineering，2002，14(1):156－171.

[31]KIM S， PARK S， CHU W. An index－based approach for similarity search supporting time warping in large sequence databases[C]//Proc of the 17th International Conference on Data Engineering.Heidelberg:IEEE Press，2001:607-614.

[32]BECKMANN N， KRIEGEL H P， SCHNEIDER R， et al. The R*－tree: an efficient and robust access method for points and rectangles[C]//Proc of ACM SIGMOD International Conference on Management of Data. Atlantic:ACM Press，1990:322-331.

[33]TAO Y， PAPADIAS D， SUN J. The TPR*－tree: an optimized spatio－temporal access method for predictive queries[C]//Proc of the 29th VLDB Conference.Berlin:Morgan Kaufmann Publishers，2003:790-801.

[34]TAO Y， PAPADIAS D. MN3R－tree: a spatio－temporal access method for timestamp and interval queries[C]//Proc of the 27th VLDB Conference.Roma:Morgan Kaufmann Publishers，2001:431-440.

[35]KALPAKIS K， GADA D， Puttagunta V. Distance measures for effective clustering of ARIMA time－series[C]//Proc of the IEEE International Conference on Data Mining. San Jose: IEEE Computer Society Press，2001:273-280.

[36]MRCHEN F.Time series feature extraction for data mining using DWT and DFT[EB/OL].(2003－11-05). http://www.mybytes.de/papers/moerchen03time.pdf.

[37]ZHANG Hui， HO Tu－bao， LIN Mao－song. A non－parametric wavelet feature extractor for time－series classification[C]//Proc of the 8th Pacific－Asia Conf Knowledge Discovery and Data Mining.Berlin:Sprin￣ger，2004:595-603.

[38]VAITHYANATHAN S， DOM B. Model－based hierarchical clustering[C]//Proc of the 16th Conference Uncertainty in Artificial Intelligence.Stanford，California:Morgan Kaufmann， 2000:599-608.

[39]KEOGH E， CHU S， HART D， et al. An on－line algorithm for segmenting time series[C]//Proc of the IEEE Int’l Conference on Data Mining.San Jose:IEEE Computer Science Press，2001:289-296.

[40]段江嬌， 薛永生， 林子雨，等.一種新的基于隱Markov模型的分層時間序列聚類算法[J].計算機研究與發展，2006，43(1):61-67.

[41]YU J， HUNTER J， REITER E， et al. Recognising visual patterns to communicate gas turbine time－series data[C]//Applications and Innovations in Intelligent Systems. London:Springer，2002:105－118.

[42]HOCHHEISER H， SHNEIDERMAN B. Visual queries for finding patterns in time series data[R]. Maryland: University of Maryland， 2002.

[43]HOCHHEISER H， SHNEIDERMAN B. Visual specification of queries for finding patterns in time series data[D]. Maryland: University of Maryland， 2001.

[44]HOCHHEISER H. Interactive graphical querying of time series and linear sequence data sets[D].Maryland:University of Maryland， 2003.

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

[46]覃征，李愛國.時間序列數據的穩健最優分割[J].西安交通大學學報，2003，37(4):338-342.

[47]SRIPADA S G， REITER E， HUNTER J， et al. Segmenting time series for weather forecasting[C]//Proc of ES. 2002.

[48]HANLON B， FORBES C. Model selection criteria for segmented time series from a bayesian approach to information compression[R].[S.l.]:Monash University，2002.

[49]HAWKINS D M. Fitting multiple change－point models to data[J]. Computational Statistic Data Analysis，2001，37(3): 323-341.

[50]劉涵，劉丁，李琦. 基于支持向量機的混沌時間序列非線性預測[J].系統工程理論與實踐，2005，25(9):94－99.

[51]張志華，鄭南寧，鄭海兵.徑向基函數神經網絡（RBF）的一種極大熵學習算法[J].計算機學報，2001，24(5):474-479.

[52]陳哲，馮天瑾，張海燕.基于小波神經網絡的混沌時間序列分析與相空間重構[J].計算機研究與發展，2001，38(5):591-596.

[53]TAKENS F. Detecting strange attractors in turbulence[C]//RAND D， YOUNG L S. Dynamical systems and turbulence， lecture notes in mathematics. New York :Springer－Verlag， 1981:336-381.

[54]蔣嶸，李德毅.基于形態表示的時間序列相似性搜索[J].計算機研究與發展，2000，37(5):601-608.

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