一種基于Grubbs和孤立森林的多維序列異常檢測方法

王銳

（中國移動(dòng)通信集團(tuán)廣東有限公司，廣東 廣州 510623）

0 引言

異常檢測[1-3]也稱為離群檢測，用于發(fā)現(xiàn)數(shù)據(jù)流中的異常類型并確定其發(fā)生的詳細(xì)信息。但是隨著移動(dòng)通信的發(fā)展，整個(gè)通信業(yè)務(wù)急劇膨脹，為了適配多種終端、不同接入方式，運(yùn)行場景日趨復(fù)雜，各類監(jiān)控指標(biāo)繁多且數(shù)據(jù)量巨大，海量多維序列數(shù)據(jù)給運(yùn)維人員帶來更高的挑戰(zhàn)。

面對大數(shù)據(jù)場景，傳統(tǒng)的單指標(biāo)檢測結(jié)果可能會(huì)出現(xiàn)片面性問題，且效率較低。文獻(xiàn)[4]綜述了多維時(shí)間序列異常檢測算法，并指出了要注意盡量降低算法的復(fù)雜度以及開展實(shí)時(shí)監(jiān)測的研究；文獻(xiàn)[5-7]針對智能運(yùn)維、安全駕駛和交易消費(fèi)等領(lǐng)域，分別提出了基于VRNN、自動(dòng)編碼器和模糊孤立森林等算法，研究了多維序列異常檢測算法及應(yīng)用，并取得良好的效果。上述研究方法中部分算法復(fù)雜度較高，面對多樣化的海量數(shù)據(jù)，算法模型的泛化能力和計(jì)算開銷有一定局限。因此，本文提出了一種多維時(shí)間序列的異常檢測算法，采用優(yōu)化的孤立森林（iForest,isolation Forest）算法，實(shí)現(xiàn)了較好的異常檢測效果。該算法易于理解，計(jì)算開銷小，并且泛化能力和實(shí)用性較好。

1 單指標(biāo)異常檢測的局限

傳統(tǒng)的單指標(biāo)異常檢測就是KPI異常檢測[8]，也是運(yùn)維領(lǐng)域中的一個(gè)重要環(huán)節(jié)。KPI指的是對系統(tǒng)、服務(wù)等運(yùn)維對象的監(jiān)控指標(biāo)（如訪問量、利用率等），其數(shù)據(jù)是按發(fā)生的時(shí)間先后順序排列而成的數(shù)列，也就是時(shí)間序列。

為了發(fā)現(xiàn)異常數(shù)據(jù)，建立了一個(gè)單指標(biāo)的時(shí)間序列異常檢測系統(tǒng)[9]，基本遵循以下步驟：

（1）數(shù)據(jù)采集：數(shù)據(jù)流的持續(xù)采集；

（2）正常行為建模：識(shí)別異常的第一步是建立一個(gè)模型，設(shè)計(jì)一個(gè)統(tǒng)計(jì)測試來確定數(shù)據(jù)點(diǎn)，如果模型沒有解釋它們，則可能就是異常點(diǎn)；

（3）異常行為檢測：通過對比正常模型發(fā)現(xiàn)異常的數(shù)據(jù)，并描述異常的各種屬性。

時(shí)間序列異常檢測系統(tǒng)通過觀察度量行為的各個(gè)方面，假設(shè)數(shù)據(jù)變化滿足一種分布（如高斯分布或者正態(tài)分布）來計(jì)算動(dòng)態(tài)閾值模型，對數(shù)據(jù)按照一定的規(guī)律波動(dòng)來判斷異常是否有效，判別速度快。通過應(yīng)用異常檢測算法將每個(gè)時(shí)間點(diǎn)標(biāo)記為正常/異常或者預(yù)測某個(gè)點(diǎn)的信號，然后測試該點(diǎn)實(shí)際值是否與預(yù)測值相差足夠大以將其視為異常。

但是，一旦數(shù)據(jù)在某一段時(shí)間變化幅度加大，數(shù)據(jù)不夠平滑，對于多指標(biāo)（多維序列）數(shù)據(jù)來說，復(fù)雜度更高、無效和干擾信息更加嚴(yán)重。針對多維度時(shí)間序列，如果需要將每個(gè)維度指標(biāo)單獨(dú)進(jìn)行檢測，會(huì)存在效率低下的問題；另一方面，大多數(shù)檢測只選取獨(dú)立的維度進(jìn)行分析，很難發(fā)現(xiàn)相關(guān)聯(lián)的異常指標(biāo)數(shù)據(jù)，不利于整體分析問題。

2 多維序列異常檢測

2.1 孤立森林的簡介

孤立森林（iForest）[10-11]屬于集成學(xué)習(xí)方法，廣泛應(yīng)用于異常檢測領(lǐng)域。iForest對數(shù)據(jù)集的適應(yīng)能力很強(qiáng)，同時(shí)在訓(xùn)練樣本以及樣本屬性的選擇方面都是隨機(jī)的，在處理多維序列存在一定的優(yōu)勢。其算法流程大致如下：

（1）從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇φ個(gè)點(diǎn)作為子樣本，放入一棵孤立樹的根節(jié)點(diǎn)；

（2）隨機(jī)指定一個(gè)維度，在當(dāng)前節(jié)點(diǎn)數(shù)據(jù)范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)切割點(diǎn)p，切割點(diǎn)產(chǎn)生于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中指定維度的最大值與最小值之間；

（3）此切割點(diǎn)的選取生成了一個(gè)超平面，將當(dāng)前節(jié)點(diǎn)數(shù)據(jù)空間切分為2個(gè)子空間：把當(dāng)前所選維度下小于p的點(diǎn)放在當(dāng)前節(jié)點(diǎn)的左分支，把大于等于p的點(diǎn)放在當(dāng)前節(jié)點(diǎn)的右分支；

（4）在節(jié)點(diǎn)的左分支和右分支節(jié)點(diǎn)遞歸步驟，不斷構(gòu)造新的葉子節(jié)點(diǎn)，直到葉子節(jié)點(diǎn)上只有一個(gè)數(shù)據(jù)（無法再繼續(xù)切割）或樹已經(jīng)生長到了所設(shè)定的高度，此時(shí)獲得了一個(gè)iTree。

獲得t個(gè)iTree之后，iForest訓(xùn)練就結(jié)束，然后可以用生成的iForest來評估測試數(shù)據(jù)。對于一個(gè)訓(xùn)練數(shù)據(jù)X，令其遍歷每一棵iTree，然后計(jì)算X最終落在每個(gè)樹第幾層（X在樹的高度），可以得出X在每棵樹的高度平均值。獲得每個(gè)測試數(shù)據(jù)的高度平均值后，可以設(shè)置一個(gè)閾值（邊界值），高度平均值低于此閾值的測試數(shù)據(jù)即為異常。

2.2 改進(jìn)的孤立森林異常檢測

孤立森林檢測算法具有較大的隨機(jī)性，且對噪聲維度魯棒性不夠強(qiáng)，可靠性較低。在建立樹的同時(shí)，可能會(huì)有部分維度的信息沒有被完全利用，這些因素都影響了樹的構(gòu)建，導(dǎo)致在實(shí)際異常檢測中一些檢測點(diǎn)會(huì)被誤判，使檢測結(jié)果的準(zhǔn)確率低下。

鑒于上述這些問題，本文提出一種基于格拉布斯準(zhǔn)則（Grubbs算法）的孤立森林算法改進(jìn)，該算法邏輯簡潔且實(shí)用性強(qiáng)，通過引入格拉布斯準(zhǔn)則，增加每個(gè)指標(biāo)檢測的正常值閾值，同時(shí)利用孤立森林進(jìn)行離群點(diǎn)檢測。實(shí)驗(yàn)結(jié)果表明，該算法具有較好的檢測效果，與孤立森林相比，檢測結(jié)果更加穩(wěn)定，可以過濾一些無關(guān)維度造成的影響。改進(jìn)的算法流程說明如下：

第一步：

對同一系統(tǒng)中多個(gè)設(shè)備所對應(yīng)的指標(biāo)同時(shí)進(jìn)行檢測，實(shí)時(shí)采集各個(gè)指標(biāo)數(shù)據(jù)，每個(gè)指標(biāo)即對應(yīng)一個(gè)維度，各指標(biāo)數(shù)據(jù)組成多維序列。對指標(biāo)的采樣時(shí)間粒度可根據(jù)實(shí)際需要進(jìn)行設(shè)定，如5分鐘。

預(yù)先獲取多維序列的歷史數(shù)據(jù)，選取的歷史時(shí)間范圍可以為一年或數(shù)月，通常是相對完整的時(shí)間周期。

進(jìn)一步地，由于任一系統(tǒng)中各設(shè)備的運(yùn)行狀態(tài)在不同的時(shí)間片段內(nèi)存在規(guī)律性的變化，如對于一個(gè)IT系統(tǒng)其各設(shè)備的使用率在每天白天和晚上會(huì)存在較大的差別，或者在一周中工作日與節(jié)假日也會(huì)存在差別，因此在獲取各指標(biāo)的正常閾值區(qū)間時(shí)，需要根據(jù)各時(shí)間片段內(nèi)的規(guī)律進(jìn)行劃分。時(shí)間片段的劃分規(guī)則可根據(jù)實(shí)際系統(tǒng)的運(yùn)行規(guī)則進(jìn)行設(shè)置，如一周的時(shí)間按照一天進(jìn)行劃片，得到的時(shí)間片段為周一、周二、……；也可以將一天的時(shí)間按一個(gè)小時(shí)進(jìn)行劃分，得到的時(shí)間片段為00:00～00:59、01:00～01:59、……、23:00～23:59；還可以將一天的時(shí)間按照白天和晚上進(jìn)行劃分等。

多維序列歷史數(shù)據(jù)通過時(shí)間劃片，建立了各個(gè)時(shí)間片段對應(yīng)的多維序列組。在每個(gè)維度序列組內(nèi)，通過預(yù)設(shè)的閾值計(jì)算方法，獲得指標(biāo)（即維度）在對應(yīng)的時(shí)間片段內(nèi)的正常閾值區(qū)間，從而得到各指標(biāo)在不同的時(shí)間片段內(nèi)的規(guī)律。本文采用閾值計(jì)算方法是Grubbs離群數(shù)據(jù)檢測方法。

Grubbs離群數(shù)據(jù)檢測方法[12]以任一維度i的采樣值組成數(shù)據(jù)集Xi={Xij}，尋找其中最大的z-score，也就是計(jì)算每一個(gè)采樣值Xij對平均值偏離與標(biāo)準(zhǔn)差Si的比值，其中z-score的計(jì)算如下：

其中，zij即為z-score；為數(shù)據(jù)的均值；Si為數(shù)據(jù)的標(biāo)準(zhǔn)差。

如果z-score大于給定顯著性水平a下的離群檢測的臨界值gc，則認(rèn)定該數(shù)為離群值，并把這個(gè)值進(jìn)行剔除。其中，tc是一個(gè)選定的值，它服從具有n-2個(gè)自由度的t分布。

通過上述Grubbs離群數(shù)據(jù)檢測算法對數(shù)據(jù)集進(jìn)行清洗后，所述數(shù)據(jù)集合中將不存在z-score大于所述臨界值gc的采集值，從而得到該維度i對應(yīng)的正常閾值區(qū)間Oseti。

第二步：

獲取歷史數(shù)據(jù)作為訓(xùn)練集，歷史時(shí)間可為近期范圍，如最近一個(gè)月內(nèi)。從所述訓(xùn)練集中進(jìn)行采樣，通過孤立森林算法，構(gòu)建異常檢測模型。

上述異常檢測模型是通過歷史數(shù)據(jù)訓(xùn)練得到的，建議定期重新訓(xùn)練更新。

第三步：

將所有同一采樣時(shí)間采集到的各指標(biāo)數(shù)據(jù)組成待測的多維序列，輸入到第二步訓(xùn)練得到異常檢測模型，輸出得到異常時(shí)間點(diǎn)集合，再結(jié)合各維度對應(yīng)的正常閾值區(qū)間進(jìn)行排除比對處理，最后得到改進(jìn)算法的最終異常點(diǎn)集合。

綜合以上三步，整體基于Grubbs和孤立森林的多維序列異常檢測算法說明如下：

（1）對多維序列的歷史數(shù)據(jù)中，按時(shí)間劃片規(guī)則進(jìn)行分組，分別針對每個(gè)時(shí)間片段中多維序列數(shù)據(jù)集使用Grubbs算法求得Oset，得到各個(gè)維度數(shù)據(jù)在每個(gè)時(shí)間片段內(nèi)的正常閾值區(qū)間；

（2）將近期多維序列歷史數(shù)據(jù)通過孤立森林算法，獲得異常檢測模型ForestModel；

（3）對待測的當(dāng)前多維序列采用異常檢測模型ForestModel進(jìn)行檢測，得到異常序列集合Anomaly；

（4）結(jié)合待測的多維序列的采樣時(shí)間對應(yīng)的時(shí)間片的Oset，對異常序列集合Anomaly進(jìn)行排除比對，同一時(shí)間片段內(nèi)異常序列集合Anomaly中存在Xij不在所對應(yīng)維度的正常閾值區(qū)間，則標(biāo)注為最終異常序列，Xij為異常數(shù)據(jù)值，最后遍歷得到最終的異常序列集合Anomaly*。

3 實(shí)驗(yàn)過程

3.1 數(shù)據(jù)介紹

實(shí)驗(yàn)中采用的數(shù)據(jù)為某IT系統(tǒng)運(yùn)行環(huán)境采集的CPU使用率、內(nèi)存使用率、數(shù)據(jù)庫等待事件等多個(gè)指標(biāo)的一個(gè)數(shù)據(jù)集，時(shí)間跨度為2020年9月至11月共計(jì)8 000余條的數(shù)據(jù)集，時(shí)間粒度為15分鐘。篩選了部分有價(jià)值的檢測指標(biāo)后，對數(shù)據(jù)進(jìn)行預(yù)處理，將要進(jìn)行訓(xùn)練的數(shù)據(jù)如表1所示：

表1 多維序列數(shù)據(jù)示例

多維時(shí)間序列數(shù)據(jù)展示圖如圖1所示?？梢钥闯觯瑫r(shí)間序列的數(shù)據(jù)中有一些突增突降的點(diǎn)，這些點(diǎn)可能是異常值，而各個(gè)指標(biāo)之間發(fā)生突增突降的時(shí)間是相近的，證明各個(gè)指標(biāo)之間的異常情況是有關(guān)聯(lián)的。

圖1 多維時(shí)間序列數(shù)據(jù)展示圖

3.2 結(jié)果對比

對數(shù)據(jù)進(jìn)行了孤立森林算法訓(xùn)練，并得出相應(yīng)的模型，然后用2020年11月23日至25日系統(tǒng)采集15分鐘粒度總計(jì)288條的數(shù)據(jù)進(jìn)行擬合，初步得出了異常結(jié)果。如表2所示，選取25日下午3點(diǎn)至6點(diǎn)的時(shí)間段進(jìn)行展示，其中字段異常情況為0的時(shí)刻表示正常、-1的時(shí)刻表示異常。

表2 孤立森林算法檢測結(jié)果

在實(shí)際情況中，這兩天的時(shí)間段共有19處故障異常點(diǎn)。孤立森林算法找出的異常點(diǎn)共有43條，在展示的時(shí)間段中，部分模型找出的時(shí)間點(diǎn)與實(shí)際情況相吻合，但是與實(shí)際的結(jié)果相對比，有許多不關(guān)聯(lián)的時(shí)間點(diǎn)也被認(rèn)為是異常點(diǎn)，產(chǎn)生了誤判的情況。為了檢驗(yàn)?zāi)Ｐ偷膶?shí)際情況，畫出了模型的ROC曲線進(jìn)行模型評估。孤立森林ROC曲線圖如圖2所示。

圖2 孤立森林ROC曲線圖

ROC曲線被用于醫(yī)學(xué)、無線電、生物學(xué)等領(lǐng)域中，在機(jī)器學(xué)習(xí)領(lǐng)域也有很好的發(fā)展。ROC曲線越靠近上方，曲線下面積AUC越大，則檢測的準(zhǔn)確率越高，否則檢測準(zhǔn)確率越低[13]。從圖2可以看到，傳統(tǒng)的孤立森林模型的預(yù)測模型結(jié)果為72.7%，檢測效果一般。

接下來使用改進(jìn)后的孤立森林算法，首先利用Grubbs算法進(jìn)行建模，得到異常檢測模型以及各個(gè)指標(biāo)的正常閾值區(qū)間（為了便于計(jì)算比較，這里統(tǒng)一對應(yīng)為一個(gè)時(shí)間分片，即白天）。各個(gè)維度的正常值區(qū)間范圍如表3所示：

表3 各個(gè)維度的正常值區(qū)間范圍

利用Grubbs算法得出各個(gè)指標(biāo)的區(qū)間范圍，與孤立森林算法的模型所求得的異常時(shí)間點(diǎn)進(jìn)行比對排除，重新求得異常時(shí)間點(diǎn)。改進(jìn)的孤立森林算法檢測結(jié)果如表4所示。

表4 改進(jìn)的孤立森林算法檢測結(jié)果

經(jīng)過改進(jìn)算法后，異常時(shí)間點(diǎn)在原來的基礎(chǔ)上縮減到了32個(gè)，每個(gè)指標(biāo)中超出正常值的點(diǎn)也被標(biāo)注了出來。同樣，畫出ROC曲線進(jìn)行模型評估。改進(jìn)的孤立森林ROC曲線圖如圖3所示。

從圖3可以看出，AUC值提升至86.4%，整體效果比原來好了很多。如表5的兩個(gè)時(shí)間段，系統(tǒng)中出現(xiàn)異常的指標(biāo)為“Oracle連接數(shù)”與“數(shù)據(jù)庫等待事件數(shù)”，這兩個(gè)指標(biāo)可能是引起異常的主要原因。在實(shí)際情況中，該時(shí)間點(diǎn)確實(shí)如此，可見算法的檢測結(jié)果是準(zhǔn)確的。

表5 實(shí)際情況說明

圖3 改進(jìn)的孤立森林ROC曲線圖

4 結(jié)束語

本文提出的改進(jìn)算法使用了基于孤立森林算法與Grubbs算法對多維序列數(shù)據(jù)進(jìn)行異常檢測，實(shí)驗(yàn)結(jié)果表明，該算法能夠有效檢測出多維時(shí)間序列中存在的異常數(shù)據(jù)，且在處理海量數(shù)據(jù)過程中效率較高。目前該檢測方法已經(jīng)逐步代替了原來的固定閾值方法，應(yīng)用于業(yè)務(wù)開通領(lǐng)域IT系統(tǒng)運(yùn)維場景中各類指標(biāo)的監(jiān)控，經(jīng)過對比分析，面對海量數(shù)據(jù)計(jì)算效率更高，預(yù)警更加準(zhǔn)確，減少了無效告警，可以得到較好的檢測效果。同時(shí)，該方法也能廣泛應(yīng)用于移動(dòng)通信的各個(gè)業(yè)務(wù)領(lǐng)域。