基于鄰域分類(lèi)AUC的屬性選擇方法＊

張艷芹，竇慧莉

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

基于鄰域分類(lèi)AUC的屬性選擇方法＊

張艷芹1，竇慧莉2

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

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

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

1 背景闡述

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

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

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

2 鄰域分類(lèi)器

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

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

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

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

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

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

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

3 屬性選擇

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

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

算法：?jiǎn)l(fā)式算法求解鄰域分類(lèi)AUC屬性選擇。

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

輸出：一個(gè)選擇出的屬性子集A。

步驟1：在S中計(jì)算AUCAT.

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

步驟4：輸出A。

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

4 實(shí)驗(yàn)分析

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

在這組實(shí)驗(yàn)中，使用了4個(gè)不同的鄰域半徑σ進(jìn)行屬性選擇計(jì)算，分別為0.1，0.2，0.3和0.4.表2中列出了在這4個(gè)不同的半徑下，屬性選擇前后鄰域分類(lèi)AUC的變化情況。

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

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

表2 屬性選擇前后的AUC值

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

5 結(jié)束語(yǔ)

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

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

［2］胡清華，于達(dá)仁.應(yīng)用粗糙計(jì)算［M］.北京：科學(xué)出版社，2012.

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

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

［5］朱鵬飛，胡清華，于達(dá)仁.基于隨機(jī)化屬性選擇和鄰域覆蓋約簡(jiǎn)的集成學(xué)習(xí)［J］.電子學(xué)報(bào)，2012，40（2）：273-279.

［6］楊習(xí)貝，徐蘇平，戚湧，等.基于多特征空間的粗糙數(shù)據(jù)分析方法［J］.江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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—），女，碩士，講師，主要研究方向?yàn)橹悄苄畔⑻幚?。竇慧莉（1980—），女，碩士，助理研究員，主要研究方向?yàn)榇植诩碚?、粒?jì)算、機(jī)器學(xué)習(xí)。

〔編輯：白潔〕

TP18

A

10.15913/j.cnki.kjycx.2017.24.043

2095-6835（2017）24-0043-03

國(guó)家自然科學(xué)基金（61572242）；江蘇省高校哲學(xué)社會(huì)科學(xué)基金（2015SJD769）