張艷芹，竇慧莉

（1.徐州工程學院 經(jīng)濟學院，江蘇 徐州 221008；2.江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

基于鄰域分類AUC的屬性選擇方法＊

張艷芹1，竇慧莉2

（1.徐州工程學院 經(jīng)濟學院，江蘇 徐州 221008；2.江蘇科技大學 計算機科學與工程學院，江蘇 鎮(zhèn)江 212003）

為了提升鄰域分類器的分類性能，提出了一種利用鄰域AUC作為分類性能度量指標的啟發(fā)式屬性選擇算法。首先，利用鄰域分類器得到鄰域AUC，然后在此基礎上，借助貪心搜索策略，逐步加入使得鄰域AUC盡可能大的屬性，當鄰域AUC不再增大時，算法終止。7個UCI數(shù)據(jù)集上的實驗結(jié)果表明，使用鄰域AUC屬性選擇算法，可以在使用較少屬性個數(shù)的基礎上有效提升鄰域分類器的分類性能。

屬性選擇；啟發(fā)式算法；鄰域分類器；AUC指標

1 背景闡述

不同于經(jīng)典粗糙集[1]方法，鄰域粗糙集[2]借助機器學習中的距離概念，構(gòu)建樣本的鄰域，進而達到刻畫數(shù)據(jù)中不確定性的目的。近年來，鄰域粗糙集方法因其對數(shù)據(jù)的適應性強、粒度變化較為靈活等優(yōu)勢受到了眾多學者的關(guān)注[3-6]。

在鄰域粗糙集理論中，除了可以使用鄰域粗糙集刻畫不確定性以外，借鑒K近鄰[7]的思想，Hu等人提出了鄰域分類器[8]。與K近鄰分類器不同，鄰域分類器不再指定待分類樣本的鄰居個數(shù)，而是通過指定半徑，自然地得到待分類樣本的鄰居，即不同的樣本可能包含不同個數(shù)的鄰居，這是鄰域分類器與K近鄰分類器最重要的差別。除此之外，鄰域分類器利用半徑這一工具，能夠自然地形成一個基于多粒度思想的分類結(jié)果，也就是說，隨著鄰域半徑的不同，鄰域分類器的分類結(jié)果自然也不相同。眾所周知，影響分類器分類性能的因素除了分類器自身的分類能力以外，數(shù)據(jù)中的屬性也是一個重要的因素。在現(xiàn)代數(shù)據(jù)中，往往存在著大量的冗余屬性，如何從原始數(shù)據(jù)中刪除影響分類器分類性能的冗余屬性，以達到提升分類器性能這一目標已然成為了機器學習中一個重要的研究問題。鑒于此，筆者利用鄰域分類器的AUC指標，提出了一種能夠提升鄰域分類AUC的屬性選擇算法。該算法與粗糙集理論中的屬性約簡算法有所不同，因為該算法的目標是提升鄰域分類器的分類性能，而非保持粗糙集理論中的不確定性刻畫能力不變。

本文的主要內(nèi)容是：第二節(jié)簡要介紹鄰域粗糙集、鄰域分類器和鄰域分類AUC；第三節(jié)設計了一種能夠提升鄰域分類AUC的啟發(fā)式算法，進行屬性選擇；第四節(jié)進行實驗分析；第五節(jié)總結(jié)全文。

2 鄰域分類器

對于分類任務來說，一個數(shù)據(jù)集或者決策系統(tǒng)可以用一個二元組進行描述，記為在S中，U表示論域，是所有樣本構(gòu)成的非空有限集合；AT是所有屬性構(gòu)成的非空有限集合；d是標記屬性。

Pawlak粗糙集利用條件屬性集合AT上的不可分辨關(guān)系生成等價類，對目標概念進行近似逼近。不同于Pawlak的經(jīng)典粗糙集，鄰域粗糙集借助距離的概念，構(gòu)建樣本之間的相似度矩陣，進行分類分析。在S中，對于任意的x，y∈U，表示對象x與y之間的距離。給定鄰域半徑為σ，不難構(gòu)建的0-1函數(shù)：“△（x，y）＝1當且僅當?（x，y）≤σ，否則△（x，y）＝0.”

利用0-1函數(shù)△（x，y），對于任意的樣本x∈U，x的鄰域記為表示所有與x之間的距離小于半徑σ的樣本所構(gòu)成的集合。

定義1[4]給定，對于任意的X的鄰域下近似與上近似分別定義為：

在鄰域粗糙集理論中，鄰域分類器是一個重要的研究方向。一個鄰域分類器的分類過程為：對于待分類樣本x，首先記錄x的鄰域σA（x）中所有樣本的標記，其次利用多數(shù)決原則，預測對象x的類別，記為Pre（x），即將鄰域σA（x）中所有樣本的標記出現(xiàn)次數(shù)最多的那一標記作為待分類樣本x的預測標記。以二分類問題為例，ROC曲線是基于樣本的真實類別和預測概率畫出的。ROC曲線的縱坐標是真正例率，即TPR＝被正確分類的正類樣本個數(shù)/所有正類樣本個數(shù)，ROC曲線的橫坐標是假正類率，即FPR＝被錯誤分類的負類樣本個數(shù)/所有負類樣本個數(shù)。而AUC則是ROC曲線下的面積，常?？梢杂脕碓u價一個分類器的優(yōu)劣。

傳統(tǒng)的AUC度量是針對二分類問題設計的，對于多類問題來說，文獻[9]中給出了一種基于類別概率的AUC計算方式，形如：式（1）中：m為類別的個數(shù)；AUCi為第i類樣本的AUC值；Pi為第i類樣本在數(shù)據(jù)中出現(xiàn)的比例。

這種計算方式借鑒了一對多的基本思想，即將多類問題轉(zhuǎn)換為多個二類問題。

3 屬性選擇

屬性約簡或?qū)傩赃x擇是粗糙集理論的核心研究內(nèi)容。在分類學習任務中，通過屬性選擇可以有效地刪除對于分類任務重要度不高的屬性，提升學習器的泛化能力。因此，借助AUC這一度量指標，可以定義以下屬性選擇。

從定義2中可以看出，鄰域分類AUC屬性選擇實際上是期望找出一個屬性子集，它是一個使得鄰域分類AUC能夠被提升的最小屬性子集。下面給出求解這個屬性子集的啟發(fā)式算法。給定定義重要度Sig（a，A）用以表示將屬性a加入到條件屬性集A中后鄰域分類AUC的變化情況：Sig（a，A）＝的值越大，表明將屬性a加入到屬性集合A中后，鄰域分類AUC的提升越明顯。如果Sig（a，A）為負值，則表示將屬性a加入到屬性集合A中后，鄰域分類AUC反而有所降低。利用屬性重要度Sig（a，A）不難設計出下面所示的啟發(fā)式算法，用以求解定義2所示的屬性選擇問題。

算法：啟發(fā)式算法求解鄰域分類AUC屬性選擇。

輸入：決策系統(tǒng)S。

輸出：一個選擇出的屬性子集A。

步驟1：在S中計算AUCAT.

步驟3：如果AUCA≥AUCAT，則轉(zhuǎn)步驟4，否則執(zhí)行以下循環(huán)：①對于任意的a∈AT-red，計算屬性a的重要度Sig（a，A）；②找出屬性b，使得b滿足Sig（b，red）＝max{Sig（a，red）：?a∈AT-red}，令 A＝A∪；③計算AUCA.

步驟4：輸出A。

表1 數(shù)據(jù)集信息

4 實驗分析

為了驗證第3節(jié)所示屬性選擇算法的有效性，特選取了7組UCI數(shù)據(jù)集進行實驗分析，這些數(shù)據(jù)信息的基本描述如表1所示。實驗環(huán)境為PC機，雙核2.60 GHz CPU，16 GB內(nèi)存，Windows10操作系統(tǒng)，MATLAB R2010a實驗平臺。

在這組實驗中，使用了4個不同的鄰域半徑σ進行屬性選擇計算，分別為0.1，0.2，0.3和0.4.表2中列出了在這4個不同的半徑下，屬性選擇前后鄰域分類AUC的變化情況。

從表2中可以發(fā)現(xiàn)，在實驗所用的4個半徑下，利用筆者提出的屬性選擇算法，AUC值明顯提升。這表明，經(jīng)過屬性選擇這一過程，鄰域分類器的分類性能有了明顯提升。這一實驗結(jié)果從分類性能的角度驗證了屬性選擇算法的有效性。此外，進一步觀察表2所示的均值可以發(fā)現(xiàn)，無論是否使用屬性選擇，隨著半徑的增大，AUC值都有所降低。這一現(xiàn)象表明，鄰域分類器的分類性能隨著半徑的增大逐漸減弱。表3給出了經(jīng)過屬性選擇算法后所得的屬性個數(shù)。

觀察表3不難發(fā)現(xiàn)，利用屬性選擇算法，鄰域分類器所使用的屬性個數(shù)明顯減少。這表明，利用筆者提出的屬性選擇算法，可以有效地刪除原始數(shù)據(jù)中的冗余屬性，以達到提升鄰域分類器性能的目的。

表2 屬性選擇前后的AUC值

表3 選擇出的屬性個數(shù)

5 結(jié)束語

傳統(tǒng)鄰域粗糙集理論中的屬性約簡問題大多是基于不確定性的角度進行分析和研究的。本文為了從AUC的角度提升鄰域分類器的分類性能，提出了基于鄰域分類AUC提升的屬性選擇算法。這一算法借助基于貪心搜索策略的啟發(fā)式過程，能夠有效地在刪除冗余屬性的基礎上，提升鄰域分類的AUC值。在本文工作的基礎上，筆者下一步將就如何提高屬性選擇算法的效率問題進行深入討論。

［1］Pawlak Z.Rough Sets-Theoretical Aspects of Reasoning about Data［M］.Boston：Kluwer Academic Publishers，1991.

［2］胡清華，于達仁.應用粗糙計算［M］.北京：科學出版社，2012.

［3］段潔，胡清華，張靈均，等.基于鄰域粗糙集的多標記分類特征選擇算法［J］.計算機研究與發(fā)展，2015，52（1）：56-65.

［4］張維，苗奪謙，高燦，等.鄰域粗糙協(xié)同分類模型［J］.計算機研究與發(fā)展，2014，51（8）：1811-1820.

［5］朱鵬飛，胡清華，于達仁.基于隨機化屬性選擇和鄰域覆蓋約簡的集成學習［J］.電子學報，2012，40（2）：273-279.

［6］楊習貝，徐蘇平，戚湧，等.基于多特征空間的粗糙數(shù)據(jù)分析方法［J］.江蘇科技大學學報（自然科學版），2016， 30（4）：370-373.

［7］Wu ХD，Kumar V，Quinlan JR，et al.Top 10 algorithms in data mining［J］.Knowledge and Information Systems，2008，14（1）：1-37.

［8］Hu QH，Yu DR，Хie ZХ.Neighborhood classifiers［J］.Expert Systems with Applications，2008，34（2）：866-876.

［9］Fawcett T.Using rule sets to maximize ROC performance［C］//IEEE International Conference on Data Mining，2001：131-138.

張艷芹（1979—），女，碩士，講師，主要研究方向為智能信息處理。竇慧莉（1980—），女，碩士，助理研究員，主要研究方向為粗糙集理論、粒計算、機器學習。

〔編輯：白潔〕

TP18

A

10.15913/j.cnki.kjycx.2017.24.043

2095-6835（2017）24-0043-03

國家自然科學基金（61572242）；江蘇省高校哲學社會科學基金（2015SJD769）