兩階段的近鄰密度投票模擬離群點檢測算法

鄭忠龍, 曾 心, 劉華文

(1.浙江師范大學 數學與計算機科學學院,浙江 金華 321004;2.紹興文理學院 計算機系,浙江 紹興 312000)

離群點檢測是指從給定數據中找出或發(fā)現那些與其他數據存在明顯差異的數據的技術[1]。由于能夠帶來諸多潛在價值,離群點檢測在現實各領域有著廣泛應用,如信用卡欺詐檢測[2]、網絡安全入侵檢測[3]、安全系統故障檢測[4]以及對敵人活動的軍事監(jiān)視[5]等。

近年來,學者們提出了許多離群點檢測算法,其中以基于近鄰的檢測方法應用較廣。該方法主要依據數據的近鄰信息,判斷其是否屬于離群點。由于具有較強的可解釋性和直觀性,基于近鄰的離群點檢測是目前應用最為廣泛的離群點檢測方法之一。根據近鄰信息的表示方式不同,基于近鄰的離群點檢測可細分為基于距離的方法和基于密度的方法。基于近鄰距離的方法更關注全局離群點,而基于近鄰密度的方法既能關注到全局離群點,也能有效發(fā)現局部離群點[6]。

為更好地表達現實生活中個體之間的復雜關系,并發(fā)現其中的結構團體,通常將社會關系描述成復雜網絡或圖的形式,其中每個節(jié)點代表一個實體,而節(jié)點之間的邊則表示為實體之間的社會連接關系。社區(qū)發(fā)現是指社會網絡從中發(fā)現那些緊密關系的節(jié)點的集合[7]。社區(qū)發(fā)現在現實生活中有著廣泛應用,如在社交網絡中挖掘具有共同興趣或相似社會背景的群體進行內容推送[8];建立傳染病網絡動態(tài)模型,預測疫情發(fā)展趨勢。

本文旨在利用社區(qū)發(fā)現中的消息傳遞機制,度量數據的密度信息,進而發(fā)掘數據中的離群點。傳統的社區(qū)發(fā)現算法通過信息傳遞在復雜網絡中交互信息,根據信息量優(yōu)先識別最具影響力的節(jié)點。這與離群點檢測原理一致,事實上,離群數據通常與大部分正常數據存在顯著差異。因此,位于網絡邊緣、且對周邊節(jié)點的影響力越小的節(jié)點,被認為是離群點的可能性越大。基于這種思想,本文提出了一種兩階段的近鄰密度投票離群點檢測算法。

本文主要創(chuàng)新點如下:①利用社區(qū)發(fā)現中節(jié)點之間的消息傳遞機制產生的影響力,提出了一種新的基于近鄰關系的投票離群點檢測算法;②采用隨機游走技術,計算節(jié)點及其近鄰的密度,以反映節(jié)點的重要程度;③節(jié)點之間的信息交互只在近鄰內部發(fā)生,從而降低了計算量,使得投票決策更具有可解釋性,相比于全局范圍內的投票決策節(jié)省了運算時間和空間。

1 相關工作

基于密度的離群點檢測算法核心思想是根據數據對象給出的某種合理閾值,形成每個數據點的鄰域范圍,若數據點遠離各鄰域,則將該數據點視為離群點。近鄰密度方法對數據整體分布沒有要求,在局部離群點檢測上表現優(yōu)異,從而得到飛速發(fā)展,其中Chen等[9]提出的K近鄰算法理論成熟且邏輯簡單,是目前使用最為廣泛的檢測算法之一。但是基于近鄰密度的方法對參數選取較為敏感,此類方法的離群點檢測精確度容易受到參數的影響而產生較大波動。

影響力最大化(influence maximization,IM)[10]作為消息傳遞機制的主要研究內容之一,廣泛應用于病毒營銷、謠言控制、社交計算等實際應用場景中。投票作為一種有效識別節(jié)點影響力的算法,能夠快速識別核心節(jié)點以進行信息傳播。VoteRank算法[11]首次使用二元組表示數據節(jié)點的投票能力與投票得分,按照一定的策略記錄投票得分,發(fā)現節(jié)點影響力與投票得分呈正相關。WVoteRank算法[12]考慮到權重對節(jié)點投票能力的影響,構建加權的一階近鄰矩陣來衡量不同相似度對節(jié)點投票能力的影響程度。在此基礎上,VoteRank++算法[13]同時引入一階、二階近鄰迭代用于表示節(jié)點的投票能力。由于投票進行消息傳遞具有魯棒性強、容錯率高、可解釋性強等優(yōu)勢,廣泛應用于社區(qū)發(fā)現和集群檢測中。然而,目前并沒有直接將投票算法應用于離群點檢測的相關研究。

本文受到節(jié)點影響力算法的啟發(fā),將投票模擬算法與傳統離群點檢測方法相結合,提出一種新穎的離群點檢測算法。離群點通常位于網絡邊緣,且對周邊節(jié)點的影響力較小,故本文選取影響力最小的數據為離群點。實驗發(fā)現,本文將投票機制嵌入到離群點檢測領域是一種新穎而有效的檢測算法。

2 近鄰投票的離群點檢測

基于近鄰投票的離群點檢測算法包括密度估計和投票模擬2個步驟:密度估計通過隨機游走進行密度迭代,得到估計密度和節(jié)點重要性;投票模擬通過重要節(jié)點傳遞信息,得到信息平衡時節(jié)點的信息量,將信息量最少的點視為異常點。

2.1 密度估計

(1)

根據Q(xi),設每個數據對象與其K近鄰間存在一條無向邊,由此構成了以近鄰關系為基礎的無權圖G。由圖G得到鄰接矩陣A:

(2)

(3)

P=M-1A。

(4)

基于貢獻均等和無后效性假設,隨機游走可達平穩(wěn)狀態(tài)。具體來說,貢獻均等指節(jié)點i的K個近鄰對i的貢獻均等,無后效性指節(jié)點i在隨機游走中具有無后效性,即i在t+1時刻狀態(tài)只與t時刻狀態(tài)有關。任意節(jié)點i做隨機游走,如圖1所示,箭頭方向表示節(jié)點間的有向關系。近鄰節(jié)點為當前節(jié)點可直達的節(jié)點,如圖1中節(jié)點2的近鄰節(jié)點為節(jié)點1和節(jié)點3,節(jié)點4的近鄰節(jié)點為節(jié)點2和節(jié)點3。參數α表示由任意節(jié)點i根據箭頭所指的有向關系游走到其近鄰j的轉移概率,認為每個節(jié)點i都有均等的概率轉移到其近鄰節(jié)點,取值在[0,1]中;節(jié)點i直接回到自身會形成一個自環(huán),如圖1中0節(jié)點,其概率為1-α,又稱回退概率。

圖1 隨機游走示意圖

將式(3)寫作向量形式得

Dt+1=αPDt+(1-α)D0。

(5)

由P的定義可知,|P|≠0,|αP|≠0,P為標準化的矩陣,則I-αP非負定。由于P每一行中非0元的個數等于K,當K>1且α∈[0,1]時,αP至少有一個非主對角元不為0、主對角元不等于1,則|I-αP|≠0,I-αP可逆。

Dt+1=αPDt+(1-α)D0;

Dt=αPDt-1+(1-α)D0;

?

D2=αPD1+(1-α)D0;

D1=αPD0+(1-α)D0。

通過迭代可得到Dt+1關于Dt,Dt-1,…,D0的表達式:

Dt+1=αPDt+(1-α)D0

=αP(αPDt-1+(1-α)D0)+(1-α)D0

=α2P2Dt-1+αP(1-α)D0+(1-α)D0

?

=αt+1Pt+1D0+(1+αP+α2P2+…+αtPt)(1-α)D0。 級數展開式:

(6)

利用式(6)可以得到估計密度值Den,則近鄰密度估計算法的簡要描述如下。

算法1近鄰密度估計。

輸入:數據集X,近鄰參數K,轉移概率α;

輸出:每個數據點的估計密度值Den。

Step 1 計算數據對象間的歐氏距離,標準化后得到距離矩陣Dist*;

Step 2 獲取數據的相似性SM=I-Dist*;

Step 3 根據相似性矩陣SM,計算每個數據對象的初始密度D0,及其K近鄰集Q(xi);

Step 4 利用K近鄰Q(xi),根據式(2),構造鄰接矩陣A,并獲取概率轉移矩陣P;

Step 5 根據式(6),估計數據的密度值Den。

算法1的時間主要花費在計算數據對象間的距離矩陣Dist*和計算估計密度Den,其最壞情況下的時間復雜度為O(NK+logN),其中N為數據集中數據對象的數量;K為每個數據對象的近鄰個數。節(jié)點的估計密度和近鄰關系是進行投票模擬的前提。

2.2 投票模擬

由于傳統的異常檢測算法對離群點的判別過于苛刻,易將小簇間節(jié)點視作異常,導致誤判。如圖2所示,圖2(a)中數據對象u處于兩簇間,且簇間距較小,易聚合成更大的簇,圖2(b)中數據對象u位于單個簇外,遠離簇中心。事實上是只有圖2(b)中u點為離群點,而傳統的離群點檢測算法會把這2種情況下的u均視為異常。投票算法通過N輪節(jié)點信息傳遞,寬松對待“可能異常”數據對象,將圖2(a)中u檢測為正常節(jié)點,是一種容錯率高的算法。

圖2 2種不同離群點情況

高密度節(jié)點周圍往往環(huán)繞更多節(jié)點,成為中心節(jié)點的可能性大,而中心節(jié)點對近鄰影響更大,故給予估計密度最大的節(jié)點優(yōu)先投票權,每一輪投票均以當前密度最大的節(jié)點為候選投票節(jié)點,輻射更多的對象。每個數據點根據相似性和密度自發(fā)投票,直到每個數據點都完成投票,統計每一輪迭代的投票結果得到投票排名。在上述背景下,模擬投票算法根據以下3種原則進行迭代:①當u為未投票節(jié)點中估計密度最大的點,且u的K近鄰集Q(u)中不存在比u估計密度更大的節(jié)點,u投票給自己;②當u的K近鄰Q(u)中存在比u估計密度更大的點,記與u相似性最大的點為v;③若v未投票,則u投票給v,若v投票給w,則u也投票給w。

圖3為上述3種模擬投票原則。箭頭方向表示投票方向,箭尾為投票者,箭頭記錄被投票者;點的大小為該點密度大小,正方形點是比u密度更大的候選節(jié)點;圓圈范圍為u的K近鄰集Q(u)。

圖3 模擬投票原則圖解

如圖3(a)所示,當u是所有未投票的節(jié)點中密度最大的點時,u的影響力最大,能夠傳遞更多的信息給近鄰節(jié)點,則u投票給自己。如圖3(b)所示,v是u的鄰域內比u密度更大且最近的節(jié)點,若v還未投票給其他節(jié)點,則u投票給v。如圖3(c)所示,v的密度在u的K近鄰集Q(u)中最大,且其影響力大于u,若v投票給了其近鄰點w,則u投票給w。算法2為投票模擬(voting simulation outlier detection, VSOD)算法。

算法2投票模擬算法。

輸入:各數據點的估計密度值Den,近鄰點個數K,異常個數nns;

輸出:離群點的索引。

Step 1 利用算法1計算密度值Den,并對其降序排列,得到投票候選節(jié)點索引voteWho;

Step 2 根據相似性SM計算每個候選點的K近鄰集Q(xi);

Step 3 以voteWho索引為序,利用3種不同模擬投票原則在候選點的近鄰集Q(xi)中投票,記錄投票得分votescore;

Step 4 完成投票的節(jié)點跳出voteWho,直到voteWho為空;

Step 5 取votescore降序排列對應的節(jié)點索引nodeOrder;

Step 6 取nodeOrder后nns個索引。

通過算法1密度估計可以得到數據點之間的相似性與密度信息,為算法2投票消息傳遞奠定了基礎。算法2中節(jié)點排序nodeOrder反映了節(jié)點重要性,當每個數據點都迭代投票后,得到nodeOrder越靠前的數據點,成為中心節(jié)點的可能性越大,而離群點往往遠離中心,故選取nodeOrder靠后的節(jié)點為離群點。

3 實驗

本節(jié)對所提出的投票離群點檢測算法進行了實驗分析,在11個不同類型和大小的公共數據集上與其他9種離群點檢測算法進行比較。這些數據集從實際應用中收集得到,廣泛用于評價異常檢測方法的性能,實驗數據來自于UCI Machine Learning Repository網站。

3.1 數據集

表1為各數據集的基本介紹。這些數據集最初應用在分類任務中,而離群點檢測是無監(jiān)督的,在實驗中往往將更少類標簽對象視為異常,其余對象視為正常[15]。本文在實驗中也遵循該原則,將較少一類作為異常類。例如WPBC數據集,有198條維數為33的數據記錄,其中有47條標簽為R的異常數據記錄,WPBC數據集中異常數據量占總數據記錄的23.74%。

表1 實驗數據簡要描述

為驗證本文算法的有效性,選取9種不同的離群點檢測方法進行比較,實驗在AMD A9-9425 RADEON R5處理器(3.10 GHz)、4 GB RAM的計算機上進行。

3.2 評價指標

不同的檢測算法參數不同,算法參數的選取可能會對最終結果產生影響,因此,合適的參數對算法至關重要。為保證嚴謹性,實驗中的每種異常檢測算法的參數都被設置為原文獻中建議的值或工具箱推薦的值。為便于比較各方法的檢測效果,實驗采用常用的3個指標:Precision、max_F1和AUC。上述3個指標值均在[0,1]中,值越大算法檢測性能越好。

3.3 實驗結果及分析

表2為異常檢測算法的Precision比較?？梢钥闯?本文投票模擬算法(VSOD)的平均精確度為79%,在大部分數據集上表現較好。在DLBCL數據集上,其他檢測方法的精確度最高為62%,而所提的VSOD算法精確度為81%。此外,VSOD算法在少數數據上表現不足,但與其他傳統檢測算法差異不大,如在Speech數據集上,VSOD算法的精確度為90%,仍高于傳統檢測方法的均值89%。而Parkinson數據集更適合采用線性和降維方法檢測離群點。

表2 VSOD算法在不同數據集上與其他算法的Precision對比

表3為9種檢測方法與VSOD算法在11個特點、規(guī)模不同的數據集上的max_F1得分?？梢钥闯?max_F1得分與表2中Precision具有類似的結論。當使用Speech數據集進行檢測時,多數算法的Precision較高,但max_F1非常低,這可能是算法出現了欠擬合現象。而與其他算法相比,VSOD算法包容性強,通過與最近鄰的信息交互,其Precision和max_F1得分均較高。Precision與max_F1均接近1,驗證了本文算法的有效性。在這11個數據集上,VSOD算法的max_F1得分表現均較好,在ALLAML、DLBCL、HeartDisease和Lung數據集上,指標值均在80%以上。

表3 VSOD算法在不同數據集上與其他算法的max_F1對比

表4給出了不同算法的AUC。在Speech數據集上,VSOD算法與ABOD算法表現相當,又明顯優(yōu)于其他算法。這可能是由于Speech數據集的分布不可區(qū)分,導致密度相近,容易聚集成為更大的簇類,需要嚴格的檢測手段加以區(qū)分。在其他數據集上,VSOD算法的性能明顯優(yōu)于其他比較檢測算法。綜上,本文提出的投票檢測算法是有效的。

表4 VSOD算法在不同數據集上與其他算法的AUC對比

4 結論

本文提出了一種有效的異常檢測方法,該方法將密度估計方法與投票算法結合,在每一輪投票中寬容算法與嚴格算法結合,連貫進行,相互平衡。通過在11個真實數據集上進行對比實驗得到如下結論。

(1)本文結合近鄰密度與模擬投票的離群點檢測算法可以在一定程度上提高檢測的精確度。在11個真實數據集上的實驗結果表明,基于近鄰的投票模擬檢測算法平均精確度為79%。

(2)通過鄰域內投票迭代網絡信息,提高了單純采用近鄰方法進行離群點檢測的算法有效性,如LOF算法和KNN算法。本文算法是一種動態(tài)信息傳遞過程,減少了對數據點初密度的依賴性,通過投票不斷修正中心節(jié)點和離群點。

本文提出的離群點檢測算法在小規(guī)模數據集上檢測效果較好,但需要根據數據集在一定區(qū)間內調整K的取值才能使其達到較優(yōu)效果,故下階段將主要研究新穎的消息傳遞方式,從而降低算法對K值的敏感度。