基于鄰域密度的異構數據局部離群點挖掘算法

王曉輝，宋學坤*，王曉川

(1. 河南中醫藥大學，河南 鄭州 450046；2. 鄭州大學，河南 鄭州 450001)

1 引言

離群點挖掘就是搜索出數據集內的異常數據，這些異常數據通常表現出一定的應用價值[1]。最初對于離群點的理解比較偏向無益信息[2]，認為一部分離群數據可能是采集過程中的偏差導致，對其深入挖掘會影響數據分析的整體質量。隨著數據采集工具的性能提升，以及離群點理解的加深，認識到離群點含有特定的分布特征，可以通過分析獲取其潛在的價值信息，是一種有益信息。離群點挖掘是數據分析領域的關鍵技術，有著廣泛的應用場景。尤其是伴隨著網絡和大數據的發展，在信息攻擊和金融詐騙相關檢測，以及氣象預報等方面[3]，離群點挖掘都有著不可或缺的地位。

在實際應用的驅動下，離群點挖掘引發了很多相關研究。目前對于離群點的挖掘，較為常見的基礎算法有距離、聚類，以及密度等[4]。文獻[5]通過近鄰的相互密度與γ密度對數據采取聚類處理，并利用聚類邊緣判斷出離群點。算法結合了聚類與密度兩種方式，無需人工介入參數，但是算法沒有對聚類時密度進行評判，從而無法準確判定離群點是否被有效挖掘。文獻[6]在分層次劃分基礎上采用了距離方式來判斷離群點，文獻[7]利用鄰域粒距離和粗糙集來判斷離群點。這類基于距離的算法在數據稠密的區域很容易產生誤判，且優化難度也較大。文獻[8]通過鄰域密度的比較，判斷數據是否為離群點。該算法較LOF具有更好的高維性能，但是挖掘精度仍然需要合適的參數支持。

針對高維異構數據，結合現有算法存在的挖掘精度差、參數敏感等缺陷，提出了一種基于鄰域密度的局部挖掘算法。通過對數據集合理分割，提高對大規模數據和高維數據的處理能力。并通過核函數改進鄰域密度計算，降低算法對異構數據的敏感度。為防止離群點的誤判，采用離群分數檢查離群點挖掘結果。本文算法的設計過程綜合考慮了離群點挖掘的準確度、效率和覆蓋率，總體性能更加均衡。

2 異構數據離群點挖掘原理

假定str為一組高維異構數據，則對于str中任意的兩個數據點di和dj，其距離可以描述如下

(1)

其中，n代表str的屬性維度；di[k]、dj[k]分別代表di、dj對應k維的度量值。設存在非確定數據集為D，數據點di在D中的近鄰可以描述為

(2)

其中，l0表示搜索范圍。如果搜索的鄰域數據量為m，那么當|N(D，di)|

(3)

3 數據集區域分割

隨著數據規模的增加，對于高維異構數據而言，直接采取整體的離群點挖掘無法達到預期效果。而采取區域分割的局部離群點挖掘，則很容易使分割子區域過多或者過少，從而影響離群點挖掘效果。于是，本文根據節點計算性能進行區域分割。假定網絡中包含n臺處理機，則任意維度數據被分割的段數計算如下

(4)

comp(pri)是處理機pri的計算性能。考慮到區域分割的合理性，通過各個維度的數據分布來評價區域分割的效果，公式如下

(5)

為保證區域分割在多維度間的分布均衡，在計算得到一維分布情況后，利用相鄰維度構建二維分布，公式如下

(6)

dis(i，j)描述了i與j構成的二維數據分布情況。與式(5)不同的是，Nm為i與j構成的二維空間區域m中的數據量。根據一維與二維的數據分布完成異構數據的區域分割，在dis(j)和dis(i，j)值最小處進行分割，同時滿足分割段數，從而使高維異構數據分割得到數據分布均衡的子區域。

4 離群點挖掘算法

4.1 基于核鄰域密度的離群點檢測

在分割完成的任意子區域中，數據集合描述為X={x1，x2，…，xn}。若該子區域存在h個屬性，則X內的數據i可描述為xi=〈xi1，xi2，…，xih〉。其中，xih為數據i對應的h屬性值。對于X內的數據xi和xj，它們的距離計算公式如下

(7)

計算得到X內l(xi，xj)的最大與最小值，分別記做max(l)、min(l)。根據式(1)將此時的鄰域定義如下

N(xi)={xi|xj∈X，l(xi，xj)

(8)

其中，R∈(min(l)，max(l))代表搜索半徑；xi的鄰域數據范圍為[0，n-1]。由N(xi)可以計算得到鄰域密度如下

(9)

對于異構數據的非確定性，采用平均鄰域密度計算缺乏穩定性和魯棒性。考慮到核密度在非平穩數據處理方面的有效性，這里采取核密度來描述局部密度。由于它可以根據高斯分布得到數據出現次數，因此與數據的異構特性無關。

對于分割子區域中數據集合X內的任意數據xi，假定其密度是de(xi)，則引入xi核函數可得

(10)

Rg(xi)=R(xi/g)/g，R(xi)代表xi核函數。de(xi|g)代表xi+g密度，g的平均值是0。如果g足夠小，那么de(xi|g)近似等于de(xi)。利用de(xi|g)計算得到g的后驗密度，公式如下

(11)

pde(g)是對g求解先驗密度。采用貝葉斯對pde(g)進行估算，可得

(12)

a代表超參數向量。通過任意xi的樣本便能夠得到de(xi|g)

(13)

將de(xi|g)作為數據鄰域密度，能夠更好的接近真實數據密度。此時，由鄰域及密度關系計算得到各數據離群度，公式描述如下

NSD(xi)=

(14)

NSD(xi)的值描述了xi在局部數據中的鄰域狀態。當NSD(xi)=0時，說明在搜索半徑內xi不存在近鄰，即xi嚴重偏離。當NSD(xi)值與1較為接近時，說明鄰域密度較為接近，即xi和其它數據屬性接近。當NSD(xi)∈(0，1)范圍，且NSD(xi)值遠離1時，說明xi比近鄰數據具有更高的屬性依賴，即xi屬于正常數據。當NSD(xi)>1，且NSD(xi)值遠離1時，說明xi的鄰域密度較小，即和近鄰存在偏離。基于以上分析，在NSD(xi)=0的情況下，判斷數據xi一定為離群點；在NSD(xi)>1的情況下，判斷數據xi有可能是離群點。

4.2 離群分數

(15)

得到數據集X={x1，x2，…，xn}對應的權重集合為W={wx1，wx2，…，wxn}。當wxi值小于1，說明xi和近鄰的距離較近，離群的可能性較小。此時，則可對xi采取剪枝，有利于降低數據處理量，改善數據挖掘效率。當wxi值不小于1，說明xi和近鄰的距離較遠，存在離群的可能。此時，則將xi保留，并利用如下公式計算加權分數

S=wxi/(N(xi)+1)

(16)

為了防止近鄰系統存在誤差，引入逆k近鄰結合加權分數，得到數據的離群分數如下

(17)

k代表xi的近鄰數量；代表逆k近鄰數量。結合離群分數，可以在鄰域密度基礎上對數據的鄰域狀態和離群狀態采取進一步確定，提高離群點挖掘的準確性。

5 仿真與結果分析

5.1 實驗環境與評價指標

鄰域密度離群點挖掘算法基于Eclipse開發，采用Java語言編程，并通過MATLAB完成實驗數據的展示分析。為了有效驗證算法對異構數據離群點的挖掘效果，引入人工與UCI數據集，并與NGOD[7]和NSD[8]算法進行對比實驗。

在對異構數據離群點挖掘算法評價時，采用準確度(Precision)與覆蓋率(CoverageRatio)兩個衡量指標。Precision的計算公式為

(18)

TP是挖掘出的實際離群點個數；FP是離群點被錯誤挖掘的個數。Precision值越大，說明離群點挖掘越準確。CoverageRatio的計算公式為

(19)

OStrue(D)是數據集合D內實際的離群點集；OS(D)是算法挖掘出離群點集。CoverageRatio值越大，說明離群點挖掘效果越好。

5.2 人工數據集

人工數據集能夠靈活模擬不同規模和維數情況下的異構數據。本文通過隨機方式產生n個數據，并以它們為中心，根據高斯規則產生聚簇數據。關于人工數據集的具體描述如表1所示。

表1 人工數據集描述

改變人工數據集的參數，分別得到數據量和數據維數對離群點挖掘準確度的影響，結果如圖1、圖2所示。根據結果對比可得，由于本文算法采用了核函數計算鄰域密度，對于非確定異構數據具有更好的魯棒性，所以在數據量或者數據維數改變的情況下，離群點挖掘準確度幾乎不受影響，明顯優于NGOD和NSD算法的性能。

圖1 Precision與數據量的關系

圖2 Precision與數據維數的關系

分別得到不同數據量和數據維數對離群點挖掘效率的影響，結果如圖3、圖4所示。根據結果分析可得，由于本文算法采用了數據分割和剪枝策略，可以有效降低待處理的數據量，所以算法的挖掘效率受數據量和維數的影響相對較小，即便是在數據量達到9×105，離群點的挖掘時間也僅為5.64s；數據維數達到100，挖掘時間也僅為0.94s。

圖3 效率與數據量的關系

圖4 效率與數據維數的關系

圖5描述了覆蓋率與異構數據中離群點對象數量變化的關系。由結果可以看出，在離群點對象為40時，本文方法的CoverageRatio指標已經達到98.63%，而此時NGOD和NSD算法僅為88.04%、92.56%。表明本文方法對于異構數據具有更好的挖掘效果，能夠有效利用有限數據對象，分析檢測出其中包含的離群點。

圖5 覆蓋率結果對比

5.3 UCI數據集

UCI數據集能夠反映實際應用場景，本文選擇UCI中的Ionosphere、Statlog、Breast和Seismic四種數據集，關于它們的具體描述如表2所示。針對Ionosphere、Statlog、Breast和Seismic，將離群點確定為類型較小的數據。

表2 數據集描述

得到各數據集下離群點挖掘的準確度和效率，結果如圖6和圖7所示。根據結果可知，數據集的差異會對離群點的挖掘準確度產生一定的影響，但是本文算法無論在哪一種數據集下，都能獲得良好的準確度，同時保持良好的挖掘效率。表明本文算法對于異構數據離群點的挖掘具有良好的普適性。

圖6 不同數據集下Precision對比

圖7 不同數據集下效率對比

6 結束語

關于高維異構數據，提出了基于鄰域密度的局部離群點挖掘算法。利用區域分割將高維數據拆分成合理的子區域，降低大量高維數據的處理難度。采用核鄰域密度替代平均鄰域密度，使密度計算與數據異構無關。最后在鄰域密度基礎上對數據的鄰域狀態和離群狀態采取進一步確定，提高離群點挖掘的準確性。通過仿真結果，說明數據量和數據維數都是影響數據離群點挖掘的主要因素，但是本文所提算法的離群點挖掘準確度、覆蓋率，以及效率均明顯優于對比算法，且對于不同類型數據集具有更好的適應性。