基于專家反饋的廣義孤立森林異常檢測算法

祝誠勇 黃鵬翔 李理敏

摘 要：針對孤立森林算法無法檢測與軸平行的局部異常點以及樹結構無法動態更新等問題，提出了一種基于專家反饋的廣義孤立森林異常檢測算法。首先，將數據映射在單位特征向量上，從映射區域內選擇分割點劃分數據空間，重復此操作構造出一棵廣義孤立樹；然后，給廣義孤立森林中每棵樹的葉節點引入權重，綜合考慮子空間劃分次數和子空間內樣本數量對數據異常分數的影響；最后，計算每個數據的加權異常分數，并選擇異常分數較大的數據交由專家進行批量標注，算法根據標注結果更新葉節點權重，從而實現樹結構的動態調整。實驗結果表明，該算法在7個數據集中專家標注真實異常的數量優于其他同類樹結構算法，并在12個數據集中平均準確率比孤立森林、擴展孤立森林和廣義孤立森林分別提升了38.952%、49.144%和49.144%。

關鍵詞：異常檢測； 孤立森林； 動態更新； 專家反饋

中圖分類號：TP393?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-014-0088-06

doi：10.19734/j.issn.1001-3695.2023.05.0182

Generalized isolation forest anomaly detection algorithm based on expert feedback

Abstract：Aiming at the problem that the isolation forest algorithm cannot detect local anomalies parallel to the axes and the tree structure is unable to be dynamically updated， this paper proposed a generalized isolation forest anomaly detection algorithm based on expert feedback. Firstly， it projected the data to the sampled normal unit vector， and selected a split point from the mapping area to divide the data space， then repeated these operations until constructed a generalized isolation tree. Secondly， it introduced the weights of the leaf nodes of each tree in the generalized isolation forest， which comprehensively considered the influence of the number of subspace partitions and the sample size in the subspace on anomaly scores. Finally， it calculated the weighted anomaly scores of each data， and submitted data with high anomaly scores to expert for batch labeling， then the algorithm updated the weights of the leaf nodes according to the labeling results， so as to dynamically adjust the structure of the generalized isolation tree. The experimental results show that the numbers of real abnormal data are marked by expert in 7 datasets are better than that of the other tree-based anomaly detection algorithms， and the average precision in 12 datasets are 38.952%， 49.144% and 49.144% higher than isolation forest， extended isolation forest， generalized isolation forest， respectively.

Key words：anomaly detection; isolation forest; dynamic update; expert feedback

0 引言

異常檢測（anomaly detection，AD），又被稱為新奇點檢測（novelty detection，ND）或離群點檢測（outlier detection，OD），可以識別出與正常數據不同的數據，或與預期行為差異大的數據［1］，是數據挖掘領域的一個重要研究方向，在工業［2］、金融［3］、網絡［4］等諸多領域中都有廣泛的應用。

目前，異常檢測方法根據數據標簽的使用情況可以分為監督、半監督、無監督三類［5，6］。標簽數據的獲取和標注需要大量的時間和精力，而且異常行為可能會隨時間發生動態變化，難以獲得全面且準確的帶有標簽的數據集［7］。因此，研究無監督異常檢測方法具有非常重要的學術價值與實際意義。孤立森林（isolation forest，IF）是一種適用于連續數據的無監督異常檢測方法，具有計算復雜度低、魯棒性好、可解釋性強等優點，在高維和海量數據處理中得到了廣泛應用［8，9］。然而IF存在決策邊界與特征軸平行的問題，在密集數據中易產生重疊效應［10］，導致檢測精度降低。為此，文獻［11］提出了一種擴展孤立森林（extended isolation forest，EIF）異常檢測算法，使用隨機斜率的超平面對數據空間進行劃分，解決了IF中決策邊界與軸平行的問題，提升了算法檢測性能，但是EIF每棵樹在分支的過程中，可能會存在空分支問題。文獻［12］提出了一種廣義孤立森林（generalized isolation forest，GIF）異常檢測算法，通過將數據映射在隨機單位特征向量上，從映射區域中選取閾值劃分數據空間，優化了EIF可能存在的空分支問題。然而，上述三種基于樹結構的異常檢測算法都是采用隔離離群點的思路進行樹的構建和異常檢測，存在一定概率的漏警問題［13］。文獻［14］通過引入專家反饋（expert feedback，EF）策略，在每次循環過程中，將IF中最有可能是異常的數據交由專家進行標注，算法再根據標注結果進行動態更新，通過這種方式解決了IF中存在的漏警問題。但是該方法仍然存在以下問題：a）以IF為基礎，存在決策邊界與特征軸平行的問題；b）專家每次只標注最具異?？赡苄缘囊粋€數據，增加了算法迭代優化的次數；c）葉節點權重更新時，僅考慮了數據從樹的根節點到葉節點的過程中經歷邊的個數，未涉及與數據同在一個葉節點中樣本數量的影響。

基于以上分析，本文提出了一種基于專家反饋的廣義孤立森林（EF-GIF）異常檢測算法，其主要創新之處體現在以下幾個方面：a）樹的分支策略，將數據映射在單位特征向量上，從映射區域中選取閾值來劃分數據空間，解決了IF中決策邊界與特征軸平行的問題；b）異常數據標注，算法將異?？赡苄暂^大的多個數據提交給專家進行批量標注，有效地減少了權重迭代更新的次數；c）葉節點權重計算，綜合考慮了數據從樹的根節點到葉節點所經過邊的個數和同在一個葉節點中樣本數量的影響。實驗結果表明，本文算法在專家標注真實異常數據數量方面優于IF、EIF和GIF算法，同時在檢測精度方面相比同類算法也取得了不同程度的提升。

1 相關工作

1.1 孤立森林算法原理

孤立森林是集成學習算法中一類典型的無監督異常檢測算法，它將異常定義為“容易被孤立的離群點”，即分布稀疏且遠離高密度數據群體的點［15］。其算法思想為：隨機選擇一個特征超平面，不斷地對數據空間劃分子空間，直至每個子空間只有一個數據點或達到限定深度。在劃分過程中，越是離群的數據點越早被劃分開來，故其平均深度也越小。數據樣本x的異常值分數計算公式如下：

其中：h（x）表示樣本x的路徑長度，其計算公式為

h（x）=e+c（size）（2）

其中：e表示樣本x從樹的根節點到葉節點所經歷邊的數目;size表示與x同在一個葉節點的樣本數目；E［h（x）］表示樣本x在所有樹中h（x）的均值；c（φ）是給定φ個數據樣本時，樹的平均路徑長度，用來對E［h（x）］作歸一化處理，其計算公式如下：

其中：H（φ－1）=ln（φ－1）+0.5772。從式（1）可以看出，數據x在每棵樹中的平均路徑E［h（x）］越短，異常分數值score（x）越接近1，表明其越可能是異常點；反之，異常分數值score（x）越接近0，表明其越可能是正常點。

1.2 分支策略

孤立森林算法的關鍵在于如何劃分數據空間，即樹的分支策略。假設數據有d1和d2兩個特征，圖1給出了IF、EIF和GIF三種算法的分支策略。如圖1（a）所示，IF從d1和d2兩個特征中隨機選取一個特征，然后在該特征的值域范圍內確定左右分支的決策邊界。IF在分支過程中存在軸平行問題，即在單一特征的決策過程中，決策邊界與特征軸平行。這會導致在密集的數據中產生重疊效應［10］，引起異常檢測精度降低。EIF考慮了d1和d2兩個特征之間的相關性，其隨機斜率的超平面由單位特征向量β和截距點PE確定，如圖1（b）所示。由于PE是從包絡數據樣本的超立方體中采樣（粉色陰影區域，參見電子版），導致EIF在劃分左右分支的過程中，可能會存在空分支問題。GIF考慮了d1和d2兩個特征之間的相關性，其決策邊界由單位特征向量β和截距點PG確定，如圖1（c）所示。PG是數據樣本在β的映射區域中選取的（綠色虛線），這有效地解決了EIF可能存在空分支的問題。

為進一步說明不同分支策略對孤立森林算法的影響，利用圖2的合成數據對三種算法性能進行比較，訓練集是以（0，0）為中心，服從高斯分布的數據，測試集是不同半徑的圓環數據，具體測試結果如圖3所示。從圖3（a）可以看出，IF在密集的數據中會產生重疊效應，存在與軸平行的局部異常點無法檢測的問題，導致檢測效果下降。同時，對比圖3（b）和（c）可以看出，GIF的異常分數比EIF更接近訓練數據的真實分布情況。圖4進一步給出了三種算法對不同半徑測試數據的異常分數標準差。從圖中可以看出，總體上GIF的異常分數標準差小于IF和EIF。

1.3 漏警問題

漏警率是評價異常檢測算法的一個重要指標。孤立森林算法將數據中分布稀疏且遠離高密度數據群體的點判斷為異常點，但是當高密度正常數據群體呈現重尾分布時，易將落于尾部區域中的異常數據判斷為正常點，即產生了漏警現象［16］。以圖5（a）中分布的數據為例，分別利用IF、EIF、GIF三種算法對其進行數據異常檢測，結果分別如圖5（b）～（d）所示。從圖中可以看出，三種孤立森林算法將靠近高密度正常數據的部分邊緣異常數據誤檢為正常數據，導致發生了漏警問題。

2 基于專家反饋的廣義孤立森林算法

2.1 專家反饋原理

在監督學習中，存在樣本難以大量獲取且標注成本高的問題。不同樣本對于特定任務的重要程度是不同的，所以帶來的模型性能提升也并不完全相同。專家反饋是一種從樣本角度提高檢測效率的方案，其基本思路是通過專家選擇性地標注少量的高質量樣本，從而訓練出表現較好的模型，如圖6所示［14］。

本文通過引入專家反饋過程，試圖在有限的反饋標注次數中，選擇最有價值的樣本交給專家進行標注并將其加入到有標簽數據集中繼續對模型進行訓練，從而實現任務模型的在線更新。原始數據根據專家標注，分成無標簽數據DO、專家標注的異常數據DA和專家標注的正常數據DN。

2.2 廣義孤立森林構造

2.3 專家反饋的廣義孤立森林

傳統的孤立森林算法在模型訓練完成后，在后續異常檢測過程中結構保持固定不變，易出現模型無法完全適應實際動態場景的現象，還可能存在嚴重的誤報與漏報問題［14］。為此，本文給GIF中每個葉節點添加一個權重，在異常檢測過程中利用專家反饋信息自適應地調整葉節點的權重，從而實現GIF中樹結構的動態更新，如圖7所示。

數據x在帶權重的廣義孤立森林中的加權路徑異常分數可以表示為

其中：h（x）是由數據x在各棵樹上的路徑長度組成的，當m列中只有t列非零的向量，m為廣義孤立森林中葉節點總數，h（x）包含了數據從樹的根節點到葉節點所經過邊的個數以及同在一個葉節點中樣本數量信息;w=［w1，…，wm］1×m表示廣義孤立森林中葉節點對應權重組成的向量。

在初始時刻，將w的值w（0）=[1/t，…，1/t］，WScore（X，w（0））將計算所有數據樣本的加權路徑異常分數，然后按照異常分數降序排列，假設位于異常百分位τ上的數據為x（0）τ，其加權路徑異常分數為s（0）τ=WScore（x（0）τ，w（0））。傳統孤立森林算法將s（0）τ作為閾值來判斷數據是否異常，即若數據xi的加權異常分數WScore（xi，w（0））

為了解決上述問題，本文在GIF中引入了專家標注反饋的過程。同時，為了減少權重迭代更新的次數，每次將異常分數值位于前q的多個數據同時交由專家進行批量標注。根據已標注數據xj的加權異常分數WScore（xj，w）、異常分數檢測閾值s（b－q）τ和真實結果標簽yj三者之間的關系定義如下損失函數：

其中：s（b－q）τ由w=w（b－q）時刻計算得到，以WScore（xj，w）與s（b－q）τ之間的距離作為損失：s（b－q）τ－WScore（xj，w）表示漏警導致的損失;WScore（xj，w）－s（b－q）τ表示虛警導致的損失。

通過最小化上述損失函數來更新GIF中的葉節點權重，從而降低系統誤報與漏報概率。定義目標函數為

其中：|·|表示標注數據集中的數據個數;超參數CA是權衡DA中數據漏警損失和DN中數據虛警損失的系數，通常CA>>1，這使得算法更注重于優化漏警問題。同時，為了避免w（b）過擬合，在目標函數中添加了L2正則化項‖w－w（b－q）‖2，λ是權衡誤報和漏報損失與正則化項的超參數。采用自適應梯度優化算法［17］對式（6）進行求解，即可得到動態更新后的w（b），使得DA中數據異常分數高于s（b－q）τ，DN中數據異常分數低于s（b－q）τ。

算法3給出了專家批量標注與葉節點權重更新的過程。

算法3 Rweight（X，B，t，q）

輸入：X為輸入數據，B為標注數據次數，t為樹的棵數，q為批量標注數。

輸出：w。

b=0

DA=DN=

權重初始化w=w（b）=［1/t，…，1/t］

while b

數據集的異常分數WScore（X，w）

異常分數值位于前q的未標注數據［x1t，…，xqt］

for i=1 to q do

if xit is anomaly

DA=DA∪xit

else

DN=DN∪xit

end if

end for

b=b+q

最小化損失以更新權重w=w（b）

end while

return w

使用如圖8（a）所示的toy2數據集［14］，驗證每次專家反饋后本文EF-GIF的檢測效果。如圖8（b）所示，隨著每次專家反饋后葉節點權重的更新，EF-GIF異常檢測效果明顯提升。

為更加直觀地說明圖8（b）異常檢測效果提升的過程，對toy2數據集進行可視化。圖9給出了當專家標注數據次數從0～60逐漸增加時，其異常分數熱力圖變化的過程，圖中紅色區域為異常分數較高的區域，藍色區域為異常分數較低的區域。

從圖9（a）～（d）的變化可以看出，隨著專家反饋標注次數的不斷增加，toy2數據集異常分數熱力圖的分布逐漸接近圖8（a）的數據真實分布。

3 實驗分析

3.1 實驗環境和數據集

本文的主要實驗環境參數為：Intel i7-10700 2.9 GHz CPU，8 GB內存，Windows 10 64位操作系統，算法采用Python 3.6實現。

采用來源于文獻［12，18］中的12個公開數據集，具體如表2所示。mammography、shuttle數據集，主要考慮多樣本數對于異常檢測算法的影響；cardio、PenGlobal、letter、breast cancer、annthyroid和ionosphere數據集，主要考慮高特征維度對于異常檢測算法的影響；ALOI數據集，綜合考慮多樣本數和高特征維度對于異常檢測算法的影響。

3.2 實驗參數設置

本文參考文獻［14］的實驗參數設置，表3給出了各參數的具體描述及取值，通過100次仿真測試得到實驗結果。

3.3 實驗結果分析

為體現每次權重更新后異常檢測算法發現異常數據的能力，圖10給出了專家標注異常數據數量的實驗結果。從圖中可以看出，EF-GIF在breast cancer、ionosphere和yeast這3個數據集中的性能與IF、EIF、GIF相似，在PenGlobal、letter、annthyroid、abalone、cardiotocograph、mammography、ALOI這7個數據集中的性能優于其他三種未改進的算法，體現出EF-GIF在發現數據中真實異常能力方面的提升。上述結果的主要原因為：如圖10所示，首先GIF的分支策略優于IF和EIF；其次EF-GIF相比GIF引入了專家反饋環節，通過式（6）中的葉節點權重更新，最小化檢測過程中誤報與漏報問題和正則化項構成的損失，最終提升了算法的檢測效果。

表4進一步給出了四種算法在PenGlobal數據集上專家標注真實異常數據數量的均值。從表中可以看出，EF-GIF發現數據中真實異常數據的數量隨反饋標注次數的增加而明顯提升，尤其是在專家標注次數達到60時，EF-GIF相比IF、EIF和GIF分別有54.882%、49.136%和57.194%的提升。從表中四種算法在真實異常數據數量上的差異可知，未引入專家反饋孤立森林算法中存在漏警問題的現象較為嚴重。

為了更進一步說明本文算法在未知數據集上的檢測效果，將數據集以7∶3的比例劃分為訓練集和測試集，取異常檢測中常用的受試工作者特征曲線下的面積（area under curve，AUC）和平均準確率（average precision，AP）作為評價指標，實驗結果如表5所示。從表5可以看出：在AUC方面，EF-GIF在12個數據集中有11個優于IF、EIF和GIF，平均分別提升了2.791%、1.925%和2.667%；在AP方面，EF-GIF在12個數據集中有11個優于IF、EIF和GIF，平均分別提升了38.952%、49.144%和49.144%。這是因為本文EF-GIF算法考慮了數據從根節點到葉節點所經過邊的個數和最終落在葉節點上數據的數量信息，保證了數據異常分數的多樣性，使專家在循環反饋過程中能夠有效區分漏警數據。

綜上所述，在發現數據中真實異常數據數量和檢測準確率方面，EF-GIF相較于其他樹異常檢測算法有明顯提升，通過專家批量標注和優化葉節點權重，使樹結構和檢測閾值能夠根據實際場景進行自適應動態調整，提高了算法的泛化能力。

4 結束語

本文提出了一種基于專家反饋的廣義孤立森林異常檢測算法，其分支策略考慮到數據特征之間的相關性，將數據先映射在單位特征向量上，然后通過從映射區域中隨機采樣閾值分割左右分支的方式，優化了IF中決策邊界與特征軸平行問題。同時，在專家反饋過程中，采用批量標注異?？赡苄暂^大的數據策略，有效減少了算法更新迭代的計算次數。另外，在葉節點權重更新方面，綜合考慮了數據從根節點到葉節點所經過邊的數量和最終落在葉節點上的數據數量對漏警問題的影響。實驗結果表明，EF-GIF在PenGlobal、letter、annthyroid、abalone、cardiotocograph、mammography、ALOI數據集上，真實異常數據的數量優于IF、EIF和GIF算法；其次在檢測準確率方面，分別有38.952%、49.144%和49.144%的提升。

后續將進一步分析不同標注策略和優化方法對異常檢測性能的影響，并探究已標注數據和標簽之間的關系，篩選關鍵特征，提升專家標注效率。

參考文獻：

[1]Ruff L， Kauffmann J R， Vandermeulen R A， et al. A unifying review of deep and shallow anomaly detection［J］.Proc of the IEEE，2021，109（5）：756-795.

［2]Zhou Xiaokang， Hu Yiyong， Liang Wei， et al. Variational LSTM enhanced anomaly detection for industrial big data［J］.IEEE Trans on Industrial Informatics，2020，17（5）：3469-3477.

［3]Li Tie， Kou Gang， Peng Yi， et al. An integrated cluster detection， optimization， and interpretation approach for financial data［J］.IEEE Trans on Cybernetics，2021，52（12）：13848-13861.

［4]Injadat M N， Moubayed A， Nassif A B， et al. Multi-stage optimized machine learning framework for network intrusion detection［J］.IEEE Trans on Network and Service Management，2020，18（2）：1803-1816.

［5]Pang Guansong， Shen Chunhua， Cao Longbing， et al. Deep learning for anomaly detection：a review［J］.ACM Computing Surveys，2021，54（2）：1-38.

［6]Schmidl S， Wenig P， Papenbrock T. Anomaly detection in time series： a comprehensive evaluation［J］.Proc of the VLDB Endowment，2022，15（9）：1779-1797.

［7]卓琳，趙厚宇，詹思延.異常檢測方法及其應用綜述［J］.計算機應用研究，2020，37（S1）：9-15.（Zhuo Lin， Zhao Houyu， Zhan Siyan. A survey of anomaly detection methods and their applications［J］.Application Research of Computers，2020，37（S1）：9-15.）

［8]唐立，郝鵬，任沛閣，等.基于改進孤立森林算法的無人機異常行??? 為檢測［J］.航空學報，2022，43（8）：584-593.（Tang Li， Hao Peng， Ren Peige， et al. UAV abnormal behavior detection based on improved iForest algorithm［J］.Acta Aeronautica et Astronautica Sinica，2022，43（8）：584-593.）

［9]杭菲璐，郭威，陳何雄，等.基于iForest和LOF的流量異常檢測［J］.計算機應用研究，2022，39（10）：3119-3123.（Hang Feilu， Guo Wei， Chen Hexiong， et al. Network traffic anomaly detection based on iForest and LOF［J］.Application Research of Compu-ters，2022，39（10）：3119-3123.）

［10]楊曉暉，張圣昌.基于多粒度級聯孤立森林算法的異常檢測模型［J］.通信學報，2019，40（8）：133-142.（Yang Xiaohui， Zhang Shengchang. Anomaly detection model based on multi-grained cascade isolation forest algorithm［J］.Journal on Communications，2019，40（8）：133-142.）

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

［12]Lesouple J， Baudoin C， Spigai M， et al. Generalized isolation forest for anomaly detection［J］.Pattern Recognition Letters，2021，149：109-119.

［13]Li Changgen， Guo Liang， Gao Hongli， et al. Similarity-measured isolation forest：anomaly detection method for machine monitoring data［J］.IEEE Trans on Instrumentation and Measurement，2021，70：1-12.

［14]Das S， Wong W K， Fern A， et al. Incorporating feedback into tree-based anomaly detection［EB/OL］.［2023-05-07］.https：//arxiv.org/pdf/1708.09441.pdf.

［15]Liu F T， Ting K M， Zhou Zhihua.Isolation forest［C］//Proc of the 8th IEEE International Conference on Data Mining.Piscataway，NJ：IEEE Press，2008：413-422.

［16]Das S， Wong W K， Dietterich T， et al. Discovering anomalies by incorporating feedback from an expert［J］.ACM Trans on Knowledge Discovery from Data，2020，14（4）：1-32.

［17]Soydaner D. A comparison of optimization algorithms for deep learning［J］.International Journal of Pattern Recognition and Artificial Intelligence，2020，34（13）：2052013.

［18]Lesouple J， Tourneret J Y. Incorporating user feedback into one-class support vector machines for anomaly detection［C］//Proc of the 28th European Signal Processing Conference.Piscataway，NJ：IEEE Press，2021：1608-1612.