基於統計的異常檢測方法S-H-ESD[twitter]

　　

　　by：RandomWalk 阿里巴巴 算法工程師

　　

Automatic Anomaly Detection in the Cloud Via Statistical Learning [1]

　　原文主要介紹了twitter雲系統中利用統計學習實現異常檢測的自動化，下面直接介紹相關方法。

　　Grubbs Test

　　表示一組時間序列，Grubbs test 檢測單變量數據集的「最異常點「。前提假設數據分布是正態的。Grubbs test假設定義如下：

　　：數據集中沒有異常點

　　: 數據集中有至少一個異常點

　　Grubbs『 test 統計量定義如下

　　其中 和 分別表示數據集的均值和方差。對於雙邊檢驗，當滿足式(2)時，以顯著性水平 拒絕原假設

　　其中 表示自由度 ，顯著性水平 的 分布的上臨界值。對於單邊檢驗，變為[2]。但是缺點是數據集中存在多個異常點則不適合，因為 分布表不會更新。下面介紹多異常點的檢測算法ESD（Extreme Studentized Deviate）[3]。

　　ESD

　　ESD可以檢測時間序列數據的多異常點。需要指定異常點比例的upper bound是k，最差的情況是至多49.9%。實際中，數據集的異常比例一般不超過5%。ESD假設定義如下：

　　：數據集中沒有異常點

　　: 數據集中有至多 個異常點

　　檢驗統計量和臨界值分別定義如下

　　其中 ，ESD會重複 次檢驗，當 時，則有至少 個異常點。對於Grubbs Test和ESD的區別[4]，主要兩點：一是ESD會根據不同的離群值調整臨界值；二是ESD一直會檢驗 個離群點，而Grubbs test可能會提前結束檢驗（當「最異常點」檢驗時 成立）。比如下面Rosner paper中的數據，設置 ，第一次和第二次檢驗接受原假設，由於剔除前兩個值之後臨界值 的變化，在第三次檢驗拒絕了原假設，因此最終得到三個異常點。

　　
前10離群點中第三個點檢測為異常，則至少有3個異常點 S-ESD

　　考慮ESD有如下兩個限制：一是對於具有季節性的時間序列異常不能很好的識別，下圖1中很多周期性變化的點並非異常點；二是多峰分布的數據點，一些低峰異常數據點不能被識別出來，如圖2。

　　
圖1 時間序列圖

　　

　　圖2 數據分布圖

　　因此介紹S-ESD（Seasonal-ESD），Algorithm 1 中主要的不同是對時間序列數據進行STL分解，剔除其中的季節項，中位數做為趨勢項（STL Variant），對殘差項進行ESD檢驗。STL variant不同於STL主要考慮圖3的情形，（a）中的STL分解得到的殘差項，其中紅色陰影部分存在spurious anomalies（這些點在原時間序列中並非異常）。

　　

　　

　　圖3 STL和變形STL分解對比圖

　　（局部異常和全局異常可識別性）S-ESD通過分解之後對殘差項進行ESD檢驗，不僅可檢驗全局異常點，而且可以檢驗出如圖4的局部異常點，這些異常點在原始數據中介於季節項的最大值和最小值之間，直接對原始數據ESD檢驗則無法識別。

　　
圖4 局部異常和全局異常對比 S-H-ESD

　　但是S-ESD也有局限性，就是對於數據中含有異常點數量較多時，很難識別較多的異常點。因此下面介紹Seasonal Hybrid ESD (S-H-ESD)，首先介紹MAD。

　　MAD

　　考慮到ESD的檢驗統計量中的均值和方差對於過大的異常值較為敏感，於是選擇利用MAD(Median Absolute Deviation)進行代替，如下

　　更一般的可以使用 或者 。

　　因此S-H-ESD相比S-ESD，是把ESD中的均值方差計算的統計量替換成MAD，圖5比較了兩種方法的效果，S-H-ESD對於異常點的識別率更高，同時由於計算中位數，時間複雜度也相對會更高。

　　
圖5 S-ESD和S-H-ESD對比 python實現

　　推薦pyculiarity，原文的github地址是R的實現。

　　Pyculiarity是twitter時序數據異常檢測AnomalyDetection[1]的python實現版本。主要是基於ESD（Extreme Studentized Deviate test）原理的異常檢測算法。ESD的主要思想就是檢驗最大值、最小值偏離均值的程度是否為異常，具體可參考[2]。通過閱讀pyculiarity的源碼[3]，了解其主要包含兩個方法：

　　

主要參數：

　　df：包含時間和值的DataFrame

　　

　　max_anoms=0.10：發現異常數據的量（佔總體的百分之多少）

　　

　　direction=』pos』：』pos』是發現數據突增點，』neg』是發現數據突降點，』both』是包含突增與突降

　　

　　alpha=0.05：接受或拒絕顯著性水平，即p-value

　　

　　only_last=None：僅再時間序列最後1天（』day』）或1小時（』hr』）尋找異常

　　

　　threshold=None：僅報告高於指定閾值的正向異常。選項有：

　　

　　med_max：每日最大值的中位數

　　

　　p95：每日最大值的95%

　　

　　p99：每日最大值的99%

　　

　　e_value=False：返回數據中新增一列期望值

　　

　　longterm=False：當時間序列超過一個月時，設置此值，

　　

　　piecewise_median_period_weeks=2：當設置longterm後需要設置該值，設置滑動窗口的大小，注意這裡需要>=2

　　

　　plot=False：輸出圖像，已經不支持

　　

　　y_log=False：對Y軸值取對數

　　

　　xlabel = 」：添加輸出到圖形的X軸標籤

　　

　　ylabel = 『count』：添加輸出到圖形的Y軸標籤

　　

　　title=None：輸出圖像的標籤

　　

　　verbose=False：是否輸出debug信息

　　

示例代碼：

//data為包含[時間，數值]兩列的dataframe
results=detect_ts(data,max_anoms=0.4,alpha=0.05,direction='both',only_last=None,longterm=True, piecewise_median_period_weeks=2)
//結果可視化
data['timestamp'] = pd.to_datetime(data['timestamp'])
data.set_index('timestamp', drop=True)

　　f, ax = plt.subplots(2, 1, sharex=True)
ax[0].plot(data['timestamp'], data['value'], 'b')
ax[0].plot(results['anoms'].index, results['anoms']['anoms'], 'ro')
ax[0].set_title('Detected Anomalies')
ax[1].set_xlabel('Time Stamp')
ax[0].set_ylabel('Count')
ax[1].plot(results['anoms'].index, results['anoms']['anoms'], 'b')
ax[1].set_ylabel('Anomaly Magnitude')
plt.show()參考

　　

　　^Hochenbaum J, Vallis O S, Kejariwal A. Automatic anomaly detection in the cloud via statistical learning[J]. arXiv preprint arXiv:1704.07706, 2017.

　　

　　^Francisco Augusto Alcaraz Garcia. Tests to identify outliers in data series. Pontifical Catholic University of Rio de Janeiro, Industrial Engineering Department, Rio de Janeiro, Brazil, 2012.

　　

　　^Bernard Rosner. On the detection of many outliers. Technometrics, 17(2):221–227, 1975.

　　

　　^https://www.itl.nist.gov/div898/handbook/eda/section3/eda35h3.htm

　　

　　^https://github.com/twitter/AnomalyDetection

　　

　　

特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺「網易號」用戶上傳並發布，本平臺僅提供信息存儲服務。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.