異常檢測算法綜述

王鑫，張濤，金映谷

（大連民族大學機電工程學院，大連116605）

0 引言

異常檢測[1-2]就是檢測數據中不符合行為的異常數據，根據研究應用的領域不同，異常數據可以稱之為離群點、污點、不一致點。近年來，異常檢測在很多領域都得到應用，如：網絡入侵檢測、故障診斷、疾病檢測、身份識別、欺詐檢測，等等。異常檢測問題可以大致總結為兩類[3]：一是對結構化數據進行異常檢測。對結構化數據進行異常檢測的核心思想就是找到與正常數據差異大的點，通常把這個點稱為離群點，但對結構化數據進行異常檢測通常面臨的問題就是如何定義邊界來區分正常點和異常點；二是對非結構化數據的異常檢測。常見的圖像識別，通過對圖像的檢測，識別出異常點。但是，對于異常的定義沒有標準答案，通常根據具體情況而異。根據現有研究階段得到的成果，采用異常檢測通常有兩個標準[4]：

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

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

1 異常檢測類別以及原理

由于訓練的數據集存在不同，根據訓練集的不同，異常檢測大致分為三類：

（1）全監督異常檢測（Supervised Anomaly Detec?tion）[5]

全監督異常檢測就是訓練的數據集都被標簽化，分別標記成正常和異常。全監督檢測算法根據訓練集中的標簽進行訓練，得到網絡模型，在測試階段，通過對網絡模型輸入未知類別的樣本測試，得到輸出結果。在現實的實踐中，由于標記樣本是個復雜的過程，因此，全監督異常檢測的應用范圍很窄。

（2）半監督異常檢測（Semi-Supervised Anomaly De?tection）[6]

半監督異常檢測只是對數據集中正常的樣本進行標簽化，然后通過訓練被標簽化的正常樣本，得到“正常”模型，將數據樣本與“正常”模型的偏差定義為異常度，如果當異常度大于設定的閾值，最終的輸出結果將是異常，相反，如果異常度小于設定的閾值，輸出結果將是正常。半監督異常檢測面臨著和全監督異常檢測一樣的問題，都需要標簽化的樣本，因此在實際中應用并不廣泛。

（3）無監督異常檢測（Unsupervised Anomaly Detec?tion）[7]

無監督異常檢測的數據集沒有任何的標簽，無監督異常檢測的數據集包含正常數據和異常數據，通常情況下，正常的數據要比異常數據多。無監督異常檢測通過訓練正常的數據集，得到網絡模型，并得到一個異常分類分數，當將測試數據輸入到網絡模型中，也會得到一個分數，通過比較，如果測試數據得到的分數大于異常分類分數時，則測試數據的輸出結果為異常，反之則為正常。在實際生產中，通常正常的數據要遠遠大于異常數據，而且無監督異常檢測不需要對數據集進行標簽化，所以無監督異常檢測應用最為廣泛。

2 異常檢測算法

異常檢測算法的基本思想是：用正常的數據去訓練模型，得到閾值，然后再去判斷新的數據是否異常。常見的幾種異常檢測算法有：基于概率統計、基于聚類、基于最近鄰等[8]。對基于異常檢測算法的比較，詳細信息如表1 所示，其中包含各種異常檢測算法中的的主流算法（模型）、優缺點對比。

表1 基于異常檢測算法的比較

2.1 基于概率統計異常檢測算法

基于概率統計的異常檢測算法[9]通過分為兩步，第一步假設數據服從一定的分布，如正態分布、泊松分布；第二步是計算每個點屬于這個分布的概率，最后得出該點是否異常。

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

2.2 基于最近鄰異常檢測算法

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

“農三代”是吳躦輝身上一個閃亮的標簽，2009年他畢業于浙江農林大學，剛一畢業就進入了浙江愛普農業科技發展有限公司工作，到今年已經整整十個年頭了。說起選擇農資行業的原因，吳躦輝說走進農資這個行業并不是他偶然的一個行為，而是經過深思熟慮后所做下的決定。

（1）基于距離異常檢測算法

基于距離的異常檢測算法主要應用于全局近鄰，常用的算法是KNN 算法[17]，KNN 算法主要思想是異常點距離正常點的距離比較遠。KNN 算法其原理對于每個數據點，通過找到k 個最近的鄰居，然后根據k 個最近的鄰居計算異常分數，計算異常分數的方法主要有兩種：1 是使用第k 個最近的距離（簡稱K-近鄰距）離；2 是計算所有的k 個距離，然后求出平均距離（簡稱平均距離）。通常在實際中方法2 的應用程度比較高。

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

（2）基于密度異常檢測算法

對于數據集存在分布不均勻，有稠密的地方，有疏松的地方，這就造成分割的閾值難以確定，為解決這一問題，提出基于密度的異常檢測算法。基于密度的異常檢測算法是根據樣本點的局部密度信息去判斷是否異常，常見的基于密度的異常檢測算法有：LOF、IN?FLO、LoOP 等。

LOF 算法[21]其基本原理是對數據點進行計算，找出其k 個近鄰，然后計算LOF 得分，得分越高則異常的可能性越大。LOF 是一個比值，其分子是k 個近鄰的平均局部可達密度，分母則是該數據點局部可達密度。可達密度則是k-近鄰個數與k-近鄰可達距離的比值。高澤雄[22]提出基于LOF 算法的規律異常車輛檢測，首先對卡口過車的軌跡數據進行特征提取，然后利用LOF 算法對車輛的規律進行異常檢測，從而發現規律異常車輛。該方法的提出，為大范圍異常車輛檢測，社會穩定提供幫助。應裴昊等人[23]為解決電力數據網對業務流量進行異常檢測的需求，提出基于LOF 的電力數據網業務流量異常檢測方法。該方法通過對LOF算法進行改進，計算每個流量包與附近流量包的分隔程度，進而推算出是否存在異常。該方法相對于傳統的方法具有更高的靈活性，進過實驗仿真，驗證該方法的可行性，能有效地提高檢測效率，減少成本。

LoOP 算法[27]與其他算法存在不同，相對于基于全局的KNN 算法還是LOF 的算法，其輸出結果都是異常分數，對于異常分數作為輸出結果而言，通常缺少一個衡量的標準，即不知道輸出多少分會被判定為異常點，LoOP 算法通過輸出異常概率解決問題。LoOP 算法計算局部密度的方法的基本原理通常會假設距離最近的鄰居服從高斯分布。距離總是以正數值存在，所以符合“半高斯”分布（均值的右邊）。使用“半高斯”分布的標準差（也稱為概率集距離）。每個數據點會與其鄰居產生一個局部異常檢測分數，最后應用一個歸一化函數和一個高斯誤差函數，將異常檢測分數轉換成一個概率的形勢輸。

2.3 基于聚類異常檢測算法

基于聚類的異常檢測算法[28]通常有三種假設，每個假設下面都有其常見的方法。

假設一：不屬于任何簇類的點就是異常點，代表方法DBSCAN 算法[29]；DBSCAN 算法是一種典型的基于密度的聚類算法，該算法通過將緊密相連的樣本劃為各個不同的類別，最終得出聚類類別結果。阮嘉琨等人[30]分析了高速公路交通流數據具有的復雜性、多變性、波動性等特點，采用傳統的異常數據檢測方法很能準確的檢測出異常數據，于是提出基于DBSCAN 密度聚類的高速公路交通流異常數據檢測算法。經過實驗表明，該檢測方法有很好的檢測效果，能夠滿足實際的路況檢測需求。

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

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

綜上所述，對異常檢測算法的研究應用進行總結，詳情如表2 所示。

3 結語

異常檢測算法在其相應的領域內得到廣泛的應用，但是隨著研究的深度，可以發現幾種典型異常檢測算法的優點與不足之處。基于概率統計異常檢測算法更適用于對低維數據進行異常檢測，其具有很好的魯棒性，但是其對模型的依賴程度比較高，模型的選取十分關鍵；基于距離的異常檢測算法具有不需要假設數據分布的優點，但是同時也存在不適用于高維數據，需要人工調參數，同時參數k 的選擇也是比較不易，僅僅適用于全局異常點，無法適用局部異常；基于密度的異常檢測算法適用于分布不均勻的數據，從中找出局部異常的數據，但同時由于需要遍歷數據計算距離，計算程度大，不適用于在線使用。基于聚類的異常檢測算法通常檢測速度快，有的可以應用到實時在線檢測，但是也存在一定的問題，如檢測效果很大程度比較依賴聚類效果，對于大數據而言，開銷成本大。

目前，對異常檢測的研究不斷深入，衡量異常檢測系統的好壞主要指標是檢測效率及檢測準確率，對于異常檢測系統而言，異常檢測算法起著決定性的作用。穩定好、速度快、適用性強的異常檢測算法將是今后研究的主要方向。

表2 基于異常檢測算法的研究應用

本文首先主要對異常檢測進行簡短的概述，描述了異常檢測解決的兩類問題及應用異常檢測的標準，然后從數據集的角度考慮，分析歸納了異常檢測的類別，闡述了其工作原理，隨之對異常檢測算法進行分類整理，介紹幾種典型的異常檢測算法的原理并列舉其研究現狀，最后對典型異常檢測算法進行總結，分析其優缺點，并對異常檢測算法的發展趨勢進行展望。