一種基于鄰近性和團的異常數(shù)據(jù)檢測算法?

解 峰 蔡江輝 楊海峰 荀亞玲

（太原科技大學計算機科學與技術學院 太原 030024）

1 引言

異常數(shù)據(jù)檢測是數(shù)據(jù)挖掘的一個熱門研究方向，其目標是尋找與多數(shù)對象明顯不同的樣本點。在數(shù)據(jù)的分布圖中，這些樣本點與其他數(shù)據(jù)點距離較遠，所以也被稱為離群點［1］（outlier）。異常數(shù)據(jù)的檢測方法按照類型分為基于模型的方法［2］、基于聚類［3］的方法、基于鄰近［4］的方法?；谀Ｐ偷姆椒ㄐ枰⒁粋€異常點不能完美擬合的數(shù)據(jù)模型，通過考慮對象異常的可能概率，運用概率分布模型［5］，計算樣本分布的均值標準差，如果對象不能很好地同該模型擬合，則認為該對象為異常點?；谀Ｐ偷漠惓z測方法對數(shù)據(jù)作統(tǒng)計學假定，只有當假定滿足實際約束時，才能檢測到異常數(shù)據(jù)。簡單模型（如高斯模型）對參數(shù)進行擬合僅需要線性時間，但當模型復雜（如混合模型［6］）時，需要多次迭代來擬合最佳參數(shù)?；诰垲惖漠惓z測方法，假定正常數(shù)據(jù)屬于相對密集的簇，而異常數(shù)據(jù)屬于稀疏的簇或不屬于任何簇，在這種假定下，通過考察對象與聚類算法產(chǎn)生的簇之間的關系來識別異常數(shù)據(jù)，當識別到不屬于任何簇類的對象，或者屬于偏遠的且樣本量較少的簇時，則大概率為異常點或異常簇?；诰垲惖姆椒ㄊ且环N無監(jiān)督的檢測方法，它不依賴于數(shù)據(jù)的標簽，直接將對象與簇進行比較來檢測異常點，但是對于大型數(shù)據(jù)集，聚類方法開銷較大，不適用于異常檢測?；卩徑缘姆椒?，在對象之間定義鄰近性度量，找到遠離大部分對象的異常點。

研究人員在多數(shù)情況下使用基于鄰近的方法來檢測異常數(shù)據(jù)，如知名的K近鄰［7］，尋找異常得分［8］最高的樣本點作為異常數(shù)據(jù)。通常異常點對K的取值高度敏感，當K較小，鄰近的異常對象得到較低的分數(shù)；當K較大，則多數(shù)對象都標記為異常點?；卩徑缘姆椒▽κ褂玫泥徑远攘恳蕾嚦潭容^高，并且面對分布相對密集的樣本點時，不易檢測異常點。

本文對基于鄰近的方法進行研究，針對不易檢測分布密集樣本的異常點問題，將圖論中團［9］的概念引入到異常檢測中，對密集樣本中存在的團進行分析，提出一種基于鄰近性和團的異常檢測算法——PCOD算法。該算法將數(shù)據(jù)轉化成圖，對圖中的團進行分析，其中不屬于團的樣本點即為異常點。同時，針對樣本量不斷增加，搜索團的難度較大的問題，本文使用良分割技術將圖分割，生成稀疏圖［10］，降低搜索團的時間。

2 相關理論基礎

基于鄰近性的異常檢測使用距離度量來量化對象之間的相似性［11］，并且假設異常對象與它的最近鄰的鄰近性顯著偏離數(shù)據(jù)集中其他對象與它們近鄰之間的鄰近性，代表性的算法有基于距離的異常檢測算法和基于密度［12］的異常檢測算法。基于距離的算法一般使用歐式距離作為數(shù)據(jù)樣本間的度量方式，計算多維空間中兩個樣本間的歐式距離d(x，y)如式（1）所示：

n為樣本維度。當有了距離度量，需要判斷給定半徑的鄰域［13］，如果鄰域內無其他對象，則可能為異常點。因此需要指定一個距離參數(shù)r來定義對象的合理鄰域，對于每個對象o，分別判斷它們鄰域內其他對象的個數(shù)，如果數(shù)據(jù)中大部分對象遠離對象o，則o為異常點，如式（2）所示：

其中r為距離閾值，π是分數(shù)閾值［14］，dist為對象之間的距離，o′為其他對象。基于距離的算法通過計算o與其他對象之間的距離，統(tǒng)計鄰域中其他對象的個數(shù)來分析o是否為異常數(shù)據(jù)。判斷每個樣本點的鄰域需要使用嵌套循環(huán)檢測異常點，嵌套循環(huán)的時間復雜度為O（n2），但在實際運用中常常是線性時間。

基于鄰近的方法通常使用距離或密度作為度量方式，在低維數(shù)據(jù)中有很好的效果，但在高維空間中，不容易得到合適的度量方式，并且基于鄰近的方法在處理高維數(shù)據(jù)時無法解決維度災難和數(shù)據(jù)高度稀疏等問題。針對這些問題，學者探究了使用新的鄰近度量或從高維數(shù)據(jù)中的子空間來檢測異常點，文獻［15］介紹了一種基于結構得分的高維數(shù)據(jù)異常檢測算法。此外，還有基于傳統(tǒng)異常檢測方法擴充而來的HilOut算法，HilOut使用距離的秩作為鄰近性度量，對每個樣本o，得到它的K最近鄰，記作nn1(o)，…，nnk(o)，對象o的權重定義為式（3）：

算法依賴于K值的選擇。尤其是在面對大數(shù)據(jù)時，獲得每個樣本的K近鄰對算法的消耗巨大。

3 基于PCOD的異常檢測算法

PCOD算法是一種結合了鄰近性與團的思想的異常檢測算法，算法將對異常點的搜索轉化為對數(shù)據(jù)圖中抱團對象的搜索，算法首先將數(shù)據(jù)對象轉化為圖中的頂點，然后根據(jù)對象之間的鄰近性判斷頂點是否連接，最后搜索圖來檢測異常對象。

3.1 極大團與最大團

最 大 團 問 題［16］（Maximum Clique Problem，MCP）是圖論中一個經(jīng)典的組合優(yōu)化問題，在國際上已有廣泛的研究。尋找最大團的經(jīng)典算法為Bron-Kerbosch算法，其是一種遞歸回溯算法，用于搜索給定圖的最大團。團（clique）是一個無向圖的完全子圖，完全子圖的每對頂點之間都互相連接，尋找數(shù)據(jù)中的團就是尋找無向圖中的完全子圖。如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖的極大團［17］，結點數(shù)最多的極大團則為最大團。

良分割分離技術是Callahan等提出的一種對圖進行成對分解獲取稀疏圖的方法，良分割對（Well-Separated pair）的定義如下。

定義1以c為中心，r為半徑的球體，可以表示為集合B={p∈Rd:dist2c，p)≤r}。給定一個分割閾值s＞0，如果數(shù)據(jù)集合A和B所在的最小矩形框R(A)和R(B)能夠被半徑為r的d維球體Sa和Sb分別包含，并且兩個球體之間的距離不小于sr，那么稱集合A和B是良分離的，如圖1所示。

由定義1可知，若A與B是良分離的，則A與B中任意兩點之間距離都是相近的，且都小于A與B之間的距離。通過這種方式將圖成對分解，即可搜索圖中孤立的異常點。

圖1 WSP示意圖

定義2給定無向圖G=(V，E)，若?V′?V，使得頂點子集V′導出的子圖G′=(V′，E′)為完全圖，則稱V′為G的團。 若 ﹁?V″?V∧V′?V″使得頂點集V′導出的子圖為完全圖，則稱V′為圖G的極大團，如果V'的頂點最多，則稱V′為圖G的最大團。

定義3如果 ?o∈V，?V′?V，使得o?V′，則稱頂點o為給定圖G的異常點。

圖2為具體案例，表示一個包含10個數(shù)據(jù)對象的無向圖，其邊集E=｛（1，2），（2，4），（2，3），（3，5），（2，5），（6，7）｝，采用上述方法即可得到c1、c2、c3、c4這四個包含多個對象的團，以及o1、o2、o3這三個孤立的對象，其中c3為最大團，c1、c2、c4為極大團，根據(jù)定義7可知，o1、o2、o3為給定數(shù)據(jù)的異常點。

圖2 極大團、最大團與異常點

3.2 PCOD算法

PCOD算法是一種基于鄰近和團的異常檢測算法，該算法使用歐式距離作為鄰近度量，將數(shù)據(jù)對象表示為圖，遞歸搜索稀疏圖中存在的團來檢測異常點。采用良分割分離技術對圖進行稀疏化并生成稀疏圖。生成稀疏圖的步驟如下所示。

1）給定數(shù)據(jù)集D=［X1，X2，……，Xn］。

2）取數(shù)據(jù)集中的對象Xi，i=1，計算X1與其他對象之間的距離d(i，j)，則X1與其他對象的最大距離為maxd(i，j)，最小距離為mind(i，j)。

3）s為分割閾值，σ為對象之間的鄰近距離，σ=s×( maxd(i，j)-mind(i，j))，如果對象之間的距離小于鄰近距離，即d(i，j)≤s×(maxd(i，j)-mind(i，j))，則兩個對象之間存在著邊的連接。

4）重復以上步驟，直到生成所有對象的邊，將數(shù)據(jù)轉化為圖。

PCOD算法對分割后的稀疏圖進行搜索，檢測沒有與其他對象抱團的異常點。本文在實驗部分驗證了鄰近距離對異常點檢測的影響。

Bron-Kerbosch算法是一種經(jīng)典的團搜索算法，其效率較低且會遍歷圖中所有非極大團的樣本點。為了提高本文算法效率，采用一種改進的搜索圖算法。該算法加入了軸的概念，其思想是選擇一個節(jié)點u作為軸，極大團要么包含u，要么包含u的非直接鄰居，因此PCOD算法通過搜索u及u的非直接鄰居來減少節(jié)點的搜索，降低算法的運行時間。PCOD算法首先將稀疏圖轉化為鄰接數(shù)據(jù)表；再根據(jù)鄰接數(shù)據(jù)表遞歸搜索團；最后對團進行分析檢測異常點，如果存在沒有與其他對象抱團的對象，則該對象被識別為異常點。PCOD算法具體步驟如下所示。

基于鄰近性與團的異常檢測算法

輸入：數(shù)據(jù)集D

輸出：異常點集合

初始化數(shù)據(jù)集D

Compute distance asd(i，j) from D

Getσfromd(i，j)

//根據(jù)步驟3）計算鄰近距離σ

Fori，jin D

Ifd(i，j)<σthen

//如果對象之間的距離小于σ，則存在連接性

將j添加到i的鄰接表Neighbor(i)

End For

RecursiveNeighbor(i)

//遞歸搜索圖

Find all cliques inNeighbor(i)

//獲得數(shù)據(jù)中所有的團

Foriin Cliques

If the number ofi=1

//單獨一個對象的團為異常點

O=O?i

End for

輸出異常點集合O

PCOD算法前期需要計算樣本點之間的鄰近距離生成距離矩陣，時間復雜度為O（n log2n），在第二階段尋找數(shù)據(jù)中的團時，雖然使用了改進的搜索團算法，但它基礎形式仍是一個遞歸回溯算法。算法過程中使用鄰接數(shù)據(jù)表保存對象之間的近鄰集合，其空間復雜度為O（mn），m為近鄰列表的廣度，n為近鄰列表的深度，即樣本個數(shù)。

4 實驗結果及分析

在本文的實驗環(huán)境為Windows10，處理器為In?tel Core i5-7200U，8.0GB運行內存，64位操作系統(tǒng)，開發(fā)工具為Spyder，開發(fā)語言為python。實驗采用UCI數(shù)據(jù)集，其基本信息如表1所示。PCOD算法從三個方面評估異常檢測的效果，一是鄰近距離對算法運行時間和精確率的影響；二在UCI數(shù)據(jù)集上檢測結果；三是與其他異常檢測算法的精確率對比。

表1 UCI數(shù)據(jù)集

4.1 鄰近距離對算法運行時間和精確率的影響

本文在500條數(shù)據(jù)、1000條數(shù)據(jù)、1500條數(shù)據(jù)三種數(shù)據(jù)規(guī)模下進行實驗。精確率的計算方法為Precison=TP/(TP+FP)，TP為真異常個數(shù)，F(xiàn)P為假異常個數(shù)，實驗結果見圖3。從圖3可以明顯看出對于測試數(shù)據(jù)集，當鄰近距離σ較小時，運行時間趨勢較為平穩(wěn)。出現(xiàn)這種情況的原因是σ較小時搜索到的團的個數(shù)較少，因此算法運行時間較低。當σ=2.0時，精確率達到最高。當σ＞2.0時精確率趨于平滑，隨著σ繼續(xù)增大，算法運行時間激增，精確率基本保持不變。隨著σ的不斷增大，團的數(shù)目逐漸增加，團搜索消耗的時間也隨之增加。實驗結果表明，當鄰近距離值在相對小的范圍時，算法檢測到相對多的異常點，且消耗的時間較少，驗證了算法在不同數(shù)據(jù)規(guī)模下的伸縮性。

圖3 鄰近距離對算法檢測結果的影響

4.2 PCOD在UCI數(shù)據(jù)集上的檢測結果

檢測率的定義為檢測出的異常個數(shù)與異?？倲?shù)之比。誤檢率也稱為假警告率，其計算方法為假異常的個數(shù)與被分類為異常的對象個數(shù)之比，實驗結果如表2所示。

表2結果可以看出PCOD算法在不同的數(shù)據(jù)集上都有較高的檢測率。其中Ionosphere數(shù)據(jù)集上檢測率達到92%，而誤檢率僅為9%，Ionosphere數(shù)據(jù)集的異常點占比達到35%。Vowel數(shù)據(jù)集的異常數(shù)據(jù)占比則相對較小，檢測到多個異常點，證明算法不受異常點占比的影響。算法在小規(guī)模數(shù)據(jù)集與相對較大數(shù)據(jù)集上都有較高的檢測率，整體結果表明PCOD算法在UCI數(shù)據(jù)集中有良好的適用性。

表2 PCOD在UCI數(shù)據(jù)集上的檢測結果

4.3 PCOD與其他算法的對比

本文使用的對比算法有基于角度的異常檢測算法ABOD、基于集成的FB算法、基于鄰近性的KNN和基于密度的LOF算法，算法對比結果如圖4所示。

總體來看，基于鄰近和團的異常檢測算法相比其他模型表現(xiàn)更好。PCOD算法與KNN算法都是基于鄰近的異常檢測方法，同樣考慮距離來分析數(shù)據(jù)的異常性，但是PCOD算法分析了對象之間存在團的可能性，因為異常點不會被吸納進正常樣本的團內，所以在多數(shù)數(shù)據(jù)集上PCOD算法表現(xiàn)更優(yōu)。Vowel數(shù)據(jù)集中異常點數(shù)占比相對較少且存在一部分與正常點較為鄰近的異常點，導致LOF和KNN等算法無法輕易識別這些對象。由于Lympho數(shù)據(jù)集僅有六個異常點，除了ABOD算法，其余檢測算法都檢測到四個異常點，并且3個為真異常點，精確率為75%。在Shuttle數(shù)據(jù)集上，基于距離的算法精確率相對較低，因為數(shù)據(jù)集規(guī)模較大且異常點數(shù)多，不容易檢測異常點，這也是基于距離的算法局限性。相比KNN、LOF等基于距離的算法，PCOD仍有比較好的檢測效果。從圖4分析可知，PCOD算法結果穩(wěn)定，在多個數(shù)據(jù)集都有較好的精確率。實驗結果證明簡單模型效果不一定比復雜模型差，需要綜合考慮算法在數(shù)據(jù)集上的穩(wěn)定性。

圖4 PCOD與其他算法在UCI上的精確率對比圖

5 結語

本文對基于距離的異常檢測算法進行研究，引入圖論中團的概念，將數(shù)據(jù)對象轉化為圖，分析圖中的團來檢測異常點。通過對象之間的最大最小距離以及良分割技術對圖進行稀疏化，提升了算法的檢測效果。同時在UCI數(shù)據(jù)集上進行實驗，對比了多種類型的異常檢測算法，實驗結果表明，在多數(shù)數(shù)據(jù)集上，本文提出的PCOD算法相比其他算法在精確率上表現(xiàn)更優(yōu)。未來將進一步擴展算法在大型高維數(shù)據(jù)上的有效性與可伸縮性。