杜旭升 ，于 炯 ，*，葉樂樂 ，陳嘉穎

（1.新疆大學(xué)軟件學(xué)院，烏魯木齊830008； 2.新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊830046；3.西安交通大學(xué)軟件學(xué)院，西安710049）

（?通信作者電子郵箱yujiong@xju.edu.cn）

0 引言

離群點(diǎn)是指那些在數(shù)據(jù)集中偏離大多數(shù)對(duì)象，讓人不得不懷疑它是由某種不同于其他大多數(shù)對(duì)象的機(jī)制所產(chǎn)生的數(shù)據(jù)對(duì)象［1］。換言之，數(shù)據(jù)集中的絕大多數(shù)對(duì)象都服從某種確定的模式P，而離群點(diǎn)是那些不服從模式P的數(shù)據(jù)對(duì)象［2］。離群點(diǎn)檢測(cè)常用于如網(wǎng)絡(luò)入侵檢測(cè)、醫(yī)療輔助診斷、金融欺詐檢測(cè)、交通流中異常行為檢測(cè)、變質(zhì)農(nóng)畜產(chǎn)品檢測(cè)等，在天文學(xué)中離群點(diǎn)檢測(cè)也被用來(lái)發(fā)現(xiàn)新天體［3-7］。

傳統(tǒng)的無(wú)監(jiān)督離群點(diǎn)檢測(cè)算法，如基于距離的LDOF（Local Distance-Based Outlier Factor）、CBOF（Cohesiveness-Based Outlier Factor）及基于密度的 LOF（Local Outlier Factor）算法在檢測(cè)高維數(shù)據(jù)集和大規(guī)模數(shù)據(jù)集時(shí)，存在檢測(cè)率低、算法執(zhí)行時(shí)間長(zhǎng)、對(duì)參數(shù)敏感等問題。針對(duì)上述問題，本文提出了一種基于圖上隨機(jī)游走（Based on Graph Random Walk，BGRW）的離群點(diǎn)檢測(cè)算法。

基于圖上隨機(jī)游走的離群點(diǎn)檢測(cè)算法，將待檢測(cè)數(shù)據(jù)集中的數(shù)據(jù)對(duì)象建模為圖中的頂點(diǎn)，圖上各頂點(diǎn)相連邊上的權(quán)重表示漫步者由某一頂點(diǎn)出發(fā)，一步移動(dòng)到另一頂點(diǎn)的概率。BGRW算法通過計(jì)算數(shù)據(jù)集對(duì)象間的轉(zhuǎn)移概率，并通過用戶預(yù)設(shè)的迭代次數(shù)和阻尼因子，迭代計(jì)算出所有對(duì)象的離群值。在UCI（University of California，Irvine）真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集實(shí)驗(yàn)表明，BGRW算法與無(wú)監(jiān)督檢測(cè)算法相比，在檢測(cè)率與執(zhí)行時(shí)間和誤報(bào)率等指標(biāo)上效果具有明顯的提升。

基于圖上隨機(jī)游走的BGRW離群點(diǎn)檢測(cè)算法的主要?jiǎng)?chuàng)新之處在于：

1）提出了一種數(shù)據(jù)集中對(duì)象間的轉(zhuǎn)移概率計(jì)算方法。對(duì)象之間的距離越遠(yuǎn)，則轉(zhuǎn)移概率越大。

2）提出了利用漫步者在數(shù)據(jù)集中對(duì)象間的隨機(jī)游走概率求解對(duì)象離群值的計(jì)算方法。通過計(jì)算數(shù)據(jù)集中對(duì)象經(jīng)t步游走之后的離群值，對(duì)象的離群值越高，代表其越可能是離群點(diǎn)；相反，其越不可能是離群點(diǎn)。

1 相關(guān)研究

早期針對(duì)離群點(diǎn)檢測(cè)的相關(guān)研究主要是為了消除數(shù)據(jù)集當(dāng)中的噪聲，以提高數(shù)據(jù)分析的質(zhì)量［8］，但“一個(gè)人的噪聲可能是另一個(gè)人的信號(hào)”［9］。離群點(diǎn)不同于噪聲點(diǎn)，噪聲一般為數(shù)據(jù)隨機(jī)分布中的隨機(jī)誤差，因此并不具有很大價(jià)值。而離群點(diǎn)由于其隱藏的可重復(fù)的產(chǎn)生機(jī)制，通過離群點(diǎn)檢測(cè)發(fā)現(xiàn)數(shù)據(jù)集中的隱藏機(jī)制有著重要意義?，F(xiàn)階段人們檢測(cè)離群點(diǎn)的主要目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)集中隱藏的有益信息或者未知的知識(shí)［10］。

目前主流離群點(diǎn)檢測(cè)算法包括：1）基于聚類，2）基于單分類支持向量機(jī)，3）基于密度，4）基于自編碼器，5）基于孤立森林，6）基于距離。

1）基于聚類的檢測(cè)算法將離群點(diǎn)檢測(cè)問題定義為聚類問題。算法通過計(jì)算對(duì)象與其最近簇的質(zhì)心之間的距離，給數(shù)據(jù)集中每個(gè)對(duì)象的離群程度打分，得分越高，表示該對(duì)象越有可能是離群點(diǎn)。該算法主要缺點(diǎn)在于算法的主要目標(biāo)是發(fā)現(xiàn)數(shù)據(jù)集中的簇，而不是離群點(diǎn)，因此檢測(cè)效率較低，且算法針對(duì)性較強(qiáng)，較依賴于簇的個(gè)數(shù)［11］。

2）基于單分類支持向量機(jī)的檢測(cè)算法通過學(xué)習(xí)數(shù)據(jù)集中絕大多數(shù)對(duì)象的邊界，將邊界以外的數(shù)據(jù)對(duì)象定義為離群點(diǎn)。該算法的主要缺點(diǎn)在于算法學(xué)習(xí)時(shí)間長(zhǎng)，難以解決稀疏問題［12］。

3）基于密度的檢測(cè)算法通過計(jì)算數(shù)據(jù)集中對(duì)象的局部密度和對(duì)象k近鄰的局部密度，最后將對(duì)象與其k近鄰局部密度相差較大的對(duì)象定義為數(shù)據(jù)集中的離群點(diǎn)?；诿芏鹊臋z測(cè)算法主要缺點(diǎn)在于算法在高維數(shù)據(jù)集和大規(guī)模數(shù)據(jù)集中檢測(cè)時(shí)間長(zhǎng)、檢測(cè)效率低，并且對(duì)序列數(shù)據(jù)和低密度數(shù)據(jù)不能有效度量［13］。

4）基于自編碼器的檢測(cè)算法首先訓(xùn)練一個(gè)輸入盡可能等于輸出的神經(jīng)網(wǎng)絡(luò)，然后將測(cè)試數(shù)據(jù)輸入該神經(jīng)網(wǎng)絡(luò)進(jìn)行重構(gòu)，最后將重構(gòu)誤差最大的對(duì)象定義為離群點(diǎn)。該算法的主要缺點(diǎn)在于對(duì)數(shù)據(jù)量較小的數(shù)據(jù)集，神經(jīng)網(wǎng)絡(luò)不能充分學(xué)習(xí)到正常樣本的特征，檢測(cè)準(zhǔn)確率低［14］。

5）基于孤立森林的檢測(cè)算法通過利用一種名為iTree的二叉搜索樹結(jié)構(gòu)來(lái)孤立數(shù)據(jù)集中的對(duì)象。離群點(diǎn)會(huì)距離iTree的根節(jié)點(diǎn)更近，而正常對(duì)象會(huì)距離iTree的根節(jié)點(diǎn)更遠(yuǎn)。基于孤立森林的檢測(cè)算法缺點(diǎn)在于樹的劃分主觀性較強(qiáng)［15］。

6）基于距離的離群點(diǎn)檢測(cè)算法是目前應(yīng)用最為廣泛的檢測(cè)算法。算法通過計(jì)算數(shù)據(jù)集中兩兩對(duì)象之間的距離，然后計(jì)算對(duì)象與其k近鄰的距離關(guān)系，最后得到對(duì)象的離群值?；诰嚯x的檢測(cè)算法主要缺點(diǎn)在于算法在高維及大規(guī)模數(shù)據(jù)集中檢測(cè)效率低、必須使用全局閾值、檢測(cè)結(jié)果對(duì)參數(shù)選擇較為敏感［16-17］。

隨著數(shù)據(jù)量的增長(zhǎng)，現(xiàn)有離群點(diǎn)檢測(cè)算法效率低的問題逐漸凸顯，近年來(lái)部分學(xué)者提出了許多改進(jìn)方法：袁鐘等［18］針對(duì)傳統(tǒng)離群點(diǎn)檢測(cè)算法不能有效處理符號(hào)型與數(shù)值型屬性混合的數(shù)據(jù)集中離群點(diǎn)的檢測(cè)問題，提出了一種改進(jìn)的基于鄰域值差異度量的算法；王習(xí)特等［19］針對(duì)傳統(tǒng)集中式的離群點(diǎn)檢測(cè)方法計(jì)算時(shí)間長(zhǎng)、檢測(cè)效率低的問題，提出了一種高效的分布式離群點(diǎn)檢測(cè)算法；Schiff等［20］將離群點(diǎn)檢測(cè)技術(shù)應(yīng)用到偵測(cè)醫(yī)生對(duì)患者開具的處方藥潛在的用藥錯(cuò)誤中，有效降低了患者的用藥風(fēng)險(xiǎn)；Huang［21］利用離群點(diǎn)檢測(cè)技術(shù)偵測(cè)電子商務(wù)系統(tǒng)中商家偽造買家評(píng)論，有效降低了評(píng)論造假現(xiàn)象；Alaverdyan等［22］將離群點(diǎn)檢測(cè)技術(shù)應(yīng)用到癲癇病灶的篩查中，為醫(yī)生快速定位患者疾病提供了較好的解決方案。

2 基于圖上隨機(jī)游走的離群點(diǎn)檢測(cè)算法

隨機(jī)游走也稱隨機(jī)漫步，是隨機(jī)過程的一個(gè)重要組成部分?；趫D的隨機(jī)游走是指給定一個(gè)圖G和一個(gè)出發(fā)點(diǎn)v（0），漫步者從出發(fā)點(diǎn)v（0）開始，隨機(jī)選擇圖G中的一個(gè)頂點(diǎn)移動(dòng)，然后以該頂點(diǎn)為出發(fā)點(diǎn)，再重新選擇一頂點(diǎn)進(jìn)行移動(dòng)，依此重復(fù)。漫步者在圖G中隨機(jī)選擇的頂點(diǎn)集合構(gòu)成了圖中的隨機(jī)游走。

在給出關(guān)于圖上隨機(jī)游走的BGRW算法的相關(guān)定義之前，先給出關(guān)于隨機(jī)過程的相關(guān)定義與性質(zhì)。

定義1 隨機(jī)過程。設(shè)（Ω，F(xiàn)，P）為一概率空間，T和S為參數(shù)集。若對(duì)任意的t∈T，均有定義在（Ω，F(xiàn)，P）上的一個(gè)取值為S的隨機(jī)變量X（ω，t）（ω∈Ω）與之對(duì)應(yīng)，則稱隨機(jī)變量族X（ω，t）為（Ω，F(xiàn)，P）上的一個(gè)隨機(jī)過程，記作｛X（ω，t），ω∈Ω，t∈T｝，簡(jiǎn)記為｛X（t），t∈T｝。

定義2 馬爾可夫鏈。若隨機(jī)過程｛X（t），t=0，1，…｝對(duì)于任意的正整數(shù)n及t1＜t2＜…＜tn∈T，其條件分布滿足：

則稱隨機(jī)過程｛X(t)，t∈T｝為馬爾可夫鏈。

定義3 轉(zhuǎn)移概率。稱式（1）中的條件概率P｛X（tn）=xn|X（tn-1）=xn-1｝為隨機(jī)過程｛X（t），t∈T｝的一步轉(zhuǎn)移概率，簡(jiǎn)稱轉(zhuǎn)移概率。

性質(zhì)1 轉(zhuǎn)移概率。

隨機(jī)過程的狀態(tài)空間記作S，i、j∈S，則有：

定義4t步轉(zhuǎn)移概率。隨機(jī)過程經(jīng)t步由狀態(tài)i轉(zhuǎn)移到j(luò)的概率記作：

稱為馬爾可夫鏈的t步轉(zhuǎn)移概率，其中s≥0，t≥1。

2.1 BGRW算法的相關(guān)定義

設(shè)D={d1，d2，…，d n}表示輸入數(shù)據(jù)的集合，其中di=表示數(shù)據(jù)集D中的任一數(shù)據(jù)對(duì)象，k表示輸入數(shù)據(jù)的維度。dij表示對(duì)象di在第j個(gè)維度上的值，E（di，dj）表示數(shù)據(jù)集D中任意兩個(gè)對(duì)象di，dj之間的歐氏距離。

定義5 頂點(diǎn)集。設(shè)V=｛v1，v2，…，vn｝表示頂點(diǎn)集，其中vi表示圖中的第i個(gè)頂點(diǎn)（在BGRW算法中也表示輸入數(shù)據(jù)D中的第i個(gè)對(duì)象di），n表示V中所含頂點(diǎn)數(shù)。

定義6 邊集。設(shè)ε=｛e1，e2，…，ek，…｝表示圖中各邊的集合，ek=（vi，vj）表示頂點(diǎn)vi與頂點(diǎn)vj相連的邊，其中ε?V×V。

定義7圖。設(shè)G=（V，ε）表示圖，若?（vi，vj）∈ε，有（vj，vi）∈ε，則稱G為無(wú)向圖；相反，稱圖G為有向圖。

定義8 轉(zhuǎn)移概率矩陣。設(shè)wij=w(vi，vj)表示頂點(diǎn)vi，vj相連邊上的權(quán)重，pij表示數(shù)據(jù)集D中對(duì)象di轉(zhuǎn)移到dj的概率，則有。定義wij的計(jì)算方法如式（5）所示：

式（5）中：di、dj、dl表示數(shù)據(jù)集D中任意一個(gè)數(shù)據(jù)對(duì)象，n表示數(shù)據(jù)集D中所含對(duì)象的個(gè)數(shù))表示對(duì)象di到數(shù)據(jù)集D中所有對(duì)象的歐氏距離之和。由式（5）可知，E（di，dj）占di到數(shù)據(jù)集中所有對(duì)象的距離之和的比值越大，則di轉(zhuǎn)移到dj的概率越大。對(duì)象di轉(zhuǎn)移到dj的概率并不一定等于由dj轉(zhuǎn)移到di的概率，即wij≠wji。由wij組成的矩陣稱為轉(zhuǎn)移概率矩陣，記作W=[wij]n×n。

在轉(zhuǎn)移概率矩陣W中任一元素wvi vj表示頂點(diǎn)vi轉(zhuǎn)移到vj的概率，根據(jù)式（2）可知，矩陣W中的每一行總和為1。為避免在圖中形成自循環(huán)，將頂點(diǎn)轉(zhuǎn)移到自身的概率設(shè)置為0，即wvivi=0。

如圖1所示，d1、d2、d3、d4為輸入數(shù)據(jù)D中的4個(gè)對(duì)象，任意兩個(gè)頂點(diǎn)相連邊上的數(shù)字表示頂點(diǎn)間的一步轉(zhuǎn)移概率。由任一頂點(diǎn)出發(fā)轉(zhuǎn)移到圖中其余所有頂點(diǎn)的轉(zhuǎn)移概率之和為1。圖1中若以d2為出發(fā)點(diǎn)，則漫步者下一步轉(zhuǎn)移到d1的概率為2/14，轉(zhuǎn)移到d3的概率為5/14，轉(zhuǎn)移到d4的概率為7/14。圖1中所有對(duì)象一步轉(zhuǎn)移到d1的概率之和為2/14+4/18+1/17=0.423 9，轉(zhuǎn)移到d2的概率之和為0.975 2，轉(zhuǎn)移到d3的概率之和為1.4579，轉(zhuǎn)移到d4的概率之和為1.1428。

圖1 基于圖的隨機(jī)游走示例Fig.1 Exampleof graph-based random walk

定義9 離群值矩陣OD。

其中：tn為迭代次數(shù)，n為輸入數(shù)據(jù)D含有的對(duì)象個(gè)數(shù)，fac為阻尼因子。OD tn-1表示在tn-1次迭代后，數(shù)據(jù)集D中所有對(duì)象的離群值構(gòu)成的離群值矩陣，WT表示轉(zhuǎn)移概率矩陣的轉(zhuǎn)置。

阻尼因子fac在圖中表示不以當(dāng)前頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行隨機(jī)游走，而重新選擇另一頂點(diǎn)進(jìn)行隨機(jī)游走的概率。1-fac表示漫步者仍以當(dāng)前頂點(diǎn)為出發(fā)點(diǎn)，再進(jìn)行隨機(jī)游走的概率，fac一般取0～1的一個(gè)較小值。(WTOD tn-1)i表示第tn-1次迭代運(yùn)算后，數(shù)據(jù)集D中對(duì)象的離群值矩陣乘轉(zhuǎn)移概率矩陣WT后第i行的值。

當(dāng)tn=0時(shí)，BGRW算法初始化輸入數(shù)據(jù)D中所有對(duì)象的離群值。WTOD tn=0如式（8）所示：

轉(zhuǎn)移概率矩陣W是n×n矩陣，數(shù)據(jù)集D的離群值矩陣OD是n×1矩陣，二者相乘后所得WTOD矩陣是n×1矩陣，離群值OD矩陣中任意一行i的值表示數(shù)據(jù)集D中對(duì)象di的離群值。

基于圖上隨機(jī)游走的BGRW離群點(diǎn)檢測(cè)算法，將輸入數(shù)據(jù)建模為圖中的頂點(diǎn)，各頂點(diǎn)之間的轉(zhuǎn)移概率建模為圖上各頂點(diǎn)相連邊上的權(quán)重。BGRW離群點(diǎn)檢測(cè)算法根據(jù)用戶預(yù)設(shè)的迭代次數(shù)與阻尼因子，首先初始化待檢測(cè)數(shù)據(jù)集D中所有對(duì)象的離群值，然后計(jì)算各對(duì)象之間的歐氏距離，并利用式（5）計(jì)算出各對(duì)象之間的轉(zhuǎn)移概率，構(gòu)建轉(zhuǎn)移概率矩陣W。最后利用式（7）求得對(duì)象的離群值，將計(jì)算完成后離群值最高的前g個(gè)對(duì)象的編號(hào)輸出。

2.2 BGRW算法描述

2.3 BGRW算法時(shí)間復(fù)雜度分析

在BGRW算法描述中，步驟1）～3）初始化數(shù)據(jù)集D中對(duì)象的離群值，時(shí)間復(fù)雜度為O（n）；步驟4）～8）計(jì)算數(shù)據(jù)集D中兩兩數(shù)據(jù)對(duì)象之間的距離，時(shí)間復(fù)雜度為O（n2）；步驟9）～13）運(yùn)用式（5）計(jì)算對(duì)象之間的轉(zhuǎn)移概率并構(gòu)建轉(zhuǎn)移概率矩陣，所需時(shí)間復(fù)雜度為O（n2）；步驟16）～24）運(yùn)用式（7）迭代計(jì)算每個(gè)對(duì)象的離群值，所需時(shí)間復(fù)雜度為O（n2）；步驟25）中對(duì)數(shù)據(jù)對(duì)象的離群值排序，所需時(shí)間復(fù)雜度為O（nlbn）。綜上可得BGRW算法的時(shí)間復(fù)雜度規(guī)模為O（n2）。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境及評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)的硬件環(huán)境為：Intel Core i7-7700 CPU 3.60 GHz，內(nèi)存為16 GB。操作系統(tǒng)環(huán)境為：Microsoft Windows 10 Professional，算法的實(shí)現(xiàn)環(huán)境為：Matlab 2017A。

實(shí)驗(yàn)所用數(shù)據(jù)集分為真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集，真實(shí)數(shù)據(jù)集均采用UCI公開數(shù)據(jù)集，分別為：KDD-CUP99（Data Mining and Knowledge Discovery in 1999）、Glass Identification、WDBC（Wisconsin Date of Breast Cancer）、Shuttle。 為 驗(yàn) 證BGRW 算法的有效性，將其與 LDOF［16］、CBOF［17］、LOF［13］三種算法在各數(shù)據(jù)集中進(jìn)行對(duì)比實(shí)驗(yàn)，采用準(zhǔn)確率ACC（Accuracy）、檢測(cè)率（Detection Rate，DR）、誤報(bào)率（False Alarm Rate，F(xiàn)AR）以及執(zhí)行時(shí)間（Execution Time，ET）作為算法性能的評(píng)價(jià)指標(biāo)。

其中：TP（True Positive）是指算法將異常樣本正確標(biāo)記為異常樣本的數(shù)量，TN（True Negative）是指算法將正常樣本正確標(biāo)記為正常樣本的數(shù)量，F(xiàn)P（False Positive）是指算法將正常樣本錯(cuò)誤標(biāo)記為異常樣本的數(shù)量，F(xiàn)N（False Negative）是指算法將異常樣本錯(cuò)誤標(biāo)記為正常樣本的數(shù)量。

3.2 KDD-CUP99數(shù)據(jù)集

KDD-CUP99數(shù)據(jù)集是離群點(diǎn)檢測(cè)研究中常用的網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集，數(shù)據(jù)集中每個(gè)對(duì)象有41個(gè)特征，其中38個(gè)特征為數(shù)值型，3個(gè)特征為字符型。KDD-CUP99共包含有四種攻擊類型，分別為：DoS（Denial of Service）、Probe、U2R（User to Root）、R2L（Remote to Local）。數(shù)據(jù)集的詳細(xì)信息如表 1所示。

表1 KDD-CUP99數(shù)據(jù)集詳細(xì)信息Tab.1 Details of KDD-CUP99 dataset

如表1所示，KDD-CUP99數(shù)據(jù)集中的四種攻擊類型可細(xì)分為39種攻擊類型：22種出現(xiàn)在訓(xùn)練數(shù)據(jù)集中，17種出現(xiàn)在測(cè)試數(shù)據(jù)集中。為適應(yīng)實(shí)驗(yàn)需要，先對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理。處理流程如下：

首先將數(shù)據(jù)集中部分重復(fù)數(shù)據(jù)刪除，其次刪除特征num_outbound_cmds、is_hot_login（兩個(gè)特征在數(shù)據(jù)集中取值均為0，對(duì)實(shí)驗(yàn)結(jié)果無(wú)影響），最后對(duì)數(shù)據(jù)集中對(duì)象進(jìn)行離差標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)化方法如下：

其中：d表示某個(gè)特征列的值，min是該特征列的最小值，max是該特征列的最大值。在處理后的正常數(shù)據(jù)對(duì)象中，添加Probe、DoS、U2R、R2L四種攻擊類型的數(shù)據(jù)對(duì)象，使攻擊類型的對(duì)象占數(shù)據(jù)集總個(gè)數(shù)的5%。處理后的數(shù)據(jù)集共計(jì)85 146個(gè)對(duì)象，其中：Probe類型1350個(gè)，DoS類型2000個(gè)，U2R類型300個(gè)，R2L類型607個(gè)。

表2中第6列參數(shù)取值表示各算法在KDD-CUP99數(shù)據(jù)集中檢測(cè)率達(dá)到最高時(shí)，算法對(duì)應(yīng)參數(shù)的取值。通過對(duì)比各算法在最高檢測(cè)率時(shí)的準(zhǔn)確率、誤報(bào)率及執(zhí)行時(shí)間（Execution Time，ET），可更加公平有效地評(píng)價(jià)各算法的性能。由表2可知，BGRW算法在迭代217次后，達(dá)到最高檢測(cè)率0.97，LDOF算法在參數(shù)k取值71時(shí)達(dá)到最高檢測(cè)率0.77，CBOF算法最高檢測(cè)率為0.92，LOF算法最高檢測(cè)率為0.83。BGRW算法的準(zhǔn)確率與檢測(cè)率均高于對(duì)比的三種算法，誤報(bào)率0.0015與執(zhí)行時(shí)間422 s明顯低于其他三種算法。

表2 KDD-CUP99數(shù)據(jù)集中各算法的檢測(cè)性能Tab.2 Detectionperformanceof each algorithm in KDD-CUP99dataset

3.3 Glass Identification數(shù)據(jù)集

Glass Identification數(shù)據(jù)集共包含214個(gè)數(shù)據(jù)對(duì)象，分為6種類型。每個(gè)對(duì)象有9個(gè)特征，特征1表示對(duì)象的折射率，特征2～9表示對(duì)象所含的化學(xué)元素在單位重量?jī)?nèi)所占百分比。對(duì)Glass Identification數(shù)據(jù)集進(jìn)行處理，刪除第4類與第6類部分對(duì)象，余留共計(jì)10個(gè)對(duì)象作為離群點(diǎn)。處理后的數(shù)據(jù)集中對(duì)象之間最小距離為0.076 8，最大距離為11.823 3，近鄰數(shù)k最小為1。

如表3所示，BGRW算法在t=75時(shí)達(dá)到最高檢測(cè)率0.8，LDOF算法在參數(shù)k取值7時(shí)達(dá)到最高檢測(cè)率0.6，CBOF算法在參數(shù)k取值13時(shí)達(dá)到最高檢測(cè)率0.6，LOF算法在參數(shù)k取值11時(shí)達(dá)到最高檢測(cè)率0.7。BGRW算法相較于執(zhí)行時(shí)間最短的CBOF算法，所用執(zhí)行時(shí)間縮短為CBOF算法的1/6，相比于執(zhí)行時(shí)間最長(zhǎng)的LOF算法，所用執(zhí)行時(shí)間縮短為L(zhǎng)OF算法的1/13。

表3 Glass Identification數(shù)據(jù)集中各算法檢測(cè)性能Tab.3 Detection performanceof each algorithm in Glass Identification dataset

3.4 WDBC數(shù)據(jù)集

WDBC數(shù)據(jù)集含有569個(gè)對(duì)象，每個(gè)對(duì)象有32個(gè)特征，屬于高維數(shù)據(jù)集。WDBC數(shù)據(jù)集分為惡性與良性腫瘤兩類對(duì)象，其中惡性對(duì)象數(shù)據(jù)共計(jì)212條。對(duì)WDBC數(shù)據(jù)集進(jìn)行處理，在良性腫瘤數(shù)據(jù)中添加20條惡性腫瘤數(shù)據(jù)，測(cè)試BGRW、LDOF、CBOF、LOF四種算法的檢測(cè)性能。

如表4所示，在迭代25次后，BGRW算法達(dá)到了最高檢測(cè)率0.85，LDOF算法的最高檢測(cè)率為0.65，CBOF算法的最高檢測(cè)率為0.75，LOF算法的最高檢測(cè)率為0.8。BGRW算法在執(zhí)行時(shí)間、準(zhǔn)確率、檢測(cè)率及誤報(bào)率方面均優(yōu)于LDOF、CBOF及LOF算法。

表4 WDBC數(shù)據(jù)集中各算法檢測(cè)性能Tab.4 Detection performance of each algorithm in WDBCdataset

3.5 Shuttle數(shù)據(jù)集

Shuttle數(shù)據(jù)集共計(jì)58 000個(gè)對(duì)象，共分為7種類型，其中78.59%的對(duì)象屬于第一類。數(shù)據(jù)集中每個(gè)對(duì)象有9個(gè)特征，所有特征均為整數(shù)型。為適應(yīng)實(shí)驗(yàn)需要，將數(shù)據(jù)集中2～7類的部分對(duì)象刪除，余留部分作為離群點(diǎn)，使數(shù)據(jù)集當(dāng)中的離群點(diǎn)比例占整個(gè)數(shù)據(jù)集的5%，處理后的數(shù)據(jù)集共計(jì)47985個(gè)對(duì)象。四種算法的檢測(cè)結(jié)果如表5所示。

表5 Shuttle數(shù)據(jù)集中各算法的檢測(cè)性能Tab5 Detection performanceof each algorithm in Shuttledataset

由表5可知，在迭代81次后，BGRW算法在Shuttle數(shù)據(jù)集中達(dá)到了最高檢測(cè)率0.87，LDOF算法的最高檢測(cè)率為0.57，CBOF算法最高檢測(cè)率為0.61，LOF算法最高檢測(cè)率為0.63。BGRW算法執(zhí)行時(shí)間為195 s，均低于與之對(duì)比的三種算法的執(zhí)行時(shí)間。

3.6 合成數(shù)據(jù)集

為驗(yàn)證BGRW算法在復(fù)雜分布的合成數(shù)據(jù)集當(dāng)中離群點(diǎn)的檢測(cè)性能，選取了三組合成數(shù)據(jù)集，將BGRW算法與LDOF、CBOF、LOF算法在合成數(shù)據(jù)集中進(jìn)行對(duì)比實(shí)驗(yàn)：第一組合成數(shù)據(jù)集分為7類，由11個(gè)離群對(duì)象與788個(gè)正常對(duì)象構(gòu)成；第二組合成數(shù)據(jù)集共計(jì)404個(gè)對(duì)象，分為6類，由5個(gè)離群對(duì)象與399個(gè)正常對(duì)象構(gòu)成；第三組合成數(shù)據(jù)集共計(jì)406個(gè)對(duì)象，分為3類，由399個(gè)正常對(duì)象與7個(gè)離群對(duì)象構(gòu)成。合成數(shù)據(jù)集如圖2所示。

三組合成數(shù)據(jù)集共計(jì)23個(gè)離群點(diǎn)中，BGRW算法共計(jì)檢測(cè)出21個(gè)離群點(diǎn)，LDOF算法檢測(cè)出11個(gè)離群點(diǎn)，CBOF算法檢測(cè)出15個(gè)離群點(diǎn)，LOF算法檢測(cè)出15個(gè)離群點(diǎn)，如圖3所示。三組合成數(shù)據(jù)集中BGRW算法的平均檢測(cè)率為0.913，LDOF算法的平均檢測(cè)率為0.478，CBOF算法的平均檢測(cè)率為0.652，LOF算法的平均檢測(cè)率為0.652，實(shí)驗(yàn)結(jié)果證明BGRW算法是有效可行的。

圖2 合成數(shù)據(jù)集Fig.2 Synthetic dataset

圖3 4種算法在三組合成數(shù)據(jù)集中的檢測(cè)結(jié)果Fig.3 Detection resultsof four algorithmsin three synthetic datasets

4 結(jié)語(yǔ)

針對(duì)基于距離的LDOF、CBOF與基于密度的LOF離群點(diǎn)檢測(cè)算法檢測(cè)率低且執(zhí)行時(shí)間長(zhǎng)的問題，提出了基于圖上隨機(jī)游走的BGRW離群點(diǎn)檢測(cè)算法。BGRW算法構(gòu)建了數(shù)據(jù)集中對(duì)象之間的轉(zhuǎn)移概率矩陣，通過迭代運(yùn)算，求得對(duì)象的離群值，將離群值最高的對(duì)象判定為數(shù)據(jù)集中的離群點(diǎn)。通過在UCI真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集的對(duì)比實(shí)驗(yàn)證明，BGRW算法相較于對(duì)比算法，降低了執(zhí)行時(shí)間和誤報(bào)率、提高了離群點(diǎn)檢測(cè)準(zhǔn)確率。未來(lái)的工作中，將進(jìn)一步研究如何利用更少的迭代次數(shù)盡快地分離出數(shù)據(jù)集當(dāng)中的離群點(diǎn)，以及研究如何在受損數(shù)據(jù)集中使BGRW算法更具魯棒性。