融合孤立森林和局部離群因子的離群點檢測方法

凌 莉 程張玉 鄒承明

1(武漢工程職業(yè)技術學院信息工程學院 湖北 武漢 431400) 2(武漢理工大學計算機科學與技術學院 湖北 武漢 430070) 3(交通物聯網技術湖北省重點實驗室 湖北 武漢 430070)

0 引 言

離群點檢測作為數據挖掘技術下的一個重要子項，被廣泛應用于欺詐檢測和網絡入侵檢測[1]以及工業(yè)系統故障檢測[2]等。隨著信息檢索和數據挖掘技術的迅速發(fā)展，離群點檢測的相關的研究也在持續(xù)發(fā)展。近年來，提出了一系列離群點檢測方法，其中，孤立森林算法是由Liu等[3]提出的無監(jiān)督離群點檢測集成方法，因其時間復雜度低、精度高而受到工業(yè)界和學術界的廣泛關注。Staerman等[4]使用孤立森林來檢測功能數據中的異常，通過對函數空間的隨機劃分，解決了函數空間具有不同拓撲結構、異常曲線具有不同模態(tài)特征的問題。徐東等[5]提出了SA-iForest算法，利用模擬退火算法去除相似度高的孤立樹，選擇精度高和差異性大的孤立樹組成孤立森林然后用于檢測，在準確率、效率和泛化能力方面都有所提高。

局部離群因子是基于密度的經典離群點檢測算法，因其簡單性和有效性被廣泛應用于現實場景下的離群點檢測，如多工況過程故障檢測[6]。現有的研究在局部離群因子算法的基礎上主要針對以下三個方面進行了改進：① 為了提升算法的檢測效率，劉芳等[7]提出了快速的 Top-n 局部離群點檢測算法(MTLOF)，設計了融合索引結構和多層LOF上界的多粒度剪枝方法來提高檢測效率。② 為了提高LOF的精度，Tu等[8]提出了譜角和局部離群點(SALOF)算法，通過計算每個簇類中各數據點的k近鄰，得到所有數據點的可達距離和局部可達密度，并依據事先設置好的分割閾值得到數據點的異常概率。③ 針對LOF的超參數選擇問題，Xu等[9]提出了一種優(yōu)化方法，即聯合調整LOF超參數k進行離群點檢測的啟發(fā)式策略。

由于缺乏離群點的相關先驗知識，依賴于數據全局分布及先驗知識的傳統離群點檢測方法無法有效地檢測出離群點。局部離群因子通過計算給定數據點的局部偏差來發(fā)現離群點，擁有檢測局部離群點的優(yōu)勢并且不依賴于數據集的先驗知識及全局分布。通常，離群點在數據集中所占比例相對較小，而現有研究中基于局部離群因子衍生出的多數方法在檢測時需要計算所有數據點的lof值，算法效率受到了較大影響，使其無法適用于大規(guī)模多維數據集的離群點檢測。孤立森林擁有線性時間復雜度且對于全局離群點的識別有著較高的精度，但在應用于大規(guī)模多維數據集的檢測時，采用全局異常標準無法準確檢測出局部離群點，常常出現精度差和效率低等問題。因此，本文提出了FSIF-HDLOF方法，即利用優(yōu)化iForest剪枝方法最大限度地剪枝掉原始數據集的高密度空間數據點，輸出規(guī)模較小的離群點候選集用于優(yōu)化LOF的精確檢測，從而提升檢測的精度和效率。

1 相關工作

孤立森林算法是一種具有線性時間復雜度的無監(jiān)督離群點檢測方法。通過對原始數據集多次隨機采樣，再對每次采樣后的數據對象隨機選擇特征進行劃分構建等價于二叉搜索樹的孤立樹，最后形成孤立森林。

局部離群因子算法是一種基于數據密度的離群點檢測算法，聚焦在數據點的鄰域密度，將具有低密度的數據點視為離群點。LOF算法的一些主要概念如下：

定義1dist(di,dj)：表示數據點di到數據點dj的歐氏距離。

定義2k距離(k_dist(di))：將數據點di到其他數據點的距離從小到大排序，數據點di到第k個數據點的距離即為k距離。

定義3k距離鄰域(Nk(di))：到數據點di距離小于k_dist(di)的數據點集合。

定義4可達距離(reach_distk(dr,di))：數據點dr到數據點di的可達距離為數據點dr的k距離和數據點di到數據c點dr間距中的最大值。

定義5局部可達密度(lrd(di))：數據點di的k距離鄰域Nk(di)內的所有數據點到數據點di的平均可達距離的倒數。

定義6局部離群因子(lof(di))：數據點di的k距離鄰域Nk(di)中所有點的局部可達密度與數據點di的局部可達密度之比的平均數，定義為：

(1)

2 整體框架

圖1顯示了融合孤立森林與局部離群因子的離群點檢測方法的總體流程，主要包括以下兩個階段：

(1) 剪枝階段：將原始數據集輸入基于數據降維和閾值優(yōu)化的剪枝方法算法，利用NMIFS選出特征子集，然后對特征子集對應的所有數據點進行采樣構建孤立森林，再定義特征離群系數計算剪枝閾值得到離群點候選集。

(2) 檢測階段：利用基于信息熵加權的歸一化歐氏距離計算得到離群點候選集的距離矩陣，再利用DPCA聚類，根據所得簇類信息計算簇類近鄰數來設置LOF的超參數k近鄰，計算每個數據點的lof值。最后，結合數據點在剪枝階段所得的異常分數Score以及在精確檢測階段所得的lof值，通過加權融合的離群分數來確定最終離群點集。

圖1 融合孤立森林與局部離群因子的離群點檢測方法框架

3 FSIF剪枝方法

3.1 NMIFS數據降維優(yōu)化策略

由于大規(guī)模多維數據集的高度稀疏及噪聲較多等特殊性質，在使用孤立森林進行剪枝時，存在著兩點不足：① 大量的特征信息未被使用，算法可靠性降低；② 可能存在的大量噪聲或無關特征會影響孤立樹的構建，算法精確度不高。因此本文考慮在剪枝前采用數據降維方法對原始數據進行降維處理，以降低多維特征對構建孤立樹的影響并提升算法的效率。一般情況下，特征選擇需要結合數據標簽的使用，而進行離群點檢測的大規(guī)模多維數據集常無對應的標簽，因此需要從數據本身出發(fā)，理解數據特性及特征之間的關聯性，針對性地選擇適用的特征選擇方法。綜上，本文采用更適合現實應用場景的基于標準化互信息(Normalized Mutual Information，NMI)的無監(jiān)督式特征選擇算法[10]。

3.2 特征離群系數用于閾值優(yōu)化

通常，在一個特定的數據集中不同特征具有不同的實際含義，特征的數值范圍也會有差異，而離群點的存在則會影響每個特征的離散程度。因此，本文通過數據特征統計分析得到特征的離散程度，定義特征離群系數來度量數據集的離散度，并通過計算得到剪枝閾值。

定義特征fj的特征離群系數Disp_coe(fj)為：

(2)

通過特征離群系數向量即可計算得到剪枝閾值θD。式(4)中，DNorm-Top(s)是指采用Top()算法快速獲取Df中特征離群系數較大的s個值，s為NMIFS對D降維后Fs中特征的數量，調節(jié)因子α為區(qū)間[0.45, 0.55]之間的隨機數。通過孤立森林算法計算每個數據點的異常分數并降序排序，將前n×θD條具有較大異常分數的數據點歸入離群候選集。

(3)

(4)

4 HDLOF檢測方法

原始LOF存在一些明顯的不足，如通過歐氏距離計算點距沒有考慮數據集不同特征的重要程度，超參數k近鄰的隨機或者憑經驗選取，都會影響數據點的lof值計算，從而影響LOF對離群點檢測的準確性。因此，本節(jié)針對以上不足進行了改進，提出了基于鄰域優(yōu)化的局部離群因子算法(HDLOF)。改進后的算法使用更加精細的基于信息熵加權的歸一化歐氏距離來計算數據點之間的距離，超參數k近鄰的值采用基于DPCA聚類后簇類信息而計算所得的簇類近鄰數來設置，離群點由最終加權融合的離群分數確定。

4.1 基于鄰域優(yōu)化的局部離群因子精確檢測

4.1.1基于信息熵加權的歸一化歐氏距離

(5)

(6)

數據點di與數據點dj間的信息熵加權歐氏距離為H_dist(di,dj,wf)，計算式如式(7)所示。為消除特征之間的量綱影響，在信息熵加權的歐氏距離基礎上，對距離進行歸一化，最后數據點di與數據點dj間基于信息熵加權的歸一化歐氏距離如式(8)所示。

(7)

(8)

4.1.2基于密度峰值的超參數優(yōu)化策略

一般而言，數據集可以劃分為幾個簇類，而同一簇類的數據點相似度較高，每個簇類內數據點可設置相同的參數k，不同簇類的數據點可根據其所在簇類信息設置相應的參數k。Rodriguez等[11]2014年提出的快速密度峰值聚類算法(DPCA)能很好地識別任何形狀的簇類，具有很強的泛化能力。因此，本文利用該聚類算法對上一階段孤立森林剪枝方法輸出的離群點候選集進行快速聚類，并根據簇類結果，為不同簇類的數據點設置不同的超參數k。

DPCA聚類結束得到c個簇類中心以及數據點所屬簇類，統計可得各簇類數據點個數{s1,s2,…,sc}。本文提出了簇類近鄰數(cluster_k)的概念，將其設置為某個簇類中所有數據點的超參數k近鄰值，第i個簇類中數據點的簇類近鄰數表示為cluster_ki，對應計算式為式(9)，其中，si為第i個簇類中數據點的個數。

(9)

4.2 HDLOF精確檢測實現

本節(jié)結合剪枝階段所得數據點d的異常分數Score(d)以及本節(jié)精確檢測所得的lof(d)，根據式(10)計算得到數據點d最終的離群分數lof-Score(d)。其中，β為融合權重。在FSIF-HDLOF中，HDLOF用于精確檢測，具有更高可信度，因此賦予lof值較大權重，β建議取值范圍區(qū)間[0.7, 0.9]。

lof-Score(d)=(1-β)×Score(d)+β×lof(d)

(10)

HDLOF具體實現步驟如算法1所示。

算法1HDLOF檢測實現

輸入: 離群點候選集OC，數據點的平均異常分數Score(c)，異常數量m。

輸出: 離群點集OutlierSet(O)。

①HNorm_dist(ci,cj,wf)；

/*根據式(8)計算離群點候選集

的距離矩陣*/

② cluster_ki；

/*根據式(9)計算數據點的簇類近鄰數，即超

參數k值*/

③lof(c)； /*根據式(1)計算所有數據點的局部離群因子*/

④lof-Score(c)；

/*根據式(10)計算所有數據點最終離群分

數*/

⑤O； /*取lof-Score最大的Top(h)個數據點作為離群點*/

⑥ returnO

/*返回離群點集*/

5 實驗與結果分析

5.1 實驗數據與實驗環(huán)境

為了全面地評估算法性能，本文所有實驗均在以下介紹的五個不同規(guī)模數據集上進行。數據集Satellite、Mnist、Shuttle以及Smtp均來自于Outlier Detection DataSets (ODDS) 網站，其出現在很多文獻[3,12-13]上被用于評估離群點檢測算法的性能。五個數據集具體信息如表1所示。

表1 數據集的詳細信息

實驗環(huán)境：本文基于Python來處理數據集、實現剪枝和檢測算法及性能驗證，實驗均在同一筆記本電腦上運行。設備硬件配置為：Intel i5-3337U CPU @ 1.80 GHz 雙核四線程處理器，8 GB內存，Python版本為3.6.4。

5.2 評價指標

5.2.1剪枝精度評價指標

基于數據降維和閾值優(yōu)化的孤立森林作為FSIF-HDLOF的剪枝方法，其目的是在保證離群點不被剪枝掉的情況下，剪枝掉盡可能多的正常數據以減少后續(xù)LOF的計算量，從而提升整體的算法效率?？紤]到剪枝比例會在不同程度上影響LOF檢測的準確度，因此本文將同時使用剪枝占比和剪枝準確率來衡量剪枝算法的高效性和準確性。

剪枝準確率(Pruning Precision，PP)，即離群點候選集中真實離群點的數量與離群點候選集數據點總數的比值，公式為ρPP=ρTP/(ρTP+ρFP)。一般PP值越高，表示在離群點候選集中，真正的離群點所占比例越大，剪枝后留下的正常數據越少，剪枝效果越好。剪枝占比(Pruning Number，PN)是指被修剪數據點的百分比，即被剪枝掉的數據點數量與數據集數據點總數的比值。通常，在PP較高的情況下，PN越大，說明算法剪枝效果越好。

5.2.2檢測精度評價指標

大部分離群點檢測算法為無監(jiān)督形式，為了準確評估及對比不同算法的檢測效果，本文實驗所用數據集均為帶標簽數據集。因此，本文利用傳統的常用評價指標Precision和F1-Measure來評估離群點檢測算法的性能，其中F1-Measure是Precision和Recall加權調和平均，作為綜合評價指標更具有代表性。

5.3 實驗方法性能評估

為了驗證本文所提的FSIF-HDLOF對大規(guī)模多維數據集離群點檢測的有效性，將FSIF-HDLOF與離群點檢測領域上常用算法，如原始Isolation Forest(IF)、原始LOF、KMeans-LOF(K-LOF)[14]和R1SVM[15]這五個方法在五個不同規(guī)模的數據集上進行對比實驗。其中，FSIF和K-Means分別用于FSIF-HDLOF和K-LOF算法剪枝階段。

5.3.1剪枝方法性能評估

剪枝方法FSIF和K-Means在數據集上的實驗結果如表2中所示，FSIF的剪枝準確性及剪枝占比均高于K-Means算法。分析發(fā)現，K-Means用于剪枝的思想是：聚類之后，根據某種規(guī)則將數據點數量少的簇類整體或者簇類中的部分數據點歸入離群點候選集。因此，這種剪枝方式極大容易受到聚類過程的影響，而K-Means的聚類結果往往具有很大的隨機性，造成了其用于剪枝的惡劣結果。孤立森林則相比使用了聚類思想的剪枝方法而言要優(yōu)勝許多。

表2 實驗方法在數據集上的剪枝性能

5.3.2融合方法性能評估

1) 檢測精度指標。圖2為上述五個算法在數據集上檢測結果的混淆矩陣，左縱坐標為數據集名稱，下橫坐標為五個算法，右縱坐標為檢測的標簽，上橫坐標為真實標簽，其中0代表離群點，1代表正常數據。每四個格子為一個算法對一個數據集的檢測結果。從圖2中可看出，五種算法均能檢測出絕大部分正常點(即TN)，但都存在著部分誤檢。其中，FSIF-HDLOF表現相對優(yōu)異，其所檢測的TN和TP總數均高于其他算法。

圖2 實驗方法在數據集上的混淆矩陣

圖3 實驗方法在數據集上的Accuracy、F1-Measure

圖3展示了五個對比算法在數據集上的Accuracy和F1-Measure結果，可以看到所提出的FSIF-HDLOF在不同數據集上都表現出了相比其他算法更好的性能和更加穩(wěn)定的檢測效果。特別地，對于大規(guī)模多維數據集ALOI和大規(guī)模數據集Smtp，其正常數據點與離群點的比例極其不平衡。分析可知，單一的離群點檢測方法對所有數據采用同一種異常標準，無法綜合考慮數據的全局和局部信息。當大規(guī)模多維數據集的正常點與離群點的比例極其不平衡時，采用統一標準的單一離群點檢測方法無法準確檢測出離群點。融合方法FSIF-HDLOF通過初步剪枝，使得離群點候選集的分布不再極端化，并結合數據的全局異常信息以及局部離群程度來綜合確定離群點，大大提高了極不平衡數據的檢測精度。

2) 運行時間成本。運行時間成本是指在標準軟硬件系統上進行離群點檢測所花費的時間，包括數據預處理時間和檢測計算時間。FSIF-HDLOF和K-LOF算法的預處理時間為FSIF和K-Means的剪枝耗時，R1SVM算法的預處理時間為數據集隨機化的耗時，而IF和LOF只有離群點檢測計算時間，在數據集上運行時間如圖4所示。 除Mnist數據集外，IF在剩余4個數據集上的運行速度最快，由此驗證了利用其對原始數據集進行剪枝的合理性。FSIF-HDLOF由于使用了LOF進行精確檢測，因此其效率不如IF，但因為結合IF的使用，其在大規(guī)模數據集Shuttle和ALOI上的檢測速度遠高于LOF。

圖4 實驗方法在數據集上的運行時間

6 結 語

在大規(guī)模多維數據集中，為了更有效地檢測離群點，本文提出一種新的融合方法。該方法融合iForest和LOF來檢測離群點，并針對剪枝階段iForest和檢測階段LOF的不足進行了相應改進。采用基于數據降維和閾值優(yōu)化的iForest對原始數據集進行剪枝，得到較小規(guī)模、高質量的離群點候選集待進一步精確檢測。基于離群點候選集，提出的閾值優(yōu)化局部離群因子方法能有效地檢測離群點。五個數據集用來評估本文算法的性能，與其他算法相比，本文算法檢測精度明顯優(yōu)于其他算法，實現了檢測精度與效率的良好平衡，在大數據量且低離群點比例的數據集ALOI和Stmp上優(yōu)勢更明顯。