劉俊成,董 東

(河北師范大學 計算機與網絡空間安全學院,河北 石家莊 050024)

0 引 言

隨著大數據時代的到來,離群點檢測成為國內外研究的熱點[1]。近年來,離群點檢測算法分為四種：基于統(tǒng)計、基于距離、基于密度以及基于聚類[2]。以箱線圖(BOXPLOT)[3]和基于連接函數的離群點檢測(COPula-based Outlier Detection,COPOD)算法[4]為代表的基于統(tǒng)計的方法,多數根據數據的分布去判斷離群點,模型一旦建立便可快速地完成檢測,該類方法適用于定量實值數據集。但因假設分布,在缺乏關于分布的先驗知識的情況下可應用性不高。K近鄰(K-Nearest Neighbor,KNN)算法[5],根據預先指定的距離度量,計算出樣本點之間的距離后排序,取最上層的樣本作為離群點。其不依賴于假設分布來擬合數據,與基于統(tǒng)計方法相比更適用于現實中分布多樣的數據集。但是算法的復雜度較高。LOF(Local Outlier Factor)算法[6]使用局部離群因子判別離群點,對局部離群點十分有效?；谙鄬γ芏鹊碾x群值檢測(Relative Density-based Outlier Source,RDOS)算法[7]引入相對密度來測量對象的局部離群值。離群點是聚類的副產品,對聚類算法DBSCAN[8]、CHAMELEON[9]、CLARANS[10]加以修改都可用于離群點檢測。這些方法大多通過考慮樣本點與簇之間的關系檢測離群點。該類方法為無監(jiān)督方法,從集群中學習后,可以插入額外的新點,這使其能適應增量模式,因此更適用于數據流中的離群點檢測。但該類方法大多需要事先指定簇的數量K,且檢測結果對于K值較敏感[11]。

隔離森林(Isolation Forest,iForest)算法[12]不依靠距離或密度作為相似度度量,而是通過隨機采樣的方式構建隔離樹,并利用離群點與正常點在隔離樹中深度不同這一特性去判別離群點。該算法的時間與空間復雜度很低,但對局部離群點的敏感性不高。針對該問題,結合LOF算法與iForest算法形成了一種兩階段離群點檢測算法[13]。首先,利用LOF算法進行離群點檢測,后使用iForest算法在其結果集中進行篩選。這樣提高了局部離群點檢測的準確率,但時間開銷太大[14]?；诟綦x森林的快速離群點檢測(Fast Isolation Forest,FIF)算法[15],根據根節(jié)點的數據分布篩選樣本子集避免無關隔離樹的產生,以及使用黃金切割法進行節(jié)點劃分,在保證準確率幾乎不變的情況下極大提高了iForest算法的效率。

擴展的隔離森林(Extended Isolation Forest,EIF)算法[16]使用隨機法向量與隨機截距確定分割超平面,解決了iForest算法的軸平行問題。但EIF算法時間開銷較大,且對局部離群點不敏感,易產生局部離群點被密度相似的簇掩蓋等問題?；陔S機子空間的隔離森林(Extended Isolation Forest based on Random Subspace,RS-EIF)算法[17],結合子空間的思想來創(chuàng)建隔離森林,相較于EIF算法減少約60%的時間開銷。廣義隔離森林(Generalized Isolation Forest,GIF)算法[18],首先將采樣數據全部投射到單位法向量上,然后在投影的最大最小值間選擇切割點,避免生成無效的空節(jié)點,提高了算法的效率。以上兩種算法雖然減少了EIF算法的時間消耗,但仍未解決局部離群點的掩蓋問題。

該文提出基于相對比重的擴展隔離森林(Relative Proportion-Extended Isolation Forest,RP-EIF)算法,不再根據樣本點在隔離樹中的路徑長度去判斷離群點,而是根據樣本點所在葉節(jié)點上的數據量與其直接父節(jié)點的數據量比重去判斷。這種基于相對比重的局部排名方式,優(yōu)化了EIF算法在局部離群點檢測上的不足,同時節(jié)省了算法的計算開銷,增加了其工程應用價值。

1 局部離群點

EIF算法根據樣本點在隔離森林中的平均路徑長度去判別離群點。這對全局離群點的檢測十分有效,原因是基于路徑長度的全局排名方式無法考慮到擁有特殊分布的局部離群點,導致局部離群點被掩蓋。在圖1中,a1、a2為局部離群點,簇C2的正常樣本點密度與局部離群點a1、a2的密度相似。這就導致C2中的一些邊緣樣本點可能會與a1、a2在隔離樹中擁有相同甚至是更短的平均路徑長度,導致EIF算法產生局部離群點掩蓋問題,降低其對局部離群點的敏感性。

圖1 局部離群點

2 PR-EIF算法

2.1 相對比重

相對比重(Relative Proportion)為隔離樹中葉節(jié)點的樣本量與父節(jié)點的樣本量之比。樣本點x的離群分數pi(x)定義為：

(1)

樣本x在森林上的最終離群得分P(X)是該樣本在每棵隔離樹上離群分數pi(x)的均值：

(2)

當對數據集中的每個樣本x完成離群得分的計算后,根據分數大小進行升序排序,最后選取前若干個樣本點作為離群點。

2.2 RP-EIF算法的實現過程

EIF算法在構建隔離樹時葉節(jié)點允許的最小樣本量為1。而RP-EIF算法使用考慮鄰域數據分布的局部排名方式,故設置葉子節(jié)點允許的最小樣本量為參數Minsize(默認值為5)。當節(jié)點上的樣本量小于等于5時,該節(jié)點便停止生長。由于超平面在N維空間中至少與一個維度至多與N個維度相交,故設置參數Exlevel,根據需要調整相交的維數。

為了方便計算子節(jié)點與父節(jié)點的樣本量比重,在隔離樹節(jié)點中增加parent屬性引用父節(jié)點。隔離樹的構建如算法1所示。

算法1：iTree(X,Height,e,MinSize=5,Exlevel)

輸入：X-當前的數據子集,Height-樹的高度限制(默認為log2(采樣量)),e-當前樹的高度,MinSize-節(jié)點允許的最小樣本數,Exlevel-擴展水平

輸出：二叉隔離樹

1. IFe≥Height orX的數據量≤MinSize THEN

3. left=null,righ=null,node_type=“葉子”)

4. ELSE

10. left←iTree(X1,Height,e+1,MinSize,Exlevel),

11. right←iTree(Xr,Height,e+1,MinSize,Exlevel),

12. node_type=“內部節(jié)點”)

13. END

隔離森林由n棵隔離樹組成,具體步驟如算法2所示。

算法2：rpForest (X,n,φ,Exlevel, MinSize=5)

輸入：X-數據集,n-隔離樹的數量,φ-隨機采樣的樣本個數,Exlevel-擴展水平,MinSize-節(jié)點允許的最小樣本數

輸出：隔離森林rpForest

1.隔離森林集合Forest初始化為空

2.設置每棵樹的高度限制Height為log2(φ)的上取整

3. FORi=1 TOnDO

4.Xsub←在X中隨機抽取φ個樣本點

5. Forest←iTree(Xsub,Height,e,MinSize=5,Exlevel)∪

6. Forest

7. END

離群分數的計算如算法3所示。

算法3：nodeSize (x,T)

輸入：x-一個樣本,T-一棵隔離樹

輸出：樣本x落入葉節(jié)點的直接父節(jié)點與該節(jié)點的樣本量比重

1. IFT為葉節(jié)點 THEN

2. 返回該節(jié)點上數據量與其直接父節(jié)點的數據量的比重

3. ELSE

7. 在節(jié)點的右子樹遞歸nodeSize(x,T.right)

8. ELSE

9. 在節(jié)點的左子樹遞歸nodeSize(x,T.left)

10. END

11. END

通過算法3得到樣本點x落在葉節(jié)點的數據量及其父節(jié)點的數據量比重,再根據公式(2)計算出最終離群分數,如算法4所示。

算法4：computeScore (test,iTree)

輸入：test-待預測的樣本集,iTree-一棵隔離樹

輸出：離群分數集合S

1.初始化一個離群分數的空集合S

2. FORi=0 TO 集合test的數據量 DO

3. FORj=0 TO 隔離樹的數量nDO

4. Score=Score+

5. END

6.S[i]=(Score/n)

7.返回離群分數集合S

8. END

3 實驗結果與分析

3.1 實驗環(huán)境

實驗均在CPU為AMD Ryzen 5 3500U,2.10 GHz,運行內存為16 GB,操作系統(tǒng)為Windows 10的PC機上進行。

采用PR-EIF算法、EIF算法、GIF算法、iForest算法4種基于樹型結構的建議參數[12]：創(chuàng)建100棵隔離樹、隨機采樣數為256。

COPOD算法無需設置任何參數[4]。最近鄰的數量達到10時LOF的標準差開始穩(wěn)定,同時考慮到時間消耗,因此將LOF算法最近鄰數設置為10[6]。

3.2 實驗數據集

為了更好地驗證RP-EIF算法在不同數據量不同維度數據集上的性能,本次實驗所選的5個數據集包括從低維度到高維度、低樣本量到高樣本量。數據集的具體屬性如表1所示。

表1 實驗所用數據集

Breastcancer為診斷乳腺癌數據集,選取其中10個惡性診斷作為離群點,所有的良性診斷作為正常點。Forest Cover為描述森林覆蓋的多分類數據集,在做離群點檢測時,第2類被認為是正常類,第4類為離群類,離群比例為0.9%。Ionosphere為電離層數據集,有一個屬性的值全為零,該屬性被丟棄,其中壞類被視為離群類,好類被視為正常類。Mammography為乳腺X光數據集共有11 183個實例,其中260個鈣化實例作為離群點。Satellite為Landsat衛(wèi)星數據集,2、3、4類作為離群類,其余所有類作為正常類。

3.3 評價指標

一般而言,離群點檢測可以看作樣本類別不均衡的二分類問題,因此實驗使用受試者工作特征曲線(Receiver Operating Characteristic,ROC)以及ROC曲線下面積(the Area Under the ROC,AUC)來評價算法的性能。

二分類問題結果分為4類：真正類(True Positive,TP)、真負類(True Negative,TN)、假正類(False Positive,FP) 、假負類(False Negative,FN)。ROC曲線的X軸為假正比例(False Postive Rate,FPR),即預測的正類中實際負實例占所有負實例的比例。Y軸為真正比例(True Positive Rate,TPR),即預測的正類中實際正實例占所有正實例的比例。假正比例與真正比例的計算見公式(3)、(4)。AUC代表ROC曲線下面積的大小,值域為[0,1],越接近1算法性能越優(yōu)秀。

(3)

(4)

3.4 局部離群點敏感性的驗證

對RP-EIF算法進行局部離群點敏感性驗證。為便于可視化,選取鳶尾花數據集的Sepal.Width、Petal.Width兩維度作為二維數據集進行實驗。首先對該數據集的局部離群點進行人工標注,標注局部離群點14個,共150個樣本點。標注后的數據集如圖2所示。可以看到數據集由兩個簇組成,人工標注的局部離群點分布在兩個簇的周圍。

圖2 實驗所用二維數據集

使用RP-EIF算法在該數據集上進行離群點檢測,根據離群分數升序排序選取前15個樣本點作為離群點。結果如圖3(a)所示。其中真正例14個,假正例1個。經計算可知,算法的局部離群點識別率為100%(真正例數量與離群點總數之比),識別準確率為93.3%(真正例數量與檢測出的離群點數之比)。

(a)RP-EIF算法檢測結果

同時,為了更好地展示算法離群分數的分布情況,這里繪制離群分數分布熱圖,如圖3(b)所示。越靠近簇的中心密集區(qū)域離群分數越高(注意該算法分數越低代表樣本點為離群點的可能性越大),而越靠近簇邊緣的稀疏區(qū)域離群分數越低。這說明RE-EIF算法在進行離群分數計算時,考慮到了數據的分布,對局部離群點具有較高的敏感性。

3.5 各算法AUC及運行時間對比

在5個ODDS數據集上驗證算法的準確率與算法效率。并與5種離群點檢測算法(EIF、GIF、iForest、COPOD、LOF)進行比較分析。

6種算法的ROC曲線如圖4所示。RP-EIF算法在5個ODDS數據集上的ROC曲線均優(yōu)于其他5種算法。其中在Forest Cover、Ionosphere、Mammography數據集上的ROC曲線明顯更靠近左上方。在圖4(a)中,可以發(fā)現6種算法在Breastcancer數據集上均可很好地識別離群點。

(a)Breastcancer數據集ROC曲線

由表2可知,RP-EIF算法相較于EIF算法,準確度從0.960提高到0.986,提高約3百分點,這是由于RP-EIF算法在離群分數計算階段使用相對比重的局部排名方式,考慮了數據點與其鄰域點的分布關系,使算法對局部離群點更加敏感。在圖4(e)中,5種算法在Satellite數據集上的離群點識別效果略差于其他4個數據集。但是RP-EIF算法在該數據集上準確率高出EIF算法、GIF算法、iForest算法、COPOD算法、LOF算法2～13百分點。

表2 各算法AUC

各算法的運行時間如表3所示。運行時間取5次運行結果的平均值作為最后結果。由表3可知,RP-EIF算法的運行時間比EIF算法快約30%。原因是RP-EIF算法在構建隔離樹的過程中,當節(jié)點上的樣本數小于或等于5時,該節(jié)點就停止生長。使RP-EIF算法的森林模型比EIF算法收斂更快。同時,在離群分數計算階段,RP-EIF算法無需根據條件調整返回的路徑長度,這也使算法的效率提高。GIF算法的運行時間略少于RP-EIF算法,這是由于GIF算法避免了隔離樹的空節(jié)點問題,使算法的效率提高,但是其準確率卻低于RP-EIF算法。而iForest算法的時間消耗少于RP-EIF算法,是由于RP-EIF算法需要進行大量的高維向量運算。但運行時間的略長,帶來的卻是準確率的顯著提高,在5個ODDS數據集上RP-EIF算法的準確率高出iForest算法5～14百分點?；诮y(tǒng)計的COPOD算法不需要計算相似性度量,模型一旦建立,便可快速完成檢測,因此其時間消耗在6個算法中最少。但其在高維或數據量大的數據集上檢測精度不佳?；诿芏鹊腖OF算法,在數據量較少時運行時間比RP-EIF算法略快。這是由于基于樹型結構的算法,無論數據的多少,都需要將每個待預測樣本點x遍歷森林中的每棵隔離樹,而LOF算法在數據量較少時可以很快得到局部離群因子,所以在數據量較少時LOF算法時間消耗較少。但LOF算法在數據集Mammography、Satellite上的時間消耗是RP-EIF算法的6～15倍。在大型數據集Forest Cover上由于LOF算法的復雜度過高無法完成有效檢測。

表3 各算法運行時間 s

4 結束語

隔離森林算法在大數據上識別離群點的表現出色?；谙鄬Ρ戎氐母拍?提出了基于相對比重的擴展隔離森林算法。優(yōu)化了算法在離群分數計算階段的排名方式,增強了算法對于局部離群點的敏感性,提高了算法的準確率與效率。在5個ODDS數據集使用RP-EIF算法進行離群點識別,并與5種離群點檢測算法(EIF算法、GIF算法、iForest算法、COPOD算法、LOF算法)進行了比較,驗證了RP-EIF算法在準確率與算法效率兩方面的有效性。在之后的工作中,計劃將算法應用于實際的大數據上,并進一步探索在深度森林上的表現。