作者： 彭冬

1. 摘要

本文介紹了大規(guī)模時序數(shù)據(jù)自動異常檢測的通用和可擴展框架。能夠在早期檢測到系統(tǒng)異常，無論在維護用戶數(shù)據(jù)一致性方面，還是在保護企業(yè)免受惡意攻擊方面都發(fā)揮著非常關(guān)鍵的作用。用于異常檢測的現(xiàn)有技術(shù)在可擴展性和易用性上都存在很大問題。我們在雅虎（EGADS）的系統(tǒng)設(shè)計了基于異常檢測和預(yù)測模型構(gòu)建的異常過濾層，用于準(zhǔn)確地進行時序數(shù)據(jù)的異常檢測。我們比較了我們的方法與其他異常檢測系統(tǒng)對實時和合成數(shù)據(jù)的不同時間序列特征。EGADS框架在精度和召回率上提高了50%～60％。

2. 簡介

雖然計算硬件和軟件的快速發(fā)展已經(jīng)極大提高了應(yīng)用程序的可靠性，但是在大型集群中仍然存在大量的軟件錯誤和硬件故障。系統(tǒng)要求7*24小時不間斷運行，因此，對這些系統(tǒng)的持續(xù)監(jiān)控就至關(guān)重要。從數(shù)據(jù)分析的角度來看，這意味著不間斷地監(jiān)控大量的時間序列數(shù)據(jù)，以便檢測潛在的故障或異常現(xiàn)象。由于實際中的系統(tǒng)異常或者軟件BUG可能會非常多，通過人工監(jiān)控幾乎是不可能的，因此非常有必要使用機器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)進行自動化異常檢測。

異常值本質(zhì)上是一個數(shù)據(jù)點。通常，大多數(shù)應(yīng)用程序中的數(shù)據(jù)是由一個或多個反映系統(tǒng)功能的程序產(chǎn)生的。當(dāng)?shù)讓討?yīng)用程序以不正常的方式運行時，它就會產(chǎn)生異常值。快速高效地發(fā)現(xiàn)這些異常值非常有價值，比如：入侵檢測、信用卡欺詐、傳感器事件、醫(yī)療診斷、執(zhí)法等。

我們在雅虎的系統(tǒng)被稱為EGADS，它可以準(zhǔn)確和可擴展地檢測時間序列異常。 EGADS將預(yù)測、異常檢測和警報分為三個單獨的組件，允許人員將自己的模型添加到任何組件中。本文重點介紹后兩個組件。

EGADS是首個靈活、準(zhǔn)確且可擴展的異常檢測綜合系統(tǒng)。 EGADS框架與異常檢測基準(zhǔn)數(shù)據(jù)已經(jīng)一起開源，旨在幫助學(xué)者和行業(yè)合作開發(fā)新的異常檢測模型。在雅虎，EGADS每天被許多團隊用于數(shù)百萬次的時間序列異常檢測工作。

整體架構(gòu)

EGADS框架由三個主要部分組成：時間序列建模模塊（TMM）、異常檢測模塊（ADM）和報警模塊（AM）。給定一個時間序列，TMM組件模擬產(chǎn)生時間序列，由ADM和AM組件進行消費處理，分別計算誤差并過濾不感興趣的異常。這些組件在第3和4節(jié)中有詳細描述。

EGADS被構(gòu)建為一個框架，可以輕松地集成到現(xiàn)有的監(jiān)控基礎(chǔ)設(shè)施中。在雅虎，我們內(nèi)部的雅虎監(jiān)控服務(wù)（YMS）每秒處理數(shù)百萬個數(shù)據(jù)點。因此，對YMS進行可擴展、精準(zhǔn)且自動化的異常檢測至關(guān)重要。接下來我們將詳細描述YMS的具體細節(jié)。

2.1系統(tǒng)集成

EGADS作為獨立平臺運行，可用作大型系統(tǒng)中的庫。因此，設(shè)計EGADS和雅虎監(jiān)控服務(wù)（YMS）之間的接口至關(guān)重要。 EGADS與YMS的集成架構(gòu)圖如圖1所示。

圖1 EGADS-YMS 整體架構(gòu)

此外，異常檢測還需要幾個支撐組件來驅(qū)動完成。首先，所有的異常檢測模型都是離線批處理（batch）產(chǎn)生的，然后應(yīng)用到實時環(huán)境（real time）。其中批處理由三個步驟組成：

• 監(jiān)測數(shù)據(jù)（即監(jiān)控的時間序列數(shù)據(jù)）批量存儲在Hadoop集群上
• 批量模型生成器針對這些數(shù)據(jù)運行，并為目標(biāo)時間序列構(gòu)建模型
• 模型存儲在模型數(shù)據(jù)庫中

然后在線實時流使用這些存儲的模型，具體步驟如下：

• 數(shù)據(jù)流入Storm進行流式處理
• 集群中的一個模塊調(diào)用EGADS ADM，根據(jù)存儲在模型數(shù)據(jù)庫中的模型來評估輸入數(shù)據(jù)點
• 如果存在異常，則將其發(fā)送到由組合規(guī)則和其他包含特定邏輯組成的輔助規(guī)則流（見第4節(jié)）
• 根據(jù)規(guī)則，如果異常是警報事件，則生成事件，存儲在狀態(tài)數(shù)據(jù)庫中，并轉(zhuǎn)發(fā)到警報路由系統(tǒng)
• 警報路由系統(tǒng)應(yīng)用路由配置規(guī)則將警報發(fā)送給相應(yīng)的處理人員

2.2 可擴展性

EGADS的監(jiān)控需要每秒分析超過百萬級數(shù)據(jù)點和億級別時間序列。要求在CPU負(fù)載、I/O和內(nèi)存占用方面具有可擴展性，并且數(shù)據(jù)點的處理需要盡可能高效。這意味著需要預(yù)先計算盡可能多的模型。從磁盤讀取模型是不切實際的，會降低性能，因此模型應(yīng)該存儲在內(nèi)存中。另一方面，為了控制成本，模型應(yīng)盡可能小。

異常檢測算法

在本節(jié)中，我們給出了EGADS支持的異常檢測算法。目前，EGADS能夠檢測出三類異常：

在以下章節(jié)中，我們給出了EGADS當(dāng)前用于檢測上述異常類型的方法。

3.1 異常檢測

檢測異常值是許多監(jiān)控應(yīng)用中最重要的功能。EGADS提供了兩類用于檢測輸出的算法，本節(jié)對這兩類算法進行了描述。

3.1.1 插件方法

EGADS中異常值檢測的第一類方法稱為插件方法。為了模擬輸入時間序列的正常行為，可以業(yè)務(wù)和時序數(shù)據(jù)的特點來插入大量的時間序列模型和預(yù)測模型（例如ARIMA、指數(shù)平滑、Kalman濾波、狀態(tài)空間模型等）。這就是為什么我們將這個總體策略稱為插件方法。應(yīng)該注意的是，所有這些模型都在EGADS中用于時間序列預(yù)測，這是我們框架的另一個特征;然而，由于本文的重點是異常檢測，更多關(guān)于EGADS的建模和預(yù)測特征的細節(jié)我們不進行更深入的討論。

如果錯誤超出某些固定閾值，則會發(fā)出警報。這種簡單的方法在某些情況下可能會起作用，但是對于大多數(shù)的方法來說，它不會是一個很好的策略，因為它不能捕獲到錯誤的具體信息。

通過對相對誤差進行閾值處理，可以檢測異常值，同時對所期望值的幅度進行歸一化。雖然這些閾值確定了異常檢測模塊的敏感度，然而，很難確定異常檢測的最佳度量。事實上，給定時間序列的最優(yōu)度量的選擇取決于時間序列的性質(zhì)以及TMM性能。例如，如果我們處理一個非常規(guī)則的時間序列，我們有一個準(zhǔn)確的模型，使用預(yù)測誤差進行異常檢測可能就足夠了，因為它預(yù)期是正態(tài)分布的。在其他情況下，最佳度量可能在預(yù)測誤差和相對誤差之間存在某種差異。因此，EGADS默認(rèn)跟蹤一組偏差度量，使用系統(tǒng)的人可以創(chuàng)建自己的錯誤度量。在第4節(jié)中描述的警報模塊（AM）中使用這些錯誤度量以及其他功能（如時間序列特征）來了解用戶的偏好并過濾不重要的異常。

3.1.2 基于分解的方法

EGADS中第二類異常值檢測方法是基于時間序列分解的思想，在時間序列分析中，通常將時間序列分解為：趨勢、季節(jié)性和噪聲三個要素。通過監(jiān)測噪聲分量，可以捕獲異常值。更準(zhǔn)確地說，如果點Xt的噪聲分量的絕對值大于某個閾值，則可以認(rèn)為Xt為異常值。

3.2 變點檢測

在一些文獻里有提到一種基于時間窗口的變點檢測技術(shù)，在EGADS中，目前采用基于模型的方法。在這些方法中，時間序列的預(yù)期行為通過3.1.1節(jié)中提到的建模技術(shù)建模。我們結(jié)合3.1.1節(jié)中描述的插件方法來計算輸入時間序列的殘差序列（或模型預(yù)測的偏差）。然后我們對殘差序列應(yīng)用絕對變化點檢測的方法來檢測殘差分布。我們使用內(nèi)核密度估計（Kernel Density Estimation）、非參數(shù)估計殘差分布和Kullback-Leibler（KL距離，常用來衡量兩個概率分布的距離）來測量分布變化。

3.3 檢測異常時間序列

報警

異常檢測的最終目標(biāo)是產(chǎn)生準(zhǔn)確和及時的警報。 EGADS通過兩階段過程實現(xiàn)這一點，首先通過閾值選擇產(chǎn)生一組候選異常，然后根據(jù)給定的規(guī)則過濾不相關(guān)的異常。

4.1 閾值選擇

閾值選擇的作用是根據(jù)異常檢測模塊（ADM）產(chǎn)生的偏差度量選擇合適的閾值。目前，EGADS基于以下兩種閾值選擇算法實現(xiàn)：

（a）Kσ 偏差

（b）密度分布

第一種方法是參數(shù)化的，并假定數(shù)據(jù)正態(tài)分布，有明確的平均值和標(biāo)準(zhǔn)偏差。依靠高斯分布，并基于“3sigma規(guī)則”（即：其中99.73％的樣本位于平均值的三個標(biāo)準(zhǔn)偏差之內(nèi)）。因此，根據(jù)Kσ中的K值，可以確定在時間t觀測樣品的可能性。根據(jù)所需的敏感度，可以測量給定的樣品是否在K = 2或1的所有樣品的95.45％或68.27％之內(nèi)。請注意，這里的假設(shè)是以我們的偏差度量是正態(tài)分布為前提的。 第二種方法是非參數(shù)的，對于偏差度量不是正態(tài)分布的情況是有用的。基本思想是找到偏差度量分布的低密度區(qū)域。一種方法是使用諸如局部離群因子（LOF）的算法。通過將對象的局部密度與其鄰居的局部密度進行比較，可以識別具有相似密度的區(qū)域，以及具有比鄰居密度明顯更低的密度的點，這些點被認(rèn)為是異常值。

4.2 過濾

表1 EGADS所使用的時序數(shù)據(jù)特征表

圖2顯示了樣本時間序列的特征曲線。請注意，以dc開始的指標(biāo)是在時間序列上經(jīng)過調(diào)整后（即刪除趨勢和季節(jié)性數(shù)據(jù)后）得到的。在第6.2節(jié)中，我們將看看這些時間序列特征如何影響模型性能。

圖2：EGADS提取的時間序列及其特征的一個示例

實驗研究

6.1數(shù)據(jù)

用于實驗的數(shù)據(jù)集由1:1的合成數(shù)據(jù)和真實數(shù)據(jù)混合而成。我們創(chuàng)建了一個合成的時間序列生成工具，該工具已經(jīng)隨著框架和基準(zhǔn)數(shù)據(jù)開源。使用該工具，通過指定長度、幅度、異常數(shù)、異常類型、異常大小、噪聲水平、趨勢和季節(jié)性來生成合成時間序列。真實數(shù)據(jù)集使用了雅虎會員登錄數(shù)據(jù)(YML)。合成和真實數(shù)據(jù)在時間序列都包含3000個數(shù)據(jù)點，YML數(shù)據(jù)包含了3個月的數(shù)據(jù)點。除非另有說明，所有實驗均以1000次隨機選取的時間序列進行，結(jié)果取平均值。還要注意，合成和真實數(shù)據(jù)都有異常標(biāo)簽，方便測量精度和召回率。

6.2建模實驗

時間序列建模（由EGADS中的TMM組件捕獲）是異常檢測的基本部分。通常情況下，異常檢測與底層時間序列模型一樣好。由于大量的候選模型，模型選擇變得至關(guān)重要，并且取決于時間序列特征和可用資源。在下面的實驗中，我們展示了時間序列特征對模型性能的影響，并顯示了精度，實驗中使用的模型和誤差度量分別參見表2和3。

表2 用于建模實驗的模型列表

表3 用于建模實驗的指標(biāo)列表

6.2.1時間序列特征和性能

為了證明時間序列特征對模型性能的影響，我們比較了不同模型的時間序列與不同特征的誤差度量（見4.2節(jié)）。圖3顯示了時間序列特征在模型行為中起著重要作用。例如，季節(jié)性模式的Olympic模型在數(shù)據(jù)集上表現(xiàn)不佳，沒有季節(jié)性和強勁趨勢。 EGADS能夠跟蹤歷史時間序列特征和模型性能，使用這些歷史信息，EGADS選擇由表3中描述的誤差度量判斷的最佳模型（給定時間序列特征）。實際上，基于數(shù)據(jù)特征進行模型選擇比針對每個模型執(zhí)行交叉驗證要快得多。

圖3 具有不同特性的時間序列性能

6.2.2時序模型的可擴展性

如第2節(jié)所述，時序模型需要高性能技術(shù)以支持大規(guī)模（例如每秒數(shù)百萬點）數(shù)據(jù)流的實時計算，因此需要在模型大小、訓(xùn)練時間和準(zhǔn)確性之間進行權(quán)衡。 這種權(quán)衡在圖4（a）和4（b）中可以看出。 例如，從圖中可以看出，季節(jié)性天性模型訓(xùn)練很快，但是具有較大的存儲要求和較高的平均誤差。 在雅虎，首先設(shè)定了資源和模型訓(xùn)練時間的目標(biāo)，然后選擇相應(yīng)的模型。 換句話說，目標(biāo)是在資源和模型建立時間限制下使得表3中的錯誤減到最小。

圖4 模型大小與訓(xùn)練時間的權(quán)衡

6.3異常檢測實驗

在本節(jié)中，我們比較了開源系統(tǒng)與EGADS，參考的開源系統(tǒng)如表4所示。

表4 開源異常檢測模型（系統(tǒng)）列表

在圖5顯示了對6.1節(jié)中描述的數(shù)據(jù)的測試結(jié)果，比較方法采用：

圖5 異常模型在不同數(shù)據(jù)集上的表現(xiàn)（觀察到在所有數(shù)據(jù)集上沒有最好的單一模型）

結(jié)果可以看出，沒有一個最佳的異常檢測模型能適合所有業(yè)務(wù)場景，不同的算法需要結(jié)合檢測不同類型的異常來確定。例如，Twitter在數(shù)據(jù)集上表現(xiàn)最好，而ExtremeLowDensity模型在上表現(xiàn)最好。但是，EGADS的設(shè)計初衷是在用戶對數(shù)據(jù)類型的時間序列和異常類型不了解的情況下，該系統(tǒng)能夠優(yōu)雅和穩(wěn)健地處理數(shù)據(jù)中存在的各種異常現(xiàn)象。因此，EGADS被構(gòu)建為將一組異常檢測模型組合成一個最佳框架的庫。這些模型的異常被轉(zhuǎn)發(fā)到過濾組件以進行精確的異常檢測。

6.4異常過濾實驗

異常的重要性往往取決于實際應(yīng)用場景。具體來說，一些用戶可能對展示惡意攻擊的時間序列行為感興趣，而其他用戶可能對收入有興趣。

為了解決這個要求，過濾階段掃描所有模型的所有異常，并使用分類為作為真正的模型。在YM用例的過濾階段使用的模型是基于AdBoost的增強樹模型。模型中使用的特征參見表1。AdaBoost的核心原理是在變化的數(shù)據(jù)上進行適合一系列weak learners（例如，小決策樹），最后的結(jié)果是通過組合加權(quán)多數(shù)表決產(chǎn)生的。圖6中的實驗結(jié)果表明，在濾波階段使用不同的模型特征，得到比較好的精確率和召回率。

圖6：使用不同類型特征的過濾階段的精度

結(jié)論

異常檢測是許多具有故障應(yīng)用的實時監(jiān)控系統(tǒng)的核心部分, 比如檢測、欺詐檢測、網(wǎng)絡(luò)入侵檢測等等。盡管它至關(guān)重要，但實際上實施全自動異常檢測系統(tǒng)是一項極具挑戰(zhàn)性的任務(wù)，這些挑戰(zhàn)通常導(dǎo)致解決方案不可擴展或并非高度專業(yè)化的，也導(dǎo)致了較高的誤報率。

在本文中，我們介紹了EGADS——雅虎實現(xiàn)的通用異常檢測系統(tǒng)，對不同的Yahoo屬性和數(shù)百萬個時間序列進行自動監(jiān)控和警報。正如我們在本文中所描述的，Hadoop上的EGADS并行架構(gòu)以及Storm的流處理機制使得它能夠在雅虎的數(shù)百萬個時序數(shù)據(jù)集上執(zhí)行實時異常檢測。此外，EGADS采用不同的時間序列建模和異常檢測算法來處理不同的監(jiān)控場景。通過將這一組算法與機器學(xué)習(xí)機制結(jié)合到警報模塊中，EGADS能自動適應(yīng)對用戶重要的異常檢測用例。所有這些功能都有效地創(chuàng)建了一個功能強大的異常檢測框架，它是通用且可擴展的。我們對真實數(shù)據(jù)集和綜合數(shù)據(jù)集的展示實驗表明，與其競爭對手的解決方案相比，我們的框架具有優(yōu)越的適用性。

End.

轉(zhuǎn)載請注明來自36大數(shù)據(jù)（36dsj.com)： 36大數(shù)據(jù) ? Yahoo大規(guī)模時列數(shù)據(jù)異常檢測技術(shù)及其高性能可伸縮架構(gòu)