基于雙向鄰居修正的局部異常因子算法

楊曉暉，劉曉明

（河北大學(xué)網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北 保定 071002）

1 引言

離群值檢測(cè)是數(shù)據(jù)挖掘領(lǐng)域的熱門(mén)話題，其任務(wù)是識(shí)別與大多數(shù)對(duì)象明顯不同的數(shù)據(jù)對(duì)象，這類數(shù)據(jù)與其他現(xiàn)有數(shù)據(jù)表現(xiàn)形式不一致，通常包含部分關(guān)鍵信息，且信息不易被發(fā)現(xiàn)，但是具有很高的研究和應(yīng)用價(jià)值。離群挖掘是數(shù)據(jù)挖掘和數(shù)據(jù)分析的重要分支，已廣泛應(yīng)用于欺詐檢測(cè)[1]、垃圾郵件檢測(cè)[2]、交通異常[3]、網(wǎng)絡(luò)流量異常檢測(cè)[4]、入侵檢測(cè)[5-6]和社交網(wǎng)絡(luò)異常用戶發(fā)現(xiàn)[7]等領(lǐng)域。大多數(shù)現(xiàn)有的解決方案通常從全局角度來(lái)識(shí)別離群值，這不適用于高維和海量數(shù)據(jù)集[8-9]。隨著獲取信息技術(shù)的發(fā)展和高維、海量數(shù)據(jù)的爆炸性增長(zhǎng)，采用傳統(tǒng)方法進(jìn)行全局異常值檢測(cè)將非常困難。

2 相關(guān)工作

離群值，即數(shù)據(jù)中的不合理值，可以由不同的機(jī)制產(chǎn)生?，F(xiàn)有檢測(cè)算法主要分為基于統(tǒng)計(jì)、基于深度、基于聚類、基于距離和基于密度的算法。

在基于統(tǒng)計(jì)的離群值檢測(cè)算法中，偏離標(biāo)準(zhǔn)分布的對(duì)象被認(rèn)為是離群值[10]，該類方法需要數(shù)據(jù)集相關(guān)的先驗(yàn)知識(shí)，不適用于高維或分布未知的數(shù)據(jù)集。

基于深度的離群值檢測(cè)算法[11-13]將數(shù)據(jù)分成不同層次，根據(jù)分層結(jié)果將外層或容易分層的對(duì)象判定為離群點(diǎn)，但該算法在高維數(shù)據(jù)集上的效率較低。

在基于聚類的離群值檢測(cè)算法中，距其聚類中心較遠(yuǎn)的某些數(shù)據(jù)對(duì)象被視為離群值[14]，算法必須建立聚類模型才能檢測(cè)離群值，因此檢測(cè)效率較低。

基于距離的離群值檢測(cè)算法因簡(jiǎn)單高效而被廣泛使用。在基于距離的異常檢測(cè)算法中，通過(guò)計(jì)算數(shù)據(jù)集中一個(gè)對(duì)象與其他對(duì)象之間的距離來(lái)發(fā)現(xiàn)異常值，但由于未考慮局部密度的變化，因此只能檢測(cè)全局異常值，無(wú)法檢測(cè)局部異常值[15]。

在基于密度的離群值檢測(cè)算法中，Breunig 等[16]定義了局部異常因子（LOF,local outlier factor）算法，通過(guò)將每個(gè)對(duì)象的密度估計(jì)值與其k個(gè)最近鄰居進(jìn)行比較來(lái)計(jì)算對(duì)象的離群程度。LOF 算法已經(jīng)廣泛使用，但是存在參數(shù)敏感問(wèn)題。為此，Ha 等[17]于2014 年提出一種不穩(wěn)定因子（INS,instability factor）算法，該算法通過(guò)控制參數(shù)靈活地用于局部和全局檢測(cè)異常值。當(dāng)參數(shù)改變時(shí)，INS 算法的準(zhǔn)確率變化很小，但是當(dāng)精度穩(wěn)定時(shí)，INS 算法精度并不高。

Jin 等[18]改進(jìn)了LOF 算法，并提出基于影響域的異常值（INFLO,influenced outlierness）檢測(cè)算法，對(duì)鄰居的使用比較直接，將正向鄰居和反向鄰居都視為同等作用，從而計(jì)算得出異常值。由于對(duì)鄰居的使用較簡(jiǎn)單直接，未考慮到最近鄰居的異常程度，因此精確度不高。

Zhu 等[19]定義自然鄰居（natural neighbor）及其搜索算法（nan-searching）來(lái)利用反向鄰居[20]，還定義自然影響空間（natural influence space）和自然鄰域圖（NNG,natural neighbor graph）[21]，并在后續(xù)工作中利用自然鄰居來(lái)約減鄰居、降低噪聲影響[22]。Ning 等[23]通過(guò)搜索互鄰圖（MNG,mutual neighbor graph）的穩(wěn)定狀態(tài)來(lái)找到合適的k值，雖然避免了參數(shù)的選取問(wèn)題，但在計(jì)算異常值時(shí)自然鄰居對(duì)鄰居的使用比較簡(jiǎn)單，且準(zhǔn)確率和效率較低。

因LOF 為無(wú)監(jiān)督算法，Auskalnis 等[24]提出了用于網(wǎng)絡(luò)入侵檢測(cè)的LOF 算法模型來(lái)檢測(cè)未知手段的攻擊。Na 等[25]提出了數(shù)據(jù)流異常檢測(cè)（DiLOF,distributed local outlier factor）算法，減少了存儲(chǔ)開(kāi)銷和時(shí)間開(kāi)銷，但是仍存在參數(shù)選取困難的問(wèn)題。Yao 等[26]提出了一種增量式局部離群值檢測(cè)模型，用于數(shù)據(jù)流中的異常檢測(cè)，雖然該模型使用了反向鄰居，但只是將反向鄰居作為鄰居擴(kuò)充，策略簡(jiǎn)單，檢測(cè)性能略低。Yang 等[27]提出了一種鄰居熵局部離群值因子（NELOF,neighbor entropy local outlier factor）)檢測(cè)模型，首先使用改進(jìn)的自組織特征圖（SOFM,self-organizing feature map）算法對(duì)數(shù)據(jù)集進(jìn)行聚類，然后進(jìn)行離群點(diǎn)檢測(cè)，精度略有提高，但因聚類算法的加入，效率較低。Gao 等[28]提出了一種基于多維數(shù)據(jù)集的離群值檢測(cè)算法，通過(guò)將高維數(shù)據(jù)切片并檢測(cè)，降低了存儲(chǔ)和時(shí)間開(kāi)銷，但數(shù)據(jù)切片會(huì)損失原有數(shù)據(jù)的高維特征，降低檢測(cè)性能。Zhao 等[29]提出了一種半監(jiān)督集成算法（ExGBOD,extreme gradient boosting outlier detection），使用集成學(xué)習(xí)的思想結(jié)合監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)的優(yōu)勢(shì)，但弱化了無(wú)監(jiān)督算法的泛化能力。

上述算法由于無(wú)法準(zhǔn)確把握對(duì)象與鄰域之間的關(guān)系，導(dǎo)致在復(fù)雜數(shù)據(jù)集上計(jì)算準(zhǔn)確率較低。如圖1(a)所示，假設(shè)其k值為3，此時(shí)對(duì)象p的3 個(gè)相鄰對(duì)象具有比p更高的局部密度，即對(duì)象p將具有較高的局部異常值。但是在復(fù)雜數(shù)據(jù)集上，常規(guī)局部異常因子算法準(zhǔn)確率并不高。如圖1(b)所示，對(duì)象p是密集簇C1附近的稀疏簇C2的一部分，與對(duì)象q和r1相比，p應(yīng)當(dāng)具有較小的離群值。若使用常規(guī)局部異常因子算法，p可能被錯(cuò)誤地認(rèn)為與對(duì)象q具有相同大小的異常值。因此，現(xiàn)有的離群值度量方法不適用于數(shù)據(jù)集包含具有不同密度多個(gè)聚類分布的情況。由于對(duì)象最近鄰居的錯(cuò)誤選擇，導(dǎo)致鄰域密度分布的錯(cuò)誤估計(jì)，從而計(jì)算出一個(gè)不準(zhǔn)確的異常值。

為了更好地估計(jì)鄰域的密度分布和計(jì)算局部異常值，使用最近鄰居和反向最近鄰居是必要的。如圖1(c)所示，情況與圖1(b)相同，但對(duì)象p具有2 個(gè)反向最近鄰居：s和t。這沒(méi)有將其與反向最近鄰居的對(duì)象q區(qū)分開(kāi)來(lái)，并且對(duì)象r1僅具有作為其反向最近鄰居的異常r2對(duì)象。因此加入反向最近鄰居能夠較好地解決不同密度鄰域間對(duì)象的異常值計(jì)算問(wèn)題。

現(xiàn)有算法對(duì)參數(shù)具有高度依賴性，參數(shù)改變對(duì)異常值檢測(cè)結(jié)果影響較大。另外由于沒(méi)有充分利用反向最近鄰居的屬性，導(dǎo)致計(jì)算準(zhǔn)確率不高。針對(duì)這一問(wèn)題，本文提出了一種快速異常值檢測(cè)算法，既充分利用雙向鄰居，也避免了參數(shù)選取問(wèn)題。

圖1 不同密度簇間對(duì)象的異常計(jì)算問(wèn)題

3 結(jié)合雙向鄰居的異常值計(jì)算算法

針對(duì)局部異常因子算法及其他改進(jìn)算法的不足，本文提出一種自動(dòng)確定良好參數(shù)的修正局部異常因子算法模型。受page-rank 算法啟發(fā)，CFLOF 算法將反向鄰居經(jīng)過(guò)特殊處理后再參與到對(duì)象的異常值計(jì)算中，若所有反向鄰居無(wú)差別地參與異常值計(jì)算，將存在誤判問(wèn)題，導(dǎo)致計(jì)算準(zhǔn)確率較低。例如，在微博用戶異常檢測(cè)中，把“僵尸粉”算作真正的粉絲是一種錯(cuò)誤處理，因此本文提出修正因子的概念來(lái)改善這種問(wèn)題，并通過(guò)第4 節(jié)的實(shí)驗(yàn)驗(yàn)證了這種處理是有效的。

算法主要由2 個(gè)部分組成：基于雙向鄰居的影響域（IS,influence space）和用于解決不同密度簇之間對(duì)象異常計(jì)算問(wèn)題的修正因子（CF,correction factor），如式(1)所示。

其中，IS(p)為對(duì)象p的影響域，o為IS(p)中的對(duì)象，lrd(p)為對(duì)象p的局部可達(dá)密度，CF(p)為對(duì)象p的修正因子，則對(duì)象p的修正局部異常值（CFLOF,correction factor local outlier factor）被定義為對(duì)象p局部可達(dá)密度與其影響域IS(p)中對(duì)象局部可達(dá)密度均值的比值乘以對(duì)象p的修正因子CF(p)。

3.1 基于雙向鄰居的影響域

在算法計(jì)算的過(guò)程中，搜索對(duì)象的雙向鄰居需要占用大量的時(shí)間，因此需要采用高效的算法來(lái)尋找鄰居節(jié)點(diǎn)。目前，主要使用K-D 樹(shù)或R 樹(shù)來(lái)索引對(duì)象，從而加快鄰居的搜索速度[19]。因此在鄰居搜索過(guò)程中，使用空間樹(shù)結(jié)構(gòu)來(lái)索引數(shù)據(jù)集中的所有對(duì)象，并通過(guò)特定的修剪技術(shù)降低鄰居節(jié)點(diǎn)查詢的成本。由于查詢對(duì)象的最近鄰時(shí)是通過(guò)遍歷數(shù)據(jù)集的子集來(lái)計(jì)算臨時(shí)第k距離（k-dist(p)），且k-dist(p)的上限值已知，當(dāng)p與R 樹(shù)中葉子節(jié)點(diǎn)最小邊界矩形（MBR,minimal bounding rectangle）之間的最小距離（記為MinDist(p,MBR)）大于當(dāng)前的k-dist(p)上限值，則節(jié)點(diǎn)中的任何對(duì)象都不會(huì)是p的k最近鄰之一。此優(yōu)化方法可以修剪與K 近鄰（KNN,K-nearest neighbor）搜索無(wú)關(guān)的整個(gè)子樹(shù)。隨著KNN 的搜索，每個(gè)對(duì)象的反向最近鄰居（RNN,reverse nearest neighbor）可以在R 樹(shù)中動(dòng)態(tài)維護(hù)在建立KNN 和RNN 索引后，可以計(jì)算局部異常值并對(duì)其進(jìn)行排序。算法1 是通過(guò)在R 樹(shù)中構(gòu)建KNN 和RNN 索引來(lái)挖掘異常值排名較高的n個(gè)對(duì)象。

。

算法1雙向鄰居搜索算法

輸入k,D,R 樹(shù)的根

輸出雙向鄰居的堆空間 heap

雙向鄰居搜索算法首先初始化數(shù)據(jù)集堆空間和k-dist，依次摘取R 樹(shù)中每一個(gè)MBR，比較MinDist(p,MBR)與k-dist 的大小。算法僅在那些MinDist(p,MBR)小于當(dāng)前k-dist(p)的MBR 中搜索對(duì)象p的k最近鄰居；當(dāng)MinDist(p,MBR)大于當(dāng)前k-dist(p)時(shí)，則這些MBR 被修剪，不需要搜索。每當(dāng)找到最近鄰時(shí)，它們就被存儲(chǔ)為p的最近鄰居，同時(shí)存儲(chǔ)p作為反向最近鄰居。最終CFLOF 基于影響域空間（KNN 和RNN）計(jì)算。

為推導(dǎo)雙向鄰居搜索算法的有效性，假設(shè)輸入數(shù)據(jù)集為Xn{p1,p2,p3,…,pn}，初始時(shí)從p1開(kāi)始搜索k近鄰和反向鄰居，初始k-dist 設(shè)置為無(wú)窮，此時(shí)沒(méi)有k近鄰。通過(guò)R 樹(shù)搜索其k近鄰時(shí)，首先尋找R樹(shù)中的MBR，R 樹(shù)是B 樹(shù)在高維空間的擴(kuò)展，其每個(gè)MBR 中包含多個(gè)pk∈Xn，每個(gè)MBR 在R 樹(shù)中索引了其上下界，例如在二維空間中使用4 個(gè)值標(biāo)明其界限，組成一個(gè)矩形（rectangle，此為最小邊界矩形MBR 的由來(lái)），因此可以通過(guò)計(jì)算p1與R 樹(shù)中的MBR 的4 個(gè)角的距離，并取最小值記為MinDist(p1,MBR)，若此最小值大于當(dāng)前k-dist，則其下屬節(jié)點(diǎn)不參與計(jì)算，從而減少計(jì)算量，提高時(shí)間效率。

本文使用基于反向鄰居的修剪算法用于修剪計(jì)算過(guò)程中不需要計(jì)算的對(duì)象，且解決k值選取困難的問(wèn)題，可以確定一個(gè)較優(yōu)的k值。該算法具體介紹如下。

算法2基于反向鄰居的修剪算法

輸入D,R 樹(shù)的根

輸出輸出CFLOF 值

通過(guò)迭代搜索數(shù)據(jù)集相對(duì)穩(wěn)定的狀態(tài)，當(dāng)反向鄰居為0 的對(duì)象在連續(xù)3 次迭代后沒(méi)有變化時(shí)，且在循環(huán)數(shù)次后未產(chǎn)生變化時(shí)達(dá)到穩(wěn)定狀態(tài)，表明在此數(shù)據(jù)集中距離相近的對(duì)象均搜索到反向鄰居，而可達(dá)密度低的對(duì)象無(wú)法搜索到反向鄰居，最近鄰空間達(dá)到一個(gè)穩(wěn)定的狀態(tài)，此時(shí)修剪反向鄰居為空的對(duì)象即Rnb=0 的對(duì)象，最后通過(guò)上述迭代的結(jié)果計(jì)算CFLOF 值。

k值確定算法通過(guò)搜索反向鄰居的穩(wěn)定狀態(tài)來(lái)實(shí)現(xiàn)k值選取。使用反向鄰居的思想是通過(guò)反向鄰居加強(qiáng)鄰居密度準(zhǔn)確率，因?yàn)橹皇褂胟近鄰的情況下容易對(duì)數(shù)據(jù)點(diǎn)的密度出現(xiàn)錯(cuò)誤的估計(jì)?，F(xiàn)假設(shè)數(shù)據(jù)集為Xn，其中含有2 個(gè)密度不同的簇C1和C2，以及離群點(diǎn)q，如圖2 所示。當(dāng)k值為1、2、3、4時(shí)，離群點(diǎn)q沒(méi)有反向鄰居，此時(shí)k值的選取不會(huì)對(duì)q的計(jì)算產(chǎn)生影響，本文選取k=2 和k=4 作為參考；當(dāng)k=5 時(shí)，離群點(diǎn)q新增了反向鄰居，如果k值繼續(xù)增加，q點(diǎn)的反向鄰居則持續(xù)增多，此時(shí)會(huì)降低離群點(diǎn)檢測(cè)的性能。因此k值選取算法可以確定一個(gè)良好的k值，此時(shí)k值選取的大小剛好使C1簇中的節(jié)點(diǎn)均存在反向鄰居，而離群點(diǎn)q依舊沒(méi)有反向鄰居，因此k值選取算法能確定一個(gè)良好的k值用于異常值的計(jì)算，且在確定k值的同時(shí)可以修剪沒(méi)有反向鄰居的數(shù)據(jù)項(xiàng)，因?yàn)闆](méi)有反向鄰居，所以該數(shù)據(jù)項(xiàng)不與任何數(shù)據(jù)項(xiàng)為同類，這符合離群點(diǎn)的定義。

圖2 數(shù)據(jù)集Xn

算法主要通過(guò)以下2 個(gè)方面提高效率。首先，對(duì)于任何對(duì)象p，除非所有其他對(duì)象都已完成最近鄰搜索，否則無(wú)法確定RNN 空間，若使用普通的搜索方法會(huì)消耗大量時(shí)間，采用算法1 可以提高搜索效率。其次，通過(guò)分析LOF 的特征，對(duì)于數(shù)據(jù)集中的任意對(duì)象p，如果存在 RNN(p)=?，則LOF(p)＞＞1。因此可以刪除這些集群對(duì)象，既降低計(jì)算開(kāi)銷，又節(jié)省存儲(chǔ)空間。

對(duì)于p∈D，如果對(duì)于任意一個(gè)對(duì)象p存在RNN(p)=?，則LOF(p)＞＞1可以直接標(biāo)為異常對(duì)象。因?yàn)镽NN(p)=?，即沒(méi)有任何一個(gè)對(duì)象跟p“親近”，所以對(duì)象p遠(yuǎn)離其他數(shù)據(jù)集中的對(duì)象，即對(duì)象p是局部異常值較高的點(diǎn)。

為了解決k值選取困難問(wèn)題，通過(guò)算法2 搜索數(shù)據(jù)集的穩(wěn)定狀態(tài)，并選取穩(wěn)定狀態(tài)下數(shù)據(jù)集中最大的RNN 的個(gè)數(shù)即最大反向鄰居的值作為k值。因?yàn)樽畲蟮姆聪蜞従拥闹捣从沉司垲惔氐哪５拇笮?，這樣選取的好處是可以保證不會(huì)因?yàn)檫x取值的數(shù)目過(guò)小而造成準(zhǔn)確率的損失，同時(shí)由于有反向鄰居修正因子的存在，不會(huì)因?yàn)橹德源笤斐慑e(cuò)誤的計(jì)算。通過(guò)對(duì)反向鄰居的特性研究，本文定義影響域?yàn)?/p>

p的影響域定義為當(dāng)k值取穩(wěn)定狀態(tài)下的

3.2 基于反向鄰居的修正因子

max(Rnb)時(shí)其雙向鄰居的集合。影響域反映了與對(duì)象p相關(guān)的數(shù)據(jù)對(duì)象的范圍。

修正因子算法借鑒了PR 算法，可以消除部分類似于“僵尸粉數(shù)據(jù)”對(duì)計(jì)算的影響，加上反向鄰居修正可以提高不同密度鄰域間對(duì)象的異常因子計(jì)算的準(zhǔn)確度。原始PR 算法是根據(jù)對(duì)象的出入度來(lái)迭代計(jì)算影響值，因此將對(duì)象正向和反向近鄰類比出入度來(lái)計(jì)算出一個(gè)節(jié)點(diǎn)的影響因子。最后將計(jì)算結(jié)果作為一個(gè)加權(quán)值放入原本的公式中，定義為修正因子，用于提高局部異常因子算法的計(jì)算準(zhǔn)確度。

修正因子計(jì)算式為

其中，CF(p)是對(duì)象p的修正因子值；CF(vi)是對(duì)象vi的修正因子值，對(duì)象vi是對(duì)象p反向最近鄰居中的某個(gè)對(duì)象，即vi∈RNN(p)；N k(vi)是對(duì)象vi指向其他對(duì)象的數(shù)目，即vi的正向最近鄰居的個(gè)數(shù)。修正因子是通過(guò)對(duì)象的反向最近鄰居傳遞的屬性，給出一個(gè)此對(duì)象的可信任程度，充分利用反向鄰居的作用，更好地計(jì)算局部密度值，提高了在密度不均的數(shù)據(jù)集上異常值計(jì)算的準(zhǔn)確率，從而重新定義帶修正因子的局部異常值。

CFL OF 計(jì)算式為

4 實(shí)驗(yàn)結(jié)果及評(píng)估

4.1 實(shí)驗(yàn)數(shù)據(jù)及流程

為了驗(yàn)證CFLOF 算法的高效率和高準(zhǔn)確性，分別在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集類別如表1 所示。用于直觀顯示結(jié)果的二維合成數(shù)據(jù)集共有5 種，包含不同聚類的模式、不同程度的聚類密度和不同聚類簇的大小，如表1的序號(hào)1～5所示。基于5 個(gè)合成的二維數(shù)據(jù)集的實(shí)驗(yàn)主要用來(lái)直觀地展示在二維合成數(shù)據(jù)集下算法的處理結(jié)果。為了更好地評(píng)估算法性能，在4.3 節(jié)選取了2 個(gè)合成的高斯數(shù)據(jù)集進(jìn)行準(zhǔn)確率和時(shí)間效率的實(shí)驗(yàn)，數(shù)據(jù)集如表1 的序號(hào)6～7 所示。同時(shí)選取6 個(gè)公開(kāi)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，用于對(duì)比CFLOF 算法在真實(shí)數(shù)據(jù)集上的檢測(cè)性能，數(shù)據(jù)集參數(shù)如表2 所示。在實(shí)驗(yàn)中使用2 種檢測(cè)指標(biāo)，即準(zhǔn)確率和時(shí)間效率來(lái)評(píng)估所提算法的性能。

表1 二維合成數(shù)據(jù)集

表2 公開(kāi)數(shù)據(jù)集

本文算法通過(guò)Python 語(yǔ)言來(lái)實(shí)現(xiàn)，合成數(shù)據(jù)集通過(guò)NumPy 庫(kù)設(shè)置不同的均值和標(biāo)準(zhǔn)差來(lái)生成，實(shí)驗(yàn)操作系統(tǒng)為Ubuntu，內(nèi)存為16 GB，CPU為i7-6700。

Letter 和Pendigit 數(shù)據(jù)集來(lái)自UCL 的數(shù)據(jù)庫(kù)。Smtp 數(shù)據(jù)集來(lái)自KDD99 數(shù)據(jù)集的子集，其中服務(wù)屬性為smtp；Http 數(shù)據(jù)集同樣來(lái)自KDD99數(shù)據(jù)集的子集，服務(wù)屬性為http。Credit 是信用卡欺詐檢測(cè)的公開(kāi)數(shù)據(jù)集。Mnist 數(shù)據(jù)集是手寫(xiě)數(shù)字?jǐn)?shù)據(jù)庫(kù)的子集。各數(shù)據(jù)集大小以及維度如表2所示。

4.2 參數(shù)調(diào)優(yōu)

為了驗(yàn)證CFLOF 算法的有效性，使用5 個(gè)數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，利用人工設(shè)置參數(shù)和不同的步長(zhǎng)來(lái)進(jìn)行實(shí)驗(yàn)。通過(guò)不同的實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)k值變化在10 以內(nèi)時(shí)，準(zhǔn)確率變化較小，因此將k值變化的步長(zhǎng)設(shè)置為大于或等于10。將不同k值情況下所得準(zhǔn)確率數(shù)據(jù)繪制成圖，并將算法確定出的k值進(jìn)行標(biāo)記，實(shí)驗(yàn)結(jié)果如圖3 所示。

圖3 不同k 值選取下的準(zhǔn)確率對(duì)比

通過(guò)對(duì)5 個(gè)數(shù)據(jù)集的實(shí)驗(yàn)發(fā)現(xiàn)，自動(dòng)參數(shù)k值的選擇算法選擇出的參數(shù)k是最優(yōu)參數(shù)。在數(shù)據(jù)集1中，算法得到的k值為20，此時(shí)的準(zhǔn)確率最高；在數(shù)據(jù)集2 中，算法選擇的k值雖然沒(méi)有達(dá)到最高的準(zhǔn)確率，但是k值小于50，算法的時(shí)間效率較好。在數(shù)據(jù)集3 中，算法確定的k值達(dá)到了最高的準(zhǔn)確率。數(shù)據(jù)集4 和數(shù)據(jù)集5 實(shí)驗(yàn)結(jié)果同樣在使用算法確定的k值達(dá)到了最高的準(zhǔn)確率。通過(guò)5 個(gè)數(shù)據(jù)集的實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，算法2 選取的參數(shù)k的值在準(zhǔn)確率上都有不錯(cuò)的表現(xiàn)。實(shí)驗(yàn)結(jié)果表明，參數(shù)選擇算法可以解決局部異常因子算法參數(shù)選取困難的問(wèn)題。

4.3 合成數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為了直觀地顯示CFLOF 算法的準(zhǔn)確性，本節(jié)首先在5 個(gè)二維合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行總結(jié)。這5 個(gè)二維合成數(shù)據(jù)集特點(diǎn)如表1 所示，包含不同聚類的模式、不同程度的聚類密度和不同聚類簇的大小，以便在復(fù)雜的測(cè)試環(huán)境中評(píng)估CFLOF 方法。將CFLOF 算法的性能與現(xiàn)有的2 種算法（LOF 算法和INS 算法）進(jìn)行了比較。在每個(gè)算法中，具有最高局部異常值的對(duì)象在以下實(shí)驗(yàn)結(jié)果中被標(biāo)記成星號(hào)形狀。圖4～圖8 顯示了3 種算法的離群檢測(cè)結(jié)果。參數(shù)k的值是通過(guò)算法2 獲取，而不是人工設(shè)置的。

圖4 顯示了數(shù)據(jù)集1 上3 種算法的實(shí)驗(yàn)結(jié)果，該數(shù)據(jù)集由3 個(gè)簇組成。數(shù)據(jù)集1 是較簡(jiǎn)單的情況，存在3 個(gè)標(biāo)準(zhǔn)高斯分布的簇。此數(shù)據(jù)集由1 500 個(gè)對(duì)象組成，其中4%（60 個(gè)對(duì)象）是異常值。由圖4 中實(shí)線方框的位置可以看出，CFLOF 算法的準(zhǔn)確度優(yōu)于INS 算法，這是因?yàn)镃FLOF 算法通過(guò)使用反向鄰居增強(qiáng)了算法的檢測(cè)能力，可以檢測(cè)出一些INS 算法和LOF 算法漏檢的對(duì)象。LOF 算法和CFLOF 算法的結(jié)果是相似的，并且在數(shù)據(jù)集1 的局部異常值檢測(cè)上優(yōu)于INS 算法。INS 算法的錯(cuò)誤率明顯高于LOF 算法，這是因?yàn)镮NS 算法錯(cuò)誤地將簇中的值檢測(cè)為異常值。

圖4 數(shù)據(jù)集1 上3 種算法的實(shí)驗(yàn)結(jié)果（k=17）

數(shù)據(jù)集2 由1 000 個(gè)對(duì)象、4 個(gè)正式簇和85個(gè)異常值組成，如圖5 所示。從圖5 所示的結(jié)果可以看出，CFLOF 算法的全局異常檢測(cè)效果與INS 算法類似，都比LOF 算法好。但是，在局部異常值檢測(cè)中，LOF 算法和CFLOF 算法的效果優(yōu)于INS 算法（一些局部異常值在實(shí)驗(yàn)結(jié)果中被實(shí)線框標(biāo)記出）。INS 算法對(duì)反向鄰居的利用較簡(jiǎn)單，而通過(guò)修正因子利用的反向鄰居可以很好地在全局和局部上正確地檢測(cè)出異常值，即當(dāng)參數(shù)k的值被賦予17 時(shí)，CFLOF 算法的準(zhǔn)確率在3 種算法中最高。

圖5 數(shù)據(jù)集2 上3 種算法的實(shí)驗(yàn)結(jié)果（k=17）

圖6 所示的數(shù)據(jù)集3 涉及局部密度問(wèn)題。此數(shù)據(jù)集中共包含1 641 個(gè)對(duì)象，其中45 個(gè)對(duì)象是異常值。INS 算法的結(jié)果是3 種算法中最差的。INS 算法由于沒(méi)有有效地利用反向鄰居，導(dǎo)致錯(cuò)誤地將位于實(shí)線方框中的正常點(diǎn)檢測(cè)為異常對(duì)象，且無(wú)法正確檢測(cè)出位于實(shí)線方框中的真實(shí)異常值。而LOF算法則錯(cuò)誤地將下方密度均勻的簇檢測(cè)為異常點(diǎn)，相比之下通過(guò)修正因子利用反向鄰居改進(jìn)后的CFLOF 算法在處理復(fù)雜數(shù)據(jù)集時(shí)，將反向鄰居的影響考慮在內(nèi)，提高了檢測(cè)的準(zhǔn)確定，檢測(cè)效果好于其他2 種算法。

圖6 數(shù)據(jù)集3 上3 種算法的實(shí)驗(yàn)結(jié)果（k=13）

圖7 中所示的數(shù)據(jù)集4 涉及低密度數(shù)據(jù)問(wèn)題。此數(shù)據(jù)集中共包含880 個(gè)對(duì)象，其中72 個(gè)對(duì)象是異常值。從圖7 結(jié)果中可以看出，經(jīng)過(guò)修正因子改進(jìn)的CFLOF 算法在較稀疏的數(shù)據(jù)集上也可以很好地檢測(cè)出異常值，不會(huì)出現(xiàn)錯(cuò)檢的情況。這同時(shí)也驗(yàn)證了當(dāng)參數(shù)k使用算法2 確定時(shí)CFLOF 算法的有效性。

圖7 數(shù)據(jù)集4 上3 種算法的實(shí)驗(yàn)結(jié)果（k=28）

如圖8 所示，數(shù)據(jù)集5 具有低密度數(shù)據(jù)和不同流形的簇，由1 400 個(gè)對(duì)象組成，其中100 個(gè)對(duì)象是異常值。INS 算法的結(jié)果是最糟糕的。INS算法錯(cuò)誤地檢測(cè)位于實(shí)線方框中的點(diǎn)，這些點(diǎn)屬于具有流形的簇，INS 算法再次錯(cuò)誤地將正常簇中的點(diǎn)識(shí)別為異常值。而CFLOF 算法在使用反向鄰居及修正因子以后，可以增強(qiáng)同簇對(duì)象間的影響，同時(shí)減少噪聲的影響，對(duì)流形數(shù)據(jù)簇分布具有較好的識(shí)別效果，最佳低保留了數(shù)據(jù)流形分布規(guī)律。

上述實(shí)驗(yàn)結(jié)果直觀顯示了CFLOF 算法的優(yōu)越性，CFLOF 算法在5 個(gè)數(shù)據(jù)集下的準(zhǔn)確率均優(yōu)于其他2 種算法，這表明修正因子的引入提高了算法在二維合成數(shù)據(jù)上的準(zhǔn)確率。

圖8 數(shù)據(jù)集5 上3 種算法的實(shí)驗(yàn)結(jié)果（k=31）

4.4 算法模型時(shí)間效率對(duì)比

通過(guò)表1 中的高斯分布數(shù)據(jù)集1 和高斯分布數(shù)據(jù)集2 來(lái)測(cè)試算法的時(shí)間效率，如圖9 所示。實(shí)驗(yàn)結(jié)果的起始部分隨著使用數(shù)據(jù)集大小的增加，算法在構(gòu)造R 樹(shù)的時(shí)間開(kāi)銷較高。距離計(jì)算與鄰居搜索的時(shí)間開(kāi)銷較低，隨著數(shù)據(jù)集的增加，距離計(jì)算與鄰居搜索的時(shí)間開(kāi)銷逐漸增大，而R 樹(shù)的使用與后期的修剪過(guò)程減少了距離計(jì)算與鄰居搜索帶來(lái)的開(kāi)銷。當(dāng)數(shù)據(jù)集規(guī)模持續(xù)上升時(shí)，可以看到，CFLOF 算法在數(shù)據(jù)集規(guī)模超過(guò)1.5×104時(shí)開(kāi)始拉開(kāi)差距，并且在后面數(shù)據(jù)集增大時(shí)差距逐漸變大。

圖9 3 種算法的計(jì)算時(shí)間隨數(shù)據(jù)集規(guī)模的變化對(duì)比

通過(guò)在符合高斯分布合成數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)發(fā)現(xiàn)，因所提剪枝算法的使用，可以有效地提高時(shí)間效率，相較于其他算法，CFLOF 算法在時(shí)間的效率上均有不同程度的優(yōu)勢(shì)。

4.5 公開(kāi)數(shù)據(jù)集上檢測(cè)性能實(shí)驗(yàn)結(jié)果對(duì)比

為了進(jìn)一步驗(yàn)證CFLOF 算法的有效性，將CFLOF 算法應(yīng)用于2 個(gè)真實(shí)世界的數(shù)據(jù)集。從UCI機(jī)器學(xué)習(xí)庫(kù)中選擇2 個(gè)具備不同屬性的數(shù)據(jù)集：Pendigit 和Letter，用于算法的準(zhǔn)確率和時(shí)間效率的測(cè)試。同時(shí)生成2 個(gè)符合高斯分布的數(shù)據(jù)集，維度均為2 維，數(shù)據(jù)生成的協(xié)方差矩陣和均值不同，大小可變，生成的數(shù)據(jù)將用于測(cè)試算法的時(shí)間效率。

在2 個(gè)真實(shí)的數(shù)據(jù)集上對(duì)3 種算法的準(zhǔn)確率進(jìn)行了對(duì)比實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)結(jié)果繪制了算法的準(zhǔn)確率隨k值的變化情況，如圖10 所示，其中垂直虛線所對(duì)應(yīng)數(shù)據(jù)點(diǎn)是CFLOF 的實(shí)驗(yàn)數(shù)據(jù)，因?yàn)槠鋕值是通過(guò)算法2 自動(dòng)確定的，所以僅標(biāo)注k=20 和k=27 時(shí)對(duì)應(yīng)的算法準(zhǔn)確率，可以明顯地發(fā)現(xiàn)，CFLOF 算法的準(zhǔn)確率高于其他2 種算法，這驗(yàn)證了CFLOF 算法避免了參數(shù)選擇的問(wèn)題。通過(guò)實(shí)驗(yàn)結(jié)果還可以發(fā)現(xiàn)，參數(shù)選擇算法不僅適用于CFLOF 算法，同時(shí)在其他改進(jìn)局部異常因子算法中也可以得到較高的準(zhǔn)確率。

為了更好地對(duì)算法的檢測(cè)性能進(jìn)行比較，驗(yàn)證模型在實(shí)際應(yīng)用領(lǐng)域的檢測(cè)效果，分別在4 個(gè)高維數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，對(duì)于前3 個(gè)數(shù)據(jù)集（Http、Smtp 和Credit），使用高斯隨機(jī)投影將維數(shù)減小為8。對(duì)于Mnist 數(shù)據(jù)集，由于原始數(shù)據(jù)是高維的，因此減小的子空間維數(shù)為15。將隨機(jī)投影過(guò)程重復(fù)10次，然后比較不同算法之間ROC 曲線下與坐標(biāo)軸圍成的面積（AUC,area under curve）的平均值。

圖9 3 種算法在2 個(gè)真實(shí)數(shù)據(jù)集下的準(zhǔn)確率隨參數(shù)k 的變化

同時(shí)將CFLOF 算法與目前主流的支持向量機(jī)（SVM,support vector machines）和iForest 進(jìn)行比較，在Http 數(shù)據(jù)集和Smtp 數(shù)據(jù)集中，CFLOF 算法的性能與SVM 的最佳結(jié)果相似。在Credit 數(shù)據(jù)集和Mnist 數(shù)據(jù)集中，CFLOF 算法的平均AUC 比其他2 種算法更高。同時(shí)相比于其他2 種算法模型，CFLOF 算法模型更簡(jiǎn)單，時(shí)間開(kāi)銷小。

表3 3 種算法在公開(kāi)數(shù)據(jù)集實(shí)驗(yàn)的AUC 均值

通過(guò)在真實(shí)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)發(fā)現(xiàn)，相較于其他算法，CFLOF 算法在檢測(cè)性能上有不同程度的優(yōu)勢(shì)，尤其是當(dāng)進(jìn)行多個(gè)聚類簇不同密度之間的對(duì)象計(jì)算時(shí)，CFLOF 算法的準(zhǔn)確率比較高，這表明雙向鄰居搜索算法和修正因子提高了算法效率和準(zhǔn)確率。同時(shí)通過(guò)KDD99 網(wǎng)絡(luò)數(shù)據(jù)集和金融領(lǐng)域的真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，CFLOF 算法模型可以很好地解決現(xiàn)有的異常檢測(cè)問(wèn)題，同時(shí)CFLOF 算法模型相較于其他算法模型也有較好的表現(xiàn)。

5 結(jié)束語(yǔ)

針對(duì)目前離群點(diǎn)檢測(cè)算法存在參數(shù)選取困難、精度低等問(wèn)題，提出了基于反向鄰居修正的局部異常因子算法來(lái)檢測(cè)異常值和評(píng)估對(duì)象離群程度。與現(xiàn)有的基于距離和基于密度的算法不同，CFLOF算法不受模型參數(shù)k值變化影響，參數(shù)k值由所提雙向鄰居搜索算法確定。同時(shí)本文還提出修正因子的概念，該概念使CFLOF 算法在處理復(fù)雜數(shù)據(jù)集中對(duì)象時(shí)，可以更準(zhǔn)確地計(jì)算異常值。在二維合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果表明，CFLOF算法相較于其他算法在時(shí)間效率和準(zhǔn)確率方面有一定優(yōu)勢(shì)，這體現(xiàn)了CFLOF 算法的有效性。但是當(dāng)維度過(guò)高時(shí)，CFLOF 算法有維度災(zāi)難問(wèn)題出現(xiàn)，會(huì)導(dǎo)致基于距離的算法失效問(wèn)題，如何尋找一個(gè)有效的并且對(duì)數(shù)據(jù)原始特征損失較小的降維算法，是未來(lái)的研究目標(biāo)。