基于反向k近鄰過濾異常的群數(shù)據(jù)異常檢測

吳金娥， 王若愚， 段倩倩， 李國強, ， 琚長江

(1. 上海工程技術(shù)大學 電子電氣工程學院， 上海 201600； 2. 上海交通大學 軟件學院， 上海 200240)

異常檢測技術(shù)通過對事物產(chǎn)生的數(shù)據(jù)進行分析和挖掘，能有效及時地發(fā)現(xiàn)事物中的異常數(shù)據(jù)，有利于預(yù)防和制止損失的產(chǎn)生.隨著該技術(shù)的發(fā)展與成熟，已被廣泛應(yīng)用于網(wǎng)絡(luò)安全、金融、醫(yī)療健康、國防軍事等多個領(lǐng)域[1].根據(jù)待檢測數(shù)據(jù)有無標簽可將異常檢測算法分為監(jiān)督[2]、半監(jiān)督[3]和無監(jiān)督[4]；依據(jù)異常類型的不同又可分為點異常、上下文異常和群異常[5].現(xiàn)有的技術(shù)大多是在有數(shù)據(jù)標簽的情況下研究單個點的異常，而現(xiàn)實生活中的部分異常只能從無數(shù)據(jù)標簽的群數(shù)據(jù)中挖掘出來.

監(jiān)督或半監(jiān)督的異常檢測技術(shù)依賴于數(shù)據(jù)集所提供的帶數(shù)據(jù)標簽的正常和異常數(shù)據(jù)，該方法利用已知正常和異常數(shù)據(jù)訓(xùn)練模型[6]，通過觀察待測數(shù)據(jù)的數(shù)據(jù)模型與帶標簽數(shù)據(jù)訓(xùn)練出的模型之間的符合程度判別是否異常.而當待檢測的數(shù)據(jù)集無已知正?；虍惓?shù)據(jù)，如網(wǎng)絡(luò)新型攻擊發(fā)生時，使用監(jiān)督式方法并不能檢測出該異常.而在異常檢測技術(shù)領(lǐng)域中，高檢測率是該領(lǐng)域追求的最終目標，漏報和誤報作為影響算法效率的根本原因，也是目前異常檢測算法中普遍存在的問題.減少漏報和誤報可以提升算法性能，對現(xiàn)實領(lǐng)域的應(yīng)用具有重大意義.

異?；螂x群值指的是與正常數(shù)據(jù)有顯著差異的數(shù)據(jù)點.早在19世紀，關(guān)于離群值問題就被統(tǒng)計學界提出并研究[7].直至2000年，Knorr等[8]提出基于距離的異常檢測方法，掀起了異常檢測技術(shù)的發(fā)展高潮.在關(guān)于群數(shù)據(jù)的異常檢測中，Lee等[9]提出的基于分段檢測的軌跡離群點檢測 (TRAOD)框架可有效檢測出異常的子軌跡.Luan等[10]在傳統(tǒng)TRAOD算法的基礎(chǔ)上，結(jié)合文獻[9]中提出的分割檢測框架提出一種基于局部密度的軌跡離群算法.Djenouri等[11]提出在給定時間間隔中同時考慮時間和空間因素建立的流量分布概率數(shù)據(jù)庫，結(jié)合基于距離的k近鄰(kNN)算法檢測交通流數(shù)據(jù)的異常.毛江云等[12]提出通過Markov決策過程實現(xiàn)異常車輛的軌跡檢測，該算法分為預(yù)處理、離線訓(xùn)練模型和在線檢測異常3個階段.Wang等[13]提出一套基于統(tǒng)計距離的群數(shù)據(jù)異常檢測技術(shù)，該技術(shù)以已知的正常群數(shù)據(jù)和異常群數(shù)據(jù)作為參照系，使用動態(tài)更新閾值法對待檢測群數(shù)據(jù)進行異常判別.通過淘寶交易刷信譽的真實數(shù)據(jù)集進行大量實驗，實驗結(jié)果證明該監(jiān)督式方法可有效識別出異常.

本文的主要創(chuàng)新點在于：① 為解決無數(shù)據(jù)標簽的群數(shù)據(jù)異常檢測問題，提出一種基于k近鄰算法的無監(jiān)督式異常檢測算法；② 為減少算法的漏報、誤報率，提出使用反向k近鄰(RkNN)算法過濾異常值，優(yōu)化算法性能；③ 相比于文獻[13]，本文解決了在無監(jiān)督模式下對異常群數(shù)據(jù)的檢測問題，并優(yōu)化了kNN算法的檢測質(zhì)量.

1 相關(guān)技術(shù)

1.1 相似性度量

相似性度量指的是兩個事物間相似程度的一種度量方式.使用統(tǒng)計距離作為不同集群數(shù)據(jù)間的相似性度量.統(tǒng)計距離度量的是兩個群數(shù)據(jù)在數(shù)據(jù)分布上的差異，常見的統(tǒng)計距離有相對熵，又被稱為Kullback-Leibler散度(KLD)或信息散度[14]，該距離度量方式不具有對稱性，而Jensen-Shannon散度(JSD)[15]作為相對熵的優(yōu)化計算方式具有對稱性.在實驗中選用具有對稱性的JSD作為衡量兩個群數(shù)據(jù)間差異的相似性度量.但當出現(xiàn)兩個數(shù)據(jù)分布完全不重疊的極端情況時，JSD不再適用.為此，考慮將集群數(shù)據(jù)以特定形式引入歐式空間中進行異常檢測.對本文中使用到的距離度量方式進行如下定義.

g、l分別表示待檢測數(shù)據(jù)集C中的任意兩個群數(shù)據(jù)，g、l間的距離可記為d(g,l).當相似性度量為JSD距離度量方式時，g、l間的距離表達式如下：

d(g,l)=JSD(G‖L)

(1)

式中：G、L分別為g和l的概率分布.KLD的距離表達方式如下：

(2)

式中：G(z)、L(z)為離散變量.G、L間JSD值的計算方式為

(3)

當使用歐式距離作為相似性度量時，g、l間的距離表達式則為

d(g,l)=E(X,Y)

(4)

式中：X、Y分別為g、l各自在24 h中每小時銷售統(tǒng)計量構(gòu)成的24維向量；E(X,Y)為X、Y間的歐式距離.具體定義如下：

(5)

1.2 k近鄰與反向k近鄰

k近鄰算法[16]是最簡單的機器學習算法之一，最開始被用于求解分類問題[17].隨著異常檢測技術(shù)的發(fā)展，該算法被應(yīng)用于異常檢測中，其判別異常的步驟如下：對每個待測樣本求得其k個最近鄰的集合，再求得每個樣本到各自k個最近鄰的平均距離，將平均距離表示為該樣本的異常得分，異常得分越高表示該樣本越異常[18].本文使用該算法求得每個群數(shù)據(jù)的異常得分后，為了更好地反映不同集群間的差異，使用每個集群到各自k個最近鄰的距離總和作為異常得分.g的k個最近鄰集合可記作Nk(g)，則有：

Nk(g)={l|d(g,l)≤dk(g),

l∈{C-{g}}}

(6)

式中：dk(g)為g的k個最近鄰.綜合以上定義，待測集群g的異常得分定義如下：

(7)

由于在計算k個最近鄰時，不可避免地會受到異常值之間的相互干擾，提出使用反向k近鄰法[19]過濾互相干擾的情況.關(guān)于反向k近鄰的定義如下：

Qk(g)={l|g∈Nk(l),l∈C}

(8)

式中：Qk(g)為g的k個反向最近鄰的集合；Nk(l)為l的k個最近鄰的集合.

2 反向k近鄰過濾異常的群數(shù)據(jù)異常檢測

2.1 模型建立

無監(jiān)督方式下的數(shù)據(jù)異常檢測對數(shù)據(jù)集的要求較低.當待檢測的異常為新發(fā)生的異常時，由于缺少先驗知識，有監(jiān)督的算法并不能實現(xiàn)檢測，而無監(jiān)督方式可直接對數(shù)據(jù)集進行建模，從而檢測出異常.針對k近鄰算法在檢測異常時存在的誤報和漏報問題，提出使用反向k近鄰法對該算法進行優(yōu)化，以提升算法的檢測效果.模型包括3個部分：① 數(shù)據(jù)預(yù)處理模塊；② 初步異常檢測模塊；③ 算法優(yōu)化模塊.各模塊部分的功能簡述如下：

(1) 數(shù)據(jù)預(yù)處理模塊.將待測數(shù)據(jù)集劃分成多個集群數(shù)據(jù)，以方便算法的實施.

(2) 初步異常檢測模塊.對輸入的多個集群數(shù)據(jù)使用k近鄰算法實現(xiàn)無監(jiān)督式的群數(shù)據(jù)異常檢測，獲得初步異常群數(shù)據(jù).

該模塊首先計算兩兩集群之間的距離，建立起距離權(quán)圖；再計算每個集群的k個最近鄰的距離之和作為該集群的異常得分；最后將異常得分最高的前m個集群Sm作為初始異常輸出到算法優(yōu)化模塊.

(3) 算法優(yōu)化模塊.對輸入的異常群數(shù)據(jù)，使用反向k近鄰法進行過濾，獲得優(yōu)化后的異常群數(shù)據(jù).

由于k近鄰算法在計算集群的k個最近鄰時存在異常集群和正常集群之間相互干擾的問題，導(dǎo)致檢測結(jié)果存在漏報和誤報.為解決這個問題，該模塊提出使用反向k近鄰算法對初始異常集群進行反向過濾.首先查找每個異常集群的反向k近鄰；再對其中的正常集群更新k近鄰，使異常集群不包含在其k近鄰中；最后重新計算異常得分，更新異常集群.重復(fù)該操作直至最終輸出的異常集群的反向k近鄰中不再包含正常集群.

根據(jù)以上3個模塊的功能簡述，所建立的算法模型如圖1所示.

圖1 模型建立流程圖Fig.1 Flow chart of model establishment

2.2 基于k近鄰的群數(shù)據(jù)異常檢測

2.2.1JSD相似性度量下的群數(shù)據(jù)異常檢測 在處理無數(shù)據(jù)標簽的數(shù)據(jù)集時，無法從數(shù)據(jù)集本身的建模判別異常集群，而建立全局的距離權(quán)圖有助于解決異常集群的識別問題.利用所建立的距離權(quán)圖，使用k近鄰算法求得每個集群的異常得分，根據(jù)異常得分識別異常數(shù)據(jù).集群數(shù)據(jù)之間的差異可以很好地體現(xiàn)在數(shù)據(jù)分布的差異性上，而統(tǒng)計距離能較好地捕捉不同群數(shù)據(jù)間的分布差異，因此使用JSD距離度量方式計算兩兩集群間的距離.為更好地反映集群間的差異性，將待測集群與其k個最近鄰集群間的距離之和作為該集群的異常得分，最后輸出異常得分排序列表的前m個集群作為異常值，即輸出Sm.根據(jù)以上分析，基于k近鄰算法的統(tǒng)計分布檢測(SDD-kNN)算法的偽代碼如算法1所示.

算法1SDD-kNN

輸入數(shù)據(jù)集C={c1,c2,…,cn}，近鄰的數(shù)量為k

輸出Sm

(1)M←n×n空矩陣

(2) fori←1 tondo

(3)Gi←ci的概率分布

(4) end for

(5) fori←1 tondo

(6) forj←1 tondo

(7)Mij←JSD(Gi‖Gj)

(8) end for

(9) end for

(10) fori←1 tondo

(11)α(ci)←M的第i行前k+1個最小元素和

(12) end for

(13)S←對所有集群按α(ci)值進行降序排列

(14)Sm←S中前m個集群

(15) returnSm

2.2.2歐式距離的應(yīng)用 當兩個集群的概率分布G和L完全沒有重疊的極端情況發(fā)生時，JSD不再適用.通過比較式(3)和(5)可以發(fā)現(xiàn)，歐式距離對數(shù)據(jù)的變化更為敏感，因此可將待檢測數(shù)據(jù)集映射到歐式空間中，使用歐式距離作為兩兩集群間的相似性度量.由于實驗數(shù)據(jù)是淘寶交易數(shù)據(jù)，所以將待檢測數(shù)據(jù)集按天劃分為不同的集群數(shù)據(jù)，將每天24 h的交易量作為歐式距離的24維向量，由此來計算不同集群間的差異.統(tǒng)計日交易數(shù)據(jù)分布直方圖如圖2所示.其中：H為不同時間點；V為銷售量.

圖2 日交易數(shù)據(jù)分布直方圖(第156天)Fig.2 Distribution histogram of daily trading data (156th day )

2.3 基于反向k近鄰的過濾法

漏報和誤報是異常檢測算法普遍存在的問題，產(chǎn)生漏報和誤報的情況有兩種，一種是算法本身存在局限性，不能準確識別出部分異常集群；另一個原因是在計算k近鄰時產(chǎn)生的誤差.在SDD-kNN算法中，造成誤差的原因是異常值與正常值之間的相互干擾，導(dǎo)致異常集群被誤判為正常集群.

SDD-kNN算法之所以能有效檢測出異常，這依賴于異常集群與正常集群之間的距離較大，而正常集群之間的距離則相對較小，所以異常集群相對于正常集群而言有更高的異常得分.假設(shè)集群g的Nk(g)中包含另一個甚至幾個其他異常集群，此時α(g)將會變低，當該值小于噪聲點或處于異常邊緣的正常集群的異常得分時，g則被誤判為正常，而噪聲點或處于異常邊緣的正常集群被宣布為異常，由此導(dǎo)致算法的誤報和漏報率上升.

為解決由上述原因產(chǎn)生的誤報和漏報問題，對算法初步輸出的異常值使用反向k近鄰法進行過濾，從而提升算法的性能.反向分析上述問題產(chǎn)生的原因，如果算法判別為正常集群的k個最近鄰中包含判別為異常的集群，那么該正常集群很有可能是受其他異常集群的干擾而被誤判的.所以在該方法中應(yīng)首先找到初步輸出的異常集群的反向k近鄰，對反向k近鄰中被初步識別為正常的集群重新計算k近鄰，且該k近鄰不再包含已知的異常集群.然后再重新計算異常得分，更新Sm，并重復(fù)上述步驟.直至Sm中集群的反向k近鄰中不再包含正常集群.根據(jù)上述分析，反向k近鄰過濾異常算法的偽代碼如算法2所示.

算法2反向k近鄰過濾異常法

輸入數(shù)據(jù)集C={c1,c2,…,cn}，初步輸出的異常集合θ，近鄰的數(shù)量為k

輸出Sm

(1) forci∈θdo

(2) forcj∈Qk(ci)do

(3) ifcj?θ

(4)Nk(cj)={cb|d(cj,cb)≤dk(cj),cb∈{C-{ci,cj}}}

(6) end for

(7) end for

(8)S←對所有集群按α(ci)值進行降序排列

(9)Sm←S中前m個集群

(10) returnSm

3 實驗及其結(jié)果分析

3.1 數(shù)據(jù)集介紹

選取文獻[13]在實驗中使用的數(shù)據(jù)集，該數(shù)據(jù)集的正常交易數(shù)據(jù)來自于阿里巴巴天池大數(shù)據(jù)競賽.提取編號為 1 629 的賣家交易史，記錄時間為2015-11-11～2016-10-31，以天為單位將數(shù)據(jù)集劃分成325個集群.關(guān)于該數(shù)據(jù)集的詳細描述如圖3所示.

圖3 數(shù)據(jù)集介紹Fig.3 Data set introduction

由圖3可見，口碑數(shù)據(jù)集中描述了集中式刷信譽和均衡式刷信譽兩種不同的刷信譽模式，這兩種模式下的數(shù)據(jù)是模擬不同刷信譽行為生成的.由于原始數(shù)據(jù)集只記錄了交易成交時間點的小時記錄數(shù)，所以引入了增強數(shù)據(jù)集，該數(shù)據(jù)集添加了時分秒的時間戳.在檢測算法性能時，待測數(shù)據(jù)集由異常群數(shù)據(jù)中的異常集群替換正常數(shù)據(jù)中的正常集群，從而組成待測數(shù)據(jù)集.

3.2 實驗結(jié)果評價指標介紹

在異常檢測問題中，正確率作為直觀的評價指標之一，通常被用于度量算法的性能.然而，當異常數(shù)據(jù)較少時，盡管算法未檢測出任何異常，該算法表現(xiàn)出的正確率仍然會很高.因此，除了正確率A之外，還引入假陽率η、精度P、召回率R、綜合評價指標F以及運行時間t作為衡量算法有效性的指標.

(1) 正確率：指預(yù)測正確的集群個數(shù)在待測數(shù)據(jù)集中的占比， 該值越大，則代表算法性能越好，

(9)

式中：FP為將正常集群誤判為異常的數(shù)量；TN為正常集群被正確判斷的數(shù)量；TP為異常集群被正確判別為異常的數(shù)量；FN為異常集群被錯判為正常的數(shù)量.

(2) 假陽率：指正常集群中被預(yù)測為異常的比例，該值越小，則代表算法性能越好，

(10)

(3) 精度：指在預(yù)測為異常的集群中真實異常的占比，即

(11)

(4) 召回率：指預(yù)測為異常的集群占總真實異常的比例，即

(12)

(5) 綜合評價指標：該指標是P和R的加權(quán)調(diào)和平均，其計算公式如下：

(13)

式中：β為參數(shù)，此處取β=1，此時將綜合評價指標記作F1值，即上式變?yōu)?/p>

(14)

隨著F1值的升高，算法性能也越來越好.

(6) 運行時間：該項指標記錄的是算法完成檢測所需的時間，該指標越小，則代表算法性能越好.

3.3 實驗分析

實驗1k值的選擇.由于kNN算法的檢測結(jié)果在很大程度上受到k值的影響，所以合理地選擇k值是保證實驗檢測效率的條件之一.實驗數(shù)據(jù)集由正常交易數(shù)據(jù)混合不同數(shù)目的集中式刷信譽數(shù)據(jù)構(gòu)成.采用單變量控制法，檢測在不同異常概率下k值對最終決策的影響，檢測結(jié)果如圖4所示，其中U為異常概率.

由圖4可見，k值對算法的檢測結(jié)果有較大的影響.隨著k值的增大，F(xiàn)1值呈上升趨勢并逐漸趨于平穩(wěn).當k值較小時，噪聲點不易與異常值區(qū)分，導(dǎo)致較低的檢測率.因此，當k逐漸增大時，可以獲得與待測集群數(shù)據(jù)更多的相關(guān)信息，使噪聲點與異常值的異常得分差距增大，算法性能得到提升.

圖4 k值對檢測結(jié)果的影響Fig.4 Influence of k values on test results

比較圖4(a)和(b)可見，在歐式距離相似性度量方式下算法性能比JSD距離度量方式下提升得更快.這是由于歐式距離對微小的變化更敏感，在k值較小的情況下也能有效區(qū)別噪聲和異常.

實驗2反向過濾干擾值的有效性驗證.由于kNN算法在檢測異常時存在一定的漏報和誤報，為減少由于數(shù)據(jù)間相互干擾帶來的誤報和漏報率，使用RkNN算法對kNN算法進行優(yōu)化.在該組實驗中，對反向過濾干擾值方法的有效性進行驗證，對兩種不同距離度量方式下的算法分別應(yīng)用該方法.實驗數(shù)據(jù)集由兩種不同刷信譽行為下的數(shù)據(jù)隨機替換正常交易數(shù)據(jù)集中20%的正常數(shù)據(jù)組成.使用反向k近鄰過濾方法下的統(tǒng)計檢測方法記作SDD-RkNN；歐式距離度量方式下的基于距離的檢測方式記為DBD-kNN；歐式距離度量方式下的基于反向k近鄰過濾法的檢測方式記為DBD-RkNN；W為各項評價指標的百分比.

由圖5可見，A與F1值在SDD-RkNN和DBD-RkNN方法下分別比SDD-kNN和DBD-kNN方法下具有更高的值，同時具有更低的η值.由此可見，無論是在集中式還是在均衡式刷信譽方式下，反向過濾異常干擾方法均能有效提升算法的檢測性能，評價指標η、A和F1值均得到了約1%的提升.

由圖6(a)可見，使用了反向k近鄰法優(yōu)化算法的SDD-RkNN和DBD-RkNN方法在增強數(shù)據(jù)集

下集中式刷信譽模式的檢測性能評測指標η、A和F1值相比于直接使用k近鄰算法有所提升.由圖6(b)可知，DBD-RkNN方法下的3項性能評價指標均無提升，因此當相似性度量為歐式距離時，對均衡式刷信譽模式應(yīng)用反向k近鄰法并不能提升算法性能，甚至會對原始算法的性能有微小的降低，增強數(shù)據(jù)集中隨機生成的時間戳是導(dǎo)致該情況發(fā)生的原因之一.

綜合而言，使用RkNN算法對異常值之間互相干擾的情況進行優(yōu)化的算法能有效提高SDD-kNN和DBD-kNN算法的檢測效果.

實驗3算法性能對比.綜合上述實驗，基于反向k近鄰的優(yōu)化算法能夠?qū)NN算法的檢測結(jié)果進行優(yōu)化，為進一步驗證算法的優(yōu)越性，將SDD-RkNN、DBD-RkNN算法與帶證據(jù)集的動態(tài)統(tǒng)計檢測(DSDD-E)算法[13]進行性能比較.為更好地檢測均衡式刷信譽的方式引入二階直方圖技術(shù)，實驗結(jié)果如表1和2所示.

圖5 反向過濾干擾值法在原始數(shù)據(jù)集下實驗結(jié)果Fig.5 Experimental results of reverse filtering interference value method in original data set

圖6 反向過濾干擾值法在增強數(shù)據(jù)集下實驗結(jié)果Fig.6 Experimental results of reverse filtering interference value method in enhanced data set

表1 原始數(shù)據(jù)集下的算法性能對比Tab.1 Comparison of algorithm performance in raw data set

表2 增強數(shù)據(jù)集下的算法性能對比Tab.2 Comparison of algorithm performance in enhanced data set

由表1可知，集中式刷信譽模式下最好的F1值可達到99.69%，而均衡式刷信譽模式下最高的F1值為80.92%.由表2可知，集中式刷信譽模式下的最優(yōu)F1值可達到96.30%，而均衡式刷信譽模式下最高的F1值為81.85%.因此，集中式刷信譽模式比均衡式刷信譽模式更易于檢測.這是由于集中式刷信譽模式下異常集群的數(shù)據(jù)分布明顯區(qū)別于正常集群，所以異常集群具有較高的異常得分.均衡式刷信譽模式由于異常集群與正常集群的數(shù)據(jù)分布比較相似而較難檢測.盡管如此，在一階直方圖下，從表1和2的均衡式刷信譽模式中可見，SDD-RkNN方法下的F1值分別從20.92%、16.92%提升至DBD-RkNN方法下的79.38%與81.85%.可見，對微小變化敏感的歐式距離仍然可以較好地識別均衡式刷信譽模式下的異常集體.均衡式刷信譽模式中，SDD-RkNN方法在一階和二階直方圖下的F1值分別從20.92%、16.92%提升至80.92%以及79.69%.由此可見，二階直方圖技術(shù)的應(yīng)用有利于發(fā)現(xiàn)均衡式異常.這是由于二階直方圖的技術(shù)通過改變數(shù)據(jù)分布放大了異常集體與正常集體的分布差異導(dǎo)致的.

對明顯區(qū)別于正常集群的集中式異常的檢測，由表1的集中式刷信譽模式可見，使用DSDD-E算法時F1值為87.99%，使用DBD-RkNN算法后F1值可達到99.69%.同時，由表1其余內(nèi)容可見，所提算法的P、R和F1值均優(yōu)于DSDD-E算法.這是由于DSDD-E算法計算的是局部差異，而SDD-RkNN和DBD-RkNN算法是與待測數(shù)據(jù)集進行全局數(shù)據(jù)的差異比較，能夠獲得更準確的信息.所以與DSDD-E算法相比，所提算法的性能更優(yōu).所提算法在建立全局距離權(quán)圖時，需要計算每兩個集群之間的距離，時間復(fù)雜度為O(n2)，算法的時間資源消耗較高.SDD-RkNN算法性能與DBD-RkNN算法性能幾乎一樣優(yōu)秀，但歐式距離的度量方式比JSD方式節(jié)省了一半的時間資源，這是由兩種不同相似性度量計算方式帶來的差異.

實驗4算法穩(wěn)定性分析.穩(wěn)定性是評價算法性能的重要指標之一，為更好地觀察算法的穩(wěn)定性，取不同的U對算法的穩(wěn)定性進行分析.實驗數(shù)據(jù)集由正常交易數(shù)據(jù)集依次替換不同數(shù)目、不同刷信譽模式的異常集群構(gòu)成.考慮到實際生活中異常出現(xiàn)的概率一般不會超過數(shù)據(jù)集的總量一半，因此分別取U=10%、20%、30%、40%、50%進行不同衡量指標的檢測.對于不能很好地識別出均衡式刷信譽的算法使用二階技術(shù)進行檢測.實驗結(jié)果如圖7所示.

圖7 不同異常概率下，3種算法的穩(wěn)定性對比Fig.7 Comparison of stability of three algorithms under different anomaly probabilities

由圖7可知，對于A和F1值這兩項評價指標，越平穩(wěn)的接近圖正上方，則算法性能越穩(wěn)定.SDD-RkNN算法和DBD-RkNN算法的性能評價指標折線圖比DSDD-E算法的性能評價指標折線圖更接近圖的正上方，故所提算法具有更高的穩(wěn)定性和更好的性能.由圖7(d)可知，DSDD-E算法的F1值在不同異常概率下明顯偏離SDD-RkNN算法和DBD-RkNN算法的F1值，這是由于SDD-RkNN算法和DBD-RkNN算法總是通過全局比較獲得異常得分，因此異常比例對該算法的影響較小.而DSDD-E算法依賴于數(shù)據(jù)分布估計的準確性，在使用二階技術(shù)時，直方圖變得粗糙，因此該算法的檢測性能明顯較差.

4 結(jié)語

本文提出一種無監(jiān)督式的基于反向k近鄰法的群數(shù)據(jù)異常檢測算法.對無數(shù)據(jù)標簽的數(shù)據(jù)集進行集體數(shù)據(jù)的劃分，直接建立模型檢測異常.根據(jù)集群數(shù)據(jù)的分布相似性，使用JSD作為k近鄰算法在求取異常得分時的距離度量，針對異常值之間相互干擾的問題提出使用反向k近鄰對異常值進行過濾，優(yōu)化算法性能.

通過大量對比實驗可見，基于反向k近鄰過濾異常值的方法能有效提高kNN算法的檢測質(zhì)量.歐式距離對微小變化足夠敏感，因此在不使用二階直方圖的技術(shù)下也能較好地識別出均衡式刷信譽模式.在二階技術(shù)的使用下，SDD-RkNN算法能較好地識別出此異常，同時該算法具有較強的穩(wěn)定性.通過與引入的DSDD-E算法的對比，所提的SDD-RkNN算法能更好地識別出異常，可應(yīng)用于相關(guān)數(shù)據(jù)資源的檢測和篩選中.