基于圖上隨機游走的離群點檢測算法

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

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

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

0 引言

離群點是指那些在數據集中偏離大多數對象，讓人不得不懷疑它是由某種不同于其他大多數對象的機制所產生的數據對象［1］。換言之，數據集中的絕大多數對象都服從某種確定的模式P，而離群點是那些不服從模式P的數據對象［2］。離群點檢測常用于如網絡入侵檢測、醫療輔助診斷、金融欺詐檢測、交通流中異常行為檢測、變質農畜產品檢測等，在天文學中離群點檢測也被用來發現新天體［3-7］。

傳統的無監督離群點檢測算法，如基于距離的LDOF（Local Distance-Based Outlier Factor）、CBOF（Cohesiveness-Based Outlier Factor）及基于密度的 LOF（Local Outlier Factor）算法在檢測高維數據集和大規模數據集時，存在檢測率低、算法執行時間長、對參數敏感等問題。針對上述問題，本文提出了一種基于圖上隨機游走（Based on Graph Random Walk，BGRW）的離群點檢測算法。

基于圖上隨機游走的離群點檢測算法，將待檢測數據集中的數據對象建模為圖中的頂點，圖上各頂點相連邊上的權重表示漫步者由某一頂點出發，一步移動到另一頂點的概率。BGRW算法通過計算數據集對象間的轉移概率，并通過用戶預設的迭代次數和阻尼因子，迭代計算出所有對象的離群值。在UCI（University of California，Irvine）真實數據集與合成數據集實驗表明，BGRW算法與無監督檢測算法相比，在檢測率與執行時間和誤報率等指標上效果具有明顯的提升。

基于圖上隨機游走的BGRW離群點檢測算法的主要創新之處在于：

1）提出了一種數據集中對象間的轉移概率計算方法。對象之間的距離越遠，則轉移概率越大。

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

1 相關研究

早期針對離群點檢測的相關研究主要是為了消除數據集當中的噪聲，以提高數據分析的質量［8］，但“一個人的噪聲可能是另一個人的信號”［9］。離群點不同于噪聲點，噪聲一般為數據隨機分布中的隨機誤差，因此并不具有很大價值。而離群點由于其隱藏的可重復的產生機制，通過離群點檢測發現數據集中的隱藏機制有著重要意義。現階段人們檢測離群點的主要目標是發現數據集中隱藏的有益信息或者未知的知識［10］。

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

1）基于聚類的檢測算法將離群點檢測問題定義為聚類問題。算法通過計算對象與其最近簇的質心之間的距離，給數據集中每個對象的離群程度打分，得分越高，表示該對象越有可能是離群點。該算法主要缺點在于算法的主要目標是發現數據集中的簇，而不是離群點，因此檢測效率較低，且算法針對性較強，較依賴于簇的個數［11］。

2）基于單分類支持向量機的檢測算法通過學習數據集中絕大多數對象的邊界，將邊界以外的數據對象定義為離群點。該算法的主要缺點在于算法學習時間長，難以解決稀疏問題［12］。

3）基于密度的檢測算法通過計算數據集中對象的局部密度和對象k近鄰的局部密度，最后將對象與其k近鄰局部密度相差較大的對象定義為數據集中的離群點。基于密度的檢測算法主要缺點在于算法在高維數據集和大規模數據集中檢測時間長、檢測效率低，并且對序列數據和低密度數據不能有效度量［13］。

4）基于自編碼器的檢測算法首先訓練一個輸入盡可能等于輸出的神經網絡，然后將測試數據輸入該神經網絡進行重構，最后將重構誤差最大的對象定義為離群點。該算法的主要缺點在于對數據量較小的數據集，神經網絡不能充分學習到正常樣本的特征，檢測準確率低［14］。

5）基于孤立森林的檢測算法通過利用一種名為iTree的二叉搜索樹結構來孤立數據集中的對象。離群點會距離iTree的根節點更近，而正常對象會距離iTree的根節點更遠。基于孤立森林的檢測算法缺點在于樹的劃分主觀性較強［15］。

6）基于距離的離群點檢測算法是目前應用最為廣泛的檢測算法。算法通過計算數據集中兩兩對象之間的距離，然后計算對象與其k近鄰的距離關系，最后得到對象的離群值。基于距離的檢測算法主要缺點在于算法在高維及大規模數據集中檢測效率低、必須使用全局閾值、檢測結果對參數選擇較為敏感［16-17］。

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

2 基于圖上隨機游走的離群點檢測算法

隨機游走也稱隨機漫步，是隨機過程的一個重要組成部分。基于圖的隨機游走是指給定一個圖G和一個出發點v（0），漫步者從出發點v（0）開始，隨機選擇圖G中的一個頂點移動，然后以該頂點為出發點，再重新選擇一頂點進行移動，依此重復。漫步者在圖G中隨機選擇的頂點集合構成了圖中的隨機游走。

在給出關于圖上隨機游走的BGRW算法的相關定義之前，先給出關于隨機過程的相關定義與性質。

定義1 隨機過程。設（Ω，F，P）為一概率空間，T和S為參數集。若對任意的t∈T，均有定義在（Ω，F，P）上的一個取值為S的隨機變量X（ω，t）（ω∈Ω）與之對應，則稱隨機變量族X（ω，t）為（Ω，F，P）上的一個隨機過程，記作｛X（ω，t），ω∈Ω，t∈T｝，簡記為｛X（t），t∈T｝。

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

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

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

性質1 轉移概率。

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

定義4t步轉移概率。隨機過程經t步由狀態i轉移到j的概率記作：

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

2.1 BGRW算法的相關定義

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

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

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

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

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

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

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

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

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

定義9 離群值矩陣OD。

其中：tn為迭代次數，n為輸入數據D含有的對象個數，fac為阻尼因子。OD tn-1表示在tn-1次迭代后，數據集D中所有對象的離群值構成的離群值矩陣，WT表示轉移概率矩陣的轉置。

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

當tn=0時，BGRW算法初始化輸入數據D中所有對象的離群值。WTOD tn=0如式（8）所示：

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

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

2.2 BGRW算法描述

2.3 BGRW算法時間復雜度分析

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

3 實驗

3.1 實驗環境及評價指標

實驗的硬件環境為：Intel Core i7-7700 CPU 3.60 GHz，內存為16 GB。操作系統環境為：Microsoft Windows 10 Professional，算法的實現環境為：Matlab 2017A。

實驗所用數據集分為真實數據集與合成數據集，真實數據集均采用UCI公開數據集，分別為：KDD-CUP99（Data Mining and Knowledge Discovery in 1999）、Glass Identification、WDBC（Wisconsin Date of Breast Cancer）、Shuttle。 為 驗 證BGRW 算法的有效性，將其與 LDOF［16］、CBOF［17］、LOF［13］三種算法在各數據集中進行對比實驗，采用準確率ACC（Accuracy）、檢測率（Detection Rate，DR）、誤報率（False Alarm Rate，FAR）以及執行時間（Execution Time，ET）作為算法性能的評價指標。

其中：TP（True Positive）是指算法將異常樣本正確標記為異常樣本的數量，TN（True Negative）是指算法將正常樣本正確標記為正常樣本的數量，FP（False Positive）是指算法將正常樣本錯誤標記為異常樣本的數量，FN（False Negative）是指算法將異常樣本錯誤標記為正常樣本的數量。

3.2 KDD-CUP99數據集

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

表1 KDD-CUP99數據集詳細信息Tab.1 Details of KDD-CUP99 dataset

如表1所示，KDD-CUP99數據集中的四種攻擊類型可細分為39種攻擊類型：22種出現在訓練數據集中，17種出現在測試數據集中。為適應實驗需要，先對數據集進行預處理。處理流程如下：

首先將數據集中部分重復數據刪除，其次刪除特征num_outbound_cmds、is_hot_login（兩個特征在數據集中取值均為0，對實驗結果無影響），最后對數據集中對象進行離差標準化，標準化方法如下：

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

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

表2 KDD-CUP99數據集中各算法的檢測性能Tab.2 Detectionperformanceof each algorithm in KDD-CUP99dataset

3.3 Glass Identification數據集

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

如表3所示，BGRW算法在t=75時達到最高檢測率0.8，LDOF算法在參數k取值7時達到最高檢測率0.6，CBOF算法在參數k取值13時達到最高檢測率0.6，LOF算法在參數k取值11時達到最高檢測率0.7。BGRW算法相較于執行時間最短的CBOF算法，所用執行時間縮短為CBOF算法的1/6，相比于執行時間最長的LOF算法，所用執行時間縮短為LOF算法的1/13。

表3 Glass Identification數據集中各算法檢測性能Tab.3 Detection performanceof each algorithm in Glass Identification dataset

3.4 WDBC數據集

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

如表4所示，在迭代25次后，BGRW算法達到了最高檢測率0.85，LDOF算法的最高檢測率為0.65，CBOF算法的最高檢測率為0.75，LOF算法的最高檢測率為0.8。BGRW算法在執行時間、準確率、檢測率及誤報率方面均優于LDOF、CBOF及LOF算法。

表4 WDBC數據集中各算法檢測性能Tab.4 Detection performance of each algorithm in WDBCdataset

3.5 Shuttle數據集

Shuttle數據集共計58 000個對象，共分為7種類型，其中78.59%的對象屬于第一類。數據集中每個對象有9個特征，所有特征均為整數型。為適應實驗需要，將數據集中2～7類的部分對象刪除，余留部分作為離群點，使數據集當中的離群點比例占整個數據集的5%，處理后的數據集共計47985個對象。四種算法的檢測結果如表5所示。

表5 Shuttle數據集中各算法的檢測性能Tab5 Detection performanceof each algorithm in Shuttledataset

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

3.6 合成數據集

為驗證BGRW算法在復雜分布的合成數據集當中離群點的檢測性能，選取了三組合成數據集，將BGRW算法與LDOF、CBOF、LOF算法在合成數據集中進行對比實驗：第一組合成數據集分為7類，由11個離群對象與788個正常對象構成；第二組合成數據集共計404個對象，分為6類，由5個離群對象與399個正常對象構成；第三組合成數據集共計406個對象，分為3類，由399個正常對象與7個離群對象構成。合成數據集如圖2所示。

三組合成數據集共計23個離群點中，BGRW算法共計檢測出21個離群點，LDOF算法檢測出11個離群點，CBOF算法檢測出15個離群點，LOF算法檢測出15個離群點，如圖3所示。三組合成數據集中BGRW算法的平均檢測率為0.913，LDOF算法的平均檢測率為0.478，CBOF算法的平均檢測率為0.652，LOF算法的平均檢測率為0.652，實驗結果證明BGRW算法是有效可行的。

圖2 合成數據集Fig.2 Synthetic dataset

圖3 4種算法在三組合成數據集中的檢測結果Fig.3 Detection resultsof four algorithmsin three synthetic datasets

4 結語

針對基于距離的LDOF、CBOF與基于密度的LOF離群點檢測算法檢測率低且執行時間長的問題，提出了基于圖上隨機游走的BGRW離群點檢測算法。BGRW算法構建了數據集中對象之間的轉移概率矩陣，通過迭代運算，求得對象的離群值，將離群值最高的對象判定為數據集中的離群點。通過在UCI真實數據集與合成數據集的對比實驗證明，BGRW算法相較于對比算法，降低了執行時間和誤報率、提高了離群點檢測準確率。未來的工作中，將進一步研究如何利用更少的迭代次數盡快地分離出數據集當中的離群點，以及研究如何在受損數據集中使BGRW算法更具魯棒性。