基于統(tǒng)計(jì)的異常檢測(cè)方法S-H-ESD[twitter]

↑↑↑點(diǎn)擊上方藍(lán)字，回復(fù)資料，10個(gè)G的驚喜
by：RandomWalk ?阿里巴巴 算法工程師

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

原文主要介紹了twitter云系統(tǒng)中利用統(tǒng)計(jì)學(xué)習(xí)實(shí)現(xiàn)異常檢測(cè)的自動(dòng)化，下面直接介紹相關(guān)方法。

Grubbs Test

?表示一組時(shí)間序列，Grubbs test 檢測(cè)單變量數(shù)據(jù)集的“最異常點(diǎn)“。前提假設(shè)數(shù)據(jù)分布是正態(tài)的。Grubbs test假設(shè)定義如下：

?：數(shù)據(jù)集中沒(méi)有異常點(diǎn)

?: 數(shù)據(jù)集中有至少一個(gè)異常點(diǎn)

Grubbs‘ test 統(tǒng)計(jì)量定義如下

其中??和??分別表示數(shù)據(jù)集的均值和方差。對(duì)于雙邊檢驗(yàn)，當(dāng)滿(mǎn)足式(2)時(shí)，以顯著性水平??拒絕原假設(shè)

其中??表示自由度??，顯著性水平??的??分布的上臨界值。對(duì)于單邊檢驗(yàn)，變?yōu)?img data-ratio="0.6190476190476191" src="https://filescdn.proginn.com/fbcae8657f6c580acc71676bf0f05d00/92d4f4045bc812e04255a86a42419948.webp" data-type="svg" data-w="42" style="vertical-align: middle;margin-right: 3px;margin-left: 3px;display: inline-block;">^[2]。但是缺點(diǎn)是數(shù)據(jù)集中存在多個(gè)異常點(diǎn)則不適合，因?yàn)??分布表不會(huì)更新。下面介紹多異常點(diǎn)的檢測(cè)算法ESD（Extreme Studentized Deviate）^[3]。

ESD

ESD可以檢測(cè)時(shí)間序列數(shù)據(jù)的多異常點(diǎn)。需要指定異常點(diǎn)比例的upper bound是k，最差的情況是至多49.9%。實(shí)際中，數(shù)據(jù)集的異常比例一般不超過(guò)5%。ESD假設(shè)定義如下：

?：數(shù)據(jù)集中沒(méi)有異常點(diǎn)

?: 數(shù)據(jù)集中有至多??個(gè)異常點(diǎn)

檢驗(yàn)統(tǒng)計(jì)量和臨界值分別定義如下

其中??，ESD會(huì)重復(fù)??次檢驗(yàn)，當(dāng)??時(shí)，則有至少??個(gè)異常點(diǎn)。對(duì)于Grubbs Test和ESD的區(qū)別^[4]，主要兩點(diǎn)：一是ESD會(huì)根據(jù)不同的離群值調(diào)整臨界值；二是ESD一直會(huì)檢驗(yàn)??個(gè)離群點(diǎn)，而Grubbs test可能會(huì)提前結(jié)束檢驗(yàn)（當(dāng)“最異常點(diǎn)”檢驗(yàn)時(shí)??成立）。比如下面Rosner paper中的數(shù)據(jù)，設(shè)置??，第一次和第二次檢驗(yàn)接受原假設(shè)，由于剔除前兩個(gè)值之后臨界值??的變化，在第三次檢驗(yàn)拒絕了原假設(shè)，因此最終得到三個(gè)異常點(diǎn)。

S-ESD

考慮ESD有如下兩個(gè)限制：一是對(duì)于具有季節(jié)性的時(shí)間序列異常不能很好的識(shí)別，下圖1中很多周期性變化的點(diǎn)并非異常點(diǎn)；二是多峰分布的數(shù)據(jù)點(diǎn)，一些低峰異常數(shù)據(jù)點(diǎn)不能被識(shí)別出來(lái)，如圖2。

因此介紹S-ESD（Seasonal-ESD），Algorithm 1 中主要的不同是對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行STL分解，剔除其中的季節(jié)項(xiàng)，中位數(shù)做為趨勢(shì)項(xiàng)（STL Variant），對(duì)殘差項(xiàng)進(jìn)行ESD檢驗(yàn)。STL variant不同于STL主要考慮圖3的情形，（a）中的STL分解得到的殘差項(xiàng)，其中紅色陰影部分存在spurious anomalies（這些點(diǎn)在原時(shí)間序列中并非異常）。

（局部異常和全局異?？勺R(shí)別性）S-ESD通過(guò)分解之后對(duì)殘差項(xiàng)進(jìn)行ESD檢驗(yàn)，不僅可檢驗(yàn)全局異常點(diǎn)，而且可以檢驗(yàn)出如圖4的局部異常點(diǎn)，這些異常點(diǎn)在原始數(shù)據(jù)中介于季節(jié)項(xiàng)的最大值和最小值之間，直接對(duì)原始數(shù)據(jù)ESD檢驗(yàn)則無(wú)法識(shí)別。

S-H-ESD

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

MAD

考慮到ESD的檢驗(yàn)統(tǒng)計(jì)量中的均值和方差對(duì)于過(guò)大的異常值較為敏感，于是選擇利用MAD(Median Absolute Deviation)進(jìn)行代替，如下

更一般的可以使用??或者??。

因此S-H-ESD相比S-ESD，是把ESD中的均值方差計(jì)算的統(tǒng)計(jì)量替換成MAD，圖5比較了兩種方法的效果，S-H-ESD對(duì)于異常點(diǎn)的識(shí)別率更高，同時(shí)由于計(jì)算中位數(shù)，時(shí)間復(fù)雜度也相對(duì)會(huì)更高。

python實(shí)現(xiàn)

推薦pyculiarity，原文的github地址是R的實(shí)現(xiàn)。

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

• detect_ts：用于時(shí)序數(shù)據(jù)，輸入的DataFrame需要兩列數(shù)據(jù)，其中一列為時(shí)間，另一列為該時(shí)間點(diǎn)對(duì)應(yīng)的值

• detect_vec：用于向量數(shù)據(jù)，可以不包含是時(shí)間列，時(shí)間索引按照DataFrame長(zhǎng)度自動(dòng)生成。

主要參數(shù)：

• df：包含時(shí)間和值的DataFrame

• max_anoms=0.10：發(fā)現(xiàn)異常數(shù)據(jù)的量（占總體的百分之多少）

• direction=’pos’：’pos’是發(fā)現(xiàn)數(shù)據(jù)突增點(diǎn)，’neg’是發(fā)現(xiàn)數(shù)據(jù)突降點(diǎn)，’both’是包含突增與突降

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

• only_last=None：僅再時(shí)間序列最后1天（’day’）或1小時(shí)（’hr’）尋找異常

• threshold=None：僅報(bào)告高于指定閾值的正向異常。選項(xiàng)有：

• med_max：每日最大值的中位數(shù)

• p95：每日最大值的95%

• p99：每日最大值的99%

• e_value=False：返回?cái)?shù)據(jù)中新增一列期望值

• longterm=False：當(dāng)時(shí)間序列超過(guò)一個(gè)月時(shí)，設(shè)置此值，

• piecewise_median_period_weeks=2：當(dāng)設(shè)置longterm后需要設(shè)置該值，設(shè)置滑動(dòng)窗口的大小，注意這里需要>=2

• plot=False：輸出圖像，已經(jīng)不支持

• y_log=False：對(duì)Y軸值取對(duì)數(shù)

• xlabel = ”：添加輸出到圖形的X軸標(biāo)簽

• ylabel = ‘count’：添加輸出到圖形的Y軸標(biāo)簽

• title=None：輸出圖像的標(biāo)簽

• verbose=False：是否輸出debug信息

示例代碼：

//data為包含[時(shí)間，數(shù)值]兩列的dataframe
results=detect_ts(data,max_anoms=0.4,alpha=0.05,direction='both',only_last=None,longterm=True, piecewise_median_period_weeks=2)
//結(jié)果可視化
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()

參考

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

2. ^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.

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

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

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

「回歸分析」知識(shí)點(diǎn)梳理

CSDN資源，免費(fèi)下載！

眾所周知,B站并不是個(gè)學(xué)習(xí)網(wǎng)站