基于時間序列模式表示的異常檢測算法

摘要：提出了一種基于時間序列的模式表示提取時間序列異常值的異常檢測算法（PREOV）。時間序列的模式表示本身就具有壓縮數據、保持時間序列基本形態的功能，并且具有一定的除噪能力。在時間序列模式表示的基礎上提取異常值，可以大大提高算法的效率和準確性，達到事半功倍的效果。在本算法中，還使用了一定的剪枝策略，使得算法的時間復雜度進一步降低。該算法計算簡單、實現方便、無須訓練，可以支持時間序列的動態增長。

關鍵詞：斜率；時間序列；模式表示；支持數；異常值

中圖分類號：TP391．41文獻標志碼：A

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

時間序列是指按照時間先后順序排列的各個觀測記錄的有序集合，廣泛存在于商業、經濟、醫療等領域。隨著時間的推移，時間序列通常包含大量的數據。對時間序列進行分析，可以揭示事物運動、變化和發展的內在規律，對于人們正確認識事物并據此作出科學的決策具有重要的現實意義。在對時間序列進行分析時，經常希望能夠發現這些時間序列在不同時間段的形態有何關聯關系。這種關聯關系一般表現為時間序列中頻繁出現的變化模式和極少出現的變化模式。這種極少出現的變化模式稱之為異常模式。在某些領域，異常模式的發現對人們來說往往更有價值。例如，醫院可以從病人的心電圖序列中發現異常模式從而進行診斷和治療。

目前為止，時間序列的異常檢測已廣泛應用到醫療、金融、入侵檢測以及可疑活動監控等領域。

1相關工作

近年來，異常檢測作為數據挖掘的一個分支，正受到越來越廣泛的關注。以往的很多研究都是基于無序數據集的，而時間序列的序列點之間又恰恰是有序的。因此很多異常檢測算法并不適用于時間序列。

時間序列的研究工作還不是很成熟，甚至到目前為止，對于時間序列的異常還沒有一個公認的定義。許多研究者在自己的研究過程中都提出了不同的時間序列異常定義，如新穎[1~4]、奇異[5，6]、變化點[7]、異常[8，9]、不正常的[10]等。

按照異常的表現形式不同，線性時間和空間上時間序列的異常主要可以分為點異常和模式異常兩種，它們都是用于發現一條時間序列上的異常情況的。本文主要研究的是模式異常。它是指在一條時間序列上與其他模式之間具有顯著差異的模式。事實上，點異常也可以認為是長度為1的模式異常。

本文提出了一種基于時間序列的模式表示提取時間序列異常值的異常檢測算法。由于時間序列的模式表示方法本身就具有刻畫時間序列的主要形態而忽略那些微小細節的特點。它可以對時間序列進行壓縮，換來更小的存儲和計算代價；可以只保留時間序列的主要形態，去除細節干擾，更能反映時間序列的自身特征。

2相關定義

定義1時間序列的模式表示。

時間序列的模式是指時間序列的某種變化特征，它可以是時間序列離散化后的符號，也可以是時間序列的傅里葉變換系數等。通過提取時間序列的模式，將時間序列變換到模式空間，就得到了時間序列的模式表示。

時間序列的模式表示方法有很多，主要有頻域表示、奇異值表示、符號化表示、分段線性表示等幾種。本文所討論的基于時間序列模式表示的異常檢測算法可以應用到所有的模式表示方法中。本文實驗所采用的是分段線性表示方法中的IEO表示（這是在筆者另外一篇論文“基于插值邊緣算子的時間序列模式表示”中提出的時間序列PLR方法）。

5結束語

由于時間序列的海量和復雜的數據特點，直接在時間序列上進行數據挖掘不但在儲存和計算上要花費高昂代價而且還可能會影響算法的準確性和可靠性。

本文提出了一種基于時間序列模式表示的異常檢測算法。該算法在時間序列模式表示方法的基礎上提取時間序列的異常值，提高了算法的效率和準確性，達到事半功倍的效果。本算法無須訓練，可以支持時間序列的動態增長。

參考文獻：

［1］DASGUPTA D，FORREST S. Novelty detection in time series data using ideas from immunology[C]//Proc of the 5th International Conferenceon Intelligent Systems.1996:82-87.

[2]MA J，PERKINS S. Timeseries novelty detection using oneclass support vector machines[C]//Proc of International Joint Conference on Neural Networks.2003.

[3]MA J，PERKINS S.Online novelty detection on temporal sequences[C]//Proc of International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2003:24-27.

[4]BORISYUK R，DENHAM M，HOPPENSTEADT F，et al.An oscillatory neural network model of sparse distributed memory and novelty detection [J].BioSystems，2000，58(1):265-272.

[5]SHAHABI C，TIAN X，ZHAO W.TSATree: a waveletbased approach to improve the efficiency of multilevel surprise and trend queries[C]//Proc of the 12th International Conference on Scientific and Statistical Database Management.Washington DC: IEEE Computer Society，2000:55-68.

[6]CHAKRABARTI S，SARAQWAGI S，DOM B.Mining surprising patterns using temporal description length[C]//Proc of the 24th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers，1998: 606-617.

[7]YAMANISHI K，TAKEUCHI J.A unifying framework for detecting outliers and change points from nonstationary time series data[C]//Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM Press，2002:676-681.

[8]WHITEHEAD B，HOYT W A.Function approximation approach to anomaly detection in propulsion system test data [J].Journal of Propulsion and Power，1995，11(5):10741076.

[9]DECOSTE D.Mining multivariate timeseries sensor data to discover behavior envelopes[C]//Proc of the 3rd Conference on Knowledge Discovery and Data Mining.[S.l.]:AAAI Press，1997:151154.

[10]JAGADISH H V，KOUDAS N，MUTHUKRISHNAN S.Mining deviants in a time series database[C]//Proc of the 25th International Conference on Very Large Data Bases.San Francisco: Morgan Kaufmann Publishers，1999:102113.

[11]KEOGH E，LONARDI S，CHIU W.Finding surprising patterns in a time series database in linear time and space[C]//Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2002:550-556.

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