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

解 峰 蔡江輝 楊海峰 荀亞玲

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

1 引言

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

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

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

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

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

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

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

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

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

3 基于PCOD的異常檢測(cè)算法

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

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

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

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

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

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

圖1 WSP示意圖

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

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

圖2為具體案例，表示一個(gè)包含10個(gè)數(shù)據(jù)對(duì)象的無(wú)向圖，其邊集E=｛（1，2），（2，4），（2，3），（3，5），（2，5），（6，7）｝，采用上述方法即可得到c1、c2、c3、c4這四個(gè)包含多個(gè)對(duì)象的團(tuán)，以及o1、o2、o3這三個(gè)孤立的對(duì)象，其中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)的異常檢測(cè)算法，該算法使用歐式距離作為鄰近度量，將數(shù)據(jù)對(duì)象表示為圖，遞歸搜索稀疏圖中存在的團(tuán)來(lái)檢測(cè)異常點(diǎn)。采用良分割分離技術(shù)對(duì)圖進(jìn)行稀疏化并生成稀疏圖。生成稀疏圖的步驟如下所示。

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

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

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

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

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

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

基于鄰近性與團(tuán)的異常檢測(cè)算法

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

輸出：異常點(diǎn)集合

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

Compute distance asd(i，j) from D

Getσfromd(i，j)

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

Fori，jin D

Ifd(i，j)<σthen

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

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

End For

RecursiveNeighbor(i)

//遞歸搜索圖

Find all cliques inNeighbor(i)

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

Foriin Cliques

If the number ofi=1

//單獨(dú)一個(gè)對(duì)象的團(tuán)為異常點(diǎn)

O=O?i

End for

輸出異常點(diǎn)集合O

PCOD算法前期需要計(jì)算樣本點(diǎn)之間的鄰近距離生成距離矩陣，時(shí)間復(fù)雜度為O（n log2n），在第二階段尋找數(shù)據(jù)中的團(tuán)時(shí)，雖然使用了改進(jìn)的搜索團(tuán)算法，但它基礎(chǔ)形式仍是一個(gè)遞歸回溯算法。算法過(guò)程中使用鄰接數(shù)據(jù)表保存對(duì)象之間的近鄰集合，其空間復(fù)雜度為O（mn），m為近鄰列表的廣度，n為近鄰列表的深度，即樣本個(gè)數(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)，開(kāi)發(fā)工具為Spyder，開(kāi)發(fā)語(yǔ)言為python。實(shí)驗(yàn)采用UCI數(shù)據(jù)集，其基本信息如表1所示。PCOD算法從三個(gè)方面評(píng)估異常檢測(cè)的效果，一是鄰近距離對(duì)算法運(yùn)行時(shí)間和精確率的影響；二在UCI數(shù)據(jù)集上檢測(cè)結(jié)果；三是與其他異常檢測(cè)算法的精確率對(duì)比。

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

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

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

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

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

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

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

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

4.3 PCOD與其他算法的對(duì)比

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

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

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

5 結(jié)語(yǔ)

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