亓慧，史穎

(太原師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山西 太原 030619)

0 引言

在粗糙集理論[1-2]的研究發(fā)展過程中,屬性約簡(jiǎn)因其在行為分析、圖像處理、推薦系統(tǒng)等各種實(shí)際問題中的應(yīng)用性,受到了眾多學(xué)者的關(guān)注[3-6]。經(jīng)過深入的分析,在涉及屬性約簡(jiǎn)的具體實(shí)現(xiàn)問題時(shí),基于適應(yīng)度函數(shù)的方法[7]因其時(shí)間高效性而備受青睞,其過程可以大致歸納為:給定一個(gè)適應(yīng)度函數(shù),通過該函數(shù)評(píng)估各個(gè)候選屬性的重要度,依次選出最重要的屬性,直到選出的屬性滿足預(yù)設(shè)的約束條件為止。

然而,大多數(shù)利用適應(yīng)度函數(shù)法求取約簡(jiǎn)的研究工作往往只構(gòu)建或使用單一的適應(yīng)度函數(shù),該策略并不能有效應(yīng)對(duì)實(shí)際應(yīng)用中的各種復(fù)雜問題,譬如,當(dāng)面對(duì)類別不平衡數(shù)據(jù)時(shí),單一的適應(yīng)度函數(shù)在整個(gè)數(shù)據(jù)中籠統(tǒng)地評(píng)估屬性的重要度,武斷而直接,并沒有深度挖掘?qū)傩栽诟鱾€(gè)類別當(dāng)中重要度的差異性,容易導(dǎo)致屬性在小類下重要度被淹沒的情況;當(dāng)面對(duì)數(shù)據(jù)擾動(dòng)問題時(shí),利用單一的適應(yīng)度函數(shù)所求得的約簡(jiǎn)往往不夠全面,無法滿足多層次、多視角以及多粒度[8-10]的需求。

為了解決該問題,Yang和Yao[11]設(shè)計(jì)了一種集成屬性選擇器。不同于以往的屬性約簡(jiǎn)方法,該選擇器通過構(gòu)建多個(gè)適應(yīng)度函數(shù),在每一輪迭代選擇中,利用這些適應(yīng)度函數(shù),對(duì)同一候選屬性進(jìn)行多次評(píng)估,繼而綜合多次評(píng)估結(jié)果,采取集成投票的機(jī)制,選出此次迭代中最重要的屬性。充足的實(shí)驗(yàn)表明,該機(jī)制有利于在數(shù)據(jù)擾動(dòng)、粒度變化等環(huán)境下,提升約簡(jiǎn)結(jié)果以及其相關(guān)分類結(jié)果的穩(wěn)定性。在此研究工作的基礎(chǔ)上,Liu等人[12]將集成屬性選擇器應(yīng)用于半監(jiān)督特征選擇問題中去,顯著地提升了由約簡(jiǎn)所得的分類準(zhǔn)確率;Wang等人[13]將其推廣至在線特征選擇的問題,在提升由約簡(jiǎn)所得分類準(zhǔn)確率的同時(shí),還有效地降低了求取約簡(jiǎn)所需的時(shí)間消耗。需要注意的是,不同的度量可以構(gòu)建不同的適應(yīng)度函數(shù),其相應(yīng)的集成屬性選擇器的性能亦會(huì)有所差異。為了分析這種差異,本文借助鄰域粗糙集模型[14],并分別將局部近似質(zhì)量[11]、局部條件熵[13]以及局部鄰域決策錯(cuò)誤率[12]引入到集成屬性選擇器中,對(duì)其約簡(jiǎn)結(jié)果進(jìn)行了實(shí)驗(yàn)對(duì)比分析。

1 基本知識(shí)

1.1 鄰域粗糙集

在粗糙集理論中,一個(gè)決策系統(tǒng)可以表示為二元組DS=,其中U是一個(gè)非空有限的樣本集合,亦被稱作論域;AT是非空有限的條件屬性集合;d是決策屬性。此外,?x∈U,d(x)表示樣本x的決策屬性值,即類別標(biāo)簽。

根據(jù)決策屬性d,?A?AT,可以定義屬性集合A上的一個(gè)不可分辨關(guān)系為

IND(0c80oso)={(x,y)∈U2:d(x)=d(y)} .

(1)

根據(jù)此不可分辨關(guān)系,可以進(jìn)一步得到論域U上的一個(gè)劃分為

U/IND(mkkkusa)={X1,X2,…,Xq}.

(2)

?Xi∈U/IND(0cgqouc)被稱之為第i個(gè)決策類,特別地,用[x]d來表示包含樣本x的決策類。

定義1[14]給定一個(gè)決策系統(tǒng)DS,非負(fù)的鄰域半徑δ,?A?AT,DS中的鄰域關(guān)系可被定義為

δA={(x,y)∈U2:ΔA(x,y)≤δ},

(3)

其中ΔA(x,y)表示樣本x與y關(guān)于屬性集合A的距離。

相應(yīng)地,?x∈U,其關(guān)于屬性集合A的鄰域?yàn)?/p>

δA(x)={y∈U:ΔA(x,y)≤δ}.

(4)

定義2[14]給定一個(gè)決策系統(tǒng)DS,?A?AT,?Xi∈U/IND(ggu0c8m),Xi關(guān)于A的下近似與上近似就可分別定義為

(5)

(6)

定義3[1]給定一個(gè)決策系統(tǒng)DS,?A?AT,關(guān)于A的近似質(zhì)量可定義為

(7)

其中|X|表示集合X的基數(shù)。

定義4[15]給定一個(gè)決策系統(tǒng)DS,?A?AT,關(guān)于A的條件熵可定義為

(8)

定義5[14]給定一個(gè)決策系統(tǒng)DS,?A?AT,關(guān)于A的鄰域決策錯(cuò)誤率可定義為

(9)

1.2 屬性約簡(jiǎn)

屬性約簡(jiǎn)[15-17]是粗糙集理論中的核心研究?jī)?nèi)容之一。當(dāng)需求發(fā)生變化,屬性約簡(jiǎn)的定義也會(huì)有所不同,以度量近似質(zhì)量與條件熵為例,近似質(zhì)量約簡(jiǎn)[1]的定義為能夠保持或提升近似質(zhì)量的最小屬性子集,而條件熵約簡(jiǎn)[15]的定義則是能夠保持或者降低條件熵的最小屬性子集。鑒于此,通過歸納總結(jié)眾多屬性約簡(jiǎn)的共性,Yao等人[7]給出了屬性約簡(jiǎn)一般形式的定義,具體定義如下所示。

定義6[7]給定一個(gè)決策系統(tǒng)DS,?R?AT,ρ為預(yù)設(shè)的約束條件,R可被視作一個(gè)約簡(jiǎn)當(dāng)且僅當(dāng)

(1)R滿足約束條件ρ;

(2) ?R′?R,R′不滿足約束條件ρ。

需要注意的是,給定不同的度量,定義6中的預(yù)設(shè)約束條件ρ可以有多種不同的形式:當(dāng)選取近似質(zhì)量為度量時(shí),為了盡可能地提升近似質(zhì)量,ρ一般設(shè)置為“γ(A)≥γ(AT)”;當(dāng)選取條件熵為度量時(shí),為了盡可能地降低條件熵,ρ一般設(shè)置為“ε(A)≤ε(AT)”;當(dāng)選取鄰域決策錯(cuò)誤率為度量時(shí),為了盡可能地降低鄰域決策錯(cuò)誤率,ρ一般設(shè)置為“η(A)≤η(AT)”。

根據(jù)定義6,通過引入啟發(fā)式算法,可以給出如算法1所示的求解約簡(jiǎn)算法。

算法1 單一適應(yīng)度函數(shù)的求解約簡(jiǎn)算法 輸入: 決策系統(tǒng)DS,約束條件ρ,適應(yīng)度函數(shù)φ. 輸出: 約簡(jiǎn)R. 步驟1 R←?; Repeat步驟2 (1) ?a∈AT-R,計(jì)算其屬性重要度φ(a);(2) 選擇屬性b滿足φ(b)=max{φ(a):?a∈AT-R};(3) R←R∪;Until R滿足約束條件ρ 步驟3 輸出R.

一般而言,算法1中適應(yīng)度函數(shù)通過計(jì)算加入屬性前后的度量值變化來反映候選屬性的重要度,每次迭代都會(huì)選出重要度最大的屬性,直到選出的屬性滿足約束條件為止?？紤]到度量的性質(zhì)不同,適應(yīng)度函數(shù)的計(jì)算也會(huì)有所區(qū)別,譬如,近似質(zhì)量提升得越大,屬性則越重要,此時(shí)構(gòu)建適應(yīng)度函數(shù)為φ(a)=γ(A∪{a})-γ(A);而條件熵與鄰域決策錯(cuò)誤率降低得越大,屬性越重要,可分別構(gòu)建適應(yīng)度函數(shù)為φ(a)=ε(A)-ε(A∪{a})與φ(a)=η(A)-η(A∪{a})。

2 集成屬性選擇器

算法1通過構(gòu)建單一的適應(yīng)度函數(shù)求解約簡(jiǎn),此類方法對(duì)于屬性評(píng)估與選擇的機(jī)制過于單一武斷,沒有充分權(quán)衡每個(gè)屬性在不同視角下的重要度。譬如,在某次迭代中,某個(gè)屬性在單一的適應(yīng)度函數(shù)評(píng)估下被認(rèn)為是重要的,但當(dāng)數(shù)據(jù)發(fā)生輕微擾動(dòng),造成粒度的變化時(shí),該屬性極有可能就不再重要,最終就容易造成約簡(jiǎn)具備較差的泛化性能。鑒于此,Yang和Yao[11]設(shè)計(jì)了一種集成屬性選擇器,其具體方法如算法2所示。

如算法2所示,多個(gè)適應(yīng)度函數(shù)是集成屬性選擇器明顯區(qū)別于算法1的關(guān)鍵部分。不言而喻,如何構(gòu)建多個(gè)適應(yīng)度函數(shù)就成為了集成屬性選擇器中的核心問題。事實(shí)上,適應(yīng)度函數(shù)通常根據(jù)度量來構(gòu)建,那么多個(gè)度量就可構(gòu)建多個(gè)適應(yīng)度函數(shù)。就目前而言,較為合理的方法是根據(jù)局部度量來構(gòu)建同質(zhì)型的適應(yīng)度函數(shù),常見的局部度量有局部近似質(zhì)量[18],局部條件熵[13]與局部鄰域錯(cuò)誤率[12]。

以下就給出這三種局部度量的具體定義。

定義7[11]給定一個(gè)決策系統(tǒng)DS,?A?AT,A關(guān)于決策類Xi的局部近似質(zhì)量可定義為

(10)

定義8[13]給定一個(gè)決策系統(tǒng)DS,?A?AT,A關(guān)于決策類Xi的局部條件熵可定義為

(11)

定義9[12]給定一個(gè)決策系統(tǒng)DS,?A?AT,A關(guān)于決策類Xi的局部鄰域決策錯(cuò)誤率可定義為

(12)

根據(jù)定義6-8所示的局部度量,不難構(gòu)造相應(yīng)的適應(yīng)度函數(shù),即φi(a)=γ(A∪{a},Xi)-γ(A,Xi),φi(a)=ε(A,Xi)-ε(A∪{a},Xi)以及φi(a)=η(A,Xi)-η(A∪{a},Xi)。顯然,不同于1.2節(jié)所介紹的適應(yīng)度函數(shù),此時(shí)構(gòu)造的適應(yīng)度函數(shù)不再單一,其數(shù)目等同于樣本中決策類的數(shù)目,考慮到現(xiàn)實(shí)數(shù)據(jù)一般具有二類甚至是多類,多個(gè)適應(yīng)度函數(shù)就可以輕而易舉地實(shí)現(xiàn)。

3 實(shí)驗(yàn)對(duì)比

文獻(xiàn)[11-13]已經(jīng)分別對(duì)由不同局部度量構(gòu)建的集成屬性選擇器與算法1進(jìn)行了比較,本文就不再加以贅述。然而,考慮到局部度量的選擇不同,集成屬性選擇器的性能也會(huì)有所差異,孰優(yōu)孰劣還有待進(jìn)一步地分析,故本文就此問題開展了實(shí)驗(yàn)對(duì)比工作。

3.1 數(shù)據(jù)集

本次實(shí)驗(yàn)選取了6組UCI標(biāo)準(zhǔn)數(shù)據(jù)集,其基本信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

3.2 實(shí)驗(yàn)設(shè)置

本次實(shí)驗(yàn)的環(huán)境為PC機(jī),Windows 10操作系統(tǒng),雙核2.60 GHz CPU,16.0 GB內(nèi)存,Matlab R2014a實(shí)驗(yàn)平臺(tái)。

此外,實(shí)驗(yàn)采用了5折交叉驗(yàn)證的方法,即將實(shí)驗(yàn)數(shù)據(jù)集隨機(jī)平均分為5份,每次取其中4份作為訓(xùn)練樣本,剩余1份作為測(cè)試樣本。實(shí)驗(yàn)還選取了10個(gè)半徑δ,值分別為0.03,0.06,…,0.3。在每個(gè)半徑下,利用算法2所示的集成屬性選擇器分別在每份訓(xùn)練樣本上求取局部近似質(zhì)量約簡(jiǎn),局部條件熵約簡(jiǎn)以及局域鄰域決策錯(cuò)誤率約簡(jiǎn)。最后主要對(duì)比選取不同半徑時(shí),在5折交叉驗(yàn)證下由約簡(jiǎn)在測(cè)試樣本上所得的平均分類準(zhǔn)確率。

3.3 實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)選取了兩種分類器,即CART分類器與KNN分類器來對(duì)比不同度量下集成屬性選擇器求得約簡(jiǎn)產(chǎn)生的分類準(zhǔn)確率,其具體結(jié)果如圖1所示。

Fig.1 Comparison among classification accuracies derived by reducts圖1 由約簡(jiǎn)所得分類準(zhǔn)確率的對(duì)比

通過觀察圖1,可以得到以下結(jié)論。

(1) 不管采用CART分類器還是KNN分類器,相比于局部近似質(zhì)量與局部條件熵,由局部鄰域決策錯(cuò)誤率構(gòu)建的集成屬性選擇器求得的約簡(jiǎn)能夠提供更好的分類性能,譬如,在數(shù)據(jù)集Waveform Database Generator (Version 1)上,由局部鄰域決策錯(cuò)誤率約簡(jiǎn)所得的分類準(zhǔn)確率可以穩(wěn)定在0.75以上,而由局部條件熵約簡(jiǎn)所得到的分類準(zhǔn)確率就一直低于0.75,甚至當(dāng)半徑處于0.21至0.30時(shí),分類準(zhǔn)確率已不足0.55,由局部近似質(zhì)量約簡(jiǎn)所得的分類準(zhǔn)確率則在半徑為0.30時(shí)陡降至0.45以下;

(2) 對(duì)于局部條件熵下的集成屬性選擇器而言,采用CART分類器能夠使所選取的約簡(jiǎn)提供更好的分類效果,而對(duì)于局部近似質(zhì)量與局部鄰域決策錯(cuò)誤率下的集成屬性選擇器而言,采用CART分類器與KNN分類器則各有優(yōu)劣,譬如,在數(shù)據(jù)集Page Blocks Classification與Wall-Following Robot Navigation Data上,采用CART分類器能夠使相應(yīng)的約簡(jiǎn)產(chǎn)生更高的分類準(zhǔn)確率,但在數(shù)據(jù)集Statlog(Landsat Satellite)與Wine Quality上,情況就有所不同,顯然是采用KNN分類器能夠使約簡(jiǎn)產(chǎn)生更好的分類結(jié)果。

4 結(jié)論與展望

集成屬性選擇器已經(jīng)被成功地應(yīng)用于半監(jiān)督學(xué)習(xí)、在線學(xué)習(xí)等問題中,為探索不同度量下集成屬性選擇器的性能差異,本文借助鄰域粗糙集,選取了3種常用的局部度量,即局部近似質(zhì)量、局部條件熵以及局部鄰域決策錯(cuò)誤率,分別構(gòu)建了不同的集成屬性選擇器,并對(duì)其約簡(jiǎn)結(jié)果進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果表明,當(dāng)選擇局部鄰域決策錯(cuò)誤率作為度量時(shí),集成屬性選擇器所產(chǎn)生的約簡(jiǎn)能夠提供更高的分類準(zhǔn)確率。

在該對(duì)比工作的基礎(chǔ)上,下一步將討論集成屬性選擇器在其他粗糙集模型下的性能差異,同時(shí)亦可考慮集成屬性選擇器在多粒度環(huán)境下的加速或優(yōu)化,以擴(kuò)展該選擇器的應(yīng)用范圍。