基于隨機子空間的擴展隔離林算法

謝 雨，蔣 瑜，龍超奇

（成都信息工程大學軟件工程學院，成都 610225）

（?通信作者電子郵箱jiangyu@cuit.edu.cn）

0 引言

大數據時代的到來，使得海量的數據被收集和存儲在數據庫中，從體量巨大的數據中挖掘可理解的知識顯得更加有意義。作為數據挖掘工作中重要的一環，異常檢測算法正在蓬勃發展［1］。越來越多的異常點檢測算法正在進一步被運用于日常生活的方方面面［2］。

近年來，國內外學者研究提出了多種異常檢測算法。文獻［3］中對這些算法進行了分類總結。按照異常識別技術分為:以基于角度的離群值檢測（Angle-Based Outlier Detection，ABOD）算法［4］與基于連接函數的異常檢測（COPula-based Outlier Detection，COPOD）算法［5］為代表的基于統計的方法；以K最近鄰（K-Nearest Neighbor，KNN）分類算法［6］為代表的基于距離的方法；以局部異常因子（Local Outlier Factor，LOF）算法［7］為代表的基于密度的方法；以及以自編碼器（Autoencoder）［8］為代表的基于學習的方法等。除此之外，基于集成的方法同樣也在不斷地被研究，其中具有代表性的技術包括:Bagging［9］與Boosting［10］抽樣等。文獻［11］中提出了一種基于隔離思想［12］的集成學習算法［1］:孤立森林（isolation Forest，iForest）算法，該算法首先構建了一個由多棵孤立樹組成的孤立森林，隨后將待檢測數據點在孤立森林中進行遍歷，記錄該數據點被完全隔離的平均路徑長度并生成對應的異常分數。文獻［13］中指出由于iForest 算法的核心思想為隔離，且每棵孤立樹通過隨機選擇的特征值來進行隔離，所以該算法具有計算速度快、準確度高與內存占用低等優點。

傳統方法在各個領域內被廣泛應用，可以通過不同方法的結合產生性能更優的異常檢測模型。文獻［14］中結合LOF算法的最近鄰思想與iForest 算法的隔離思想，提出使用最近鄰集合進行隔離（isolation using Nearest Neighbor Ensemble，iNNE）的異常檢測算法，使用最近鄰隔離超球體來隔離目標空間中的數據。該算法是一種基于隔離思想的高精度集成學習算法，具有精度高的優點，但在樣本數量巨大的數據集中，時間開銷太大。文獻［15］中結合多粒度掃描機制，提出了基于多粒度隨機超平面的孤立森林（Multi-dimensional Random Hyperplane iForest，MRHiForest）算法，該算法在多個小于原始數據空間的k維空間內分別構建孤立森林，通過多個森林集成投票機制，構成層次化集成學習的異常檢測模型。該模型提高了在高維數據集上進行異常檢測工作的穩定性與準確性，但存在精度下降、時間開銷增加等缺點。

文獻［16］中指出，iForest算法雖然效率與精度很高，但由于隔離條件通常為軸平行的，軸平行的隔離條件必然會導致隔離平面的交叉，進而產生呈規則分布的異常分數不準確區域。文獻［17］中進一步指出，在高維數據空間中使用iForest算法將導致類似的異常分數不準確區域大量存在，因此將這種問題定義為“局部異常不敏感問題”，并在最后提出了擴展隔離林（Extended Isolation Forest，EIF）算法，該算法則完全解決了孤立森林算法對局部異常不敏感的問題。但由于EIF 算法在擴展孤立樹的每一個節點上進行隔離計算時，都需要進行一次向量點乘運算，所以在預測中高維數據時，其時間開銷往往遠大于iForest算法。

綜上所述，iForest 算法對局部異常不敏感的問題會導致部分異常點無法被準確檢測，而EIF 算法雖然解決了局部異常不敏感的問題，但由于該算法的時間開銷太大，在高速發展的當下并不適用。

因此，本文結合子空間思想提出了基于隨機子空間的擴展隔離林（Extended Isolation Forest based on Random Subspace，RS-EIF）算法。該算法從數據空間中隨機選擇維度構建子空間，并使用隨機超平面來避免軸平行隔離條件下隔離條件重合區域的產生。本文算法在解決iForest算法對局部異常不敏感問題的同時，相較于EIF算法減少了計算開銷。

1 相關工作

1.1 iForest算法

1.1.1 孤立森林的構建

設數據集D={d1，d2，…，dn}且D?Ru，其中Ru為實數集，u為最高維度，n為數據個數，di={xi1，xi2，…，xiu}，其中i∈[0，n]。

文獻［12］定義孤立森林的構建過程為:首先，在數據集D中隨機抽取η次，每次確定ψ個樣本作為訓練集；然后，在每次抽樣完成后，以lbψ為高度限制構建一棵孤立樹；最后，在構建η棵孤立樹后，集成為一個孤立森林。

在每一個孤立森林中，包含的孤立樹均為二叉樹結構，下面給出孤立樹的定義。

定義1孤立樹。從［1，u］中隨機確定一個整數p作為隨機選擇的維度，統計維度p的范圍［pmin，pmax］，并在該范圍下隨機確定隔離條件q。當訓練集ψ中的數據點在p維度的值小于q時，將該數據確定為節點的左子樹節點；反之確定為右子樹節點。遞歸構建一棵高度限制為lbψ的二叉搜索樹。

完成構建孤立森林后，得到一個基于樹形結構的集成學習模型［18］。

1.1.2 孤立森林的缺點

在孤立森林中，數據點的異常程度通常由數據點在每棵孤立樹中遍歷的深度決定。這里的深度指的是數據點在空間中被劃分到無法繼續劃分的子空間時所需的劃分次數h。使用數據dk在具有η棵孤立樹的孤立森林中進行遍歷，得到路徑深度集合H(dk)={h1，h2，…，hη}，并求得平均深度E(h)。最后，將平均深度值通過式（1）歸一化處理為一個取值范圍為0～1的異常分數s(dk，n)。

式中，c(n)為歸一化因子，被定義為搜索失敗的平均路徑［12］。式（2）為c(n)的具體計算方式:

其中，H(i)為調和級數，可以通過ln(i)+0.577 215 664 9（歐拉常數）確定。

數據并不只是單一地分布在一個聚類中心，真實的數據往往具有多個聚類中心［19］。由于iForest算法的隔離條件是軸平行的，在多元數據集中，算法會因隔離條件的重疊使得局部異常難以被檢測到，從而導致算法精度下降。針對該問題，提出了基于隨機斜率構建超平面的EIF算法［17］。

1.2 EIF算法

1.2.1 EIF算法相關定義

EIF 算法基于iForest 算法進行改進，將軸平行的隔離條件替換為具有隨機斜率［20］的超平面。

定義2隨機斜率。在二維空間中，隨機超平面可以理解為線，而線段是具有斜率的，其斜率可以用平面內隨機一個點到原點的向量表示。同理，在k維的高維空間中，其隨機斜率可以表示為空間內的向量j=(i1，i2，…，ik)，其中i∈[0，1)且隨機生成。

本文將一個N維空間定義為一個具有N條坐標軸的空間。若存在一個超平面與N條坐標軸中的一條相交，則稱該超平面的擴展程度為0。以二維空間為例，在二維空間中，當擴展等級為0 時，隔離超平面可以理解為一條平行于坐標軸的直線。由于超平面需要由斜率與截距確定，下面給出自定義隔離等級的隨機截距向量與隔離超平面的定義。

定義3自定義隔離等級的隨機截距向量。在維度為k的空間中，存在s=(n1，n2，…，nk)，當隔離等級為k-1 時，n1，n2，…，nk均為不為0的實數。

定義4隔離超平面。在EIF 算法中，通過隨機生成超平面的隨機斜率j與具有自定義隔離等級的存在于超平面上的隨機截距s可以確定一個唯一的隔離超平面。

在確定隔離超平面后，隔離條件確定為:(d-s)·j，其中d表示來自數據集D中的一個待檢測數據點。當隔離條件的值小于0 時，將d劃分到當前根節點的左子樹，反之劃分到當前節點的右子樹。

1.2.2 EIF算法的優勢

為了展示由于隔離平面軸平行導致的精度下降的問題，本節首先使用基于正弦函數分布的二維數據集來計算各個點的異常分數，并使用熱圖分別繪制EIF 算法與iForest 算法對該數據集進行分析后的得分分布。實驗數據集為隨機在正弦曲線兩側呈高斯分布的1 000個二維數據點。隨后，對所得的數據分別使用EIF 算法與iForest 算法進行預測后，將所得到的異常分數劃分為10 個不同的等級，為每個等級標注邊界，并使用熱圖繪制邊界。兩種算法的得分熱圖如圖1所示。

iForest 算法得分熱圖如圖1（a）所示，而EIF 算法得分熱圖則如圖1（b）所示。對比兩個圖可以發現，正弦函數的任意兩個波峰或波谷之間，EIF 算法計算得到的異常分數相較于iForest 算法異常分數更加具有層次感；而且在EIF 算法的得分熱圖中，在數據分布外并沒有存在矩形的得分異常區域。因此，EIF 算法可以更好地計算處在正弦函數任意兩個波峰或波谷之間局部數據點的異常得分。

圖1 正弦分布數據上不同算法得分熱圖Fig.1 Score heat maps of different algorithms on sine distribution data

1.2.3 EIF算法的劣勢

EIF 算法核心為使用隨機隔離超平面進行隔離。假設使用維度為k的數據集構建一個包含η棵孤立樹的擴展隔離林，其中，每棵樹均為平衡二叉樹且包含有256 個節點，每棵樹的擴展等級均設定為k-1。現存在隨機生成的數據點m=(x1，x2，…，xk)，要想計算出該點的異常分數，在iForest 森林中，最多只需要進行8η次、最少僅需要η次比較運算即可得出數據點m的遍歷深度。

在EIF 森林中，每個節點上需要進行1 次向量減法與1 次向量乘法運算（在k維數據集中，需要進行k次減法、k次加法與k次乘法運算），即:最多需要8η次、最少η次向量運算。雖然在EIF 算法中的計算時間總體是呈線性增長的［16］，但相較于iForest算法，EIF算法的時間成本過高。

2 RS-EIF算法

首先，引入子空間思想，在介紹子空間思想在EIF 算法中的應用后，結合集成學習的優點，使用隨機子空間思想完成算法改進。然后，分析改進后算法RS-EIF 的時間復雜度與空間復雜度。

2.1 隨機子空間優化

根據多粒度思想［15］，本文將子空間定義為維度小于目標空間并存在于目標空間中的一個空間，此處的目標空間被定義為數據集所在的高維空間［21］。由此可知，擴展等級為k-1的EIF 算法可以理解為在維度為k-1 的子空間中構建維度為k的隨機斜率向量與隨機截距向量，其中k為目標空間維度。因此，EIF 算法可以理解為在一個完整的數據空間中，以子空間思想對數據進行隔離。

在文獻［17］中，隨著EIF 算法擴展等級的提高，算法對局部異常的敏感性也隨之提升。因此，為了在實驗中獲得最高的精確度，擴展等級往往需要設置為k-1。

然而，在最高擴展等級的子空間中構建擴展隔離森林雖然可以得到一個高精度的異常檢測模型，但是隨之而來的是大量上升的運算成本。因此考慮在更小的子空間中構建擴展隔離森林來提高運算速度。

EIF 算法本身是一種集成學習算法，并包含多個弱分類器。在EIF 算法中，雖然一棵擴展隔離樹的預測結果并不令人滿意，但在組合多棵樹構成森林后，其預測結果變得優于多數傳統的異常檢測算法。

因此，本文在隨機子空間l中生成具有擴展等級的隨機斜率j'與隨機截距向量s'，其中l＜k。再將隔離條件優化為d·j'＜s'·j'來確定數據點是否存在于l維子空間中的隔離超平面內。由此方法構建的樹結構命名為隨機擴展隔離樹RS-Tree（Random Subspace Tree）。

由于RS-Tree的精度會低于原本的擴展隔離樹，因此再通過構建多棵基于隨機子空間的RS-Tree 組成一個完整的模型來提高算法的精度。下面，給出構建RS-EIF 森林的偽代碼如算法1所示。

算法1 rsForest（X，t，ψ，k，extendlevel）。

輸入 數據集X，樹的棵數t，每棵樹包含的節點個數ψ，隨機子空間維度k，樹的擴展等級extendlevel；

輸出 包含t棵RS-Tree的RS-EIF森林。

算法1 需要構建RS-EIF 森林，該過程與EIF 算法中的擴展隔離樹構建過程類似。而森林中是包含多棵樹的，因此給出樹的構建偽代碼如算法2所示。

算法2 rsTree（X，e，l，k，extendlevel）。

輸入 數據集X，當前樹的高度e，樹的高度限制l，子空間維度k，樹的擴展等級extendlevel；

輸出 1棵RS-Tree。

在一個完整的RS-EIF 森林中，要想實現對數據的決策判斷，需要將該數據在森林中的每棵樹進行遍歷，計算其平均路徑長度，最終給出判斷結果。下面給出計算遍歷深度的偽代碼如算法3所示。

算法3 PathCount（d，tree，e，k）。

輸入 數據點d，RS-Tree 的節點tree，當前路徑長度e，隨機子空間維度k；

輸出 數據點d的路徑遍歷長度。

最終，在計算出目標數據點的平均路徑長度（平均深度）后，再使用式（1）處理為對應的異常分數。異常分數越高，則數據的異常程度就越高。

2.2 時間與空間開銷分析

2.2.1 時間開銷分析

假設在n個維度為K的數據集中，構建包含t棵RS-Tree的RS-EIF 森林，每棵樹包含ψ個節點，取子空間大小為k，擴展等級為k-1。其中，0 ＜k＜K。

在訓練階段，需要進行t次隨機抽樣。由于t是常數，因此其時間復雜度為O(1)。在構建RS-Tree時，每棵樹只需要進行一次隨機的k維選擇即可確定子空間，再在子空間中進行ψ次隨機生成所需的兩個向量并計算不同節點隔離值的工作。因此，一棵完全的RS-Tree只需要常數時間O(ψ)即可完成構建。對于包含t棵樹的RS-EIF 森林，其訓練過程時間復雜度為O(ψt)。

在測試階段，一棵完全RS-Tree 中，最多只需要8 次向量乘法運算與比較運算，由于k維常量，可以近似地等于O(1)。則在t棵RS-Tree進行遍歷，時間復雜度為O(t)。因此，訓練階段的時間復雜度取決于樣本個數。對于n個樣本，時間復雜度則等同于O(tn)。由于t是一個需要指定的參數，該參數通常為常數，因此時間復雜度可以理解為O(n)。

2.2.2 空間開銷分析

由于RS-EIF 算法的目的是生成一個強分類器用于判斷輸入信息是否是異常的，因此，算法只需要存儲這個包含t棵RS-Tree 的數據結構以及其包含的信息。因此空間復雜度為常數。

3 實驗與結果分析

為了驗證RS-EIF 算法的有效性，本文使用3 組實驗來分別驗證該算法的準確性與時間提升。

實驗中，使用的人工數據集共有7 個，這些人工數據集均使用Python 自帶的sklearn 包生成，每個數據所包含的數據點都是呈高斯分布均勻地分布在4 個聚類中心周圍。其中，DS_One、DS_Two、DS_Three 與DS_Four 均為二維數據，其樣本數量以2 000 的步長遞增；而DS_Five、DS_Six 與DS_Seven 則為包含4 000 個樣本的數據集，并且其維度以步長2 增長。在這些數據集中，異常數據由均勻分布在其他聚類中心周圍的10個數據代替，具體的信息如表1所示。

表1 實驗使用的人工數據集Tab.1 Synthetic datasets used in experiments

其次，實驗使用的真實數據集來自離群值檢測數據庫（Outliter Detection DataSet，ODDS）［22］，本文選擇其中9個具有代表性的多維點數據集進行實驗。選取的數據集信息如表2所示。這些數據包括低維到高維、低樣本數量到高樣本數量的數據，可以更好地展現本文算法的性能。

表2 實驗使用的ODDS數據集Tab.2 ODDS datasets used in experiments

最后，所有實驗使用Python3.8.3 編程實現，運行在Windows 10 操作系統，12 GB 內存，Intel Core i5-4200H CPU@2.90 GHz的計算機平臺上。由于實驗中所涉及的5種算法中有3 種均為基于樹型結構的集成學習算法，因此為了更加清晰直接地展現對比結果，將3 種算法的部分參數默認設置為訓練100棵包含256個節點的樹。

3.1 局部異常檢測

本節選取DS_One 為實驗數據集。在該數據集中，存在2個聚類中心的距離偏近，因此視覺上產生了類似于存在3 個聚類中心的效果。而異常點則明顯遠離數據集中的大量數據。

根據前文分析，如果在該數據集上使用傳統的iForest 算法，則必定會產生至少一個矩形的得分異常區域。因此，本節使用與前文類似的方式繪制EIF算法與RS-EIF算法的異常得分熱圖來觀察是否有效避免了矩形異常區域的產生。

在參數設置方面，由于DS_One 是一個二維數據集，為了避免RS-EIF算法在維度為1的子空間出現隔離條件失效的問題，本節將子空間的維度設置為2。除此之外，兩種算法的擴展等級均設置為最高等級。實驗結果如圖2所示。

在圖2（a）中清晰地展示出:EIF 算法的異常分數熱圖中，并沒有存在呈矩形、由隔離條件重疊所導致的分數異常區域。在圖2（b）中，同樣沒有發現類似的矩形區域。然而，圖2（b）的異常分數輪廓的平滑程度并沒有達到圖2（a）的程度。分析后發現，導致該現象出現的原因在于:本節并沒有刻意地調整參數設置以達到最佳效果。

圖2 多元分布數據上不同算法得分熱圖Fig.2 Score heat maps of different algorithms on multivariate distribution data

綜上所述，不難發現，RS-EIF 算法具有與EIF 算法相似的局部異常檢測能力。

3.2 維度與樣本數量對算法運行時間的影響

本節首先使用RS-EIF 算法與EIF 算法對DS_One、DS_Two、DS_Three 與DS_Four 這4 個數據集進行預測。除了默認參數外，同樣指定RS-EIF 算法在維度為2 的子空間進行訓練，兩種算法的擴展等級均設置為最高等級，并且采取10次實驗求平均值的方法，得到在不同人工數據集的運行時間，實驗結果如圖3所示。

圖3 展示了在不同樣本數據量的情況下，兩種算法在運行時間方面的差異。在圖3（a）中，所繪制的兩條線分別代表兩種算法在不同數據集的運行時間。不難看出，雖然兩條折線都是近似線性增加的，但RS-EIF 算法的運算時間明顯少于EIF 算法。出現該現象的原因是:RS-EIF 算法在預測階段，每個節點的遍歷只需要計算1 次隨機斜率向量與數據點的點乘；而EIF 算法在預測階段的節點遍歷則需要分別計算隨機截距向量與數據點同隨機斜率向量的點乘。

除此之外，本節還選取了DS_Two、DS_Five、DS_Six 與DS_Seven 數據比較數據維度對兩種算法運行時間的影響。由于上述4 個數據的維度是不同的，因此在兩種算法中，擴展等級均設置為最高等級。而RS-EIF 算法的子空間維度則分別設置為:2、3、5、7。

通過圖3（b）發現，兩種算法在不同維度的數據集中，運行時間均在一個固定范圍內上下變化，但RS-EIF 算法的運行時間同樣遠少于EIF 算法。出現該現象的原因在于:所選取的數據集樣本數量并不大，沒有完全體現算法在不同維度數據集上的運行時間差異。

圖3 數量與維度對運行時間的影響Fig.3 Impact of quantity and dimension on running time

綜上所述，在相同維度的數據集中，雖然EIF 算法與RSEIF 算法時間開銷均表現為隨樣本數量的增加而線性增加；但在樣本數量相同的數據集中，EIF 算法的時間開銷是遠多于RS-EIF算法。

3.3 與其他異常檢測算法的比較

本節將兩個樣本數量較多的數據集ForestCover與Http按照1∶9 劃分為測試集與訓練集；將兩個樣本數量過少的數據集Glass 與Lympho 采用10 折交叉驗證求均值的方法進行實驗；其余數據則使用5折交叉驗證取平均值的方法獲得結果。

算法選擇方面，將RS-EIF 算法與同為集成模型的iForest算法、EIF 算法與輕型在線異常檢測（Lightweight On-line Detection of Anomalies，LODA）算法［23］以及基于統計的COPOD 算法［5］進行對比，這些模型均使用PyOD 庫［24］實現。參數設置方面，iForest 算法使用默認參數；而EIF 算法與RSEIF 算法的擴展等級則均設置為最高；除此之外，為了方便計算，RS-EIF 算法的子空間維度設置為對應數據空間維度的一半；LODA 算法的直方圖數量與隨機消減數則分別設置為文獻［23］中提出的10與100。

表3 給出了5 種算法在時間開銷與精確度方面的差異。其中:時間是指從開始訓練到結束預測的時間；精確度（ACcuracy score，AC）則表示使用sklearn 包中的相應函數計算5種算法預測結果的準確度。通過表3可以發現，在樣本數量大于1 000 的數據集中，RS-EIF 算法、EIF 算法的精確度與iForest 算法、LODA 算法、COPOD 算法相比分別高出了2～12 個百分點與3～15 個百分點，但在時間開銷上，兩種算法則均劣于其他3 種算法。除此之外，RS-EIF 算法與EIF 算法在這些數據集上的精確度均相差不超過5 個百分點，而RS-EIF 算法的運行時間卻遠少于EIF 算法。RS-EIF 算法與EIF 算法的精確度遠高于其他算法的原因是兩種算法均使用隨機超平面進行隔離，可以有效識別出絕大部分異常點。因此，RS-EIF 算法相較于EIF 算法的改進是行之有效的。而在兩個樣本數量過少的數據中，RS-EIF 算法的精確度雖然低于EIF 算法，但與其他3 種算法對比可以發現，其精確度還是明顯高于iForest 算法的，導致出現該現象的原因則可能是樣本數量過少。

綜合分析實驗結果可知，RS-EIF 算法的時間開銷在各類型的數據集上均少于EIF 算法，具體約下降60%。在實驗精確度上，RS-EIF算法與EIF算法相差不大，但在中大型數據集中卻明顯優于iForest 算法、LODA 算法與COPOD 算法。除此之外，由于RS-EIF 算法需要在子空間中進行訓練與預測，而該過程包含大量的隨機運算，因此，即使集成學習的方式提高了RS-EIF 算法的精確度，但在少數數據集上，RS-EIF 算法與EIF算法相比還是略有不足。

4 結語

本文從iForest算法的隔離條件軸平行導致算法對局部異常不敏感入手，借鑒EIF 算法解決該問題的思想，提出在隨機子空間中使用隨機超平面進行隔離的RS-EIF 算法。該算法從減少向量計算維度的角度入手，充分利用隨機的不確定性與集成學習提高弱分類器分類效果的特質，使得性能更加穩定。

實驗結果驗證了RS-EIF 算法存在精度高、時間開銷呈線性增加并且明顯少于EIF 算法的特點。在真實的ODDS 數據集上，將RS-EIF 算法與其他4 種算法分別對比了精確度與時間開銷的差異，得出結論為:在樣本數量更大的數據集中，RSEIF算法的精確度與EIF算法相近，但相較iForest算法、LODA算法與COPOD算法來說，RS-EIF算法的精確度平均提升約為5個百分點；在時間開銷方面，該算法較EIF 算法減少約60%，但與其他3 種算法相比，時間開銷并不占優勢。因此，本文所提RS-EIF 算法是一種適用于中大型多元數據集的高精度異常檢測算法。

由于本文算法在計算隨機超平面時離不開向量的點乘計算，因此時間開銷還是偏大。下一步，可以結合集成學習中，各個弱分類器之間可以不存在耦合關系的特點，將該算法部署在分布式系統上，通過合理的任務規劃，提高本文算法的運行速度與精確度。