本文總結(jié)了我在時(shí)間序列異常算法方面的一些經(jīng)驗(yàn)焊傅。讀者需要對(duì)常規(guī)機(jī)械學(xué)習(xí)算法有一定的了解。希望本文能幫助有相關(guān)需求的工程師快速切入狈涮。
EGADS Java Library
EGADS (Extendible Generic Anomaly Detection System)是Yahoo一個(gè)開源的大規(guī)模時(shí)間序列異常檢測(cè)項(xiàng)目租冠。它的框架主要由兩個(gè)模塊構(gòu)成，一個(gè)是時(shí)間序列構(gòu)造模塊薯嗤，另一個(gè)是異常檢測(cè)模塊顽爹。給定一段時(shí)間的離散值（構(gòu)成一個(gè)序列），時(shí)間序列模塊會(huì)學(xué)習(xí)這段序列的特征骆姐，并試圖重新構(gòu)建一個(gè)和原序列盡量接近的序列镜粤。結(jié)果和原序列一同送入異常檢測(cè)模塊，基于不同的算法（原則玻褪，閾值）肉渴，異常點(diǎn)會(huì)被標(biāo)記出來。
Time-series Modeling Module
時(shí)間序列構(gòu)造模塊提供了多種算法带射。簡(jiǎn)單介紹如下：
Olympic Model（Seasonal Naive）一個(gè)簡(jiǎn)單的窗口模型同规，對(duì)點(diǎn)Px的預(yù)測(cè)為點(diǎn)Px前n個(gè)值的Smoothed Average.
Exponential Smoothing Model 一個(gè)平滑模型，由簡(jiǎn)單的數(shù)列獲得窟社。ETS模型可以自動(dòng)選擇Single券勺、Double、Triple里面匹配最好的輸出灿里。
Moving Average Model 也是平滑模型关炼，點(diǎn)Px的預(yù)測(cè)值取鄰近點(diǎn)的平均值。
Regression Models 一般是線性回歸匣吊，特殊例子或者異常偏差特別大的時(shí)候有用儒拂。
Anomaly Detection Module
異常檢測(cè)模塊
ExtremeLowDensityModel 超低密度模型，很簡(jiǎn)單有效的密度模型色鸳。
AdaptiveKernelDensityChangePointDetector 拐點(diǎn)檢測(cè)模型
KSigmaModel 經(jīng)典K-sigma模型
DBScanModel（Density-Based Spatial Clustering of Applications with Noise）又是一個(gè)基于密度的模型社痛，在空間中作聚類，如果目標(biāo)序列可以比較好的分類的話會(huì)有不錯(cuò)的效果命雀。
實(shí)踐經(jīng)驗(yàn)
序列構(gòu)造自動(dòng)選優(yōu)
不同類型的數(shù)據(jù)可能適合不同的模型蒜哀。選擇AutoForecastModel，程序會(huì)自動(dòng)把所有TMM都跑一遍咏雌，并推選偏差值最小的模型送入異常檢測(cè)模塊凡怎。值得注意的是校焦，這里自動(dòng)選取的標(biāo)準(zhǔn)只關(guān)注了還原度赊抖，但還原度高并不直接代表能更好的查找異常统倒，在使用本方法的時(shí)候要留意在心。
多數(shù)投票算法
不同的異常檢測(cè)算法從不同的角度定義了異常氛雪。實(shí)踐過程中我發(fā)現(xiàn)房匆，單一異常算法并不能找出所有異常點(diǎn)，同時(shí)還會(huì)出現(xiàn)一系列的假陽性異常报亩。使用Majority Voting浴鸿，規(guī)定半數(shù)以上算法識(shí)別為異常的點(diǎn)才輸出為結(jié)果，在實(shí)際數(shù)據(jù)中提供了遠(yuǎn)高于單一算法的準(zhǔn)確度弦追。
Surus
Surus是Netflix開源的一個(gè)項(xiàng)目岳链，因?yàn)镹etflix內(nèi)部大量使用Pig和Hive，Surus主要的功能是提供RPCA的Pig/Hive封裝劲件。核心算法Robust PCA是Java實(shí)現(xiàn)的掸哑，可以單獨(dú)調(diào)用。
Netflix首先對(duì)他們的問題定了一個(gè)基調(diào)零远。Profile是一個(gè)非常好的習(xí)慣苗分，對(duì)決策者來說可以提供命中率，也就提高了團(tuán)隊(duì)效率牵辣。問題的特征定義如下：
高緯度摔癣。數(shù)據(jù)集緯度高，數(shù)據(jù)間相互交織纬向，人工檢測(cè)基本不可能择浊。
最低加陽性。作為異常檢測(cè)問題逾条，我們不希望有過多的假陽性報(bào)警來干擾監(jiān)控人員近她。
周期性。每小時(shí)/每天/每周/每月這樣的周期性數(shù)據(jù)如果不妥善處理膳帕，某些周期性的行為可能誤報(bào)為異常粘捎。實(shí)際數(shù)據(jù)中，每天固定時(shí)段的峰值數(shù)據(jù)相對(duì)于大部分采樣點(diǎn)都可能被判定為異常危彩，但實(shí)際為周期性正吃苣ィ現(xiàn)象。
數(shù)據(jù)并不是均勻分布的汤徽。像Netflix在兩年中實(shí)現(xiàn)了高增長(zhǎng)娩缰，算法需要足夠健壯來處理非均勻分布的數(shù)據(jù)集(增長(zhǎng)性數(shù)據(jù)是一個(gè)普遍現(xiàn)象，如長(zhǎng)期來看的股市指數(shù)等)谒府。
算法細(xì)節(jié)
Robust PCA是一個(gè)非常常見的主要成分提取算法拼坎。RPCA本質(zhì)其實(shí)是一個(gè)矩陣分解算法浮毯。目標(biāo)是將輸入X分解為X=L+S+E。L代表了X的low rank approximation（低秩估計(jì)）泰鸡。而低秩估計(jì)本質(zhì)就是將矩陣中相關(guān)性強(qiáng)的行投影到更低維的線性空間债蓝，實(shí)現(xiàn)了一個(gè)降維平滑的功能，同時(shí)剔除了冗余信息盛龄，提取了矩陣特征饰迹。提取完主要成分L后，獲得了剩下的稀疏矩陣S余舶，和噪點(diǎn)E啊鸭。
這里做異常檢測(cè)的時(shí)候簡(jiǎn)單認(rèn)為低秩矩陣L就能大部分還原輸入序列。異常點(diǎn)的特征應(yīng)該就表現(xiàn)在S或者E中匿值。實(shí)際應(yīng)用中可以把RPCA作為一個(gè)時(shí)間序列構(gòu)造模型添加入EGADS中赠制，用后者的異常檢測(cè)模塊提取異常。
Isolation Forest
上面兩個(gè)項(xiàng)目使用了若干種類的異常檢測(cè)算法挟憔。如基于模型的（統(tǒng)計(jì)模型钟些，線性模型）；基于距離的（K臨近等聚類算法）曲楚；基于密度模型的（Extreme Low Density Model）厘唾。隔離森林（Isolation Forest）跟他們都有比較明顯的區(qū)別。論文代碼
在訓(xùn)練階段龙誊，小樣本抽樣更利于獲得優(yōu)質(zhì)的分類結(jié)果抚垃。
因?yàn)椴挥糜?jì)算點(diǎn)與點(diǎn)直接的距離，計(jì)算時(shí)間大大優(yōu)于各種基于距離的算法趟大。
同樣因?yàn)樾颖境闃雍蟮资鳎瑫r(shí)間、空間復(fù)雜度都可以維持在相當(dāng)?shù)偷乃健?/p>
基于上一點(diǎn)逊朽，iForest有能力處理超高維罕伯，超大規(guī)模的數(shù)據(jù)。
iForest適用場(chǎng)景需要符合兩個(gè)要求：1. 異常點(diǎn)非常少 2. 異常點(diǎn)的某些屬性要跟正常點(diǎn)非常不同叽讳。
iForest是基于隨機(jī)森林的算法追他。對(duì)異常的分類能力基于兩個(gè)假設(shè)：
數(shù)據(jù)集中少數(shù)的異常點(diǎn)會(huì)形成少量的聚類。
異常點(diǎn)具有明顯不同的屬性岛蚤，使他們很快在分類中被區(qū)分出來邑狸。正常點(diǎn)很難被分類，而存在于樹的更深層涤妒。
上圖橫坐標(biāo)表示了隨機(jī)森林的迭代過程单雾。選取一個(gè)異常點(diǎn)Xo和一個(gè)正常點(diǎn)Xi。縱軸代表了點(diǎn)Xo和Xi在迭代中被區(qū)分出時(shí)樹深度的平均值硅堆∮齑ⅲ可以明顯的看到，正常節(jié)點(diǎn)平均需要12次隨機(jī)分類渐逃，而異常點(diǎn)只需要4次多就可以被區(qū)分出來够掠。
上圖展示了小規(guī)模隨機(jī)抽樣同樣可以達(dá)到非常好的聚類效果。這在處理大規(guī)模數(shù)據(jù)的時(shí)候尤其有用朴乖，在多篇文章中祖屏，iForest因?yàn)檫@一特性被推薦為首選算法助赞。實(shí)現(xiàn)方面有R买羞，Java，Python雹食，搜索一下就有畜普。
BENCHMARKING ALGORITHMS FOR DETECTING ANOMALIES IN LARGE DATASETS
這篇論文使用了比較常見，簡(jiǎn)單易得的算法群叶，基于學(xué)術(shù)界認(rèn)可的標(biāo)準(zhǔn)數(shù)據(jù)集吃挑，進(jìn)行了一系列性能，準(zhǔn)確度試驗(yàn)街立，希望得到異常檢測(cè)這一問題的一個(gè)基準(zhǔn)舶衬。
本文使用了以下幾種算法，因?yàn)槭钦{(diào)用的Weka赎离，所以算是比較簡(jiǎn)單的試驗(yàn)逛犹。
K鄰近（K Nearest Neighbor）
多層神經(jīng)網(wǎng)絡(luò)（Multi-layer Perceptron） 可以簡(jiǎn)單認(rèn)為是一個(gè)復(fù)雜參數(shù)學(xué)習(xí)的分類器。
基于密度的聚類算法：LOF (Local Outlier Factor)
隨機(jī)森林（Random Forest）
Isolation Forest
經(jīng)過一系列試驗(yàn)梁剔，結(jié)論中推舉了以下步驟：
如果是維度非常高的數(shù)據(jù)虽画，用J48選Attribute。
用iForest預(yù)選異常點(diǎn)荣病，標(biāo)準(zhǔn)為score > 0.50
把ANN码撰，J48，RF作為一個(gè)組合再處理2步得到的異常點(diǎn)个盆。
被較多算法標(biāo)注為異常的點(diǎn)就認(rèn)為有高可信度脖岛。
主要數(shù)據(jù)集
KDDCUP99網(wǎng)絡(luò)流數(shù)據(jù)。常用入侵檢測(cè)數(shù)據(jù)颊亮，學(xué)術(shù)界大量使用柴梆。不過據(jù)說后來被證明不太可靠。
Amazon監(jiān)控?cái)?shù)據(jù)Amazon EC2性能檢測(cè)的真實(shí)檢測(cè)數(shù)據(jù)编兄，放出的數(shù)據(jù)有真實(shí)異常轩性，并且有人工標(biāo)注。
內(nèi)部威脅數(shù)據(jù)CERT人造的內(nèi)部威脅數(shù)據(jù)。人造的方法還是比較科學(xué)的揣苏，不過異常模式比較簡(jiǎn)單悯嗓，知道答案倒推就很容易。不過要自己發(fā)現(xiàn)異常就需要比較大的工作量了卸察。
