結(jié)合局部加權(quán)回歸的時(shí)序異常檢測方法研究

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

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

關(guān)鍵詞：局部加權(quán)回歸;時(shí)間序列分解;假設(shè)檢驗(yàn);異常檢測

中圖分類號(hào)：TP309? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Research on Time Series Anomaly Detection Based on Locally Weighted Regression

JIANG Xinle1，LONG Jun2，CHEN Gang1，XIA Lei1，LIANG Duozi1，LIU Limin2，F(xiàn)AN 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）

智能運(yùn)維將傳統(tǒng)機(jī)械、人力驅(qū)動(dòng)的監(jiān)、管、控運(yùn)維平臺(tái)，逐步轉(zhuǎn)變成為依托于大數(shù)據(jù)技術(shù)和人工智能技術(shù)的智能運(yùn)維平臺(tái)。大數(shù)據(jù)技術(shù)，人工智能技術(shù)是智能運(yùn)維平臺(tái)的核心驅(qū)動(dòng)力：大數(shù)據(jù)技術(shù)可以幫助IT運(yùn)維人員快速，全面的處理過去無法處理的海量機(jī)器數(shù)據(jù)，發(fā)掘其中“信息寶藏”，從而為企業(yè)帶來極大業(yè)務(wù)價(jià)值;而人工智能技術(shù)的算法模型，通過大量有價(jià)值的機(jī)器數(shù)據(jù)訓(xùn)練和自我調(diào)參，使得機(jī)器可以學(xué)習(xí)到“知識(shí)”，賦予運(yùn)維以“智慧”，大大提升運(yùn)維分析和判斷力并通過前所未有的智能技術(shù)幫助企業(yè)降低風(fēng)險(xiǎn)和成本，幫助IT部門敏捷的應(yīng)對(duì)企業(yè)業(yè)務(wù)快速變化。

運(yùn)維過程中由于其復(fù)雜的性質(zhì)是容易出現(xiàn)性能異常的。雖然以前的工作已經(jīng)表明使用統(tǒng)計(jì)學(xué)習(xí)來檢測性能異常的有效性，但以前的方案基本都是采用監(jiān)督學(xué)習(xí)方式，即往往需要標(biāo)記訓(xùn)練數(shù)據(jù)，這需要大量的人力成本，并且需要花費(fèi)大量的時(shí)間及數(shù)據(jù)進(jìn)行訓(xùn)練，并且只能處理以前已知的異常。針對(duì)以上情況我們自研并落地了基于智能無監(jiān)督的行為學(xué)習(xí)（UBL）運(yùn)維系統(tǒng)。UBL系統(tǒng)利用自組織映射來捕獲系統(tǒng)行為并預(yù)測未知異常?？紤]到部署的靈活性，UBL可以使用基礎(chǔ)架構(gòu)中的剩余資源進(jìn)行行為學(xué)習(xí)和異常預(yù)測，能保證其開銷甚微。我們?cè)诙鄠€(gè)分布式平臺(tái)和系統(tǒng)上進(jìn)行廣泛的實(shí)驗(yàn)和驗(yàn)證。研究結(jié)果表明，UBL可以高準(zhǔn)確性地同時(shí)預(yù)測多個(gè)異常指標(biāo)，通過關(guān)聯(lián)分析多指標(biāo)的異常準(zhǔn)確定位問題，不僅如此，無監(jiān)督行為學(xué)習(xí)ULB系統(tǒng)還能以充裕的時(shí)間提前量實(shí)現(xiàn)故障自動(dòng)預(yù)測。

本論文定位于智能運(yùn)維之無監(jiān)督行為學(xué)習(xí)實(shí)現(xiàn)指標(biāo)異常檢測算法的研究，是集團(tuán)公司借助大數(shù)據(jù)及人工智能技術(shù)來改變傳統(tǒng)運(yùn)維固有的方式，以解決集團(tuán)公司實(shí)際運(yùn)維過程中痛點(diǎn)及難點(diǎn)的一次重要嘗試。

2? ?局部加權(quán)回歸法（Locally weighted regression）

2.1? ?局部加權(quán)回歸概念

局部加權(quán)回歸[1]是一種非參數(shù)學(xué)習(xí)方法，在擬合具有復(fù)雜波動(dòng)性的數(shù)據(jù)時(shí)相比傳統(tǒng)的線性回歸和多項(xiàng)式回歸表現(xiàn)優(yōu)秀，因?yàn)橥ǔＧ闆r下的線性擬合不能很好地預(yù)測所有的值，因?yàn)樗菀讓?dǎo)致欠擬合（under fitting），比如數(shù)據(jù)集是一個(gè)鐘形的曲線。一個(gè)方法是多項(xiàng)式或者其他函數(shù)如正余弦等等，多項(xiàng)式甚至能擬合所有數(shù)據(jù)，但是在預(yù)測新樣本的時(shí)候又會(huì)變得很糟糕，因?yàn)樗鼘?dǎo)致模型的過擬合[2]（overfitting），不符合數(shù)據(jù)背后的“邏輯”。而通過采用局部加權(quán)回歸方法，既避免了復(fù)雜的參數(shù)調(diào)整過程，又不會(huì)出現(xiàn)“過擬合”或者“欠擬合”的問題。局部加權(quán)回歸通過每個(gè)實(shí)際點(diǎn)的權(quán)重代表實(shí)際值相對(duì)于其他位置值的可靠性[3]，在每次迭代過程中更新樣本權(quán)重，則可以不斷將擬合過程中每個(gè)樣本的可靠性進(jìn)行調(diào)整，從而使得異常點(diǎn)對(duì)擬合值的影響降到最低。

2.2? ?局部加權(quán)回歸的過程

假設(shè)和為自變量和因變量，Loess（Locally weighted regression，局部加權(quán)回歸）回歸曲線可認(rèn)為是對(duì)于、的平滑曲線[4]，的計(jì)算方法如下：

對(duì)于一個(gè)正整數(shù)，目前假設(shè)小于，值代表與最接近的個(gè)點(diǎn)，而且每一個(gè)點(diǎn)根據(jù)其與的距離給出一個(gè)鄰近權(quán)重。假設(shè)是指距離點(diǎn)第個(gè)遠(yuǎn)的點(diǎn)的距離。讓表示三次方程：

則對(duì)于，其鄰近權(quán)重為：

由于的取值可無最大限制，現(xiàn)在我們假設(shè)，此時(shí)是中與最遠(yuǎn)點(diǎn)的距離;對(duì)于，我們定義：

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

局部加權(quán)回歸的損失函數(shù)如下：

同理推導(dǎo)：

其中，α為是權(quán)重的對(duì)角矩陣。對(duì)w求導(dǎo)得到：

所以得到：

其加權(quán)矩陣為：

在得到其加權(quán)矩陣后，我們可通過回歸計(jì)算得到其原始序列的擬合值，并通過迭代不斷調(diào)節(jié)權(quán)重矩陣中每個(gè)點(diǎn)的權(quán)重，從而降低離群點(diǎn)的影響，使得擬合效果最優(yōu)。

迭代過程如下：

首先，已知原始值序列為，擬合序列為，殘差為：，記s為的中位數(shù)，則對(duì)任意一點(diǎn)k：

其權(quán)重調(diào)整值為：

其修正后的權(quán)重為：。

在得到其權(quán)重調(diào)整值后，我們可一直更新每個(gè)點(diǎn)的權(quán)重，從而在計(jì)算出新的后進(jìn)行權(quán)重調(diào)整。

2.3? ?基于局部加權(quán)回歸的時(shí)間序列分解

時(shí)間序列分解方法[5]將原始時(shí)間序列分解為：趨勢(shì)項(xiàng)、季節(jié)項(xiàng)、余項(xiàng)，其中趨勢(shì)項(xiàng)是指數(shù)據(jù)中蘊(yùn)含的長期的波動(dòng)情況，不會(huì)在短期內(nèi)發(fā)生劇烈變化，而季節(jié)項(xiàng)指原始序列中不同周期間具備的相同走勢(shì)和變化，余項(xiàng)是指原始序列減去趨勢(shì)項(xiàng)、季節(jié)項(xiàng)后的剩余部分;趨勢(shì)項(xiàng)[6]、季節(jié)項(xiàng)都是相對(duì)穩(wěn)定的分量，而經(jīng)過分解后的余項(xiàng)可被視為是符合正態(tài)分布的，由此我們便可以通過假設(shè)檢驗(yàn)[7]方法對(duì)余項(xiàng)進(jìn)行分析，從而尋找數(shù)據(jù)中的異常點(diǎn)。

我們以表示原始的時(shí)間序列，則有以下假設(shè)：

其中，Tv表示v點(diǎn)的趨勢(shì)分量，Sv表示v點(diǎn)的季節(jié)分量，Rv表示v點(diǎn)的余項(xiàng)。

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

①內(nèi)層循環(huán)數(shù)

②外層循環(huán)數(shù)

③一個(gè)周期的樣本數(shù)

④Step2中局部加權(quán)回歸平滑參數(shù)

⑤Step3中局部加權(quán)回歸平滑參數(shù)

⑥Step6中局部加權(quán)回歸平滑參數(shù)

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

Step 1：去趨勢(shì)，減去上一輪結(jié)果的趨勢(shì)分量，。

Step 2：周期子序列平滑，使用局部加權(quán)回歸對(duì)每個(gè)子序列做回歸，并向前向后各延展一個(gè)周期;平滑結(jié)果組成 temporary seasonal series，記為

Step 3：周期子序列的低通量過濾，對(duì)上一個(gè)步驟的結(jié)果序列依次做長度為、、3的滑動(dòng)平均，然后做局部加權(quán)回歸，得到結(jié)果序列

Step 4：去除平滑周期子序列趨勢(shì)：

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

Step 6：趨勢(shì)平滑，對(duì)于去除周期之后的序列做局部加權(quán)回歸，得到趨勢(shì)分量。

外循環(huán)主要用于調(diào)節(jié)每個(gè)點(diǎn)的權(quán)重，如果數(shù)據(jù)序列中存在異常點(diǎn)，則該點(diǎn)余項(xiàng)會(huì)較大，定義

對(duì)于位置為的數(shù)據(jù)點(diǎn)，其權(quán)重為：

其中，B為bisquare函數(shù)：

然后在每一次迭代的內(nèi)循環(huán)中，在Step 2與Step 6中做局部加權(quán)回歸時(shí)，將每個(gè)點(diǎn)的原始權(quán)重乘以，以減少異常點(diǎn)對(duì)回歸的影響[9]。

圖1 時(shí)序分解圖

Fig.1 Time series decomposition

3 基于假設(shè)檢驗(yàn)的異常值檢測方法（Anomaly detection method based on hypothesis testing）

在完成時(shí)間序列分解后，我們抽取余項(xiàng)進(jìn)行格雷布斯檢驗(yàn)。

格雷布斯檢驗(yàn)是對(duì)于類正態(tài)分布樣本中異常點(diǎn)的檢驗(yàn)方法，該方法最初是用來檢驗(yàn)單個(gè)異常點(diǎn)的，我們通過對(duì)已知異常點(diǎn)進(jìn)行剔除，重復(fù)計(jì)算剩余樣本中的異常點(diǎn)，便可以使用格雷布斯檢驗(yàn)按照余項(xiàng)的絕對(duì)值大小對(duì)余項(xiàng)進(jìn)行排序后進(jìn)行多異常點(diǎn)的檢驗(yàn)[10-12]。

格雷布斯檢驗(yàn)法有以下統(tǒng)計(jì)量：

其中，表示當(dāng)前數(shù)據(jù)集的樣本均值，s表示當(dāng)前數(shù)據(jù)集的樣本方差。

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

圖1為附表部分。得到臨界值后，可對(duì)當(dāng)前序列中絕對(duì)值最大的點(diǎn)或進(jìn)行異常判定：

上側(cè)判斷：當(dāng)時(shí)，判定為異常點(diǎn)，否則非異常點(diǎn);

下側(cè)判斷：當(dāng)時(shí)，判定為異常點(diǎn)，否則非異常點(diǎn)。

因此我們?cè)谠O(shè)定檢出水平后，便可快速進(jìn)行異常檢測。

4? ?實(shí)驗(yàn)結(jié)果（The experimental results）

實(shí)驗(yàn)數(shù)據(jù)選擇真實(shí)來源的CPU數(shù)據(jù)、交易量數(shù)據(jù)，數(shù)據(jù)大小分別為Data1、Data2（43200個(gè)數(shù)據(jù)點(diǎn)，時(shí)間跨度30天，數(shù)據(jù)的時(shí)間間隔為1min），Data3、Data4（86400個(gè)數(shù)據(jù)點(diǎn)，時(shí)間跨度60天，數(shù)據(jù)的時(shí)間間隔為1min）。為了驗(yàn)證算法的準(zhǔn)確性，我們采用F1-Score、精度、召回率進(jìn)行算法的準(zhǔn)確性評(píng)估，并與傳統(tǒng)的時(shí)間序列方法三次指數(shù)平滑法（Holt-winters）、基于統(tǒng)計(jì)的3σ準(zhǔn)則方法進(jìn)行對(duì)比。對(duì)比結(jié)果如下：

從實(shí)驗(yàn)結(jié)果中可以看到，3σ準(zhǔn)則算法由于未考慮到數(shù)據(jù)的時(shí)間特性，只從統(tǒng)計(jì)方面進(jìn)行異常度量，其準(zhǔn)確率及召回率遠(yuǎn)低于其他算法，而Holt-winters三次指數(shù)平滑法由于受到異常值對(duì)模型擬合的影響，其整體效果也是差于基于采用局部加權(quán)回歸的時(shí)間序列分解方法和假設(shè)檢驗(yàn)的無監(jiān)督異常檢測算法的。

5? ?結(jié)論（Conclusion）

將局部加權(quán)回歸算法融入時(shí)間序列分解模型中，通過自動(dòng)調(diào)節(jié)權(quán)重的方式可以有效提升算法對(duì)正常值的擬合精度，并結(jié)合假設(shè)檢驗(yàn)方法進(jìn)行異常檢測使得檢測效果更加優(yōu)秀，為實(shí)時(shí)、精準(zhǔn)的發(fā)現(xiàn)業(yè)務(wù)故障、為生產(chǎn)環(huán)境護(hù)駕保航。

參考文獻(xiàn)（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] 楊永嬌，邱宇，占力超.基于寬度學(xué)習(xí)的智能電網(wǎng)數(shù)據(jù)服務(wù)器流量異常檢測算法[J].計(jì)算機(jī)與現(xiàn)代化，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] 楊姣，高仲合，王來花.網(wǎng)絡(luò)數(shù)據(jù)流異常檢測研究[J].通信技術(shù)，2019，52（01）：129-133.

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

[7] 楊金艷，江曾杰，陳偉.穩(wěn)健統(tǒng)計(jì)與格拉布斯準(zhǔn)則在能力驗(yàn)證結(jié)果分析中的應(yīng)用[J].計(jì)量學(xué)報(bào)，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] 李忠武.時(shí)間序列分析與數(shù)據(jù)挖掘[J].電子商務(wù)，2016（11）：41-44.

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

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

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

作者簡介：

江新樂（1963-），男，本科，高級(jí)工程師.研究領(lǐng)域：信息化管理.

龍? ?軍（1972-），男，博士，教授.研究領(lǐng)域：計(jì)算機(jī)科學(xué).

陳? ?剛（1976-），男，本科，高級(jí)工程師.研究領(lǐng)域：信息化管理.

夏? ?雷（1978-），男，本科，高級(jí)工程師.研究領(lǐng)域：信息化管理.

梁多姿（1982-），男，本科，高級(jí)工程師.研究領(lǐng)域：信息化管理.

劉麗敏（1976-），女，博士，講師.研究領(lǐng)域：計(jì)算機(jī)科學(xué).

范慧龍（1992-），男，博士生.研究領(lǐng)域：計(jì)算機(jī)科學(xué).