基于時(shí)間序列模式表示的異常檢測(cè)算法

摘要：提出了一種基于時(shí)間序列的模式表示提取時(shí)間序列異常值的異常檢測(cè)算法（PREOV）。時(shí)間序列的模式表示本身就具有壓縮數(shù)據(jù)、保持時(shí)間序列基本形態(tài)的功能，并且具有一定的除噪能力。在時(shí)間序列模式表示的基礎(chǔ)上提取異常值，可以大大提高算法的效率和準(zhǔn)確性，達(dá)到事半功倍的效果。在本算法中，還使用了一定的剪枝策略，使得算法的時(shí)間復(fù)雜度進(jìn)一步降低。該算法計(jì)算簡(jiǎn)單、實(shí)現(xiàn)方便、無(wú)須訓(xùn)練，可以支持時(shí)間序列的動(dòng)態(tài)增長(zhǎng)。

關(guān)鍵詞：斜率；時(shí)間序列；模式表示；支持?jǐn)?shù)；異常值

中圖分類號(hào)：TP391．41文獻(xiàn)標(biāo)志碼：A

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

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

目前為止，時(shí)間序列的異常檢測(cè)已廣泛應(yīng)用到醫(yī)療、金融、入侵檢測(cè)以及可疑活動(dòng)監(jiān)控等領(lǐng)域。

1相關(guān)工作

近年來(lái)，異常檢測(cè)作為數(shù)據(jù)挖掘的一個(gè)分支，正受到越來(lái)越廣泛的關(guān)注。以往的很多研究都是基于無(wú)序數(shù)據(jù)集的，而時(shí)間序列的序列點(diǎn)之間又恰恰是有序的。因此很多異常檢測(cè)算法并不適用于時(shí)間序列。

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

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

本文提出了一種基于時(shí)間序列的模式表示提取時(shí)間序列異常值的異常檢測(cè)算法。由于時(shí)間序列的模式表示方法本身就具有刻畫(huà)時(shí)間序列的主要形態(tài)而忽略那些微小細(xì)節(jié)的特點(diǎn)。它可以對(duì)時(shí)間序列進(jìn)行壓縮，換來(lái)更小的存儲(chǔ)和計(jì)算代價(jià)；可以只保留時(shí)間序列的主要形態(tài)，去除細(xì)節(jié)干擾，更能反映時(shí)間序列的自身特征。

2相關(guān)定義

定義1時(shí)間序列的模式表示。

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

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

5結(jié)束語(yǔ)

由于時(shí)間序列的海量和復(fù)雜的數(shù)據(jù)特點(diǎn)，直接在時(shí)間序列上進(jìn)行數(shù)據(jù)挖掘不但在儲(chǔ)存和計(jì)算上要花費(fèi)高昂代價(jià)而且還可能會(huì)影響算法的準(zhǔn)確性和可靠性。

本文提出了一種基于時(shí)間序列模式表示的異常檢測(cè)算法。該算法在時(shí)間序列模式表示方法的基礎(chǔ)上提取時(shí)間序列的異常值，提高了算法的效率和準(zhǔn)確性，達(dá)到事半功倍的效果。本算法無(wú)須訓(xùn)練，可以支持時(shí)間序列的動(dòng)態(tài)增長(zhǎng)。

參考文獻(xiàn)：

［1］DASGUPTA D，F(xiàn)ORREST 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.

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