一種改進(jìn)隔離森林的快速離群點(diǎn)檢測算法

馮嘉琛，蔡江輝，楊海峰

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

1 引 言

離群數(shù)據(jù)(Outliers)是明顯偏離其他數(shù)據(jù)、不滿足數(shù)據(jù)的一般模式或行為、與其他數(shù)據(jù)存在顯著不同的數(shù)據(jù)[1].離群數(shù)據(jù)往往蘊(yùn)含著大量不易被發(fā)現(xiàn)但很有價(jià)值的信息，所以高性能的離群點(diǎn)檢測算法[2]被廣泛應(yīng)用于信用卡欺詐交易、入侵檢測、醫(yī)療診斷、地震預(yù)報(bào)等領(lǐng)域.現(xiàn)有的離群數(shù)據(jù)檢測算法大致可以分為以下幾類：基于統(tǒng)計(jì)的方法，基于距離的方法，基于密度的方法和基于聚類的方法等.其中，基于統(tǒng)計(jì)的方法首先建立一個(gè)數(shù)據(jù)模型，不能同模型擬合的對象被認(rèn)為是離群點(diǎn)[3].代表性例子包括最小協(xié)方差矩陣(MCD)[4]和一類支持向量機(jī)(OCSVM)[5].基于距離的方法考慮數(shù)據(jù)對象給定半徑的鄰域，如果它的鄰域沒有足夠多的其他點(diǎn)，則認(rèn)為它是離群點(diǎn)[3]，例如k近鄰算法[6]和反向最近鄰算法[7].基于密度的方法采用數(shù)據(jù)點(diǎn)的鄰域密度來表示其離群程度，離群點(diǎn)與正常點(diǎn)相比具有較低的密度.代表性的例子包括局部異常因子(LOF)[8]和基于局部密度的離群檢測方法(RDOS)[9].基于聚類的方法假定正常數(shù)據(jù)對象屬于大或稠密的簇，而離群點(diǎn)屬于小或稀疏的簇，或者不屬于任何簇[3].例如基于快速k近鄰的最小生成樹方法[10].但這些傳統(tǒng)的檢測方法都會(huì)受到“維度災(zāi)難”的影響，在高維空間中，由于數(shù)據(jù)量大且維度高，嚴(yán)重影響了離群數(shù)據(jù)挖掘的效果和效率[11]，算法在全維度進(jìn)行離群檢測時(shí)，真正的離群點(diǎn)被多個(gè)不相關(guān)維度的噪聲效應(yīng)掩蓋，此時(shí)離群點(diǎn)通常嵌入到局部相關(guān)子空間中[12].

與基于密度和基于距離等方法不同，隔離森林[13]算法在識(shí)別離群點(diǎn)時(shí)考慮分散和聚類屬性，它通過隔離數(shù)據(jù)來檢測離群點(diǎn)，而不依賴于任何距離或密度度量.給定一個(gè)數(shù)據(jù)集，隔離森林構(gòu)建了一個(gè)隔離樹(iTree)集合.在樹內(nèi)，離群點(diǎn)是具有較短平均路徑長度的樣本.同時(shí)，隔離森林也可以被視為子空間方法，因?yàn)樗惴ǖ脑u(píng)分函數(shù)量化了局部低維子空間分割特定點(diǎn)的容易程度，即越容易被分割的數(shù)據(jù)越有可能是離群點(diǎn)[12].但隔離森林在構(gòu)造隔離樹的過程中，選擇根節(jié)點(diǎn)樣本和選擇切割點(diǎn)時(shí)隨機(jī)性較強(qiáng)，可能導(dǎo)致構(gòu)造隔離樹的屬性為無關(guān)屬性，影響隔離樹的性能，當(dāng)存在較多無關(guān)屬性時(shí)，會(huì)影響算法準(zhǔn)確率和效率.

本文針對隔離森林算法的上述缺陷，提出了一種新的基于隔離森林的快速離群點(diǎn)檢測算法FIF(Fast Isolation Forest).該算法首先根據(jù)所選根節(jié)點(diǎn)樣本的數(shù)據(jù)分布，確定該樣本集是否可能存在離群點(diǎn)，若不存在則不需構(gòu)建隔離樹，從而有效地避免無關(guān)隔離樹對最終結(jié)果產(chǎn)生的影響；其次，在隔離樹構(gòu)建過程中，采用確定性的方法選擇分割點(diǎn)，可以有效地降低隨機(jī)選擇對算法性能的影響；然后將隔離出的每個(gè)葉子節(jié)點(diǎn)的平均路徑長度進(jìn)行歸一化，歸一化后的結(jié)果即為離群值，將離群值最大的若干個(gè)數(shù)據(jù)對象視為離群點(diǎn)；最后采用UCI數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的正確性和有效性.

2 相關(guān)工作

2.1 隔離森林算法及相關(guān)概念

Isolation Forest主要利用集成學(xué)習(xí)的思路來檢測離群點(diǎn)，它和隨機(jī)森林類似，都是通過構(gòu)建多棵決策樹形成森林來對數(shù)據(jù)進(jìn)行劃分.但隔離森林每次選擇劃分屬性和劃分點(diǎn)(值)時(shí)都是隨機(jī)的，而不是根據(jù)信息增益或基尼指數(shù)來選擇.隔離樹(Isolation tree)是一種特殊的二叉樹，它把一維空間中的二分查找樹擴(kuò)展到了多維空間中，因此可以用于索引多維數(shù)據(jù)，在建樹過程中，如果一些樣本很快就到達(dá)了葉子節(jié)點(diǎn)(即葉子到根的距離很短)，則有很大概率是離群點(diǎn).因?yàn)槟切┞窂奖容^短的樣本，都是距離主要的樣本點(diǎn)分布中心比較遠(yuǎn)的，也就是說，可以通過計(jì)算樣本在所有樹中的平均路徑長度來尋找異常點(diǎn)，該算法不依賴于近鄰查詢，也不需要計(jì)算距離，比傳統(tǒng)的離群點(diǎn)檢測算法更適合處理高維數(shù)據(jù).

隔離森林算法中每個(gè)隔離樹都是一個(gè)二叉樹結(jié)構(gòu)，其構(gòu)造步驟是首先從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇若干樣本點(diǎn)作為子樣本，放入樹的根節(jié)點(diǎn).其次隨機(jī)指定一個(gè)維度，在當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中隨機(jī)產(chǎn)生一個(gè)位于當(dāng)前節(jié)點(diǎn)數(shù)據(jù)中指定維度的最大值和最小值之間的切割點(diǎn)，然后以此切割點(diǎn)生成一個(gè)超平面，將當(dāng)前節(jié)點(diǎn)數(shù)據(jù)劃分為兩個(gè)子空間：把指定維度里小于該切割點(diǎn)的數(shù)據(jù)放在當(dāng)前節(jié)點(diǎn)的左子樹，把大于等于該切割點(diǎn)的數(shù)據(jù)放在當(dāng)前節(jié)點(diǎn)的右子樹.在葉子節(jié)點(diǎn)中遞歸重復(fù)以上過程，不斷構(gòu)造新的葉子節(jié)點(diǎn)，直到當(dāng)前節(jié)點(diǎn)的高度超過了算法設(shè)置的閾值；或當(dāng)前子樹只包含一個(gè)葉節(jié)點(diǎn)；或當(dāng)前子樹的所有節(jié)點(diǎn)值的所有屬性完全一致.

隔離樹全部構(gòu)造完成之后，算法訓(xùn)練階段結(jié)束，需要用測試數(shù)據(jù)來評(píng)估生成的隔離森林.令訓(xùn)練數(shù)據(jù)遍歷每一棵隔離樹，計(jì)算該數(shù)據(jù)點(diǎn)最終落在每個(gè)樹第幾層，可以得出其在每棵樹的高度平均值，平均高度值低于閾值的數(shù)據(jù)即為候選離群數(shù)據(jù).文獻(xiàn)[13]給出了計(jì)算離群值的方法：

(1)

其中，h(x)是數(shù)據(jù)點(diǎn)x從根節(jié)點(diǎn)到x所在葉子節(jié)點(diǎn)的路徑長度，E(h(x))是所有隔離樹集合的h(x)的平均值，c(m)指的是二叉搜索樹中搜索不成功的平均路徑長度：

(2)

其中H(i)為諧波數(shù)，通過ln(i)+0.5772156649(歐拉常數(shù))來計(jì)算，公式(1)用c(m)來歸一化h(x).若s接近于1，則它是離群點(diǎn)，若s遠(yuǎn)小于0.5，則它是正常點(diǎn).

隔離森林是目前離群點(diǎn)檢測比較常用的算法之一，它對內(nèi)存要求較低，處理速度快，具有線性時(shí)間復(fù)雜度.因?yàn)槊靠脴涠际腔ハ嗒?dú)立生成的，可以部署在大規(guī)模分布式系統(tǒng)上來加速運(yùn)算，所以能夠適應(yīng)大規(guī)模數(shù)據(jù)的處理需求.

2.2 隔離森林相關(guān)改進(jìn)算法分析

目前針對隔離森林的改進(jìn)方法主要包括：文獻(xiàn)[14]提出一種名為SCiForest的檢測算法，該算法通過引入隨機(jī)生成的超平面構(gòu)建模型，以便找到將離群點(diǎn)與正常點(diǎn)區(qū)分的合適投影來檢測局部聚類離群點(diǎn)，但該算法相對于原隔離森林算法運(yùn)行時(shí)間較長.文獻(xiàn)[15]提出了一種名為Half-Space-Trees的檢測算法，該方法針對數(shù)據(jù)流離群點(diǎn)檢測構(gòu)造了一個(gè)半空間隔離樹，在選擇切割點(diǎn)時(shí)使用所選屬性的中點(diǎn)，將工作空間平分為兩個(gè)半空間，從而創(chuàng)建節(jié)點(diǎn)的左右子節(jié)點(diǎn).節(jié)點(diǎn)持續(xù)迭代，直到達(dá)到設(shè)定的最大深度，并根據(jù)質(zhì)量概念使用滑動(dòng)窗口對數(shù)據(jù)進(jìn)行離群評(píng)分.文獻(xiàn)[16]則針對隔離森林對局部離群點(diǎn)不敏感的缺點(diǎn)，提出了一種名為ReMass-IForest的檢測算法，該算法使用基于局部相對質(zhì)量的評(píng)估方法來對隔離出的數(shù)據(jù)進(jìn)行排序，以檢測局部離群點(diǎn).上述各改進(jìn)算法和原隔離森林算法采取的屬性選擇方式隨機(jī)性較強(qiáng)，并且在大數(shù)據(jù)集的離群點(diǎn)檢測方面用時(shí)較長.本文接下來的內(nèi)容將針對隔離樹在構(gòu)建過程中的分割屬性和分割點(diǎn)問題以及如何快速完成檢測展開討論，引入新的基于隔離森林的快速檢測算法，以提高離群點(diǎn)檢測的效率.

3 快速隔離森林算法

3.1 算法思想

針對隔離森林算法在構(gòu)建隔離樹分割屬性和分割數(shù)據(jù)時(shí)隨機(jī)性較強(qiáng)的問題，F(xiàn)IF重新定義隔離樹，首先在構(gòu)建隔離樹采樣時(shí)，對采樣數(shù)據(jù)的數(shù)據(jù)分布進(jìn)行分析，決定是否利用此樣本集構(gòu)造隔離樹，以避免隨機(jī)選擇的根節(jié)點(diǎn)中包含較多沒有離群點(diǎn)的樣本集而對算法性能造成影響；然后在構(gòu)造隔離樹時(shí)，采用特定的切割點(diǎn)將數(shù)據(jù)分成兩個(gè)子空間，比切割點(diǎn)大的放入右子樹，小的放入左子樹，這樣做的目的同樣是將隨機(jī)選擇切割點(diǎn)對算法的影響降低，并且可以加快隔離樹的迭代.遞歸上述操作直到當(dāng)前子樹只包含一個(gè)節(jié)點(diǎn)或達(dá)到預(yù)設(shè)的樹高，此時(shí)一棵隔離樹構(gòu)建完成.將若干隔離樹組成隔離森林，然后計(jì)算每個(gè)被分割出的樣本點(diǎn)在所有隔離樹上的平均路徑長度，將平均路徑長度歸一化后作為樣本數(shù)據(jù)的離群值，選擇離群值最高的前若干個(gè)數(shù)據(jù)點(diǎn)作為最終的離群點(diǎn)進(jìn)行輸出.

在隔離樹的構(gòu)建過程中，選擇合適的根節(jié)點(diǎn)樣本和屬性分割值對算法至關(guān)重要，它們直接決定隔離樹的性能.

定義(隔離樹)：給定一組數(shù)據(jù)集D，隨機(jī)選擇X個(gè)樣本點(diǎn)作為隔離樹根節(jié)點(diǎn)子樣本，再隨機(jī)選擇其中一維作為切割屬性，在基于統(tǒng)計(jì)學(xué)的參數(shù)方法中，一元數(shù)據(jù)通常假定數(shù)據(jù)由高斯分布產(chǎn)生，且樣本點(diǎn)離估計(jì)的分布均值超過三倍標(biāo)準(zhǔn)差的概率值很低，因此，由輸入的根節(jié)點(diǎn)樣本數(shù)據(jù)學(xué)習(xí)高斯分布的參數(shù)，若含有概率低的點(diǎn)，則說明可能存在離群值.用最大似然方法估計(jì)參數(shù)均值μ和標(biāo)準(zhǔn)差σ：

(3)

其中n是隔離樹根節(jié)點(diǎn)樣本數(shù)，在高斯分布的假定下，μ±3σ區(qū)域包含99.7%的數(shù)據(jù)，所以若有數(shù)據(jù)點(diǎn)落在此區(qū)域外則所選根節(jié)點(diǎn)樣本中很可能包含離群點(diǎn)，若滿足公式(4)，則選取X放入樹的根節(jié)點(diǎn)：

maxValue>μ+3σ

(4)

其中maxValue代表樣本集中的最大值，若不滿足條件，則不再利用該子樣本創(chuàng)建隔離樹，而是將此樹設(shè)計(jì)為一棵空樹.這樣做的目的是將可能影響隔離效果的樹去除，既可以提高算法準(zhǔn)確率，又能降低原隔離森林算法的運(yùn)算時(shí)間.在選擇切割點(diǎn)時(shí)，取樣本數(shù)據(jù)最大值與最小值之間的黃金分割點(diǎn)作為切割點(diǎn)，以減小切割時(shí)的隨機(jī)性并且黃金分割點(diǎn)切割能夠讓隔離樹在生成子空間時(shí)每次都切割為與樣本父節(jié)點(diǎn)均等比例的大小兩棵左右子樹，使構(gòu)造子樹時(shí)迭代速度加快.遞歸上述過程直到當(dāng)前子樹只包含一個(gè)節(jié)點(diǎn)或達(dá)到預(yù)設(shè)的樹高，這里將此樹定義為隔離樹.

構(gòu)建隔離樹時(shí)采用子采樣方法，因?yàn)楫?dāng)樹的根節(jié)點(diǎn)樣本太多時(shí)，包含正常點(diǎn)過多，正常點(diǎn)過于接近離群點(diǎn)導(dǎo)致算法隔離異常點(diǎn)所需的樹高增加，分割離群點(diǎn)的子空間加深，隔離樹分割離群點(diǎn)的能力降低，而采用子采樣方法即可減少上述影響.隔離樹通常是不平衡二叉樹，因?yàn)槌砻軈^(qū)域的數(shù)據(jù)點(diǎn)往往需要多次分裂才能被完全隔離，而稀疏區(qū)域的數(shù)據(jù)僅需幾次分裂就能被完全隔離.因此，數(shù)據(jù)點(diǎn)的離群程度等于其在隔離樹中的深度，并用公式(1)計(jì)算每個(gè)樣本的離群值.如果數(shù)據(jù)集包含局部離群點(diǎn)，則將若干隔離樹組成隔離森林后，把基于路徑長度的全局排名度量替換為基于相對質(zhì)量的局部排名度量.在隔離樹結(jié)構(gòu)中，數(shù)據(jù)點(diǎn)的相對質(zhì)量是直接父節(jié)點(diǎn)和該點(diǎn)落入的葉節(jié)點(diǎn)的質(zhì)量比，而數(shù)據(jù)的質(zhì)量定義為一定區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)個(gè)數(shù).為了能夠增強(qiáng)隔離森林的局部離群點(diǎn)檢測能力，可以用相對質(zhì)量來評(píng)估離群值，參照文獻(xiàn)[16]，數(shù)據(jù)點(diǎn)x的異常分?jǐn)?shù)可以估計(jì)為數(shù)據(jù)質(zhì)量的比率，如公式(5)所示：

(5)

與原隔離森林算法相同，樣本的路徑長度即平均高度以logn的速度增長，此時(shí)離群得分歸一化不是有界的，不能直接比較，所以單個(gè)數(shù)據(jù)點(diǎn)在某棵隔離樹的離群得分由公式(1)計(jì)算得到，樣本最終的離群得分可以估算為各隔離樹上的離群分?jǐn)?shù)的平均值，如公式(6)所示：

(6)

對給定數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行評(píng)分，就可以按其離群值分?jǐn)?shù)的降序?qū)?shù)據(jù)點(diǎn)進(jìn)行排序.當(dāng)離群值越接近1時(shí)，該數(shù)據(jù)點(diǎn)是離群點(diǎn)的概率越大，當(dāng)離群值遠(yuǎn)遠(yuǎn)小于0.5時(shí)，該數(shù)據(jù)點(diǎn)將不是明顯的離群點(diǎn).最后選取離群值最高的前若干個(gè)數(shù)據(jù)點(diǎn)作為離群點(diǎn).

3.2 算法描述

算法的具體步驟如下：

1)構(gòu)造隔離樹

算法：iTree

輸入：數(shù)據(jù)集D，樣本點(diǎn)數(shù)量X，樹高度限制l，當(dāng)前樹高e，

輸出：隔離樹

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

1)if e>=l or |x|<=1 then

2) return exNode

/*選擇切割屬性*/

3)else

4) 隨機(jī)選擇切割屬性q∈X

/*確定當(dāng)前樣本是否適合建樹*/

5) if maxValue<=μ+3σthen

6) 返回空樹

7) else

/*選擇黃金分割點(diǎn)作為切割點(diǎn)p*/

8) p=(maxValue-minValue)*0.382+minValue

9) Xl=filter(X,q

10) Xr=filter(X,q>=p)

/*遞歸構(gòu)造隔離子樹*/

11) return inNode{Left = iTree(Xl,e + 1,l),

12) Right = iTree(Xr,e + 1,l),

13) SplitAttr= q,

14) SplitValue = p}

15) end if

16)end if

2)構(gòu)造隔離森林

與原隔離森林相同，給定一個(gè)包含n條記錄的數(shù)據(jù)集D，隨機(jī)采樣一部分?jǐn)?shù)據(jù)來構(gòu)造每一棵樹，保證不同隔離樹之間的差異性，然后將構(gòu)建好的隔離樹組成隔離森林.

隔離森林的組建過程如下：

輸入：數(shù)據(jù)集D,樣本數(shù)量X,隔離樹的數(shù)量t,限制樹的高度為l

輸出：隔離森林

1)初始化森林

2)fori=1 totdo

3)D′=sample(D,X)

4)Forest=Forest∪iTree(D′,0,l)

5)end for

6)return Forest

隔離森林構(gòu)造完成之后，計(jì)算被隔離的樣本在每棵隔離樹的離群得分，樣本在各隔離樹的平均得分即為該點(diǎn)的最終離群分?jǐn)?shù)，將離群得分最高的若干數(shù)據(jù)點(diǎn)確定為離群點(diǎn).

3.3 算法復(fù)雜性分析

本文算法主要分為兩個(gè)階段，第一階段為構(gòu)造隔離樹，第二階段為組合隔離森林并計(jì)算離群值，對于包含n個(gè)點(diǎn)的數(shù)據(jù)集，構(gòu)造隔離樹平均情況下時(shí)間復(fù)雜度為O(n·log(n))，每棵隔離樹所需要的空間復(fù)雜度為O(n).在最壞的情況下時(shí)間復(fù)雜度為O(n2).算法整體的時(shí)間復(fù)雜度為O(t(n+φ)logφ).為了使算法更有效，通常采用子采樣策略，原因是大樣本會(huì)影響隔離效果，當(dāng)正常點(diǎn)過多時(shí)，正常點(diǎn)與異常點(diǎn)距離太近導(dǎo)致隔離異常點(diǎn)所需的路徑長度變長，不利于隔離樹的構(gòu)造.子采樣方法需要單獨(dú)的測試階段才能對數(shù)據(jù)點(diǎn)進(jìn)行評(píng)分，測試階段算法的時(shí)間復(fù)雜度和空間復(fù)雜度是恒定的，且都為O(n).若把整個(gè)數(shù)據(jù)集都放入隔離樹根節(jié)點(diǎn)，則測試階段每個(gè)數(shù)據(jù)點(diǎn)的平均時(shí)間復(fù)雜度為O(log(n)).改進(jìn)算法與原隔離森林同樣都不涉及距離的計(jì)算，且改進(jìn)算法去除了可能含有干擾屬性的隔離樹，大大減少了計(jì)算開銷.

4 實(shí)驗(yàn)結(jié)果與分析

基于上述思想，對本文提出的算法進(jìn)行性能測試.實(shí)驗(yàn)平臺(tái)配置為Intel core i7 8550U CPU，16G內(nèi)存，64位操作系統(tǒng)的PC機(jī)，算法程序使用Python語言在Anaconda3 Spyder平臺(tái)實(shí)現(xiàn).

4.1 UCI數(shù)據(jù)集

為了驗(yàn)證所提方法的有效性，使用UCI機(jī)器學(xué)習(xí)庫1http://www.ics.uci.edu和ODDS(異常檢測數(shù)據(jù)集)2http://odds.cs.stonybrook.edu的11個(gè)真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn).它們包含已知的離群點(diǎn)作為基礎(chǔ)事實(shí)，且在其他離群點(diǎn)檢測的文獻(xiàn)中被多次使用.數(shù)據(jù)預(yù)處理階段進(jìn)行Z-S標(biāo)準(zhǔn)化處理，只保留連續(xù)型數(shù)值屬性.

表1 選擇的UCI數(shù)據(jù)集
Table 1 UCI dataset used in the experiment

數(shù)據(jù)集數(shù)據(jù)量維數(shù)離群數(shù)據(jù)占比/%Http(KDDCUP)56749730.4Shuttle4909797Breastw683935Arrhythmia45227815StatlogShuttle14500920.84Musk30621663.2Optdigits5216643WBC278305.6Mammography1118362.32Pima768835Smtp9515630.03

數(shù)據(jù)具體屬性如表1所示，其中Http(kddcup)和Smtp是網(wǎng)絡(luò)入侵檢測數(shù)據(jù)，Shuttle是飛機(jī)的飛行數(shù)據(jù)，樣本由兩種類別構(gòu)成，實(shí)驗(yàn)將相對較少的第二類樣本標(biāo)記為離群點(diǎn)，Breastw是威斯康星的乳腺癌診斷數(shù)據(jù)，其中惡性腫瘤占35%，實(shí)驗(yàn)將此類樣本標(biāo)記為離群點(diǎn).Statlog Shuttle數(shù)據(jù)集中第二類中有3022個(gè)數(shù)據(jù)，約占20%，將這些數(shù)據(jù)點(diǎn)作為離群值.Arrhythmia是具有279個(gè)維度的多分類心律失常數(shù)據(jù)集.本實(shí)驗(yàn)去除五個(gè)分類屬性，共274個(gè)屬性.將其中數(shù)據(jù)量較小的3，4，5，7，8，9，14，15類組合作為離群點(diǎn).Musk是麝香數(shù)據(jù)集，將非麝香類j146，j147和252作為正常點(diǎn)，而麝香類213和211作為離群值，并將其他類舍棄.Optdigits是光學(xué)識(shí)別手寫數(shù)字?jǐn)?shù)據(jù)集，數(shù)字1-9作為正常點(diǎn)，150個(gè)數(shù)字0的樣本作為異常點(diǎn).WBC數(shù)據(jù)集有兩個(gè)類，良性和惡性.將該數(shù)據(jù)集的惡性類作為離群點(diǎn).Mammography數(shù)據(jù)集有11183個(gè)樣本，其中260個(gè)為鈣化，將鈣化的少數(shù)類作為是異常類，非鈣化類作為正常類.

4.2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

本節(jié)對所提出的算法進(jìn)行性能評(píng)估，與其他9種離群點(diǎn)檢測算法進(jìn)行AUC(Area Under Curve)對比并畫出ROC(Receiver Operating Characteristic Curve)曲線，計(jì)算AUC[17]的公式(7)如下：

(7)

其中M和N分別是正樣本的個(gè)數(shù)和負(fù)樣本的個(gè)數(shù)，rankinsi代表第i條樣本的序號(hào)(概率得分從小到大排，排在第rank個(gè)位置).∑insi∈positiveclass表示只把正樣本的序號(hào)加起來.在ROC曲線中，AUC的值就是曲線下方的面積.AUC越接近1，說明算法效果越好，AUC低于0.5，則說明算法性能比隨機(jī)檢測效果差.

4.2.1 根節(jié)點(diǎn)采樣大小X對AUC的影響

本節(jié)實(shí)驗(yàn)采用數(shù)據(jù)量大于10000的數(shù)據(jù)集對不同的X進(jìn)行實(shí)驗(yàn)，因?yàn)楫?dāng)根節(jié)點(diǎn)采樣較大時(shí)，數(shù)據(jù)量小的數(shù)據(jù)集將不再是子采樣，而是利用全部數(shù)據(jù)構(gòu)造隔離樹.實(shí)驗(yàn)結(jié)果如圖1所示.

圖1 采樣數(shù)X對算法AUC的影響Fig.1 AUC impact of X

由圖1可知，F(xiàn)IF算法在各數(shù)據(jù)集上的AUC在初始階段隨根節(jié)點(diǎn)樣本數(shù)X的增大而增加，由于離群點(diǎn)只占整個(gè)數(shù)據(jù)集中非常小的一部分，當(dāng)采樣數(shù)很小時(shí)，所構(gòu)造的隔離樹往往不包含離群點(diǎn)，此時(shí)算法無法完成有意義的檢測.從實(shí)驗(yàn)結(jié)果可以看出，采樣數(shù)X為16時(shí)，AUC已逐漸趨于收斂.這是因?yàn)閄為16時(shí)隔離樹已經(jīng)具備將數(shù)據(jù)切割為多層子空間的能力，計(jì)算離群值的歸一化方法可以將較長和較短的路徑長度數(shù)據(jù)點(diǎn)進(jìn)行有效區(qū)分.當(dāng)樣本數(shù)為256時(shí)AUC接近最大值，與原隔離森林算法相同，算法在X很小時(shí)就能得到很快收斂且樣本較小時(shí)構(gòu)造隔離樹所需的時(shí)間較短，小樣本的隔離樹還可以適當(dāng)減輕高維數(shù)據(jù)中掩蔽效應(yīng)對精度的影響.因此不需要一直增加X.因?yàn)檫^度增加X只會(huì)使時(shí)間和空間復(fù)雜度增加，且樣本數(shù)量很大時(shí)包含正常點(diǎn)過多，正常點(diǎn)與離群點(diǎn)距離接近會(huì)干擾隔離過程，導(dǎo)致算法精度下降.由于本文算法要先分析所選樣本的數(shù)據(jù)分布再?zèng)Q定是否構(gòu)建隔離樹，所以若樣本太小則很有可能其中不包含離群點(diǎn)，無法完成有意義的隔離樹構(gòu)建.因此選擇256作為根節(jié)點(diǎn)樣本集的大小，既可以使隔離樹在構(gòu)建時(shí)能多次切割將離群點(diǎn)和正常點(diǎn)分割，又能避免大數(shù)據(jù)量造成的淹沒和掩蔽效應(yīng).

4.2.2 隔離樹數(shù)量t對AUC的影響

采用與4.2.1節(jié)中同樣的方法對不同的t進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2所示.

由圖2可知，算法在五個(gè)數(shù)據(jù)集上的AUC初期隨隔離樹的數(shù)量t增加而增加，且算法AUC在t很小時(shí)即可收斂且對于t的增加算法性能不敏感，因此，為了使算法效率提高，可以設(shè)置較小的t，但隔離森林算法本身依賴于集成學(xué)習(xí)的聚合能力.一棵樹可能不是最優(yōu)的，多棵樹集合就能發(fā)揮強(qiáng)大的性能.FIF在選擇隔離樹樣本時(shí)，會(huì)根據(jù)樣本分布選擇可能含有離群點(diǎn)的子樣本集進(jìn)行隔離樹的構(gòu)建，當(dāng)選到可能不包含離群點(diǎn)的子樣本集時(shí)，會(huì)將此樹變?yōu)榭諛洌瑸榱吮苊廨^小的t可能只產(chǎn)生少量的有效隔離樹而對最終的結(jié)果產(chǎn)生不良影響，

圖2 隔離樹數(shù)量t對算法AUC的影響Fig.2 AUC impact of t

我們要保證樹的數(shù)量不能太小，從多次實(shí)驗(yàn)可以看出，在100棵隔離樹時(shí)既可保證算法能構(gòu)造出一定數(shù)量的有效隔離樹，又能確保時(shí)間和空間消耗在很小的范圍內(nèi)，同時(shí)體現(xiàn)出集成方法的組合特性.若無特殊說明，實(shí)驗(yàn)中采用t=100作為默認(rèn)值，可同時(shí)兼顧精度和效率.而對于樹的高度限制l，隔離樹作為一棵二叉樹，是將較早被隔離出的數(shù)據(jù)視為離群點(diǎn)，越晚被隔離的點(diǎn)越有可能是正常點(diǎn)，因此不需要把所有的點(diǎn)都隔離，所以在根節(jié)點(diǎn)采樣數(shù)為256時(shí)，將樹高限制為8，使算法時(shí)間和空間消耗較少.

4.2.3 各算法AUC及運(yùn)行時(shí)間對比

本節(jié)的目的是對10種離群點(diǎn)檢測算法的AUC進(jìn)行比較.對于原隔離森林算法和本文改進(jìn)算法，我們采用默認(rèn)參數(shù)：創(chuàng)建100棵隔離樹，每棵樹256個(gè)樣本，樹高限制為8.在4.2.1和4.2.2節(jié)中已做出分析，結(jié)果表明在該默認(rèn)參數(shù)設(shè)置下檢測性能接近最優(yōu).KNN算法使用距離第一個(gè)k最近鄰居的距離作為離群值得分，使用KNN默認(rèn)設(shè)置k=10.PCA[18]算法使用具有特征向量超平面的加權(quán)投影距離之和作為離群值得分.MCD使用馬氏距離作為離群值得分.基于密度的LOF算法在實(shí)驗(yàn)中設(shè)置常用的k=10.ABOD[19]在該實(shí)驗(yàn)中使用FastABOD并用10個(gè)鄰居來評(píng)估離群得分.FB算法是特征裝袋，本實(shí)驗(yàn)中采用10個(gè)LOF作為訓(xùn)練子模型.LSCP[20]是一種無監(jiān)督的并行異常檢測集合框架，本實(shí)驗(yàn)中使用平均最大值策略.

表2 各算法的AUC
Table 2 AUC of several algorithm

圖3 各算法ROC曲線Fig.3 ROC curve of several algorithm

表2展示了在11個(gè)數(shù)據(jù)集上各算法的AUC，并突出顯示了各數(shù)據(jù)集中兩個(gè)最高的AUC.其中HTTP和SMTP數(shù)據(jù)集因?yàn)閿?shù)據(jù)量較大，所以一些時(shí)間復(fù)雜度很高的算法不能完成有效檢測，表中用NA表示.通過比較各算法的AUC可以看出本文改進(jìn)的算法在Arrhythmia，WBC，Pima和Statlog Shuttle數(shù)據(jù)集上比原IForest算法AUC高，在其他數(shù)據(jù)集上略低于或與原IForest基本相同.FIF和IForest在很多數(shù)據(jù)集上表現(xiàn)優(yōu)于其他算法，且FIF，Iforest和MCD的表現(xiàn)較為穩(wěn)定.KNN，LOF和其他基于距離測量的算法受數(shù)據(jù)維度的影響很大.當(dāng)維度很高時(shí)，算法的效果并不理想.而FIF性能優(yōu)于其他算法是因?yàn)樵撍惴ㄍㄟ^找到可能存在離群點(diǎn)的子樣本集來構(gòu)造隔離樹，降低了原隔離森林算法中隨機(jī)效應(yīng)對實(shí)驗(yàn)結(jié)果產(chǎn)生的不良影響，使隔離樹分割出的子空間比隨機(jī)選擇屬性維度準(zhǔn)確率高，且計(jì)算離群值時(shí)可信度更高.

圖3展示了各算法在三個(gè)代表性數(shù)據(jù)集上的ROC曲線，它們分別是FIF與其他算法ROC曲線相近的圖像，比其他算法ROC曲線高的圖像和ROC曲線低于其他算法的圖像，其中虛線是本文算法，通過圖3可以看出，在Arrhythmia數(shù)據(jù)集上改進(jìn)算法ROC曲線與其他算法基本相同，在Shuttle數(shù)據(jù)集上ROC曲線下面積幾乎達(dá)到了1，比其他算法高很多，而在Statlog-shuttle數(shù)據(jù)集上的AUC僅低于MCD算法，這是因?yàn)榛诟綦x的檢測方法更傾向于極值，而數(shù)據(jù)集內(nèi)部區(qū)域存在離群點(diǎn)時(shí)，算法可能效果不佳，MCD方法則以多元高斯分布的形式將整個(gè)數(shù)據(jù)集建模為關(guān)于其均值的高斯分布，把每個(gè)方向按比例縮放到特征空間中，因此該高斯分布的所有不相關(guān)方向具有相同的方差.在這種情況下，將點(diǎn)與球面高斯中心的距離作為離群值得分對數(shù)據(jù)內(nèi)部含有離群點(diǎn)的數(shù)據(jù)集是非常有效的[12].但MCD算法在處理大數(shù)據(jù)集時(shí)構(gòu)造相似度矩陣并對角化在時(shí)間和空間復(fù)雜度方面都面臨巨大挑戰(zhàn).

圖4展示了本文算法與原算法及2.2節(jié)中介紹的三種改進(jìn)隔離森林算法在各數(shù)據(jù)集上運(yùn)行十次的總時(shí)間對比.由圖4可以看出，F(xiàn)IF的運(yùn)行時(shí)間與其他算法相比較快，在Shuttle，Breastw，Musk，Optdigits數(shù)據(jù)集上進(jìn)行十次實(shí)驗(yàn)的運(yùn)行時(shí)間比原算法快近十倍，在Http數(shù)據(jù)集上的時(shí)間比原算法快數(shù)百秒.SCiForest算法為了使正常簇和異常簇分割，要使用其設(shè)定分割選擇標(biāo)準(zhǔn)尋找最佳分裂點(diǎn)，而原算法則采用隨機(jī)分割，所以SCiForest比原算法稍慢.ReMass-iForest算法構(gòu)造隔離樹時(shí)使用和原算法相同的策略，因此與原算法具有相同的時(shí)間復(fù)雜度.但由圖4可以看到它的運(yùn)行時(shí)間比原算法稍快，這是由于原算法在子樹只包含一個(gè)節(jié)點(diǎn)時(shí)才停止構(gòu)造隔離樹，而ReMass-iForest在評(píng)估階段采用基于局部相對質(zhì)量的方式來檢測離群點(diǎn)，在構(gòu)建隔離樹過程中子樹的節(jié)點(diǎn)小于5時(shí)即停止分裂，因此該算法比原隔離森林算法稍快.而本文算法運(yùn)行時(shí)間最短的主要原因是FIF在構(gòu)建隔離樹時(shí)去除了可能不包含離群屬性的樹，只保留可能存在離群點(diǎn)的子樣本集構(gòu)造隔離樹，減少了構(gòu)造無關(guān)隔離樹的時(shí)間，并使用收斂較快的黃金分割點(diǎn)來切分葉子節(jié)點(diǎn)，而隔離森林本身作為一種子空間方法，可以將隔離樹看作隔離低維度的局部子空間中的集合，所以算法的微小修改也可用于快速發(fā)現(xiàn)低密度的子空間區(qū)域，使得算法在計(jì)算離群值時(shí)消耗的時(shí)間更少.

圖4 算法的運(yùn)行時(shí)間(以秒為單位)Fig.4 Run time(s)

5 結(jié)束語

本文提出了一種基于隔離森林的快速離群點(diǎn)檢測算法.該算法通過使用確定的分裂點(diǎn)，降低了隔離森林的隨機(jī)效應(yīng)，提高了算法準(zhǔn)確性；引入啟發(fā)式的根節(jié)點(diǎn)樣本選擇策略，找到可能包含離群點(diǎn)的子空間構(gòu)建隔離樹，避免了無關(guān)屬性對離群數(shù)據(jù)的影響，使算法在不降低精度的情況下提高隔離森林的效率.采用UCI數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證了算法的正確性和有效性.下一步的工作是實(shí)現(xiàn)算法的并行化，以適應(yīng)海量高維數(shù)據(jù).