基于鄰域密度的異構(gòu)數(shù)據(jù)局部離群點(diǎn)挖掘算法

王曉輝，宋學(xué)坤*，王曉川

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

1 引言

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

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

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

2 異構(gòu)數(shù)據(jù)離群點(diǎn)挖掘原理

假定str為一組高維異構(gòu)數(shù)據(jù)，則對于str中任意的兩個(gè)數(shù)據(jù)點(diǎn)di和dj，其距離可以描述如下

(1)

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

(2)

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

(3)

3 數(shù)據(jù)集區(qū)域分割

隨著數(shù)據(jù)規(guī)模的增加，對于高維異構(gòu)數(shù)據(jù)而言，直接采取整體的離群點(diǎn)挖掘無法達(dá)到預(yù)期效果。而采取區(qū)域分割的局部離群點(diǎn)挖掘，則很容易使分割子區(qū)域過多或者過少，從而影響離群點(diǎn)挖掘效果。于是，本文根據(jù)節(jié)點(diǎn)計(jì)算性能進(jìn)行區(qū)域分割。假定網(wǎng)絡(luò)中包含n臺處理機(jī)，則任意維度數(shù)據(jù)被分割的段數(shù)計(jì)算如下

(4)

comp(pri)是處理機(jī)pri的計(jì)算性能?？紤]到區(qū)域分割的合理性，通過各個(gè)維度的數(shù)據(jù)分布來評價(jià)區(qū)域分割的效果，公式如下

(5)

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

(6)

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

4 離群點(diǎn)挖掘算法

4.1 基于核鄰域密度的離群點(diǎn)檢測

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

(7)

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

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

(8)

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

(9)

對于異構(gòu)數(shù)據(jù)的非確定性，采用平均鄰域密度計(jì)算缺乏穩(wěn)定性和魯棒性?？紤]到核密度在非平穩(wěn)數(shù)據(jù)處理方面的有效性，這里采取核密度來描述局部密度。由于它可以根據(jù)高斯分布得到數(shù)據(jù)出現(xiàn)次數(shù)，因此與數(shù)據(jù)的異構(gòu)特性無關(guān)。

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

(10)

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

(11)

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

(12)

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

(13)

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

NSD(xi)=

(14)

NSD(xi)的值描述了xi在局部數(shù)據(jù)中的鄰域狀態(tài)。當(dāng)NSD(xi)=0時(shí)，說明在搜索半徑內(nèi)xi不存在近鄰，即xi嚴(yán)重偏離。當(dāng)NSD(xi)值與1較為接近時(shí)，說明鄰域密度較為接近，即xi和其它數(shù)據(jù)屬性接近。當(dāng)NSD(xi)∈(0，1)范圍，且NSD(xi)值遠(yuǎn)離1時(shí)，說明xi比近鄰數(shù)據(jù)具有更高的屬性依賴，即xi屬于正常數(shù)據(jù)。當(dāng)NSD(xi)>1，且NSD(xi)值遠(yuǎn)離1時(shí)，說明xi的鄰域密度較小，即和近鄰存在偏離?；谝陨戏治觯贜SD(xi)=0的情況下，判斷數(shù)據(jù)xi一定為離群點(diǎn)；在NSD(xi)>1的情況下，判斷數(shù)據(jù)xi有可能是離群點(diǎn)。

4.2 離群分?jǐn)?shù)

(15)

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

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

(16)

為了防止近鄰系統(tǒng)存在誤差，引入逆k近鄰結(jié)合加權(quán)分?jǐn)?shù)，得到數(shù)據(jù)的離群分?jǐn)?shù)如下

(17)

k代表xi的近鄰數(shù)量；代表逆k近鄰數(shù)量。結(jié)合離群分?jǐn)?shù)，可以在鄰域密度基礎(chǔ)上對數(shù)據(jù)的鄰域狀態(tài)和離群狀態(tài)采取進(jìn)一步確定，提高離群點(diǎn)挖掘的準(zhǔn)確性。

5 仿真與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境與評價(jià)指標(biāo)

鄰域密度離群點(diǎn)挖掘算法基于Eclipse開發(fā)，采用Java語言編程，并通過MATLAB完成實(shí)驗(yàn)數(shù)據(jù)的展示分析。為了有效驗(yàn)證算法對異構(gòu)數(shù)據(jù)離群點(diǎn)的挖掘效果，引入人工與UCI數(shù)據(jù)集，并與NGOD[7]和NSD[8]算法進(jìn)行對比實(shí)驗(yàn)。

在對異構(gòu)數(shù)據(jù)離群點(diǎn)挖掘算法評價(jià)時(shí)，采用準(zhǔn)確度(Precision)與覆蓋率(CoverageRatio)兩個(gè)衡量指標(biāo)。Precision的計(jì)算公式為

(18)

TP是挖掘出的實(shí)際離群點(diǎn)個(gè)數(shù)；FP是離群點(diǎn)被錯(cuò)誤挖掘的個(gè)數(shù)。Precision值越大，說明離群點(diǎn)挖掘越準(zhǔn)確。CoverageRatio的計(jì)算公式為

(19)

OStrue(D)是數(shù)據(jù)集合D內(nèi)實(shí)際的離群點(diǎn)集；OS(D)是算法挖掘出離群點(diǎn)集。CoverageRatio值越大，說明離群點(diǎn)挖掘效果越好。

5.2 人工數(shù)據(jù)集

人工數(shù)據(jù)集能夠靈活模擬不同規(guī)模和維數(shù)情況下的異構(gòu)數(shù)據(jù)。本文通過隨機(jī)方式產(chǎn)生n個(gè)數(shù)據(jù)，并以它們?yōu)橹行?，根?jù)高斯規(guī)則產(chǎn)生聚簇?cái)?shù)據(jù)。關(guān)于人工數(shù)據(jù)集的具體描述如表1所示。

表1 人工數(shù)據(jù)集描述

改變?nèi)斯?shù)據(jù)集的參數(shù)，分別得到數(shù)據(jù)量和數(shù)據(jù)維數(shù)對離群點(diǎn)挖掘準(zhǔn)確度的影響，結(jié)果如圖1、圖2所示。根據(jù)結(jié)果對比可得，由于本文算法采用了核函數(shù)計(jì)算鄰域密度，對于非確定異構(gòu)數(shù)據(jù)具有更好的魯棒性，所以在數(shù)據(jù)量或者數(shù)據(jù)維數(shù)改變的情況下，離群點(diǎn)挖掘準(zhǔn)確度幾乎不受影響，明顯優(yōu)于NGOD和NSD算法的性能。

圖1 Precision與數(shù)據(jù)量的關(guān)系

圖2 Precision與數(shù)據(jù)維數(shù)的關(guān)系

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

圖3 效率與數(shù)據(jù)量的關(guān)系

圖4 效率與數(shù)據(jù)維數(shù)的關(guān)系

圖5描述了覆蓋率與異構(gòu)數(shù)據(jù)中離群點(diǎn)對象數(shù)量變化的關(guān)系。由結(jié)果可以看出，在離群點(diǎn)對象為40時(shí)，本文方法的CoverageRatio指標(biāo)已經(jīng)達(dá)到98.63%，而此時(shí)NGOD和NSD算法僅為88.04%、92.56%。表明本文方法對于異構(gòu)數(shù)據(jù)具有更好的挖掘效果，能夠有效利用有限數(shù)據(jù)對象，分析檢測出其中包含的離群點(diǎn)。

圖5 覆蓋率結(jié)果對比

5.3 UCI數(shù)據(jù)集

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

表2 數(shù)據(jù)集描述

得到各數(shù)據(jù)集下離群點(diǎn)挖掘的準(zhǔn)確度和效率，結(jié)果如圖6和圖7所示。根據(jù)結(jié)果可知，數(shù)據(jù)集的差異會(huì)對離群點(diǎn)的挖掘準(zhǔn)確度產(chǎn)生一定的影響，但是本文算法無論在哪一種數(shù)據(jù)集下，都能獲得良好的準(zhǔn)確度，同時(shí)保持良好的挖掘效率。表明本文算法對于異構(gòu)數(shù)據(jù)離群點(diǎn)的挖掘具有良好的普適性。

圖6 不同數(shù)據(jù)集下Precision對比

圖7 不同數(shù)據(jù)集下效率對比

6 結(jié)束語

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