基于相關(guān)子空間的擴(kuò)展隔離森林離群檢測算法

劉 佳，朱鵬云，荀亞玲

(太原科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

離群檢測是數(shù)據(jù)挖掘任務(wù)的重要內(nèi)容之一，試圖捕獲顯著偏離多數(shù)模式的異常情況[1]，挖掘出潛在的、有意義的知識。離群檢測挖掘出的離群數(shù)據(jù)對象隱藏著非常重要的信息和知識,其背后可能蘊(yùn)含著更大的研究價值。離群檢測已經(jīng)被廣泛應(yīng)用于入侵檢測[2-4]、欺詐檢測[5-6]、醫(yī)療異常診斷[7-8]、工業(yè)控制系統(tǒng)的異常檢測[9]、無線傳感器網(wǎng)絡(luò)的異常檢測[10]、城市交通流異常檢測[11]、天體光譜數(shù)據(jù)挖掘[12]等領(lǐng)域。現(xiàn)有的離群檢測算法大致可以分為以下幾類：基于統(tǒng)計的方法、基于距離的方法、基于密度的方法、基于聚類的方法和基于集成的方法等。集成離群檢測作為一種離群檢測方法，將多個離群檢測算法或模型相結(jié)合，形成一個集成框架，提高離群檢測性能。

隔離森林(Isolation Forest)[13]作為一種集成離群檢測方法,利用離群數(shù)據(jù)少且與眾不同的特點(diǎn)將離群數(shù)據(jù)隔離在離樹根較近的地方，而將正常數(shù)據(jù)隔離在離樹根較遠(yuǎn)的一端。隔離森林可以將離群數(shù)據(jù)與正常數(shù)據(jù)快速分離，具有較低的線性時間復(fù)雜度。在組合多棵樹構(gòu)成森林后，離群檢測效果優(yōu)于多數(shù)傳統(tǒng)的離群檢測算法，但隔離森林在構(gòu)建隔離樹的過程中，分枝僅隨機(jī)選擇一個維度屬性進(jìn)行水平或垂直的切割，且屬性可能為無關(guān)屬性，降低了離群檢測效果。擴(kuò)展隔離森林算法具備了隔離森林離群檢測的優(yōu)點(diǎn)，允許數(shù)據(jù)切片使用帶有隨機(jī)斜率的超平面，解決了隔離森林中樹分枝軸平行的切割使異常分?jǐn)?shù)圖中存在偏差等問題[14]，但隔離樹超平面選取在數(shù)據(jù)集的密集區(qū)域或含有無關(guān)維度的區(qū)域，影響離群檢測的效果。該文采用相關(guān)子空間，提出了一種基于相關(guān)子空間的擴(kuò)展隔離森林離群檢測算法，解決了擴(kuò)展隔離森林離群檢測確定超平面隨機(jī)性強(qiáng)的問題，其主要貢獻(xiàn)如下：

·提出了一種基于相關(guān)子空間的分支切割截距點(diǎn)選取方法；

·給出了一種擴(kuò)展隔離森林分割平面選擇策略；

·提出了一種基于相關(guān)子空間的擴(kuò)展隔離森林離群檢測算法。

1 相關(guān)工作

離群檢測算法大致分為以下幾類：基于統(tǒng)計的方法、基于距離的方法、基于密度的方法、基于聚類的方法和基于集成的方法等。隔離森林是一種獨(dú)特的集成離群檢測方法，它利用一種隔離機(jī)制來檢測異常，通過遞歸軸平行細(xì)分將每個實例與其余實例隔離開來。隔離森林有較低的線性時間復(fù)雜度，避免了基于距離和密度方法進(jìn)行檢測時的計算量大的問題。隔離森林是集成的方法，組合多棵樹構(gòu)成森林后，離群檢測效果優(yōu)于多數(shù)傳統(tǒng)的離群檢測算法。隔離森林離群檢測可以用在含有海量數(shù)據(jù)的數(shù)據(jù)集上，由于每棵樹都是互相獨(dú)立生成的，因此可部署在大規(guī)模分布式系統(tǒng)上來加速運(yùn)算。

隔離森林作為一類集成離群檢測方法，國內(nèi)外學(xué)者對其進(jìn)行了大量研究，其典型研究工作包括：文獻(xiàn)[14]擴(kuò)展隔離森林離群檢測算法可選取隨機(jī)斜率的超平面，解決了隔離森林中樹分枝軸平行的切割使異常分?jǐn)?shù)圖中存在偏差等問題。文獻(xiàn)[15]提出一種利用隔離概念進(jìn)行離群檢測的方法(isolation using Nearest Neighbor Ensemble，iNNE)，采用最近鄰算法來代替基于樹的方法來隔離數(shù)據(jù)對象,使用最近鄰隔離超球體來隔離目標(biāo)空間中的數(shù)據(jù)，是一種基于隔離思想的高精度集成學(xué)習(xí)算法，對局部離群數(shù)據(jù)較敏感，但在數(shù)量巨大的數(shù)據(jù)集中時間開銷太大。文獻(xiàn)[16]提出了一種基于k-means的隔離森林算法，優(yōu)化隔離樹的結(jié)構(gòu)通過將每個節(jié)點(diǎn)分割成k個子節(jié)點(diǎn)，且在樹的每個節(jié)點(diǎn)上采用k-means進(jìn)行劃分。該算法可以處理不同應(yīng)用領(lǐng)域的數(shù)據(jù)，但沒有考慮隨機(jī)選擇的屬性可能為無關(guān)屬性的問題。文獻(xiàn)[17]提到基于樹隔離機(jī)制的離群檢測方法使用的這種快速隔離機(jī)制僅局限于距離測量，不能推廣到其他常用測量，因此提出了一個LSHiForest通用框架，使用位置敏感哈希(LSH)森林。該框架具有通用性，可以用不同范圍的LSH函數(shù)實例化，并且快速隔離機(jī)制可以擴(kuò)展到定義LSH函數(shù)的任何距離度量、數(shù)據(jù)類型和數(shù)據(jù)空間。該文獻(xiàn)表明現(xiàn)有的基于樹隔離的檢測方法是此框架的特例，具有相應(yīng)的距離度量，且該框架具有較高的時間效率和異常檢測效果。文獻(xiàn)[18]提出了一種基于模糊孤立森林算法的離群數(shù)據(jù)檢測方法，通過挑選一些有價值的屬性對其分別建樹組成孤立森林，從多維度出發(fā)，對每一維屬性的檢測結(jié)果進(jìn)行隸屬度判斷，最后與模糊矩陣進(jìn)行模糊運(yùn)算得到最終評價結(jié)果。但算法需要從單因素的角度對各等級的模糊子集做隸屬度判斷，由專家根據(jù)評判等級對評價對象進(jìn)行打分，組成模糊關(guān)系矩陣。

隔離森林離群檢測算法可以將離群數(shù)據(jù)與正常數(shù)據(jù)快速分離，有較低的線性時間復(fù)雜度。但隔離森林每次分割隨機(jī)選取一個維度，高維空間中可能有大量的維度信息沒有被使用進(jìn)行分割，且可能存在無關(guān)維度影響樹的構(gòu)建，基于路徑長度的全局排名測度對局部異常不敏感，軸平行的細(xì)分掩蓋了軸平行之間存在的異常。針對隔離森林算法的不足，一些國內(nèi)外學(xué)者進(jìn)行了改進(jìn)，但算法選擇分割點(diǎn)的方式隨機(jī)性較強(qiáng)，均沒有考慮無關(guān)屬性維對離群檢測的影響。該文提出了一種基于相關(guān)子空間的擴(kuò)展隔離森林離群檢測算法，利用多維度隨機(jī)斜率的超平面，避免了軸平行分割帶來的不足；優(yōu)先在數(shù)據(jù)分布稀疏的數(shù)據(jù)集中進(jìn)行分割，使離群數(shù)據(jù)快速地從稀疏數(shù)據(jù)區(qū)域中隔離出來；在數(shù)據(jù)的相關(guān)子空間維度上確定超平面，避免了無關(guān)維度的干擾，提高了離群檢測的準(zhǔn)確率和效率。

2 隔離森林與相關(guān)子空間

2.1 子空間與隔離森林離群檢測

隔離森林離群檢測利用了離群數(shù)據(jù)的兩個特征：離群數(shù)據(jù)占數(shù)據(jù)集總體規(guī)模的比重較?。浑x群數(shù)據(jù)相比正常數(shù)據(jù)的屬性值存在明顯的差異。在隔離森林中，遞歸地隨機(jī)分割數(shù)據(jù)集，直到所有的樣本點(diǎn)都是孤立的。在該隨機(jī)分割策略下，離群數(shù)據(jù)可以快速被隔離，而正常數(shù)據(jù)需要許多分支切割來隔離。參照文獻(xiàn)[13]，相關(guān)概念定義如下：

定義1(隔離樹，Isolation Tree)：令T是一棵二叉隔離樹的節(jié)點(diǎn)，T要么是沒有子節(jié)點(diǎn)的葉子節(jié)點(diǎn)(外部節(jié)點(diǎn))，要么是只有兩個孩子節(jié)點(diǎn)(Tl,Tr)的內(nèi)部節(jié)點(diǎn)。每一次分割都包含屬性q和分割值p，將數(shù)據(jù)點(diǎn)在屬性q的值qi

給定n個樣本數(shù)據(jù)的數(shù)據(jù)集X={x1,x2,…,xn}，數(shù)據(jù)集的特征維度為d。為其構(gòu)造一棵隔離樹，每次分割需要隨機(jī)選擇一個特征q及其分割值p，遞歸地分割數(shù)據(jù)集X構(gòu)造左子樹和右子樹，直到滿足以下任意一個條件：(1)樹達(dá)到了限制的高度；(2)節(jié)點(diǎn)上只有一個樣本；(3)節(jié)點(diǎn)上的樣本所有特征都相同。

定義2(路徑長度)：在一棵隔離森林樹Isolation Tree中，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)所經(jīng)歷邊的數(shù)目稱為數(shù)據(jù)點(diǎn)x的路徑長度，記為h(x)。

由于Isolation Tree與二叉查找樹的結(jié)構(gòu)等價，外部節(jié)點(diǎn)的平均路徑長度h(x)的估計等價于二叉查找樹中查找不成功的平均查找長度。對于給定的數(shù)據(jù)集X，二叉查找樹中查找不成功的平均查找長度為：

c(n)=2H(n-1)-(2(n-1)/n)

(1)

其中，H(i)為調(diào)和數(shù)，H(i)=ln(i)+0.577 215 664 9 (歐拉常數(shù))；n為葉子節(jié)點(diǎn)數(shù)；c(n)為給定n時h(x)的平均值，用來標(biāo)準(zhǔn)化數(shù)據(jù)點(diǎn)x的路徑長度h(x)。數(shù)據(jù)點(diǎn)x的離群得分計算方法如下：

(2)

其中，E(h(x))為Isolation Tree集合中h(x)的平均值。當(dāng)E(h(x))→c(n)時，s→0.5，即當(dāng)所有數(shù)據(jù)均返回的s≈0.5時，全部樣本中沒有明顯的異常值；當(dāng)E(h(x))→0時，s→1，即當(dāng)數(shù)據(jù)返回的s非常接近于1時，它們是異常值；當(dāng)E(h(x))→n-1時，s→0，即當(dāng)數(shù)據(jù)返回的s遠(yuǎn)小于0.5時，它們有很大的可能為正常值。

隔離森林離群檢測每次隨機(jī)選擇一個屬性維再隨機(jī)選擇其屬性維的一個值作為分割點(diǎn)進(jìn)行分割，一方面，隔離森林離群檢測受到“維災(zāi)”的影響，在高維空間中一些無關(guān)維度嚴(yán)重地影響離群檢測效果；另一方面，選擇的分割點(diǎn)若在稠密數(shù)據(jù)區(qū)域，很難將離群數(shù)據(jù)隔離出來。

2.2 高斯混合模型與相關(guān)子空間

在隔離森林離群檢測中，每次分割在由有意義屬性維構(gòu)成的子空間中，隨機(jī)選擇一個屬性，可避免無關(guān)屬性維對離群檢測的干擾。在稀疏數(shù)據(jù)區(qū)域中，隨機(jī)選擇一個屬性取值實現(xiàn)分割，可避免稠密數(shù)據(jù)區(qū)域的屬性取值分割對離群檢測的影響。

在離群檢測中，某些相關(guān)屬性維提供了有價值信息，而有些屬性維有價值信息很少甚至沒有[20]。若利用所有屬性實現(xiàn)離群檢測，就會受到離群信息很少的無關(guān)屬性干擾。參考文獻(xiàn)[20-21]，相關(guān)子空間是非均勻分布的屬性維組成的集合，可有效地體現(xiàn)出“離群數(shù)據(jù)”的價值信息，其相關(guān)定義如下：

定義4：設(shè)DS是一個d維數(shù)據(jù)集,屬性集FS={A1,A2,…,Ad},數(shù)據(jù)對象x的最近鄰為N(x,FS)(即局部數(shù)據(jù)集LDS),如果N(x,FS)在Ai屬性維上的取值是非均勻分布的,則稱Ai可以提供有價值的信息,屬于相關(guān)子空間中的屬性維；反之，如果N(x,FS)在Ai屬性維上的取值是均勻分布的,則稱Ai不能提供有價值的信息,屬于不相關(guān)子空間中的屬性維。

為了通過局部屬性維數(shù)的稀疏性來度量屬性是否服從均勻分布，在文獻(xiàn)[21]中，引入了稀疏度的概念。第i條數(shù)據(jù)第j維度的數(shù)據(jù)稀疏度yij為:

(3)

由公式(3)可得知，yij代表局部數(shù)據(jù)屬性維的方差，yij較大,表明xi的局部數(shù)據(jù)集在屬性維j上的值不均勻，xij在其局部數(shù)據(jù)集中的密度較小，xij所在的是稀疏子空間(相關(guān)子空間)；相反，yij較小，表明xi的局部數(shù)據(jù)集在屬性維j上的值較均勻，xij在其局部數(shù)據(jù)集中的密度較大，xij所在的是稠密子空間(不相關(guān)子空間)。根據(jù)公式(3)，可以計算所有數(shù)據(jù)對象在每個屬性維度的稀疏度，并生成整個數(shù)據(jù)集的稀疏因子矩陣，稀疏度矩陣每個維度的稀疏度yij是由稀疏子空間和稠密子空間混合組成的。通過稀疏度矩陣，可以更方便衡量數(shù)據(jù)空間的稠密和稀疏區(qū)域，去除均勻分布屬性維，保留非均勻分布屬性維，發(fā)現(xiàn)數(shù)據(jù)空間的相關(guān)子空間。

文獻(xiàn)[21]中通過預(yù)先設(shè)定好的閾值對每個維度上稀疏因子進(jìn)行區(qū)分，從而確定各數(shù)據(jù)對象的相關(guān)子空間和不相關(guān)子空間，解決了檢測相關(guān)子空間時時間復(fù)雜度較高的問題，提高了算法的效率，然而通過同一個閾值對所有的維度確定子空間，當(dāng)各個維度的數(shù)據(jù)分布有差異時，得到的相關(guān)子空間就會有一定的誤差。但高斯混合模型利用高斯概率密度函數(shù)(正態(tài)分布曲線)精確地量化事物，它是一個將事物分解為若干的基于高斯概率密度函數(shù)形成的模型。稀疏度矩陣每個維度的稀疏度yij是由稀疏子空間和稠密子空間混合組成的，高斯混合模型的靈活性使其能夠很好地適應(yīng)稀疏度的分布，可以自適應(yīng)地得到該維度的稀疏子空間和稠密子空間[22]。因此，利用高斯混合模型識別稀疏度yij所在的子空間，即該維度的相關(guān)子空間和不相關(guān)子空間。

把第j維所有數(shù)據(jù)對象的稀疏度yij用作高斯混合模型：

(4)

第r個高斯分布的密度函數(shù)為:

(5)

其中，每個部分的密度函數(shù)Nr含有兩個參數(shù)，分別為期望ur和標(biāo)準(zhǔn)差σr，ur描述正態(tài)分布的集中趨勢位置，σr描述正態(tài)分布中數(shù)據(jù)分布的離散程度。使用高斯混合模型對每一維度稀疏度進(jìn)行擬合，把稀疏度分為兩個高斯分布，稀疏度較大的分布中的數(shù)據(jù)構(gòu)成相關(guān)子空間，較小的分布中的數(shù)據(jù)構(gòu)成無關(guān)子空間，所以該高斯混合模型由兩個高斯分布組成，即m=2。EM算法[23](最大似然估計)是一種改善模型參數(shù)估計的迭代算法，可以用來估計模型中的參數(shù)，也是GMM參數(shù)估計最常用的一種方式。使用EM算法來估計高斯混合模型各個參數(shù)，得到每一維度的每個稀疏度屬于兩個高斯分布的概率值，在哪個高斯分布的概率值大就屬于哪個高斯分布。同時可以得到每一維度的兩個高斯分布的均值，均值較大的高斯分布的稀疏度比較大，屬于均值較大的高斯分布的數(shù)據(jù)構(gòu)成的子空間是稀疏子空間即相關(guān)子空間。

文獻(xiàn)[22]中使用二進(jìn)制矩陣Z直觀表示稀疏因子矩陣的相關(guān)性。第i個數(shù)據(jù)對象第j維度的值zij的定義如下：

定義5：對于數(shù)據(jù)對象xi，yij是第i個數(shù)據(jù)對象第j維度的稀疏度，zi是其子空間向量，zij是第i個數(shù)據(jù)對象第j維度的值，如果yij屬于相關(guān)子空間，則zij=1，如果yij屬于不相關(guān)子空間，則zij=0。

根據(jù)EM算法對稀疏度區(qū)分的結(jié)果和定義5，可以生成數(shù)據(jù)對象的子空間向量zi。

3 相關(guān)子空間與擴(kuò)展隔離森林離群檢測

3.1 相關(guān)子空間與分支切割截距點(diǎn)

設(shè)DS是一個d維數(shù)據(jù)集，xi為DS中的任意數(shù)據(jù)對象，依據(jù)公式(3)、(4)、(5)和定義5，可得到xi的子空間向量zi。為了刻畫xi所有屬性維度的稀疏程度，可定義如下的xi相關(guān)維系數(shù)mi：

(6)

由公式(6)可知，mi越大，表明xi在相關(guān)子空間中的維度占DS全部維度d的比值越大，即：xi的稀疏維度數(shù)量越多，xi越可能處于稀疏區(qū)域；反之，mi越小，表明xi在相關(guān)子空間中的維度占DS全部維度d的比值越小，即：xi的稀疏維度數(shù)量越少，xi越可能處于稠密區(qū)域。

利用相關(guān)維系數(shù)mi，將數(shù)據(jù)集DS分成稠密分布的子集Dd和稀疏分布的子集Ds，其中：Dd={xi|xi∈DS，mi=0}，Ds={xi|xi∈DS,mi≠0}。當(dāng)mi=0時，xi的每個維度都不屬于相關(guān)子空間屬性，xi不存在稀疏屬性維，xi屬于稠密區(qū)域；當(dāng)mi≠0時，表示xi的維度屬于相關(guān)子空間屬性，xi含有稀疏屬性，xi屬于稀疏區(qū)域。

由公式(3)可知，xi的稀疏度yij是在xi的局部數(shù)據(jù)集LDS上獲得的，xi的局部數(shù)據(jù)集LDS反映了xi的分布情況，公式(4)和(5)高斯混合模型能很好地區(qū)分?jǐn)?shù)據(jù)對象屬性維的稀疏，因此xi的子空間向量zi能夠準(zhǔn)確反映局部數(shù)據(jù)的分布特征，mi的大小是由zi的取值決定的，可以較為準(zhǔn)確地刻畫數(shù)據(jù)對象分布的稀疏，從而可將DS劃分為稀疏區(qū)域和稠密區(qū)域。

3.2 擴(kuò)展隔離森林分割平面選擇策略

依據(jù)該選擇策略確定超平面，遞歸其分割操作，直到當(dāng)前子樹只包含一個節(jié)點(diǎn)或達(dá)到預(yù)設(shè)的樹高。優(yōu)先在數(shù)據(jù)分布稀疏的數(shù)據(jù)集中，選擇分支切割的隨機(jī)截距點(diǎn)，可快速地使離群數(shù)據(jù)從稀疏數(shù)據(jù)區(qū)域中隔離出來，并在截距點(diǎn)數(shù)據(jù)所對應(yīng)的相關(guān)子空間維度上，生成超平面的隨機(jī)斜率來確定超平面，可避免無關(guān)維度的影響，提高擴(kuò)展隔離森林離群檢測的效果。

3.3 擴(kuò)展隔離森林離群檢測算法

綜上所述，采用相關(guān)子空間，擴(kuò)展隔離森林離群檢測基本思想為：首先，通過kd樹尋找數(shù)據(jù)集中每個數(shù)據(jù)對象的k近鄰并生成其局部數(shù)據(jù)集LDS，依據(jù)公式(3)-(5)計算出每個數(shù)據(jù)對象的稀疏度yij并識別yij所在的子空間,生成數(shù)據(jù)對象xi的子空間向量zi；然后，隨機(jī)采樣t次構(gòu)造t棵不同的隔離樹,每次隨機(jī)采樣ψ個數(shù)據(jù)，按照上述分割平面選擇策略，構(gòu)造每棵隔離樹；最后，對整個數(shù)據(jù)集進(jìn)行檢測，使用PathLength函數(shù)計算數(shù)據(jù)對象xi在gTree樹的路徑長度h(x)，并計算xi在各隔離樹的平均路徑長度，依據(jù)公式(2)將平均路徑長度歸一化后作為數(shù)據(jù)對象的離群得分，輸出離群得分最高的前M個數(shù)據(jù)對象作為離群數(shù)據(jù)。其算法描述如下：

算法：RSGMM-EIF

輸入:數(shù)據(jù)集DS，子抽樣大小ψ，隔離樹數(shù)量t，近鄰數(shù)k

輸出:離群數(shù)據(jù)

1.n=DS的數(shù)據(jù)個數(shù)，d=DS的維度

2.for(i=0;i

3.LDSi=getknn()； //計算第i個數(shù)據(jù)對象的局部數(shù)據(jù)集LDS

4.spi=getspdegree()； //依據(jù)公式(3)計算第i個數(shù)據(jù)對象的稀疏度

5.}

6.Z=getsubspace(); //依據(jù)公式(4)和(5)計算相關(guān)子空間

7.IForest=iForest(DS,t,ψ)；//構(gòu)造隔離森林

8.T=gTree(DS,e,l,Z)；//構(gòu)造gTree

9.forxiin DS{

10.h_temp=0

11.forjin range(t){

13.h_temp= h_temp+depth；

14.}

15.Eh=h_temp/t；

16.依據(jù)公式(2)，計算數(shù)據(jù)對象的離群得分；

17.}

18.選取離群得分最大的M個數(shù)據(jù)對象作為離群數(shù)據(jù)；

19.End RSGMM-EIF

函數(shù)：gTree(DS,e,l,Z)

輸入:數(shù)據(jù)集DS,當(dāng)前樹的高度e,隔離樹的高度限制l,二進(jìn)制矩陣Z

輸出:隔離樹

//達(dá)到限定高度或孩子節(jié)點(diǎn)只有一個數(shù)據(jù)時完成樹的構(gòu)建

1.ife≥lor |X|≤1 then

2.return exNode

3.else

4. 依據(jù)公式(6)和(7)計算稀疏分布的數(shù)據(jù)集Ds；

5.if len(Ds)≠0，

8.else

11.end if

15.end if

16.End gTree

算法復(fù)雜性分析：參照文獻(xiàn)[22]，計算數(shù)據(jù)對象的稀疏度和利用高斯混合模型識別數(shù)據(jù)對象的相關(guān)子空間的時間復(fù)雜度是O(nlogn)+O(n*k*d)+O(n*d)≈O(nlogn)+O(n*k*d)；在構(gòu)建gTree時，每次分割需要生成確定超平面的兩個向量并計算不同數(shù)據(jù)對象的隔離方向，構(gòu)造隔離森林的時間復(fù)雜度是O(tdψlog2ψ)；計算整個數(shù)據(jù)集離群得分的過程時間復(fù)雜度和空間復(fù)雜度是O(ntdlog2ψ)；RSGMM-EIF的時間復(fù)雜度是O(nlogn)+O(n*k*d)+O(tdψlog2ψ)+O(ntdlog2ψ)。

4 實驗結(jié)果及分析

實驗環(huán)境：Intel(R) Core(TM) i5-1135G7，16 GB內(nèi)存，Windows10操作系統(tǒng)，采用python語言實現(xiàn)了RSGMM-EIF算法及對比算法IF[13]、EIF[14]、iNNE[15]和基于密度的局部異常因子LOF算法[24]。采用UCI數(shù)據(jù)集作為實驗數(shù)據(jù)，詳見表1。

表1 UCI數(shù)據(jù)集

在表1中，Pima是印第安人糖尿病診斷數(shù)據(jù)集，由8個醫(yī)學(xué)預(yù)測變量和一個目標(biāo)變量Outcome類標(biāo)變量(0或1)組成，預(yù)測變量包括患者的懷孕次數(shù)、BMI、胰島素水平、年齡等；Cardio是由心電圖上的胎兒心率(FHR)和子宮收縮(UC)特征測量結(jié)果組成的分類數(shù)據(jù)集，產(chǎn)科專家將其結(jié)果分為正常、可疑和病理三個類別，將可疑類的數(shù)據(jù)對象丟棄后作為離群檢測數(shù)據(jù)集；Satellite是衛(wèi)星圖像的分類數(shù)據(jù)，樣本分為7類，其中第6類沒有實例，實驗將數(shù)量較少的第2、4、5類樣本標(biāo)記為離群數(shù)據(jù)；Satimage-2是將多分類數(shù)據(jù)集Statlog (Landsat Satellite)的第2類數(shù)據(jù)對象作為離群數(shù)據(jù)，其他類合并作為正常數(shù)據(jù)得到的；Optdigits是光學(xué)識別手寫數(shù)字?jǐn)?shù)據(jù)集，數(shù)字1～9的數(shù)據(jù)對象作為正常數(shù)據(jù),150個數(shù)字0的數(shù)據(jù)對象作為離群數(shù)據(jù)；Mnist將手寫數(shù)字的原始Mnist數(shù)據(jù)集中數(shù)字0的圖像作為正常數(shù)據(jù)，將抽取的700幅數(shù)字6圖像中作為離群數(shù)據(jù)，并且數(shù)據(jù)集的特征是從圖像總共784個特征中隨機(jī)抽取了100個。

性能評估指標(biāo)：AC和AUC。準(zhǔn)確率AC表示給定測試集預(yù)測正確的樣本數(shù)與總樣本數(shù)之比，準(zhǔn)確率能夠衡量預(yù)測結(jié)果總體的正確率。ROC曲線是一個二維平面上的曲線，平面的橫坐標(biāo)是實際負(fù)樣本中被錯誤預(yù)測為正樣本的概率(FPR)，縱坐標(biāo)是實際正樣本中被預(yù)測正確的概率(TPR)，可準(zhǔn)確反映FPR和TPR的關(guān)系，能更好地衡量樣本不均衡的情況，是檢測準(zhǔn)確性的綜合代表。AUC(Area Under Curve)是ROC曲線下方的面積。AUC值可以體現(xiàn)算法的性能，AUC越接近1，表明算法效果越好，AUC低于0.5，表明算法效果比隨機(jī)檢測還差。

4.1 參數(shù)ψ

為了實驗驗證參數(shù)抽樣數(shù)ψ對算法性能的影響，采用了表1中的5個數(shù)據(jù)集，其實驗結(jié)果詳見圖1和圖2。

圖1 抽樣數(shù)ψ對算法AC的影響

圖2 抽樣數(shù)ψ對算法AUC的影響

從圖1和圖2可以看出，隨著ψ增大，AC、AUC指標(biāo)值逐漸增加，并接近最優(yōu)值，后有所降低，表明將ψ一般設(shè)置為256通?？扇〉煤玫臋z測效果，無需再增大ψ，與文獻(xiàn)[13]中的結(jié)論一致。其主要原因是隨著ψ增大，隔離樹的樹高增加，可以更好地區(qū)分?jǐn)?shù)據(jù)對象的路徑長度，得到數(shù)據(jù)對象的離群得分；當(dāng)樣本量過大時，包含正常數(shù)據(jù)對象過多，不利于離群對象被隔離出來，導(dǎo)致算法效果不好。

4.2 參數(shù)t

為了實驗驗證參數(shù)隔離樹的數(shù)量t對算法性能的影響，采用表1中的4個數(shù)據(jù)集，其實驗結(jié)果詳見圖3和圖4。

圖3 隔離樹數(shù)量t對算法AC的影響

圖4 隔離樹數(shù)量t對算法AUC的影響

從圖3和圖4可知，隨著t的增加，AC、AUC指標(biāo)值逐漸增加,并趨于穩(wěn)定，表明隨著t值的增加，離群檢測性能趨于穩(wěn)定。其主要原因是隔離森林離群檢測依賴于集成學(xué)習(xí)的聚合能力，多棵樹集合更體現(xiàn)隔離森林離群檢測優(yōu)勢。

4.3 近鄰k

為了實驗驗證參數(shù)近鄰k對算法性能的影響，采用了表1中的4個數(shù)據(jù)集，其實驗結(jié)果詳見表2。

表2 近鄰k對算法性能的影響

4.4 離群檢測性能

為了實驗驗證算法的離群檢測準(zhǔn)確性，采用了表1中的數(shù)據(jù)集，以及AC和AUC指標(biāo)，其實驗結(jié)果詳見表3。RSGMM-EIF、IF和EIF的默認(rèn)參數(shù):創(chuàng)建100棵隔離樹,每棵樹256個樣本,樹高限制為8。

表3 離群檢測算法AC和AUC的比較

從表3可知，在大部分?jǐn)?shù)據(jù)集上，RSGMM-EIF的AC和AUC指標(biāo)值大，表明RSGMM-EIF優(yōu)于其他算法的離群檢測效果。在大部分?jǐn)?shù)據(jù)集上，RSGMM-EIF優(yōu)于IF和EIF的離群檢測效果，其主要原因是RSGMM-EIF利用了相關(guān)維系數(shù)mi，將數(shù)據(jù)集劃分為了稠密區(qū)域和稀疏區(qū)域，優(yōu)先在稀疏數(shù)據(jù)區(qū)域中選擇分支切割的隨機(jī)截距點(diǎn)，使離群數(shù)據(jù)快速地從稀疏數(shù)據(jù)區(qū)域中隔離出來，且在數(shù)據(jù)對象的相關(guān)子空間確定超平面的隨機(jī)斜率，避免了無關(guān)維度的干擾，算法性能更佳。在少部分?jǐn)?shù)據(jù)集上，EIF是在數(shù)據(jù)集的全維度空間中確定超平面，利用了每個維度的信息，取得了良好的離群檢測效果。iNNE和LOF在大部分?jǐn)?shù)據(jù)集上離群檢測效果不佳，主要原因是iNNE的抽樣數(shù)ψ對檢測性能有顯著影響，若ψ過大，會將分布密集的一些正常對象當(dāng)成異常對象；LOF沒有考慮無關(guān)屬性的影響，且對密度差異較大的簇邊界上的數(shù)據(jù)對象評分不準(zhǔn)確。

5 結(jié)束語

擴(kuò)展隔離森林離群檢測的超平面選取在數(shù)據(jù)集的密集區(qū)域或含有無關(guān)維度的區(qū)域，影響了離群檢測效果。該文采用相關(guān)子空間，給出了一種擴(kuò)展隔離森林離群檢測算法RSGMM-EIF。該算法利用數(shù)據(jù)對象的稀疏度和高斯混合模型，構(gòu)造了相關(guān)子空間，并在擴(kuò)展隔離樹構(gòu)建過程中，利用其相關(guān)子空間，確定超平面，從而使離群數(shù)據(jù)快速地從稀疏數(shù)據(jù)區(qū)域中隔離出來，避免了無關(guān)維度的干擾。