基于鄰域值差異度量的離群點(diǎn)檢測(cè)算法

袁 鐘，馮 山

(四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院，成都 610068)(*通信作者電子郵箱fengshanrq@sohu.com)

0 引言

離群點(diǎn)是數(shù)據(jù)集中數(shù)據(jù)對(duì)象特征顯著區(qū)別于其他數(shù)據(jù)對(duì)象的數(shù)據(jù)對(duì)象[1]，其出現(xiàn)往往隱含或預(yù)示具有特殊意義的事件或現(xiàn)象發(fā)生。在入侵與欺詐檢測(cè)、醫(yī)療處理、公共安全等領(lǐng)域，離群點(diǎn)檢測(cè)技術(shù)具有十分重要的應(yīng)用[2-4]。

離群點(diǎn)檢測(cè)研究最早出現(xiàn)于統(tǒng)計(jì)學(xué)領(lǐng)域[5]。后來(lái)，Knorr等[6-7]將其引入到數(shù)據(jù)挖掘領(lǐng)域。現(xiàn)有離群點(diǎn)檢測(cè)方法主要有三類：1)基于統(tǒng)計(jì)[5]；2)基于鄰近性[6-8]；3)基于聚類[9]。其中，基于鄰近性的離群點(diǎn)檢測(cè)有基于距離、基于網(wǎng)格和基于密度三種方式。

符號(hào)型屬性值是離散的，用傳統(tǒng)距離法檢測(cè)符號(hào)型屬性數(shù)據(jù)集的離群點(diǎn)效果并不理想。為此，人們引入了粗糙集下的符號(hào)型屬性離群點(diǎn)檢測(cè)[10]，但它基于等價(jià)關(guān)系和等價(jià)類建模，用于處理數(shù)值型屬性數(shù)據(jù)集時(shí)要先對(duì)屬性值離散化，既增加了處理時(shí)間，還帶來(lái)了明顯的數(shù)據(jù)信息損失，影響檢測(cè)精準(zhǔn)度。

為解決數(shù)值型屬性的粗糙計(jì)算問(wèn)題，結(jié)合鄰域概念和鄰域關(guān)系，文獻(xiàn)[11]建立了鄰域粗糙集模型，它是屬性約簡(jiǎn)、特征選擇、分類和不確定性推理研究中的重要工具[12]；但是，利用鄰域粗糙集模型進(jìn)行離群點(diǎn)檢測(cè)的研究并不多見(jiàn)，文獻(xiàn)[13]進(jìn)行了這方面的研究嘗試，但是其鄰域半徑直接給定，具有較強(qiáng)的主觀性和隨機(jī)性。

針對(duì)離群點(diǎn)檢測(cè)中傳統(tǒng)距離法不能有效處理符號(hào)型屬性和經(jīng)典粗糙集方法不能有效處理數(shù)值型屬性的問(wèn)題，本文以鄰域粗糙集模型為基礎(chǔ)，提出了改進(jìn)的鄰域值差異度量(Neighborhood Value Difference Metric, NVDM)進(jìn)行離群點(diǎn)檢測(cè)。該方法通過(guò)定義鄰域值差異度量來(lái)構(gòu)造表征對(duì)象離群程度的鄰域離群因子(Neighborhood Outlier Factor， NOF)，從而，設(shè)計(jì)并實(shí)現(xiàn)了基于鄰域值差異度量的離群點(diǎn)檢測(cè)(Neighborhood Value Difference Metric-based Outlier Detection, NVDMOD)算法。所提算法拓展了離群點(diǎn)檢測(cè)的傳統(tǒng)距離法和粗糙集法，在計(jì)算單屬性鄰域覆蓋(Single Attribute Neighborhood Cover, SANC)時(shí)改進(jìn)了傳統(tǒng)的無(wú)序逐一計(jì)算模式，使得算法時(shí)間復(fù)雜度降低到了對(duì)數(shù)級(jí)，明顯優(yōu)于現(xiàn)有傳統(tǒng)無(wú)序逐一比較模式。UCI標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)表明，改進(jìn)算法能有效分析和處理符號(hào)型、數(shù)值型和混合型屬性數(shù)據(jù)集的離群點(diǎn)檢測(cè)問(wèn)題，且適應(yīng)能力更強(qiáng)。

1 鄰域粗糙集

對(duì)?x,y,z∈U和B?C，關(guān)聯(lián)于屬性子集B的距離函數(shù)dB:U×U→R+(R+非負(fù)實(shí)數(shù)集)應(yīng)滿足以下條件：

1)dB(x,y)≥0，dB(x,x)=0(非負(fù)性)；

2)dB(x,y)=dB(y,x)(對(duì)稱性)；

3)dB(x,z)≤dB(x,y)+dB(y,z)(三角式)。

如果B={cj1,cj2,…,cjk}?C(1≤k≤m)，距離函數(shù)dB的閔可夫斯基距離計(jì)算公式如下：

因等價(jià)關(guān)系和等價(jià)類只能處理符號(hào)型屬性，可將距離函數(shù)和鄰域半徑ε結(jié)合并用來(lái)對(duì)論域U中的數(shù)據(jù)對(duì)象?；纬删哂邢嗨菩蕴卣鞯泥徲蜿P(guān)系和鄰域類，進(jìn)而構(gòu)建可同時(shí)處理符號(hào)型屬性和數(shù)值型屬性的鄰域信息系統(tǒng)(Neighborhood Information System, NIS)。

定義1 鄰域。對(duì)?x∈U，B?C和ε≥0，x在屬性集B上的ε-鄰域定義為：

(1)

以鄰域信息系統(tǒng)為基礎(chǔ)，可以利用鄰域粗糙性引起的鄰域間的值差異度量對(duì)論域中對(duì)象之間的差異性或離群性進(jìn)行度量，從而發(fā)現(xiàn)離群點(diǎn)。

2 基于鄰域值差異度量的離群點(diǎn)檢測(cè)

2.1 基于鄰域值差異度量的離群點(diǎn)檢測(cè)方法

用鄰域粗糙集進(jìn)行數(shù)據(jù)處理時(shí)通常會(huì)存在數(shù)據(jù)描述的量級(jí)和量綱差異。為使不同數(shù)據(jù)類型的表述都得到有效的數(shù)據(jù)處理結(jié)果，需要對(duì)數(shù)值型屬性值進(jìn)行歸一化、標(biāo)準(zhǔn)化處理。本文采用的最小—最大法歸一化的計(jì)算公式如下：

(2)

其中:maxcj和mincj為U中對(duì)象關(guān)于屬性cj的最大取值和最小取值。顯然，標(biāo)準(zhǔn)化屬性取值區(qū)間為[0,1]。

為同時(shí)有效度量數(shù)值型和混合型屬性值的差異，可用混合歐氏重疊度量(Heterogeneous Euclidian-Overlap Metric, HEOM)[14]進(jìn)行鄰域距離度量。

定義5 混合歐氏重疊度量。對(duì)?x,y∈U，x和y的混合歐氏重疊度量HEOMB(x,y)定義為：

(3)

其中：

dcjh(x,y)=

對(duì)象鄰域半徑的設(shè)定一般由專家根據(jù)經(jīng)驗(yàn)確定，具有較強(qiáng)的主觀性和隨機(jī)性。減少鄰域構(gòu)造判定算法對(duì)專家所定參數(shù)的敏感度，是提升離群點(diǎn)檢測(cè)算法準(zhǔn)確率的客觀基礎(chǔ)。能夠?qū)?shù)據(jù)對(duì)象的屬性取值分布信息和專家知識(shí)融合的鄰域半徑參數(shù)確定法更加合理、有效。為此，本文提出了x在屬性cj上的鄰域半徑設(shè)置新方法，它具有很好的自適應(yīng)特征：

(4)

其中：std(cj)是cj屬性的取值標(biāo)準(zhǔn)差，用于衡量cj的均值分散程度，std(cj)大表示大部分?jǐn)?shù)據(jù)對(duì)象在cj上的取值與其均值間的差異大，std(cj)小表示數(shù)據(jù)對(duì)象在cj上的取值與均值接近。λ是專家預(yù)設(shè)的用于調(diào)整鄰域半徑大小的參數(shù)，λ<1時(shí)鄰域半徑應(yīng)大于屬性值標(biāo)準(zhǔn)差；λ=1時(shí)鄰域半徑即屬性值標(biāo)準(zhǔn)差；λ>1時(shí)鄰域半徑應(yīng)小于屬性值標(biāo)準(zhǔn)差。這種主、客觀融合的鄰域半徑調(diào)節(jié)法兼顧了專家經(jīng)驗(yàn)和屬性取值分布特征對(duì)對(duì)象離群性的影響，為有效的自適應(yīng)離群點(diǎn)檢測(cè)奠定了基礎(chǔ)。

通過(guò)對(duì)象鄰域及其距離度量可刻畫對(duì)象間的相似性或不可區(qū)分性。值差異度量(Value Difference Metric, VDM)[15]是度量符號(hào)型屬性距離的一種有效的非加權(quán)函數(shù)。假定x和y是U中對(duì)象，F(xiàn)是U的特征集，xf和yf是x和y在f上的取值，df(xf,xf)是xf和xf的距離。對(duì)象x和y的VDM可定義如下：

其中：df(xf,yf)=(P(xf)-P(yf))2，P(xf)和P(yf)是x和y在f上的取值概率。

以此類推，為度量數(shù)值型屬性取值的離群程度，可通過(guò)對(duì)象鄰域概念將給定對(duì)象的鄰域半徑內(nèi)的對(duì)象集成，進(jìn)而對(duì)數(shù)值型屬性取值進(jìn)行離群度量。為此，可定義鄰域值差異度量(NVDM)、鄰域離群因子(NOF)及鄰域離群點(diǎn)概念如下。

定義6 鄰域值差異度量。給定λ>0，對(duì)?xi,xj∈U，xi,xj的鄰域值差異度量NVDM(xi,xj)為：

(5)

實(shí)際上，對(duì)象離群程度可用鄰域離群因子度量，可將文獻(xiàn)[13]的鄰域離群因子開(kāi)平方以加大對(duì)象離群程度的變化對(duì)其離群特性的正面影響。

定義7 鄰域離群因子。對(duì)?xi∈U，xi的鄰域離群因子的計(jì)算公式如下：

(6)

定義8 基于鄰域值差異度量的離群點(diǎn)。令μ為給定的離群點(diǎn)判定閾值，對(duì)?x∈U，如果NOF(x)>μ，稱x為U中基于鄰域值差異度量的離群點(diǎn)。

2.2 基于鄰域值差異度量的離群點(diǎn)檢測(cè)算法

基于鄰域和值差異度量概念，本文提出了基于鄰域值差異度量的離群點(diǎn)檢測(cè)(NVDMOD)算法(算法2)。它在單屬性鄰域覆蓋(SANC)(算法1)計(jì)算時(shí)采取有序二分近鄰搜索模式，效率較傳統(tǒng)無(wú)序逐一比較模式有顯著提升。在數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)上，新算法用數(shù)組首行存放U中對(duì)象按屬性cj升序排列的結(jié)果，數(shù)組第二行存放對(duì)象在U中的原始順序號(hào)。

算法1 單屬性鄰域覆蓋(SANC)算法。

輸入：IS=(U,C,V,f)，λ和j，其中|U|=n。

1)

/*初始化*/

2)

N← ?

3)

RankIndex[1..n][1..2] ← Ascend_sort(U)

/*U中對(duì)象按cj升序排列*/

4)

fori=1 tondo

5)

k←i

6)

whilek>0 do

7)

ifHEOM{cj}(RankIndex[i][1],

RankIndex[k][1])≤εcj

8)

k←k-1

9)

else

10)

break

11)

end if

12)

end while

13)

a←k+1

/*a：對(duì)象鄰域的下限順序號(hào)*/

14)

k←i+1

15)

whilek

16)

ifHEOM{cj}(RankIndex[i][1],

RankIndex[k][1])≤εcj

17)

k←k+1

18)

else

19)

break

20)

end if

21)

end while

22)

b←k-1

/*b：對(duì)象鄰域的上限順序號(hào)*/

23)

N←RankIndex[a..b][1]

24)

25)

end for

26)

SANC算法第3)步采用堆排序[16]，第4)～25)步的頻度為n，第6)～12)及15)～21)步的頻度為n，理論時(shí)間復(fù)雜度O(n2)與傳統(tǒng)無(wú)序逐一比較算法相同，但由于SANC算法第3)步進(jìn)行了屬性值的預(yù)排序，計(jì)算對(duì)象的單屬性鄰域時(shí)可以利用該有序性進(jìn)行二分近鄰搜索。由于鄰域中的對(duì)象都分布在鄰近位置，對(duì)給定對(duì)象的鄰域搜索比較次數(shù)會(huì)比n小很多，故SANC算法的實(shí)際計(jì)算復(fù)雜度遠(yuǎn)低于O(n2)。假定對(duì)象屬性的取值等概率均勻分布，此時(shí)ε小，有序二分近鄰搜索的復(fù)雜度將接近O(n)。綜上，SANC算法的實(shí)際時(shí)間復(fù)雜度為O(nlogn)，明顯低于傳統(tǒng)的無(wú)序逐一比較算法。

算法2 基于鄰域值差異度量的離群點(diǎn)檢測(cè)(NVDMOD)算法。

輸入：IS=(U,C,V,f)，閾值μ，λ，其中|U|=n，|C|=m。

輸出：基于鄰域值差異度量的離群點(diǎn)集OS(Outlier Set)。

1)

OS← ?

2)

forj← 1 tomdo

3)

/*由SANC算法計(jì)算*/

4)

end for

5)

fori← 1 tondo

6)

forj← 1 tondo

7)

fork← 1 tomdo

8)

ifi≠j

9)

計(jì)算d{ck}(xi,xj)

/*xi,xj的單屬性距離*/

10)

end if

11)

end for

12)

end for

13)

計(jì)算NVDM(xi,xj)

/*xi,xj的鄰域值差異度量*/

14)

計(jì)算NOF(xi)

/*對(duì)象xi的鄰域離群因子*/

15)

ifNOF(xi)>μ

16)

OS←OS∪{xi}

17)

end if

18)

end for

19)

returnOS

對(duì)于NVDMOD算法，由于SANC算法的復(fù)雜度為O(nlogn)，它重復(fù)m次，同時(shí)，第5)～18)步的頻度為m×n2，因此，NVDMOD算法的時(shí)間復(fù)雜度為O(mn2)，空間復(fù)雜度為O(mn)。

3 實(shí)驗(yàn)結(jié)果及其分析

本章對(duì)NVDMOD算法、鄰域離群點(diǎn)檢測(cè)(NEighborhood outlier Detection, NED)算法[13](鄰域半徑直接給定)、基于距離的離群點(diǎn)檢測(cè)(DIStance-based outlier detection, DIS)方法[6](傳統(tǒng)距離檢測(cè)方法)和K最近鄰(K-Nearest Neighbors,KNN)算法[17](傳統(tǒng)距離檢測(cè)方法)的性能進(jìn)行實(shí)驗(yàn)比較，驗(yàn)證NVDMOD算法的有效性和適應(yīng)性。

3.1 實(shí)驗(yàn)環(huán)境

為測(cè)試NVDMOD算法的有效性，選取Annealing和Wisconsin Breast Cancer兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

首先從UCI機(jī)器學(xué)習(xí)庫(kù)中獲得上述數(shù)據(jù)集[18]。實(shí)驗(yàn)平臺(tái)配置：處理器Intel Core i5- 2400；主頻3.10 GHz；內(nèi)存4 GB；操作系統(tǒng)Windows 7；編程環(huán)境Matlab R2015b。

為增強(qiáng)實(shí)驗(yàn)結(jié)果的可比性，本文采用文獻(xiàn)[19]中的離群點(diǎn)檢測(cè)方法評(píng)價(jià)體系以給定數(shù)據(jù)集上找出的離群點(diǎn)占比衡量算法的有效性。

3.2 Annealing數(shù)據(jù)集

Annealing數(shù)據(jù)集有798個(gè)數(shù)據(jù)對(duì)象、37個(gè)條件屬性和1個(gè)決策屬性。其中，條件屬性包括30個(gè)符號(hào)型和7個(gè)數(shù)值型。數(shù)據(jù)對(duì)象分為5類，類3以外的數(shù)據(jù)對(duì)象均為離群點(diǎn)，共190個(gè)離群點(diǎn)。Annealing鄰域信息系統(tǒng)記為NISA，鄰域半徑參數(shù)λA=0.2。4種算法的實(shí)驗(yàn)結(jié)果如表1所示。

表1 鄰域信息系統(tǒng)NISA上的實(shí)驗(yàn)結(jié)果

其中：離群程度前k%的對(duì)象(對(duì)象數(shù))是指將數(shù)據(jù)對(duì)象按離群程度值由高到低排序后，用于對(duì)比分析的對(duì)象子集比例(前k%)及其對(duì)象數(shù)；屬于離群點(diǎn)的對(duì)象數(shù)是指離群度前k%的對(duì)象中屬于離群點(diǎn)的對(duì)象數(shù)；覆蓋率是指屬于離群點(diǎn)對(duì)象數(shù)占離群點(diǎn)總數(shù)的比例。

Annealing數(shù)據(jù)集是混合型屬性數(shù)據(jù)集。由表1可見(jiàn)，NVDMOD算法準(zhǔn)確率明顯高于其他3種算法，如離群程度前10.03%的80個(gè)數(shù)據(jù)對(duì)象中，它能檢測(cè)出64個(gè)離群點(diǎn)，而NED、KNN和DIS算法只分別檢測(cè)出了51、33和21個(gè)。由此可見(jiàn)，NVDMOD算法適用于混合型數(shù)據(jù)集，且優(yōu)于其他算法。

圖1 離群點(diǎn)數(shù)隨λA變化的折線圖(離群程度前10.03%)

離群程度前10.03%的對(duì)象中，NVDMOD算法檢測(cè)出的離群點(diǎn)數(shù)隨λA變化如圖1所示，當(dāng)λA=0.2時(shí)效果最好。0<λA≤2時(shí)，NVDMOD算法總體優(yōu)于其他3種算法，而其余情形時(shí)優(yōu)于DIS和KNN算法，接近NED算法。

3.3 Wisconsin Breast Cancer 數(shù)據(jù)集

Wisconsin Breast Cancer數(shù)據(jù)集有699個(gè)對(duì)象，分成 benign(65.5%)和malignant(34.5%)兩類，對(duì)象的描述由9個(gè)數(shù)值型屬性完成。為形成不均勻分布數(shù)據(jù)集，仿照Harkins等提出的方法[20]移去了一些屬于malignant類的對(duì)象，最終的數(shù)據(jù)集包含了483個(gè)對(duì)象，其中39個(gè)屬于malignant類。

將malignant類作為離群點(diǎn)，數(shù)據(jù)集的鄰域信息系統(tǒng)記為NISW，鄰域半徑參數(shù)λW=0.4。在NISW上實(shí)驗(yàn)結(jié)果如表2所示。

表2 鄰域信息系統(tǒng)NISW上的實(shí)驗(yàn)結(jié)果

從表2可知，在Wisconsin Breast Cancer數(shù)據(jù)集中，NVDMOD算法具有最好性能，通過(guò)對(duì)離群程度前9.94%的48個(gè)數(shù)據(jù)對(duì)象進(jìn)行檢測(cè)，即可檢測(cè)出所有離群點(diǎn)。該數(shù)據(jù)集的9個(gè)屬性全為數(shù)值型屬性。由此可見(jiàn)，NVDMOD算法處理數(shù)值型數(shù)據(jù)對(duì)象問(wèn)題也能取得很好的效果。

離群程度前9.94%的48個(gè)數(shù)據(jù)對(duì)象中，NVDMOD算法檢測(cè)出的離群點(diǎn)數(shù)隨λW變化的規(guī)律如圖2所示，當(dāng)λW=0.4時(shí)效果最好；λW≥0.4時(shí)NVDMOD算法大致具有穩(wěn)定性和優(yōu)化性。

圖2 離群點(diǎn)數(shù)隨λW變化的折線圖(離群程度前9.94%)

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)距離法不能有效處理符號(hào)型屬性和經(jīng)典粗糙集方法不能有效處理數(shù)值型屬性問(wèn)題，通過(guò)歸一化預(yù)處理、HEOM距離選取和具有自適應(yīng)特征的鄰域半徑設(shè)定，本文構(gòu)建了基于鄰域關(guān)系和鄰域類的鄰域信息系統(tǒng)，利用鄰近多數(shù)類的不確定性顆粒性質(zhì)，以對(duì)象鄰域值差異度量為基礎(chǔ)進(jìn)行離群點(diǎn)檢測(cè)，較好地融合和拓展了傳統(tǒng)距離法和粗糙集方法，能夠更有效地處理符號(hào)型、數(shù)值型和混合型屬性數(shù)據(jù)集。實(shí)驗(yàn)結(jié)果表明，所提算法在各類屬性組合情形下都有更好的適應(yīng)能力。本文的研究是針對(duì)鄰域粗糙集方法及其應(yīng)用的拓展。后續(xù)研究中，可以考慮通過(guò)屬性序列和屬性集序列[10]集成離群因子，以提高算法檢測(cè)結(jié)果的有效性和算法效率。另外，還可以考慮將各類屬性取值的離群特征信息融合到對(duì)象的離群度量模型中，進(jìn)一步提高算法效率；以及引入統(tǒng)計(jì)檢驗(yàn)進(jìn)一步分析各算法的性能優(yōu)劣。