《電子技術應用》
您所在的位置：首頁 > 嵌入式技術 > 設計應用 > 基于殘差統(tǒng)計的時間序列加性離群點檢測算法研究
基于殘差統(tǒng)計的時間序列加性離群點檢測算法研究
張 玲，劉 波
國家數(shù)字交換系統(tǒng)工程技術研究中心，北京100094
摘要： 針對時間序列，提出了一種基于殘差統(tǒng)計的加性離群點檢測算法，利用AR模型對時間序列進行前向與后向擬合；采用了數(shù)據相對變化率判別法減少離群點對擬合的影響；根據假設檢驗原理，以高斯分布統(tǒng)計檢驗對殘差進行統(tǒng)計分析并最終確定離群點。仿真結果表明，該方法對離群點檢測有較高的準確性。
中圖分類號： TP311.11
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2015.09.023

中文引用格式： 張玲，劉波. 基于殘差統(tǒng)計的時間序列加性離群點檢測算法研究[J].電子技術應用，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.
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
Abstract： 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.
Key words : time series；outlier；AR model；Gauss distribution


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

201509b-tx1t1.jpg

圖1  受加性離群點“干擾”的時間序列與正常時間序列

    本文以一維時間序列為研究對象，提出了一種基于殘差統(tǒng)計的加性離群點檢測算法，基本思想是利用p階AR模型對時間序列進行前向與后向擬合，得到每個時間點擬合殘差。采用了鄰域區(qū)間變化率判別法對離群點進行初判，初判的疑似離群點不參與擬合運算。最后根據高斯分布假設檢驗的方法對殘差進行統(tǒng)計分析并最終確定離群點。
    定義待檢測時間序列數(shù)據樣本為xt，t=1，2，3，4…M，xt∈R，并做如下假設：
    (1)離群點隨機分布；
    (2)正常數(shù)據的數(shù)量遠大于離群點數(shù)量。
2.2 算法描述
2.2.1 鄰域區(qū)間變化率
    定義1 鄰域區(qū)間變化率：時間序列各時刻點與相鄰前后時刻的幅度變化率。設時刻t的鄰域區(qū)間變化率為δt，則：
    δt=|(xt-xt-1)+(xt-xt+1)|
    對所有δt進行考慮，選定門限δ，δ值的計算可以采用平均法或加權計算等。若δt>δ，則將xt標志為LK點（疑似離群點），否則標志為uLK點（非疑似離群點）。
    離群點相對于它前后相鄰數(shù)據都會有較大變化，因此鄰域區(qū)間變化率要同時對前向時刻和后向時刻進行考慮。定義LK點和uLK點是為了在擬合過程中盡量減少離群點的影響，對疑似離群點不作擬合參考。
2.2.2 AR模型擬合與參數(shù)計算
    擬合常用的模型有AR模型、MA模型、ARIMA模型等。AR模型一般用于擬合平穩(wěn)的時間序列，而時間序列從局部來看近似一個平穩(wěn)的過程，并且AR模型結構相對簡單，擬合精度較高，因此本文選用p階自回歸AR模型。為了準確反應各檢測點的局部變化屬性，并減少離群點對參數(shù)估計的影響，本文在文獻[9]所采用的兩窗口模型基礎上，提出了改進的窗口計算模型，基本原理是：檢測窗口僅包含t時刻待檢測點，前向學習窗口和后向學習窗口位于檢測窗口鄰近兩側，寬度為N，并且N>p，根據前向和后向學習窗口中的數(shù)據分別對t時刻待檢測點進行前向和后向擬合，采用剪枝思想，若學習窗口中包含疑似離群點LK，則該點退出學習窗口不參與計算，其余時間軸上的uLK點向t時刻整體移位并填滿窗口。如圖2所示。

201509b-tx1t2.jpg

圖2  改進的窗口模型

K[%M%%%LUM]HI4JEPTUTXWY.png

2.2.3 高斯統(tǒng)計檢測
    基于假設檢驗理論，在一定的顯著性水平下，擬合殘差εt近似服從高斯分布，即ε~N(u，σ2)。并且在假設2前提下，高斯分布作為殘差統(tǒng)計模型對離群點判決同樣具有較高置信度。在此，選擇高斯分布做為統(tǒng)計模型，εt的概率密度為：
B[}C05N)K]M2BR%YK5ZZ%T5.png

3 仿真
    為了驗證本文所提算法的有效性，以局域網內某主機通信流量監(jiān)測數(shù)據為對象進行測試。通信流量監(jiān)測是網絡管理的重要內容，通過流量監(jiān)測，可以全面透視網絡的流量控制，快速定位和發(fā)現(xiàn)網絡故障，并保障關鍵應用的穩(wěn)定運行，減少泄密風險。一般情況下，主機通信流量的具體業(yè)務包括Web、Telnet、SNMP、請求應答數(shù)據包等，在仿真實驗中，通過隨機加入異常事件，比如網絡擁塞、數(shù)據分發(fā)等來模擬加性離群點。
    圖3所示為某日上午8:00-12:00的某主機通信流量監(jiān)測數(shù)據，單位為KB/min，數(shù)據樣本200個，離群點5個。窗口寬度取15，模型階數(shù)取4，擬合殘差分布情況如圖4所示。由圖看出，擬合后，離群點的殘差值與正常的浮動范圍相比有較大偏移。

201509b-tx1t3.jpg

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

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

201509b-tx1t4.jpg

圖4  擬合殘差

    檢出率：檢測出的真實離群點數(shù)量與實際離群點數(shù)量之比。
    誤檢率：檢測出的錯誤離群點數(shù)量與實際離群點數(shù)量之比。

)@OK9M_IDAFJTP@ZD$(~A5L.png

    檢測統(tǒng)計結果如表1所示。結果顯示，當實際離群點數(shù)量在樣本中的比重小于0.05時，算法能對離群點進行完全有效地檢測，當實際離群點數(shù)量在樣本中的比重大于0.1時，檢出率下降，誤檢率有所上升，但此時離群點的發(fā)生不再是小概率事件，根據加性離群點對時間序列產生的影響上看，它不符合加性離群點特征。因此，本文所提算法對檢測時間序列中的加性離群點有較好的性能，同時，在實際應用中證明該算法對其他類型離群點的檢測也有一定的魯棒性。
4 結論
    本文針對時間序列中的加性離群點檢測，提出了一種基于殘差統(tǒng)計的檢測算法。該算法利用AR模型計算每個樣本點擬合殘差，通過統(tǒng)計分析殘差的概率分布來判別離群點。通過對局域網某主機通信流量監(jiān)測數(shù)據的仿真結果顯示，該算法在檢測加性離群點方面是有效的，結果有較高的置信度。此外，在對擬合殘差進行分析時，除了本文采用的統(tǒng)計模型方法外，還可以采用基于密度的聚類的方法。另外如何檢測時間序列中其他類型的離群點也是值得研究的內容。
參考文獻
[1] 胡云，王崇駿，謝俊元，等.社群演化的隱健遷移估計及演化離群點檢測[J].軟件學報，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] 劉耀宗，張宏，孟錦，等.基于小波密度估計的數(shù)據流離群點檢測[J].計算機工程，2013，39(2)：178-181.
[5] 江峰，杜軍威，葛艷，等.基于粗糙集理論的序列離群點檢測[J].電子學報，2011(2)：345-350.
[6] 李權，周興社.一種新的多變量時間序列數(shù)據異常檢測方法[J].時間頻率學報，2011，34(2)：154-158.
[7] 周勇.時間序列時序關聯(lián)規(guī)則挖掘研究[D].成都：西南財經大學，2008.
[8] 蘇衛(wèi)星，朱云龍，胡琨元，等.基于模型的過程工業(yè)時間序列異常值檢測方法[J].儀器儀表學報，2012(9)：2080-2087.
[9] 皇甫堪，陳建文，樓生強.現(xiàn)代數(shù)字信號處理[M].北京：電子工業(yè)出版社，2003.
[10] 薛安榮，鞠時光，何偉華，等.局部離群點挖掘算法研究[J].計算機學報，2007(8)：1455-1463.

此內容為AET網站原創(chuàng)，未經授權禁止轉載。