一種面向樞紐現象的離群數據檢測算法

馬文強，趙旭俊，張繼福，饒元淇

(太原科技大學 計算機科學與技術學院，太原 030024)

E-mail:mwq_93@163.com

1 引 言

離群點挖掘是數據挖掘中的一個重要領域，也被稱作離群點檢測.隨著人工智能技術飛速的發展，對離群點檢測研究的興趣正在大大增加[1].Hawkins[2]將離群點定義如下：離群數據是數據集中偏離大部分對象的數據，它們的表現與大多數常規對象有著明顯的差異，以至于讓人懷疑它們可能是由另外一種完全不同的機制所產生的.但是，離群數據并不全是錯誤數據，離群數據中可能蘊含著極為重要的信息，并已廣泛應用在許多領域，例如天文光譜[3]，信用卡欺詐[4]，網絡異常檢測[5，6]，道路交通異常[7]等.近年來，研究者提出了許多離群檢測算法，其中基于k近鄰(kNN)和逆近鄰(RNN)的離群檢測是重要算法之一.隨著數據維度的增加[8]，一些數據對象(樞紐點)會經常出現在其他數據對象的kNN列表中，其逆近鄰集合中包含的數據對象個數很多，同時，一些數據對象(非樞紐點)幾乎成為不常見的鄰居，其逆近鄰集合中包含的數據對象個數很少或者為零，這種現象稱為樞紐現象.

樞紐現象(Hubness)是高維空間學習中的一個普遍問題，在許多文獻中將其作為一個新的研究方向[9，10].樞紐現象是“維度災難”中與k近鄰查詢相關的概念，它是指數據對象出現在其他數據對象的kNN列表中的次數Nk(i)(即RNN).其出現的原因是由于隨著數據維度的增加，導致數據對象的次數Nk(i)出現的分布出現向右偏斜，同時方差也隨之增加.樞紐現象造成的后果是一些數據對象(hubs，稱為樞紐點)會經常出現在其他數據對象的kNN列表中，同時，一些數據對象(antihubs，稱為非樞紐點)會經常不出現或很少出現在其他數據對象的kNN列表中.非樞紐與離群數據在高維和低維數據上均存在著聯系.本文針對離群檢測中的樞紐現象，結合k近鄰和逆近鄰互補性能，分析了離群檢測中的影響空間，并一種面向樞紐現象的雙向近鄰離群檢測算法，HPOD算法.首先，算法引入并重新定義了對象的影響空間，在影響空間中，不僅考慮對象的k近鄰的影響作用同時還考慮逆近鄰的影響作用；其次，在HPOD算法的基礎上引入了啟發式信息，提出了改進算法HPOD2算法，有效的降低了k的取值，從而減少了算法的計算量和運行時間；最后，采用真實數據集對本文提出的改進算法進行了檢測并證明了本文提出的算法要優于傳統的基于樞紐現象的離群數據挖掘算法.

2 相關工作

傳統的離群點檢測算法，大致可以分為基于統計的離群檢測[11]，基于距離的離群檢測[12]，基于密度的離群檢測[13，14]，基于近鄰的離群檢測[15]，基于角度的離群檢測[16，17]等.樞紐現象是高維數據中普遍存在的現象，而且隨著數據集維數的不斷增加，樞紐現象會越來越明顯，被作為“維度災難”的新方面和高維空間學習的一般問題進行了研究.

樞紐現象是“維度災難”中與k近鄰查詢相關的概念，而k近鄰查詢是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一[18].加權k最近鄰算法[19]是k近鄰查詢最簡單、最有效改進算法，其主要思想是根據它們的距離來分配同一個權重的鄰居，權重隨著距離變化而變化，距離越近，權重越大，反之，距離越遠，權重越小；LOF算法[20]通過k近鄰查詢計算對象的 k-距離、可達距離和可達密度，用數據對象k最近鄰的平均可達密度與數據對象自身的可達密度之比表示數據對象的離群程度，但計算量大，不適合高維數據；還有LOCI算法[21]和LoOP算法[22]等很多算法都用到了k近鄰查詢.

逆k近鄰查詢是在k近鄰查詢問題的基礎上產生的，獲得將查詢對象作為kNN的數據對象集合，逆k近鄰可以評價查詢對象的影響力，同樣在離群數據挖掘方面也有廣泛的應用.ODIN算法[23]是基于k最近鄰圖的入度(即逆近鄰)來實現異常檢測的算法，如果數據的入度小就可以被看做離群數據，但是需要人為設定區分度，不適用于未知數據集；INFLO算法[24]是一種基于密度的技術，在估計點的離群值時，除了直接鄰居之外還考慮反向鄰居的密度，是對LOF算法的擴展，解決了LOF算法對密度變化不敏感的缺點，但是只適合在低維和中維數據集，在高維數據集中效果較差.在數據聚類方面，逆k近鄰查詢也得到應用，RNN-DBSCAN算法[25]用Nk(i)作為對觀測密度的估計，不僅可以處理較大的密度變化，而且將閾值由兩個降低到一個，減少了人為因素的干擾，但是k值的選擇對RNN-DBSCAN算法有較大的影響；Radovanovic等人[26]提出了適用高維數據的AntiHub和AntiHub2算法.Antihub算法根據每個數據對象i的Nk(i)值來確定離群點，AntiHub2算法則是在Antihub算法的基礎上同時考慮每個數據對象i的值Nk(i)及其k最近鄰Nk(i)值，但是AntiHub算法只有在較大的k值上才能提高正常數據與離群數據的區分度，運算量代價昂貴，雖然AntiHub2算法可以在相對較小的k值獲得較高的區分度，但是k的取值還是相對較大.Guo等[27]人在AntiHub2算法的基礎上引入距離加權提出了WAntiHub算法，雖然提高了算法的準確性，但是并未解決AntiHub2算法所出現的問題，并且隨著k值的逐漸增大，距離加權的效果逐漸降低.

綜上所述，現有的大部分基于逆k近鄰(RkNN)的離群挖掘算法主要使用逆近鄰來檢測離群數據.但是，這些算法需要較大的k值才能獲得較高的正常數據與離群數據的區分度，運算量較大，耗費時間較長，并且未考慮k近鄰等信息.

3 影響空間下的離群數據挖掘樞紐算法

現有的基于逆k近鄰(RkNN)的離群挖掘算法均利用數據對象的Nk(i)值來確定離群值，文獻[11]中算法在較低的k值上對正常數據與離群數據的區分度不高，主要是因為數據對象的Nk(i)值本質是離散的，要想得到較高的準確率，往往需要選擇較大的k值，但是計算量較大，并且從未考慮k近鄰因素.針對上述問題，提出了一種面向樞紐現象的離群數據檢測算法(An Outlier Detection Algorithm for Hubness Phenomenon，HPOD)，算法利用對象的影響空間進行離群數據檢測，同時考慮數據對象的逆近鄰和近鄰等信息，有效的消除只由逆近鄰帶來的局限性，提高了算法的準確率.為了進一步提高算法的性能，本文對HPOD算法進行了改進，提出了HPOD2算法，HPOD2算法在HPOD算法的基礎上引入了啟發式信息，可以減小k的取值，從而減少算法的計算量.

3.1 影響空間

針對現有的大部分基于逆k近鄰(RkNN)的離群挖掘算法單純只使用逆近鄰來檢測離群數據且并未考慮k近鄰等原因，本文提出使用對象的影響空間來檢測異常數據，同時考慮數據對象的逆近鄰和近鄰等信息，相關定義如下：

定義 1.數據對象p的k-距離.對?p∈數據集D，p的k-距離，記作kdist(p)，定義為對象p和對象q之間的距離dist(p,q)，且滿足：

1)至少有k個對象qi∈D，使得

dist(p,qi)≤dist(p,q)；

2)至多有(k-1)個對象qi∈D，使得

dist(p,qi)

定義 2.數據對象p的k最近鄰集合.對p∈數據集D，p的k鄰域點集NNk(p)，定義為數據集D的一個非空子集X，滿足dist(p,X)≤kdist(p)即P的k鄰域點集為

NNk(p)={X?D}dist(p,X)≤kdist(p)}

(1)

由定義1和定義 2可知，雖然數據對象p的k最近鄰集合可能不是唯一的，但數據對象p的kdist(p)是唯一的.而且數據對象p的最近鄰關系是不對稱的.對于給定的數據對象p，p的最近鄰可能并沒有把數據對象p作為自己的最近鄰之一.

定義 3.數據對象p的逆近鄰集合.數據對象p的逆鄰域點集RNNk(p)，定義為

RNNk(p)={q∈D|q∈NNk(p)}

(2)

由定義3可知對于任意數據對象p的k近鄰數據集NNk(p)包含至少k個數據對象，而數據對象p的RNNk(p)取決于數據對象p作為其他點的k近鄰次數可能為空，也有可能含有遠遠大于k個數據對象.而同時考慮數據對象p的RNNk(p)和NNk(p)，形成一個關于數據對象p的局部鄰域空間，用來表示數據對象p的離群程度，定義如下：

定義 4.對象p的影響空間.數據對象p的影響空間ISk(p)，定義為對象p的k最近鄰集合和逆近鄰集合的交集，即

ISk(p)=NNk(p)∩RNNk(p)

(3)

由定義4可知離群數據都會較少或不出現在其他數據對象的近鄰列表中，表示逆近鄰集合包含的數據對象數量較少或者為空，其影響空間中包含的數據對象也會較少或不存在.采用對象的影響空間代替逆近鄰進行離群數據檢測，同時考慮數據對象的逆近鄰和近鄰等信息，可以消除只由逆近鄰帶來的局限性，有效減少誤報率，除此之外，對象的影響空間同時考慮數據對象的逆近鄰和近鄰，對局部密度的變化有較高的敏感性，要優于其他方法.

3.2 HPOD算法

文獻[25]利用數據對象的Nk(i)值來確定離群值，并選擇全體數據對象中離群分數最小的n個數據對象作為離群對象，并未考慮數據對象的k近鄰等因素.因此，根據定義4來定義對象的影響空間，并結合文獻[25]，計算數據對象xi離群分數的標準化公式可重新定義為：

(4)

其中：ε為影響因子且ε∈[0,1]，dist(xi)為對象p的k-距離，sxi為數據對象xi的離群分數，Nk(i)為數據對象xi的逆近鄰數量.

由公式(4)可得當數據對象xi為離群數據時，經常不出現或很少出現在其他數據對象的kNN列表中，其Nk(i)值較低，該數據對象的逆近鄰所包含的數據對象也就較少，且數據對象的dist(xi)較大，sxi的得分也就越大.當數據對象的Nk(i)值較低時，其數據對象的dist(xi)則對數據對象的離群得分有較大的影響，從而保證了算法在較小的k值獲得較高的正常數據與離群數據的區分度；雖然隨著k值的增加數據對象的dist(xi)對數據對象的離群得分的影響逐漸降低，但數據對象的Nk(i)值逐漸變大，對數據對象的離群得分的影響逐漸增加，能保證算法在較高的k值也能獲得較高的區分度.綜上所述，數據對象的影響空間，可以保證算法無論在較高或者較低的k值上都能保持一個理想的正常數據與離群數據的區分度.

影響因子ε的給定可以調節dist(xi)和Nk(i)所占的比重，使算法適應不同的場景應用.當待檢測數據比較適合逆近鄰檢測時，可以將影響因子ε變小；當待檢測數據比較適合用距離檢測時，可以將影響因子ε變大.在一些極端的情況下，例如，當待檢測數據過度分散時，采用逆近鄰檢測，準確率極低，甚至干擾檢測結果，此時可以將ε設為1，只靠dist(xi)來檢測數據；反之，當待檢測數據對距離信息不敏感時，此時可以將ε設為0，只根據待檢測數據的逆近鄰信息來檢測數據.極端情況下，計算數據對象xi離群分數的公式(4)則變為：

(5)

3.3 HPOD2算法

為了能夠在相對較小的k值上獲得較高的正常數據與異常數據之間的區分度，減少計算量與運行時間，本文提出了HPOD算法的改進算法，HPOD2算法.

HPOD2算法在HPOD算法的基礎上引入了啟發式信息，不僅考慮數據對象xi本身的離群分數sxi，同時還考慮其k近鄰對象的離群情況.數據對象xi的k近鄰對象的離群得分之和annxi計算公式定義如下：

annxi=∑xj∈NN(xi)sxj

(6)

其中：annxi是數據對象xi的k近鄰sxj得分之和，數據對象xj則是xi的k近鄰，sxj為數據對象xj的離群得分.

對于每個數據對象xi，HPOD2算法按比列將(1-α)*sxi與數據對象xi的k近鄰的離群分數之和α*annxi相加，其中α為最大區分度比列，能最大限度的區分離群數據與正常數據.數據對象xi的離群程度計算公式為：

ssxi=(1-α)*sxi+α*annxi

(7)

其中：ssxi為數據對象xi的離群總得分，sxi為數據對象xj的離群得分，annxi為數據對象xj的k近鄰sxj得分之和，α是最大區分比例，α∈[0,1].

4 算法描述

HPOD算法的基本過程為：第一步，對數據集中的每個數據對象xi計算其k近鄰，根據數據對象的k近鄰得到每個數據對象xi出現在其他數據對象的kNN列表中的次數Nk(i)和dist(xi)；第二步，根據公式(4)，計算數據對象的離群分數，得到sxi；最后，根據上一步得到的每個數據對象的離群分數，從中選取離群分數最高的n個對象作為離群對象.其算法描述如下：

算法：HPOD

輸入：

數據集D={x1,x2,…,xn},其中，xi∈D,i∈{1,2,…,n}

近鄰數量k∈{1,2,…,n}

影響因子ε∈[0,1]

輸出：離群分數最高的n個數據對象

步驟：

1)For each i∈(1, 2,…, n) in D

2) 計算數據對象xi的k近鄰，得到數據對象xi的Nk(i)值

3) 和dist(xi)

4)end for；

5)For each i∈(1, 2,…, n) in D

6) 根據公式(4)，計算數據對象的離群分數，得到sxi

7)end for；

8)End HPOD

HPOD2算法在HPOD算法的基礎上同時考慮其k近鄰數據，在計算數據對象xi的sxi得分的同時，還考慮其k近鄰數據對象的s得分，通過設置step參數進行遍歷，找到最大區分度比例α，區分度比列α通過最大限度地區分離群程度最大異常對象的異常值得分自動確定，并且由兩個參數控制：離群值與最大識別率之比ρ(其中，ρ∈(0,1])和搜索最大區分度比列α時的步長step(step∈(0,1])，并在最大區分度比例α的基礎上將數據對象xi的sxi得分和其k近鄰對象的離群得分之和annxi相加，得到最后的數據對象的離群分數，從中選取離群分數最高的n個對象作為離群對象.其算法描述如下：

算法：HPOD2

輸入：

數據集D={x1,x2,…,xn},其中，xi∈D,i∈{1,2,…,n}

近鄰數量k∈{1,2,…,n}

影響因子ε∈[0,1]

離群值與最大識別率之比ρ∈(0,1]

搜索最大區分度比列α時的步長step∈(0,1]

輸出：離群分數最高的若干對象

局部函數：discScore(ssxi,ρ)：對于ss∈Rn和ρ∈(0，1]，輸出ss中的[nρ]最小成員中唯一項的數目，并除以「nρ?.

步驟：

1)For each i∈(1, 2,…, n) in D

2) 計算數據對象xi的k近鄰，得到數據對象xi的Nk(i)值和

dist(xi)

3)end for；

4)For each i∈(1, 2,…, n) in D

5) 根據公式(4)，計算數據對象的離群分數，得到sxi

6) 根據公式(6)，計算數據對象xi的k近鄰的離群分數之和

annxi

7)end for；

8)disc :=0；

9)For each α∈(0,step,2·step,…, 1)

10) For each i∈(1, 2,…, n)

11) 根據公式(7)，計算數據對象xi的離群分數，得到ssxi

12) end for；

13) cdisc :=discScore(ssxi,ρ) //計算α對應的區分度

14) If cdisc>disc

15) t:=ssxi；disc:=cdisc；

16) end if；

17)end for；

18)For each i ∈ (1, 2,…, n) in D

19) 根據得到的最大區分度α值和公式(7)計算數據對象的離群

分數

20)end for；

21)End HPOD2

算法的復雜性分析：

HPOD算法中，計算每個數據對象的k近鄰之后，可以同時得到數據對象xi的Nk(i)值和dist(xi)，因此HPOD算法的時間復雜度為O(n2)；HPOD2算法在HPOD算法的基礎上引入了啟發式信息，還考慮其k近鄰數據，除此之外，還需要計算最大區分度，因此HPOD2算法的時間復雜度為O(n2s)，其中s為計算最大區分度α值的時間復雜度.

5 實驗結果

為了驗證提出的基于數據對象的影響空間算法的有效性，選取真實數據集進行性能測試，并與AntiHub2算法和WAntiHub算法的實驗結果進行了比較.AntiHub2算法和WAntiHub算法是兩種常見基于樞紐現象的離群數據檢測算法，其中AntiHub2算法分析了樞紐現象，并且證明了非樞紐點和離群數據存在著聯系；WAntiHub算法是對AntiHub2算法的改進，在AntiHub2算法的基礎上利用k近鄰中的距離信息作為權值，對逆k近鄰中的離群分數進行了加權.本文所有的實驗測試，均在以下環境進行：Inter(R)Core(TM)i5-4200CPU，8GB內存，Windows7操作系統，IntelliJ IDEA開發平臺，采用java語言實現了所提出的算法以及涉及的相關算法.

實驗全部采用真實數據集進行驗證，且真實數據集全部來源于ELKI庫(1)https：// elki-project.github.io/datasets/，分別為Ionosphere、SpamBase和PenDigits.數據集Ionosphere包含351條數據和32個屬性，其中包括126個離群數據；數據集SpamBase包含2588條數據和57個屬性，其中包括50個離群數據；數據集PenDigits包含9878條數據和16個屬性，其中包括30個離群數據.測試數據集的詳細信息如表1所示.

表1 測試數據集信息

Table 1 Details of test data

數據集數量n維度d離群點數量PenDigits98781630Ionosphere35132126SpamBase25885750

5.1 驗證對象影響空間的有效性

為了驗證算法采用對象的影響空間的性能要優于其逆近鄰，本文將HPOD算法、HPOD2算法、Antihub2算法和WAntiHub算法在數據集SpamBase上進行測試，算法都使用相同的參數，搜索最大區分度比列α時的步長step=0.001，離群值與最大識別率之比ρ=0.1，HPOD算法和HPOD2算法中的影響因子ε=0.5，然后將兩者的實驗結果進行比較.

圖1 數據集SpamBase上性能對比

由圖1可知，Antihub2算法和WAntiHub算法的準確率隨著k值的增加而逐漸變高，在k取值900以后才一直維持較高的區分度，主要原因是數據對象的逆近鄰數量是離散的，需要較大的k值才能獲得較高的區分度；而HPOD算法和HPOD2算法在k取值30到50之間就能獲得較高的區分度，遠遠小于Antihub2算法和WAntiHub算法中的k取值，并且隨著k值的增加，一直具有較高的準確率，主要原因是HPOD算法和HPOD2算法引入了數據對象的影響空間，同時考慮數據對象的逆近鄰和近鄰等信息，雖然在k值較小的時候，只靠數據對象的逆近鄰數量無法獲得較高的區分度，但是數據對象的近鄰因素對數據對象的影響較大，使得HPOD算法和HPOD2算法能在較低的k值上有較高的準確率.

由圖2可知，在數據集SpamBase上，WAntiHub算法和Antihub2算法和HPOD2算法都隨著k值的增加耗費時間逐漸增加，并且在相同的k值上，效率差別不大，HPOD算法；但是由圖1可知，HPOD算法和HPOD2算法在較低的k值上就可以得到較高的準確率，而WAntiHub算法和Antihub2算法卻需要較大的k值；從圖4(c)中的數據集SpamBase上，可以看出在各自最優k值上HPOD算法和HPOD2算法耗費的時間要遠遠低于WAntiHub算法和Antihub2算法，主要是由于WAntiHub算法和Antihub2算法的k值較大，計算量變大，從而導致算法耗費時間變長.

圖2 數據集SpamBase上效率對比

在圖1和圖2中還可以看出，HPOD算法比HPOD2算法的準確率低，但算法效率明顯高于其他算法，主要有兩方面的原因：一是HOPD2算法中需要設置步長，step值越小，在搜索最大區分度比例時耗費時間O(s)將越長(可參見第5節HPOD算法的時間復雜度分析)，而在HPOD算法中不需要這一步驟，因此HPOD2算法的執行時間會高于HPOD算法，并受到步長step值的直接影響；二是由于HPOD2算法在HPOD算法的基礎上進行了改進，引入了啟發式信息，考慮數據對象的k近鄰對象的離群情況，提高了算法的準確率，但增加了算法的執行時間.

如果應用場景對效率要求高的情況下，可以采用HPOD算法，在犧牲一定的精度下保持較高的效率；如果應用場景對準確率要求較高，可以采用HPOD2算法.

5.2 算法性能對比

在驗證了影響空間的有效性之后，使用真實數據集Ionosphere和真實數據集PenDigits對算法的性能進行實驗測試，并對所有算法在效率和準確率上進行比較來驗證改進算法的有效性.在這里所有算法使用相同的參數，對比的是HPOD算法、HPOD2算法、Antihub2算法和WAntiHub算法在各自選取最優的k值時的準確率及其效率.

圖3表明，在真實數據集Ionosphere和真實數據集PenDigits上，HPOD算法和HPOD2算法的準確率都要高于AntiHub2算法和WAntiHub算法，主要原因是HPOD算法和HPOD2算法引入對象的影響空間進行離群數據檢測，同時考慮數據對象的逆近鄰和近鄰等信息，可以有效的消除逆近鄰帶來的在較低的k值上區分度不高的問題，提高了算法的準確率；在k取值較小時，WAntiHub算法的準確率要高于AntiHub2算法，主要是因為WAntiHub算法在AntiHub2算法的基礎上引入了加權信息，從而提高了準確率，但是隨著k值的增加，任意兩個數據對象之間的k近鄰中相同的數據對象會越來越多，兩者距離慢慢地趨于一致，使基于距離信息加權的效果變差，并且WAntiHub算法同AntiHub2算法一樣往往需要取較大的k值才能獲得較高的準確率.

圖3 真實數據集上算法準確率對比

由圖4(a)和(b)可知，在相同k取值下AntiHub2算法和HPOD2算法的運行時間基本上相同，WAntiHub算法的運行時間略低于AntiHub2算法和HPOD2算法，但是相差不大，而HPOD算法的運行時間要小于其他算法；但是由圖4(c)可以看出，所有算法為了獲得最高的區分度而選取不同的k值情況，運行時間卻是不同的.在數據集Ionosphere中，所有算法運行時間幾乎沒有差別，主要原因是數據集Ionosphere的數據量較小，在進行k近鄰查詢時耗時極少，差別不大；而在數據集PenDigits和SpamBase中HPOD算法和HPOD2算法所耗費時間要明顯少于AntiHub2算法和WAntiHub算法，主要是原因數據集PenDigits和SpamBase數據量較大，而HPOD算法和HPOD2算法可以在較低的k值上獲得最佳的正常數據與離群數據的區分度，而AntiHub2算法和WAntiHub算法則需要較高的k值，計算量的增加導致了算法運行時間變長，而且HPOD算法和HPOD2算法獲得的最優區分度要高于其他算法的最優區分度.

6 結束語

針對在高維數據中進行離群數據挖掘導致出現的樞紐現象，提出了一種面向樞紐現象的雙向近鄰離群檢測算法.該算法同時考慮影響空間中對象的k近鄰和逆近鄰對對象的影響作用；并且在HPOD算法的基礎引入了啟發式信息，提出了改進算法HPOD2算法，有效的降低了k的取值，從而大大提高了算法的效率；最后，對于本文提出的改進算法采用真實數據集對其進行了檢測，實驗表明本文提出的改進算法要優于傳統的基于樞紐現象的離群數據挖掘算法.同時，面對海量高維數據，算法的并行化將是下一步的研究工作.

圖4 真實數據集上算法效率對比