一種基于鄰近性和團的異常數據檢測算法?

解 峰 蔡江輝 楊海峰 荀亞玲

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

1 引言

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

研究人員在多數情況下使用基于鄰近的方法來檢測異常數據，如知名的K近鄰［7］，尋找異常得分［8］最高的樣本點作為異常數據。通常異常點對K的取值高度敏感，當K較小，鄰近的異常對象得到較低的分數；當K較大，則多數對象都標記為異常點。基于鄰近性的方法對使用的鄰近性度量依賴程度較高，并且面對分布相對密集的樣本點時，不易檢測異常點。

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

2 相關理論基礎

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

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

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

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

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

3 基于PCOD的異常檢測算法

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

3.1 極大團與最大團

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

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

定義1以c為中心，r為半徑的球體，可以表示為集合B={p∈Rd:dist2c，p)≤r}。給定一個分割閾值s＞0，如果數據集合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個數據對象的無向圖，其邊集E=｛（1，2），（2，4），（2，3），（3，5），（2，5），（6，7）｝，采用上述方法即可得到c1、c2、c3、c4這四個包含多個對象的團，以及o1、o2、o3這三個孤立的對象，其中c3為最大團，c1、c2、c4為極大團，根據定義7可知，o1、o2、o3為給定數據的異常點。

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

3.2 PCOD算法

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

1）給定數據集D=［X1，X2，……，Xn］。

2）取數據集中的對象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）重復以上步驟，直到生成所有對象的邊，將數據轉化為圖。

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

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

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

輸入：數據集D

輸出：異常點集合

初始化數據集D

Compute distance asd(i，j) from D

Getσfromd(i，j)

//根據步驟3）計算鄰近距離σ

Fori，jin D

Ifd(i，j)<σthen

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

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

End For

RecursiveNeighbor(i)

//遞歸搜索圖

Find all cliques inNeighbor(i)

//獲得數據中所有的團

Foriin Cliques

If the number ofi=1

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

O=O?i

End for

輸出異常點集合O

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

4 實驗結果及分析

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

表1 UCI數據集

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

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

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

4.2 PCOD在UCI數據集上的檢測結果

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

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

表2 PCOD在UCI數據集上的檢測結果

4.3 PCOD與其他算法的對比

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

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

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

5 結語

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