劉峰麟，殷銘，袁平

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201620；3.重慶第二師范學(xué)院數(shù)學(xué)與信息工程學(xué)院，重慶 400067)

0 引言

異常檢測(cè)是從一個(gè)數(shù)據(jù)集合當(dāng)中檢測(cè)出和推斷的預(yù)期值不一致的數(shù)據(jù)元素，這些和預(yù)期值不吻合的數(shù)據(jù)元素，就被稱為異常。異常檢測(cè)廣泛應(yīng)用于信用卡欺詐檢測(cè)、網(wǎng)絡(luò)的入侵檢測(cè)等多個(gè)領(lǐng)域中[1]。隨著互聯(lián)網(wǎng)的高速發(fā)展，以及微服務(wù)的大規(guī)模實(shí)踐，龐大的后臺(tái)系統(tǒng)每天產(chǎn)生大量的時(shí)序數(shù)據(jù)。從大量的時(shí)序數(shù)據(jù)中準(zhǔn)確檢測(cè)出異常，及時(shí)觸發(fā)報(bào)警、排出故障對(duì)于保證互聯(lián)網(wǎng)服務(wù)的高可用有重大意義。異常檢測(cè)作為工業(yè)界服務(wù)器后臺(tái)智能運(yùn)維的重要組成部分，在各大公司都有著廣泛應(yīng)用。通過(guò)統(tǒng)計(jì)后臺(tái)機(jī)器的關(guān)鍵指標(biāo)信息構(gòu)成時(shí)序數(shù)據(jù)，進(jìn)行異常檢測(cè)，可以極大降低運(yùn)維成本。例如，騰訊有自研的Metis，采用統(tǒng)計(jì)、無(wú)監(jiān)督、監(jiān)督的方式對(duì)內(nèi)部應(yīng)用指標(biāo)進(jìn)行異常檢測(cè)，以降低運(yùn)維成本；推特、雅虎、領(lǐng)英等知名互聯(lián)網(wǎng)公司都開(kāi)源有自己的異常檢測(cè)工具。

異常從類型上可以分為三類：點(diǎn)異常、上下文異常、集合異常[1]。如果單個(gè)數(shù)據(jù)相對(duì)于其余數(shù)據(jù)可以被認(rèn)為是異常的，則該數(shù)據(jù)被稱作點(diǎn)異常。如果數(shù)據(jù)在特定上下文中是異常的，但是在其他情況下不是異常，則該數(shù)據(jù)被稱為上下文異常。如果數(shù)據(jù)所在的集合和該集合同處于一個(gè)數(shù)據(jù)集的其他兄弟集合不一致，則稱該集合為集合異常。時(shí)序數(shù)據(jù)的異常檢測(cè)有基于插件的方法和基于分解的方法[2]?；诓寮姆椒ㄊ歉鶕?jù)歷史時(shí)序數(shù)據(jù)集合，通過(guò)時(shí)序預(yù)測(cè)算法，得到未來(lái)一段時(shí)間的時(shí)序數(shù)據(jù)，若對(duì)于i時(shí)刻，存在，則認(rèn)為i時(shí)刻存在異常，反之則正常?；诓寮侵赴呀?jīng)典的時(shí)序數(shù)據(jù)預(yù)測(cè)算法作為插件，嵌入到異常檢測(cè)算法中。基于分解的方法是對(duì)時(shí)序數(shù)據(jù)進(jìn)行分解，提取周期、趨勢(shì)、季節(jié)性、自相關(guān)、非線性、偏態(tài)、峰度、林中小丘、李亞普諾夫指數(shù)等特征，通過(guò)檢測(cè)噪聲成分，如果噪聲分量，則認(rèn)為是異常，反之則正常。在時(shí)序數(shù)據(jù)的異常檢測(cè)中，Nikolay等人[2]采用3σ準(zhǔn)則，假定數(shù)據(jù)的分布服從正態(tài)分布。在正態(tài)分布的數(shù)據(jù)中，σ表示標(biāo)準(zhǔn)差，μ表示均值，3σ準(zhǔn)則認(rèn)為 99.7%的數(shù)據(jù)都在（μ-3σ,μ+3σ）區(qū)間內(nèi)。然而，在數(shù)據(jù)不是正太分布的情況下，無(wú)法選出正確閾值。Zhao[3]提出枚舉所有的閾值，并采用F-score作為度量來(lái)避免閾值選擇問(wèn)題。枚舉閾值的方式會(huì)帶來(lái)大量的計(jì)算，增加異常檢測(cè)的時(shí)間延遲，回避了閾值選擇的問(wèn)題。為了解決上述問(wèn)題，本文利用EWMA算法對(duì)時(shí)序數(shù)據(jù)進(jìn)行預(yù)測(cè)建模，然后利用衡量預(yù)測(cè)精度的指標(biāo)建立誤差模型，提出了一個(gè)基于DBSCAN的時(shí)序數(shù)據(jù)異常檢測(cè)閾值選擇算法來(lái)對(duì)每個(gè)指標(biāo)選擇閾值，從而檢測(cè)時(shí)序數(shù)據(jù)的異常，提高準(zhǔn)確率。

1 算法實(shí)現(xiàn)

1.1 時(shí)序模型

建立時(shí)序模型是指對(duì)后臺(tái)系統(tǒng)關(guān)鍵指標(biāo)信息采集的數(shù)據(jù)進(jìn)行建模，得到關(guān)鍵指標(biāo)數(shù)據(jù)的觀測(cè)時(shí)序數(shù)據(jù)模型和預(yù)測(cè)時(shí)序數(shù)據(jù)模型。時(shí)序模型建立的流程如圖1所示。關(guān)鍵指標(biāo)數(shù)據(jù)主要包括服務(wù)器運(yùn)行時(shí)的CPU、I/O等數(shù)據(jù)，通過(guò)監(jiān)控任務(wù)進(jìn)行定時(shí)采集可以得到關(guān)鍵指標(biāo)的書(shū)序數(shù)據(jù)。時(shí)序數(shù)據(jù)通過(guò)提前部署到服務(wù)器的程序進(jìn)行采集，因而一般有著固定時(shí)間間隔。通常時(shí)序數(shù)據(jù)是完整的，但在個(gè)別情況下時(shí)序數(shù)據(jù)會(huì)出現(xiàn)數(shù)據(jù)丟失的情況。建立時(shí)序模型首先通過(guò)多個(gè)數(shù)據(jù)點(diǎn)提取原始時(shí)序數(shù)據(jù)的采樣間隔時(shí)間，其中i是數(shù)據(jù)點(diǎn)的邏輯索引。若>interval，則進(jìn)行線性差值，插入序列到點(diǎn)i和i+1之間，插值后的到完整的觀測(cè)序列。經(jīng)典的時(shí)序預(yù)測(cè)算法有MA（Moving Average）、HW（Holt Winter）等，MA（Moving Average）是通過(guò)創(chuàng)建數(shù)據(jù)集的不同子集的平均數(shù)來(lái)分析數(shù)據(jù)點(diǎn)的技術(shù)。MA也是一種卷積，過(guò)濾掉了時(shí)間序列中的高頻擾動(dòng)，保留有用的低頻趨勢(shì)。MA通常與時(shí)間序列數(shù)據(jù)一起使用，以平滑短期波動(dòng)，突出長(zhǎng)期趨勢(shì)或周期。MA的衍生改進(jìn)算法版本有SMA、WMA等。EWMA（Exponentially Weighted Moving Average）又稱作EMA（Exponential Moving Average）是采用指數(shù)衰減加權(quán)因子的一階無(wú)限沖激響應(yīng)濾波器。對(duì)于時(shí)序數(shù)據(jù)的EWMA序列可以表示

其中，系數(shù)α表示權(quán)重降低的程度，是介于0和1之間的常數(shù)平滑因子。根據(jù)線性插值補(bǔ)全數(shù)據(jù)得到完整的觀測(cè)時(shí)序數(shù)據(jù)模型和預(yù)測(cè)時(shí)序數(shù)據(jù)，可以建立誤差模型。誤差模型的度量指標(biāo)由計(jì)算預(yù)測(cè)精度的三個(gè)主要指標(biāo)構(gòu)成，它們分別是：MAE（Mean Absolute Error）、MAPE（Mean Absolute Percentage Error）、MASE（Mean Absolute Scaled Error）。對(duì)于有：

圖1 時(shí)序模型建立流程圖

1.2 基于DBSCAN的閾值選擇算法

DBSCAN是經(jīng)典的聚類算法，它依靠數(shù)據(jù)點(diǎn)間定義的密度度量來(lái)聚類。它通過(guò)指定數(shù)據(jù)聚類最小點(diǎn)數(shù)MinPts，和聚類距離半徑ε自動(dòng)依據(jù)數(shù)據(jù)點(diǎn)的密度聚類。相對(duì)于我們熟悉的K-means算法，不需要指定聚類的個(gè)數(shù)。聚類是一種無(wú)監(jiān)督學(xué)習(xí)，它在樣本沒(méi)有標(biāo)記的情況可以把數(shù)據(jù)分成不同的組，聚類算法分組的依據(jù)是數(shù)據(jù)間的距離度量值。在本算法中，采用最常見(jiàn)的歐氏距離作為DBSCAN的距離度量算法。

閾值選擇對(duì)于時(shí)序數(shù)據(jù)異常檢測(cè)來(lái)說(shuō)至關(guān)重要。異常就是超過(guò)了一定閾值的數(shù)據(jù)，而閾值選擇是一個(gè)復(fù)雜的問(wèn)題，涉及到數(shù)據(jù)上下文等多個(gè)方面，好的閾值可以更準(zhǔn)確地區(qū)分出正常和異常。誤差模型中的閾值選擇可以看做是另一個(gè)數(shù)據(jù)序列的異常檢測(cè)問(wèn)題。閾值選擇不準(zhǔn)確的一個(gè)原因是閾值數(shù)據(jù)中存在噪點(diǎn)。從這個(gè)角度出發(fā)，在沒(méi)有樣本標(biāo)記的誤差模型數(shù)據(jù)中，運(yùn)用聚類算法剔除噪點(diǎn)，有助于選擇更加合適的閾值。本文提出的閾值選擇算法通過(guò)DBSCAN聚類算法在誤差模型中發(fā)現(xiàn)噪點(diǎn)數(shù)據(jù)序列。對(duì)每個(gè)一個(gè)誤差度量指標(biāo)剔除掉噪點(diǎn)后得到修正誤差模型k=1,2,3。然后，對(duì)修正誤差模型中的每一個(gè)誤差度量指標(biāo)計(jì)算對(duì)應(yīng)的誤差閾值thk：

其中，mean是均值函數(shù)，sd是標(biāo)準(zhǔn)差函數(shù)，α調(diào)諧系數(shù)。接下來(lái)，對(duì)數(shù)據(jù)點(diǎn)用投票機(jī)制進(jìn)行異常檢測(cè)，如果一個(gè)數(shù)據(jù)點(diǎn)的多個(gè)誤差度量指標(biāo)中過(guò)半數(shù)的誤差度量指標(biāo)超過(guò)修正誤差模型中對(duì)應(yīng)的閾值，則該數(shù)據(jù)點(diǎn)視為異常。經(jīng)過(guò)三個(gè)誤差度量指標(biāo)構(gòu)成的投票機(jī)制，超過(guò)半數(shù)以上的度量指標(biāo)判定該數(shù)據(jù)點(diǎn)異常的話，則最終認(rèn)定該數(shù)據(jù)點(diǎn)是一個(gè)異常數(shù)據(jù)點(diǎn)，如上述，最終得到的時(shí)序數(shù)據(jù)異常檢測(cè)的異常點(diǎn)結(jié)果可以用集合表示為

綜上，基于DBSCAN的閾值選擇算法的時(shí)序數(shù)據(jù)異常檢測(cè)過(guò)程描述如下:

2 實(shí)驗(yàn)結(jié)果與分析

本文的異常檢測(cè)實(shí)驗(yàn)依托于雅虎EGADS異常檢測(cè)框架，在EGADS框架的基礎(chǔ)上進(jìn)行二次開(kāi)發(fā)，實(shí)現(xiàn)該閾值選擇算法。EGADS是一個(gè)良好的異常檢測(cè)開(kāi)源平臺(tái)，它實(shí)現(xiàn)了基礎(chǔ)數(shù)據(jù)處理、時(shí)序建模以及常見(jiàn)異常檢測(cè)算法，開(kāi)發(fā)者只需要對(duì)框架定義好的接口實(shí)現(xiàn)自己的算法即可得到異常檢測(cè)的文本和圖像結(jié)果，這有助于算法的分析和實(shí)踐。

2.1 數(shù)據(jù)集

實(shí)驗(yàn)運(yùn)用的時(shí)序數(shù)據(jù)是后臺(tái)服務(wù)器的運(yùn)行情況數(shù)據(jù)，該數(shù)據(jù)以（timestamp,value）形式存儲(chǔ)。timestamp是以秒為單位的Unix時(shí)間戳，value是用小數(shù)表示的服務(wù)器CPU使用情況。實(shí)驗(yàn)數(shù)據(jù)通過(guò)后臺(tái)工程師進(jìn)行過(guò)異常標(biāo)注，并且從工程實(shí)踐的角度進(jìn)行了重新討論和審校，增加了部分異常點(diǎn)。

2.2 實(shí)驗(yàn)結(jié)果

在工程實(shí)踐過(guò)程中，異常點(diǎn)的報(bào)警有助于運(yùn)維人員及時(shí)根據(jù)異常點(diǎn)修復(fù)鄰近時(shí)間窗口的異常。因此結(jié)合實(shí)際需要，在統(tǒng)計(jì)檢測(cè)結(jié)果時(shí)，如果異常點(diǎn)所在的相鄰幾個(gè)時(shí)間窗口在存在真實(shí)異常，則表示異常召回成功。經(jīng)過(guò)實(shí)驗(yàn)，對(duì)CPU使用情況數(shù)據(jù)的異常檢測(cè)召回率、準(zhǔn)確率、假陰性率結(jié)果如表1所示。

表1

3 程序運(yùn)行界面效果

該程序運(yùn)行的界面效果如圖2所示，圖中紅色曲線是根據(jù)觀測(cè)數(shù)據(jù)進(jìn)行數(shù)據(jù)補(bǔ)全后建立的觀測(cè)時(shí)序數(shù)據(jù)數(shù)據(jù)模型繪制出的觀測(cè)時(shí)序圖，橫坐標(biāo)是時(shí)間，縱坐標(biāo)是觀測(cè)值。圖中藍(lán)色曲線是根據(jù)經(jīng)典的時(shí)序預(yù)測(cè)算法，在完整的時(shí)序觀測(cè)數(shù)據(jù)基礎(chǔ)上建立的預(yù)測(cè)時(shí)序數(shù)據(jù)模型繪制出的預(yù)測(cè)時(shí)序圖，橫坐標(biāo)是時(shí)間，縱坐標(biāo)是預(yù)測(cè)值。觀測(cè)時(shí)序圖中的黑色豎線是根據(jù)基于DBSCAN的時(shí)序數(shù)據(jù)異常檢測(cè)閾值選擇算法篩選的閾值，以投票機(jī)制對(duì)數(shù)據(jù)點(diǎn)誤差統(tǒng)計(jì)度量進(jìn)行篩檢測(cè)到的數(shù)據(jù)異常點(diǎn)。

圖2 時(shí)序數(shù)據(jù)異常檢測(cè)程序界面

4 結(jié)語(yǔ)

本文總結(jié)了時(shí)序數(shù)據(jù)異常檢測(cè)領(lǐng)域的有關(guān)文獻(xiàn)，闡述了該領(lǐng)域的研究和應(yīng)用現(xiàn)狀。針對(duì)時(shí)序數(shù)據(jù)異常檢測(cè)的閾值選擇問(wèn)題，提出了基于DBSCAN的時(shí)序數(shù)據(jù)異常檢測(cè)閾值選擇算法，該算法從閾值選擇角度優(yōu)化了時(shí)序數(shù)據(jù)異常檢測(cè)的效果，具有實(shí)際工程價(jià)值。實(shí)驗(yàn)部分基于EGADS進(jìn)行二次開(kāi)發(fā)，在一個(gè)后臺(tái)服務(wù)器運(yùn)行數(shù)據(jù)上進(jìn)行了測(cè)試，效果較好。

時(shí)序數(shù)據(jù)的異常檢測(cè)是當(dāng)下智能運(yùn)維的重要組成部分[4]。今后還可以從以下幾個(gè)方面深入，一，在時(shí)序數(shù)據(jù)建模上充分考慮周期性、季節(jié)性等特征；二，該算法檢測(cè)異常的時(shí)間窗口較大，在時(shí)序預(yù)測(cè)和誤差度量模型上改進(jìn)，減小時(shí)間窗口；三，時(shí)序數(shù)據(jù)聚類效果好壞的一個(gè)關(guān)鍵因素是選擇的距離度量算法是否能很好地適應(yīng)時(shí)序數(shù)據(jù)的特征，考慮改進(jìn)簡(jiǎn)單的歐氏距離度量算法，獲得更適應(yīng)時(shí)序數(shù)據(jù)特征的距離度量算法；四，在時(shí)序數(shù)據(jù)異常檢測(cè)過(guò)程當(dāng)中引入深度學(xué)習(xí)，進(jìn)一步優(yōu)化傳統(tǒng)算法的效果。