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)檢測(cè)作為對(duì)數(shù)據(jù)進(jìn)行挖掘處理的第一步，已經(jīng)成為該研究領(lǐng)域的重要方向之一，并廣泛應(yīng)用于通信流量監(jiān)測(cè)、工業(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)檢測(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)，不少研究人員提出了專門針對(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)檢測(cè)離群點(diǎn)。文獻(xiàn)[7]通過建立多變量時(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 問題提出
    對(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)行考慮，選定門限δ，δ值的計(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)是為了在擬合過程中盡量減少離群點(diǎn)的影響，對(duì)疑似離群點(diǎn)不作擬合參考。
2.2.2 AR模型擬合與參數(shù)計(jì)算
    擬合常用的模型有AR模型、MA模型、ARIMA模型等。AR模型一般用于擬合平穩(wěn)的時(shí)間序列，而時(shí)間序列從局部來(lái)看近似一個(gè)平穩(wěn)的過程，并且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í)刻整體移位并填滿窗口。如圖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)容，通過流量監(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)中，通過隨機(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ì)其他類型離群點(diǎn)的檢測(cè)也有一定的魯棒性。
4 結(jié)論
    本文針對(duì)時(shí)間序列中的加性離群點(diǎn)檢測(cè)，提出了一種基于殘差統(tǒng)計(jì)的檢測(cè)算法。該算法利用AR模型計(jì)算每個(gè)樣本點(diǎn)擬合殘差，通過統(tǒng)計(jì)分析殘差的概率分布來(lái)判別離群點(diǎn)。通過對(duì)局域網(wǎng)某主機(jī)通信流量監(jiān)測(cè)數(shù)據(jù)的仿真結(jié)果顯示，該算法在檢測(cè)加性離群點(diǎn)方面是有效的，結(jié)果有較高的置信度。此外，在對(duì)擬合殘差進(jìn)行分析時(shí)，除了本文采用的統(tǒng)計(jì)模型方法外，還可以采用基于密度的聚類的方法。另外如何檢測(cè)時(shí)間序列中其他類型的離群點(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)星，朱云龍，胡琨元，等.基于模型的過程工業(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.