劉文芬，穆曉東 ，黃月華，2

1.桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004

2.桂林航天工業(yè)學院 計算機科學與工程學院，廣西 桂林 541004

1 引言

異常檢測是一種重要的數據挖掘手段，它的目標在于發(fā)掘與大部分對象不同的對象，而這個異常的對象被稱之為離群點或異常點。異常檢測技術在欺詐檢測、入侵檢測、公共衛(wèi)生、工業(yè)異常檢測等領域有著重要的應用價值。早在1980 年，霍金斯就對離群點下了準確的定義，即：“離群點是一個觀測值，它同其他觀測值的差別如此之大，以至于懷疑它是由不同機制產生的[1]”。由該定義可知，離群點更深層次的意義在于其產生機制不同。

針對異常產生本質的不同理解，異常檢測的方法大致可以分為基于統計、基于距離、基于密度、基于聚類、基于機器學習等類型。網格劃分大多用于聚類，這類聚類算法首先將數據空間劃分成有限數量的單元，從而形成一種網格結構，然后再在這種網格結構上進行聚類。經典的基于網格的聚類算法有STING[2]、WaveCluster[3]、CLIQUE[4]。由于聚類在網格上進行，而不是數據點，這類算法最大的優(yōu)勢是速度快。但是基于網格劃分的算法需要解決兩個問題，一個是網格的劃分尺度問題，另一個是高維度的適用性問題。網格劃分太密時，不僅計算量增大，而且每個網格內的點都幾乎相等，無法區(qū)分離群點和非離群點，網格劃分太稀疏時，同一個網格可能不光包含大量的非離群點，也包含離群點，無法達到良好的區(qū)分，在疏密交界處的網格這種現象尤為明顯。同時，隨著空間維度的增長，當維度較高時，即使是密度較大的區(qū)域，也會被(d-1)維的超平面分割而變得稀疏，導致算法無法區(qū)分疏密。

二分網格聚類的方法[5]從某種程度上克服了這兩個問題，該方法每次對一個維度進行二分，循環(huán)劃分，直到所有網格密度小于預先設置的密度閾值，再通過數據點從開始到停止劃分所需要的劃分次數來區(qū)分疏密（所需要的劃分次數越多，數據點所處區(qū)域越密集，反之越稀疏）最終達到聚類的目的。該算法解決了網格劃分尺度問題和高維度不適用的問題，但是該算法每次只劃分一個維度，維度之間的相關性考慮較少，且該算法中的密度閾值參數仍然需要提前設定。參數自適應的網格密度聚類算法[6]針對網格尺寸和密度閾值的選取問題，提出了從噪聲曲線中獲取最優(yōu)密度閾值的思路，可以自動設定密度閾值，但仍然需要人工從噪聲曲線中識別最佳閾值。針對高維度數據，基于網格劃分的算法一般在子空間上進行聚類。這類算法首先用傳統的特征選取算法確定相關維度，然后在對應的子空間上聚類，不同的簇可能對應不同的子空間，每個子空間維度也可能不同，因此時間效率較低，經典的算法有PROCLUS[7]等。

網格劃分技術應用于異常檢測時，常作為輔助工具出現，傳統的基于網格的異常檢測算法通常與其他算法結合使用。GDLOF[8]、OMAGT[9]、FOMAUC[10]、ODAVG[11]以及最近的NLOF[12]等算法，大多將網格技術作為數據篩選工具，或將密集區(qū)域去除，或將稀疏區(qū)域取出，以提高算法的時間效率，再結合LOF等傳統的異常檢測算法在剩余網格或者剩余數據點上提取異常點。這類算法有很好的時間效率，但是這些算法對于異常的衡量是一次性的，只考慮了一種網格尺度下的異常值，與基于網格的聚類算法一樣，它們無法回避網格尺度和密度閾值選取的問題，算法需要較為苛刻的選取密度閾值以適應不同的數據。為應對高維數據，與子空間聚類方法類似，子空間異常檢測算法[13]通過在低維投影中查詢異常區(qū)域來發(fā)現異常數據，這種方法可以很好地應對高維數據，但仍需要大量的算力來發(fā)現合適的子空間。RRGOD[14]結合粗糙集理論，通過一個屬性重要度閾值，淘汰部分維度，再在降維后的數據上進行自適應的網格劃分，淘汰高密度網格后用LOF 算法進行異常檢測，該方法可以在保證精度的同時，顯著降低LOF 的時間和空間復雜度，但仍需要人工設置屬性重要度閾值和密度閾值參數。

本文提出的方法將多分辨率的網格技術引入異常檢測，通過從稀疏到稠密的多分辨率的自適應網格劃分避免了網格尺度參數的引入，同時提出一種局部異常值的計算方式，綜合衡量了不同分辨率網格下，數據點的異常程度，并將所有尺度下數據點的局部異常值之和作為該點的全局異常值，在保證檢測精度的前提下避免了網格尺度劃分參數和密度閾值參數的引入。為了能夠適應高維度數據，本文引入了一個子空間劃分參數，將高維度切割成多個低維數據集處理，多分辨率網格劃分在低維的子空間上進行。這樣的子空間劃分策略，既可以保證多分辨網格劃分的高維度適用性，也避免了子空間查詢花費大量的算力，使算法在較低的時間復雜度下完成異常檢測。

2 算法介紹

2.1 傳統網格劃分方法

設A=D1×D2×…×Dm是一個m維的數據空間，算法的輸入是n個m維的數據點，設為vi=(vi,1,vi,2,…,vi,j,…,vi,m)，i=1,2,…,n，vi,j∈Dj，j=1,2,…,m。傳統的網格劃分算法需要輸入一個網格尺度劃分參數ε，將空間A每一維劃分成相同的ε個區(qū)間，從而將整個空間分成εm個互不相交的矩形單元格，矩形單元格可以描述為u1×u2×…×um，其中uj=[lj,hj)，j=1,2,…,m，均為一個前閉后開的區(qū)間。一個數據點vi=(vi,1,vi,2,…,vi,j,…,vi,m)落入一個單元格u1×u2×…×um中，當且僅當lj≤vi,j＜hj成立，其中j=1,2,…,m。

這樣的網格劃分策略有以下兩點不足：（1）整個空間分成εm個互不相交的矩形單元格，當數據維度高時，m偏大，網格單元數呈指數增長，導致時間效率降低；（2）參數ε需要人工選取，該參數魯棒性差，太大或太小都會導致檢測性能下降。

針對傳統網格劃分策略存在的不足，本文提出了基于多分辨率網格劃分的異常檢測方法，主要包含三個步驟：（1）子空間劃分；（2）對每個子空間進行多分辨率網格劃分；（3）計算每個數據點的全局異常值并輸出異常值排序。

2.2 子空間劃分方法

為了解決異常檢測中數據的高維度問題，通常有兩種解決方法，降維或劃分子空間。降維技術將原始數據集的高維空間映射至低維空間，再在低維空間中使用傳統算法進行異常檢測，以保證異常檢測算法的效率[15-16]。子空間技術將原始數據集劃分成多個低維的子空間，每個子空間包含一個或多個維度，再在子空間上進行異常檢測?；谧涌臻g的異常點挖掘最重要的是選擇包含異常點的子空間，然而在一個m維的數據集里，新維度的組合有2m種可能，子空間的個數隨數據維度增加呈指數增長，這就需要有效的算法來尋找合適的子空間，典型的算法有Aggarwal 使用遺傳算法尋找最優(yōu)子空間[17]，最近的算法有Gao Zhipeng的SRS[18]等。

為了保證算法的時間效率，以及對高維數據的適用性，本文引入了一個子矩陣劃分參數d，一般d取值在10以內。將n×m大小的原始數據矩陣，劃分成多個n×d大小的子矩陣，其中d≤m，最后一個子矩陣不足d的取余，即最后一個子矩陣大小為n×d'，d'=mmodd，其余子矩陣大小為n×d。為表示方便，子矩陣的兩種大小統一表示為n×d。

經過子矩陣劃分的數據集，保留了原始數據的所有維度，不需要額外的算力來確定子空間的大小，高效地保證了該算法對高維數據的適用性。

2.3 多分辨率網格劃分

為了解決網格劃分參數和密度閾值需要人工選取的問題，本文提出的算法引入多分辨率網格劃分自動適應數據。STING 聚類算法是經典的多分辨率網格聚類算法，它將空間區(qū)域根據不同的分辨率，劃分成多個級別的網格單元，這些單元形成一個層次結構：高層的每個單元被劃分為多個低一層的單元，遞歸劃分，直到形成多個層次的網格結構。通過預先計算和存儲每個網格單元的統計信息，包括總數、均值、最大值、最小值等，來預處理數據，然后依據這些信息自下向上的通過一個閾值來確定相關網格，最終達到聚類的目的。

如圖1所示，多分辨率網格劃分技術是一種空間劃分技術，它將空間區(qū)域（以二維為例）分層遞歸的進行劃分，形成多層矩形單元，每層矩形單元對應不同的分辨率，并構成了一個層次結構，每個高層網格在下一層被劃分成4 個網格（2d個，d為維度），依次遞歸，直到達成某種終止條件才停止劃分。此時的多分辨層次網格，從上到下，是一系列從稀疏到密集的網格單元，每層網格都對數據進行了一次劃分，因此，數據被多個分辨率的網格單元劃分。統計數據點在多種分辨率情況下的局部密度，即可在不需要設定網格參數的前提下得到數據點更為精確的全局密度。

圖1 多分辨率網格劃分過程

多分辨率網格的優(yōu)勢在于高層次網格劃分所帶來的誤差，可以由低層次網格繼續(xù)劃分進行彌補，直到劃分得足夠細致。本文算法將多分辨率網格劃分引入異常檢測，以網格數近似等于數據點個數為終止條件，實現了網格的自適應劃分。具體過程如下：

原始數據集大小記為n×m，被劃分后的子矩陣大小為n×d，即n行d列的矩陣。首先對子矩陣所有維度進行二分，形成2d個網格，記為第一層，i=1。再在這2d個網格的基礎上對所有維度進行二分，形成22×d個網格，記為第二層，i=2。依次遞歸，則第i次劃分后的網格個數為2i×d個。為保證網格個數不超過數據點個數，令：

求得：

圖2 網格劃分過程

2.4 計算全局異常值

在進行網格劃分后，需要計算每個數據點的異常值以確定最終的異常值排序。通常的方法是以單元格內數據點的個數近似表示數據的局部密度，將局部密度的倒數直接作為局部異常值，沒有進行標準化處理，容易受數據量n的影響。CLIQUE算法用單元格中的點數除以總的點數作為局部密度，解決了這一問題。但CLIQUE算法只劃分一次網格，局部異常值的計算方法不能直接用于多分辨率網格劃分算法。為了適應多分辨率網格劃分算法，本文提出的算法重新定義了局部密度，具體過程如下：

子矩陣編號記為k，子矩陣大小記為n×d，網格劃分次數記為i（即第i層），某個網格的在某一層中的編號記為j。子矩陣k的第i層第j個網格內數據點的個數記為ck,i,j。本文提出的算法定義網格的局部密度為：

該公式用每個網格內的相對數據點個數，近似表示了該網格內數據點的密度。由于網格內數據點越少，表明該網格內數據點越稀疏，越有可能是異常點，所以數據點密度與異常值成反比，本文算法定義數據點p的局部異常值為：

任意數據點p的全局異常值是它在所有子矩陣內劃分的每一層下所處網格的局部異常值之和，即：

接下來以500 個2 維數據點來解釋這一過程，由于維度較低，直接令m=d=2，此時只有一個子矩陣，即數據集本身，因此k=1。

如圖3 所示，只取典型的第二次和第三次劃分為例。由第二次劃分（即i=2）可知，數據集被均勻地分成16 個網格，在這16 個網格中，中間紅色方框內的4個網格內數據點個數明顯多于周圍的8 個網格（例如6號網格的數據點個數明顯大于2 號網格）。根據局部異常值的定義可知，網格內數據點越多，局部異常值越小，因此周圍網格內數據點的局部異常值就會明顯高于中間4 個網格的局部異常值。這樣該算法就在16 網格的分辨率尺度上實現了一次異常檢測。然而這樣的檢測比較粗略，以6 號網格為例，該網格左上角的數據密度明顯小于右下角，但由于在同一網格內，因此并沒有得到很好的區(qū)分。又因為i ＜I，I=5，不滿足多分辨率網格劃分的終止條件，所以網格還會進一步劃分，這個問題會在64 網格的分辨率尺度（第三次劃分）上得到解決。

圖3 異常值計算過程

如圖3所示，i=3 時數據被均勻地劃分在64個網格內，此時上一次沒有得到精確劃分的6號網格被劃分為4 個區(qū)域，分別是19，20，27，28 號網格。在64 網格的分辨率尺度下，計算這4 個網格的局部異常值，根據局部異常值的定義可知19 號網格的數據點少于其他3 個網格，因此19 號網格的局部異常值會大于其他3 個網格。這樣該算法就在64網格的分辨率尺度上又實現一次異常檢測，與上一次的異常值疊加，就可以更細致地區(qū)分數據點的疏密區(qū)域（例如6號網格左上角的19號網格內數據點的異常值會大于6 號網格內的其他3 個網格，而小于紅色區(qū)域外的8個網格）。依次迭代，直至i=I，累加得到的全局異常值會綜合考慮多個分辨率的情況下的局部異常程度，可以很好地區(qū)分各個區(qū)域數據的疏密，以達到較高的異常檢測精度。

2.5 算法步驟和偽代碼

算法實現過程中用到的重要變量及符號定義如表1。

表1 變量及符號定義

2.5.1 算法步驟

輸入：所有數據點組成的矩陣X=[x1,x2,…,xn]T，每個數據點x都是m維數據，X為n×m大小的矩陣；子矩陣尺度劃分參數d，d≤m；異常點比例R%。

輸出：算法判定所有異常點的編號。

步驟1子矩陣劃分。將輸入數據矩陣X劃分成n×d大小的 ■nd■ 個子矩陣。

步驟2取一個子矩陣進行多分辨率網格劃分。

步驟3按照公式（4）計算每個數據點的局部異常值，累加到該點的全局異常值。

步驟4判斷是否所有子矩陣都已計算異常值，若全部計算完畢則繼續(xù)下一步，若沒有則轉至步驟2執(zhí)行。

步驟5對所有數據點按照全局異常值大小進行降序排列，并輸出前R%的編號組成的異常數據集。

2.5.2 算法偽代碼

算法本文算法

輸入：原始數據集X，子矩陣尺度劃分參數d，異常點比例R%。

2.6 算法時間復雜度

對于n×m大小的數據集，算法需要劃分成■m d■個子矩陣。記每個子矩陣大小為n×d，d≤m，每個子矩陣進行次網格劃分。每次網格劃分遍歷一次數據集（n個數據）。所以該算法的時間復雜度為：

3 實驗

實驗基于Python3.7、VSCode 平臺，計算機硬件配置為：Windows10操作系統、Intel Core i5-3230M CPU、2.6 GHz、4 GB RAM。

3.1 人造數據集上有效性驗證

實驗首先用人造數據集來驗證算法的有效性，為了方便觀察，本文用sklearn 庫的datasets 工具創(chuàng)建了四組二維數據集（dataset 1，dataset 2，dataset 3，dataset 4）。四組數據集都是由1 700 個正常點和300 個異常點組成。dataset 1數據集的正常點部分是方差為0.5的二維高斯分布，dataset 2數據集的正常點部分是兩個方差分別為1.5和0.3的高斯分布，dataset 3數據集的正常點部分是一對月牙形分布，dataset 4數據集的正常點部分是一對環(huán)形分布。實驗結果如圖4，橘色為算法輸出的正常值，藍色為算法輸出的異常值。由圖可知，算法可以很好地區(qū)分稠密與稀疏區(qū)域，并且可以對非凸數據集進行檢驗，從而達到了預期效果，驗證了算法的有效性。

3.2 公開數據集上有效性驗證

本文選用8個公開數據集驗證算法的適用性，它們均來自ODDS網站，具體數據集信息如表2。

表2 數據集信息表

新算法在8 個公開數據集上實驗的ROC[25]曲線如圖5。

圖5 新算法在不同數據集上的ROC曲線

由圖5可知，算法在一些數據集上可以保證較高的真正率和較低的假正率，具有較好的異常檢測效果，有一定的應用價值。

為了定量地分析算法的性能，本文對比分析了三種常用的異常檢測算法，基于網格的Isolation Forest[26]算法、基于統計的Robust Covariance[27]算法和基于密度的LOF[28]算法，分別記為IF、RC、LOF，本文算法記為NA。其中IF 算法是最常用的基于網格劃分的異常檢測算法，RC 是經典的基于統計的算法且不需要預設參數，LOF 是經典的基于密度的異常檢測算法。與經典的網格劃分算法IF比較的目的是為了考察本文所設計算法和同類算法的性能對比，與三種不同類型的經典算法對比，是為了進一步考察算法的性能和算法的普適性。

各算法參數設置如表3。

表3 參數設置信息

主要性能指標為AUC 值（ROC 曲線所圍的面積）、檢測率TPR、誤報率FPR和運行時間T（單位：s）。對于二分類問題，可以將真實類別和算法檢測的類別組合劃分為四種情況，如表4所示。

表4 混淆矩陣

FP是標記為正常但被檢測為異常的點（False Positive），TN是標記為正常也被檢測為正常的點（True Negative），FN是標記為異常但被檢測為正常的點（False Negative），TP是標記為異常也被檢測為異常的點（True Positive）。

檢測率和誤報率分別定義為：

從上述計算公式可以看出，檢測率代表的是被正確檢測出的異常點占所有真實異常點的比例，誤報率代表的是被錯誤檢測的正常點占所有真實正常點的比例。一個性能較優(yōu)的異常檢測算法有較高的AUC值和TPR，較低的FPR。由于異常檢測數據集是典型的不平衡數據集，單純的準確率不能很好地描述算法的性能，利用檢測率和誤報率兩個指標來衡量，可以解決異常檢測算法在不平衡數據上的度量問題，在不同異常檢測算法對比時，可以有效地衡量算法的性能。

實驗結果如表5。

表5 不同算法實驗結果對比

由對比實驗表5可以看出，本文提出的異常檢測算法在Mammography、Shuttle、Wbc 三個數據集上具有比其他三種常用算法更好的檢測效果，該算法在這三個數據集上有更高的AUC值和TPR，更低的FPR。該算法在其他五個數據集雖然檢測效果不是最好的，但與最高值十分接近，例如數據集Wine，效果最好的LOF算法AUC 值為 0.999，而該算法 AUC 值為 0.989。上述實驗還表明該算法可以有效地應對高維度的數據集，例如在166維的Musk數據集上，該算法表現良好。

由運行時間的對比實驗可以看出，該算法在時間效率優(yōu)于基于統計的Robust Covariance 算法。在高維度或大數據量的情況下（例如Mammography、Shuttle、Musk三個數據集）時間效率略優(yōu)于LOF算法，低于Isolation Forest。在低維度小數據集上，時間效率略優(yōu)于Isolation Forest，低于LOF算法。整體上，本文提出的算法在兩個數據集上（Mammography、Vowels）時間效率優(yōu)于其他三種傳統算法，在其他六個數據集上僅次于一種算法，與對比算法相比，有一定的優(yōu)勢。

該算法需要預先設置子矩陣劃分參數d，為了驗證不同的子矩陣劃分參數d對算法性能的影響，本文對比了不同d取值下，該算法在各數據集上AUC值的變化，實驗結果如圖6。

由圖6 實驗結果可知，即使d取值不同，該算法在多個數據集上AUC值依舊可以穩(wěn)定保持在較高水平，說明d參數的選取對最終實驗結果影響有限，該參數魯棒性較好。

4 結語

圖6 算法在各數據集上不同d 取值時的AUC 值

為了避免傳統的基于網格的異常檢測算法網格劃分尺度和密度閾值兩個參數的選取，本文將多分辨率網格的概念引入異常檢測，并相應地提出了一種局部異常值的計算方法，衡量了數據點在不同分辨率網格下的局部異常值，在較低的時間復雜度下，既保證了檢測的精度，又避免了兩個參數的引入。為了能夠適應高維度數據，本文引入了一個數據尺度劃分參數，將高維數據切割成多個低維數據集處理，實驗表明，該參數具有良好的魯棒性。為驗證算法的檢測效果，本文通過人造數據集上的實驗證明了該算法的有效性，實驗結果還表明該算法可以有效地檢驗多種形狀的數據。多個公開數據集上的對比實驗表明該算法具有良好的檢測性能，能在多個應用場景下接近或超過現有的常用異常檢測算法，有一定的適應性和應用價值。