基于高對比度子空間的改進孤立森林方法

摘 要：針對孤立森林通過隨機選擇屬性進行數據空間分割，在面對高維數據時具有不可靠性這一問題，提出了一種基于高對比度子空間的改進孤立森林算法 （high contrast subspace isolation forest，HiForest）。首先，該方法基于子空間各屬性邊緣概率與聯合概率間的偏差值，選取具有高對比度值的子空間；其次，在相關子空間中構建離群點檢測能力更優的隔離樹，多棵隔離樹集成為隔離林，通過遍歷數據點在隔離森林中的平均路徑長度從而得到異常分數。基于ODDS數據集的實驗表明，與傳統的異常檢測算法相比，HiForest在曲線下面積、查準率、召回率和F1-score評價指標上均有較明顯的提升。因此，HiForest算法是一種適用于中高維數據集，檢測精度更高的異常檢測算法。

關鍵詞：異常檢測；孤立森林；子空間；HiForest

中圖分類號：TP18 文獻標志碼：A 文章編號：1001-3695（2023）02-012-0388-06

doi： 10.19734/j.issn.1001-3695.2022.06.0305

Improved isolation forest method based on high contrast subspace

Zhou Hang， Jiang Yu

（College of Software Engineering， Chengdu University of Information Technology， Chengdu 610200， China）

Abstract：Aiming at the problem that isolation forest is unreliable in the face of high-dimensional data by randomly selecting attributes， this paper proposed an improved anomaly detection algorithm high contrast subspace isolation forest （HiForest）. Firstly， this algorithm selected the subspace with high contrast value based on the deviation between the edge probability and the joint probability of each attribute in the subspace. After that， the algorithm constructed isolation trees which had a stronger ability to isolate outliers in the relevant subspace. Finally， the algorithm integrated these isolation trees into isolation forest， and obtained the anomaly score by traversing the average path length of data points in the isolation forest. Compared with traditional anomaly detection algorithms， the experimental results based on the ODDS database show that the HiForest algorithm improves the AUC， accuracy， recall rate significantly. Therefore， HiForest algorithm is an anomaly detection algorithm suitable for high-dimensional datasets with higher detection accuracy.

Key words：anomaly detection; isolation forest; subspace; HiForest

0 引言

隨著大數據時代的到來，數據容量和維度的增加對包括異常檢測在內的數據挖掘帶來了新的挑戰，如何在復雜的數據中準確地找到少量的異常成為異常檢測的一個重要研究方向。異常檢測在數據挖掘有著重要的作用，Hawkins［1］將異常定義為一種與其他觀察結果非常不同的觀察結果，以至于使人們懷疑它是由一種不同的機制產生的。近年來，異常檢測在生產生活的場景中有許多應用領域，包括網絡安全中的入侵檢測［2］、信用卡欺詐檢測［3］、醫療數據分析［4］等。文獻［5］指出，基于無監督的異常檢測模型主要包含基于統計的方法［6］、基于距離的方法［7］、基于密度的方法［8］、基于聚類的方法［9］以及基于樹［10］的方法四種。

本文重在研究基于樹的異常檢測，Liu等人［11］提出了孤立森林（isolation forest，iforest），算法利用隔離的思想使用垂直于坐標軸的隨機超平面對數據空間進行切割，從而“孤立”離群點，與基于密度和聚類的方法先相比，它避免了計算距離、密度，所以算法在時間開銷上更有優勢，同時也減少了異常的掩蓋和淹沒效應。 隨著孤立森林的提出，大量學者對其展開了研究。文獻［12］提出了SCiForest（separate cluster iForset，SCiForset），算法主要是用于檢測局部聚類異常，它在構造隔離樹的節點時隨機生成多個超平面并計算它們的增益Sdgain，最后選擇Sdgain值最大的超平面作為最優超平面進行切割，相比于傳統的孤立森林算法更適合于離群點分布復雜的場景，但是由于需要計算超平面的信息增益，計算量相比于iForest有所增加。Hariri等人［13］針對iForest每次都是垂直或者水平切割，會造成偽影的問題提出了EIF（extended isolation forest），EIF通過使用隨機斜率而非軸平行的超平面對數據空間進行切割，解決了偽影的問題并且提高了精度和穩定性，但執行效率低。針對EIF時間開銷過大的問題，文獻［14］提出了一種基于隨機子空間的擴展隔離林算法（random subspase EIF，RS-EIF），該算法在隨機子空間中通過計算每個節點的截距向量與斜率來構建隔離樹以達到提升算法速度的目的，但仍存在檢測精度下降的問題。

在高維數據中基于距離、密度的算法通常不可行，這是因為在高維空間中會出現數據稀疏的問題，幾乎等距的問題導致計算出來的距離沒有過大的差異。而異常值的定義是處在稀疏區域的數據點，這種矛盾導致在高維數空間中找到離群點變得困難。顯然，在全維度進行異常檢測會存在問題，異常值將會被大量正常點掩蓋，所以異常值通常會嵌在局部相關的子空間中。而孤立森林也可以看做一種子空間的方法，它在構建隔離樹的過程中，每一次空間切割都是在全維空間中隨機選擇的屬性，面對高維數據存在無關維度或噪聲維度時，這種較強的隨機性會影響到算法可靠性和效率，而找到適當的子空間可以過濾掉大量無關維度累加的噪聲效應。

針對以上問題，本文提出了一種改進的孤立森林算法HiForest進行異常檢測。該算法利用高對比度子空間在處理高維數據中的特點，首先用統計學檢驗的方法計算子空間的對比值，根據參數的選擇尋找高對比度子空間，在搜索到對比度值排名靠前的子空間中進行隔離樹的構建。與原算法相比，該算法能夠避免無關維度對構建隔離樹的影響，從而提高了異常檢測的性能和效率。

1 相關工作

1.1 孤立森林

孤立森林與同為集成學習的隨機森林［15］類似，都是由多棵樹構成的集合，但孤立森林的構建過程與隨機森林不同，在每棵隔離樹中，對屬性進行隨機抽取并隨機選擇處于最小值與最大值之間的特征值進行軸平行分割，異常值通常單獨被劃分到一個分支中的葉子節點，其所需的劃分次數與正常值相比較少。因此，葉子節點到根節點的距離可用于計算得分，最后將樣本在不同隔離樹上的平均路徑長度用于最后的異常評分計算。

具體地，隔離樹構造的初始狀態是先創建一個包含所有節點的根節點，假設用于進一步分裂的候選列表C是一個包含根節點的列表。隨機從列表C中選擇一個節點R，然后從列表C中刪除，接著再隨機選擇一個屬性xi，并將節點R中的數據按照隨機值p分成R1和R2兩組，在R1中的所有數據都滿足xi≤p，R2中的所有數據都滿足xigt;p。隨機值p是在節點R的第i個屬性的最小值和最大值之間隨機選擇。重復以上步驟即可創建一棵隔離樹，直到候選列表C為空。

一旦生成t棵隨機隔離樹就創建了森林，用測試數據x去遍歷所有隔離樹，整個遍歷過程中的路徑長度記做h（x）。最后，異常分數的定義如式（1）所示。

其中：E［h（x）］是樣本x在孤立森林中路徑長度的期望；c（n）是數據集大小為n的h（x）的平均值，c（n）的計算為

其中：H（i）是一個諧波數，可以近似為In（i）+0.5772156649（歐拉常數）。

根據式（1），當E［h（x）］=C（n）時，異常分數趨近于0.5，樣本x的平均長度與樹的平均路徑長度相近時，不能區分是否為異常。當h（x）趨近于無窮時，異常得分趨近于0，說明x不是一個孤立點。相反，x是正常樣本時，h（x）趨近于0，異常得分趨近于1。因此，可以設置一個閾值S0∈［0，1］，當S（x）gt;S0時判定為異常，反之為正常。

1.2 高對比度子空間

給定一個數據集DB，其中包含N個數據對象，每一個數據對象都可以描述為一個向量x=（x1，…，xD），其中索引的集合ω={1，…，D}表示一個全局的數據空間。對于任意的屬性子集S={s1，…，sd}ω被稱為d維的子空間投影。假設給定了子空間S={s1，…，sd}，在該子空間中的數據向量表示為xs=（xs1，…，xsd），其聯合概率密度表示為ps1，…，sd（xs1，…，xsd），屬性Si的邊緣概率密度函數表示為psi（xsi）。該方法的思想是通過一系列統計概率的計算找到一個具有高對比度值的子空間。具體定義如下：

定義1 相關子空間。根據概率論中的定義，若有兩個事件A和B，當且僅當滿足p（A∩B）=p（A）·p（B）時，事件A和B被稱為相互獨立且不相關的。將這個定義引申到子空間中，當且僅當滿足式（3）時，滿足這樣條件的子空間被稱為不相關子空間。

ps1，…，sd（xs1，…，xsd）=∏di=1psi（xsi）（3）

但是由于數據的分布具有不均勻性，高對比度子空間是不滿足這一假設的。為了直觀理解相關子空間和不相關子空間的差異，圖1中給出了示例，這兩個數據集來自相同的邊緣分布。

可以在圖1（a）中觀察到x和y這兩個維度是完全不相關的，但是數據集中卻包含一個離群點m1，若考慮一維屬性的投影，m1為離群點是合理的，并將具有這種性質的離群點稱為平凡離群點。而在圖1（b）中，維度之間明顯出現了相關性，除了離群點m1外還出現了離群點m2，而m2隱藏在所有一維子空間投影之中，將這種離群點稱之為非平凡離群點，因此對于包含了非平凡離群點的子空間稱為相關子空間，其中隱藏了更具有價值的信息，而m1只要在包含維度y的子空間中都可被檢測出來。對于不相關子空間而言，應當滿足式（4），其中在不相關子空間中假設一個數據對象x的期望密度為pexpected（xs1，…，xsd）。

定義2 子空間切片。在子空間S中，|S－1|個上下條件［li，ri］的集合稱為子空間切片。

最后，子空間的對比值由式（6）計算，整個過程采用了蒙特卡羅方法計算，算法進行了M次迭代，對于每次迭代，隨機選擇一個屬性si∈S并生成一個隨機子空間切片Ci。其中，si指屬性si相對整個數據集的邊緣密度。si∣Ci指xsi相對于剩下屬性且滿足約束條件集合Ci的密度。

執行統計檢驗的deviation函數如式（7）所示。最后，通過平均M個統計檢驗的偏差作為計算子空間對比度的最后結果。

2 基于高對比度子空間的孤立森林算法

孤立森林的整個構造過程是在數據全空間中不斷地隨機選擇一維切割，這種隨機性會導致在生成隔離樹時未用到大量有用的屬性，且噪聲維度也會對算法的可靠性產生負面影響。所以，當面對海量高維的數據時，孤立森林的這種隨機性可能會漏選掉導致異常程度較高的屬性，使得孤立森林算法在異常檢測中出現精度較低的問題。

文獻［16］指出在構建隔離樹時，由于是基于隨機化技術，不清楚如何選擇合適的屬性以及在給定屬性上定位優化分割點，利用各屬性上的值分布的累計差異對屬性異常程度進行評估。文獻［17］提出孤立森林不適用于特殊的高維數據，對噪聲特征不夠魯棒，所以將熵這個概念引入到其中，通過信息熵來反饋每個屬性中樣本數據分布的均勻性，若該屬性熵越高每次就越有可能被選擇用于數據空間的切割。從以上文獻可知，眾多學者針對孤立森林在構建隔離樹時隨機選擇屬性的問題采用不同方法進行了優化。但是，他們只從單維度的角度出發，忽略了一些維度的相關性，所以在多維空間中不能夠精確地檢測到異常點。

受文獻［18］啟發，本文引入高對比度子空間的概念，通過對子空間中各屬性邊緣密度與聯合概率密度之間的偏差進行計算，可得到子空間各屬性之間的相關度評估。孤立森林也可以看做是在隨機子空間中構建隔離樹，而子空間的選擇對隔離林是否能有效檢測出離群點起著至關重要的作用，采用相關度高的子空間相比于孤立森林產生的隨機子空間更易于分割出離群點。此外，與基于概率統計的方法相比，隨機方式尋找到具有高相關度子空間的概率較小。本文利用高對比度子空間的思想選取屬性相關度排名靠前的子空間，并在各個子空間中構建隔離樹相比于iForest而言，在構建隔離樹時降低了隨機性，從而使得隔離樹中的分支有更為明顯的差異，通過改進隔離林的構造過程，使得HiForest算法在多個性能指標上有所提升。

首先，隨機生成多個子空間切片，在生成子空間的過程中評估當前d維子空間的對比度，對比度高于一定閾值的子空間將用于生成（d+1）維候選子空間，像這樣逐步生成高維子空間，并根據式（6），利用統計檢驗方法和概率密度之間的關系計算對比度值。其次，在訓練階段選擇具有高對比度值的子空間，用其構建隔離樹。最后，對于待檢測數據x，計算它在遍歷每一棵HiTree時的路徑長度h（x），并按照式（1）得到其異常分數，從而判斷是否為異常值。本文算法的具體步驟如下。

算法1 function findHiCS（S，M，α）

輸入：子空間S，迭代次數M，參數α。

輸出：S的對比度值contrast（S）。

在子空間S中隨機選擇一個樣本點

for i=1 to M do

初始化子空間屬性序列si∈S

selectedObject←true

for j=1 to |S|-1 do

隨機選擇大小為N·|S|α的索引塊

標記索引塊為selectedObject

end for

deviation（si，si|selectedObject）

end for

return contrast（s）

通過計算子空間中聯合概率密度和邊緣密度之間的偏差找到具有高對比度值的子空間，根據偏差值找到需要的子空間后在其中構建隔離樹。下面給出隔離樹構建的偽代碼。

算法2 function HiTree（φ，e，l，selected_s）

輸入：子采樣φ；當前樹高e；樹限制高度l；子空間selected_s。

輸出：隔離樹HiTree。

if e≥l or |x|≤1 then /*若當前樹高超過了限制高度或樣本點不夠則返回葉子節點*/

return exNode

end if

隨機選擇一個維度q∈selected_s

在維度q中隨機選擇分割值p

Rl← filter （qlt;p）

Rr← filter （q≥p）

return inNode（

left←HiTree（Rl，l+1， limit）

right←HiTree（Rr，l+1，limit）

splitDim←q

splitVal←p）

end

在算法2中，在具有高對比度子空間中通過遞歸的方式生成隔離樹后，下一步將隔離樹集成為森林，偽代碼如下：

算法3 function HiTreeForest（X，φ，t）

輸入：數據集X，子采樣數φ，隔離樹數量t。

輸出：包含多棵HiTree集合成的森林Forest。

初始化森林HiForest

限制隔離樹的樹高set l=ceil（log2φ）

for i=1 to t do

X′←sample（X，φ）" //從數據集X中子采樣

forest←HiTree（X′，0，l，selected_s）

end for

與原算法一樣，通過整合多棵具有差異性的HiTree來構建隔離森林。特別地，樹高度的限制是由子采樣的大小決定的，但通常被設置為8。

算法4 function computePathLength（x，T，e）

輸入：測試樣本x；隔離樹T；當前路徑長度e （初始化為0）。

輸出：x的異常分數。

if type（T）==exNode then

return e+c（T.size）

end if

splitDim←q

splitVal←p

if x［q］lt;p then

return computePathLength（x，T.left，e+1）

end if

else

return computePathLength（x，T.right，e+1）

end

最后，通過遞歸的方式計算了樣本x的平均遍歷長度，利用式（1）得到異常得分。根據得分進行異常判斷，異常分數越高，說明樣本為異常的可能性越大。

3 算法復雜度分析

假設在一個包含t棵樹的隔離林中且每棵樹的子采樣為φ。首先，在訓練階段，HiForest需要計算子空間的對比度值，在這一部分時間復雜度為O（M·N），每次計算需要迭代M次，在每次迭代中需要計算N次，由于M是常數，所以在計算子空間對比度值時需要的是線性的時間復雜度。構建一棵包含φ個節點的隔離樹來說時間復雜度為O（φ×log（φ）），所以在構建隔離林時整體的時間復雜度為O（t×φ×log（φ））+O（M×N） ，由于t和φ都為常數，最終的時間復雜度為O（M×N）；在測試階段，與訓練階段類似，給定測試樣本數量為n，整體的時間復雜度為O（n×t×log（φ）），同樣t和φ都為常數，因此時間復雜度為線性的O（n）。最后，整體上時間復雜度為O（M×N），盡管相比于原算法時間復雜度并沒有明顯的優勢，但是也是線性的時間復雜度，并且在性能方面有所提高。最后，對于空間復雜度，在構建隔離林時每棵樹需要的空間復雜度為O（n），整個森林為O（tn），由于t通常為較小的常數，所以最終還是為O（n）。

4 實驗結果及分析

為了評估HiCS-iForest的性能，在本章與其他七個離群值檢測方法進行了對比，包括基于角度、距離以及同為樹模型等異常檢測算法。其中，ABOD［19］、LOF［20］、PCA［21］、CBLOF［22］、COPOD［23］、iForest的實現都可以在開源工具庫PyOD［24］中找到。使用的六個數據集均來自ODDS，表1記錄了數據集的詳細信息。實驗平臺配置位Intel Core i7-7500U CPU，8.00 GB內存，64位操作系統的Windows主機，實驗采用Python語言版本為3.8，并在Anaconda4 JupyterLab中實現。

4.1 數據集

實驗采用的數據集均來自于ODDS，包括optdigits、speech、wbc、satellite、lympho和satimage-2六個數據集，在表1中有簡單的描述。其中，speech數據集由3 686段不同口音的英語語音組成，大多數數據對應于美國口音，只有1.65%對應于其他口音之一，被視為異常值；optdigits是一個手寫數字數據集，包含64個屬性，數字1～9是正常實例，數字0歸為異常；wbc數據集是威斯康辛州診斷的乳腺癌數據，特征由乳腺腫塊的數字化圖像計算出來，惡性腫瘤被視為異常；satellite數據集是一個多分類數據集，包含了衛星圖像3×3領域中的多光譜值，以及與每個領域中新像素相關的分類，其中2、4、5組成異常值類，其他類歸為正常類；lympho數據集是由腫瘤研究所提供的淋巴圖，共有四個類，2和4這兩個占比小的類作為異常；satiamge-2數據集是satellite的改良，從數據庫中隨機抽取圖像并對圖像進行分割和處理，最初是為了多分類而設計的，通常將不常見的類合并在一起將它們標記為異常。

4.2 HiForest參數分析

為了驗證HiForest在參數t=100，φ=256條件下能夠取得較好的表現，在本節中分別對參數進行討論，分析不同參數數值對實驗結果的影響。

首先，為了探測根節點采樣數量對隔離樹構建的影響，設定t=100，將子采樣分別設置為φ=16，32，…，4 096，因此在數據集上選用超過5 000樣本點的三個數據集satimage-2、satellite和optdigits。為了降低實驗偏差帶來的影響，每輪都取10次運行結果的平均值作為最后的實驗結果，實驗結果可以從圖2中觀察到AUC在子采樣很小的時候趨于收斂，數據集satimage-2中在φ=128附近處于峰值，optdigits在φ=64附近AUC接近于最優值，隨后在φ=256后趨于穩定，而數據集satellite在φ=256處表現最為良好，根據測試結果選擇φ=256作為最優參數。

其次，由于集成學習是通過結合策略將弱學習器組合起來以達到一個強學習器的目的，但對于基分類器的數量并不是越多越好，所以為了驗證隔離樹數量對實驗結果的影響，設定φ=256，將隔離樹數量分別設置為t=10，15，…，500，采用數據集optdigits、wbc、satellite、lympho和satimage-2作為實驗對象，同時也取10次實驗結果的平均值作為最后的評價指標，所得結果如圖3所示，optdigits數據集中的AUC隨著t的增加呈現上升的趨勢，80棵附近達到峰值，隨后呈下降趨勢，在t=100趨于平緩，其他數據集整體上都在達到100棵時開始收斂。綜合來看，選擇參數值t=100作為最佳參數。

4.3 算法的性能驗證

為了評估分類算法的性能，通常會使用到混肴矩陣，對于二分類問題，其混肴矩陣如表2所示。其中，TP（true positive）表示實例為正并且被預測為正類的樣本；TN（true negative）表示實例為負并且被預測為負類的樣本；FN（1 negative）表示實例為正并且被預測為負類的樣本；FP（1 positive）表示實例為負并且被預測為正類的樣本。

通常異常檢測面對的都是不平衡數據集，如果只是使用單一的評估指標并不能衡量模型的性能，所以，在本文實驗中采用了AUC（area under curve）、查準率（precision）、召回率（recall）以及F1值（F1-score）作為評估指標。AUC是ROC曲線與坐標軸圍成的面積，取值為［0，1］，面積越大作為代表模型的性能越優越，計算如式（8）所示，其中，ri表示在增序序列中第i 個正類實例的位置，n0和n1分別是正類和負類的個數。如式（9）和（10），查準率的目的在于計算所有被預測為正的樣本中實際為正的概率，召回率在于找到實際為正的樣本中被預測為正樣本的概率。當比較兩個具有低查準率和高召回率的模型時很難作出好壞的判斷，為了使它們具有可比性，需要計算F1-score，如式（11）可以同時度量查準率和召回率，F1值越大則表明分類器效果更好。表3記錄了HiForest與不同算法的AUC對比。

從表3可以觀察到，HiForest相比較于其他異常檢測方法，可以看出在數據集optdigits、wbc、satellite、lympho上在AUC上均優于其他檢測器。具體地，HiForest在lympho上表現最好，AUC高達0.998 2，略微優于傳統的iForest，但在數據集optdigits上的提升最高，相比于原算法提高了約20%，相較于檢測性能次高的算法提升了約3.2%，而對比于其余的算法平均提升了約40%，這是因為在高維數據集中，數據的分布不同于低維空間，數據之間的距離、密度和角度之間的偏差越來越相近，所以在ABOD、LOF等基于這種思想的算法中表現較差，而iForest、SCiForest算法是利用隔離的思想，并不需要進行相似度計算，所以在高維數據有更好的表現。整體上看，HiForest在六個數據集上的表現相較于同類型的算法在AUC指標上平均提升了約10%，這是因為孤立森林與子空間異常值檢測密切相關，不同的分支對應于數據的不同局部子空間，由于其他算法是隨機選擇的屬性，所以這種子空間具有隨機性，而HiForest對利用了統計檢驗的方法篩選出了屬性之間相關度高的子空間，因此在構建隔離樹時分支有更明顯的差異，能夠有效檢測出異常，相反地，如果在構建隔離樹時樣本全是正常點，會降低離群值檢測的效率，并且直觀上來講，相關子空間的選擇會比隨機的選擇更有效。但是在speech數據集上的表現無論在任何算法中都處于較低的值，這是因為數據集本身在維度分布上的正常值和異常值很相近，使得異常值難以區分，無法充分利用檢測器的優勢得到更好的性能。

圖4、5展示了不同維度區間上數據集的ROC曲線。從圖4可以觀察到在數據集optdigits上，HiForest的ROC曲線相比于其他算法更貼近左上角，曲線面積更接近于1，比其他算法高很多，這是因為數據集optdigits維度高達64維，數據對象之間越來越接近，距離出現同質化，而LOF、ABOD和CBLOF這種基于相似度度量算法的性能會下降，而在wbc數據集上與其他數據集的ROC曲線比較相近，但是仍然優于其他算法，這是因為wbc數據集規模較小，異常值的分布很稀疏，所以易于劃分。

僅采用AUC作為性能指標并不全面，為了精確地評估模型的效果，采用查準率、召回率和F1值作為評估指標，其中F1值是對查準率和召回率的綜合評估指標，其值通常接近于較低的那個值，并且越高代表模型的分類效果越好。實驗選用了基于iForest改進的SCiForest和RS-EIF、最新的異常檢測算法COPOD以及經典的LOF算法作為對比參照，對比結果如表4所示。通過比較表4記錄的實驗結果不難看出，HiForest在平均查準率上具有最高的值，均值在0.692 0，比次高的iForest和排在第三的RS-EIF均高出了約10個百分點，相比于SCiFo-rest、COPOD和LOF平均提升了約20個百分點。對于召回率略高于原算法，說明本文算法將正常值識別為異常值的情況較少。但是對于其他算法而言，召回率均有提升，具體提升了約42.5%，這是因為SCiForest算法是為了檢測局部聚類異常而改進的算法，所以在面對有聚類異常的數據集表現可能會更好。類似地，在LOF算法上的效果不好的原因可能是它需要檢測的數據集需要有明顯的密度差異。最后，本文算法的F1均值在0.684 5，排在第一，相比于原算法高出了7.95%，進一步說明了本文算法的有效性。

4.4 算法時間開銷對比

在本節中為了檢驗算法的時間開銷，將本文算法分別與其他五種方法進行比較，時間結果由各算法在不同數據集上運行十次綜合取得的時間，圖6展現了HiForest、iForest、SCiForest、RS-EIF、COPOD和LOF對不同數據集的時間開銷。通過圖6可以觀察到在規模較小的wbc數據集中各算法的運行時間處于一個量級，并無明顯的差異。而隨著數據規模的增大，iForest的優勢更為明顯，這是因為使用隔離的方法避免了距離的計算從而減少了時間開銷；LOF的時間開銷較大，是因為它與基于距離的算法一樣，需要對最近鄰進行計算，所以時間性能很大程度上取決于近鄰搜索算法的效率；COPOD的時間開銷一直很穩定，處于一個較低的值，同樣也是因為COPOD不需要進行樣本點之間的距離計算，所以它的速度較快；SCiFo-rest的時間開銷相比其余四個算法更多是因為在構造隔離樹的每個節點時，需要隨機生成多個超平面，并且計算它們的Sdgain值，排序后選擇最大的作為最優超平面，所以對于SCiForest的時間復雜度是顯而易見地高于iForest。同為使用了隨機超平面進行空間切割的RS-EIF的速度很快，這是因為它只需要計算一次隨機斜率向量與樣本點的點乘。最后，本文算法相比于iForest在訓練階段需要對子空間進行選擇，在選擇階段的時間復雜度為O（M×N），所以時間復雜度也有所上升，但是總體上也是呈線性上升的趨勢。雖然在時間上比iForest略慢，但是在性能上有所提升。

5 結束語

本文結合孤立森林和高對比度子空間算法，提出了一種異常檢測算法HiForest。該算法針對孤立森林在構建隔離樹時隨機性造成的檢測能力不足的問題，利用統計檢驗的方法發現具有高對比度值的子空間，并在子空間中進行隔離樹的構建，在篩選過后的子空間中屬性之間的相關性更高，從而降低了iForest在訓練過程中過于隨機性的問題，通過多種實驗驗證并與ABOD、LOF、PCA、CBLOF、iForest和SCiForest算法進行對比，結果表明，HiForest算法在ODDS數據集上取得了更好的異常檢測效果。隨著時代的發展，多數領域的數據集通常是海量高維的，而該算法在維度稍高的數據集上有著顯著的優勢，具有一定的參考價值。在未來的工作中，計劃將該算法應用到保險欺詐問題中，同時面對不同數據分布特性對算法進行擴展，使其能夠解決更多實際問題。但由于HiForest在子空間的搜索上增加了時間開銷，下一步的工作可以考慮采用分布式計算來提升算法的執行效率。同時，檢測出來的離群點缺乏解釋性，如何解釋檢測出來的離群點就是異常也是以后需要研究的方向。

參考文獻：

［1］Hawkins D M. Identification of outliers［M］. London： Chapman and Hall，1980.

［2］Swarnamalya M，Raghavendra C K，Seshamalini M. Hyper parameter optimization technique for network intrusion detection system using machine learning algorithms［M］// Skala V，Singh T P，Choudhury T，et al. Machine Intelligence and Data Science Applications. Berlin： Springer，2022： 441-456.

［3］Madhurya M J，Gururaj H L，Soundarya B C，et al. Exploratory analysis of credit card fraud detection using machine learning techniques［J］. Global Trans Proceedings，2022，3（1）： 31-37.

［4］Hansen S，Gautam S，Jenssen R，et al. Anomaly detection-inspired few-shot medical image segmentation through self-supervision with supervoxels［J］. Medical Image Analysis，2022，78： 102385.

［5］Wang Hongzhi，Jaward B M，Hammad M. Progress in outlier detection techniques： a survey［J］. IEEE Access，2019，7： 107964-108000.

［6］Goldstein M，Uchida S. A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data［J］. PLoS One，2016，11（4）： e0152173.

［7］Radovanovic＇ M，Nanopoulos A，Ivanovic＇ M. Reverse nearest neighbors in unsupervised distance-based outlier detection［J］. IEEE Trans on Knowledge and Data Engineering，2014，27（5）： 1369-1382.

［8］Kriegel H P，Krger P，Schubert E，et al. LoOP： local outlier probabilities［C］// Proc of the 18th ACM Conference on Information and Knowledge Management. 2009： 1649-1652.

［9］He Zengyou，Xu Xiaofei，Deng Shengchun. Discovering cluster-based local outliers［J］. Pattern Recognition Letters，2003，24（9-10）：1641-1650.

［10］Barbariol T，Chiara F D，Marcato D，et al. A review of tree-based approaches for anomaly detection［M］// Tran K P. Control Charts and Machine Learning for Anomaly Detection in Manufacturing. Cham： Springer，2022： 149-185.

［11］Liu F T，Ting Kaiming，Zhou Zhihua. Isolation forest［C］// Proc of the 8th IEEE International Conference on Data Mining.2008：413-422.

［12］Liu F T，Ting Kaiming，Zhou Zhihua. On detecting clustered anomalies using SCiForest［C］// Proc of European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin： Springer-Verlag，2010： 274-290.

［13］Hariri S，Kind M C，Brunner R J. Extended isolation forest［J］. IEEE Trans on Knowledge and Data Engineering，2019，33（4）： 1479-1489.

［14］謝雨，蔣瑜，龍超奇. 基于隨機子空間的擴展隔離林算法［J］. 計算機應用，2021，41（6）：1679-1685. （Xie Yu，Jiang Yu，Long Chaoqi. Extended isolation forest algorithm based on random subspace［J］. Journal of Computer Applications，2021，41（6）：1679-1685.）

［15］Breiman L. Random forests［J］. Machine Learning，2001，45（1）： 5-32.

［16］Liu Zhen，Liu Xin，Ma Jin，et al. An optimized computational framework for isolation forest［J］. Mathematical Problems in Enginee-ring，2018，2018： article ID 2318763.

［17］Liao Liefa，Luo Bin. Entropy isolation forest based on dimension entropy for anomaly detection［C］// Peng Hu，Deng Changshou，Wu Zhijian，et al. International Symposium on Intelligence Computation and Applications. Berlin： Springer，2018： 365-376.

［18］Keller F，Muller E，Bohm K. HiCS： high contrast subspaces for density-based outlier ranking ［C］// Proc of the 28th International Confe-rence on Data Engineering. Piscataway，NJ： IEEE Press，2012： 1037-1048.

［19］Kriegel H P，Schubert M，Zimek A. Angle-based outlier detection in high-dimensional data［C］// Proc of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008： 444-452.

［20］Breunig M M，Kriegel H P，Ng R T，et al. LOF： identifying density-based local outliers［J］. ACM SIGMOD Record，2000，29（2）： 93-104.

［21］Abdi H，Williams L J. Principal component analysis［J］. Wiley Interdisciplinary Reviews： Computational Statistics，2010，2（4）： 433-459.

［22］Duan Lian，Xu Lida，Liu Ying，et al. Cluster-based outlier detection［J］. Annals of Operations Research，2009，168（1）： 151-168.

［23］Zheng Li，Zhao Yue，Botta N，et al. COPOD： copula-based outlier detection［C］// Proc of IEEE International Conference on Data Mining. 2020： 1118-1123.

［24］Zhao Yue，Nasrullah Z，Li Zheng. PyOD： a Python toolbox for scalable outlier detection［EB/OL］. （2019-06-10）. https：//arxiv.org/abs/1901. 01588.

［25］Grigelionis B. Student’s t-distribution and related stochastic processes ［M］. Berlin： Springer，2013.

收稿日期：2022-06-08；修回日期：2022-08-10

作者簡介：周杭（1997-），女，四川成都人，碩士研究生，主要研究方向為數據挖掘、智能計算與異常檢測；蔣瑜（1980-），男（通信作者），四川鄰水人，副教授，碩士，主要研究方向為入侵檢測、粗糙集、數據挖掘與智能計算（763711665@qq.com）.