基于鄰域值差異度量的離群點檢測算法

袁 鐘，馮 山

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

0 引言

離群點是數據集中數據對象特征顯著區別于其他數據對象的數據對象[1]，其出現往往隱含或預示具有特殊意義的事件或現象發生。在入侵與欺詐檢測、醫療處理、公共安全等領域，離群點檢測技術具有十分重要的應用[2-4]。

離群點檢測研究最早出現于統計學領域[5]。后來，Knorr等[6-7]將其引入到數據挖掘領域。現有離群點檢測方法主要有三類：1)基于統計[5]；2)基于鄰近性[6-8]；3)基于聚類[9]。其中，基于鄰近性的離群點檢測有基于距離、基于網格和基于密度三種方式。

符號型屬性值是離散的，用傳統距離法檢測符號型屬性數據集的離群點效果并不理想。為此，人們引入了粗糙集下的符號型屬性離群點檢測[10]，但它基于等價關系和等價類建模，用于處理數值型屬性數據集時要先對屬性值離散化，既增加了處理時間，還帶來了明顯的數據信息損失，影響檢測精準度。

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

針對離群點檢測中傳統距離法不能有效處理符號型屬性和經典粗糙集方法不能有效處理數值型屬性的問題，本文以鄰域粗糙集模型為基礎，提出了改進的鄰域值差異度量(Neighborhood Value Difference Metric, NVDM)進行離群點檢測。該方法通過定義鄰域值差異度量來構造表征對象離群程度的鄰域離群因子(Neighborhood Outlier Factor， NOF)，從而，設計并實現了基于鄰域值差異度量的離群點檢測(Neighborhood Value Difference Metric-based Outlier Detection, NVDMOD)算法。所提算法拓展了離群點檢測的傳統距離法和粗糙集法，在計算單屬性鄰域覆蓋(Single Attribute Neighborhood Cover, SANC)時改進了傳統的無序逐一計算模式，使得算法時間復雜度降低到了對數級，明顯優于現有傳統無序逐一比較模式。UCI標準數據集實驗表明，改進算法能有效分析和處理符號型、數值型和混合型屬性數據集的離群點檢測問題，且適應能力更強。

1 鄰域粗糙集

對?x,y,z∈U和B?C，關聯于屬性子集B的距離函數dB:U×U→R+(R+非負實數集)應滿足以下條件：

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

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

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

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

因等價關系和等價類只能處理符號型屬性，可將距離函數和鄰域半徑ε結合并用來對論域U中的數據對象粒化，形成具有相似性特征的鄰域關系和鄰域類，進而構建可同時處理符號型屬性和數值型屬性的鄰域信息系統(Neighborhood Information System, NIS)。

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

(1)

以鄰域信息系統為基礎，可以利用鄰域粗糙性引起的鄰域間的值差異度量對論域中對象之間的差異性或離群性進行度量，從而發現離群點。

2 基于鄰域值差異度量的離群點檢測

2.1 基于鄰域值差異度量的離群點檢測方法

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

(2)

其中:maxcj和mincj為U中對象關于屬性cj的最大取值和最小取值。顯然，標準化屬性取值區間為[0,1]。

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

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

(3)

其中：

dcjh(x,y)=

對象鄰域半徑的設定一般由專家根據經驗確定，具有較強的主觀性和隨機性。減少鄰域構造判定算法對專家所定參數的敏感度，是提升離群點檢測算法準確率的客觀基礎。能夠將數據對象的屬性取值分布信息和專家知識融合的鄰域半徑參數確定法更加合理、有效。為此，本文提出了x在屬性cj上的鄰域半徑設置新方法，它具有很好的自適應特征：

(4)

其中：std(cj)是cj屬性的取值標準差，用于衡量cj的均值分散程度，std(cj)大表示大部分數據對象在cj上的取值與其均值間的差異大，std(cj)小表示數據對象在cj上的取值與均值接近。λ是專家預設的用于調整鄰域半徑大小的參數，λ<1時鄰域半徑應大于屬性值標準差；λ=1時鄰域半徑即屬性值標準差；λ>1時鄰域半徑應小于屬性值標準差。這種主、客觀融合的鄰域半徑調節法兼顧了專家經驗和屬性取值分布特征對對象離群性的影響，為有效的自適應離群點檢測奠定了基礎。

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

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

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

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

(5)

實際上，對象離群程度可用鄰域離群因子度量，可將文獻[13]的鄰域離群因子開平方以加大對象離群程度的變化對其離群特性的正面影響。

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

(6)

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

2.2 基于鄰域值差異度量的離群點檢測算法

基于鄰域和值差異度量概念，本文提出了基于鄰域值差異度量的離群點檢測(NVDMOD)算法(算法2)。它在單屬性鄰域覆蓋(SANC)(算法1)計算時采取有序二分近鄰搜索模式，效率較傳統無序逐一比較模式有顯著提升。在數據結構設計上，新算法用數組首行存放U中對象按屬性cj升序排列的結果，數組第二行存放對象在U中的原始順序號。

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

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

1)

/*初始化*/

2)

N← ?

3)

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

/*U中對象按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：對象鄰域的下限順序號*/

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：對象鄰域的上限順序號*/

23)

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

24)

25)

end for

26)

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

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

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

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

1)

OS← ?

2)

forj← 1 tomdo

3)

/*由SANC算法計算*/

4)

end for

5)

fori← 1 tondo

6)

forj← 1 tondo

7)

fork← 1 tomdo

8)

ifi≠j

9)

計算d{ck}(xi,xj)

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

10)

end if

11)

end for

12)

end for

13)

計算NVDM(xi,xj)

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

14)

計算NOF(xi)

/*對象xi的鄰域離群因子*/

15)

ifNOF(xi)>μ

16)

OS←OS∪{xi}

17)

end if

18)

end for

19)

returnOS

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

3 實驗結果及其分析

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

3.1 實驗環境

為測試NVDMOD算法的有效性，選取Annealing和Wisconsin Breast Cancer兩個數據集進行實驗。

首先從UCI機器學習庫中獲得上述數據集[18]。實驗平臺配置：處理器Intel Core i5- 2400；主頻3.10 GHz；內存4 GB；操作系統Windows 7；編程環境Matlab R2015b。

為增強實驗結果的可比性，本文采用文獻[19]中的離群點檢測方法評價體系以給定數據集上找出的離群點占比衡量算法的有效性。

3.2 Annealing數據集

Annealing數據集有798個數據對象、37個條件屬性和1個決策屬性。其中，條件屬性包括30個符號型和7個數值型。數據對象分為5類，類3以外的數據對象均為離群點，共190個離群點。Annealing鄰域信息系統記為NISA，鄰域半徑參數λA=0.2。4種算法的實驗結果如表1所示。

表1 鄰域信息系統NISA上的實驗結果

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

Annealing數據集是混合型屬性數據集。由表1可見，NVDMOD算法準確率明顯高于其他3種算法，如離群程度前10.03%的80個數據對象中，它能檢測出64個離群點，而NED、KNN和DIS算法只分別檢測出了51、33和21個。由此可見，NVDMOD算法適用于混合型數據集，且優于其他算法。

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

離群程度前10.03%的對象中，NVDMOD算法檢測出的離群點數隨λA變化如圖1所示，當λA=0.2時效果最好。0<λA≤2時，NVDMOD算法總體優于其他3種算法，而其余情形時優于DIS和KNN算法，接近NED算法。

3.3 Wisconsin Breast Cancer 數據集

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

將malignant類作為離群點，數據集的鄰域信息系統記為NISW，鄰域半徑參數λW=0.4。在NISW上實驗結果如表2所示。

表2 鄰域信息系統NISW上的實驗結果

從表2可知，在Wisconsin Breast Cancer數據集中，NVDMOD算法具有最好性能，通過對離群程度前9.94%的48個數據對象進行檢測，即可檢測出所有離群點。該數據集的9個屬性全為數值型屬性。由此可見，NVDMOD算法處理數值型數據對象問題也能取得很好的效果。

離群程度前9.94%的48個數據對象中，NVDMOD算法檢測出的離群點數隨λW變化的規律如圖2所示，當λW=0.4時效果最好；λW≥0.4時NVDMOD算法大致具有穩定性和優化性。

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

4 結語

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