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

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

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

中圖分類號：TP309? ? ?文獻(xiàn)標(biāo)識碼：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ū)動的監(jiān)、管、控運(yùn)維平臺，逐步轉(zhuǎn)變成為依托于大數(shù)據(jù)技術(shù)和人工智能技術(shù)的智能運(yùn)維平臺。大數(shù)據(jù)技術(shù)，人工智能技術(shù)是智能運(yùn)維平臺的核心驅(qū)動力：大數(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í)到“知識”，賦予運(yùn)維以“智慧”，大大提升運(yùn)維分析和判斷力并通過前所未有的智能技術(shù)幫助企業(yè)降低風(fēng)險(xiǎn)和成本，幫助IT部門敏捷的應(yīng)對企業(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ù)據(jù)進(jìn)行訓(xùn)練，并且只能處理以前已知的異常。針對以上情況我們自研并落地了基于智能無監(jiān)督的行為學(xué)習(xí)（UBL）運(yùn)維系統(tǒng)。UBL系統(tǒng)利用自組織映射來捕獲系統(tǒng)行為并預(yù)測未知異常?？紤]到部署的靈活性，UBL可以使用基礎(chǔ)架構(gòu)中的剩余資源進(jìn)行行為學(xué)習(xí)和異常預(yù)測，能保證其開銷甚微。我們在多個分布式平臺和系統(tǒng)上進(jìn)行廣泛的實(shí)驗(yàn)和驗(yàn)證。研究結(jié)果表明，UBL可以高準(zhǔn)確性地同時預(yù)測多個異常指標(biāo)，通過關(guān)聯(lián)分析多指標(biāo)的異常準(zhǔn)確定位問題，不僅如此，無監(jiān)督行為學(xué)習(xí)ULB系統(tǒng)還能以充裕的時間提前量實(shí)現(xiàn)故障自動預(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ù)雜波動性的數(shù)據(jù)時相比傳統(tǒng)的線性回歸和多項(xiàng)式回歸表現(xiàn)優(yōu)秀，因?yàn)橥ǔＧ闆r下的線性擬合不能很好地預(yù)測所有的值，因?yàn)樗菀讓?dǎo)致欠擬合（under fitting），比如數(shù)據(jù)集是一個鐘形的曲線。一個方法是多項(xiàng)式或者其他函數(shù)如正余弦等等，多項(xiàng)式甚至能擬合所有數(shù)據(jù)，但是在預(yù)測新樣本的時候又會變得很糟糕，因?yàn)樗鼘?dǎo)致模型的過擬合[2]（overfitting），不符合數(shù)據(jù)背后的“邏輯”。而通過采用局部加權(quán)回歸方法，既避免了復(fù)雜的參數(shù)調(diào)整過程，又不會出現(xiàn)“過擬合”或者“欠擬合”的問題。局部加權(quán)回歸通過每個實(shí)際點(diǎn)的權(quán)重代表實(shí)際值相對于其他位置值的可靠性[3]，在每次迭代過程中更新樣本權(quán)重，則可以不斷將擬合過程中每個樣本的可靠性進(jìn)行調(diào)整，從而使得異常點(diǎn)對擬合值的影響降到最低。

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

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

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

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

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

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

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

同理推導(dǎo)：

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

所以得到：

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

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

迭代過程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 時序分解圖

Fig.1 Time series decomposition

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

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

格雷布斯檢驗(yàn)是對于類正態(tài)分布樣本中異常點(diǎn)的檢驗(yàn)方法，該方法最初是用來檢驗(yàn)單個異常點(diǎn)的，我們通過對已知異常點(diǎn)進(jìn)行剔除，重復(fù)計(jì)算剩余樣本中的異常點(diǎn)，便可以使用格雷布斯檢驗(yàn)按照余項(xiàng)的絕對值大小對余項(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為附表部分。得到臨界值后，可對當(dāng)前序列中絕對值最大的點(diǎn)或進(jìn)行異常判定：

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

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

因此我們在設(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個數(shù)據(jù)點(diǎn)，時間跨度30天，數(shù)據(jù)的時間間隔為1min），Data3、Data4（86400個數(shù)據(jù)點(diǎn)，時間跨度60天，數(shù)據(jù)的時間間隔為1min）。為了驗(yàn)證算法的準(zhǔn)確性，我們采用F1-Score、精度、召回率進(jìn)行算法的準(zhǔn)確性評估，并與傳統(tǒng)的時間序列方法三次指數(shù)平滑法（Holt-winters）、基于統(tǒng)計(jì)的3σ準(zhǔn)則方法進(jìn)行對比。對比結(jié)果如下：

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

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

將局部加權(quán)回歸算法融入時間序列分解模型中，通過自動調(diào)節(jié)權(quán)重的方式可以有效提升算法對正常值的擬合精度，并結(jié)合假設(shè)檢驗(yàn)方法進(jìn)行異常檢測使得檢測效果更加優(yōu)秀，為實(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] 陳波，劉厚泉，趙志凱.時間序列多尺度異常檢測方法[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ù)據(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.時間序列分解算法：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-），男，本科，高級工程師.研究領(lǐng)域：信息化管理.

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

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

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

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

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

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