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

吳金娥， 王若愚， 段倩倩， 李國(guó)強(qiáng), ， 琚長(zhǎng)江

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

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

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

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

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

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

1.1 相似性度量

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

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

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

(1)

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

(2)

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

(3)

當(dāng)使用歐式距離作為相似性度量時(shí)，g、l間的距離表達(dá)式則為

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

(4)

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

(5)

1.2 k近鄰與反向k近鄰

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

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

l∈{C-{g}}}

(6)

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

(7)

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

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

(8)

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

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

2.1 模型建立

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

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

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

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

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

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

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

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

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

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

(12) end for

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

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

(15) returnSm

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

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

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

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

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

為解決由上述原因產(chǎn)生的誤報(bào)和漏報(bào)問題，對(duì)算法初步輸出的異常值使用反向k近鄰法進(jìn)行過濾，從而提升算法的性能.反向分析上述問題產(chǎn)生的原因，如果算法判別為正常集群的k個(gè)最近鄰中包含判別為異常的集群，那么該正常集群很有可能是受其他異常集群的干擾而被誤判的.所以在該方法中應(yīng)首先找到初步輸出的異常集群的反向k近鄰，對(duì)反向k近鄰中被初步識(shí)別為正常的集群重新計(jì)算k近鄰，且該k近鄰不再包含已知的異常集群.然后再重新計(jì)算異常得分，更新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←對(duì)所有集群按α(ci)值進(jìn)行降序排列

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

(10) returnSm

3 實(shí)驗(yàn)及其結(jié)果分析

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果評(píng)價(jià)指標(biāo)介紹

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

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

(9)

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

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

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

(6) 運(yùn)行時(shí)間：該項(xiàng)指標(biāo)記錄的是算法完成檢測(cè)所需的時(shí)間，該指標(biāo)越小，則代表算法性能越好.

3.3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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