Yahoo大規模時列數據異常檢測技術及其高性能可伸縮架構

作者：彭冬

1. 摘要

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

2. 簡介

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

異常值本質上是一個數據點。通常，大多數應用程序中的數據是由一個或多個反映系統功能的程序產生的。當底層應用程序以不正常的方式運行時，它就會產生異常值。快速高效地發現這些異常值非常有價值，比如：入侵檢測、信用卡欺詐、感測器事件、醫療診斷、執法等。

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

EGADS是首個靈活、準確且可擴展的異常檢測綜合系統。 EGADS框架與異常檢測基準數據已經一起開源，旨在幫助學者和行業合作開發新的異常檢測模型。在雅虎，EGADS每天被許多團隊用於數百萬次的時間序列異常檢測工作。

整體架構

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

EGADS被構建為一個框架，可以輕鬆地集成到現有的監控基礎設施中。在雅虎，我們內部的雅虎監控服務（YMS）每秒處理數百萬個數據點。因此，對YMS進行可擴展、精準且自動化的異常檢測至關重要。接下來我們將詳細描述YMS的具體細節。

2.1系統集成

EGADS作為獨立平台運行，可用作大型系統中的庫。因此，設計EGADS和雅虎監控服務（YMS）之間的介面至關重要。 EGADS與YMS的集成架構圖如圖1所示。

圖1 EGADS-YMS 整體架構

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

監測數據（即監控的時間序列數據）批量存儲在Hadoop集群上

批量模型生成器針對這些數據運行，並為目標時間序列構建模型

模型存儲在模型資料庫中

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

數據流入Storm進行流式處理

集群中的一個模塊調用EGADS ADM，根據存儲在模型資料庫中的模型來評估輸入數據點

如果存在異常，則將其發送到由組合規則和其他包含特定邏輯組成的輔助規則流（見第4節）

根據規則，如果異常是警報事件，則生成事件，存儲在狀態資料庫中，並轉發到警報路由系統

警報路由系統應用路由配置規則將警報發送給相應的處理人員

2.2 可擴展性

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

異常檢測演算法

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

在以下章節中，我們給出了EGADS當前用於檢測上述異常類型的方法。

3.1 異常檢測

檢測異常值是許多監控應用中最重要的功能。EGADS提供了兩類用於檢測輸出的演算法，本節對這兩類演算法進行了描述。

3.1.1 插件方法

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

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

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

3.1.2 基於分解的方法

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

3.2 變點檢測

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

3.3 檢測異常時間序列

報警

異常檢測的最終目標是產生準確和及時的警報。 EGADS通過兩階段過程實現這一點，首先通過閾值選擇產生一組候選異常，然後根據給定的規則過濾不相關的異常。

4.1 閾值選擇

閾值選擇的作用是根據異常檢測模塊（ADM）產生的偏差度量選擇合適的閾值。目前，EGADS基於以下兩種閾值選擇演算法實現：

（a）Kσ 偏差

（b）密度分布

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

4.2 過濾

表1 EGADS所使用的時序數據特徵表

圖2顯示了樣本時間序列的特徵曲線。請注意，以dc開始的指標是在時間序列上經過調整後（即刪除趨勢和季節性數據後）得到的。在第6.2節中，我們將看看這些時間序列特徵如何影響模型性能。

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

實驗研究

6.1數據

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

6.2建模實驗

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

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

表3 用於建模實驗的指標列表

6.2.1時間序列特徵和性能

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

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

6.2.2時序模型的可擴展性

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

圖4 模型大小與訓練時間的權衡

6.3異常檢測實驗

在本節中，我們比較了開源系統與EGADS，參考的開源系統如表4所示。

表4 開源異常檢測模型（系統）列表

在圖5顯示了對6.1節中描述的數據的測試結果，比較方法採用：

圖5 異常模型在不同數據集上的表現（觀察到在所有數據集上沒有最好的單一模型）

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

6.4異常過濾實驗

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

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

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

結論

異常檢測是許多具有故障應用的實時監控系統的核心部分, 比如檢測、欺詐檢測、網路入侵檢測等等。儘管它至關重要，但實際上實施全自動異常檢測系統是一項極具挑戰性的任務，這些挑戰通常導致解決方案不可擴展或並非高度專業化的，也導致了較高的誤報率。

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

End.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！