基于多粒度級聯孤立森林算法的異常檢測模型

楊曉暉，張圣昌

（河北大學網絡空間安全與計算機學院，河北 保定 071002）

1 引言

異常檢測的作用是分類出與多數數據有不同行為模式的稀有數據。Grubbs[1]對異常點有如下定義：異常點是一種模式，在此模式下的數據點偏離了大部分數據點的模式特征，甚至不是同一種機制產生的。本文將異常點定義為分布稀疏且距離密度較高的數據簇較遠的點。異常檢測在諸多領域中有廣泛應用，例如，在電子現金支付過程中，異常點代表著套現欺詐行為；在科學計算領域，異常數據和正常數據具有相等的利用價值[2]，如天文圖像檢測中的異常點可能意味著新星的出現；在網絡安全領域，異常點可能是惡意用戶的非法入侵。

近年來，基于密度評估的異常檢測方案深受關注[3]。基于密度評估的異常檢測方案將異常點定義如下：異常點是低密度區域的數據對象，密度的核心概念是近鄰距離。對密度概念的改進衍生出不同的算法，例如局部異常因子算法（LOF,local outlier factor）[4]、密度偏移抽樣算法[5]等。LOF 通過k近鄰距離計算局部可達密度，得到每個點的局部離群因子，根據閾值判斷點是否異常。LOF 的優勢是既可以計算局部異常點，也可以計算全局異常點，在小數據集中效果極佳。利用聚類進行異常檢測也是基于密度概念，此類算法利用數據點的分布規律對數據集進行分簇，按每個數據點到簇中心的距離排序，根據超參閾值比較，超過閾值的數據點稱為異常點。例如經典k-means 聚類算法檢測網絡流量異常[6]，利用遺傳算法對k-means 聚類改進解決了局部最優問題[7]；Tang 等[8-9]提出了基于特征選擇的模糊聚類異常檢測模型，利用層次聚類和遺傳算法改進了聚類模型，進一步降低了異常檢測的誤報率。

隨著大數據時代的到來，數據的量和維度發生了爆炸式增長。高維數據存在2 個問題：1)距離計算上的“維數災難”[10]，數據相似度的計算離不開距離計算，比如歐氏距離，隨著數據維度的增加，點與點間距離的區分度變小，數據分布稀疏，異常點不再敏感；2)時間復雜度過高，高維數據間的距離計算所需時間開銷過大，對實時檢測應用來說無法滿足需求，例如網絡入侵檢測和信用卡欺詐檢測都對低時間開銷有較高要求。基于密度評估的異常檢測方案時間復雜度均在O(n2)[11]，因此設計出對高維度、大數據集進行異常檢測的高效方法具有重要意義。

質量評估思想在數據分類、回歸異常檢測等領域有顯著效果，該思想重新定義數據點靠近數據簇中心或靠近數據簇邊緣的度量，并稱該度量為質量。相比于密度評估方法，基于質量評估的方法有以下2 個優勢[12]：1)數據質量的計算量小，數據質量計算只統計一個區域內的數據量，不需要計算距離；2)數據質量的大小反映了數據點是靠近還是遠離數據簇中心。

基于質量評估的異常檢測方案利用隔離機制來計算數據質量。根據隔離機制的不同，衍生出許多異常檢測算法，例如half-space tree[13]、SCiForest[14]、基于近鄰距離的隔離機制[15]等。

孤立森林（iForest，isolation forest）[16]屬于集成學習方法，是隨機森林算法的無監督版本，廣泛應用于異常檢測領域。iForest 對數據空間進行隨機隔離，以此構造決策樹樁（decision stump），也稱為孤立樹（iTree,isolation tree）。iForest 也符合質量評估思想，質量被定義為iTree 中葉節點的深度，深度越小，越有可能為異常點。

iForest 解決了高維數據集中異常檢測的2 個問題[17]：1)iForest 不需要計算距離，算法的時間開銷不隨數據維度的增加而增加，為線性時間復雜度；2)iForest 對大型數據集的檢測性能好，并且是集成學習算法，iTree 越多，iForest 越穩定。

雖然iForest 適用于高維數據集的異常檢測，但隨著數據分布復雜性的增加，檢測效率也會降低，而且在極高維數據的異常檢測中，算法的波動性較高。因此，本文提出基于多特征決策的隨機超平面隔離機制，以及基于滑動窗口的多粒度掃描機制，進而構造層次化集成學習模型。

2 iForest 方案

2.1 質量評估思想

定義1隔離超平面。假設數據集D在維數i上有序，當 且 僅 當且時，為數據點在維度i上的隔離超平面。

定義2基本質量函數。數據集D中每個點都有

定義3數據點質量函數。計算式如式(2)所示。

2.2 iForest 的構建

定義4 孤立樹。若Node 是孤立樹的節點，則是具有(NodeL,NodeR)子節點的內部節點，或是無子節點的終端節點。NodeL與 NodeR的定義為在特征集合中選擇i，該特征上值區間內隨機選擇數據j，小于j的數據劃分為左子樹NodeL，大于j的數據劃分為右子樹 NodeR。

iForest 由T個iTree 構成，如式(3)所示。

2.3 iForest 的問題

軸平行（axis-parallel）是指在單一特征的決策過程中，決策邊界與坐標軸平行的現象。軸平行是決策樹的一種特性，由于iForest 的決策模式類似于決策樹，因此也受軸平行特性的影響。

在密集的數據集中，受軸平行特性的影響，iForest會產生重疊和覆蓋效應，導致決策精度降低，同時會增加iTree 的高度和訓練過程的時間開銷，無法高效生成iTree，因此iForest 更適用于具有分布稀疏特性的數據集。文獻[16]提出類似于隨機森林中子采樣的方法解決了這個問題。設定ψ為隨機子采樣的樣本數量，iTree 由隨機子采樣的樣本集生成。

圖1(a)構造了3 個服從高斯分布的數據集。左上數據簇的數量為300，左下為500，右側為1 000。圖1(b)中的數據量為1 000，數據的分布模式符合余弦函數趨勢。黑白梯度線為異常分數的等高線，黑色表示1，白色表示0，異常分數越大，表示越有可能為異常點。如圖1(a)所示，異常分數梯度線在數據簇的平行軸線上偏差較大；圖1(b)失去了余弦函數趨勢，無法正確檢測異常點。

圖1 iForest 對不同數據集的異常分數

3 基于多粒度級聯孤立森林算法

為解決iForest 的不足，本文提出基于多維度隨機超平面的孤立森林（MRHiForest,multi-dimensional random hyperplane iForest）隔離機制，在數據集隔離的過程中，使用多元線性組合構成多樣化的隨機超平面。同時，利用多粒度掃描器（MGS，multi-grained scanner）進行高維數據的特征子采樣，類似隨機森林，但樣本的選取采用滑動窗口的方式，特征樣本存在連續性。每個特征樣本構造新的數據集訓練孤立森林，以此構造基于多粒度級聯孤立森林算法的異常檢測模型。

3.1 隨機超平面隔離

定義5隨機超平面。隨機超平面為iForest 的隔離機制產生的超平面，Su是所有隨機超平面的集合。p(x,y)表示為點x及點y被隨機超平面K隔離的概率，如式(4)所示。

iForest 中的隔離機制為式(4)的特例。iForest隨機選擇一個特征η，令

聯合式(4)和式(5)得到iForest 的隔離超平面為

iForest 僅就一個特征η進行隔離，丟失了大部分特征信息，因此隨著數據維數的增加，iForest 的性能不穩定。相比之下，隨機超平面的隔離機制包含所有特征信息。

在iForest 中，數據的隔離是隨機的，針對隨機超平面的隨機選擇容易出現偏離數據集現象，造成無效開銷。本文利用法向量隨機生成斜率向量。首先隨機選擇2 個點，然后求2 個點的法向量作為斜率向量，從而保證隨機超平面存在于數據集中。

圖2(a)是二維數據空間中一個iTree 的生成過程實例。選取平行于軸的超平面來隔離數據，數據質量高的數據點被隔離多次才會被劃分出去（如圖2(a)中的點n），而質量低的數據點經過少數的幾次隔離就會被劃分出去（如圖2(a)中的點a）。圖2(b)展示了MRHiForest 中隨機超平面的生成過程，圖中兩點是隨機選取的，兩點的法向量表示隨機超平面的方向，灰色區域為截距b的區間選取范圍。從圖2 中可以明顯看出，iForest 隔離超平面是平行于坐標軸的，MRHiForest 隔離超平面的方向是隨機的。

圖2 隔離超平面的構造過程

生成MRHiTree 的偽代碼如算法1 所示。

算法1生成MRHiTree

參數數據集X，當前樹高度h，閾值yz

3.2 多粒度掃描采樣

定義 6多粒度掃描。設數據的特征集合P={d1,d2,d3,…,du}，特征的最大值為u。多粒度掃描定義窗口大小q，當且僅當u＞q，根據窗口q重新構成新的特征集合，定義滑動窗口步長step，生成多個子特征集合，新的特征集合構成新的數據集。如式(7)所示。

其中，L為特征子采樣的最大值，如式(8)所示。

多粒度掃描的滑動窗口過程如圖3 所示。影響特征空間大小的因素為step 和q，隨著step 的減小，特征空間數量越多，但是時間開銷就越高。相反，隨著step 增大，生成新的特征空間數量就越少，當step＞q時，會產生特征丟失現象，因此step 的理論峰值為q。MGS 偽代碼如算法2 所示。

圖3 多粒度掃描過程

算法2 MGS

參數數據集X，維度集Dims，維度數目u，步長step

3.3 層次化集成學習異常檢測模型

本文首先利用多粒度掃描機制MGS 作為特征選擇過程，然后利用多維度隨機超平面隔離機制MRH 對基于孤立森林iForest 的異常檢測模型進行優化，從而構建基于多粒度掃描與多維度隨機超平面的孤立森林算法（MGS-MRHiForest）的層次化集成學習異常檢測模型。模型結構如圖4 所示，偽代碼如算法3 所示。

圖4 基于MGS-MRHiForest 的層次化集成學習異常檢測模型

算法3MGS_MRHiForest

參數數據集X，MRHiTree 的數量T，子樣本數ψ

MRHiForest 經過多粒度掃描后形成森林集合RFs={RF1,RF2,…,RFL}，表示葉子節點的深度，經過集成學習計算的過程如式(9)所示。

其中，ψ表示MRHiForest 的隨機子采樣大小，歐拉常數γ=0.577 215 664 901532 8，c(ψ)表示孤立樹中查找點失敗的平均路徑。

iForest 的時間復雜度為O(Tψlbψ)[18]，多粒度級聯會產生L個森林，所以MGS_MRHiForest 的時間復雜度為O(LTψlbψ)。

4 實驗結果與分析

實驗環境為Intel Core i7-6700 3.4 GHz；16 GB內存：Windows 10 操作系統。本文所有算法都基于Python 語言的Sklearn 庫實現，MRHiForest 在原始iForest 基礎上增加了多粒度掃描算法和隨機森林算法。本文使用Area Under ROC Curve(AUC)作為算法性能評測標準，AUC 越大，代表學習模型的泛化能力越強。所有實驗均經過5 次運算得到測量結果，并以其算術平均值作為最終的實驗結果。

iForest 的默認參數設定為 iTree 的數量T=100，子樣本數量ψ=256。這是因為iForest在此參數下有最好的檢測效果。

MGS 的默認參數設定為維數閾值q=100，粒度掃描步長step=1 。q體現多粒度掃描的特征選擇過程，step 則關系著樣本集的多樣性，步長越小，樣本集的多樣性就越高，iForest 的泛化能力就越強，但代價是時間開銷會增加。

4.1 復雜數據模式的局部異常點檢測

為了驗證在復雜數據分布的數據集中進行異常檢測的效果，使用阿基米德螺旋方程構造了包含1 000 個點的螺旋數據分布數據集，分別使用iForest和MRHiForest 算法生成異常分數圖，以展示算法對異常點的梯度分布。

實驗結果如圖5 所示。其中亮區表示異常分數較低，暗區表示異常分數較高，兩部分區域構成了復雜數據模式下正常數據和異常數據的數據分布規律。由圖5(a)可知，iForest 生成的異常分數梯度偏差較大，圖5(b)中MRHiForest 的異常分數梯度更符合螺旋數據的分布規律。上述實驗結果與算法的隔離機制有關，iForest 軸平行的特點導致偏差，MRHiForest 對隔離機制的改進使之對復雜數據模式具有更好的隔離能力。

圖5 iForest 和MRHiForest 在螺旋數據集中的異常分數圖

為了測試算法對異常數據的穩健性，在上述螺旋數據集中逐步添加異常點，分別計算2 種算法的AUC。螺旋數據集中添加100 個異常點如圖6 所示。

圖6 螺旋數據集中插入100 個均勻分布異常點

實驗結果如圖7 所示，2 種算法的AUC 曲線表明，MRHiForest 整體性能高于iForest，說明MRHiForest 的隨機超平面隔離機制更好地隔離了復雜數據模型的局部異常點。當異常點數為115 時，iForest 的AUC 減少到0.9 以下；當異常點為200 時，MRHiForest 的AUC 下降到0.9 以下，此時iForest 的AUC 為0.78。由此可知，MRHiForest 的穩健性強于iForest，AUC 的持續下降是因為異常點的數量占比達到數據集的16%以上，iForest 的適用前提正是數據集中異常點分布的稀疏特性。

圖7 iForest 和MRHiForest 在不同異常點樣本數量上的AUC

上述實驗中，MRHiForest 將iTree 數量T直接設定為iForest 的最佳參數值100。為進一步探討MRHiForest 中T的最佳設定，在異常樣本集為100 的螺旋數據集中，令T分別為20、50、100、150、200、250、300、350，逐一計算MRHiForest的AUC，以5 次實驗結果的算術平均值作為最終結果，并以方差作為算法的穩定性指標。實驗結果分別如圖8 和圖9 所示。

圖8 MRHiForest 在不同數量孤立樹下的AUC

圖9 MRHiForest 在不同數量孤立樹下AUC 的方差

隨機性是導致iForest 性能不穩定的主要原因[19]。而圖8 和圖9 表明，隨著iTree 數量T的增加，MRHiForest 的性能和穩定性也在增強，當T=100 時，AUC 的增長趨勢和方差逐漸平緩。這是因為MRHiForest 屬于集成學習方法，弱學習器iTree 的增加會降低錯誤率，增加穩定性[20]。考慮到iTree 帶來的時間開銷，將T的默認值設定為100。

4.2 高維數據集異常點檢測

為了檢測多粒度掃描機制MGS 對高維數據集異常點檢測的性能，使用維數為617 的實驗數據集isolet，分別測試iForest 和MRHiForest 的平均異常分數來對比算法對異常點的分離程度。平均異常分數AveScore 定義為數據集中所有異常點的異常分數的算術平均值，如式(12)所示。

其中，na為異常數據點總數，S(x a,ψ)為異常點xa在iForest 中的異常分數。

實驗分為iForest 組和MRHiForest 組，分別使用不帶MGS 的iForest 和MRHiForest 與帶MGS的MGS-iForest 和MGS-MRHiForest 進行評測并計算其AveScore。由于MGS 會產生多個子數據集，每個子數據集再分別使用 iForest 或者MRHiForest 進行層次化集成學習，因此，對未啟用MGS 的iForest 或者MRHiForest 也構造層次化集成學習模型，僅對完整的數據集進行L次重復訓練，從而生成L個iForest 或者MRHiForest。對各組分別進行500 次實驗，結果分別如圖10和圖11 所示。

圖10 iForest 組在高維數據集中的平均異常分數

圖10 的測試結果顯示，iForest 的AveScore 在0.55 附近波動，MGS-iForest 的AveScore 在0.65 附近波動，說明MGS-iForest 對異常點的檢測和分離能力高于iForest。

圖11 MRHiForest 組在高維數據集中的平均異常分數

圖11的測試結果顯示，MRHiForest的AveScore在0.76 附近波動，MGS-MRHiForest 的AveScore在0.85 附近波動，說明MGS-MRHiForest 對異常點的檢測和分離能力高于MRHiForest。

結合兩組實驗結果，使用MGS的算法AveScore普遍高于不使用MGS 的算法，說明多粒度掃描機制提高了算法對高維數據集異常點的檢測性能。

進一步的實驗結果如表1 所示，在不啟用MGS的iForest 和MRHiForest 的500 次實驗中，平均異常分數最大值與最小值之間的極差分別達到0.19和0.11；而在啟用MGS 的對照實驗中，平均異常分數最大值與最小值之間的極差降為0.05。這說明多粒度掃描機制提高了異常檢測算法的穩定性。

表1 4 種算法的平均異常分數

4.3 真實數據集

本節對表2 所示的4 個真實數據集分別進行異常檢測算法的性能評估。

表2 真實數據集詳細情況

表2 中，isolet 是簡單的音頻字母識別數據集，包括617 個特征。P53Mutant 是P53 基因編碼中與癌癥相關的數據集，包括5 408 個特征。http 是網絡入侵檢測數據集，來自KDD CUP99，提取其中3 個特征。mnist 為手寫數字0～9 數據集，提取其中2、3、5 的數據，并利用文獻[15]的算法進行處理，特征維度是96。對于低維度數據集http 和mnist，不需要進行多粒度掃描；對于高維度數據集isolet和P53Mutant，則要開啟多粒度掃描機制。

為評估基于質量評估算法和基于密度評估算法的優劣，將LOF 算法作為實驗的對比算法之一。在參數選擇上，LOF 的參數區間設置為10～1 000。iForest的隨機子采樣數量設置為2n，n取值1～10，取AUC最優組為實驗結果。實驗結果如表3～表5 所示。

表3 3 種算法的AUC

表4 3 種算法的時間開銷

表5 3 種算法的最優參數設定

由表3 可知，4 個數據集中，MRHiForest 的AUC 均優于iForest 和LOF。其中iForest 僅在低維度的http 數據集中表現出和MRHiForest 和LOF 相同的檢測性能。在http 數據集中，MRHiForest 的時間開銷比iForest 少，這是因為：1)MRHiForest 的隨機子采樣數目小于iForest，這使iTree 的構建速度更快；2)MRHiForest 的隔離機制提高了算法對異常點的敏感性，進而提高了異常檢測效率。

由表4 可知，除了isolet 數據集外，其他數據集中LOF 的時間開銷最大，這是因為：1)隨著數據量的增加，LOF 的最優參數K隨之增大，增加了處理開銷；2)隨著數據集維度的增加，距離計算的時間復雜度隨之提高。isolet 數據集中LOF 的時間開銷小是因為其數據量小，因此LOF 不適用于高維度、大數據量下的異常檢測。在高維數據集中iForest 的時間開銷是最少的，這是因為iForest 的單維度隔離機制對數據集的維數沒有依賴性，無論維度多高的數據集，iForest 都能以線性的時間開銷進行異常檢測[21]。

由表3～表5 可知，數據集維度和數據集大小與算法的時間開銷存在相關性，因此設計了2 個實驗進一步探索其相關性。

第一個實驗用來測試數據集大小與算法時間開銷的關系。將http 作為實驗數據集，選擇1×103～500×103個數據分別測試算法的執行時間。

圖12 表明，隨著數據集大小的增加，iForest和 MRHiForest 的執行時間均單調增加，但MRHiForest 的時間開銷更小。這是因為MRHiForest的平均查找路徑更短，而iForest 由于軸平行特性，iTree 相對較高，平均查找路徑較長。

圖12 iForest 和MRHiForest 不同數據集大小的執行時間

第二個實驗用來測試數據集維度與算法時間開銷的關系。將P53Mutant 作為實驗數據集，選擇5到1 000 個維度分別測試算法的執行時間。

圖13 表明，隨著數據集維度的增加，iForest 和MRHiForest 的執行時間均單調遞增，但維度的增加對MRHiForest 的影響更大。這是因為MRHiForest中每一顆樹的節點均是多項式計算，維度的提升增加了計算開銷；iForest 僅隨機選擇一個維度進行隔離，并不依賴于維度大小，因此時間開銷增加不明顯。

圖13 iForest 和MRHiForest 不同數據集維度的執行時間

進一步測試多粒度掃描機制對MRHiForest 和iForest 的性能提升，實驗結果如表6 所示。

表6 多粒度掃描機制下算法的AUC

由表6 可知，通過多粒度掃描的特征選擇，MRHiForest 和iForest 的AUC 均有所提升，驗證了多粒度掃描機制對算法的優化效果。

5 結束語

本文提出基于多維度隨機超平面的iForest 異常檢測模型MRHiForest，同時引入多粒度掃描機制MGS，構造了層次化集成學習異常檢測模型。MRHiForest 使用隨機超平面生成MRHiTree，使隔離機制更符合數據分布特征；MGS 增加了對高維數據集檢測的多樣性。與傳統iForest 的對比實驗結果表明，MRHiForest 對復雜的數據模型有更高的檢測效率，并且在低維數據集中檢測時間更少。對高維度數據集進行的對比實驗結果表明，MGS-MRHiForest 能夠彌補iForest 對高維度數據異常點不敏感和檢測不穩定的缺陷。

MGS 未考慮到關聯屬性特性，增加了算法的不確定性，隨著集成數量的增加，時間開銷有所增加，因此后續工作將考慮對關聯屬性特性的處理，進一步改善異常檢測模型的性能。