一種面向混合屬性數(shù)據(jù)的鄰域粒離群點檢測

李 毅，胡建成

(成都信息工程大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，成都 610225)

1 引 言

離群點檢測是數(shù)據(jù)挖掘的重要研究方向之一，其目的是找出數(shù)據(jù)集中行為與其他對象很不相同的對象[1].離群點檢測有很多應(yīng)用，如入侵檢測、信用卡詐騙和醫(yī)學(xué)診斷等[2].因此，對離群點檢測的研究是非常有必要的.

近幾十年來，離群點檢測的研究非常普遍，提出了許多離群點檢測方法.現(xiàn)有的離群點檢測方法主要包括極值分析、概率統(tǒng)計模型、線性模型、基于鄰近性的模型、信息理論模型和高維離群點檢測[2].其中，基于鄰近性的模型主要包括三種方法：1)基于聚類的方法[3]；2)基于距離的方法[4，5]；3)基于密度的方法[6].然而，大多數(shù)基于距離的算法都是利用歐氏距離來設(shè)計的.在實際應(yīng)用中，歐氏距離可能不是檢測分類和混合屬性數(shù)據(jù)離群值的最佳方法.

粗糙集理論(Rough Set Theory，RST)是由Pawlak在1982年提出的[7]，并得到了許多學(xué)者地不斷改進.它為不充分和不完備分類屬性數(shù)據(jù)的特征選擇、分類規(guī)則學(xué)習(xí)和離群點檢測等提供了形式化的框架.如前所述，大多數(shù)基于距離的方法都使用歐氏距離來計算兩個數(shù)據(jù)對象之間的距離.然而，分類屬性值之間并沒有固有的距離度量，因此不能有效地處理包含分類屬性的數(shù)據(jù).此外，經(jīng)過分析發(fā)現(xiàn)大多數(shù)離群點檢測方法基本上都是用確定性的方式來表示和處理數(shù)據(jù)，沒有考慮數(shù)據(jù)集的不確定性和不完備性.然而，現(xiàn)實生活中采集的數(shù)據(jù)集中存在大量的不確定性和不完備性數(shù)據(jù).基于這些原因，提出了多種基于粗糙集的檢測方法[8-12].例如，Chen等人以粗糙集為基本框架提出了一種基于粒計算(Granular Computing，GrC)的檢測方法[8].該方法基于等價關(guān)系和等價類建立數(shù)學(xué)模型，其檢測模型只適用于分類屬性而不是數(shù)值屬性數(shù)據(jù)集.這些檢測模型在處理數(shù)值屬性數(shù)據(jù)時，需要離散化處理，從而提高數(shù)據(jù)處理所用時間，并伴隨著明顯的信息丟失，因此影響檢測的準(zhǔn)確性.此外，為處理數(shù)值和混合屬性數(shù)據(jù)，Hu等人提出了一種鄰域粗糙集模型，并在此基礎(chǔ)上提出了特征選擇算法[13].鄰域粗糙集是一種強大的數(shù)據(jù)挖掘工具，用于數(shù)值和混合屬性特征選擇、分類和不確定性推理等[13，14].然而，近年來鄰域粗糙集模型中混合屬性離群點檢測的報道較少[15-18].

基于這些討論，本文在鄰域粗糙集的基礎(chǔ)上，構(gòu)造了一種基于鄰域粒的混合屬性離群點檢測方法.首先，該方法優(yōu)選混合鄰域距離度量和統(tǒng)計值的鄰域半徑以構(gòu)建鄰域信息系統(tǒng).其次，定義粒離群程度和離群因子來分別表征鄰域粒和對象的離群性，并設(shè)計了相關(guān)的基于鄰域粒的離群點檢測(Neighborhood Granule-based Outlier Detection，NGOD)算法.對比實驗結(jié)果表明，該方法比現(xiàn)有的離群檢測方法具有更好的適應(yīng)性和有效性.它可以應(yīng)用于三種數(shù)據(jù)，包括分類、數(shù)值和混合屬性數(shù)據(jù).

2 預(yù)備知識

在本節(jié)中，將介紹鄰域粗糙集[13]中的一些基本概念.

定義 1[13].給定任意的xi∈U和B?C，特征空間B中xi的鄰域δB(xi)定義為：

δB(xi)={xj|xj∈U,ΔB(xi,xj)≤ε}

(1)

其中，ε是鄰域半徑，ΔB(xi,xj)是一個關(guān)聯(lián)于B的距離函數(shù).對?xi,xj,xk∈U,ΔB(xi,xj)滿足：

1)ΔB(xi，xj)≥0?xi=xj，ΔB(xi，xj)=0；

2)ΔB(xi，xj)=ΔB(xj，xi)；

3)ΔB(xi，xk)≤ΔB(xi，xj)+ΔB(xj，xk).

模式識別中有多種距離函數(shù).如閔可夫斯基距離(包括曼哈頓距離、歐式距離和切比雪夫距離)、混合歐式重疊度量和值差異度量等[19].例如，關(guān)于C的混合歐式重疊度量(Heterogeneous Euclidean Overlap Metric，HEOM)函數(shù)定義為：

(2)

其中：

其中ωcj是屬性cj的權(quán)重，maxcj和mincj分別表示屬性cj的最大值和最小值.

δB(xi)是以對象xi為中心的鄰域粒，鄰域大小取決于閾值ε，如果ε取較大值，則更多的對象落在xi的鄰域內(nèi).

通過以上討論，可以看到影響鄰域的主要因素有兩個：一個是所使用距離函數(shù)，另一個是閾值ε.第一個決定了鄰域的形狀，而閾值ε控制著鄰域粒的大小.此外，還可以看到，如果讓ε=0，鄰域粒退化為等價類.在這種情況下，相同鄰域粒中的樣本是等價的，鄰域粗糙集模型退化為Pawlak粗糙集.因此，鄰域粗糙集是Pawlak粗糙集的自然推廣.

顯然，鄰域關(guān)系是一類相似關(guān)系，它滿足自反和對稱的性質(zhì).鄰域關(guān)系將對象匯集到一起，以距離表示相似性或不可分辨性，同一鄰域粒內(nèi)的樣本彼此接近.

鄰域粒族{δB(xi)|xi∈U}形成了一個基本粒系，它覆蓋了論域，而不是將論域劃分開來.我們有：

1)?xi∈U;δ(xi)??;

3 基于鄰域粒的混合屬性離群點檢測

在本節(jié)中，首先建立了相關(guān)的檢測系統(tǒng)，其次構(gòu)建了離群點檢測模型，最后設(shè)計了相應(yīng)的檢測算法.

3.1 檢測系統(tǒng)

在本小節(jié)中，構(gòu)建了一個用于離群點檢測的鄰域信息系統(tǒng)，主要包括歸一化預(yù)處理、鄰域距離度量的選取和鄰域半徑的標(biāo)準(zhǔn)設(shè)置.

鄰域粗糙集中的數(shù)據(jù)處理通常存在大小和維數(shù)的差異.為了獲得準(zhǔn)確的數(shù)據(jù)處理結(jié)果，在數(shù)據(jù)處理前對原始的數(shù)值屬性數(shù)據(jù)進行歸一化處理.本文具體采用以下公式形式的最小-最大歸一化方法：

(3)

顯然，歸一化后，這些數(shù)值屬性的屬性值范圍為[0，1].

為了有效地處理數(shù)值和混合屬性數(shù)據(jù)集，本文重新定義HEOM度量如下.

定義 2.對任意x，y∈U，x與y關(guān)聯(lián)于B的混合歐式重疊度量定義為：

(4)

其中：

現(xiàn)實生活中的大多數(shù)數(shù)據(jù)都是混合的.從以上定義可以看出，HEOM不僅可以處理數(shù)值數(shù)據(jù)，還可以同時處理數(shù)值和分類屬性組合的混合數(shù)據(jù).因此，本文采用HEOM度量作為鄰域距離度量.

數(shù)據(jù)對象的鄰域獲取涉及到鄰域半徑，鄰域半徑通常由專家根據(jù)經(jīng)驗確定[13，15].例如，如果采用文獻[15]中鄰域半徑的設(shè)置方法，所涉及的參數(shù)將與屬性數(shù)m相同.顯然，它是主觀的和隨機的，這導(dǎo)致了算法對參數(shù)選擇的敏感性.此外，降低算法對專家指定參數(shù)的敏感性是提高算法精度的客觀依據(jù).因此，對象x相對于屬性cj的鄰域半徑設(shè)為[16]：

(5)

1https：//github.com/BElloney/Outlier-detection

其中std(cj)表示數(shù)值屬性值的標(biāo)準(zhǔn)差，λ是半徑調(diào)整的給定參數(shù).

3.2 檢測模型

為了計算粒之間的距離，文獻[8]定義了重疊距離度量.同理，為了能有效處理數(shù)值和混合屬性數(shù)據(jù)，在鄰域粗糙集的鄰域重疊度量(Neighborhood Overlap Metric，NOM)定義如下.

定義 3.給定一個信息系統(tǒng)IS.對x，y∈U，對象x與y之間的鄰域重疊度量定義為：

NOM(x，y)=|{cj∈C|y?δ{cj}(x)}|

(6)

定義 4.對ngi，ngj∈NGB，鄰域粒ngi與ngj的距離定義為：

(7)

對于任何對象xi∈U，大多數(shù)當(dāng)前離群點檢測方法僅給出xi的二進制分類，即xi是或不是離群點[6].但是，在許多情況下，為xi指定一個離群因子更有意義.在下文中，定義了兩個概念：“粒離群度(GOD)”和“基于鄰域粒的離群因子(NGOF)”，其中前者量化給定鄰域粒的離群特性，后者表示給定的對象離群特性.

定義 5.對ngi∈NGB，ngi的鄰域粒離群度為：

(8)

定義 6.對于任何對象xi∈U，xi的基于鄰域粒的離群因子定義為：

(9)

權(quán)重函數(shù)W{cj}符合這樣的觀點，即離群點檢測總是涉及數(shù)據(jù)集中的少數(shù)對象，并且這些對象更可能是離群點.從公式(9)中可以看出，權(quán)重越高，基于鄰域粒的離群因子越大，因此，對于?xi∈U和cj∈C，如果鄰域粒δ{cj}(xi)的基數(shù)小于其他鄰域粒的基數(shù)，那么將xi視為屬于U中的少數(shù)對象，并為xi賦予高權(quán)重.如果xi的離群因子越高，那么xi越可能是離群點.

定義 7.設(shè)μ是一個給定的閾值，對任意xi∈U，如果NGOF(xi)>μ，則把xi稱為基于鄰域粒的離群點.

3.3 檢測算法

算法1.基于鄰域粒的離群點檢測算法(NGOD)

輸入：信息系統(tǒng)IS=(U，C，V，f)，閾值μ

輸出：離群點集(Outlier Set，OS)

1.OS←?

2.對任意x，y∈U，計算NOM(x，y)

3.forj←1tomdo

4. 計算鄰域粒族{δ{cj}(xi)|xi∈U}

5. 構(gòu)建NG{cj}={ng1，ng2，…，ngk}

6.endfor

7.forj←1tomdo

8.fori←1tokdo

9.forr←1tokdo

10. 計算M(ngi，ngr)

11.endfor

12.endfor

13.endfor

14.fori←1tondo

15.forj←1tomdo

16. 計算GOD(δ{cj}(xi))

17. 計算W{cj}(x)

18.endfor

19. 計算NGOF(xi)

20.ifNGOF(xi)>μthen

21.OS←OS∪{xi}

22.endif

23.endfor

24.returnOS

算法1通過 “for”循環(huán)的獲得離群點集，步驟(2)的頻度為n×n，步驟(3)-步驟(6)的頻度為m，步驟(4)的頻度為n×n，步驟(7)-步驟(13)的頻度為m，步驟(8)-步驟(12)的頻度為k，步驟(9)-步驟(11)的頻度為k，步驟(14)-步驟(23)的頻度為n，步驟(15)-步驟(18)的頻度為m.從而，算法1總的頻度為n×n+m×n×n+m×k×k+m×n.因此，在最壞的情況下，算法1的時間復(fù)雜度為O(mn2)，空間復(fù)雜度為O(mn).

4 數(shù)據(jù)實驗

在本節(jié)中，為了評估NGOD算法的有效性，選取了三個數(shù)據(jù)集(包括數(shù)值、分類和混合屬性)進行實驗[21].為了形成一個非常不平衡的分布，本文使用文獻[3，8]中的實驗技術(shù)對數(shù)據(jù)集進行預(yù)處理，最后的數(shù)據(jù)預(yù)處理和描述如表1所示1.在三個數(shù)據(jù)集上，本文比較了NGOD算法與GrC、FindCBLOF、LOF、DIS和KNN算法的性能.如表2所示，描述了六種比較算法及其優(yōu)缺點.

4.1 實驗設(shè)置

在實驗中，對于GrC算法，使用重疊距離量度來計算兩個粒之間的距離，對于Cr數(shù)據(jù)集，GrC算法需要的參數(shù)d為|C|/4，另外兩個數(shù)據(jù)集的實驗結(jié)果參考文獻[8].本文對三個數(shù)據(jù)集重復(fù)LOF和KNN算法，分別計算其參數(shù)MinPts和K在1～n范圍內(nèi)的最優(yōu)參數(shù).對于LOF算法，Cr，Ly和Wi數(shù)據(jù)集的最優(yōu)參數(shù)MinPts分別設(shè)置為：197、36和15.對于KNN算法，Cr、Ly和Wi數(shù)據(jù)集的最優(yōu)參數(shù)K分別設(shè)置為：33、27和39.對于Cr數(shù)據(jù)集，F(xiàn)indCBLOF算法所需的三個參數(shù)α、β和s分別設(shè)置為90%、5和5，而對于Ly和Wi數(shù)據(jù)集的實驗結(jié)果參考文獻[3].此外，對于所有基于粗糙集的方法，Ly和Wi數(shù)據(jù)集中的所有屬性值均被認為是分類類型[3，8].

表1 最終數(shù)據(jù)的預(yù)處理和描述
Table 1 Final data preprocessing and description

數(shù)據(jù)集縮寫預(yù)處理對象數(shù)數(shù)值屬性分類屬性離群點數(shù)正常點數(shù)Credit ApprovalCr忽略有一個或多個缺失值的37個對象,然后從剩余的653個對象中刪除271 “+”個對象,類“+”被看作離群點.3826925357LymphographyLy類“1”和“4”被看作離群點.1483156142Wisconsin Breast CancerWi刪除202個“malignant”對象和14個“benign”對象,“malignant”類被看作離群點.4839039444

表2 六種比較算法的優(yōu)缺點
Table 2 Advantages and disadvantages of six comparison algorithms

算法(參考文獻)策略優(yōu) 點缺 點NGOD(本文)基于鄰域粒的最優(yōu)的混合距離度量和合理的半徑設(shè)置,鄰域粒的不確定性,適用于分類、數(shù)值和混合屬性數(shù)據(jù).需要計算更多的鄰域關(guān)系,只考慮單個屬性的信息.GrC(文獻[7])基于粒計算的?；芰?適用于分類屬性數(shù)據(jù).數(shù)值數(shù)據(jù)需離散化預(yù)處理,不適用于數(shù)值屬性數(shù)據(jù).FindCBLOF(文獻[3])基于聚類的與經(jīng)典聚類相結(jié)合,適用于分類屬性數(shù)據(jù).檢測效果差,不適用于數(shù)值屬性數(shù)據(jù).LOF(文獻[5])基于密度的適用于數(shù)值屬性數(shù)據(jù).不適用于分類屬性數(shù)據(jù).DIS(文獻[4])基于距離的簡單且適用于數(shù)值屬性數(shù)據(jù).不適用于分類屬性數(shù)據(jù).KNN(文獻[20])K-近鄰適用于數(shù)值屬性數(shù)據(jù).不適用于分類屬性數(shù)據(jù).

4.2 實驗評估

對于所有的算法，通過Aggarwal和Yu引入的評估方法來評估它們的性能[5].它主要包括“頂比率(對象數(shù))”和“屬于離群點的個數(shù)(覆蓋率)”.首先，六種離群點檢測算法被用來計算每個對象的離群因子.然后，所有對象通過離群因子升序排列，令OStopk(U)表示U中排序前k個對象的集合，OStrue(U)表示在U中真實離群點的集合.所以，對于每個算法，對象數(shù)等于|OStopk(U)|，屬于離群點的個數(shù)等于|OStopk(U)∩OStrue(U)|.而頂比率(Top Ratio，TR)和覆蓋率(Coverage Ratio，CR)計算如下：

(10)

(11)

顯然，當(dāng)TR(k)一定時，CR(k)越大，算法的性能越好.使用這個方法，NGOD算法的參數(shù)僅需λ.

4.3 實驗結(jié)果分析

三個數(shù)據(jù)集的所有數(shù)據(jù)都分別被導(dǎo)入信息系統(tǒng)ISCr，ISLy和ISWi.則有：|UCr|=382，OStrue(UCr)=25;|ULy|=148，OStrue(ULy)=6;|UWi|=382，OStrue(UWi)=39.對于NGOD算法，ISCr，ISLy和ISWi的參數(shù)分別設(shè)為λCi=0.8，λLy=0.2，λWi=1.4.實驗結(jié)果如表3～表5所示.

表3ISCr中的對比實驗結(jié)果
Table 3 Comparative experimental results inISCr

k(TR(k)(\%))|OStopk(UCr)∩OStrue(UCr)|(CR(t)(\%))NGODGrCFindCBLOFLOFDISKNN25(6.54)18(72.00)17(68.00)18(72.00)18(72.00)17(68.00)15(60.00)43(11.26)21(84.00)20(80.00)20(80.00)19(76.00)20(80.00)19(76.00)61(15.97)25(100.00)21(84.00)21(84.00)21(84.00)20(80.00)20(80.00)77(20.16)25(100.00)22(88.00)22(88.00)21(84.00)22(88.00)21(84.00)90(23.56)25(100.00)23(92.00)23(92.00)23(92.00)22(88.00)22(88.00)110(28.80)25(100.00)23(92.00)23(92.00)23(92.00)23(92.00)25(100.00)116(30.37)25(100.00)25(100.00)25(100.00)23(92.00)23(92.00)25(100.00)145(37.96)25(100.00)25(100.00)25(100.00)23(92.00)25(100.00)25(100.00)172(45.03)25(100.00)25(100.00)25(100.00)25(100.00)25(100.00)25(100.00)

由表3可見，對于信息系統(tǒng)ISCr，NGOD算法明顯要好于其他算法.例如，當(dāng)k=61時，NGOD算法能檢測出全部真實離群點，其覆蓋率為100.00%.然而，對于GrC、FindCBLOF、LOF、DIS和KNN算法，其覆蓋率分別為84.00%、84.00%、84.00%、80.00%和80.00%，比NGOD算法低.更多的是Cr數(shù)據(jù)集為混合屬性數(shù)據(jù).因此，我們可以得到NGOD算法適用于混合屬性數(shù)據(jù).

表4ISLy中的對比實驗結(jié)果
Table 4 Comparative experimental results inISLy

k(TR(k)(\%))|OStopk(ULy)∩OStrue(ULy)|(CR(t)(\%))NGODGrCFindCBLOFLOFDISKNN6(4.05)5(83.33)5(83.33)4(66.67)4(66.67)4(66.67)4(66.67)7 (4.73)6(100.00)6(100.00)4(66.67)5(83.33)5(83.33)4(66.67)8(5.41)6(100.00)6(100.00)4(66.67)5(83.33)5(83.33)5(83.33)9(6.08)6(100.00)6(100.00)4(66.67)5(83.33)5(83.33)6(100.00)10(6.76)6(100.00)6(100.00)4(66.67)6(100.00)5(83.33)6(100.00)11(12.22)6(100.00)6(100.00)4(66.67)6(100.00)6(100.00)6(100.00)20(13.51)6(100.00)6(100.00)4(66.67)6(100.00)6(100.00)6(100.00)30(20.27)6(100.00)6(100.00)6(100.00)6(100.00)6(100.00)6(100.00)

表5ISWi中的對比實驗結(jié)果
Table 5 Comparative experimental results inISWi

k(TR(k)(\%))|OStopk(UWi)∩OStrue(UWi)|(CR(t)(\%))NGODGrCFindCBLOFLOFDISKNN8(1.66)8(20.51)7(17.95)7(17.95)8(20.51)8(20.51)8(20.51)16(3.31)15(38.46)14(35.90)14(35.90)16(41.03)16(41.03)16(41.03)24(4.97)23(58.97)21(53.85)21(53.85)24(61.54)24(61.54)24(61.54)32(6.63)30(76.92)28(71.79)27(69.23)30(76.92)31(79.49)30(76.92)40(8.28)36(92.31)32(82.05)32(82.05)35(89.74)35(89.74)35(89.74)44(9.11)38(97.44)35(89.74)35(89.74)36(92.31)38(97.44)36(92.31)49(10.14)39(100.00)37(94.87)36(92.31)39(100.00)38(97.44)38(97.44)50(10.35)39(100.00)37(94.87)37(94.87)39(100.00)38(97.44)39(100.00)52(10.77)39(100.00)38(97.44)38(97.44)39(100.00)39(100.00)39(100.00)54(11.18)39(100.00)38(97.44)38(97.44)39(100.00)39(100.00)39(100.00)56(11.59)39(100.00)39(100.00)38(97.44)39(100.00)39(100.00)39(100.00)64(13.25)39(100.00)39(100.00)39(100.00)39(100.00)39(100.00)39(100.00)

對于表4和表5，可以做同樣的分析，當(dāng)k分別為7和49時，得到NGOD算法同樣優(yōu)于或等于其它算法的結(jié)論.Ly數(shù)據(jù)集的屬性大多數(shù)為符號屬性，而Wi數(shù)據(jù)集的屬性為數(shù)值型屬性.因此，NGOD算法也適用于符號屬性和數(shù)值屬性數(shù)據(jù).

5 結(jié) 論

本文在鄰域粗糙集的框架下提出了一種基于鄰域粒的離群點檢測，并給出了相應(yīng)的檢測算法，該算法充分利用鄰域粗糙集能處理多種數(shù)據(jù)類型的特性，可以在不確定數(shù)據(jù)中挖掘出多樣屬性類型的離群點.最后，通過數(shù)據(jù)實驗對比分析，所提的算法是有效的，能適用于數(shù)值、分類和混合屬性數(shù)據(jù).在未來的研究工作中，還可以采用其他粗糙集模型來構(gòu)建離群點檢測方法，如模糊粗糙集、優(yōu)勢粗糙集等.