基于孤立森林的多離群點數據檢測算法設計

摘" 要： 精準找出異常離群數據有利于確保大規模數據在應用中的精確度，為此，設計了基于孤立森林的多離群點數據檢測算法。首先，采用近似符號聚合算法處理大規模數據的多條件時間序列，再通過計算歐氏距離分析多條件時間序列的相似度，而后采用加權調整法調整相似曲線，剔除其中的異常數據，完成對大規模數據的清洗；利用清洗后的數據構建孤立樹形成孤立森林，將待檢測數據作為孤立森林的輸入量，通過計算數據樣本點到每棵樹根節點的距離，實現對離群點數據的檢測。實驗結果表明：該算法能夠有效地檢測出離群點數據，在針對大規模數據離群點的檢測時，檢測結果精確度較高。

關鍵詞： 孤立樹； 孤立森林； 離群點； 大規模數據； 異常檢測； 相似度測量； 數據清洗； 時間序列

中圖分類號： TN99?34" " " " " " " " " " " " " 文獻標識碼： A" " " " " " " " " " " " " "文章編號： 1004?373X（2024）05?0139?04

Design of multi?outlier data detection algorithm based on isolation forest

LI Jiajun

（School of Data Science， Guangzhou Huashang College， Guangzhou 511399， China）

Abstract： Accurately identifying outlier data is beneficial for ensuring the accuracy of large?scale data in applications. Therefore， a multi?outlier data detection algorithm based on isolation forests has been designed. The approximate symbol aggregation algorithm is used to process the multi conditional time series of large?scale data. The similarity of the multi conditional time series is analyzed by calculating the Euclidean distance. The weighted adjustment method is used to adjust the similarity curve， eliminate abnormal data， and complete the cleaning of large?scale modular data. The cleaned data is used to construct an isolation tree and form an isolation forest. The data under detection is used as the input for the isolation forest. By calculating the distance between the data sample points and each node of the tree roots， outlier data detection is achieved. Experimental results have shown that the algorithm can effectively detect outlier data， and its detection accuracy is high when detecting outliers in large?scale data.

Keywords： isolation tree; isolation forest; outlier; large?scale data; anomaly detection; similarity measurement; data cleansing; time series

0" 引" 言

離群點數據通常稱為異常點數據，其存在于某個數據集中，但不完全符合該數據集的特征規律，視為一個不合群的數據點，該數據點就是離群點。通俗的講，在數據集中，離群點是指與其他樣本明顯不同或遠離主要樣本分布的數據點。故而，可以將多離群點數據視為是若干個不符合原規律的數據點[1?2]。

目前，離群點數據檢測方法的發展從傳統的統計學方法逐漸演變為注重距離、密度、聚類和機器學習等多種技術手段的綜合應用。這些方法在各種領域中被廣泛應用，如金融欺詐檢測、網絡入侵檢測、異常檢測、工業監控等。例如：文獻[3]中通過質心投影波動變化檢測離群點，利用離群點和內部點質心投影變化差異，考量異常數據的離群程度，最終完成離群點檢測。但是使用該方法檢測前未處理無效和缺失的數據，影響了檢測精度。文獻[4]提出利用EWT方法提取時間序列運行特征，消除序列運行特征后，再通過LOF方法在若干數據點中求得異常點，最終確定序列離群點。但該方法在提取時間序列時，缺少對原始數據集中缺失值的補充，影響了原始數據集的完整性及監測精確度。文獻[5]中利用NSGA?Ⅱ優化算法求解數據集中每個數據的最優Eps，然后利用基于Eps的LOF算法完成離群點檢測。但是在實際應用中發現，該方法存在參數Eps不確定性的問題，影響檢測結果的精確度。

孤立森林（Isolation Forest）算法主要針對具有連續性時間、結構復雜的數據中的異常點實施檢測，無需監督，即可進行模型訓練，尤其適用于處理大規模數據問題。在原始數據集中隨機采集若干次樣本數據，依據其特征劃分形成二叉樹，也就是孤立樹（Isolation Tree），最終構建成i Forest。

基于上述分析，本文設計了基于孤立森林的多離群點數據檢測算法，以期能夠提高異常點檢測的精準度。

1" 多離群點檢測方法設計

孤立森林是一種常見的異常檢測方法，適用于連續、繁雜的數據集檢測[6]。該算法基于一種稱為“孤立性”的概念，該概念指出異常數據點相對來說更容易被孤立在數據集中。算法的主要思想是通過構建一棵隨機的二叉搜索樹，將正常樣本和異常樣本分離開來。

具體來說，孤立森林通過以下步驟進行：

1） 隨機選擇一個特征和對應的閾值，將數據集劃分為兩個子集。

2） 重復步驟1），直到每個子集中的數據點都被單獨分割或達到了預定的樹的深度。

3） 通過路徑長度評估數據點的異常程度。路徑長度是沿著樹從根節點到達數據點所經過的分割次數。異常點通常具有較短的路徑長度，因為它們在分割時更容易被孤立。

基于孤立森林的多離群點數據檢測流程如圖1所示。

數據清洗完成后，基于孤立森林檢測算法，隨機拆分大規模數據集合，直至整個數據集全部成為單獨的一個數據點。在隨機拆分數據集的情況下，離群點路徑較短是被隨機拆分數據集的基本特征，因此，數據點異常的判斷就取決于i Forest中樣本點到達根節點的距離長度。

1.1" 數據清洗處理

利用近似符號聚合算法對原始大規模數據進行處理，再采用相似度測量方法，經相似曲線擬合后，剔除偏差、缺失、繁冗等異常數據，形成清洗后的大規模數據。

1.1.1" 近似符號聚合算法

近似符號聚合算法（Symbolic Aggregation Approximation， SAX）是一種用分散式字符序列描述時間序列的方法，該符號也可默認為距離向量[7]。采用近似符號聚合算法對原始大規模數據進行多條件時間序列分散和符號化轉換，減小原始大規模數據中的缺失和異常數據因部分數據變動的波動，再獲取較小規模字符序列，大大提升多條件時間序列數據的聚合程度，有助于相似度對比。

近似符號聚合算法使多條件時間序列的維度由[n]下落至[N]，由近似符號聚合算法轉換成數據形式的一個字符串。[X=x1，x2，…，xn]表示原始多條件時間序列集。對每個多條件時間序列統一處理，令0代表平均值，1代表基準差，[C=c1，c2，…，cn]表示統一后的數據多條件時間序列，[μ]、[δ]分別代表原始時間序列的平均值和基準差。用公式（1）可描述[C]的第[i]個元素為：

[Ci=xiδ-μX， i=1，2，…，n] （1）

針對多條件序列[C]采取維度下落，使原始多條件時間序列維度[n]下落至[N]。用[C=C1，C2，…，CN]表示下落后的[N]維多條件時間序列。用[1t]表示各分段的間隔長度，[t=nN]表示各分段的間隔壓縮率，[Ci]表示原始時間序列向量切分[N]個片段中第[i]片段中的均值，其可用公式（2）表示：

[Ci=j=ti-1ticjt] （2）

1.1.2" 相似度計算

歐氏距離是最普遍、較簡單的相似度測量指標，用于衡量兩個點在多維空間中的距離[8]。它要求對比序列應滿足長度和點的標準，并匹配出序列間的不同，對比的序列具有相同的維度，并且每個維度上的數值是可比較的。近似符號聚合算法采用符號描述式的相似度易被快速獲取，如果近似符號聚合算法符號上的兩個原始數據距離較遠，則兩者間的相似度較小[9]。

假設[Q]代表除[C]之外的另一條多條件時間序列；[qi]和[cj]分別對應[Q]序列的[i]點以及[C]序列的[j]點，用式（3）描述兩條原始數據多條件時間序列點的曲線相似性。

[SQ，C=i=1nqi-cj2-1] （3）

1.1.3" 相似曲線調整

經過多條件時間序列近似符號聚合以及相似度測量后，再利用加權調整法（Fitted Curve）計算[ω]個相似的多條件時間序列[A]，即可得到原始多條件時間序列[X]的對應參照曲線[X]。如果缺失值在原始多條件時間序列[X]中，可通過多次加權計算獲得參照曲線進行補充，對比分析異樣數據情況[10]。為獲取精準的相似多條件時間序列加權平均值，可通過調整最大閾值方法判斷數據中點的異常。利用公式（4）描述閾值[xk]與[δk]的關系。

[δk=maxA-xkSQ，C] （4）

以滿足公式（4）為前提條件，如果[x]不能滿足其條件，[x]為異常數據。濾除異常數據即可實現對大規模數據的清洗處理，得到清洗后的數據集[C]。

1.2" 基于孤立森林檢測多離群點

1.2.1" 構建孤立森林

大規模數據通過數據清洗，保證其數據的一致性，并清除無效值和補充缺失值，完善大規模數據后，即可構建i Tree，最后形成i Forest（孤立森林）。每個孤立樹是由隨機選擇的特征和閾值組成的二叉搜索樹[11]。通常孤立樹的深度由問題的復雜程度和數據集的大小來確定。最后，將多個孤立樹組合起來形成i Forest，即孤立森林。孤立森林通過路徑長度評估數據點的異常程度，路徑長度較短的數據點被認為是異常點。根據異常點在不同孤立樹中的出現頻率，可以對數據點進行異常程度的排序和評級。

上述過程具體可以分為如下步驟：

步驟1：構造i Tree的根節點。可遴選[ψ]個清洗后樣本數據作為訓練數據中的子樣本集。

步驟2：根據隨機選取的任意一個特征，切分數據中任選的一個點[P]，[P]值為切分閾值且[P∈min，max]。

步驟3：依據[P]值生成超平面，切分數據，并將數據空間切割成兩個子空間，將選定特征中大于[P]值的數據放入左子空間，小于[P]值的數據放入右子空間。

步驟4：在子節點中循環步驟2和步驟3，不斷迭代出新的子節點，直至子節點中只剩下一個數據點，不再滿足分割條件，或者因進入i Tree預設最大高度，從而停止分割，獲取包含若干i Tree的i Forest。

1.2.2" 離群點檢測實現

孤立樹的構成與離群點檢測圖如圖2所示。由圖2可知，點[Q]在經歷過兩次隨機拆分后掉落在葉子節點形成孤立點，其他正常樣本點可再被拆分，正常樣本點到達根節點的距離全部大于點[Q]，點[Q]是離群點的可能性很大[12?13]。

由清洗后數據集[C]組成i Forest后，檢測數據集[C]是否異常。數據[xp]代表數據集[C]中的離群點數據，離群點檢測即檢測出哪棵樹的哪片葉子節點是數據[xp]的落至處。離群點數據在大規模數據中是極少存在的，所以數據點[xp]落至葉子節點處速度很快。假設路徑[lxp]用于描述數據點[xp]所在葉節點滑落至根節點的距離，可通過[lxp]的距離長度判斷數據點[xp]是否是離群點。

基于i Forest的大規模數據異常檢測算法輸入為：大規模數據集構造的i Forest；大規模數據集[C]中某一個待檢測的離群點數據為[x]；輸出：離群點檢測結果。

檢測步驟為：

步驟1：第1～3行獲取i Tree的數量[t]和每棵i Tree包含的離群點數據量[η]，i Tree的高度為[h∈log η，η-1]。

步驟2：第4行計算[xp]到i Tree根節點的距離，如果[xp]不在該i Tree中，則成為新的葉子節點。

步驟3：對于大規模數據訓練集[C]中的樣本數據，循環遍歷每一棵i Tree，根據步驟2即可檢測出數據[xp]落至哪棵i Tree的層數。

步驟4：第6行[Ehxp]是計算求取所有i Tree高度的平均值，通過代入式（5）、式（6）可得到數據的異常指數，公式（5）綜合所有i Tree的結果，提升高度估計的可預測性，提高離群點異常檢測結果的精準性。

[Sx，n=2-Ehxpcn] （5）

[cn=2HN-1-2n-12] （6）

步驟5：第8～16行判斷樣本數據點是否為離群點，[Sxp，n]是離群點[xp]在由大規模數據子樣本集構造的i Tree中的異常指數，[Sx，n]在[0，1]范圍內，第7行中的[cn]為公式（6）所定義的平均路徑長度。[Sxp，n]越接近1，[xp]越有可能為離群點；[Sxp，n]越接近0，[xp]越有可能為正常樣本點；如果[Sxp，n≈0.5]，則表示數據集[C]沒有明顯的異常值，也就是不存在離群點。

2" 實驗分析

為驗證基于孤立森林的多離群點數據檢測算法的實際應用性能，設計如下實驗。

實驗數據來源于2022年水發航宇星物聯科技有限公司提供的用戶異常行為數據集，數據集包含6 958 324個數據，其中包含屬性5個：日志數據記錄編號（ID）、終端IP（IP）、終端上網應用端口（port）、終端上網行為發生時間（time）、異常行為評價得分（ret）。

設i Forest中i Tree的數量為50棵，每棵i Tree中的樣本數為128；設置數據集的異常值比例為2%；每棵i Tree的最大高度為10；正常樣本表示為“1”，離群樣本表示為“-1”。

為了驗證本文算法檢測數據中離群點的準確性，隨機選取某用戶IP 2022年3月1日—16日流量數據，對其ret字段的數據離群點進行檢測，其中含有4個異常數據。采用本文算法對ret處理后，數據異常檢測結果如圖3所示。

根據圖3所示的結果可以看出，本文算法共檢測到4個值為-1，判斷為離群點（異常數據），分別是3月3日、3月4日、3月7日和3月14日。本文實驗結果與數據樣本結果一致，實驗證明，本文算法可以有效識別離群點且準確率較高。

為了驗證本文算法針對離群點檢測的精確度，將文獻[3]基于質心投影波動檢測算法、文獻[4]基于EWT?LOF檢測算法作為本文算法的對比算法。使用本文算法對表1中三種屬性的數據展開實驗。

利用受試者工作特征曲線下的面積（AUC）指標可表示算法異常檢測精準度。AUC的取值范圍是[0，1]，檢測結果越接近于1，則說明算法的檢測精確性越高。

三種算法的AUC值統計結果如表2所示。

根據表2所示的結果可以看出，在測試三個屬性時，本文算法的AUC值明顯高于兩種傳統算法，其AUC值最大可達到98.11%。上述結果表明，本文算法在檢測大規模數據的離群點時具有較高的精確度。

3" 結" 論

本文基于孤立森林實現了多離群點檢測，針對孤立森林算法中時間復雜度高的問題，對多條件時間序列進行了近似符號聚合算法，大大降低了孤立森林算法的時間復雜程度，提高了大規模數據的處理效率。實驗證明，相對于傳統離群點檢測算法，本文算法在數據離群檢測上準確率非常高，提高了離群點檢測精準度。希望今后該算法能夠應用到更多領域范圍，實現其應用價值。

參考文獻

[1] 劉財輝，劉地金.離群點檢測的鄰近性方法綜述[J].計算機工程與應用，2022，58（21）：1?12.

[2] 張玉婷，馮山.一種基于鄰域近似精度的離群點檢測方法[J].數據采集與處理，2022，37（5）：1018?1025.

[3] 張忠平，張玉停，劉偉雄，等.基于質心投影波動的離群點檢測算法[J].計算機集成制造系統，2022，28（12）：3869?3878.

[4] 董澤，賈昊.基于EWT?LOF的熱工過程數據異常值檢測方法[J].儀器儀表學報，2020，41（2）：126?134.

[5] 王習特，朱宗梅，于雪蘋，等.異構分布式環境中的并行離群點檢測算法[J].湖南大學學報（自然科學版），2020，47（10）：100?110.

[6] 周杭，蔣瑜.基于高對比度子空間的改進孤立森林方法[J].計算機應用研究，2023，40（2）：388?393.

[7] 金利娜，于炯，杜旭升，等.基于生成對抗網絡和變分自編碼器的離群點檢測算法[J].計算機應用研究，2022，39（3）：774?779.

[8] 季偉東，倪婉璐.一種基于歐氏距離的種群規模動態控制方法[J].電子與信息學報，2022，44（6）：2195?2206.

[9] 張豹，應勵志，余宇峰.基于趨勢特征的時間序列符號聚集近似表示方法[J].計算機應用，2022，42（z1）：123?129.

[10] 林昕玥，于炯，杜旭升，等.基于自編碼器和密度的融合離群點檢測算法[J].東北師大學報（自然科學版），2021，53（1）：53?60.

[11] 孫葉芳，張月義，茅婷，等.一種基于改進NISD的偏二叉樹馬田系統的數據多分類算法[J].統計與決策，2022，38（16）：22?26.

[12] 郭一陽，于炯，杜旭升，等.基于隨機投影與集成學習的離群點檢測算法[J].計算機應用研究，2022，39（9）：2608?2614.

[13] 蔣斌，黃恩銘.基于分形理論的異質網絡中局部離群點檢測[J].計算機仿真，2023，40（1）：544?547.