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

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

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

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

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

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

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

3.1 無(wú)監(jiān)督方法

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

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

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

3.1.2 基于距離（KNN）

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

3.1.3 基于密度（KNN）

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

3.1.4 基于聚類

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

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

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

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

3.1.5 基于樹

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

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

3.2 半監(jiān)督方法

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

3.3 有監(jiān)督方法

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

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

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

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

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

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

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

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

五、參考文獻(xiàn)