Categories
程式開發

螞蟻智能運維:單指標異常檢測算法初探


1 背景介紹

AntMonitor:螞蟻集團研發的一款面向雲原生時代的全功能智能運維產品,包含業務監控、應用監控、基礎設施監控、雲原生可觀測、一站式多維分析等功能。 其中,智能化的單指標異常檢測是該產品最基礎、最重要的組成部分。

針對時序異常檢測,目前螞蟻集團內部基本都在按照以下幾個思路進行研發:

  1. 通過時序預測的方法,典型算法為ARIMA、LSTM 等,將歷史數據訓練的模型預測當前時刻的幅值,通過與真實值的差異來判斷此刻的異常程度。 在多次嘗試此類模型後發現,其不但算法複雜度較高,還存有隱藏風險,此類模型訓練遵循的是全局最優化策略,因此在預測當前值時無法保證當前值是單點最優(運氣不好的情況下,當前點預測值誤差較大)。 一種解決的思路是結合其他算法進行集成學習,將誤差概率盡可能的降低;
  2. 採用深度學習的方法,通過大量採集正負樣本,採用一維CNN、甚至二維CNN (將時序數據視為圖像)的方法訓練模型。 在嘗試該類方法後發現,雖然其能夠解決一些無法用規則描述的異常場景,但要搭建一個合適的針對時序數據的網絡模型難度較大,此外在當前異常標準沒有完全統一的情況下,模型移植性存在著很大的問題,當不同的SRE 對業務容忍閾值不一致時,意味著要針對性地重新訓練模型,這個工作量是十分巨大的;
  3. 通過集成學習的方法,有項目組是將多個弱分類賦予權重後投票來解決異常識別問題,當前的效果是在部分場景中可以達到很高的準招率。 但與傳統Ensemble Learning 不同的是,其各個弱分類器的權重調整併不是一個自優化過程,而是需要通過人工調整獲得,這在檢測指標數量不大的時候可以採用,但是針對AntMonitor 動輒幾十萬個目標指標的場景就無解了;
  4. 通過統計規則與機器學習相結合的方法,需要盡可能地將異常場景進行分類剝離(或者對數據進行分類,即算法路由),再針對各個場景進行求解。 其中機器學習或深度學習可以用於描述一些難於公式化的場景,如描述波形相似。 此類方法還可以將模型內部的各個參數進行透傳,可以兼顧計算效率和模型移植性;

上述幾種思路無所謂優劣,不同的方法都有其優勢及不足,都有其契合及尷尬的場景,合適的方法才是最好的方法。 針對AntMonitor 實際面對的運維場景,統計規則和機器學習相結合的方法被選為最終解決方案。 本文將分享研發AntMonitor 智能檢測算法時的一些想法和思路,歡迎各位交流學習。

2 異常分類

在做智能异常检测的过程中,其中最棘手的问题是获得一个明确的异常判断标准。比较遗憾的是,针对不同的业务、不同的指标甚至不同的使用方都会有不同的判断标准。因此,本文从另一个角度出发,先挖掘认可度高的基础异常波形,再以点到面逐步地解决异常判断问题。以耗时值上升异常检测为例,下图给出了 AntMonitor 常见异常波形 A-D(各种异常波形都可认为是以下几种波形的变种或组合),根据各自不同的特性将其归纳为3种不同的类型,分别为冲高异常、趋势抬升异常和频率变化异常。其中 A、B 归为冲击异常,从图中可以看到其都有一个显著的幅值突变;C 归为缓变抬升异常,相较与冲击异常,其幅值抬升过程相对较为平缓;D 归为频率变化异常,主要特征为波动频率出现巨大的变化。下面分别对不同类型异常进行求解。

螞蟻智能運維:單指標異常檢測算法初探 1

圖1 常見異常波形

3 算法整體架構

圖2 為整體算法架構,其主要由preFilter、coreUp 和adapter 三部分組成。 preFilter 為前置過濾器,能夠在較少數據輸入的情況下過濾絕大部分正常信號,極大地降低資源消耗,這是算法能夠大規模覆蓋的基礎;coreUp 為核心檢測層,通過算法路由將不同類型數據映射到對應到合適的算法參數或模塊,主要對沖擊、趨勢和頻率三種異常類型進行檢測;adapter 為適配層,其主要作用是能夠允許不同對象創建適合自身的異常檢測模型,其中可通過透出的算法進行人工配置,也可以通過樣本打標來自動訓練最優模型參數。 下一章節主要對coreUp 層幾個核心模塊的具體實現做詳細介紹。

螞蟻智能運維:單指標異常檢測算法初探 2

圖2 算法整體構架

4 核心模塊介紹

衝擊異常模塊

冲击异常在波形上表现为某时刻突然出现的一个尖峰,往往是局部的幅值极大值。然而直接从幅值触发判断当前点是否异常,往往会出现漏报。如图3所示,由于原始波形存在着趋势项,冲击波形虽然是局部及极大值但往往不是全局视野内的最大值,因此会有被过滤的可能。观察冲击异常波形,发现其往往都是瞬时“变化”最大的时刻,其显著特征是当前值远大于前一时刻的值或持续大于前值。因此,本节从寻找瞬时波动幅值突变点的角度出发,开发基于一阶差分的异常检测算法。

當間距相等時,用下一個值減去上一個值定義為“一階差分”。 如圖3所示,當帶有趨勢項的時間序列經過一次差分後可以有效地去除趨勢項,同時衝擊異常點也從局部極大值轉變為了全局最大值。 針對長度為$N$ 的時間序列$X={x_1,x_2,dots,x_n}$,其對應差分序列可以表示為${rmDelta}={{rmDelta}x_1,{ rmDelta}x_2,dots,{rmDelta}x_{n-1}}$, 其中${rmDelta}x_i=x_{i+1}-x_i$。 若當天時間序列與歷史事件序列分別用$X_T$ 和$X_H$ 表示,分別計算各自差分序列得到${rmDelta}X_T$ 和${rmDelta}X_H$, 同時獲得當前時刻差值${rmDelta}x^{now}_T$。 若${rmDelta}x^{now}_T$ 在集合${rmDelta}X_T$ 和${rmDelta}X_H$ 同時被判定為異常,則意味著當前時刻存在著衝擊異常可能。 考慮到存在著連續上升的情況,在實際應用中對差分計算稍作修改使其更為精確,例如當滿足$x_{i+1}>x_i>x_{i-1}$ 時,令${ rmDelta}x_i=x_{i+1}-x_{i-1}$。

螞蟻智能運維:單指標異常檢測算法初探 3

圖3 時序趨勢的影響

常用的異常檢測方法可參考異常檢測算法綜述類論文。 此處採用Tukey 箱型圖作為異常檢測算法。 選擇箱線圖算法的原因主要有三點:1)計算簡單;2)可適用於非正態分佈數據;3)可調整判斷閾值。

Tukey 箱型圖

此處對Tukey 箱型圖分析做一下簡單介紹。 眾所周知,基於正態分佈的3σ 法則或Z 分數方法的異常檢測是以假定數據服從正態分佈為前提的,但實際數據往往並不嚴格服從正態分佈。 應用這種方法於非正態分佈數據中判斷異常值,其有效性是有限的。 Tukey 箱型圖是一種用於反映原始數據分佈的特徵常用方法,也可用於異常點識別。 在識別異常點時其主要依靠實際數據,因此有其自身的優越性。 箱型圖的繪製方法是:

  1. 先找出一組數據的最大值、最小值、中位數和兩個四分位數;
  2. 然後,連接兩個四分位數畫出箱子;
  3. 再將最大值和最小值與箱子相連接,中位數在箱子中間;

箱型圖為我們提供了識別異常值的一個標準:異常值被定義為小於Q1-1.5IQR 或大於Q+1.5IQR 的值。 雖然這種標準有點任意性,但它來源於經驗判斷,經驗表明它在處理需要特別注意的數據方面表現不錯。

螞蟻智能運維:單指標異常檢測算法初探 4

圖4 箱型圖示意圖

衝擊檢測流程

衝擊異常檢測的簡要流程如下:

  • 當日序列$X_T$ 和歷史序列$X_H$ ,獲得差分序列${rmDelta}X_T$ 和${rmDelta}X_H$ ,已經當前差分值${rmDelta}x^{now }_T$ ;
  • 採用Turkey箱線圖獲得集合${rmDelta}X_T$ 的上限,判斷${rmDelta}x^{now}_T$ 是否超限,若否返回“正常”,若是進入下一步;
  • 判斷異常時刻是否超過預設異常持續時長$T$ ,若否返回“正常”,若是進入下一步;
  • 在${rmDelta}X_H$ 中截取以當前時刻為中心且長度為$L$ 的子集合,採用Turkey 箱線圖獲得其上限,判斷${rmDelta}x^{now}_T $ 是否超限,若否返回“正常”,若是進入下一步;
  • 判斷在當日前序時間序列中是否也存在衝高異常點,若不存在返回“異常”結果;若存在進入下一步;
  • 判斷${rmDelta}x^{now}_T$ 是否大於$k*{rmDelta}x^i_T$ ,若是返回“異常”結果,若否則返回“正常”結果;

螞蟻智能運維:單指標異常檢測算法初探 5

圖5 衝擊檢測流程

存在的問題

採用上述方法存在兩個問題,第一個如下左圖所示,若出現大幅度下跌回升(相當於下跌檢測中的衝高回落)的情況,當前點的差分值必然會超限告警,這種誤報當前通過類似“衝高回落”的方法進行過濾,本文不再具體介紹;第二種,在整體波動幅度較大的情況下,出現這種小幅緩變抬升的小凸起,採用衝擊異常檢測是無能為力的。 針對這種異常類型,本文通過趨勢異常模塊來進行解決。

螞蟻智能運維:單指標異常檢測算法初探 6

圖6 存在的漏報場景

趨勢異常模塊

當波形緩慢上升時,由於差值大小是基本穩態的,上述衝擊異常模塊是無法有效識別的。 因此,必須要有方法支持此類緩慢變化異常識別。 在嘗試各種算法模型後,本文最終選擇AugmentedDickey–FullerTest 和Mann-Kendall Test 相結合的方式來求解此類問題。

ADF測試

Augmented Dickey–Fuller test 又称为扩展迪基-福勒检验,其可以用来检测当前序列是否平稳。ADF 检验的原假设是存在单位根,因为存在单位根就是非平稳时间序列了,只要这个统计值是小于 1% 水平下的数字就可以极显著的拒绝原假设,认为数据平稳。注意,ADF 值一般是负的,也有正的,但是它只有小于 1% 水平下的才能认为是及其显著的拒绝原假设。

曼肯德爾檢驗

Mann-Kendall 非參數秩次檢驗原理如下,對長度為$N$ 的時間序列${X_i|i=1,2,dots,N}$ , 統計假設$H_0$ :未經調整修正的數據系列${X_i}$ 是一個由$N$ 個元素組成的獨立的具有相同分佈的隨機變量。 備擇假設$H_1$ 是雙邊檢測:對所有的$i$ ,當$jleq N$ 時和$ine j$ 時${X_i}$ 和${X_j}$ 的分佈不相同。 計算時,對每一個$X_i(i=1,2,dots,N-1)$ ,與其後的${X_j|j=1,2,dots,N}$ 進行比較,記錄$X_j> X_i$ 出現的次數。 定義Mann-Kendall 統計量$S$ :

$$ S = sum ^ {n-1} _ {i = 1} sum ^ n_ {j = i + 1} sign(X_i-X_j)$$

其中, $sign()$ 為符號函數。 當$X_i-X_j$ 小於、等於或者大於零時, $sign(X_i-X_j)$ 分別為-1、0或者1;對於假設統計$H_0$ ,當$Ntoinfty$ 時, $S $ 的分佈為正態分佈, $S$ 的均值為$0$ ,方差為$n(n-1)/(2n+5)/18$ 。 當$N>10$ 時,即可應用近似正態分佈進行檢驗分析。

標準整體統計變量$Z$ 可以用下式計算:

螞蟻智能運維:單指標異常檢測算法初探 7

这样,在双边的趋势检验中,在给定的 $alpha$ 置信水平上,如果 $|Z|>Z_{1-alpha/2}$ 则原假设是不可接受的。 $Z$ 为正值表示增加趋势,负值表示减少趋势。 $Z$ 的绝对值在大于等于1.28、1.64、2.32时表示分别通过了信度为90%、95%、99%的显著性检验。

Mann-Kendall 非參數秩次檢驗在數據趨勢檢測中極為有用,其特點表現為:

  • 無需對數據系列進行特定的分佈檢驗,對於極端值也可參與趨勢檢驗;
  • 允許系列有缺失值;
  • 主要分析相對數量級而不是數字本身,這使得微量值或低於檢測範圍的值也可以參與分析;
  • 在時間序列分析中,無需指定是否是線性趨勢;

趨勢檢測流程

趨勢檢測並不是直接檢測當日數據是否存在上漲趨勢,理論上若歷史數據與當天數據同步上漲,那麼該波形趨勢不應該識別為異常。 換句話說,需要去除當日數據相對於歷史的趨勢。 此處採用相對差值的方式來實現該目的。 假設當日數據為$X_T={x^i_T|i=1,2,dots,N}$ ,某天歷史數據為$X_{H_k}={x^i_{H_k}|i=1,2, dots,N}$ ,那麼兩者之間的差值序列可以表示為$D_k={x^i_T-x^i_{H_k}|i=1,2,dots,N}$ ,在此基礎上再進行趨勢分析。

詳細流程如下:

  • 計算當日數據$X_T$ 與某歷史數據$X_{H_k}$ 的相對差值序列$D_k$ ;
  • 採用Mann-Kendall 檢驗判斷$D_k$ 是否存在上漲趨勢,若無上漲趨勢返回“正常”結果,反之進入下一步;
  • 計算趨勢上漲的起始點$p$ ,採用最小二乘法擬合上漲段波形,獲得上漲絕對幅值$delta x$ , 計算當日數據$X_T$ 中$p$ 點對應的基礎值$x_{base }$ ,計算實際上漲比率$r_{real}=delta x/x_{base}$ ;
  • 判斷$r_{real}$ 是否大於設定漲幅比率閾值$r_{default}$ ,若不大於設定閾值則返回“正常”結果,反之則進入下一步;
  • 採用T檢驗判斷前序數據是否存在類似的上漲波形,若存在則返回“正常”結果,若不存在則返回“異常”結果;

螞蟻智能運維:單指標異常檢測算法初探 8

圖7 單次趨勢檢測流程

實際應用中流程會稍複雜一點,並且做了部分假設:1)若當天相對於昨日不存在上漲趨勢,即可認為不存在緩變上漲異常;2)若當天相對於昨日存在上漲趨勢,那麼需考察當天相對與剩餘歷史是否也存在上漲趨勢,此處設定若有大於$N_{default}$ 天不存在相對趨勢,即認為不存在緩變趨勢。 考慮到算法需要獲得準確的告警時間點,並用來計算精確的漲幅比率,此處對$X_T$ 按不同長度先後進行趨勢判斷。 大致的判斷流程如圖13所示,此處不再展開。

螞蟻智能運維:單指標異常檢測算法初探 9

圖8 趨勢上漲異常檢測整體流程

頻率異常模塊

頻率異常在實際場景中並不多見,但是作為一類異常類型,此處也對其進行了覆蓋。 針對頻率異常數據類型,本文采用分位數聚合特徵來進行求解,主要步驟如下:

DoulbeRollingAggregate

分位數定義:對一個有著連續分佈函數的樣本集$X$ ,分位數是將一個概率分佈切分為有著相同概率的連續區間的切分點。 用數學公式表達的話: $P{Xleq x_{alpha}}=alpha$ ,則稱$x_{alpha}$ 為隨機變量$X$ 的$alpha$ 分位數。

分位數聚合特徵$$F$$計算流程如下:

  • 長度為$N$ 的時間序列$X={x_1,x_2,dots,x_n}$ ,分別擴展得到$N+W$ 的時間序列$X_l$ 和$X_r$ ,具體為:

$ X_l = { underbrace {x_1,x_1, dots,x_1} _W,x_1, dots,x_n},〜X_r = {x_1, dots,x_n, underbrace {x_n,x_n, dots,x_n} _W }; $

  • 對時間序列$X_l$ 進行滑窗截取操作,窗口長度為$W$ ,獲得長度為$N$ 的子序列集合$D_l={DL_1,Dl_2,dots,Dl_n}$ ,其中$Dl_i={x_i ,x_{i+1},dots,x_{i+w}}$ ;同樣的,獲得時間序列$X_r$ 對應的子序列$D_r={Dr_1,Dr_1,dots,Dr_n}$ ;
  • 計算$D_l$ 集合中各個子序列的$K$ 個分位數,用$Dl^{alpha_k}_i$ 表示子序列$Dl_i$ 的$alpha_k$ 分位數;同樣的,計算$D_r$集合中各個子序列的對應的分位數,用$Dr^{alpha_k}_i$ 表示;
  • 通過$Dl^{alpha_k}_i$ 和$Dr^{alpha_k}_i$ 獲得當前時刻的分位數聚合特徵,具體公式如下:

$$ F_i = sqrt { sum ^ K_ {k-1}(Dl ^ { alpha_k} _i-Dr ^ { alpha_k} _i)^ 2} $$

分位數聚合特徵計算示意圖如下所示:

螞蟻智能運維:單指標異常檢測算法初探 10

圖9 分位數聚合特徵計算示意圖

實際檢測效果

在頻率異常檢測的應用中,需要對數據類型進行區分。 針對稀疏類型數據直接進行“分位數聚合”算法計算,而對於存在趨勢項的非稀疏數據,必須先對其進行一階差分操作後才可以使用當前算法。 圖10給出了兩者不同類型的頻率異常檢測模型,分別給出了“分位數聚合”特徵曲線,從圖中可以看到可以準確地識別此類異常波形。 在實際使用中還需要根據具體場景添加一些規則限制,此處不再具體展開。

螞蟻智能運維:單指標異常檢測算法初探 11

圖10 不同類型異常數據檢測效果

相似性檢測模塊

相似性誤報在時序異常檢測中佔有不小的比例。 如下圖時序在檢測時刻出現異常衝高時,若不考慮歷史同期波形,往往會出現相似性誤報現象。 實際在波形進行相似性檢測時,往往需要考慮時序長短不一致和波形偏移的問題。 一般來講,時序長短不一致和波形偏移主要表現為:

  • 如下圖所示,當日波形$T_0$ 與歷史波形的衝高部分出現一段前後偏移;
  • 為提高實時檢測的時效性,一般參考將歷史參考波形相對於當前檢測時刻延後幾分鐘;

螞蟻智能運維:單指標異常檢測算法初探 12

圖11 相似性誤報

由於時序長短不一致和波形偏移的情況,皮爾遜相關係數、餘弦相似度、歐式距離等相似性評價指標就不再適用。 動態時間規整(DTW)是一種常用的模板匹配算法,其可以有效的解決對比長度不一致的時間序列相似性問題,圖12給出了DTW 算法與傳統歐式距離評價的差異,此處不再展開描述。 但實際應用中,DTW 算法更多的是一種搜索匹配算法,即其返回結果是目標庫中的最優匹配對象,而在時間序列實時監測過程中,需要的是能給出一個可量化的相似度參考值做為判斷依據,因此DTW 也不能直接使用。 本文給出了一種基於動態時間規整(DTW)及T檢驗的時序波形相似性評估方法,不但能夠有效評估長度不同、發生偏移序列的相似度,還可以返回可量化的相似性度量值,能夠應用於時間序列實時異常檢測。

螞蟻智能運維:單指標異常檢測算法初探 13

圖12 DTW 算法與歐式距離對比

相似性檢測流程

  • 截取當日數據,記時間序列為$X_T={x^i_T|i=1,2,dots,n}$ , $x^n_T$ 表示當前時刻的實時數據;
  • 截取歷史同時刻對比數據,記為$X_{H_k}={x^i_{H_k}|i=1,2,dots,n+m}$ , 為了刻畫數據偏移特性,歷史對比數據比當天數據往後多取$m$ 個數據點;
  • 為消除時序常數項對$DTW$ 距離度量的影響,對時序做“拉平”預處理,即將各個時間序列減去其自身中位數,獲得新的序列分別記為$X’_T$ 和$X ‘_{H_k}$ ;
  • 定義時序$tsI$ 到時序$tsJ$ 的$DTW$ 距離定義為$dtw(tsI,tsJ)$ ,分別計算當日$X’_T$ 與各個歷史$X’_{H_k}$ 的$DTW$ 距離,獲得距離集合$D_1$ ,此處$tsI$ 和$tsJ$ 的長度分別為$n$ 和$n+m$ ;
  • 分別計算$X’_{H_k}$ 內兩兩時序的$DTW$ 距離,獲得距離集合$D_2$ ,為與上一步驟保持一致,此處$dtw(tsI,tsJ)$ 中波形$tsI$取數據前$n$ 個點, $tsJ$ 取$n+m$ 個點;
  • 采用STest算法判断集合 $D_1$ 和 $D_2$ 中的距离均值 $mu_1$ 和 $mu_2$ 是否存在显著性差异,设原假设 $H_0:mu_1=mu_2$ ,备择假设 $H_1:mu_1nemu_2$ ,检验水准 $alpha=0.01$ ;
  • 計算獲得pValue,若pValue> $alpha$ ,不拒絕原假設$H_0$ ,表明當日波形與歷史波形相似; 反之,當日波形與歷史波形不相似;

實際檢測效果

下圖給出了“相似性檢測模塊”的實際檢測效果,圖13中的4例告警都為未配置“相似性檢測”模塊前的上升告警樣例,採用上述算法回跑後都可以有效地識別為相似性誤報。 從實際使用情況來看,該模塊評估為誤報的案例基本都是相似的,反之存在著一定的偏差,但對於一個後置過濾模塊來講是完全可接受的。 總體來講,對較為規整的波形判斷效果不錯,當歷史數據本身趨勢不相關、波形太過雜亂,上述算法效果一般。

螞蟻智能運維:單指標異常檢測算法初探 14

圖13 相似性檢測效果

五算法過濾場景

通過上述整體算法判斷後,下圖中的潛在異常場景,如單點衝高、衝高前序相似、衝高歷史相似、抬升歷史相似等都可以被有效過濾。 在實際應用中,此類過濾項都配置有相應的開關,由業務人員來確認是否開啟。

螞蟻智能運維:單指標異常檢測算法初探 15

圖14 典型過濾場景

六總結與展望

本文算法總體思路是對單指標波形異常檢測問題進行拆解,將其歸納為衝高異常、趨勢上漲異常和頻率變化異常三個模式。 在此基礎上,輔以一些過濾模塊來減少特定誤報的產生,如利用基於DTW 的算法來求解諸如”波形相似性”的誤報場景。 此外,本文中的異常判斷標準相對統一,都以箱線圖分析為標準,各個超參數都可以進行透傳,後期針對不同的應用場景不同的閾值都可以快速調整。 當前根據以上思路設計的模型主要應用在JVM&System 指標監測上,約5w 條key 總體異常告警量小於5條/分鐘。

基本上,上述算法可以覆蓋絕大部分的場景,但往往會有各種意想不到的誤報漏報情況出現,後期的一部分工作要重點解決此類問題;另一方面,針對一些偏明確的場景,在後期可以用機器學習或者深度學習模型來進行代替,如“波形相似性”問題,在積累足夠樣本量後可嘗試通過深度學習模型進行覆蓋。 同時,也可以嘗試集成算法,以往從事機器學習的項目經驗表明,往往集成後會有意想不到的精度提升。

作者介紹

徐劍,花名輅遠,螞蟻集團高級開發工程師,工學博士,長期從事智能運維、機器學習和信號處理等領域的研究及開發工作,當前為AntMonitor 算法開發人員。

本文轉載自公眾號金融級分佈式架構(ID:Antfin_SOFA)。

原文鏈接

螞蟻智能運維:單指標異常檢測算法初探