結合局部加權回歸的時序異常檢測方法研究

江新樂 龍軍 陳剛 夏雷 梁多姿 劉麗敏 范慧龍

摘? 要：局部加權回歸是非參數學習方法，可自動規避在數據擬合過程中異常值對近鄰點的影響。通過使用基于局部加權回歸的時間序列分解方法，我們對時間序列進行特征分解，將原始時間序列分解為趨勢項、周期項和殘差項;在給出合理的檢出水平閾值后，我們使用改進的格雷布斯檢驗法在得到殘差項后對殘差項進行異常值檢測。經過實驗證明，該方法相比傳統的時間序列方法三次指數平滑法可減低離群值對模型擬合的影響，更能有效適應數據中潛存的趨勢項的復雜變換，從而更加精準地找到數據中的真實異常點。

關鍵詞：局部加權回歸;時間序列分解;假設檢驗;異常檢測

中圖分類號：TP309? ? ?文獻標識碼：A

Research on Time Series Anomaly Detection Based on Locally Weighted Regression

JIANG Xinle1，LONG Jun2，CHEN Gang1，XIA Lei1，LIANG Duozi1，LIU Limin2，FAN Huilong2

（1.Information Technology Department，China Railway Shanghai Group Co.，Ltd.，Shanghai 200071，China;

2.School of Computer Science and Engineering，Central South University，Changsha 410083，China）

Abstract：Locally Weighted Regression is a non-parametric method，which can automatically avoid the influence of anomaly values against adjacent data in the process of data fitting.By means of time series decomposition method based on Locally Weighted Regression，the original time series can be decomposed into trend，seasonality and residual.After reasonable threshold of detection level is given，we implement anomaly detection for the residual gained by the improved Grubbs testing method.Experiments show that compared with traditional time series method-Holt Winters，this method can reduce the effect of outliers during model fitting process，and adapt the complex variation of the trend in the data more effectively so as to find the real anomaly in the data accurately.

Keywords：Locally Weighted Regression;time series decomposition;hypothesis testing;anomaly detection

1? ?引言（Introduction）

智能運維將傳統機械、人力驅動的監、管、控運維平臺，逐步轉變成為依托于大數據技術和人工智能技術的智能運維平臺。大數據技術，人工智能技術是智能運維平臺的核心驅動力：大數據技術可以幫助IT運維人員快速，全面的處理過去無法處理的海量機器數據，發掘其中“信息寶藏”，從而為企業帶來極大業務價值;而人工智能技術的算法模型，通過大量有價值的機器數據訓練和自我調參，使得機器可以學習到“知識”，賦予運維以“智慧”，大大提升運維分析和判斷力并通過前所未有的智能技術幫助企業降低風險和成本，幫助IT部門敏捷的應對企業業務快速變化。

運維過程中由于其復雜的性質是容易出現性能異常的。雖然以前的工作已經表明使用統計學習來檢測性能異常的有效性，但以前的方案基本都是采用監督學習方式，即往往需要標記訓練數據，這需要大量的人力成本，并且需要花費大量的時間及數據進行訓練，并且只能處理以前已知的異常。針對以上情況我們自研并落地了基于智能無監督的行為學習（UBL）運維系統。UBL系統利用自組織映射來捕獲系統行為并預測未知異常。考慮到部署的靈活性，UBL可以使用基礎架構中的剩余資源進行行為學習和異常預測，能保證其開銷甚微。我們在多個分布式平臺和系統上進行廣泛的實驗和驗證。研究結果表明，UBL可以高準確性地同時預測多個異常指標，通過關聯分析多指標的異常準確定位問題，不僅如此，無監督行為學習ULB系統還能以充裕的時間提前量實現故障自動預測。

本論文定位于智能運維之無監督行為學習實現指標異常檢測算法的研究，是集團公司借助大數據及人工智能技術來改變傳統運維固有的方式，以解決集團公司實際運維過程中痛點及難點的一次重要嘗試。

2? ?局部加權回歸法（Locally weighted regression）

2.1? ?局部加權回歸概念

局部加權回歸[1]是一種非參數學習方法，在擬合具有復雜波動性的數據時相比傳統的線性回歸和多項式回歸表現優秀，因為通常情況下的線性擬合不能很好地預測所有的值，因為它容易導致欠擬合（under fitting），比如數據集是一個鐘形的曲線。一個方法是多項式或者其他函數如正余弦等等，多項式甚至能擬合所有數據，但是在預測新樣本的時候又會變得很糟糕，因為它導致模型的過擬合[2]（overfitting），不符合數據背后的“邏輯”。而通過采用局部加權回歸方法，既避免了復雜的參數調整過程，又不會出現“過擬合”或者“欠擬合”的問題。局部加權回歸通過每個實際點的權重代表實際值相對于其他位置值的可靠性[3]，在每次迭代過程中更新樣本權重，則可以不斷將擬合過程中每個樣本的可靠性進行調整，從而使得異常點對擬合值的影響降到最低。

2.2? ?局部加權回歸的過程

假設和為自變量和因變量，Loess（Locally weighted regression，局部加權回歸）回歸曲線可認為是對于、的平滑曲線[4]，的計算方法如下：

對于一個正整數，目前假設小于，值代表與最接近的個點，而且每一個點根據其與的距離給出一個鄰近權重。假設是指距離點第個遠的點的距離。讓表示三次方程：

則對于，其鄰近權重為：

由于的取值可無最大限制，現在我們假設，此時是中與最遠點的距離;對于，我們定義：

然后我們像之前一樣使用定義鄰近變量。

局部加權回歸的損失函數如下：

同理推導：

其中，α為是權重的對角矩陣。對w求導得到：

所以得到：

其加權矩陣為：

在得到其加權矩陣后，我們可通過回歸計算得到其原始序列的擬合值，并通過迭代不斷調節權重矩陣中每個點的權重，從而降低離群點的影響，使得擬合效果最優。

迭代過程如下：

首先，已知原始值序列為，擬合序列為，殘差為：，記s為的中位數，則對任意一點k：

其權重調整值為：

其修正后的權重為：。

在得到其權重調整值后，我們可一直更新每個點的權重，從而在計算出新的后進行權重調整。

2.3? ?基于局部加權回歸的時間序列分解

時間序列分解方法[5]將原始時間序列分解為：趨勢項、季節項、余項，其中趨勢項是指數據中蘊含的長期的波動情況，不會在短期內發生劇烈變化，而季節項指原始序列中不同周期間具備的相同走勢和變化，余項是指原始序列減去趨勢項、季節項后的剩余部分;趨勢項[6]、季節項都是相對穩定的分量，而經過分解后的余項可被視為是符合正態分布的，由此我們便可以通過假設檢驗[7]方法對余項進行分析，從而尋找數據中的異常點。

我們以表示原始的時間序列，則有以下假設：

其中，Tv表示v點的趨勢分量，Sv表示v點的季節分量，Rv表示v點的余項。

基于局部加權回歸的時間序列分解方法分為內循環、外循環[8]，其中內循環主要做了趨勢分量和周期分量的計算，假定、為內循環中第k-1次結束時的趨勢分量、周期分量，初始化時，并有以下參數：

①內層循環數

②外層循環數

③一個周期的樣本數

④Step2中局部加權回歸平滑參數

⑤Step3中局部加權回歸平滑參數

⑥Step6中局部加權回歸平滑參數

每個周期相同位置的樣本點組成一個子序列，容易知道這樣的子序列共有個，我們稱為cycle-subseries;內循環主要分為以下六個步驟：

Step 1：去趨勢，減去上一輪結果的趨勢分量，。

Step 2：周期子序列平滑，使用局部加權回歸對每個子序列做回歸，并向前向后各延展一個周期;平滑結果組成 temporary seasonal series，記為

Step 3：周期子序列的低通量過濾，對上一個步驟的結果序列依次做長度為、、3的滑動平均，然后做局部加權回歸，得到結果序列

Step 4：去除平滑周期子序列趨勢：

Step 5：去周期，減去周期分量：。

Step 6：趨勢平滑，對于去除周期之后的序列做局部加權回歸，得到趨勢分量。

外循環主要用于調節每個點的權重，如果數據序列中存在異常點，則該點余項會較大，定義

對于位置為的數據點，其權重為：

其中，B為bisquare函數：

然后在每一次迭代的內循環中，在Step 2與Step 6中做局部加權回歸時，將每個點的原始權重乘以，以減少異常點對回歸的影響[9]。

圖1 時序分解圖

Fig.1 Time series decomposition

3 基于假設檢驗的異常值檢測方法（Anomaly detection method based on hypothesis testing）

在完成時間序列分解后，我們抽取余項進行格雷布斯檢驗。

格雷布斯檢驗是對于類正態分布樣本中異常點的檢驗方法，該方法最初是用來檢驗單個異常點的，我們通過對已知異常點進行剔除，重復計算剩余樣本中的異常點，便可以使用格雷布斯檢驗按照余項的絕對值大小對余項進行排序后進行多異常點的檢驗[10-12]。

格雷布斯檢驗法有以下統計量：

其中，表示當前數據集的樣本均值，s表示當前數據集的樣本方差。

通過設定檢出水平，可在附表中查出其臨界值。

圖1為附表部分。得到臨界值后，可對當前序列中絕對值最大的點或進行異常判定：

上側判斷：當時，判定為異常點，否則非異常點;

下側判斷：當時，判定為異常點，否則非異常點。

因此我們在設定檢出水平后，便可快速進行異常檢測。

4? ?實驗結果（The experimental results）

實驗數據選擇真實來源的CPU數據、交易量數據，數據大小分別為Data1、Data2（43200個數據點，時間跨度30天，數據的時間間隔為1min），Data3、Data4（86400個數據點，時間跨度60天，數據的時間間隔為1min）。為了驗證算法的準確性，我們采用F1-Score、精度、召回率進行算法的準確性評估，并與傳統的時間序列方法三次指數平滑法（Holt-winters）、基于統計的3σ準則方法進行對比。對比結果如下：

從實驗結果中可以看到，3σ準則算法由于未考慮到數據的時間特性，只從統計方面進行異常度量，其準確率及召回率遠低于其他算法，而Holt-winters三次指數平滑法由于受到異常值對模型擬合的影響，其整體效果也是差于基于采用局部加權回歸的時間序列分解方法和假設檢驗的無監督異常檢測算法的。

5? ?結論（Conclusion）

將局部加權回歸算法融入時間序列分解模型中，通過自動調節權重的方式可以有效提升算法對正常值的擬合精度，并結合假設檢驗方法進行異常檢測使得檢測效果更加優秀，為實時、精準的發現業務故障、為生產環境護駕保航。

參考文獻（References）

[1] Robert B.Cleveland，William S.Cleveland，Jean E.McRae，et al.STL：A Seasonal-Trend Decomposition Procedure Based on Loess[N].Journal of Offical Statistics，1990：3-72.

[2] Nawar N.Chaker，Doug Walker，Edward L.Nowlin，et al.When and how does sales manager physical attractiveness impact credibility：A test of two competing hypotheses[J].Journal of Business Research，2019，1（6）：105.

[3] 楊永嬌，邱宇，占力超.基于寬度學習的智能電網數據服務器流量異常檢測算法[J].計算機與現代化，2019（09）：77-82;89.

[4] Jia Zhang，Zhiyong Li，Ke Nai，et al.DELR：A double-level ensemble learning method for unsupervised anomaly detection[J].Knowledge-Based Systems，2019，2（6）：181.

[5] 楊姣，高仲合，王來花.網絡數據流異常檢測研究[J].通信技術，2019，52（01）：129-133.

[6] 陳波，劉厚泉，趙志凱.時間序列多尺度異常檢測方法[J].計算機工程與應用，2018，54（20）：122-127.

[7] 楊金艷，江曾杰，陳偉.穩健統計與格拉布斯準則在能力驗證結果分析中的應用[J].計量學報，2018，39（06）：862-867.

[8] D.F.Andrews.A Robust Method for Multiple Linear Regression[J/OL].Technometrics，1974，16（4）：523-531.

[9] 李忠武.時間序列分析與數據挖掘[J].電子商務，2016（11）：41-44.

[10] 孟永偉，秦濤，趙亮，等.利用殘差分析的網絡異常流量檢測方法[J/OL].西安交通大學學報.http：//kns.cnki.net/kcms/detail/61.1069.T.20190808.1349.002.html，2019-09-11.

[11] Treant.時間序列分解算法：STL[EB/OL].https：//www.cnblogs.com/en-heng/p/7390310.html，2016.

[12] batistuta_lj.Grubbs檢驗法[EB/OL].https：//wenku.baidu.com/view/84695b4e852458fb770b56bb.html，2010-11-19.

作者簡介：

江新樂（1963-），男，本科，高級工程師.研究領域：信息化管理.

龍? ?軍（1972-），男，博士，教授.研究領域：計算機科學.

陳? ?剛（1976-），男，本科，高級工程師.研究領域：信息化管理.

夏? ?雷（1978-），男，本科，高級工程師.研究領域：信息化管理.

梁多姿（1982-），男，本科，高級工程師.研究領域：信息化管理.

劉麗敏（1976-），女，博士，講師.研究領域：計算機科學.

范慧龍（1992-），男，博士生.研究領域：計算機科學.