0 引言
    在時(shí)間序列數(shù)據(jù)挖掘中,，不可避免地存在一些遠(yuǎn)離序列一般水平的極端大值和極端小值，或者與其他序列樣本點(diǎn)一般行為或特征不一致的點(diǎn)值,，這些點(diǎn)被稱(chēng)做離群點(diǎn),。離群點(diǎn)的產(chǎn)生可能是采樣中的誤差，也可能是被研究對(duì)象本身由于受各種偶然非正常的因素影響而引起的,。一方面,，離群點(diǎn)的存在會(huì)影響時(shí)間序列模式表示,，可能使數(shù)據(jù)挖掘陷入混亂，導(dǎo)致在隨后的數(shù)據(jù)處理過(guò)程中產(chǎn)生偏差或誤導(dǎo),；另一方面,，離群點(diǎn)可以提供一些潛在的重要信息。目前,，時(shí)間序列離群點(diǎn)檢測(cè)作為對(duì)數(shù)據(jù)進(jìn)行挖掘處理的第一步,，已經(jīng)成為該研究領(lǐng)域的重要方向之一，并廣泛應(yīng)用于通信流量監(jiān)測(cè),、工業(yè)故障診斷,、金融貿(mào)易等方面。
    時(shí)間序列中的離群點(diǎn)有很多類(lèi)型,，按照出現(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)檢測(cè)方法進(jìn)行研究,，并在此基礎(chǔ)上提出了一種基于殘差統(tǒng)計(jì)的檢測(cè)方法，仿真結(jié)果表明該方法在檢測(cè)加性離群點(diǎn)方面具有較好的性能,。
1 離群點(diǎn)檢測(cè)方法研究
    針對(duì)無(wú)序的數(shù)據(jù)集,，離群點(diǎn)檢測(cè)方法主要有基于統(tǒng)計(jì)的方法、基于距離的方法[4],、基于密度的方法[5]和基于偏離的方法,。近年來(lái)，不少研究人員提出了專(zhuān)門(mén)針對(duì)時(shí)間序列的離群點(diǎn)檢驗(yàn)算法,，主要有統(tǒng)計(jì)診斷方法,、貝葉斯方法、遺傳算法,、人工神經(jīng)網(wǎng)絡(luò),、小波檢測(cè)等。國(guó)內(nèi)也有相關(guān)人員對(duì)此做了深入的研究[2-5],。文獻(xiàn)[6]提出了基于粗糙集理論的序列離群點(diǎn)檢測(cè)方法,，它利用粗糙集理論中的知識(shí)熵和屬性重要性等概念來(lái)構(gòu)建三種類(lèi)型的序列，并通過(guò)分析序列中元素的變化情況來(lái)檢測(cè)離群點(diǎn),。文獻(xiàn)[7]通過(guò)建立多變量時(shí)間序列數(shù)據(jù)相似度矩陣,，對(duì)相似度矩陣進(jìn)行轉(zhuǎn)換以最大化數(shù)據(jù)之間的相關(guān)性，并采用隨機(jī)游走模型計(jì)算數(shù)據(jù)點(diǎn)之間的連接系數(shù)來(lái)檢測(cè)數(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)檢測(cè)算法
2.1 問(wèn)題提出
    對(duì)于時(shí)間序列,，離群點(diǎn)可能會(huì)隱藏在時(shí)間序列的趨勢(shì)、季節(jié)或其他變化中,，增加了檢測(cè)難度,。以圖1所示的時(shí)間序列為例，兩個(gè)時(shí)間序列都處于上升趨勢(shì),，A點(diǎn)明顯偏離了整個(gè)趨勢(shì),，應(yīng)判定為離群點(diǎn)；B點(diǎn)雖然與前向時(shí)刻點(diǎn)在幅度變化率上發(fā)生了較大變化,，但符合后向時(shí)刻點(diǎn)的變化趨勢(shì),，是一個(gè)正常時(shí)間序列點(diǎn)，因此不應(yīng)判定為離群點(diǎn),。

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

    本文以一維時(shí)間序列為研究對(duì)象,，提出了一種基于殘差統(tǒng)計(jì)的加性離群點(diǎn)檢測(cè)算法，基本思想是利用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)。
    定義待檢測(cè)時(shí)間序列數(shù)據(jù)樣本為x_t,，t=1,，2,，3，4…M,，x_t∈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，則：
    δ_t=|(x_t-x_t-1)+(x_t-x_t+1)|
    對(duì)所有δ_t進(jìn)行考慮,，選定門(mén)限δ,，δ值的計(jì)算可以采用平均法或加權(quán)計(jì)算等。若δ_t>δ,，則將x_t標(biāo)志為L(zhǎng)K點(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)是為了在擬合過(guò)程中盡量減少離群點(diǎn)的影響,，對(duì)疑似離群點(diǎn)不作擬合參考。
2.2.2 AR模型擬合與參數(shù)計(jì)算
    擬合常用的模型有AR模型,、MA模型,、ARIMA模型等。AR模型一般用于擬合平穩(wěn)的時(shí)間序列,，而時(shí)間序列從局部來(lái)看近似一個(gè)平穩(wěn)的過(guò)程,，并且AR模型結(jié)構(gòu)相對(duì)簡(jiǎn)單，擬合精度較高,，因此本文選用p階自回歸AR模型,。為了準(zhǔn)確反應(yīng)各檢測(cè)點(diǎn)的局部變化屬性，并減少離群點(diǎn)對(duì)參數(shù)估計(jì)的影響,，本文在文獻(xiàn)[9]所采用的兩窗口模型基礎(chǔ)上,，提出了改進(jìn)的窗口計(jì)算模型，基本原理是：檢測(cè)窗口僅包含t時(shí)刻待檢測(cè)點(diǎn),，前向?qū)W習(xí)窗口和后向?qū)W習(xí)窗口位于檢測(cè)窗口鄰近兩側(cè),，寬度為N，并且N>p,，根據(jù)前向和后向?qū)W習(xí)窗口中的數(shù)據(jù)分別對(duì)t時(shí)刻待檢測(cè)點(diǎn)進(jìn)行前向和后向擬合，采用剪枝思想,，若學(xué)習(xí)窗口中包含疑似離群點(diǎn)LK,，則該點(diǎn)退出學(xué)習(xí)窗口不參與計(jì)算，其余時(shí)間軸上的uLK點(diǎn)向t時(shí)刻整體移位并填滿(mǎn)窗口,。如圖2所示,。

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

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

3 仿真
    為了驗(yàn)證本文所提算法的有效性，以局域網(wǎng)內(nèi)某主機(jī)通信流量監(jiān)測(cè)數(shù)據(jù)為對(duì)象進(jìn)行測(cè)試,。通信流量監(jiān)測(cè)是網(wǎng)絡(luò)管理的重要內(nèi)容,，通過(guò)流量監(jiān)測(cè)，可以全面透視網(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)中，通過(guò)隨機(jī)加入異常事件,，比如網(wǎng)絡(luò)擁塞,、數(shù)據(jù)分發(fā)等來(lái)模擬加性離群點(diǎn)。
    圖3所示為某日上午8:00-12:00的某主機(jī)通信流量監(jiān)測(cè)數(shù)據(jù),，單位為KB/min,，數(shù)據(jù)樣本200個(gè)，離群點(diǎn)5個(gè),。窗口寬度取15,，模型階數(shù)取4，擬合殘差分布情況如圖4所示,。由圖看出,，擬合后，離群點(diǎn)的殘差值與正常的浮動(dòng)范圍相比有較大偏移,。

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

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

圖4  擬合殘差

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

    檢測(cè)統(tǒng)計(jì)結(jié)果如表1所示,。結(jié)果顯示,，當(dāng)實(shí)際離群點(diǎn)數(shù)量在樣本中的比重小于0.05時(shí)，算法能對(duì)離群點(diǎn)進(jìn)行完全有效地檢測(cè),，當(dāng)實(shí)際離群點(diǎn)數(shù)量在樣本中的比重大于0.1時(shí),，檢出率下降,，誤檢率有所上升，但此時(shí)離群點(diǎn)的發(fā)生不再是小概率事件,，根據(jù)加性離群點(diǎn)對(duì)時(shí)間序列產(chǎn)生的影響上看,，它不符合加性離群點(diǎn)特征。因此,，本文所提算法對(duì)檢測(cè)時(shí)間序列中的加性離群點(diǎn)有較好的性能,，同時(shí)，在實(shí)際應(yīng)用中證明該算法對(duì)其他類(lèi)型離群點(diǎn)的檢測(cè)也有一定的魯棒性,。
4 結(jié)論
    本文針對(duì)時(shí)間序列中的加性離群點(diǎn)檢測(cè),，提出了一種基于殘差統(tǒng)計(jì)的檢測(cè)算法。該算法利用AR模型計(jì)算每個(gè)樣本點(diǎn)擬合殘差,，通過(guò)統(tǒng)計(jì)分析殘差的概率分布來(lái)判別離群點(diǎn),。通過(guò)對(duì)局域網(wǎng)某主機(jī)通信流量監(jiān)測(cè)數(shù)據(jù)的仿真結(jié)果顯示，該算法在檢測(cè)加性離群點(diǎn)方面是有效的,，結(jié)果有較高的置信度,。此外，在對(duì)擬合殘差進(jìn)行分析時(shí),，除了本文采用的統(tǒng)計(jì)模型方法外,，還可以采用基于密度的聚類(lèi)的方法。另外如何檢測(cè)時(shí)間序列中其他類(lèi)型的離群點(diǎn)也是值得研究的內(nèi)容,。
參考文獻(xiàn)
[1] 胡云,，王崇駿，謝俊元,，等.社群演化的隱健遷移估計(jì)及演化離群點(diǎn)檢測(cè)[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)檢測(cè)[J].計(jì)算機(jī)工程，2013,，39(2)：178-181.
[5] 江峰,，杜軍威,，葛艷，等.基于粗糙集理論的序列離群點(diǎn)檢測(cè)[J].電子學(xué)報(bào),，2011(2)：345-350.
[6] 李權(quán),，周興社.一種新的多變量時(shí)間序列數(shù)據(jù)異常檢測(cè)方法[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)星，朱云龍,，胡琨元,，等.基于模型的過(guò)程工業(yè)時(shí)間序列異常值檢測(cè)方法[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.