2-1 異常檢測（Anomaly detection）方法小結(jié)

??異常檢測技術(shù)被廣泛應(yīng)用到各個應(yīng)用領(lǐng)域之中，包括疾病檢測、金融欺詐檢測、網(wǎng)絡(luò)入侵檢測等。在智能運維領(lǐng)域，異常檢測處理的數(shù)據(jù)類型主要是時間序列數(shù)據(jù)（KPI序列）和文本數(shù)據(jù)（日志），處理方法主要有基于規(guī)則處理、基于統(tǒng)計學(xué)處理和基于機器學(xué)習(xí)處理，在機器學(xué)習(xí)處理方法中，根據(jù)數(shù)據(jù)的標(biāo)簽情況，又分為有監(jiān)督、半監(jiān)督和無監(jiān)督三種情況。
??異常數(shù)據(jù)主要包括三類：異常點、背景異常、群體異常。異常點是最常見的一種。背景異常是指，在特定的背景下是異常數(shù)據(jù)，在其他背景下不是異常數(shù)據(jù)。群體異常是指，某個群體內(nèi)的單個數(shù)據(jù)不像是異常的，但這個群體在整個數(shù)據(jù)集中是異常的。
??文章首先按照基于規(guī)則、基于統(tǒng)計、基于機器學(xué)習(xí)三個方向?qū)Ξ惓z測算法做了總結(jié)，然后又分高維數(shù)據(jù)、時間序列數(shù)據(jù)和文本數(shù)據(jù)三部分做了介紹，最后總結(jié)了下常用算法的優(yōu)缺點以及相應(yīng)的參考文獻。重點部分和重點論文已用黑體加粗。

一、基于規(guī)則處理

??這種方法第一步需要獲取規(guī)則，主要有兩種方法，一是設(shè)計算法自動提取，二是專家手工制定。第二步是判斷行為是否和異常規(guī)則相似。
??優(yōu)點：可以精準(zhǔn)找出符合規(guī)則的異常
??缺點：受限于專家知識，規(guī)則庫可能不完善；
????規(guī)則庫需要經(jīng)常更新，否則無法發(fā)現(xiàn)新的異常種類；
????在將行為和規(guī)則庫對比時，會花費一些時間（取決于規(guī)則庫的大?。?。

二、基于統(tǒng)計學(xué)處理

??需要假設(shè)數(shù)據(jù)服從某種分布，然后利用數(shù)據(jù)去進行參數(shù)估計。
??方法主要三種，簡單的比如有3σ準(zhǔn)則、箱型圖、Grubbs檢驗等。復(fù)雜點的比如有時間序列建模（移動平均、指數(shù)平滑、ARMA、ARIMA）。還有混合方法，假設(shè)正常數(shù)據(jù)和異常數(shù)據(jù)來自不同的高斯分布，然后用Grubbs檢驗；或者僅對正常數(shù)據(jù)進行混合高斯建?；蛘卟此山５鹊?。
??優(yōu)點：適合低維數(shù)據(jù)、魯棒性較好
??缺點：對假設(shè)依賴比較嚴重

三、基于機器學(xué)習(xí)處理

??無監(jiān)督：無標(biāo)注，假設(shè)數(shù)據(jù)中正常數(shù)據(jù)比異常數(shù)據(jù)多很多。常用方法分為基于統(tǒng)計分布、基于距離、基于密度、基于距離、基于聚類和基于樹的五類方法。
??半監(jiān)督：被標(biāo)注的全是正常數(shù)據(jù)。常用方法包括one-class SVM、AutoEncoder、GMM等。
??有監(jiān)督：數(shù)據(jù)標(biāo)注是個問題，并且處理時需要注意類別不均衡現(xiàn)象，不適用于檢測新類別。常用方法包括LR、SVM、RF、NN等。

3.1 無監(jiān)督方法

??在實際應(yīng)用場景中，數(shù)據(jù)大多是沒有標(biāo)簽的，因此無監(jiān)督方法是實際應(yīng)用中使用最廣泛的方法。

3.1.1 基于統(tǒng)計分布

HBOS：基于直方圖的異常檢測
??過程類似于樸素貝葉斯模型。假設(shè)特征相互獨立，對每個特征作直方圖，對于某個樣例，連乘其特征在各個直方圖中的頻率得到該樣例的生成概率。
??優(yōu)點：
????速度快，適合大數(shù)據(jù)情形
??缺點：
????特征相互獨立的條件比較強，現(xiàn)實中可能不符合
????不適合異常數(shù)據(jù)過多的情形

3.1.2 基于距離（KNN）

??這種方法認為異常點距離正常點比較遠，因此可以對于每一個數(shù)據(jù)點，計算它的K-近鄰距離（或平均距離），并將距離與閾值進行比較。若大于閾值，則認為是異常點?；蛘呤菍⑷繕颖镜腒-近鄰距離排序，取前n個最大的作為異常點。計算距離時一般使用歐式距離，也可以使用角度距離。
基于距離的異常檢測優(yōu)缺點
??優(yōu)點：
????不需要假設(shè)數(shù)據(jù)的分布
??缺點：
????不適合高維數(shù)據(jù)
????只能找出異常點，無法找出異常簇
????你每一次計算近鄰距離都需要遍歷整個數(shù)據(jù)集，不適合大數(shù)據(jù)及在線應(yīng)用
????有人用hyper-grid技術(shù)提速將KNN應(yīng)用到在線情況，但是還不是足夠快
????參數(shù)K和閾值需要人工調(diào)參
????當(dāng)正常點較少、異常點較多時，該方法不好使
????當(dāng)使用歐式距離時，即默認是假設(shè)數(shù)據(jù)是球狀分布，因此在邊界處不容易識別異常
????僅可以找出全局異常點，無法找到局部異常點

3.1.3 基于密度（KNN）

??基于距離的方法中，閾值是一個固定值，屬于全局性方法。但是有的數(shù)據(jù)集數(shù)據(jù)分布不均勻，有的地方比較稠密，有的地方比較稀疏，這就可能導(dǎo)致閾值難以確定（稠密的地方和稀疏的地方最好不用同一閾值）。我們需要根據(jù)樣本點的局部密度信息去判斷異常情況?；诿芏鹊姆椒ㄖ饕蠰OF、COF、ODIN、MDEF、INFLO、LoOP、LOCI、aLOCI等。
LOF
??首先對于每一個數(shù)據(jù)點，找出它的K個近鄰，然后計算LOF得分，得分越高越可能是異常點。
??LOF是一個比值，分子是K個近鄰的平均局部可達密度，分母是該數(shù)據(jù)點的局部可達密度。可達密度是一個比值，分子是K-近鄰的個數(shù)，分母是K-近鄰可達距離之和。A到B的可達距離定義：A和B的真實距離與B的k-近鄰距離的最大值。
COF
??LOF中計算距離是用的歐式距離，也是默認了數(shù)據(jù)是球狀分布，而COF的局部密度是根據(jù)最短路徑方法求出的，也叫做鏈?zhǔn)骄嚯x。
INFLO
??LOF容易將邊界處的點判斷為異常，INFLO在計算密度時，利用k近鄰點和反向近鄰集合，改善了LOF的這個缺點。
LoOP
??將LOF中計算密度的公式加了平方根，并假設(shè)近鄰距離的分布符合正態(tài)分布。
??其他算法具體細節(jié)還沒有看。
基于密度的異常檢測優(yōu)缺點
優(yōu)點：
??可以找出分布不均勻的數(shù)據(jù)中局部異常的數(shù)據(jù)
??可以給出數(shù)據(jù)的異常得分，得分越高越可能異常，不是二分類
缺點：
??不適合高維數(shù)據(jù)
??由于需要遍歷數(shù)據(jù)計算距離，因此計算復(fù)雜度也很高，不適合在線應(yīng)用
??只能找到異常點，無法找出異常簇
??需要人工調(diào)參

3.1.4 基于聚類

??此類方法主要有三種假設(shè)，三種假設(shè)下有各自的方法。計算復(fù)雜度很大程度上取決于聚類算法的計算復(fù)雜度。
??假設(shè)一：不屬于任何聚類的點是異常點，主要方法包括DBSCAN、SNN clustering、FindOut algorithm、WaveCluster Algorithm。
??缺點：不能發(fā)現(xiàn)異常簇

??假設(shè)二：距離最近的聚類結(jié)果較遠的點是異常點，主要方法包括K-Means、Self-Organizing Maps（SOM）、GMM。
??首先進行聚類，然后計算樣例與其所屬聚類中心的距離，計算其所屬聚類的類內(nèi)平均距離，用兩者的比值衡量異常程度。
??缺點：不能發(fā)現(xiàn)異常簇

??假設(shè)三：稀疏聚類和較小的聚類里的點都是異常點，主要方法包括CBLOF、LDCOF、CMGOS等。
??首先進行聚類，然后啟發(fā)式地將聚類簇分成大簇和小簇。如果某一樣例屬于大簇，則利用該樣例和其所屬大簇計算異常得分，如果某一樣例屬于小簇，則利用該樣例和距離其最近的大簇計算異常得分。三種算法的區(qū)別在于計算異常得分的方式不同，具體細節(jié)還未看。
??優(yōu)點：考慮到了數(shù)據(jù)全局分布和局部分布的差異，可以發(fā)現(xiàn)異常簇

基于聚類的異常檢測優(yōu)缺點：
??優(yōu)點：
????測試階段會很快，以內(nèi)只需要和有限個簇比較
????有些聚類算法（k-means）可以在線應(yīng)用（準(zhǔn)實時）
??缺點：
????異常檢測效果很大程度上依賴于聚類效果，但是聚類算法主要目的是聚類，并不是為了異常檢測
????大數(shù)據(jù)聚類計算開銷比較大，可能是個瓶頸

3.1.5 基于樹

??此類方法的思想是通過劃分子空間尋找異常點，不同的方法區(qū)別主要在三個地方：特征的選取、分割點的選取和分類空間打標(biāo)簽的方案。此類方法不受球形鄰近的限制，可以劃分任意形狀的異常點。此類方法主要包括iForest、SCiForest、RRCF
iForest
??此方法適用于異常點較少的情況，采用構(gòu)造多個決策樹的方式進行異常檢測。對數(shù)據(jù)集進行有放回抽樣，對每一次抽樣出來的樣本構(gòu)建二叉樹，構(gòu)建二叉樹時，隨機選取一個特征，然后在特征上隨機選一個分割點，將該特征小于分割點的數(shù)據(jù)放在二叉樹左邊，反之放在右邊，直至二叉樹達到一定深度或者葉子節(jié)點只包含一個數(shù)據(jù)點為止。進行異常檢測時，計算該數(shù)據(jù)點在多個二叉樹上的平均深度，深度越淺越可能是異常值。
??iForest只適合檢測全局異常點，不適合檢測局部異常點，因此有人做了改進, 論文為Improving iForest with Relative Mass.
SCiForest
??傳統(tǒng)iForest方法在選擇特征是隨機選取的，SCiForest在選擇特征時利用了方差；傳統(tǒng)iForest選擇分割點后形成的分割超平面是平行于坐標(biāo)軸的，SCiForest可以生成任意角度的分割超平面。
RRCF
??可以動態(tài)增刪樹種的節(jié)點，適用于流數(shù)據(jù)異常檢測

基于樹的異常檢測優(yōu)缺點：
??優(yōu)點：
????每棵樹都是獨立構(gòu)建，適合分布式計算
????可以分割任意形狀的數(shù)據(jù)集，不受限于球形近鄰
????測試時速度很快，適合在線處理
??缺點：
????只適用于異常點較少的情況
????不適合高維數(shù)據(jù)，因為高維數(shù)據(jù)會有很多無關(guān)特征

3.2 半監(jiān)督方法

??此類方法適用于標(biāo)注的數(shù)據(jù)全都是正常數(shù)據(jù)，常用方法有one-class SVM、SVDD、AutoEncoder、GMM、Na?ve Bayes等。此類方法與無監(jiān)督方法有些重合，因為無監(jiān)督方法的基本假設(shè)就是數(shù)據(jù)集中正常數(shù)據(jù)遠遠多于異常數(shù)據(jù)。
One-class SVM
??利用核函數(shù)將數(shù)據(jù)映射到高維空間，尋找超平面使得數(shù)據(jù)和坐標(biāo)原點間隔最大
SVDD
??利用核函數(shù)將數(shù)據(jù)映射到高維空間，尋找盡可能小的超球體包裹住正常數(shù)據(jù)。
AutoEncoder
??對正常數(shù)據(jù)進行訓(xùn)練Encoder和Decoder，進行異常檢測時，如果Decoder出來的向量與原始向量差別很大，就認為是異常數(shù)據(jù)。
GMM
??對正常數(shù)據(jù)進行高斯混合模型建模，最大似然估計參數(shù)。進行異常檢測時，將其特征帶入模型，可得出它屬于正常數(shù)據(jù)的概率。
Na?ve Bayes
??過程同高斯混合模型。

3.3 有監(jiān)督方法

??常規(guī)分類器都可以使用，需要注意樣本不均衡問題。通常情況下，異常樣本會遠遠小于正常樣本，因此需要處理樣本不均衡問題，比如上采樣、下采樣、調(diào)整閾值等等。評估時需要靠precision和recall，而不是accuracy。

四、數(shù)據(jù)類型

4.1. 高維數(shù)據(jù)

??在高維數(shù)據(jù)中，傳統(tǒng)的異常數(shù)據(jù)的定義不能再使用，利用上述方法在高維空間中直接尋找異常點效果也不好。常用的方法是使用降維技術(shù)，在降維后的子空間里尋找異常點。常用的降維技術(shù)有PCA、kernal PCA、AutoEncoder、深度信念網(wǎng)絡(luò)等，其中深度信念網(wǎng)絡(luò)效果是相對比較好的。

4.2. 時間序列數(shù)據(jù)

??這種情況往往屬于有監(jiān)督類型。處理時間序列數(shù)據(jù)時，常常是利用一些統(tǒng)計方法構(gòu)造特征，然后利用分類器進行分類。構(gòu)造特征的方法包括移動平均、指數(shù)平滑等時間序列相關(guān)知識。

4.3. 文本數(shù)據(jù)

??基于日志的異常檢測通常包括三類：基于規(guī)則、有監(jiān)督和無監(jiān)督。
??基于規(guī)則的方法需要人工制定規(guī)則，優(yōu)缺點前面已說到。
??有監(jiān)督方法是常規(guī)的二分類任務(wù)，同樣有樣本不均衡問題。
??無監(jiān)督方法中，傳統(tǒng)是首先解析出日志模板，然后劃定時間窗，在每個時間窗內(nèi)將多條日志編碼成向量，然后用PCA等無監(jiān)督方式進行異常檢測。缺點是只能判斷某時間窗內(nèi)是否有數(shù)據(jù)異常，無法判斷單個日志是否異常。
??一篇論文（DeepLog）提供了另外一個思路，屬于無監(jiān)督類型。首先對日志進行解析，得到日志模板和日志變量，分別使用LSTM判斷流數(shù)據(jù)中日志模板是否正常、日志變量是否正常。其中，對于判斷模板是否正常，做法是將每一個模板當(dāng)成一個單詞，基于正常數(shù)據(jù)使用LSTM擬合模板數(shù)據(jù)流。對于判斷變量是否正常，做法是將數(shù)據(jù)流按模板分開，生成每一個模板對應(yīng)的數(shù)據(jù)流，然后每一個模板數(shù)據(jù)流里的變量流進行LSTM擬合。在異常檢測時，判斷待檢測值是否出現(xiàn)在LSTM的輸出概率最高前K個值，如果出現(xiàn)就說明正常。

五、參考文獻

方法 論文
**HBOS **M. Goldstein, A. Dengel. Histogram-based Outlier Score (HBOS): A fast Unsupervised Anomaly Detection Algorithm[C]. In: W?lfl S, editor. KI-2012: Poster and Demo Track. Online;2012. p. 59–63
GMM X. Yang, L. J. Latecki, D. Pokrajac. Outlier Detection with Globally Optimal Exemplar-Based GMM[C]. Siam International Conference on Data Mining, SDM 2009, April 30 - May 2, 2009, Sparks, Nevada, Usa. DBLP, 2009:145-154
KNN S. Ramaswamy, R. Rastogi, K. Shim. Efficient Algorithms for Mining Outliers from Large Data Sets [C]. ACM SIGMOD International Conference on Management of Data. ACM, 2000:427-438、F. Angiulli, C. Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. European Conference on Principles of Data Mining and Knowledge Discovery. Springer-Verlag, 2002:15-26
KNN-weight F. Angiulli, C. Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. European Conference on Principles of Data Mining and Knowledge Discovery. Springer-Verlag, 2002:15-26
**LOF M. M. Breunig. LOF: identifying density-based local outliers[J]. 2000, 29(2):93-104
COF J. Tang, Z. Chen, A. Fu, D. Cheung. Enhancing Effectiveness of Outlier Detections for Low Density Patterns[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Berlin, Heidelberg, 2002:535-548
INFLO W. Jin, A. K. H. Tung, J. Han, et al. Ranking Outliers Using Symmetric Neighborhood Relationship[J]. Lecture Notes in Computer Science, 2006, 3918:577-593.
**LoOP H. P. Kriegel, E. Schubert, A. Zimek. LoOP:local outlier probabilities[C]. ACM, 2009:1649-1652
CBLOF Z. He, X. Xu, S. Deng. Discovering cluster-based local outliers[J]. Pattern Recognition Letters, 2003, 24(9–10):1641-1650
LFCOF M Amer, M. Goldstein. Nearest-Neighbor and Clustering based Anomaly Detection Algorithms for RapidMiner[C]. Rapidminer Community Meeting and Conferernce. 2012
CMGOS M. Goldstein. Anomaly Detection in Large Datasets[M]. 2014
**DBSCAN+GMM Bigdeli E, Mohammadi M, Raahemi B, et al. A fast and noise resilient cluster-based anomaly detection[J]. Pattern Analysis & Applications, 2017, 20(1):1-17.
**iForest F. T. Liu, M. T. Kai, Z. H. Zhou. Isolation-Based Anomaly Detection[M]. ACM, 2012, 6 (1) :1-39
**iForest局部異常 Aryal S, Kai M T, Wells J R, et al. Improving iForest with Relative Mass[C]// Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Cham, 2014:510-521.
**SCiForest F. T. Liu, M. T. Kai, Z. H. Zhou. Isolation-Based Anomaly Detection[M]. ACM, 2012, 6 (1) :1-39
RRCF G. Roy, G. Roy, G. Roy, et al. Robust random cut forest based anomaly detection on streams[C]. International Conference on International Conference on Machine Learning. JMLR.org, 2016:2712-2721
AutoEncoder S. S. Khan, B. Taati. Detecting unseen falls from wearable devices using channel-wise ensemble of autoencoders[J]. Expert Systems with Applications. 2017, 87:280-290
One-class SVM W. Khreich, B. Khosravifar, A. Hamou-Lhadj, et al. An anomaly detection system based on variable N-gram features and one-class SVM[J]. Information and Software Technology, 2017, 91:186-197
SVDD D.M.J Tax, R.P.W. Duin. Support vector domain description. Pattern Recognition Letters[J]. 1999, vol.20:1191-1199
SVM Wang G P, Yang J X, Li R. Imbalanced SVM‐Based Anomaly Detection Algorithm forImbalanced Training Datasets[J]. Etri Journal, 2017, 39(5):621-631.
**隨機森林 Liu D, Zhao Y, Xu H, et al. Opprentice:Towards Practical and Automatic Anomaly Detection Through Machine Learning[C]// Internet Measurement Conference. ACM, 2015:211-224.
PCA Xu W, Huang L, Fox A, et al. Detecting large-scale system problems by mining console logs[C]// ACM Sigops, Symposium on Operating Systems Principles. ACM, 2009:117-132.
**系統(tǒng)日志 He S, Zhu J, He P, et al. Experience Report: System Log Analysis for Anomaly Detection[C]// IEEE, International Symposium on Software Reliability Engineering. IEEE, 2016:207-218.**
**LSTM無監(jiān)督 Du M, Li F, Zheng G, et al. DeepLog: Anomaly Detection and Diagnosis from System Logs through Deep Learning[C]// ACM Sigsac Conference on Computer and Communications Security. ACM, 2017:1285-1298.
**深度信念網(wǎng)絡(luò)+one-class SVM Erfani S M, Rajasegarar S, Karunasekera S, et al. High-dimensional and large-scale anomaly detection using a linear one-class SVM with deep learning[J]. Pattern Recognition, 2016, 58(C):121-134.
**無監(jiān)督異常檢測方法測評 Goldstein M, Uchida S. A Comparative Evaluation of Unsupervised Anomaly Detection Algorithms for Multivariate Data[J]. Plos One, 2016, 11(4):e0152173.
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容