基于集成預(yù)測的稀有時間序列檢測

.摘 要：為了解決誤判問題，從預(yù)測的角度給出了離群點的定義，并提出了預(yù)測可信度和離群度的概念；同時，提出采用置換技術(shù)來降低離群點對預(yù)測模型的影響，并提出了基于集成預(yù)測的稀有時間序列檢測算法。針對真實數(shù)據(jù)集的實驗表明，可信度和離群度的定義是合理的，稀有時間序列檢測算法是有效的。

關(guān)鍵詞：異常檢測；離群點；時間序列；神經(jīng)網(wǎng)絡(luò)集成

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

文章編號：1001-3695(2008)09-2620-03

Outlier detection in time series through neural networks forecasting

TAN Qi1，YANG Pei2

(1.School of Computer Science Engineering， South China Normal University， Guangzhou 510631， China;2.School of Computer Science， South China University of Technology， Guangzhou 510640， China)

Abstract:From the view of forecasting， a novel definition of outlier in time series was presented， as well as the definition of the forecasting confidence and the degree of outlier. The technique of permutation was proposed to alleviate the impact of outliers upon the forecasting model. To solve the 1 alarm problem， the forecastingbased outlier detection algorithm was presented. The experiments conducted on the realworld datasets show that definition of the degree of outlier is reasonable and the outlier detection algorithm is effective.

Key words:outlier detection; outlier; time series; neural network ensemble



0 引言

異常檢測的目標(biāo)是發(fā)現(xiàn)與大部分其他對象不同的對象。通常，異常對象被稱為離群點(outlier)。Hawkins對離群點的定義^[1]是：離群點是一個觀測值，它與其他觀測值的差別是如此之大，以至于懷疑它是由不同機制產(chǎn)生的。異常檢測是數(shù)據(jù)挖掘研究中一個活躍的分支，廣泛應(yīng)用于欺詐檢測、入侵檢測、生態(tài)系統(tǒng)失調(diào)、公共衛(wèi)生等領(lǐng)域。

異常檢測技術(shù)大體可以分為基于統(tǒng)計模型、鄰近度、密度、偏差等四類。對于時間序列，它的一個重要特點是具有時間屬性，是一種有序的數(shù)據(jù)。上述異常檢測算法大都是針對無序數(shù)據(jù)集的，并不完全適用于時間序列數(shù)據(jù)。而且，真實世界中時間序列數(shù)據(jù)受多重因素影響，使得時間序列具有一定的規(guī)律性、突發(fā)性和偶然性，這給時間序列的異常檢測帶來極大的挑戰(zhàn)性。

許多研究者都提出了不同的時間序列異常定義。與時間序列異常相關(guān)的術(shù)語包括新穎性^[2~5]、不規(guī)則^[6]、奇異^[7，8]、偏離^[9]、變化點^[10]和不一致^[11]等。

Dasgupta等人^[2]提出采用人工免疫系統(tǒng)的負選擇機制來檢測時間序列的新穎模式。文獻[3，4]提出基于支撐向量回歸（SVR）模型的算法，可以在線發(fā)現(xiàn)時態(tài)序列的新穎事件。采用SVR模型對歷史時間序列建立回歸模型，判斷新到來的序列點與SVR回歸模型的匹配程度，考察連續(xù)一段時間內(nèi)的匹配情況，給出其為新穎事件的置信度。Chakrabarti等人^[7]提出了利用TSAtree的改進型來實現(xiàn)奇異模式的查詢，他們把奇異模式定義為時間序列上的突然變化，通過小波系數(shù)的局部極大值來發(fā)現(xiàn)。但是，他們對異常模式的定義是建立在小波系數(shù)的基礎(chǔ)上，因此不夠準(zhǔn)確和全面，有些奇異模式無法發(fā)現(xiàn)^[8]。Keogh等人^[8]提出了奇異模式發(fā)現(xiàn)，他們提出了Tarzan算法，采用后綴樹來編碼所有出現(xiàn)的模式，用馬爾可夫模型預(yù)測未現(xiàn)模式的期望出現(xiàn)概率。Jagadish等人^[9]將時間序列上的異常描述為偏離點，偏離點是時間序列上那些與相鄰點具有顯著差異的序列點。Yamanishi等人^[10]采用AR模型對歷史時間序列數(shù)據(jù)建模，能夠動態(tài)適應(yīng)新的數(shù)據(jù)，漸漸遺忘歷史數(shù)據(jù)；給新到來的序列點與模型的偏差程度打分，分高的認為是高概率的異常。Keogh等人^[11]將時間序列中與其他序列最不相似的子序列稱為不一致序列，它只需要定義一個參數(shù)——子序列長度，采用啟發(fā)式搜索技術(shù)，在離散化的序列中尋找最不相似的子序列。Oliveira等人^[5]采用基于神經(jīng)網(wǎng)絡(luò)預(yù)測的技術(shù)來檢測時間序列的新穎模式，同時提出了置信度區(qū)間的概念，以有效定義異常檢測的閾值。但是該方法沒有解決潛在的誤判問題。

基于預(yù)測的異常檢測需要解決兩個關(guān)鍵問題：誤判和預(yù)測精度。在基于預(yù)測的異常檢測中，離群點會擾亂預(yù)測模型，導(dǎo)致正常對象被誤認為離群點或?qū)㈦x群點誤認為正常對象，發(fā)生誤判。為了解決誤判問題，本文從預(yù)測角度給出了離群點的定義，并提出了預(yù)測可信度和離群度的概念；同時，提出采用置換技術(shù)來降低離群點對預(yù)測模型的影響。在預(yù)測精度方面，筆者在前期研究中提出了一種基于變窗口的神經(jīng)網(wǎng)絡(luò)集成模型，該模型能有效降低系統(tǒng)的預(yù)測誤差。在此基礎(chǔ)上，進一步提出了基于變窗口集成預(yù)測模型的稀有序列檢測算法。

1 稀有序列檢測

神經(jīng)網(wǎng)絡(luò)集成之所以能夠應(yīng)用于異常檢測，在于神經(jīng)網(wǎng)絡(luò)能捕獲數(shù)據(jù)的基本分布規(guī)律，而異常序列并不符合基本規(guī)律。因此神經(jīng)網(wǎng)絡(luò)對其預(yù)測誤差很大。如果多個神經(jīng)網(wǎng)絡(luò)對同一部分數(shù)據(jù)樣本的預(yù)測誤差均很大，則可以初步判斷該部分數(shù)據(jù)樣本為異常序列。

1.1 基于集成預(yù)測的稀有序列檢測

時間序列預(yù)測可分為單步預(yù)測和多步預(yù)測。在單步預(yù)測中，預(yù)測模型輸出節(jié)點數(shù)為一個；而多步預(yù)測模型輸出節(jié)點數(shù)為多個。為簡便，以單步預(yù)測為例進行介紹，但是該方法可以很方便地推廣到多步預(yù)測模型中。

由式(6)可知，δi(x)=0表示第i個預(yù)測模型對樣本點x的預(yù)測誤差已經(jīng)遠遠偏離誤差的期望值。但是并不能根據(jù)δi(x)=0判斷x是離群點，因為x的多個輸入中可能包含離群點。離群點擾亂了預(yù)測模型，可能導(dǎo)致所謂的泥潭（spamming）和屏蔽（masking）問題。泥潭問題是指由于若干離群點的出現(xiàn)導(dǎo)致正常的對象被誤識別為離群點；而屏蔽問題是指由于若干離群點的出現(xiàn)導(dǎo)致離群點被誤識別為正常對象。為了解決誤判問題，本文提出了預(yù)測可信度的概念。

定義1 預(yù)測可信度。對于單個預(yù)測模型fi，給定樣本xw，其預(yù)測可信度表示為

下面從預(yù)測的角度給出時間序列的離群點定義。

定義2 離群點。在一個時間序列中，如果對某個樣本的預(yù)測是可信的，而且該預(yù)測誤差遠離預(yù)測誤差期望值，則認為該樣本是離群點。

以上只是給出了離群點的定性定義。為了提高可操作性，采用以下定量方式確定離群點。

則認為樣本xw是離群點。其中：β(0.5≤β≤1)為設(shè)定閾值。上式的直觀含義是：如果多數(shù)預(yù)測模型對樣本x的預(yù)測誤差均嚴重偏離誤差期望值，而且各個預(yù)測均是可信的，則可以判斷樣本x為離群點。

1.2 稀有時間序列檢測算法

如上所述，離群點的存在會擾亂預(yù)測模型，導(dǎo)致誤判發(fā)生，即將正常對象誤認為離群點或?qū)㈦x群點誤認為正常對象。為了盡可能地避免誤判發(fā)生，提出了置換的概念。

定義4 置換。如果樣本xw是離群點，x^w是預(yù)測模型對xw的預(yù)測值，即f

對離群點而言，預(yù)測值比真實值更符合大多數(shù)樣本的分布規(guī)律。因此，將離群點置換能有效地減少離群點對預(yù)測模型的干擾。

稀有時間序列檢測算法如下：

輸入：時間序列數(shù)據(jù)集D；

輸出：離群點集合Ω。

算法邏輯：

a)根據(jù)訓(xùn)練集構(gòu)建變窗口神經(jīng)網(wǎng)絡(luò)集成預(yù)測模型，并利用預(yù)測模型對測試集進行預(yù)測。

b)對每個預(yù)測模型，計算每個樣本的預(yù)測誤差，根據(jù)誤差計算正態(tài)分布的均值和方差。

c)計算每個樣本的離群度，確定離群點，并將離群點存入離群點集合Ω。

d)如果沒有檢測到離群點，則退出。

e)針對所有離群點執(zhí)行置換操作，將離群點的真實值以預(yù)測值代替。

f)利用預(yù)測模型重新對測試集進行預(yù)測，轉(zhuǎn)c)。

2 實驗分析

利用實際應(yīng)用系統(tǒng)中的數(shù)據(jù)集，對可信度和離群度定義的合理性及稀有時間序列檢測算法的有效性進行了驗證。數(shù)據(jù)集是廣東某小區(qū)從2006年4月到2007年3月共一年的每天最大忙時話務(wù)量數(shù)據(jù)。實驗在Weka數(shù)據(jù)挖掘平臺上進行，預(yù)測系統(tǒng)采用十折交叉驗證法進行評估。

部分預(yù)測結(jié)果如圖1、2所示。圖1是實際話務(wù)量和預(yù)測話務(wù)量，圖2是預(yù)測誤差。從圖2可以看出，前面大部分樣本的預(yù)測誤差都很小，但是在第28~34天（[28，34]）內(nèi)，預(yù)測誤差都很大，遠遠偏離誤差期望值。從圖1的曲線走勢來看，前面大部分樣本的預(yù)測序列和實際話務(wù)序列的步調(diào)基本一致，數(shù)據(jù)也比較接近，但是[28，34]內(nèi)每天的話務(wù)量與預(yù)測話務(wù)量相差很大。查看原始數(shù)據(jù)，發(fā)現(xiàn)[28，34]正好是國慶黃金周，從圖1的實際話務(wù)序列可以看出，該區(qū)間每天的話務(wù)量都比較低，數(shù)據(jù)分布曲線也與平常不一樣。而神經(jīng)網(wǎng)絡(luò)擬合的只是大部分數(shù)據(jù)的分布規(guī)律，對黃金周的預(yù)測誤差則比較大。因此可以將黃金周等異常序列從中篩選和分離出來。

圖2中的兩條曲線分別表示置換前后的預(yù)測誤差，可以看出，在執(zhí)行置換操作前，在第35~38天（[35，38]）的預(yù)測誤差都較大。可見離群點的存在使得預(yù)測模型對正常對象的預(yù)測誤差也較大，從而導(dǎo)致誤判發(fā)生；執(zhí)行置換操作后，[35，38]的預(yù)測誤差降到了合理的水平。而在第28天之前的點，由于沒有離群點的干擾，置換前后的預(yù)測誤差曲線是基本重合的。圖3曲線的凸起部分表示檢測到的稀有子序列[28，34]。

從圖1還可以看出，離群點并不一定是絕對值超過閾值的點，而是數(shù)據(jù)分布與常規(guī)數(shù)據(jù)分布不一致的點。常規(guī)的異常檢測往往是根據(jù)當(dāng)前的觀測值是否超出預(yù)先設(shè)定的閾值作出判定。顯然，單純依靠閾值來判斷并不能找出所有的異常點。

3 結(jié)束語

集成預(yù)測可以有效地應(yīng)用于稀有時間序列的檢測，但是需要解決誤判問題。針對誤判問題，本文提出了可信度和離群度的概念，并提出了稀有時間序列檢測算法。實驗表明，稀有時間序列檢測算法是有效的。在一個動態(tài)非線性時間序列中，可能存在多個稀有子序列，而且稀有子序列的類型可能互不相同，怎么在檢測的基礎(chǔ)上對這些稀有子序列進行有效的區(qū)分將是筆者下一步的研究目標(biāo)。

參考文獻：

［1］HAWKINS D M.Identification of outliers[M]//Monographs on applied probability and statistics.London:Chapman Hall，1980.

[2]DASGUPTA D，F(xiàn)ORREST S.Novelty detection in time series data using ideas from immunology[C]//Proc of the 5th International Conference on Intelligent Systems.1996:82-87.

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

[4]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.

[5]OLIVEIRA A L I，MEIRA S R L.Detecting novelties in time series through neural networks forecasting with robust confidence intervals[J].Neurocomputing，2006，70(1-3):79-92. 

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

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

[8]KEOGH E，LONARDI S，CHIU W.Finding surprising patterns in a time series databases 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.

[9]JAGADISH H V，KOUDAS N，MUTHUKRISHNAN S.Mining deviants in a time series databases[C]//Proc of the 25th International Conference on Very Large Databases. San Francisco: Morgan Kaufmann Publishers，1999:102113.

[10]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.

[11]KEOGH E，LIN J，F(xiàn)U A.HOT SAX:efficiently finding the most unusual time series subsequence[C]//Proc of the 5th IEEE International Conference on Data Mining.Washington DC：IEEE Computer Society，2005:226-233