張　玲，劉　波

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，北京 100094)

基于殘差統(tǒng)計(jì)的時(shí)間序列加性離群點(diǎn)檢測算法研究

張玲，劉波

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，北京 100094)

針對(duì)時(shí)間序列，提出了一種基于殘差統(tǒng)計(jì)的加性離群點(diǎn)檢測算法，利用AR模型對(duì)時(shí)間序列進(jìn)行前向與后向擬合；采用了數(shù)據(jù)相對(duì)變化率判別法減少離群點(diǎn)對(duì)擬合的影響；根據(jù)假設(shè)檢驗(yàn)原理，以高斯分布統(tǒng)計(jì)檢驗(yàn)對(duì)殘差進(jìn)行統(tǒng)計(jì)分析并最終確定離群點(diǎn)。仿真結(jié)果表明，該方法對(duì)離群點(diǎn)檢測有較高的準(zhǔn)確性。

時(shí)間序列；離群點(diǎn)；AR模型；高斯分布

0　引言

在時(shí)間序列數(shù)據(jù)挖掘中，不可避免地存在一些遠(yuǎn)離序列一般水平的極端大值和極端小值，或者與其他序列樣本點(diǎn)一般行為或特征不一致的點(diǎn)值，這些點(diǎn)被稱做離群點(diǎn)。離群點(diǎn)的產(chǎn)生可能是采樣中的誤差，也可能是被研究對(duì)象本身由于受各種偶然非正常的因素影響而引起的。一方面，離群點(diǎn)的存在會(huì)影響時(shí)間序列模式表示，可能使數(shù)據(jù)挖掘陷入混亂，導(dǎo)致在隨后的數(shù)據(jù)處理過程中產(chǎn)生偏差或誤導(dǎo)；另一方面，離群點(diǎn)可以提供一些潛在的重要信息。目前，時(shí)間序列離群點(diǎn)檢測作為對(duì)數(shù)據(jù)進(jìn)行挖掘處理的第一步，已經(jīng)成為該研究領(lǐng)域的重要方向之一，并廣泛應(yīng)用于通信流量監(jiān)測、工業(yè)故障診斷、金融貿(mào)易等方面。

時(shí)間序列中的離群點(diǎn)有很多類型，按照出現(xiàn)的個(gè)數(shù)，可以分為孤立離群點(diǎn)和成片離群點(diǎn)，按照產(chǎn)生的影響可以分為加性離群點(diǎn) AO(Additive Outlier)、更新離群點(diǎn) IO (Innovational Outlier)、水平移位離群點(diǎn)LS(Level Shift Outlier)和暫時(shí)變更離群點(diǎn) TC(Temporary Change Outlier)[1]。本文主要對(duì)時(shí)間序列中的加性離群點(diǎn)檢測方法進(jìn)行研究，并在此基礎(chǔ)上提出了一種基于殘差統(tǒng)計(jì)的檢測方法，仿真結(jié)果表明該方法在檢測加性離群點(diǎn)方面具有較好的性能。

1　離群點(diǎn)檢測方法研究

針對(duì)無序的數(shù)據(jù)集，離群點(diǎn)檢測方法主要有基于統(tǒng)計(jì)的方法、基于距離的方法[4]、基于密度的方法[5]和基于偏離的方法。近年來，不少研究人員提出了專門針對(duì)時(shí)間序列的離群點(diǎn)檢驗(yàn)算法，主要有統(tǒng)計(jì)診斷方法、貝葉斯方法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、小波檢測等。國內(nèi)也有相關(guān)人員對(duì)此做了深入的研究[2-5]。文獻(xiàn)[6]提出了基于粗糙集理論的序列離群點(diǎn)檢測方法，它利用粗糙集理論中的知識(shí)熵和屬性重要性等概念來構(gòu)建三種類型的序列，并通過分析序列中元素的變化情況來檢測離群點(diǎn)。文獻(xiàn)[7]通過建立多變量時(shí)間序列數(shù)據(jù)相似度矩陣，對(duì)相似度矩陣進(jìn)行轉(zhuǎn)換以最大化數(shù)據(jù)之間的相關(guān)性，并采用隨機(jī)游走模型計(jì)算數(shù)據(jù)點(diǎn)之間的連接系數(shù)來檢測數(shù)據(jù)點(diǎn)上的異常。文獻(xiàn)[8]指出離群點(diǎn)與它所在時(shí)間段內(nèi)的其他數(shù)據(jù)不具有相似性，從時(shí)序圖上看，離群點(diǎn)相對(duì)于它相鄰區(qū)域內(nèi)的數(shù)據(jù)具有很強(qiáng)的跳躍性，進(jìn)而提出基于數(shù)據(jù)相對(duì)變化率的時(shí)間序列離群點(diǎn)識(shí)別方法。

2　基于殘差統(tǒng)計(jì)的加性離群點(diǎn)檢測算法

2.1問題提出

對(duì)于時(shí)間序列，離群點(diǎn)可能會(huì)隱藏在時(shí)間序列的趨勢、季節(jié)或其他變化中，增加了檢測難度。以圖1所示的時(shí)間序列為例，兩個(gè)時(shí)間序列都處于上升趨勢，A點(diǎn)明顯偏離了整個(gè)趨勢，應(yīng)判定為離群點(diǎn)；B點(diǎn)雖然與前向時(shí)刻點(diǎn)在幅度變化率上發(fā)生了較大變化，但符合后向時(shí)刻點(diǎn)的變化趨勢，是一個(gè)正常時(shí)間序列點(diǎn)，因此不應(yīng)判定為離群點(diǎn)。

圖1　受加性離群點(diǎn)“干擾”的時(shí)間序列與正常時(shí)間序列

本文以一維時(shí)間序列為研究對(duì)象，提出了一種基于殘差統(tǒng)計(jì)的加性離群點(diǎn)檢測算法，基本思想是利用p階AR模型對(duì)時(shí)間序列進(jìn)行前向與后向擬合，得到每個(gè)時(shí)間點(diǎn)擬合殘差。采用了鄰域區(qū)間變化率判別法對(duì)離群點(diǎn)進(jìn)行初判，初判的疑似離群點(diǎn)不參與擬合運(yùn)算。最后根據(jù)高斯分布假設(shè)檢驗(yàn)的方法對(duì)殘差進(jìn)行統(tǒng)計(jì)分析并最終確定離群點(diǎn)。

定義待檢測時(shí)間序列數(shù)據(jù)樣本為 xt，t=1，2，3，4…M，xt∈R，并做如下假設(shè)：

(1)離群點(diǎn)隨機(jī)分布；

(2)正常數(shù)據(jù)的數(shù)量遠(yuǎn)大于離群點(diǎn)數(shù)量。

2.2算法描述

2.2.1鄰域區(qū)間變化率

定義1鄰域區(qū)間變化率：時(shí)間序列各時(shí)刻點(diǎn)與相鄰前后時(shí)刻的幅度變化率。設(shè)時(shí)刻t的鄰域區(qū)間變化率為δt，則：

對(duì)所有δt進(jìn)行考慮，選定門限δ，δ值的計(jì)算可以采用平均法或加權(quán)計(jì)算等。若 δt＞δ，則將 xt標(biāo)志為 LK點(diǎn)（疑似離群點(diǎn)），否則標(biāo)志為 uLK點(diǎn)（非疑似離群點(diǎn)）。

離群點(diǎn)相對(duì)于它前后相鄰數(shù)據(jù)都會(huì)有較大變化，因此鄰域區(qū)間變化率要同時(shí)對(duì)前向時(shí)刻和后向時(shí)刻進(jìn)行考慮。定義LK點(diǎn)和uLK點(diǎn)是為了在擬合過程中盡量減少離群點(diǎn)的影響，對(duì)疑似離群點(diǎn)不作擬合參考。

2.2.2AR模型擬合與參數(shù)計(jì)算

擬合常用的模型有AR模型、MA模型、ARIMA模型等。AR模型一般用于擬合平穩(wěn)的時(shí)間序列，而時(shí)間序列從局部來看近似一個(gè)平穩(wěn)的過程，并且AR模型結(jié)構(gòu)相對(duì)簡單，擬合精度較高，因此本文選用p階自回歸AR模型。為了準(zhǔn)確反應(yīng)各檢測點(diǎn)的局部變化屬性，并減少離群點(diǎn)對(duì)參數(shù)估計(jì)的影響，本文在文獻(xiàn)[9]所采用的兩窗口模型基礎(chǔ)上，提出了改進(jìn)的窗口計(jì)算模型，基本原理是：檢測窗口僅包含t時(shí)刻待檢測點(diǎn)，前向?qū)W習(xí)窗口和后向?qū)W習(xí)窗口位于檢測窗口鄰近兩側(cè)，寬度為N，并且N＞p，根據(jù)前向和后向?qū)W習(xí)窗口中的數(shù)據(jù)分別對(duì)t時(shí)刻待檢測點(diǎn)進(jìn)行前向和后向擬合，采用剪枝思想，若學(xué)習(xí)窗口中包含疑似離群點(diǎn)LK，則該點(diǎn)退出學(xué)習(xí)窗口不參與計(jì)算，其余時(shí)間軸上的uLK點(diǎn)向t時(shí)刻整體移位并填滿窗口。如圖2所示。

圖2　改進(jìn)的窗口模型

前向擬合得到 t時(shí)刻前向擬合殘差ε1t為：

后向擬合得到t時(shí)刻后向擬合殘差ε2t為：

其中 ε1t和 ε2t服從 N(0，σ2)，α=(α1，α2，…，αp)為前向自回歸系數(shù)，β=(β1，β2，…，βp)為后向自回歸系數(shù)。最后得到時(shí)刻t的擬合殘差：εt=ε1t+ε2t。

在計(jì)算殘差之前，首先要對(duì)自回歸系數(shù)進(jìn)行估計(jì)。AR模型的自回歸系數(shù)在預(yù)測誤差功率最小條件下滿足Yule－Walker方程[10]，以前向自回歸系數(shù)(α1，α2，…，αp)為例：

采用自相關(guān)法，根據(jù)t時(shí)刻前向窗口內(nèi)的觀測數(shù)據(jù)樣本 xt－1，xt－2，…，xt－N計(jì)算自相關(guān)函數(shù) rx(0)，rx(1)，…，rx(p)估計(jì)值，窗口外的計(jì)算樣本值假設(shè)為0，自相關(guān)函數(shù)計(jì)算如下：

上述線性方程的求解按如下形式：

后向自回歸系數(shù)(β1，β2，…，βp)的計(jì)算同上，其自相關(guān)函數(shù)計(jì)算為：

2.2.3高斯統(tǒng)計(jì)檢測

基于假設(shè)檢驗(yàn)理論，在一定的顯著性水平下，擬合殘差εt近似服從高斯分布，即 ε～N(u，σ2)。并且在假設(shè)2前提下，高斯分布作為殘差統(tǒng)計(jì)模型對(duì)離群點(diǎn)判決同樣具有較高置信度。在此，選擇高斯分布做為統(tǒng)計(jì)模型，εt的概率密度為：

計(jì)算時(shí)間序列每個(gè)樣本點(diǎn)的似然殘差概率分布f(εi)，選定一個(gè)顯著水平上的臨界值F，對(duì)xi是否為離群點(diǎn)做出決策：

3　仿真

為了驗(yàn)證本文所提算法的有效性，以局域網(wǎng)內(nèi)某主機(jī)通信流量監(jiān)測數(shù)據(jù)為對(duì)象進(jìn)行測試。通信流量監(jiān)測是網(wǎng)絡(luò)管理的重要內(nèi)容，通過流量監(jiān)測，可以全面透視網(wǎng)絡(luò)的流量控制，快速定位和發(fā)現(xiàn)網(wǎng)絡(luò)故障，并保障關(guān)鍵應(yīng)用的穩(wěn)定運(yùn)行，減少泄密風(fēng)險(xiǎn)。一般情況下，主機(jī)通信流量的具體業(yè)務(wù)包括 Web、Telnet、SNMP、請(qǐng)求應(yīng)答數(shù)據(jù)包等，在仿真實(shí)驗(yàn)中，通過隨機(jī)加入異常事件，比如網(wǎng)絡(luò)擁塞、數(shù)據(jù)分發(fā)等來模擬加性離群點(diǎn)。

圖3所示為某日上午 8:00－12:00的某主機(jī)通信流量監(jiān)測數(shù)據(jù)，單位為KB/min，數(shù)據(jù)樣本200個(gè)，離群點(diǎn) 5個(gè)。窗口寬度取15，模型階數(shù)取4，擬合殘差分布情況如圖4所示。由圖看出，擬合后，離群點(diǎn)的殘差值與正常的浮動(dòng)范圍相比有較大偏移。

圖3　加入AO的通信流量監(jiān)測數(shù)據(jù)

圖4　擬合殘差

為了驗(yàn)證算法對(duì)離群點(diǎn)數(shù)量的魯棒性，在200個(gè)流量監(jiān)測數(shù)據(jù)樣本點(diǎn)中分別隨機(jī)加入 5、10、15、20個(gè)離群點(diǎn)，擬合計(jì)算的窗口寬度取 15，模型階數(shù)取 4，概率判決臨界值分別取 0.95、0.95、0.9、0.9。在仿真測試中并未使用離群點(diǎn)數(shù)量先驗(yàn)知識(shí)。在此定義兩個(gè)檢測指標(biāo)：

檢出率：檢測出的真實(shí)離群點(diǎn)數(shù)量與實(shí)際離群點(diǎn)數(shù)量之比。

誤檢率：檢測出的錯(cuò)誤離群點(diǎn)數(shù)量與實(shí)際離群點(diǎn)數(shù)量之比。

檢測統(tǒng)計(jì)結(jié)果如表1所示。結(jié)果顯示，當(dāng)實(shí)際離群點(diǎn)數(shù)量在樣本中的比重小于0.05時(shí)，算法能對(duì)離群點(diǎn)進(jìn)行完全有效地檢測，當(dāng)實(shí)際離群點(diǎn)數(shù)量在樣本中的比重大于0.1時(shí)，檢出率下降，誤檢率有所上升，但此時(shí)離群點(diǎn)的發(fā)生不再是小概率事件，根據(jù)加性離群點(diǎn)對(duì)時(shí)間序列產(chǎn)生的影響上看，它不符合加性離群點(diǎn)特征。因此，本文所提算法對(duì)檢測時(shí)間序列中的加性離群點(diǎn)有較好的性能，同時(shí)，在實(shí)際應(yīng)用中證明該算法對(duì)其他類型離群點(diǎn)的檢測也有一定的魯棒性。

表1　不同離群點(diǎn)數(shù)量下算法有效性檢測

4　結(jié)論

本文針對(duì)時(shí)間序列中的加性離群點(diǎn)檢測，提出了一種基于殘差統(tǒng)計(jì)的檢測算法。該算法利用AR模型計(jì)算每個(gè)樣本點(diǎn)擬合殘差，通過統(tǒng)計(jì)分析殘差的概率分布來判別離群點(diǎn)。通過對(duì)局域網(wǎng)某主機(jī)通信流量監(jiān)測數(shù)據(jù)的仿真結(jié)果顯示，該算法在檢測加性離群點(diǎn)方面是有效的，結(jié)果有較高的置信度。此外，在對(duì)擬合殘差進(jìn)行分析時(shí)，除了本文采用的統(tǒng)計(jì)模型方法外，還可以采用基于密度的聚類的方法。另外如何檢測時(shí)間序列中其他類型的離群點(diǎn)也是值得研究的內(nèi)容。

[1]胡云，王崇駿，謝俊元，等.社群演化的隱健遷移估計(jì)及演化離群點(diǎn)檢測[J].軟件學(xué)報(bào)，2013，24(11)：2710－2720.

[2]Hu Tianming，Sung Sam Yuan.A trimmed mean approach to finding spatial outliers[J].Intelligent Data Analysis，2004，8(1)：79－95.

[3]ALARCON－AQUINO V，BARRIA J A.Anomaly detection in communication networks using wavelets[J].Communications，IEEE，2001，148(6)：355－362.

[4]劉耀宗，張宏，孟錦，等.基于小波密度估計(jì)的數(shù)據(jù)流離群點(diǎn)檢測[J].計(jì)算機(jī)工程，2013，39(2)：178－181.

[5]江峰，杜軍威，葛艷，等.基于粗糙集理論的序列離群點(diǎn)檢測[J].電子學(xué)報(bào)，2011(2)：345－350.

[6]李權(quán)，周興社.一種新的多變量時(shí)間序列數(shù)據(jù)異常檢測方法[J].時(shí)間頻率學(xué)報(bào)，2011，34(2)：154－158.

[7]周勇.時(shí)間序列時(shí)序關(guān)聯(lián)規(guī)則挖掘研究[D].成都：西南財(cái)經(jīng)大學(xué)，2008.

[8]蘇衛(wèi)星，朱云龍，胡琨元，等.基于模型的過程工業(yè)時(shí)間序列異常值檢測方法[J].儀器儀表學(xué)報(bào)，2012(9)：2080-2087.

[9]皇甫堪，陳建文，樓生強(qiáng).現(xiàn)代數(shù)字信號(hào)處理[M].北京：電子工業(yè)出版社，2003.

[10]薛安榮，鞠時(shí)光，何偉華，等.局部離群點(diǎn)挖掘算法研究[J].計(jì)算機(jī)學(xué)報(bào)，2007(8)：1455-1463.

張玲 (1976-)，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，高級(jí)工程師，博士生，主要研究方向：關(guān)聯(lián)規(guī)則挖掘。

劉波 (1982-)，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，工程師，主要研究方向：網(wǎng)絡(luò)入侵檢測。

Residuals statistics-based additive outlier detection algorithm for time series

Zhang Ling，Liu Bo
(China National Digital Switching System Engineering and Technological Research Center，Beijing 100094，China)

We propose a residuals statistics-based additive outlier detection algorithm for one-dimensional time series,The basic idea is using time series AR model for forward and backward fitting.In order to reduce the influence of outlier,we use data’s relative change rate to preliminary judge the outlier.According to hypothesis testing theory and Gauss distribution statistic testing, we find out the outliers.The simulation results show that the this method has good performance on outlier detection.

time series；outlier；AR model；Gauss distribution

TP311.11

A

10.16157/j.issn.0258-7998.2015.09.023

2014-03-21)

中文引用格式：張玲，劉波.基于殘差統(tǒng)計(jì)的時(shí)間序列加性離群點(diǎn)檢測算法研究[J].電子技術(shù)應(yīng)用，2015，41(9)：85-87，91.

英文引用格式：Zhang Ling，Liu Bo.Residuals statistics-based additive outlier detection algorithm for time series[J].Application of Electronic Technique，2015，41(9)：85-87，91.