王智遠，陳 榕，任崇廣

(山東理工大學 計算機科學與技術學院，山東 淄博 255000)

0 引 言

云計算與大數(shù)據(jù)技術為分布式計算提供了一種解決方案。對于大型的分布式系統(tǒng)，出現(xiàn)異?；蛘埱蟪瑫r可能帶來巨大的損失，而由于系統(tǒng)規(guī)模較大，復雜度較高，給系統(tǒng)維護人員帶來了巨大挑戰(zhàn)。監(jiān)測告警對于保證云平臺的高效性與可用性至關重要，如何全面、精準地定位異常點越來越受到工業(yè)界與學術界的關注。

異常點檢測是找出被檢測樣本中行為很不同于預期值的樣本，這些樣本叫異常點或離群點。常見的離群點檢測算法包括基于機器學習的檢測模型、基于統(tǒng)計的檢測模型、基于線性或非線性的檢測模型、基于距離的檢測模型等[1]?；诮y(tǒng)計的檢測模型將違背正常數(shù)據(jù)分布的樣本判為異常點；基于距離的檢測模型將遠離其它對象的樣本判為異常點[2-4]；基于線性與非線性的檢測模型將違背數(shù)據(jù)相關性的樣本判為異常點[5，6]；基于機器學習的檢測模型將不在超平面內的樣本判為異常點[7，8]。

傳統(tǒng)基于閾值的異常點檢測方法存在適用場景單一、誤報率或漏報率高等問題，本文提出了一種基于集成學習的異常點檢測系統(tǒng)，對于異常點檢測有一定的通用性與有效性。通過監(jiān)測相似序列的聚類、監(jiān)測序列的預處理、監(jiān)測序列特征化、異常點檢測器構建、結果評估幾個流程對工業(yè)界帶有標注的監(jiān)測序列進行異常點檢測，實驗結果表明，基于集成學習的異常點檢測系統(tǒng)效果優(yōu)于單一檢測系統(tǒng)。

1 集成學習

集成學習，有時也被稱為多分類器系統(tǒng)，通過構建并結合多個弱檢測器來完成檢測任務。集成學習先產(chǎn)生一組弱檢測器，再按某種策略將它們結合，?？色@得比弱檢測器顯著優(yōu)越的泛化性能。集成學習方法大致可分為兩大類：第一Boosting，該方法弱檢測器間存在強依賴關系，需串行生成；第二類是Bagging，該方法弱檢測器間不存在強依賴關系，可并行生成[9]。

1.1 Boosting

(1)

(2)

Xgboost對于式(2)利用泰勒公式進行二階近似展開得到式(3)，求解后得到式(4)，確定樹的結構后可用式(4) 求相應的權重值

(3)

(4)

求樹的結構時采用貪心算法，求在分裂前后使式(5)減小最大的特征為分裂節(jié)點

(5)

其中，ObjnoSplit代表按某個檢測特征分裂前的損失，ObjSplit代表按某個檢測特征分裂后的損失，GL，GR代表分裂后弱檢測器的左子樹與右子樹上被檢測樣本損失的一階導數(shù)和，HL，HR代表分裂后弱檢測器左子樹與右子樹相應被檢測樣本損失的二階導數(shù)和，Tsplit，Tnosplit代表弱檢測器分裂前后葉節(jié)點的個數(shù)，γ為常數(shù)項。

1.2 Bagging

Bagging通過構造多個相互獨立的弱檢測器來提高泛化能力，基本思想是從m個被檢測樣本中有放回地抽樣m個樣本得到一個訓練集，采樣T次得到T個訓練集，訓練T個檢測器，基于一定的投票策略產(chǎn)生最終結果。本文使用了Bagging流派的隨機森林[11]，對其基本原理進行分析。

隨機森林是Bagging的一個變體，加入了隨機特征選擇的思想，傳統(tǒng)決策樹在分類時采用式(6)衡量純度，在所有特征中選擇使式(7)增益最大的特征分裂。而隨機森林的每個弱檢測器隨機選取k個檢測特征進行樹的構建，最終結果由多個弱檢測器投票產(chǎn)生

(6)

其中，D代表被檢測樣本，Ck代表第k個類別的樣本，K代表所有類的總數(shù)

(7)

其中，A代表檢測特征，D1、D2代表按相應檢測特征劃分后的樣本，Gini的計算方式為式(6)。

1.3 Stacking

Stacking[12]從原始被檢測樣本集中訓練第一級檢測器，由第一級檢測器生成新的被檢測樣本集用于訓練第二級檢測器。在新的被檢測樣本集中，第一級檢測器的輸出作為第二級檢測器的輸入，第二級的標注與第一級相同。檢測器構建階段，直接將第一級檢測器的結果作為第二級檢測器的輸入容易過擬合，采用k折交叉驗證生成第二級的檢測集。圖1顯示了一個檢測器生成訓練集，測試集的過程，5折交叉驗證，其中的一折與其它4折交替，訓練預測5次后構成了Model1的次級訓練數(shù)據(jù)，n個檢測器最終會構造出m×n的訓練集與p×n的預測集，其中m，p為原訓練集，測試集的樣本個數(shù)，利用次級訓練測試數(shù)據(jù)進行學習得到最終結果。

圖1 Stacking融合過程

2 監(jiān)測序列特征工程

監(jiān)測序列特征化是一個數(shù)據(jù)處理過程，通過各種運算將原始監(jiān)測序列處理成異常點檢測器可直接訓練的數(shù)據(jù)，特征化是為了更好地捕捉異常值特征，提高檢測精度。與原始監(jiān)測序列相比，特征化的監(jiān)測序列檢測精度有顯著提高，特征化過程包括監(jiān)測序列預處理、監(jiān)測序列特征化、監(jiān)測序列特征選擇。不同監(jiān)測序列表現(xiàn)出不同的特性，直接使用原始監(jiān)測序列構造檢測器會造成誤報，需要將相同特性的監(jiān)測序列歸為一類，同一類序列統(tǒng)一訓練檢測。原始的監(jiān)測序列值不能很好捕獲序列的特性，需要從多個方面構建特征減少誤報漏報，更好捕獲異常特性。現(xiàn)實場景中異常極少發(fā)生，導致標注為異常的樣本遠少于標注為正常的樣本，使用不平衡數(shù)據(jù)訓練的檢測器將導致檢測器向正常類傾斜，不平衡樣本的過采樣可以在一定程度上解決正常樣本遠大于異常樣本的問題。將原始監(jiān)測序列轉換成監(jiān)測序列特征后，需要對監(jiān)測特征進行特征篩選，使用發(fā)揮作用較大的監(jiān)測特征可提高訓練速度與檢測速度。對篩選后的監(jiān)測特征進行主成分分析，消除特征之間的線性關系。

2.1 監(jiān)測序列聚類

不同特性的監(jiān)測序列異常表現(xiàn)方式不一樣，直接使用原始監(jiān)測序列構造統(tǒng)一的檢測器不能適用于所有場景，因此需要將相同特性的監(jiān)測序列歸為一類，同一類序列統(tǒng)一訓練檢測。

監(jiān)測序列X=[x1，x2…xn] 與監(jiān)測序列Y=[y1，y2,…,yn] 之間的相似度定義為式(8)，m條監(jiān)測序列的相似度矩陣定義為式(10)，將相似度矩陣作為監(jiān)測序列聚類的輸入

(8)

其中，X，Y代表監(jiān)測序列，φi(X) 的定義為式(9)，Cov代表協(xié)方差，Var代表方差，n代表監(jiān)測序列的長度，i∈[-n+1，n+1]

(9)

其中，Xn代表監(jiān)測序列的值

(10)

其中，Cij代表第i個監(jiān)測序列與第j個監(jiān)測序列的相似度。

自組織映射(self-organizing maps)算法是一種無導師的聚類方法，可以將多維度的監(jiān)測序列映射成二維離散變量。SOM網(wǎng)絡在樣本聚類、樣本的組合優(yōu)化等問題上有著廣泛的應用，具有優(yōu)良的自組織、自適應等特性。SOM網(wǎng)絡沒有中間層，只有監(jiān)測序列輸入層與輸出層，網(wǎng)絡將監(jiān)測序列類別映射到輸出層的某個神經(jīng)元。在訓練階段，各神經(jīng)元競爭學習，每個監(jiān)測序列通過計算到神經(jīng)元之間的距離得到激活結點。計算出激活結點后，對相關結點的參數(shù)迭代更新；在測試階段，計算待分類的監(jiān)測序列與各神經(jīng)元之間的距離，距離最小的神經(jīng)元為該測試序列的類別。

監(jiān)測序列相似度矩陣的每行Ci=[Ci1，Ci2…Cin](i=1，2…n) 代表SOM網(wǎng)絡的一個待訓練監(jiān)測序列，Wj=[Wi1，Wi2…Win](j=1，2…l，l為輸出層神經(jīng)元的總量)代表輸出層神經(jīng)元的權重向量，通過式(11)計算出與待訓練監(jiān)測序列最匹配的神經(jīng)元k。計算出最匹配的神經(jīng)元k后，通過式(12)找到獲勝神經(jīng)元的鄰域半徑，用式(13)對最匹配的神經(jīng)元及其鄰域內的神經(jīng)元進行權值更新。對上述操作進行多次迭代，直到映射關系不在發(fā)生顯著變化

(11)

其中，k代表最匹配神經(jīng)元的編號，Wj表示與第j個神經(jīng)元相關的權值系數(shù) (j=1，2…l，l代表輸出層的總量)，Ci代表式(10)的一行

(12)

式中：neighbor_redius代表鄰域半徑，neighbor0代表鄰域的初始值，neighbor_para代表鄰域參數(shù)，t代表網(wǎng)絡迭代更新的次數(shù)

(13)

式中：wk(t) 代表最匹配的神經(jīng)元節(jié)點更新后的權值，wk(t-1) 代表最匹配神經(jīng)元節(jié)點上次一更新的權值系數(shù)，Ci代表式(10)中的一行，ηt代表學習速率，式(14)為ηt的計算公式，式(11)為dk的計算公式，式(15)為σt的計算公式

(14)

其中，learn0為初始的學習速率，learn_para為學習速率參數(shù)，t代表迭代次數(shù)

(15)

其中，σ0代表鄰域函數(shù)的初始值，neighbor_para代表鄰域參數(shù)，t代表網(wǎng)絡迭代更新的次數(shù)。

與K-Means相比，監(jiān)測序列采用SOM神經(jīng)網(wǎng)絡進行聚類有以下優(yōu)點：①在聚類之前，K-Means方法需要確定監(jiān)測序列的類別總量(K值)，而監(jiān)測序列的類別總量與SOM神經(jīng)網(wǎng)絡輸出層神經(jīng)元個數(shù)是多對多的關系，無需指定該值，因此K值對K-Means方法影響較大；②監(jiān)測序列使用K-Means聚類后，只對相應簇的中心迭代更新，而SOM神經(jīng)網(wǎng)絡聚類會迭代更新最匹配神經(jīng)元及鄰域神經(jīng)元的權重系數(shù)，因此，SOM神經(jīng)網(wǎng)絡聚類相對于K-Means聚類不易受噪聲點的影響，抗干擾性更強；③SOM神經(jīng)網(wǎng)絡輸出層的拓撲關系較明確，可視化較好。

2.2 監(jiān)測序列預處理

監(jiān)測數(shù)據(jù)在采集的過程中不可避免的會出現(xiàn)漏采的現(xiàn)象，因此需要對數(shù)據(jù)的缺失值進行填充。本文利用牛頓插值法進行缺失數(shù)據(jù)處理，先求出f(x)的各階差商，再利用式(16)進行缺失值填充。

對于異常檢測，監(jiān)測序列的標注大部分是正常的，只有少量序列的標注為異常。在檢測器構建階段，如果標注為異常的監(jiān)測序列較少，檢測器從異常類學習到的信息就少，很難檢測異常類。直接使用原始數(shù)據(jù)建模會導致模型偏向于正常一類，導致異常點的漏報與誤報。本文對監(jiān)測序列進行SMOTE過采樣操作，采樣之后正常監(jiān)測序列的數(shù)量：異常監(jiān)測序列的數(shù)量≈1∶1。

由于異常對象多種多樣，直接使用原始值檢測器的效果較差，需要考慮監(jiān)測序列的數(shù)據(jù)結構與一些隱含特性，從多方面對原始序列進行特征轉換。本文參考Opprentice框架[13]和動態(tài)數(shù)列提取特征的方法，對原始監(jiān)測序列進行統(tǒng)計特征轉換、擬合特征轉換、分解特征轉換

f(x)=f(x0)+f[x0,x1](x-x0)+
f[x0,x1,x2](x-x0)(x-x1)+…+
f[x0,x1,…,xn-2,xn-1](x-x0)(x-x1)…
(x-xn-2)(x-xn-1)+f[x0,x1,…,xn-1,xn]
(x-x0)(x-x1)…(x-xn-1)(x-xn)

(16)

2.3 特征構建

監(jiān)測序列是在時間維度上呈現(xiàn)一定規(guī)律性的動態(tài)序列，對原始監(jiān)測序列進行統(tǒng)計特征轉換、擬合特征轉換、分解特征轉換，具體的特征見表1。

表1 特征

監(jiān)測序列的統(tǒng)計特征對業(yè)務人員關注的指標進行統(tǒng)計方面的刻畫。如果監(jiān)測的業(yè)務指標出現(xiàn)非常大或非常小的反常變化，該業(yè)務指標在反常值的時間點可能出現(xiàn)了異常。業(yè)務指標的z-score值代表監(jiān)測序列的每個點相對于整體基線的偏離程度，距離基線越遠越有可能是異常，很多現(xiàn)實的業(yè)務一天一周期，因此計算整體基線時以天為單位。業(yè)務指標的同比差分反映了現(xiàn)時刻與上一周期同時刻的差值情況，環(huán)比差分反映了現(xiàn)時刻與上一時刻的差值情況，同比差分或環(huán)比差分值越大，越有可能是異常。

監(jiān)測序列的分解特征將序列分解成周期序列、趨勢序列、隨機序列，如果分解后的序列存在非常大或非常小的反常變化，該業(yè)務指標在反常值的時段可能出現(xiàn)了異常。在文件系統(tǒng)中，磁盤利用率是業(yè)務人員很關注的一個指標，將該指標分解后可從趨勢序列分析使用情況，趨勢序列陡增或持續(xù)增加考慮異?；驍U容，趨勢序列陡降或一直很低考慮異?；蚩s容；對于具有周期性的業(yè)務指標，分解后對周期序列進行分析，如果某個周期序列相對于其它周期非常大或非常小，則該業(yè)務指標在反常值的時間點可能出現(xiàn)了異常。每個業(yè)務指標都有隨機成分，如果分解后的隨機序列存在非常大的波動，則該業(yè)務指標在反常值的時間點可能出現(xiàn)了異常。小波分解對業(yè)務指標進行頻率方面的刻畫，按天將監(jiān)測序列分解為高頻、中頻、低頻3個序列，高頻序列對監(jiān)測指標短期內的陡升或陡降類異常識別較好，低頻序列對監(jiān)測指標長期內的持續(xù)升高類異常識別較好。

監(jiān)測序列的擬合特征綜合序列的趨勢性、周期性、歷史性對序列的期望值進行預測，真實值與期望值差別差值越大，相應的指標在異常值的時間點可能出現(xiàn)了異常。監(jiān)測序列是動態(tài)數(shù)列，在時間維度上具有一定的規(guī)律性，預測點受相鄰點的變化規(guī)律影響較大，距離越遠的點對預測的貢獻度越小。監(jiān)測序列的指數(shù)平滑預測法可以消除毛刺，通過平滑系數(shù)控制歷史值對當前預測值的影響，對持續(xù)上升或持續(xù)下降類的業(yè)務異常識別效果較好；監(jiān)測序列的移動均值法將窗口內的序列均值作為期望值，序列值與期望值差值越大越有可能是異常，移動均值預測法可以消除序列的隨機噪聲；序列的三次指數(shù)平滑預測法綜合趨勢、周期、隨機因素對期望值做出預測，距離預測點越遠對預測點的影響越小，序列值與期望值差值越大越有可能是異常；ARIMA對原始序列進行差分操作去除序列不平穩(wěn)因素，結合歷史值與歷史噪聲值對期望值進行預測，序列值與期望值差值越大越有可能是異常。

監(jiān)測序列特征化后，某些特征對于檢測的貢獻度較小或有冗余特征，為了降低時間復雜度進行特征選擇與特征降維。序列標注與特征之間的互信息描述了特征包含標注的信息量，將互信息作為貢獻度，計算出貢獻度后本文選取貢獻較大的度前70%特征作為候選特征。檢測器進行異常檢測時可能存在冗余特征，需要對候選特征進行降維處理，采用PCA進行主成分提取(主成分占比90%)。

3 基于集成學習的異常點檢測系統(tǒng)

圖2是基于集成學習的異常點檢測算法的基本框架，檢測流程包括離線訓練檢測器、在線使用檢測器、檢測器迭代更新。離線訓練階段，將具有相同特性的監(jiān)測序列歸為一類形成該類的訓練集，利用訓練集訓練出該類的最優(yōu)檢測器。在線檢測階段，根據(jù)訓練好的網(wǎng)絡識別出待測試監(jiān)測序列的所屬類別，用相應類的檢測器進行檢測。檢測器迭代更新階段，將檢測器檢測為異常但標注為正常的監(jiān)測序列、檢測器檢測為正常但標注為異常的監(jiān)測序列、新收集的監(jiān)測序列作為回注訓練集，定期用回注訓練集對檢測器迭代更新。離線檢測器構建提供檢測器是正反饋，在線檢測器提供錯檢、漏檢樣本是負反饋，檢測的整個流程是閉環(huán)，隨著迭代輪數(shù)的增加，異常點檢測系統(tǒng)的準度逐漸增加，抗干擾能力逐漸增強，直至達到一定程度的收斂。

圖2 異常點檢測框架

3.1 單檢測器構建

對監(jiān)測序列進行歸屬類計算、預處理、特征化、篩選降維、樣本均衡后，形成離群點檢測器所需要的數(shù)據(jù)格式，每個簇采用相同的訓練方式。對每個簇按8∶2劃分離線訓練集與在線測試集，在離線訓練集上進行訓練，在線測試集上進行檢測。單檢測器的結構為Xgboost檢測器、Random forest檢測器、Bagging檢測器(基學習器為Logistic回歸)、Bagging檢測器(基學習器為神經(jīng)網(wǎng)絡)，使用網(wǎng)格搜索進行參數(shù)調優(yōu)。

3.2 多檢測器融合

檢測器融合綜合考慮不同模型的優(yōu)缺點，將它們的結果融合到一起對于檢測結果的提高有一定幫助。檢測器融合的優(yōu)點有：①減少因誤選單檢測器而導致泛化性能不佳的風險；②降低陷入局部極小點的風險；③可以擴大假設空間，得到更好的近似。

本文考慮到Random forest檢測器是低方差的模型，Xgboost檢測器是低偏差的模型，利用Stacking方法將兩者融合，可能會在低方差與低偏差之間找到最優(yōu)解。設計了兩層Stacking模型，第一層包含3個低方差模型：Random forest檢測器、Bagging檢測器(基檢測器為邏輯回歸)和Bagging檢測器(基檢測器為神經(jīng)網(wǎng)絡)，在生成監(jiān)測序列樣本時每個檢測器進行5輪交叉驗證；融合模型的第二層是Xgboost檢測器，第二層利用第一層生成的監(jiān)測樣本訓練與預測。融合結構如圖3所示。

圖3 檢測器融合

3.3 實驗評估

本文采用真實場景帶標記的數(shù)據(jù)集(http://iops.ai/，數(shù)據(jù)量約300兆)進行檢測，異常樣本標記為1，正常樣本標記為0，共26個監(jiān)測指標。聚類后形成6類序列，每類序列分為離線檢測器訓練數(shù)據(jù)和在線檢測器使用數(shù)據(jù)(隨機劃分)，劃分比例為8∶2，離線檢測器訓練數(shù)據(jù)分為訓練集和模型選擇驗證集(隨機劃分)，劃分比列為7∶3。

實驗環(huán)境為：英特爾i7 8700K(3.7GHz,六核心)，金士頓內存條(16 G)。

檢測器構建階段采用ROC曲線對訓練的結果評估，ROC曲線是反映敏感度和特異度連續(xù)變量的綜合指標，ROC曲線的橫坐標為FPR(false positive rate)，縱坐標為TPR(true positive rate)，計算方式為式(17)

(17)

其中，TP(true positive)為真陽性，代表數(shù)據(jù)集的標注為異常且檢測器檢測為異常的個數(shù)；FP(false positive)為假陽性，代表數(shù)據(jù)集的標注為正常且檢測器檢測為異常的個數(shù)；TN(true negative)為真負性，代表數(shù)據(jù)集的標注為正常且檢測器檢測為正常的個數(shù)；FN(false negative)為假負性，代表數(shù)據(jù)集的標注為異常且檢測器檢測為正常的個數(shù)。

每個監(jiān)測序列的異常概率值可以作為檢測閾值，得到一組FPR和TPR，利用所有組繪制得到ROC曲線。計算ROC曲線與水平軸之間的面積可以得到AUC，AUC的范圍為[0,1]，AUC≈1，說明檢測器檢測結果接近完美，AUC在0.7-0.9之間，說明檢測器檢測精度較高，AUC=0.5，說明檢測器檢測效果很差。

訓練后序列1在離線驗證集上融合前后的ROC如圖4(其它的簇的AUC值波動在[-0.02,0.03]，融合后的檢測器AUC值均優(yōu)于單檢測器)所示。

圖4 融合檢測模型與單一檢測模型ROC曲線

利用在線測試數(shù)據(jù)評估各檢測器的效果，評估的標準為式(18)F1-score，表2為各檢測器的F1-score均值(在6類監(jiān)測序列的測試結果上取了均值)，表中效果最好的是融合檢測器，表明檢測器的融合對于檢測結果的提升有非常大的幫助

(18)

其中，precision為檢測的準確率，recall為檢測的召回率。

表2 在線檢測結果

準確率precision的計算方式如下

(19)

其中，TP(true positive)為真陽性，代表數(shù)據(jù)集的標注為異常且檢測器檢測為異常的個數(shù)；FP(false positive)為假陽性，代表數(shù)據(jù)集的標注為正常且檢測器檢測為異常的個數(shù)。

召回率recall的計算方式如下

(20)

其中，F(xiàn)N(false negative)為假負性，代表數(shù)據(jù)集的標注為異常且檢測器檢測為正常的個數(shù)。

4 結束語

本文設計了一個異常點檢測系統(tǒng)，系統(tǒng)由檢測器的構建、檢測器的使用、檢測器的迭代更新構成。離線檢測器構建提供檢測器是正反饋，在線檢測器提供錯檢、漏檢樣本是負反饋，隨著迭代次數(shù)的增加，系統(tǒng)的精度會逐漸提高；異常點檢測系統(tǒng)的特征構建階段可以增加與修改特征，擴展性較好。對異構的檢測器進行基于委員會的學習，提高了異常點檢測的精度與泛化性。實驗中的隨機森林與Xgboost均可并行計算，對于工業(yè)界的大數(shù)據(jù)具有適用性。異常點檢測特征依賴于人的先驗知識，如何利用深度學習模型自動學習特征是本文下一步的研究重點[14]。