鄰域粗糙集中基于序列的混合型屬性離群點檢測

袁 鐘,張賢勇,馮 山

1(四川師范大學 數學與軟件科學學院,成都 610068)

2(四川師范大學 智能信息與量子信息研究所,成都 610068)

1 引 言

離群點(也稱異常點)是數據集中偏離大部分對象的數據點[1].離群點檢測在欺詐檢測、醫療處理、公共安全、工業損毀檢測、圖象處理、視頻網絡監視以及入侵檢測等諸多領域都具有十分重要的作用[2-4].現有的離群點檢測方法主要有4類:(1) 基于統計的[5];(2) 基于鄰近性的[6-8](包括基于距離的、基于網格和基于密度的);(3) 基于聚類的[9];(4)基于粗糙集的[10].

經典粗糙集方法基于等價關系和等價類,其檢測模型僅適用于符號型屬性而非數值型屬性數據集.這類方法對數值型屬性數據集處理時必須進行符號化處理,從而增加數據處理時間,并伴有影響檢測精度的信息損失.

為了處理數值型屬性數據,文[11]提出鄰域粗糙集的概念.但是,目前在鄰域粗糙集模型中對于離群點檢測的研究還很少[12,13].本文將回顧鄰域和鄰域粗糙集的基本概念,提出基于序列的混合型屬性離群點檢測方法.該方法通過每個屬性值的均勻性來構建屬性序列,以此定義屬性集序列并定義鄰域類序列.進一步通過分析鄰域類序列中對象的變化情況來檢測離群點,并設計出相應的離群點檢測算法(Sequence-based Mixed Attribute Outlier Detection,SMAOD).所建方法拓展了傳統粗糙集方法,同時適用于符號型、數值型和混合型屬性數據集.在UCI標準數據集上與主要的一些離群點檢測方法進行了實驗比較分析,結果表明所提出的方法具有更好的適應性和有效性.

2 鄰域粗糙集

對?x,y,z∈U.關聯于B的距離函數dB:U×U→R+(R+是非負實數集)應滿足:

(1)dB(x,y)≥0(非負性);

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

(3)dB(x,z)≤dB(x,y)+dB(y,z)(三角不等式).

對于B={ci1,ci2,…,cik},1≤k≤m,dB的閔可夫斯基距離表示為:

基于距離度量,可引入鄰域半徑ε來粒化論域U,形成鄰域關系及鄰域類,以便構建鄰域信息系統.

定義1[14].(鄰域)對?x∈U和ε≥0,x在屬性集B上的ε-鄰域定義為:

(1)

3 基于序列的混合型屬性離群點檢測方法

在文獻[10]中,給定一個信息系統,為條件屬性集的每個屬性指派一個均勻性,并且通過每次從條件屬性集中去掉均勻性最大的那個屬性,來觀察U中每個對象所屬的等價類的變化情況,進而構建序列離群因子來表征每個數據對象的離群程度.但是,該方法主要基于等價關系和等價類來建模,其檢測模型適用于符號型屬性而非數值型屬性數據集.對此,本節在文獻[10]基礎上進行有效拓展,主要采用鄰域粗糙集的鄰域關系和鄰域類來建模,相關結果廣泛適用于符號型、數值型和混合型屬性數據集.

利用鄰域粗糙集數據處理時,數據對象的描述通常會存在量級和量綱的差異.為得到精確的數據處理結果,避免不同數據之間的影響,要先對原始數值型屬性值進行歸一化處理[15],本文采用最小-最大標準化.其計算公式如下:

(2)

其中,maxcj和mincj分別為U中關于屬性cj的最大值和最小值.標準化后,這些屬性的屬性值的范圍為[0,1].

為有效處理數值型和混合型屬性數據集,文[16]提出了混合歐氏重疊度量(HEOM).相仿,可定義如下的混合曼哈頓重疊度量(Heterogeneous Manhattan-Overlap Metric,HMOM).

定義5.(HMOM距離)對象x,y∈U的混合曼哈頓重疊度量HMOMB(x,y)定義為:

(3)

其中,

從上述定義可以看出,HMOM函數不僅可以處理數值型屬性數據集,而且可以處理數值型和符號型屬性相結合的復雜數據集,當部分屬性值未知時也可以使用.因此,本文采用HMOM函數作為鄰域距離,這為應用范圍拓展奠定了基礎.

鄰域涉及鄰域半徑的選取.傳統的鄰域半徑ε一般是專家根據經驗給定.顯然,這樣的處理方法具有主觀性和隨機性,會導致算法的參數選取特敏感.為此,本文將對象x在屬性cj的鄰域半徑設為:

(4)

其中,std(cj)是cj的屬性值標準差,預設參數λ用于調整鄰域大小.這為后續檢測方法的有效性奠定了基礎.

標準差用于衡量數據的均值分散程度.標準差較大表示大部分數據對象值和其均值之間差異較大;標準差較小表示數據對象值較接近均值.因此,標準差可以此作為調整鄰域半徑的一個重要因素.這里,λ的作用是根據標準差調整鄰域大小.當λ<1時,鄰域半徑大于屬性值的標準差;當λ=1時,鄰域的半徑即為屬性值的標準差;當λ>1時,鄰域半徑小于屬性值的標準差.

由此,可基于距離度量計算對象鄰域以得到鄰域關系和鄰域類,從而構建鄰域信息系統.

定義6.(屬性的均勻性)給定λ>0,屬性cj的均勻性Var(cj)定義為:

(5)

關聯于統計方差,Var(cj)衡量對象在屬性cj上的離散程度,揭示了對象內部彼此波動的程度.通過計算出C中每個屬性的均勻性,就可以將C中的所有屬性按照均勻性進行排序,從而得到一個屬性序列.

定義7.(屬性序列)屬性序列S定義為:

(6)

進一步由屬性集C開始,每次從中去除均勻性最大的那個屬性,直到得到一個只包含一個屬性的集.這樣,就可以確定一個屬性集序列.

定義8.(屬性集序列)屬性集序列CS定義為:

CS=

(7)

屬性集序列CS中每個屬性集都可以確定一個鄰域關系,這樣就得到對象x的m個鄰域類.由此,可以構造相應的鄰域類序列.

定義9.(鄰域類序列)對象x的鄰域類序列NS(x)定義為:

(8)

基于上述三種序列的定義,類似于Breunig等的做法[8],下面提出鄰域序列離群因子的概念來表征對象的離群程度.

(9)

定義11.(鄰域序列離群點)給定λ>0,令μ為一個給定的閾值.對于?x∈U,NSOF(x)>μ,則x被稱為U中的一個鄰域序列離群點.

定義10通過鄰域類序列建立了鄰域序列離群因子,用于刻畫對象的離群程度.進而,定義11基于判定閾值,自然進行離群點檢測.

一般情況下,離群點檢測方法只給出了每個對象的離群程度;在使用該方法來檢測離群點之前,用戶應該首先輸入一個經驗值k來表示他們期望的離群點的個數.在定義11所述離群點檢測方法中,參數μ的設置也取決于用戶提供的k值.首先,可以計算每個對象x的離群因子,并把這些對象根據其離群因子從大到小排序;進而,由此設置閾值μ,確保找到k個對象使其離群程度在U中高于其他對象;最后,這k個對象將作為離群點返回給用戶.

4 基于序列的混合型屬性離群點檢測算法SMAOD

基于上述離群點檢測方法,本節提出基于序列的混合型屬性離群點檢測算法(SMAOD)(算法2).特別地,算法2調用了單屬性鄰域覆蓋算法(Single Attribute Neighborhood Covering,SANC)(算法1),而算法1改進了傳統的逐一比較的計算模式.

算法1.計算單屬性鄰域覆蓋SANC

(2)N←φ;

(3) [Rank,Index]←Ascend_sort(U);

/*據屬性cj對U中對象升序排列,其中Rank保存排列結果,Index保存對應的原始順序*/

(4)fori←1 tondo

(5)k←i;

(6)whilek>0do

(7)ifHEOM{cj}(Rank[i],Rank[k])≤εcjthen

(8)k←k-1;

(9)else

(10) break;

(11)endif

(12)endwhile

(13)a←k+1;/*用a記錄對象鄰域的下限序號*/

(14)k←i+1;

(15)whilek

(16)ifHEOM{cj}(Rank[i],Rank[k])≤εcjthen

(17)k←k+1;

(18)else

(19) break;

(20)endif

(21)endwhile

(22)b←k-1;/*用b記錄對象鄰域的上限序號*/

(23)N←Rank[a…b];

(25)endfor

算法1中第3步使用由Williams等人提出的堆排序法[17],它的時間復雜度為O(nlogn),改進了通常的排序時間復雜度O(n2).第4步的頻度為n,第5-24步的頻度為n.所以第4-25步頻度為n×n.因此,在最壞的情況下,SANC算法的時間復雜度為O(n2),與傳統逐一比較算法的時間復雜度一致.但是,由于SANC算法基于排序結果進行鄰域計算,對象的每個屬性的取值等概率分布,則在平均情況下,SANC算法的第4-25步平均比較次數接近n,它遠比傳統的逐一比較計算方法的比較次數n×n低.綜上,SANC算法的實際時間復雜度為O(nlogn),表明算法1優于傳統逐一比較計算模式的時間復雜度O(n2).

算法2.基于序列的混合型屬性離群點檢測算法 SMAOD

輸出:鄰域序列離群點集OS.

(1)OS←φ;

(2)forj←1 tomdo

(4) 計算Var(cj);

(5)endfor

(7)構造屬性集序列CS=;

(8)forj←1 tomdo

(10)endfor

(11)fori←1 tondo

(12) 構造鄰域類序列

(13) 計算W(xi);

(14) 計算NSOF(xi);

(15)ifNSOF(xi)>μthen

(16)OS←OS∪{xi};

(17)endif

(18)endfor

(19)returnOS.

下面分析算法2.由算法1知,第2-5步的頻度為m×n×logn;第8-10步的頻度為m×n2;第11-18步的頻度為n.所以算法2的頻度為m×n×logn+m×n2+n.因此,算法2的時間復雜度為O(mn2),空間復雜度為O(mn).

5 實驗結果與分析

本節主要比較SMAOD算法、NED算法[12]、SEQ算法[10]、基于距離的離群點檢測方法[6]和KNN算法[18]的性能.為了測試SMAOD算法的有效性,這里選取三種UCI數據集[19]進行實驗,它們是:Annealing數據集(混合型屬性)、Wisconsin Breast Cancer數據集(數值型屬性)和Lymphography數據集(多數為符號型屬性).其中,在Annealing數據集上,將比較SMAOD算法、NED算法、基于距離的離群點檢測方法和KNN算法的性能,在Wisconsin Breast Cancer和Lymphography數據集上,將比較SMAOD算法、NED算法、SEQ算法、基于距離的離群點檢測方法和KNN算法的性能.

為了增強實驗結果的可比性,本文采用目前最常用的一種離群點檢測方法評價體系[20]來評測各算法的性能.具體地,給定一個數據集以及數據集中每個對象所屬的類,通過在該數據集上運行該算法,并且計算在由該算法所找出的離群點中,真正的離群點所占比越高,則表明該算法的性能越好.

5.1 Annealing 數據集

Annealing數據集中包含798個對象,37個條件屬性和1個決策屬性.其中條件屬性包括30個符號型屬性和7個數值型屬性.798個對象被分為5類,類3包含最多的對象數,把余下的類看作稀有類,總共190個離群點(即屬于稀有類的對象數).相關的鄰域信息系統記為NISA.對于SMAOD算法,設置λ=0.3(其主要由數據實驗而設定).具體的實驗結果如表1所示.

表1 鄰域信息系統NISA上的實驗結果Table 1 Experimental results in NISA

在表1中,|RUA|表示UA中離群點的個數,“DIS”代表基于距離的離群點檢測方法.對于數據集中每個對象x,分別利用這四種離群點檢測方法來計算x的離群程度值.然后根據每種方法所計算出的數據集中對象的離群程度值,由高到低對數據集中對象進行排序.由此,表1中“離群程度值前k%的對象(對象數)”是指在采用某種離群點檢測方法來計算數據集中對象的離群程度值之后,離群程度值排在前k%的對象以及這些對象的個數;“屬于稀有類的對象數”則是指在由該方法所檢測出的離群程度值排在前k%的對象中屬于稀有類的對象個數;“覆蓋率”是指這些屬于稀有類的對象占數據集中所有離群點的比例.

圖1 鄰域信息系統NISA上的實驗結果折線圖Fig.1 Line chart of experimental results in NISA

表1可見,在Annealing數據集中SMAOD算法具有最好的性能.SMAOD算法的準確率高于其它方法.例如,當離群程度前10.03%(對象數為80),SMAOD算法檢測離群點的數目是60,即由SMAOD算法檢測出的60個對象是Annealing數據集中的離群點,但對NED、DIS和KNN算法分別只檢測出51、33和21個離群點.這說明SMAOD算法在Annealing數據集上的有效性.為了更加形象,這四種算法的實驗結果(表1)也用折線圖描繪于圖1,其更明顯地展現了SMAOD算法優于其它算法.此外,Annealing數據集不僅具有符號型屬性數據,而且還具有連續性數值型屬性數據.因此,實驗結果也表明,SMAOD算法適用于混合型屬性數據集.

5.2 Wisconsin Breast Cancer數據集

Wisconsin Breast Cancer數據集中包含699個對象,9個數值型屬性.所有對象被分成兩類:“benign”(65.5%)和“malignant”(34.5%).為了形成一個非常不均勻的分布,我們仿照Harkins等的做法[21],從該數據集中移去一些屬于“malignant”類的對象.最終的數據集包括483個對象,其中39個對象屬于“malignant”類,444個屬于“benign”類,相關的鄰域信息系統記為NISW.

表2 鄰域信息系統NISW上的實驗結果Table 2 Experimental results in NISW

在最終的Wisconsin Breast Cancer數據集中,將“malignant”類看作離群點.對于SMAOD算法,我們設置λ=2.具體實驗結果如表2和圖2所示.

圖2 鄰域信息系統NISW上的實驗結果折線圖Fig.2 Line chart of experimental results in NISW

從表2和圖2中可以看到,對于Wisconsin Breast Cancer數據集,SMAOD算法的性能比其它的離群點檢測方法的性能好.Wisconsin Breast Cancer數據集9個屬性全為數值型屬性,這說明SMAOD算法在處理全是數值型屬性的數據時也有很好效果.

5.3 Lymphography數據集

Lymphography數據集中包含148對象、18個條件屬性和1個決策屬性,其中條件屬性有3個數值型屬性,15個符號型屬性.所有的對象被決策屬性分成四個類:“normal find”(1.35%)、“metastases”(54.73%)、“malign lymph”(41.22%)和“fibrosis”(2.7%).將“normal find”和“fibrosis”看作離群點,總共有6個離群點(即屬于稀有類的對象數).相關鄰域信息系統記為NISL.對于SMAOD算法,設置λ=0.2.具體實驗結果如表3和圖3所示.

從表3和圖3中可以看到,對于Lymphography數據集,SMAOD算法的性能比其它的離群點檢測方法的性能好.Lymphography數據集多數為符號型屬性,因此SMAOD算法也適用于符號型屬性數據.

表3 鄰域信息系統NISL上的實驗結果Table 3 Experimental results in NISL

圖3 鄰域信息系統NISL上的實驗結果折線圖Fig.3 Line chart of experimental results in NISL

6 結 論

離群點檢測在許多領域中具有重要作用.針對傳統粗糙集的離群點檢測方法難以處理數值型屬性數據的缺陷,提出鄰域粗糙集中基于序列的混合型屬性離群點檢測方法.相關方法采用每個屬性值的均勻性構建屬性序列,以此定義屬性集序列,從而定義鄰域類序列.進一步通過分析鄰域類序列中對象的變化情況來檢測離群點,并設計出相應的離群點算法SMAOD.該方法拓展了傳統粗糙集方法,同時適用于符號型、數值型和混合型屬性數據集.在UCI標準數據集上與現有的一些離群點檢測方法進行了實驗的比較分析,實驗結果表明所提方法具有更好的適應性和有效性.對此,相關的檢測機制主要得益于HMOM混合距離選擇、標準差方差的統計使用、多級序列構造等.由于利用鄰域粗糙集的方法進行離群點檢測的研究還比較少見,本文的工作拓展了鄰域粗糙集在數據挖掘等領域的應用范圍,為混合型屬性離群點檢測提供了一點思路.在未來的工作中,為減少算法運行時間復雜度,可考慮在離群點檢測之前,先對數據集進行屬性約簡或特征選擇.

：

[1] Hawkins D.Identification of outliers [M].London:Chapman and Hall,1980:1-2.

[2] Ge Qing-long,Xue An-rong,Jia Xiao-yan.Relevant subspace based outlier mining [J].Journal of Chinese Computer Systems,2015,36(5):1028-1032.

[3] Yang Jin-hong,Deng Ting-quan.A one-cluster kernel PCM based SVDD method for outlier detection[J].Acta Electronica Sinica,2017,45(4):813-819.

[4] Han J W,Kamber M,Pei J.Data mining:concepts and techniques third edition [M].San Francisco:Morgan Kaufmann,2011:543-583.

[5] Rousseeuw P J,Leroy A M.Robust regression and outlier detection [M].New York:John Wiley & Sons,1987:1-18.

[6] Knorr E,Ng R,Tucakov V.Distance-based outliers:algorithms and applications [J].The VLDB Journal,2000,8(3-4):237-253.

[7] Knorr E,Ng R.A unified notion of outliers:properties and computation [C].In International Conference on Knowledge Discovery & Data Mining,1997:219-222.

[8] Breunig M M,Kriegel H P,Ng R T,et al.LOF:identifying density-based local outliers [C].Proc of the ACM SIGMOD Int Conf on Management of Data,Dallas:ACM Press,2000:93-104.

[9] Jain A K,Murty M N,Flynn P J.Data clustering:a review [J].ACM Computing Surveys,1999,31(3):264-323.

[10] Jiang F,Sui Y F,Cao C G.Some issues about outlier detection in rough set theory [J].Expert Systems with Applications,2009,36(3):4680-4687.

[11] Lin T Y.Neighborhood systems-application to qualitative fuzzy and rough sets [C].Advances in Machine Intelligence and Soft-computing,Durham:Department of Electrical Engineering,1997:132-155.

[12] Chen Y M,Miao D Q,Zhang H Y. Neighborhood outlier detection [J].Expert Systems with Applications,2010,37(12):8745-8749.

[13] Li X J,Rao F.Outlier detection using the information entropy of neighborhood rough sets[J].Journal of Information & Computational Science,2012,12(9):3339-3350.

[14] Hu Q H,Yu D R,Liu J F,et al.Neighborhood rough set based heterogeneous feature subset selection [J].Information Sciences,2008,178(18):3577-3594.

[15] Kennedy R L,Lee Y,Van Roy B,et al.Solving data mining problems through pattern recognition [M].Prentice Hall PTR,1997.

[16] Wilson D R,Martinez T R.Improved heterogeneous distance functions [J].Journal of Artificial Intelligence Research,1997,6(1):1-34.

[17] Williams J.Algorithm 232 (heapsort)[J].Communications of the ACM,1964,7(6):347-348.

[18] Ramaswamy S,Rastogi R,Shim K.Efficient algorithms for mining outliers from large datasets [C].Proc of the 2000 ACM SIGMOD Int Conf on Management of Data,Dallas:ACM Press,2000:427-438.

[19] Bay S D.The UCI KDD repository[DB/OL].http://kdd.ics.uci.edu,2016-05-12.

[20] Aggarwal C C,Yu P S.Outlier detection for high dimensional data [C].In Proc of the 2001 ACM SIGMOD Int Conf on Management of Data,Califomia:ACM Press,2001:37-46.

[21] Harkins S,He H,Williams G,et al.Outlier detection using replicator neural networks [C].Proc of the 4th Int Conf on Data Warehousing and Knowledge Discovery,Aix-en-Provence:Springer-Verlag,2002:170-180.

附中文參考文獻：

[2] 葛清龍,薛安榮,賈小艷.關聯子空間離群點挖掘 [J].小型微型計算機系統,2015,36(5):1028-1032.

[3] 楊金鴻,鄧廷權.一種基于單簇核PCM的SVDD離群點檢測方法[J].電子學報,2017,45(4):813-819.