高維離散分布數(shù)據(jù)集中NSD算法精度、敏感度校正及應(yīng)用

韓孝明

(呂梁學(xué)院 汾陽師范分校，山西 汾陽 032200)

離群點(diǎn)檢測作為數(shù)據(jù)挖掘的重要手段已在各個領(lǐng)域得到了廣泛的應(yīng)用[1-2].基于密度的LOF離群點(diǎn)檢測算法在當(dāng)下比較流行，但由于算法過于復(fù)雜且其準(zhǔn)確性受到參數(shù)選擇的深度影響，因此應(yīng)用于高維離散數(shù)據(jù)集時準(zhǔn)確率并不理想[3-5].本文提出了一種基于數(shù)據(jù)對象密度差異計算的NSD離群點(diǎn)檢測算法，通過對比數(shù)據(jù)對象密度和在截取距離內(nèi)與其相鄰區(qū)域點(diǎn)的密度來判斷對象的離群趨勢.NSD算法計算過程簡單，計算結(jié)果準(zhǔn)確，具有很高的效率.

1 問題描述

在眾多的數(shù)據(jù)集離群點(diǎn)檢測方式中，基于密度的LOF檢測算法最具典型性，它通過計算數(shù)據(jù)集中各數(shù)據(jù)對象的間距，即在事先設(shè)定相鄰數(shù)據(jù)對象數(shù)量的前提下計算對象的最高分布密度，然后以此為基礎(chǔ)確定特定對象的離群系數(shù).離群系數(shù)越大，對象成為離群點(diǎn)的可能性越高.由此可見LOF算法通過離群系數(shù)的數(shù)值大小判斷對象的離群傾向[6-7].然而，該算法必須對所有的對象逐一進(jìn)行密度和離群系數(shù)的計算，且一旦參數(shù)選擇不當(dāng)就難以獲得準(zhǔn)確的結(jié)論.基于以上分析，優(yōu)化算法流程、降低參數(shù)因素干擾能夠有效提高算法的準(zhǔn)確度，具體可通過以下集中方式進(jìn)行.

(1)設(shè)定一個數(shù)據(jù)點(diǎn)截取距離，以數(shù)據(jù)對象為中心，以該距離為半徑劃定一個圓形區(qū)域作為數(shù)據(jù)對象的相鄰區(qū)域，取代LOF算法按數(shù)量選擇相鄰數(shù)據(jù)點(diǎn)的方式，對象離群程度越高，區(qū)域內(nèi)相鄰點(diǎn)越少，由此可減少計算量.

(2)直接以區(qū)域內(nèi)的相鄰點(diǎn)數(shù)量描述對象的密度，取代LOF算法通過數(shù)據(jù)點(diǎn)間距值進(jìn)行密度計算的方式，進(jìn)一步簡化計算流程.

(3)對所有沒有相鄰數(shù)據(jù)點(diǎn)的對象進(jìn)行統(tǒng)一賦值，無需計算數(shù)據(jù)集中每個數(shù)據(jù)對象的離群系數(shù).

以上幾點(diǎn)即為NSD作為LOF優(yōu)化算法的設(shè)計思路.

2 NSD算法設(shè)計

每一個數(shù)據(jù)集X中都包含了數(shù)據(jù)的K種屬性，xi、xj分別為從數(shù)據(jù)集中隨機(jī)選取的兩個數(shù)據(jù)對象，dist(xi，xj)為二者在數(shù)據(jù)集中的距離，其表達(dá)式為

(1)

基于數(shù)據(jù)屬性的不同設(shè)定一個截取距離R，由此可定義在dist(xi，xj)≤R的條件下由所有與目標(biāo)對象距離為dist(xi，xj)的數(shù)據(jù)所組建的數(shù)據(jù)集為目標(biāo)對象xi的鄰域系統(tǒng)NR(xi)，其構(gòu)成如圖1圓形區(qū)域所示.

對于圖1中的多屬性數(shù)據(jù)集，C1、C2、C3分別為其中的三個屬性簇，O1、O2是兩個離群數(shù)據(jù)點(diǎn).以C2簇中的目標(biāo)對象xi為中心，以截取距離R為半徑的鄰域系統(tǒng)內(nèi)包含xm，xn，xj，xl4個數(shù)據(jù)點(diǎn)，因此xi的鄰域系統(tǒng)可表示為

NR(xi)=

{xm，xn，xj，xl}，∣NR(xi)∣=4.

圖1 鄰域系統(tǒng)示意圖

鄰域系統(tǒng)中數(shù)據(jù)點(diǎn)密度den(xi)的表達(dá)式為

(2)

由上式可見，NR(xi)中數(shù)據(jù)點(diǎn)數(shù)量越多，則其密度越大.同時，

0≤den(xi)≤(N-1)/R,

N為數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的總數(shù)量.

不同對象的鄰域系統(tǒng)密度如圖2所示.

圖2 不同對象的鄰域系統(tǒng)密度

圖2中的三個圓形區(qū)域分別為正常數(shù)數(shù)據(jù)對象xi與離群數(shù)據(jù)對象O1、O2的鄰域系統(tǒng)，它們的半徑即截取距離是相同的.xi在C2屬性簇中的鄰域系統(tǒng)包含了4個數(shù)據(jù)點(diǎn)，O1在C1屬性簇中的鄰域系統(tǒng)同樣包含了4個數(shù)據(jù)點(diǎn)，而O2的鄰域系統(tǒng)是空的，按照鄰域系統(tǒng)密度的定義，數(shù)據(jù)對象xi和O1的鄰域系統(tǒng)密度均為4/R，而數(shù)據(jù)對象O2的鄰域系統(tǒng)密度為0.

在以鄰域系統(tǒng)中數(shù)據(jù)點(diǎn)數(shù)量描述系統(tǒng)密度的前提下，數(shù)據(jù)對象xi在多屬性數(shù)據(jù)集X中的離群度NSD(xi)的計算方式為

(3)

當(dāng)∣NR(xi)∣>0時，上式可轉(zhuǎn)換為

(4)

離群度數(shù)值與目標(biāo)對象的離群程度存在以下幾種對應(yīng)關(guān)系.

(1)當(dāng)NSD(xi)=0時，表明目標(biāo)對象的鄰域系統(tǒng)中沒有數(shù)據(jù)點(diǎn)，xi不屬于任何屬性簇，離群程度較高.

(2)當(dāng)NSD(xi)>1時，表明目標(biāo)對象的鄰域系統(tǒng)中雖然存在一些數(shù)據(jù)點(diǎn)，但xi與這些數(shù)據(jù)點(diǎn)各自鄰域系統(tǒng)的密度存在較大差異，即xi與這些數(shù)據(jù)點(diǎn)并不屬于同一個屬性簇.

(3)當(dāng)NSD(xi)≈1時，表明xi與其鄰域數(shù)據(jù)點(diǎn)各自鄰域系統(tǒng)的密度近似相等，二者位于同一屬性簇的可能性較大.

(4)當(dāng)NSD(xi)<1時，表明xi的鄰域系統(tǒng)密度大于其鄰域數(shù)據(jù)點(diǎn)的鄰域系統(tǒng)密度，是數(shù)據(jù)集中較為常見的現(xiàn)象.

由此可見，對于數(shù)據(jù)集中的任意一個數(shù)據(jù)對象xi，如果其離群度為0，則可認(rèn)定其為離群點(diǎn)，如果其離群度大于1，則說明對象的離群趨勢比較明顯.數(shù)據(jù)對象離群程度如圖3所示.

圖3 數(shù)據(jù)對象離群程度示意圖

在圖3中，xd為離群點(diǎn)O1的鄰域系統(tǒng)數(shù)據(jù)點(diǎn)之一，在半徑同樣為R的xd的鄰域系統(tǒng)中包含了19個數(shù)據(jù)點(diǎn)，那么xd與O1的鄰域系統(tǒng)密度比為

den(xd)/den(O1)=(4/R)/(19/R)=19/4，

即二者的鄰域密度相似性量化數(shù)值為4.75.通過式(4)可計算出NSD(O1)=3.8125，說明O1具有明顯的離群趨勢.相比之下，對于圖2中C2屬性簇內(nèi)的正常數(shù)據(jù)對象xi，其鄰域系統(tǒng)密度為4/R，

NSD(xi)=1.25，

與1較為接近，說明xi基本不具離群可能性.

在確定數(shù)據(jù)集X中任意數(shù)據(jù)對象xi的離群程度時，如果僅通過xi鄰域系統(tǒng)的密度進(jìn)行判斷，那么當(dāng)對象位于數(shù)據(jù)點(diǎn)分布較為稀疏的屬性簇中時發(fā)生誤判的可能性極大，因此NSD算法基于數(shù)據(jù)對象本身及其領(lǐng)域數(shù)據(jù)點(diǎn)各自的鄰域系統(tǒng)密度相似性進(jìn)行離群趨勢判斷，從而保證了離群度判定的準(zhǔn)確性.算法流程如下[8-11].

輸入：k維數(shù)據(jù)集X，截取距離R，n.

輸出：NSD算法判定的離群點(diǎn)編號.

3 測試與分析

選取國外某網(wǎng)絡(luò)入侵記錄數(shù)據(jù)集進(jìn)行離群點(diǎn)檢測，該數(shù)據(jù)集為高維數(shù)據(jù)集，特征維度多達(dá)41個，共包含50000個數(shù)據(jù)點(diǎn)，其中離群點(diǎn)數(shù)量為1500個，各數(shù)據(jù)對象最小間距值為1.5，對象最少有1個臨近數(shù)據(jù)點(diǎn)數(shù)量.分別通過本文設(shè)計的NSD算法與現(xiàn)有的CBOF、LDOF、LOF算法進(jìn)行檢測并對比檢測結(jié)果，以驗(yàn)證NSD算法的性能與檢測準(zhǔn)確性.本次測試用計算機(jī)采用Intel Corei 5處理器、主頻為2.5 GHz、4 GB內(nèi)存、安裝Windows 7專業(yè)版操作系統(tǒng)，算法軟件運(yùn)行環(huán)境為MATLAB 2016A.

由于NSD算法的關(guān)鍵參數(shù)為截取距離R，而其它3種算法的關(guān)鍵參數(shù)為近鄰參數(shù)k，所以需要對各算法的參數(shù)敏感性進(jìn)行計算，以反映其對不同算法檢測準(zhǔn)確率的影響程度，具體計算公式為

(5)

式中：m為實(shí)驗(yàn)次數(shù)，參數(shù)變化速率為設(shè)定值.

以所選數(shù)據(jù)集為基礎(chǔ)，按數(shù)據(jù)點(diǎn)數(shù)量為10000、20000、30000、40000、50000創(chuàng)建5個不同規(guī)模的數(shù)據(jù)集，通過上述算法對各數(shù)據(jù)集分別進(jìn)行離群點(diǎn)檢測，準(zhǔn)確率結(jié)果如表1所列.

表1 不同算法的離群度檢測準(zhǔn)確率對比

由表1中的數(shù)據(jù)可見，在各種關(guān)鍵參數(shù)設(shè)定的條件下，NSD算法的離群點(diǎn)檢測準(zhǔn)確率均高于其它3種算法，截取距離為較小值2時，準(zhǔn)確率較低，而延長截取距離后檢測準(zhǔn)確率均達(dá)到90%以上.同時，通過表中數(shù)值計算各算法的參數(shù)敏感性，結(jié)果為

S(NSD)=24.72，S(CBOF)=34.01，
S(LOF)=45.03，S(LDOF)=52.98，

對比可見NSD算法的參數(shù)敏感性較低.

在不同數(shù)據(jù)規(guī)模下對NSD算法的R及其它算法的k取最優(yōu)值，得到最高檢測準(zhǔn)確率條件下的算法運(yùn)行效率，具體結(jié)果如表2所列.

表2 不同算法的運(yùn)行效率對比

由表2中的數(shù)據(jù)可見，各算法的運(yùn)行時間隨數(shù)據(jù)集規(guī)模的擴(kuò)大而延長，而在相同數(shù)據(jù)規(guī)模的條件下NSD算法的運(yùn)行時間均比其它3種算法短，由此可認(rèn)定NSD算法具有更高的運(yùn)行效率.

4 結(jié)語

為了有針對性地解決傳統(tǒng)離群點(diǎn)檢測算法參數(shù)敏感性高、準(zhǔn)確率低的問題，本文提出了一種基于鄰域數(shù)據(jù)對象密度差異的NSD離群點(diǎn)檢測算法，通過目標(biāo)對象與其鄰域數(shù)據(jù)點(diǎn)的密度相似性判斷其在數(shù)據(jù)集中的離群程度，相較于傳統(tǒng)的LOF算法，本文所設(shè)計的算法優(yōu)化了計算流程，提高了計算結(jié)果的準(zhǔn)確性并降低了參數(shù)對計算精度的影響，對于各鄰域數(shù)據(jù)挖掘技術(shù)的發(fā)展具有重要意義.