基于孤立森林的多離群點數(shù)據(jù)檢測算法設(shè)計

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

關(guān)鍵詞： 孤立樹； 孤立森林； 離群點； 大規(guī)模數(shù)據(jù)； 異常檢測； 相似度測量； 數(shù)據(jù)清洗； 時間序列

中圖分類號： TN99?34" " " " " " " " " " " " " 文獻(xiàn)標(biāo)識碼： 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" 引" 言

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

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

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

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

1" 多離群點檢測方法設(shè)計

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

具體來說，孤立森林通過以下步驟進(jìn)行：

1） 隨機(jī)選擇一個特征和對應(yīng)的閾值，將數(shù)據(jù)集劃分為兩個子集。

2） 重復(fù)步驟1），直到每個子集中的數(shù)據(jù)點都被單獨分割或達(dá)到了預(yù)定的樹的深度。

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

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

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

1.1" 數(shù)據(jù)清洗處理

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

1.1.1" 近似符號聚合算法

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

近似符號聚合算法使多條件時間序列的維度由[n]下落至[N]，由近似符號聚合算法轉(zhuǎn)換成數(shù)據(jù)形式的一個字符串。[X=x1，x2，…，xn]表示原始多條件時間序列集。對每個多條件時間序列統(tǒng)一處理，令0代表平均值，1代表基準(zhǔn)差，[C=c1，c2，…，cn]表示統(tǒng)一后的數(shù)據(jù)多條件時間序列，[μ]、[δ]分別代表原始時間序列的平均值和基準(zhǔn)差。用公式（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" 相似度計算

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

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

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

1.1.3" 相似曲線調(diào)整

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

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

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

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

1.2.1" 構(gòu)建孤立森林

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

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

步驟1：構(gòu)造i Tree的根節(jié)點?？慑噙x[ψ]個清洗后樣本數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)中的子樣本集。

步驟2：根據(jù)隨機(jī)選取的任意一個特征，切分?jǐn)?shù)據(jù)中任選的一個點[P]，[P]值為切分閾值且[P∈min，max]。

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

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

1.2.2" 離群點檢測實現(xiàn)

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

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

基于i Forest的大規(guī)模數(shù)據(jù)異常檢測算法輸入為：大規(guī)模數(shù)據(jù)集構(gòu)造的i Forest；大規(guī)模數(shù)據(jù)集[C]中某一個待檢測的離群點數(shù)據(jù)為[x]；輸出：離群點檢測結(jié)果。

檢測步驟為：

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

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

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

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

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

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

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

2" 實驗分析

為驗證基于孤立森林的多離群點數(shù)據(jù)檢測算法的實際應(yīng)用性能，設(shè)計如下實驗。

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

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

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

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

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

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

三種算法的AUC值統(tǒng)計結(jié)果如表2所示。

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

3" 結(jié)" 論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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