基于集成預測的稀有時間序列檢測

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

關鍵詞：異常檢測；離群點；時間序列；神經網絡集成

中圖分類號：TP311 文獻標志碼：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 引言

異常檢測的目標是發現與大部分其他對象不同的對象。通常，異常對象被稱為離群點(outlier)。Hawkins對離群點的定義^[1]是：離群點是一個觀測值，它與其他觀測值的差別是如此之大，以至于懷疑它是由不同機制產生的。異常檢測是數據挖掘研究中一個活躍的分支，廣泛應用于欺詐檢測、入侵檢測、生態系統失調、公共衛生等領域。

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

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

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

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

1 稀有序列檢測

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

1.1 基于集成預測的稀有序列檢測

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

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

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

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

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

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

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

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

如上所述，離群點的存在會擾亂預測模型，導致誤判發生，即將正常對象誤認為離群點或將離群點誤認為正常對象。為了盡可能地避免誤判發生，提出了置換的概念。

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

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

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

輸入：時間序列數據集D；

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

算法邏輯：

a)根據訓練集構建變窗口神經網絡集成預測模型，并利用預測模型對測試集進行預測。

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

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

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

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

f)利用預測模型重新對測試集進行預測，轉c)。

2 實驗分析

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

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

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

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

3 結束語

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

參考文獻：

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

[2]DASGUPTA D，FORREST 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，FU 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