一種相似度剪枝的離群點檢測算法

丁天一,張 旻,方勝良

(電子工程學院,合肥 230037) E-mail:tianyi_ding@126.com

1 引 言

離群點檢測是數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的一個重要研究領域,其目的是有效識別出數(shù)據(jù)集中的異常數(shù)據(jù),以及挖掘出數(shù)據(jù)集中有意義的潛在信息[1].離群點檢測有著非常廣闊的應用前景,特別是在欺詐檢測、醫(yī)療診斷、市場分析、氣象分析、網(wǎng)絡入侵檢測等領域,離群信息往往比常規(guī)模式更具價值[2-4].因此,離群點檢測已經(jīng)引起了越來越多國內(nèi)外學者的關注,所提出的算法也層出不窮.

現(xiàn)有的離群點檢測方法大致上可分為以下幾類:基于統(tǒng)計學的離群點檢測方法,基于距離的離群點檢測方法,基于聚類的離群點檢測方法和基于密度的離群點檢測方法等[1].基于統(tǒng)計學的離群點檢測方法是通過擬合給定數(shù)據(jù)集的生成模型,識別該模型低概率區(qū)域的對象來檢測離群點,依賴于給定數(shù)據(jù)的全局分布,當給定數(shù)據(jù)分布不均勻時,很難確定一個合適的模型;基于距離的離群點檢測方法可以處理多維數(shù)據(jù),也不需要用戶事先知道數(shù)據(jù)分布模型,但是當數(shù)據(jù)集包含不同密度的區(qū)域時,該方法不能很好地識別離群點;基于聚類的離群點檢測算法通過考察對象與簇之間的關系檢測離群點,將不屬于任何簇或者屬于較小的簇的對象作為離群點,離群點是作為聚類算法的副產(chǎn)物而被發(fā)現(xiàn)的,高度依賴于聚類算法的有效性;基于密度的局部離群點檢測方法不將離群點看作一種二元性質(zhì),而是衡量一個對象的離群程度,能夠在數(shù)據(jù)分布不均勻的情況下準確地發(fā)現(xiàn)離群點.Breunig等人提出了局部離群因子的概念,這是一種基于密度的局部離群點檢測方法,通過賦予每一個數(shù)據(jù)對象一個表征它離群程度的量化指標來進行離群點檢測[5].后續(xù)出現(xiàn)了很多新的改進方法,以期取得更好的離群點檢測結果.文獻[6]針對不確定數(shù)據(jù)集進行離群點檢測,設計了一種基于密度的不確定數(shù)據(jù)局部離群因子檢測算法;文獻[7]提出了一種基于偏離的局部離群點檢測算法,通過對數(shù)據(jù)集進行數(shù)據(jù)塊的劃分,計算每個數(shù)據(jù)塊中數(shù)據(jù)對象的離散程度,發(fā)現(xiàn)可能存在的局部離群點;文獻[8]提出的NLOF算法利用鄰域查詢優(yōu)化方法降低鄰域查詢的復雜度,并通過DBSCAN對數(shù)據(jù)集進行預處理,提高離群點檢測精度;文獻[9]提出了一種基于方形對稱鄰域的局部離群點檢測方法,通過擴張方形鄰域建立候選異常點集合,并引入記憶思想和新的離群度度量方法.上述的離群點檢測算法都在各自的應用背景下取得了一定檢測效果.然而,隨著數(shù)據(jù)集的涌現(xiàn),不規(guī)則形狀數(shù)據(jù)集和復雜分布的多維數(shù)據(jù)集給離群點檢測帶來了更大的難題,以上算法對于此類問題的檢測精度較低,需要一種更加有效的離群點檢測方法.

本文首先介紹了LOF算法的相關概念,然后分析利用構造相似度矩陣的方法進行離群點挖掘的合理有效性,并將基于相似度矩陣的非離群點剪枝與局部離群點檢測算法相結合,提出了一種新的離群點檢測算法.最后,采用人工數(shù)據(jù)集和UCI數(shù)據(jù)集,實驗驗證了本文算法的有效性.

2 局部離群點檢測算法

LOF算法為每一個數(shù)據(jù)對象賦予一個表征該數(shù)據(jù)對象離群程度的局部離群因子,用于衡量每一個數(shù)據(jù)點的離群程度.具有較大局部離群因子的數(shù)據(jù)點其密度小于它周圍數(shù)據(jù)點的密度,因此這樣的數(shù)據(jù)對象被判別為離群點.相反,具有較小局部離群因子或者局部離群因子接近于1的數(shù)據(jù)點,在此算法下被判別為正常點[10,11].LOF算法的一些基本概念如下[5,8].

定義1.(對象p的第k距離,k-distance(p)) 對于任意的自然數(shù)k,定義p的第k距離為p與某個對象o之間的距離,記為k-distance(p),這里的對象o屬于數(shù)據(jù)集D并且滿足以下條件:

1)至少存在k個對象o′∈D{p}滿足d(p,o′)≤d(p,o);

2)至多存在k-1個對象o′∈D{p}滿足d(p,o′)

其中,d(p,o)表示對象p和對象o之間的距離.換言之,k-distance(p)是對象p與其第k個最近鄰之間的距離.

定義2.(對象p的第k距離鄰域,Nk-distance(p)) 已知數(shù)據(jù)對象p的k-distance(p),對象p的第k距離鄰域是所有與p的距離不超過k-distance(p)的數(shù)據(jù)對象的集合,即:

Nk-distance(p)={q|d(p,q)≤k-distance(p)}

(1)

式(1)中,Nk-distance(p)在本文中為便于描述簡記為Nk(p).

定義3.(對象p相對于對象o的可達距離,reach-dist(p,o)) 對于給定的自然數(shù)k,對象p相對于對象o的可達距離為:

reach-dist(p,o)=max{k-distance(o),d(p,o)}

(2)

定義4.(對象p的局部可達密度,lrdk(p)) 對象p的局部可達密度是對象p與它的第k距離鄰域Nk(p)的平均可達距離的倒數(shù),計算公式為:

(3)

定義5.(對象p的局部離群因子,LOFk(p)) 對象p的局部離群因子表征對象p為離群點的程度,局部離群因子越大,對象p為離群點的可能性越大;反之,則越小.計算公式為:

(4)

3 一種相似度剪枝的離群點檢測算法

本文提出的算法主要分為兩個階段,首先,通過構造相似度矩陣的方法對數(shù)據(jù)集進行預處理,找到與其他數(shù)據(jù)相似度較小的對象,以此作為初步的離群點候選集,完成對非離群點的剪枝;然后,針對得到的離群點候選集,采用LOF算法計算離群點候選集中每個數(shù)據(jù)對象的局部離群因子,將所有對象的局部離群因子大小進行排序,進而獲得最終的離群點檢測結果.

3.1 相似度矩陣構造

合理的相似度矩陣構造方法可以有效地得到復雜分布數(shù)據(jù)之間的相似度,反映數(shù)據(jù)集原有的基本特征.離群數(shù)據(jù)往往是與其他數(shù)據(jù)相似度較小的點,尋求一種合適的相似度矩陣的構造方法,能夠有效地找到數(shù)據(jù)集中與其他數(shù)據(jù)相似度較小的一部分對象,完成對非離群點的剪枝,得到離群點候選集.

為了能夠有效地反映出不規(guī)則形狀數(shù)據(jù)集和復雜分布的多維數(shù)據(jù)集的特征,需要確定一種有效的相似度計算方法,以提高離群點檢測的精確度.本文采用了如下的相似度函數(shù):

(5)

其中,‖xi-xj‖表示點xi與xj之間的歐氏距離,σi=d(xi,xk),表示樣本點xi到其第k個最近樣本點的歐氏距離.文獻[12]指出,k的選擇是與數(shù)據(jù)規(guī)模無關的,通過對于合成數(shù)據(jù)和圖像數(shù)據(jù)的實驗確定了k的最佳取值為k=7,此時即使對于高維數(shù)據(jù)也能得到很好的結果,這是一個經(jīng)驗值.這樣,對于數(shù)據(jù)集中的每一個樣本點,都計算了一個局部尺度參數(shù),可以根據(jù)樣本點xi與xj相鄰數(shù)據(jù)的統(tǒng)計特性自動調(diào)整點到點之間的距離,于是點xi與xj的距離從xi的角度可以看作是d(xi,xj)/σi,而從xj的角度可以看做是d(xi,xj)/σj[12].

式(5)的相似度函數(shù)基于高斯核函數(shù)提出,可以將樣本間的相似度計算從基于歐氏距離的原始特征空間映射到高維特征核空間,通過非線性映射將數(shù)據(jù)從線性不可分變成線性可分,能夠放大有用的特征以便更好地區(qū)分數(shù)據(jù).

同時,該方法在以高斯核函數(shù)作為樣本之間相似性度量方式的基礎上,將每個樣本點的鄰域信息引入到高斯核函數(shù)的相似度計算中,以樣本點與其近鄰的距離作為該點的局部尺度參數(shù)代替全局單一尺度參數(shù),通過兩個樣本點各自的局部分布情況來改進它們之間的相似度,使得在同一密集區(qū)的樣本點相似度更高,稀疏區(qū)的樣本點則相似度較小[12].

圖1 多尺度數(shù)據(jù)集Fig.1 Multiscale data set

圖1是一個多尺度數(shù)據(jù)集,由弧形的密集簇和一組稀疏簇組成,其中樣本點A和C位于較為緊密的弧形數(shù)據(jù)簇中,而樣本點B位于稀疏簇中.假設AB和AC的距離相等,如果僅用歐氏距離表示兩者之間的相似度,則wAB=wAC,即AB與AC之間相似度相等,而客觀情況是樣本點A和C位于同一流形上的密集簇,樣本間的相似度應該大于位于不同密集程度的樣本點A和B的相似度,顯然在這種情況下僅憑歐氏距離不能正確地衡量樣本間的相似度.如果采用式(5)的方法,通過引入鄰域信息,有σC>σB,則σAσC>σAσB,從而得到wAC>wAB,更真實準確地反映出了復雜分布數(shù)據(jù)的內(nèi)在結構特征.

由此,通過式(5)計算得到了樣本間的相似度矩陣W,其矩陣形式表示如式(6)所示.

(6)

3.2 基于相似度矩陣的非離群點剪枝策略

為了能夠篩選出與其他樣本相似度較小的對象,下一步,需要根據(jù)式(5)計算得到的相似度矩陣對數(shù)據(jù)集進行非離群點剪枝.

(7)

然后,將度矩陣D中的所有元素d11,d22,…,dnn按照從小到大排列,選取相似度值較小的一部分樣本作為數(shù)據(jù)集的離群點候選集.

基于相似度矩陣的非離群點剪枝策略可以有效地適應不規(guī)則形狀、非均勻分布的數(shù)據(jù)集,還原出數(shù)據(jù)集的基本特征,更好地區(qū)分原始數(shù)據(jù)和離群數(shù)據(jù),使后續(xù)的局部離群點檢測更具針對性,從而提高離群點檢測的精確度.

3.3 算法描述

輸入:數(shù)據(jù)集X={x1,x2,…,xn},近鄰個數(shù)k,離群點候選集樣本個數(shù)c,離群點個數(shù)m

輸出:數(shù)據(jù)集X的離群點集合

Step1.利用式(5)建立相似度矩陣W;

Step2.計算相似度矩陣W的度矩陣D;

Step3.將度矩陣D中的所有元素按照從小到大排列;

Step4.選取度矩陣中相似度值較小的前c個數(shù)據(jù)對應的樣本作為離群點候選集;

Step5.從離群點候選集任取一個對象p,計算對象p的第k距離k-distance(p)和第k距離鄰域Nk-distance(p);

Step6.根據(jù)式(2)計算對象p相對于對象o的可達距離reach-dist(p,o);

Step7.根據(jù)式(3)計算對象p的局部可達密度lrdk(p);

Step8.根據(jù)式(4)計算對象p的局部離群因子LOFk(p);

Step9.重復Step 5～ Step 8,直至計算得到離群點候選集中所有對象的局部離群因子;

Step10.對離群點候選集中所有對象的局部離群因子的值由大到小排序,輸出排序后前m個對象作為數(shù)據(jù)集X的離群點集合.

3.4 算法復雜度分析

本文算法主要分為兩個階段,則其時間復雜度主要由兩部分組成.首先,構造樣本的相似度矩陣,時間復雜度為O(N2),根據(jù)計算得到的相似度矩陣對數(shù)據(jù)集進行非離群點剪枝,時間復雜度為O(N)+O(NlogN),其中,N為數(shù)據(jù)集中的樣本個數(shù);其次,計算離群點候選集中所有對象的局部離群因子,時間復雜度為O(M2),對離群點候選集中所有對象的局部離群因子排序,時間復雜度為O(MlogM),其中,M表示剪枝后的離群點候選集中樣本個數(shù).綜上,本文算法的時間復雜度為O(N2)+O(N)+O(NlogN)+O(M2)+O(MlogM),即O(N2)+O(M2).通常情況下,離群點個數(shù)遠遠小于樣本個數(shù),因此離群點候選集中樣本個數(shù)也遠遠小于樣本個數(shù),即M<

4 實驗結果與分析

4.1 人工數(shù)據(jù)集仿真實驗

為了驗證本文算法對于不規(guī)則形狀數(shù)據(jù)集離群點檢測的有效性,實驗選取了兩組分布復雜的人工數(shù)據(jù)集進行仿真實驗,每組人工數(shù)據(jù)集中含有少量隨機分布的離群點,實驗數(shù)據(jù)如圖2所示.第一組人工數(shù)據(jù)集有500個點以及20個離群點,共520個點;第二組人工數(shù)據(jù)集有312個點以及18個離群點,共330個點.

圖2 人工數(shù)據(jù)集Fig.2 Artificial datasets

實驗分別采用本文算法和LOF算法對人工數(shù)據(jù)集進行離群點檢測,將離群點候選集樣本個數(shù)c設置為離群點數(shù)m的1.5倍,LOF算法的近鄰個數(shù)k設置為9,得到兩組數(shù)據(jù)集的實驗結果如圖3和圖4所示.圖中分別用點和圓圈表示進行離群點檢測后得到的離群點和原始數(shù)據(jù).

第一組人工數(shù)據(jù)集有20個離群點,LOF算法檢測出5個離群點,本文算法檢測出17個離群點.第二組人工數(shù)據(jù)集有18個離群點,LOF算法檢測出2個離群點,本文算法檢測出16個離群點.從圖3和圖4中的實驗結果可以看出,本文算法可以較好地完成不規(guī)則形狀數(shù)據(jù)集的離群點檢測.相比于LOF算法,本文算法具有較高的離群點檢測精確度,可以更好地反映出數(shù)據(jù)集的原有特征.

4.2 UCI數(shù)據(jù)集仿真實驗

UCI數(shù)據(jù)集常用于分類、聚類等算法的有效性驗證,數(shù)據(jù)中的離群點是未知的,不能直接用于離群點檢測算法的驗證實驗.所以,在實驗之前需要對數(shù)據(jù)進行處理,本文參照文獻[13]的方法,刪除原始數(shù)據(jù)集中某一類的數(shù)據(jù),僅保留該類極少量的點,如表1所示,“刪除類中樣本數(shù)目”表示原始數(shù)據(jù)集中此類別數(shù)據(jù)的樣本個數(shù),“離群點數(shù)”表示刪除此類樣本的大部分數(shù)據(jù)后余下的樣本個數(shù),由于余下的這些樣本偏離于其它類別,且數(shù)量較少,可視為離群點,括號內(nèi)的數(shù)字表示存在兩個刪除類時,每個刪除類中余下的離群點數(shù).文章分別采用本文提出的算法,文獻[13]提出的LCDO算法,文獻[14]提出的LOAS算法和LOF算法對處理后的UCI數(shù)據(jù)集進行離群點檢測,實驗結果如表2所示.

圖3 第一組數(shù)據(jù)集實驗結果Fig.3 Experimental results of the first data set

圖4 第二組數(shù)據(jù)集實驗結果Fig.4 Experimental results of the second data set

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

表2 四種算法在UCI數(shù)據(jù)集上的離群點檢測結果對比Table 2 Comparison of outlier detection results of the four algorithms on UCI datasets

從表2實驗結果看出,LOF算法對于UCI數(shù)據(jù)集的離群點檢測結果較差;在Glass數(shù)據(jù)集和Yeast數(shù)據(jù)集的離群點檢測實驗中,本文算法、LOAS算法和LCDO算法均可有效檢測出離群點;在Iris數(shù)據(jù)集和Ionosphere數(shù)據(jù)集的離群點檢測實驗中,本文算法取得了最好的檢測結果,性能更優(yōu).因此,本文提出的算法對于復雜分布數(shù)據(jù)的離群點檢測是有效的.

5 結束語

本文將相似度矩陣的構造方法引入到離群點檢測中,提出了一種基于相似度剪枝的離群點檢測算法.該算法通過基于相似度矩陣的非離群點剪枝,有效地找到與其他數(shù)據(jù)相似度較小的一部分對象作為離群點候選集,使得離群點檢測對象更具針對性.然后,通過LOF算法計算離群點候選集中對象的局部離群因子,得到最終的檢測結果.實驗結果表明,該算法在人工數(shù)據(jù)集和真實數(shù)據(jù)集的實驗均取得了較好的結果,有效地提高了離群點檢測的精確度,可以更好地適應不規(guī)則形狀數(shù)據(jù)集和復雜分布的多維數(shù)據(jù)集.下一步,將重點研究參數(shù)與運行結果之間的關系,確定最優(yōu)的離群點候選集樣本個數(shù)c與近鄰個數(shù)k選擇方法.