時序異常檢測演算法概覽
來自專欄論智19 人贊了文章
作者:Pavel Tiunov
編譯:weakish
在Statsbot,我們持續檢查異常檢測方法這一領域的研究,並據此更新我們的模型。
本文概覽了最流行的時序異常檢測演算法,並討論了它們的優點和缺點。
本文是為想要了解異常檢測技術發展現狀的經驗不足的讀者寫的,我們將模型的數學藏在參考鏈接里,以免嚇到讀者。
異常的重要類型
時序異常檢測通常形式化為根據某種標準或正常信號尋找離群數據點。有很多異常類型,但本文只關注那些從商業角度來說最重要的類型,包括意料之外的峰谷、趨勢變動、水平變化(level shift)。
例如,追蹤網站的用戶數時發現短時間內出乎意料的用戶增長,看起來像是一個尖峰。這類異常通常稱為加性離群值(additive outlier)。
再舉一個例子,伺服器掛了,某段時間內的用戶數為零或極低。這類異常通常歸類為時間變動(temporal change)。
再比如,你正處理某種轉化漏斗(conversion funnel),可能會碰到轉化率下降。如果發生這種情況,目標測度通常不會改變信號的形狀,但會改變某段時期內的總值。取決於變化的特徵,這類異常通常稱為水平變化(level shift)或季節性水平變化(seasonal level shift)。
基本上,異常檢測演算法要麼將每個時間點標記為異常/非異常,要麼預測某一點的信號,並測試這一點的值和預測值的偏離程度,以認定異常。
使用第二種方法的時候,可以可視化置信區間,這對理解異常出現的原因並加以確認很有幫助。
下面我們將從應用角度查看尋找不同類型離群值的演算法。
STL分解
STL是基於損失的季節性趨勢分解過程的簡稱。這一技術可以將時序信號分成三部分:季節性(seasonal)、趨勢(trend)、殘餘(residue)。
顧名思義,STL分解適用於季節性時序數據,這是最常見的情形。
如果你分析殘餘的偏離程度,並引入某種閾值,你會得到一種異常檢測演算法。
為了得到魯棒性更好的檢測效果,這裡應該使用絕對中位差。該方法最先進的實現是Twitter的異常檢測庫。它使用Generalized Extreme Student Deviation(廣義ESD)測試殘餘點是否是離群值。
優點
這一方法的優點在於簡單性和魯棒性。它可以處理許多不同情況,並且所有異常仍然可以直觀地解釋。
它主要擅長檢測加性離群值。如果想要檢測水平變化,你可以轉而分析某種移動平均信號。
缺點
這一方法的缺點是調整選項很死板,你只能通過顯著性水平調整置信區間。
信號特徵劇烈變動是該方法效果不佳的典型場景。例如,追蹤原本不對公眾開放,隨後突然開放的網站的用戶數。在這種情形下,你應該分別追蹤網站上線前和上線後的異常。
分類回歸樹
分類回歸樹(CART)是魯棒性最好、效率最高的機器學習演算法之一。它同樣可以應用於異常檢測問題。
- 首先,你可以使用監督學習教樹分類異常數據點和非異常數據點。這需要你有標記好的數據點。
- 第二種方法是使用無監督學習教CART預測時序中的下一個數據點,得到和STL分解方法類似的置信區間或預測誤差。你可以使用廣義ESD檢驗或Grubbs檢驗檢查數據點是否位於置信區間之內。
最流行的實現是XGBoost。
優點
這一方法的強項是它不受信號結構限制,可以引入更多的學習的特徵參數得到複雜模型。
缺點
這一方法的弱點是特徵數的增長很快會影響到算力表現。這種情形下,你應該精心選擇特徵。
ARIMA
ARIMA(整合移動平均自回歸模型)是一個設計得非常簡單的方法,但仍然足夠強大,可以預測信號並指出其中的異常值。
它的思路是過去的若干數據點加上某個隨機變數(通常是白雜訊)可以預測下一個數據點。預測數據點可以進一步用來生成新預測,以此類推。顯然,它的效果是讓信號變得更平滑。
應用這一方法的難點在於你需要通過Box-Jenkins方法選擇差異數、自回歸數、預測誤差係數。
處理新信號時應該創建新ARIMA模型。
另一個麻煩是對信號取差值後得到的信號應該是停滯的。也就是說,信號不應取決於時間,這是一個顯著的限制。
創建一個適應離群點的模型,基於t統計量看它是否比原模型更好地擬合數據,這就可以實現異常檢測。
這一方法的實現,大家比較偏愛R語言的tsoutliers包。它適用於你可以為信號找到一個合適的ARIMA模型的情形,可以檢測出各種異常。
指數平滑
指數平滑技術和ARIMA方法非常類似。基本指數模型等價於ARIMA (0, 1, 1)模型。
從異常檢測的角度來說,我們最感興趣的是Holt-Winters季節性方法。你需要定義季節性周期,比如一周、一月、一年。
萬一你需要追蹤多種季節性周期,比如同時追蹤周和年,你應該選擇其中的一種。通常是選擇最短的周期,比如,在周和年之間選擇周。
很明顯,這是該方法的一個缺陷,會大大影響預測範圍。
和STL或CART一樣,通過統計學檢驗可以實現異常檢測。
神經網路
和CART的情形類似,神經網路有兩種應用方式:監督學習和無監督學習。
由於我們處理的是時序數據,最合適的神經網路類型是LSTM。如果構建得當,這種循環神經網路可以建模時序中最複雜的依賴關係,包括高層季節性依賴。
這一方法在處理耦合的多個時序數據時非常有用(arXiv:1602.07109)。
這一領域仍在研究之中(es2015-56),創建時序模型需要花很多功夫。不過,如果你成功的話,你可能取得突出的精確度。
??建議??
- 嘗試最適合你的問題的最簡單的模型和演算法。
- 如果最簡單的模型不奏效,轉向更高級的技術。
- 從覆蓋所有情形的更通用的解決方案開始是一個很有誘惑力的選項,但它並不總是最佳選擇。
在Statsbot,我們組合使用從STL到CART和LSTM的不同技術,在不同規模上監測異常。
覺得本文有用?請分享本文,幫助其他人發現這篇文章。
推薦閱讀:
※FTRL總結(二)自適應學習率和AdaGrad
※機器如何「猜你喜歡」?深度學習模型在1688的應用實踐
※個性化色彩分享
※基於貝葉斯個性化排序演算法及實現
※推薦系統的幾種形式(python版)