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

解 峰 蔡江輝 楊海峰 荀亞玲

（太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 太原 030024）

1 引言

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

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

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

2 相關(guān)理論基礎(chǔ)

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

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

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

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

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

3 基于PCOD的異常檢測算法

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

3.1 極大團(tuán)與最大團(tuán)

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

良分割分離技術(shù)是Callahan等提出的一種對圖進(jìn)行成對分解獲取稀疏圖的方法，良分割對（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中任意兩點(diǎn)之間距離都是相近的，且都小于A與B之間的距離。通過這種方式將圖成對分解，即可搜索圖中孤立的異常點(diǎn)。

圖1 WSP示意圖

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

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

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

圖2 極大團(tuán)、最大團(tuán)與異常點(diǎn)

3.2 PCOD算法

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

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

2）取數(shù)據(jù)集中的對象Xi，i=1，計(jì)算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）重復(fù)以上步驟，直到生成所有對象的邊，將數(shù)據(jù)轉(zhuǎn)化為圖。

PCOD算法對分割后的稀疏圖進(jìn)行搜索，檢測沒有與其他對象抱團(tuán)的異常點(diǎn)。本文在實(shí)驗(yàn)部分驗(yàn)證了鄰近距離對異常點(diǎn)檢測的影響。

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

4.1 鄰近距離對算法運(yùn)行時間和精確率的影響

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

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

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

檢測率的定義為檢測出的異常個數(shù)與異常總數(shù)之比。誤檢率也稱為假警告率，其計(jì)算方法為假異常的個數(shù)與被分類為異常的對象個數(shù)之比，實(shí)驗(yàn)結(jié)果如表2所示。

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

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

4.3 PCOD與其他算法的對比

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

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

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

5 結(jié)語

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