異常檢測(cè)算法綜述

王鑫，張濤，金映谷

（大連民族大學(xué)機(jī)電工程學(xué)院，大連116605）

0 引言

異常檢測(cè)[1-2]就是檢測(cè)數(shù)據(jù)中不符合行為的異常數(shù)據(jù)，根據(jù)研究應(yīng)用的領(lǐng)域不同，異常數(shù)據(jù)可以稱(chēng)之為離群點(diǎn)、污點(diǎn)、不一致點(diǎn)。近年來(lái)，異常檢測(cè)在很多領(lǐng)域都得到應(yīng)用，如：網(wǎng)絡(luò)入侵檢測(cè)、故障診斷、疾病檢測(cè)、身份識(shí)別、欺詐檢測(cè)，等等。異常檢測(cè)問(wèn)題可以大致總結(jié)為兩類(lèi)[3]：一是對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行異常檢測(cè)。對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行異常檢測(cè)的核心思想就是找到與正常數(shù)據(jù)差異大的點(diǎn)，通常把這個(gè)點(diǎn)稱(chēng)為離群點(diǎn)，但對(duì)結(jié)構(gòu)化數(shù)據(jù)進(jìn)行異常檢測(cè)通常面臨的問(wèn)題就是如何定義邊界來(lái)區(qū)分正常點(diǎn)和異常點(diǎn)；二是對(duì)非結(jié)構(gòu)化數(shù)據(jù)的異常檢測(cè)。常見(jiàn)的圖像識(shí)別，通過(guò)對(duì)圖像的檢測(cè)，識(shí)別出異常點(diǎn)。但是，對(duì)于異常的定義沒(méi)有標(biāo)準(zhǔn)答案，通常根據(jù)具體情況而異。根據(jù)現(xiàn)有研究階段得到的成果，采用異常檢測(cè)通常有兩個(gè)標(biāo)準(zhǔn)[4]：

（1）異常數(shù)據(jù)跟樣本中大多數(shù)數(shù)據(jù)不一樣，存在差異性大。

（2）異常數(shù)據(jù)在總體數(shù)據(jù)樣本中所占的比例小。

1 異常檢測(cè)類(lèi)別以及原理

由于訓(xùn)練的數(shù)據(jù)集存在不同，根據(jù)訓(xùn)練集的不同，異常檢測(cè)大致分為三類(lèi)：

（1）全監(jiān)督異常檢測(cè)（Supervised Anomaly Detec?tion）[5]

全監(jiān)督異常檢測(cè)就是訓(xùn)練的數(shù)據(jù)集都被標(biāo)簽化，分別標(biāo)記成正常和異常。全監(jiān)督檢測(cè)算法根據(jù)訓(xùn)練集中的標(biāo)簽進(jìn)行訓(xùn)練，得到網(wǎng)絡(luò)模型，在測(cè)試階段，通過(guò)對(duì)網(wǎng)絡(luò)模型輸入未知類(lèi)別的樣本測(cè)試，得到輸出結(jié)果。在現(xiàn)實(shí)的實(shí)踐中，由于標(biāo)記樣本是個(gè)復(fù)雜的過(guò)程，因此，全監(jiān)督異常檢測(cè)的應(yīng)用范圍很窄。

（2）半監(jiān)督異常檢測(cè)（Semi-Supervised Anomaly De?tection）[6]

半監(jiān)督異常檢測(cè)只是對(duì)數(shù)據(jù)集中正常的樣本進(jìn)行標(biāo)簽化，然后通過(guò)訓(xùn)練被標(biāo)簽化的正常樣本，得到“正?！蹦Ｐ停瑢?shù)據(jù)樣本與“正?！蹦Ｐ偷钠疃x為異常度，如果當(dāng)異常度大于設(shè)定的閾值，最終的輸出結(jié)果將是異常，相反，如果異常度小于設(shè)定的閾值，輸出結(jié)果將是正常。半監(jiān)督異常檢測(cè)面臨著和全監(jiān)督異常檢測(cè)一樣的問(wèn)題，都需要標(biāo)簽化的樣本，因此在實(shí)際中應(yīng)用并不廣泛。

（3）無(wú)監(jiān)督異常檢測(cè)（Unsupervised Anomaly Detec?tion）[7]

無(wú)監(jiān)督異常檢測(cè)的數(shù)據(jù)集沒(méi)有任何的標(biāo)簽，無(wú)監(jiān)督異常檢測(cè)的數(shù)據(jù)集包含正常數(shù)據(jù)和異常數(shù)據(jù)，通常情況下，正常的數(shù)據(jù)要比異常數(shù)據(jù)多。無(wú)監(jiān)督異常檢測(cè)通過(guò)訓(xùn)練正常的數(shù)據(jù)集，得到網(wǎng)絡(luò)模型，并得到一個(gè)異常分類(lèi)分?jǐn)?shù)，當(dāng)將測(cè)試數(shù)據(jù)輸入到網(wǎng)絡(luò)模型中，也會(huì)得到一個(gè)分?jǐn)?shù)，通過(guò)比較，如果測(cè)試數(shù)據(jù)得到的分?jǐn)?shù)大于異常分類(lèi)分?jǐn)?shù)時(shí)，則測(cè)試數(shù)據(jù)的輸出結(jié)果為異常，反之則為正常。在實(shí)際生產(chǎn)中，通常正常的數(shù)據(jù)要遠(yuǎn)遠(yuǎn)大于異常數(shù)據(jù)，而且無(wú)監(jiān)督異常檢測(cè)不需要對(duì)數(shù)據(jù)集進(jìn)行標(biāo)簽化，所以無(wú)監(jiān)督異常檢測(cè)應(yīng)用最為廣泛。

2 異常檢測(cè)算法

異常檢測(cè)算法的基本思想是：用正常的數(shù)據(jù)去訓(xùn)練模型，得到閾值，然后再去判斷新的數(shù)據(jù)是否異常。常見(jiàn)的幾種異常檢測(cè)算法有：基于概率統(tǒng)計(jì)、基于聚類(lèi)、基于最近鄰等[8]。對(duì)基于異常檢測(cè)算法的比較，詳細(xì)信息如表1 所示，其中包含各種異常檢測(cè)算法中的的主流算法（模型）、優(yōu)缺點(diǎn)對(duì)比。

表1 基于異常檢測(cè)算法的比較

2.1 基于概率統(tǒng)計(jì)異常檢測(cè)算法

基于概率統(tǒng)計(jì)的異常檢測(cè)算法[9]通過(guò)分為兩步，第一步假設(shè)數(shù)據(jù)服從一定的分布，如正態(tài)分布、泊松分布；第二步是計(jì)算每個(gè)點(diǎn)屬于這個(gè)分布的概率，最后得出該點(diǎn)是否異常。

一般情況下根據(jù)估計(jì)參數(shù)的方法來(lái)確定分布模型，利用數(shù)據(jù)集的數(shù)據(jù)去估計(jì)，得到一個(gè)估計(jì)的模型。通常在一元正態(tài)分布異常檢測(cè)時(shí)，常常利用3 原則，當(dāng)數(shù)據(jù)不在3 標(biāo)準(zhǔn)內(nèi)，則視為異常。多元正態(tài)分布中，用到基于協(xié)方差矩陣的Mahalanobis 距離。基于概率統(tǒng)計(jì)的異常檢測(cè)算法對(duì)于模型的選擇十分關(guān)鍵，選擇了錯(cuò)誤的模型，檢測(cè)對(duì)象就很可能被錯(cuò)誤地判為異常點(diǎn)。李際磊[10]對(duì)于現(xiàn)有的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的檢測(cè)技術(shù)進(jìn)行分析，指出現(xiàn)有技術(shù)的不足并提出基于概率統(tǒng)計(jì)的網(wǎng)絡(luò)異常檢測(cè)方法。該方法通過(guò)統(tǒng)計(jì)IP、端口、時(shí)間、周期等因子來(lái)判斷網(wǎng)絡(luò)行為是否異常，通過(guò)對(duì)算法的不斷優(yōu)化與實(shí)驗(yàn)，該方法對(duì)DDoS 攻擊、木馬盜竊等網(wǎng)絡(luò)異常行為有較高的檢測(cè)準(zhǔn)確率和速度。陳開(kāi)河等人[11]為解決地鐵出行存在的異常情況對(duì)地鐵系統(tǒng)帶來(lái)的不利影響，提出基于概率統(tǒng)計(jì)的地鐵出行異常的集成檢測(cè)方法，該方法包含三個(gè)方面相關(guān)聯(lián)的檢測(cè)算法：出行時(shí)間、出行時(shí)間差、出行時(shí)間比值。經(jīng)過(guò)實(shí)驗(yàn)，該方法有效可行，而且與其相關(guān)聯(lián)的三個(gè)算法形成互補(bǔ)，極大地提高檢測(cè)率。衛(wèi)薇等人[12]針對(duì)電力IT 監(jiān)控對(duì)象特征數(shù)據(jù)，提出基于統(tǒng)計(jì)模型的電力IT 監(jiān)控對(duì)象特征數(shù)的異常檢測(cè)方法，經(jīng)過(guò)試驗(yàn)表明，該方法解決了傳統(tǒng)電力IT 監(jiān)控軟件存在的缺點(diǎn)，其在異常檢測(cè)的準(zhǔn)確率、召回率上有明顯的提升。曹晨曦等人[13]提出一種基于統(tǒng)計(jì)的時(shí)間序列數(shù)據(jù)的異常點(diǎn)檢測(cè)方法，該方法能有效的檢測(cè)出異常點(diǎn)出現(xiàn)的位置，從而避免異常點(diǎn)對(duì)時(shí)間序列數(shù)據(jù)帶來(lái)的負(fù)面影響。通過(guò)用數(shù)據(jù)進(jìn)行實(shí)驗(yàn)表明，預(yù)測(cè)精度會(huì)提高3.4%-4.4%。

2.2 基于最近鄰異常檢測(cè)算法

基于最近鄰的異常檢測(cè)算法[14]通常根據(jù)近鄰度分為全局近鄰和局部近鄰，在全局近鄰異常檢測(cè)算法中常見(jiàn)的是基于距離的異常檢測(cè)算法[15]；局部近鄰異常檢測(cè)算法中常見(jiàn)是基于密度的異常檢測(cè)算法[16]。

“農(nóng)三代”是吳躦輝身上一個(gè)閃亮的標(biāo)簽，2009年他畢業(yè)于浙江農(nóng)林大學(xué)，剛一畢業(yè)就進(jìn)入了浙江愛(ài)普農(nóng)業(yè)科技發(fā)展有限公司工作，到今年已經(jīng)整整十個(gè)年頭了。說(shuō)起選擇農(nóng)資行業(yè)的原因，吳躦輝說(shuō)走進(jìn)農(nóng)資這個(gè)行業(yè)并不是他偶然的一個(gè)行為，而是經(jīng)過(guò)深思熟慮后所做下的決定。

（1）基于距離異常檢測(cè)算法

基于距離的異常檢測(cè)算法主要應(yīng)用于全局近鄰，常用的算法是KNN 算法[17]，KNN 算法主要思想是異常點(diǎn)距離正常點(diǎn)的距離比較遠(yuǎn)。KNN 算法其原理對(duì)于每個(gè)數(shù)據(jù)點(diǎn)，通過(guò)找到k 個(gè)最近的鄰居，然后根據(jù)k 個(gè)最近的鄰居計(jì)算異常分?jǐn)?shù)，計(jì)算異常分?jǐn)?shù)的方法主要有兩種：1 是使用第k 個(gè)最近的距離（簡(jiǎn)稱(chēng)K-近鄰距）離；2 是計(jì)算所有的k 個(gè)距離，然后求出平均距離（簡(jiǎn)稱(chēng)平均距離）。通常在實(shí)際中方法2 的應(yīng)用程度比較高。

曾存等人[18]為了能提高柴油機(jī)異常情況的檢測(cè)速度，提出基于空間幾何法和距離法的柴油機(jī)異常熱工參數(shù)檢測(cè)方法。通過(guò)對(duì)熱工參數(shù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了兩種方法的可行性，同時(shí)也能快速準(zhǔn)確的確定異常樣本數(shù)據(jù)。霍文君等人[19]通過(guò)總結(jié)已有異常檢測(cè)算法存在低準(zhǔn)確率問(wèn)題，在現(xiàn)有的時(shí)間序列異常檢測(cè)算法中，結(jié)合優(yōu)點(diǎn)，彌補(bǔ)不足，提出一種新的基于歐氏距離的在線異常檢測(cè)算法。該算法通過(guò)對(duì)運(yùn)維時(shí)的時(shí)間序列進(jìn)行實(shí)驗(yàn)，最終結(jié)果表明該算法能快速準(zhǔn)確地檢測(cè)出異常數(shù)據(jù)。陳嘉偉等人[20]在手勢(shì)識(shí)別方面，通過(guò)解決傳統(tǒng)的k 最近鄰算法的缺點(diǎn)，提出一種基于改進(jìn)KNN 算法應(yīng)用于動(dòng)態(tài)手勢(shì)識(shí)別。該算法通過(guò)記錄手勢(shì)信號(hào)的特征量作為訓(xùn)練和測(cè)試，并及時(shí)存儲(chǔ)。通過(guò)實(shí)驗(yàn)結(jié)果表面，改進(jìn)的KNN 算法相較于原始的KNN 算法在成果率方面提升10&左右。

（2）基于密度異常檢測(cè)算法

對(duì)于數(shù)據(jù)集存在分布不均勻，有稠密的地方，有疏松的地方，這就造成分割的閾值難以確定，為解決這一問(wèn)題，提出基于密度的異常檢測(cè)算法?；诿芏鹊漠惓z測(cè)算法是根據(jù)樣本點(diǎn)的局部密度信息去判斷是否異常，常見(jiàn)的基于密度的異常檢測(cè)算法有：LOF、IN?FLO、LoOP 等。

LOF 算法[21]其基本原理是對(duì)數(shù)據(jù)點(diǎn)進(jìn)行計(jì)算，找出其k 個(gè)近鄰，然后計(jì)算LOF 得分，得分越高則異常的可能性越大。LOF 是一個(gè)比值，其分子是k 個(gè)近鄰的平均局部可達(dá)密度，分母則是該數(shù)據(jù)點(diǎn)局部可達(dá)密度?？蛇_(dá)密度則是k-近鄰個(gè)數(shù)與k-近鄰可達(dá)距離的比值。高澤雄[22]提出基于LOF 算法的規(guī)律異常車(chē)輛檢測(cè)，首先對(duì)卡口過(guò)車(chē)的軌跡數(shù)據(jù)進(jìn)行特征提取，然后利用LOF 算法對(duì)車(chē)輛的規(guī)律進(jìn)行異常檢測(cè)，從而發(fā)現(xiàn)規(guī)律異常車(chē)輛。該方法的提出，為大范圍異常車(chē)輛檢測(cè)，社會(huì)穩(wěn)定提供幫助。應(yīng)裴昊等人[23]為解決電力數(shù)據(jù)網(wǎng)對(duì)業(yè)務(wù)流量進(jìn)行異常檢測(cè)的需求，提出基于LOF 的電力數(shù)據(jù)網(wǎng)業(yè)務(wù)流量異常檢測(cè)方法。該方法通過(guò)對(duì)LOF算法進(jìn)行改進(jìn)，計(jì)算每個(gè)流量包與附近流量包的分隔程度，進(jìn)而推算出是否存在異常。該方法相對(duì)于傳統(tǒng)的方法具有更高的靈活性，進(jìn)過(guò)實(shí)驗(yàn)仿真，驗(yàn)證該方法的可行性，能有效地提高檢測(cè)效率，減少成本。

LoOP 算法[27]與其他算法存在不同，相對(duì)于基于全局的KNN 算法還是LOF 的算法，其輸出結(jié)果都是異常分?jǐn)?shù)，對(duì)于異常分?jǐn)?shù)作為輸出結(jié)果而言，通常缺少一個(gè)衡量的標(biāo)準(zhǔn)，即不知道輸出多少分會(huì)被判定為異常點(diǎn)，LoOP 算法通過(guò)輸出異常概率解決問(wèn)題。LoOP 算法計(jì)算局部密度的方法的基本原理通常會(huì)假設(shè)距離最近的鄰居服從高斯分布。距離總是以正數(shù)值存在，所以符合“半高斯”分布（均值的右邊）。使用“半高斯”分布的標(biāo)準(zhǔn)差（也稱(chēng)為概率集距離）。每個(gè)數(shù)據(jù)點(diǎn)會(huì)與其鄰居產(chǎn)生一個(gè)局部異常檢測(cè)分?jǐn)?shù)，最后應(yīng)用一個(gè)歸一化函數(shù)和一個(gè)高斯誤差函數(shù)，將異常檢測(cè)分?jǐn)?shù)轉(zhuǎn)換成一個(gè)概率的形勢(shì)輸。

2.3 基于聚類(lèi)異常檢測(cè)算法

基于聚類(lèi)的異常檢測(cè)算法[28]通常有三種假設(shè)，每個(gè)假設(shè)下面都有其常見(jiàn)的方法。

假設(shè)一：不屬于任何簇類(lèi)的點(diǎn)就是異常點(diǎn)，代表方法DBSCAN 算法[29]；DBSCAN 算法是一種典型的基于密度的聚類(lèi)算法，該算法通過(guò)將緊密相連的樣本劃為各個(gè)不同的類(lèi)別，最終得出聚類(lèi)類(lèi)別結(jié)果。阮嘉琨等人[30]分析了高速公路交通流數(shù)據(jù)具有的復(fù)雜性、多變性、波動(dòng)性等特點(diǎn)，采用傳統(tǒng)的異常數(shù)據(jù)檢測(cè)方法很能準(zhǔn)確的檢測(cè)出異常數(shù)據(jù)，于是提出基于DBSCAN 密度聚類(lèi)的高速公路交通流異常數(shù)據(jù)檢測(cè)算法。經(jīng)過(guò)實(shí)驗(yàn)表明，該檢測(cè)方法有很好的檢測(cè)效果，能夠滿足實(shí)際的路況檢測(cè)需求。

假設(shè)二：距離最近的聚類(lèi)結(jié)果較遠(yuǎn)的點(diǎn)為異常點(diǎn)，常見(jiàn)方法K-means 算法[31]。該算法首先對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)，然后通過(guò)計(jì)算樣本與所屬聚類(lèi)的兩個(gè)距離，一個(gè)是樣本與所屬聚類(lèi)中心的距離，一個(gè)是樣本與所屬聚類(lèi)的類(lèi)內(nèi)平均距離，通過(guò)兩個(gè)距離的比值衡量異常程度。李峰等人[32]為解決K-means 算法存在由于選擇中心值不當(dāng)而造成聚類(lèi)效果不好的問(wèn)題，提出一種局部迭代的快速K-means 聚類(lèi)算法。該算法降低聚類(lèi)更新的時(shí)間復(fù)雜度，提高聚類(lèi)效果，最終通過(guò)仿真實(shí)驗(yàn)與真實(shí)數(shù)據(jù)實(shí)驗(yàn)，驗(yàn)證了該算法在提高檢測(cè)準(zhǔn)確率的同時(shí)，其檢測(cè)時(shí)間也大幅度縮短。劉慕嫻等人[33]提出一種基于K-means 算法的網(wǎng)絡(luò)流量異常檢測(cè)模型，該方法先將網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行量化，將量化后的熵值進(jìn)行分類(lèi)，然后將K-means 聚類(lèi)算法運(yùn)用到異常檢測(cè)中，實(shí)現(xiàn)安全檢測(cè)預(yù)警。經(jīng)過(guò)試驗(yàn)，該方法提高了檢測(cè)準(zhǔn)確率，為異常流量檢測(cè)提供一種高效的手段。

假設(shè)三：疏松聚類(lèi)與較小的聚類(lèi)里的點(diǎn)都是異常點(diǎn)，主要方法CBLOF 算法[34]、LDCOF 算法[35]。該類(lèi)方法通過(guò)聚類(lèi)后將聚類(lèi)簇分成大簇和小簇，如果樣本數(shù)據(jù)屬于大簇，則利用該樣本和所屬大簇進(jìn)行計(jì)算異常得分；如果樣本數(shù)據(jù)屬于小簇，則利用該樣本距離最近的大簇計(jì)算異常得分。錢(qián)景輝等人[36]在CBLOF 算法基礎(chǔ)上進(jìn)行改進(jìn)，提出一種基于多示例學(xué)習(xí)的時(shí)序離群點(diǎn)檢測(cè)算法MIL-FindCBlof，該算法將數(shù)據(jù)進(jìn)行聚類(lèi)，然后采用全局策略計(jì)算因子數(shù)值，最后通過(guò)計(jì)算平均因子來(lái)確定離群點(diǎn)。經(jīng)過(guò)實(shí)驗(yàn)表明，該算法與經(jīng)典離群點(diǎn)檢測(cè)算法相比，在檢測(cè)的全面性和準(zhǔn)確性都有提高。

綜上所述，對(duì)異常檢測(cè)算法的研究應(yīng)用進(jìn)行總結(jié)，詳情如表2 所示。

3 結(jié)語(yǔ)

異常檢測(cè)算法在其相應(yīng)的領(lǐng)域內(nèi)得到廣泛的應(yīng)用，但是隨著研究的深度，可以發(fā)現(xiàn)幾種典型異常檢測(cè)算法的優(yōu)點(diǎn)與不足之處?；诟怕式y(tǒng)計(jì)異常檢測(cè)算法更適用于對(duì)低維數(shù)據(jù)進(jìn)行異常檢測(cè)，其具有很好的魯棒性，但是其對(duì)模型的依賴(lài)程度比較高，模型的選取十分關(guān)鍵；基于距離的異常檢測(cè)算法具有不需要假設(shè)數(shù)據(jù)分布的優(yōu)點(diǎn)，但是同時(shí)也存在不適用于高維數(shù)據(jù)，需要人工調(diào)參數(shù)，同時(shí)參數(shù)k 的選擇也是比較不易，僅僅適用于全局異常點(diǎn)，無(wú)法適用局部異常；基于密度的異常檢測(cè)算法適用于分布不均勻的數(shù)據(jù)，從中找出局部異常的數(shù)據(jù)，但同時(shí)由于需要遍歷數(shù)據(jù)計(jì)算距離，計(jì)算程度大，不適用于在線使用?；诰垲?lèi)的異常檢測(cè)算法通常檢測(cè)速度快，有的可以應(yīng)用到實(shí)時(shí)在線檢測(cè)，但是也存在一定的問(wèn)題，如檢測(cè)效果很大程度比較依賴(lài)聚類(lèi)效果，對(duì)于大數(shù)據(jù)而言，開(kāi)銷(xiāo)成本大。

目前，對(duì)異常檢測(cè)的研究不斷深入，衡量異常檢測(cè)系統(tǒng)的好壞主要指標(biāo)是檢測(cè)效率及檢測(cè)準(zhǔn)確率，對(duì)于異常檢測(cè)系統(tǒng)而言，異常檢測(cè)算法起著決定性的作用。穩(wěn)定好、速度快、適用性強(qiáng)的異常檢測(cè)算法將是今后研究的主要方向。

表2 基于異常檢測(cè)算法的研究應(yīng)用

本文首先主要對(duì)異常檢測(cè)進(jìn)行簡(jiǎn)短的概述，描述了異常檢測(cè)解決的兩類(lèi)問(wèn)題及應(yīng)用異常檢測(cè)的標(biāo)準(zhǔn)，然后從數(shù)據(jù)集的角度考慮，分析歸納了異常檢測(cè)的類(lèi)別，闡述了其工作原理，隨之對(duì)異常檢測(cè)算法進(jìn)行分類(lèi)整理，介紹幾種典型的異常檢測(cè)算法的原理并列舉其研究現(xiàn)狀，最后對(duì)典型異常檢測(cè)算法進(jìn)行總結(jié)，分析其優(yōu)缺點(diǎn)，并對(duì)異常檢測(cè)算法的發(fā)展趨勢(shì)進(jìn)行展望。