山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室,太原 030006
山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室,太原 030006
粗糙集理論是一種處理不精確、不確定與不完全數(shù)據(jù)的數(shù)學(xué)工具[1-2],其主要思想是:在保持信息系統(tǒng)分類能力不變的前提下,經(jīng)過(guò)屬性約簡(jiǎn)導(dǎo)出分類或決策規(guī)則。目前,粗糙集理論已經(jīng)被廣泛地應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識(shí)別、故障診斷等領(lǐng)域[3-5]。
特征選擇是指在不改變?cè)继卣骺臻g性質(zhì)的前提下,從原始特征空間中選擇一部分重要的特征,組成一個(gè)新的低維特征空間的過(guò)程。屬性約簡(jiǎn)是在保持原始數(shù)據(jù)的屬性區(qū)分能力不變的前提下,選擇具有最小屬性(特征)數(shù)量的屬性子集的過(guò)程,是一種特定背景下的特征選擇方法。屬性約簡(jiǎn)是粗糙集理論中的核心內(nèi)容之一。
目前,研究者已經(jīng)提出了許多屬性約簡(jiǎn)方法[6-8]。Skowron[6]提出了區(qū)分矩陣屬性約簡(jiǎn)方法,該方法可以得到信息系統(tǒng)的所有約簡(jiǎn),但是這種算法的復(fù)雜度過(guò)高(已經(jīng)被證明為NP-Hard問(wèn)題)。為了提高約簡(jiǎn)算法的效率,許多學(xué)者應(yīng)用啟發(fā)式的搜索策略求解屬性約簡(jiǎn),從而有效地降低約簡(jiǎn)算法的耗時(shí)。Hu和Cercone[7]將相對(duì)正域引入到屬性約簡(jiǎn)中,提出了一種啟發(fā)式屬性約簡(jiǎn)算法。王國(guó)胤等[8-9]將Shannon信息熵用于屬性子集評(píng)價(jià),提出相應(yīng)的啟發(fā)式屬性約簡(jiǎn),該方法的停止條件也是利用Shannon條件熵。梁吉業(yè)等[10-14]將互補(bǔ)熵引入粗糙集理論用于度量信息系統(tǒng)的不確定性,并提出利用互補(bǔ)熵評(píng)價(jià)屬性子集的屬性約簡(jiǎn)算法。
上述啟發(fā)式屬性約簡(jiǎn)方法都是先根據(jù)前向貪婪搜索策略產(chǎn)生候選的屬性子集,然后利用某種度量對(duì)候選屬性子集進(jìn)行評(píng)價(jià),如果某個(gè)屬性子集與原始屬性集的區(qū)分能力相同(即滿足停止條件),則得到屬性約簡(jiǎn),否則重復(fù)前面的過(guò)程直至滿足停止條件(如圖1所示)。這些算法都使用相同的度量作為屬性子集的評(píng)價(jià)指標(biāo)和算法的停止條件。評(píng)價(jià)指標(biāo)決定著算法的收斂方向,而停止條件決定著算法得到的約簡(jiǎn)的性質(zhì),因此這兩者并不必須使用相同的度量。

圖1 屬性約簡(jiǎn)過(guò)程示意圖
根據(jù)上述分析,本文根據(jù)互補(bǔ)熵的隨劃分的變化規(guī)律,分四種情況分析了約簡(jiǎn)過(guò)程中當(dāng)某個(gè)屬性加入屬性子集后,相對(duì)正域和互補(bǔ)條件熵的變化。并提出了一種以互補(bǔ)條件熵為啟發(fā)信息、以相對(duì)正域?yàn)橥V箺l件的屬性約簡(jiǎn)方法,與傳統(tǒng)的以相對(duì)正域?yàn)閱l(fā)信息的正域約簡(jiǎn)算法相比,該算法可以得到屬性數(shù)量更少的約簡(jiǎn),同時(shí)計(jì)算約簡(jiǎn)的時(shí)間消耗也更少。
設(shè)S=(U,A,V,f)為一個(gè)信息系統(tǒng),其中U為非空有限對(duì)象集合,稱為論域;A為非空有限屬性集合;對(duì)任意a∈A有 a:U→Va,其中Va稱為屬性 a 的值域,V=∪a∈AVa,f:U×A=V是一個(gè)函數(shù),對(duì)于任意的a∈A有 f(x,a)∈Va。

稱集合 BNR(Y)=-為Y的 R邊界域;POSR(Y)=為Y的 R正域;NEGR(Y)=U-RY為Y的 R負(fù)域。
若信息系統(tǒng)中的屬性集 A=C∪D,C表示條件屬性集,D表示決策屬性集,C∩D≠,則該信息系統(tǒng)稱為一個(gè)決策表,記為DT=(U,C∪D,V,f)。如果其中條件屬性集C對(duì)論域U的劃分為={X1,X2,…,Xm},決策屬性集D對(duì)論域U的劃分為={Y1,Y2,…,Yn},則 D 關(guān)于C的相對(duì)正域記為POSC。若某個(gè)決策表的決策屬性集關(guān)于條件屬性集的相對(duì)正域?yàn)檎麄€(gè)論域,則稱其為協(xié)調(diào)的決策表,否則稱其為不協(xié)調(diào)的決策表。


基于互補(bǔ)條件熵可以給出屬性a關(guān)于屬性集C重要度 SGF(a,C,D)的定義:

為了給出新的屬性約簡(jiǎn)算法,首先引入下面的定理。
定理1[15]給定決策表 DT=(U,C∪D,V,f),C 是條件屬性集,D是決策屬性集。若U/B?U/C,則

定理1表明隨著論域劃分的變細(xì),決策表的互補(bǔ)條件熵將變小。
定理2[16]給定決策表 DT=(U,C∪D,V,f),C 是條件屬性集,B?C,D是決策屬性集,則

定理2表明互補(bǔ)條件熵不僅與其正域部分的大小有關(guān),還與其非正域部分的互補(bǔ)條件熵的大小有關(guān)。進(jìn)一步結(jié)合定理1的結(jié)論可以得出非正域部分的條件熵的大小與其劃分的粗細(xì)程度有關(guān)。因此,利用互補(bǔ)條件熵作為啟發(fā)式信息,則不但可以反映正域部分大小,也可以反映非正域部分的分布情況(劃分的粗細(xì)程度)。
在屬性約簡(jiǎn)的過(guò)程中,決策屬性關(guān)于當(dāng)前屬性集的非正域部分中對(duì)象將會(huì)成為下一次迭代時(shí)相對(duì)正域中的對(duì)象,如圖2所示,圖中決策屬性關(guān)于屬性集B的非正域中的一些對(duì)象(陰影部分)在條件屬性集為B∪{ai}時(shí)進(jìn)入了相對(duì)正域。因此,決策屬性集關(guān)于某一條件屬性集的非正域中的對(duì)象的分布情況也會(huì)對(duì)約簡(jiǎn)過(guò)程中屬性的選擇產(chǎn)生重要的影響,進(jìn)而影響約簡(jiǎn)算法收斂的方向和速度。

圖2 約簡(jiǎn)過(guò)程中相對(duì)正域和非正域的變化
為了更好地說(shuō)明約簡(jiǎn)過(guò)程中以互補(bǔ)條件熵為啟發(fā)信息和以正域?yàn)閱l(fā)信息的區(qū)別,下面分四種情況來(lái)分析。
不失一般性,不妨設(shè)當(dāng)前屬性子集為B,可選擇加入的屬性有ai和aj。

為了說(shuō)明該情況時(shí)在論域U下互補(bǔ)條件熵的變化情況,給出下面的定理3。
定理3 給定決策表 DT=(U,C∪D,V,f),C 是條件屬性集,D是決策屬性集,B?C。若對(duì)于任意的屬性ai和aj,POSB∪{ai}(D)=POSB∪{aj}(D), 且 U-POSB∪{ai}(D)/(B ∪{ai})?U-POSB∪{aj}(D)/(B∪{aj}),則

證明根據(jù)已知條件(U-POSB∪{ai}(D))/(B∪{ai})?(UPOSB∪{aj}(D))/(B∪{aj})和定理 1,可以得到(D|B ∪{ai})>(D|B∪{aj})。

證畢。
根據(jù)定理3可以得出,在約簡(jiǎn)過(guò)程中當(dāng)兩個(gè)屬性ai和aj分別加入的候選屬性子集B時(shí),如果決策屬性集D關(guān)于B∪{ai}的相對(duì)正域與關(guān)于B∪{aj}的相對(duì)正域大小相等,且屬性B∪{ai}對(duì)非正域部分的劃分比B∪{aj}對(duì)非正域部分的劃分細(xì),則在論域U下,D關(guān)于B∪{ai}的互補(bǔ)條件熵較小。
因此,在約簡(jiǎn)過(guò)程中,出現(xiàn)情況1時(shí),若選擇正域作為啟發(fā)式信息,則屬性ai和aj的重要程度相同,只能任意選擇一個(gè)。而選擇互補(bǔ)條件熵為啟發(fā)信息則可以選擇到對(duì)非正域部分劃分更細(xì)的屬性,為約簡(jiǎn)過(guò)程的下一次迭代奠定更好基礎(chǔ)。

為了說(shuō)明該情況時(shí)在論域U下互補(bǔ)條件熵的變化情況,給出下面的定理4。
定理4 給定決策表 DT=(U,C∪D,V,f),C 是條件屬性集,D是決策屬性集,B?C。若對(duì)于任意的屬性ai和aj,POSB∪{ai}(D)> POSB∪{aj}(D) 且(D|B ∪{ai})=(D|B ∪{aj}),則

類似于定理3,容易證明定理4。
定理4表明在約簡(jiǎn)過(guò)程中當(dāng)兩個(gè)屬性ai和aj分別加入候選屬性子集B時(shí),如果在決策表的非正域部分B∪{ai}關(guān)于決策屬性的互補(bǔ)條件熵與B∪{aj}關(guān)于決策屬性的互補(bǔ)條件熵相等,且在論域U上D關(guān)于B∪{ai}相對(duì)正域比D關(guān)于B∪{aj}相對(duì)正域大,則在論域U上D關(guān)于B∪{ai}關(guān)的互補(bǔ)條件熵較小。
因此,在約簡(jiǎn)過(guò)程中,出現(xiàn)情況2時(shí)利用正域和互補(bǔ)條件熵作為啟發(fā)信息,都會(huì)選擇并入屬性子集B后使得相對(duì)正域更大的屬性ai。

為了說(shuō)明該情況時(shí)在論域U下互補(bǔ)條件熵的變化情況,給出下面的定理5。
定理5 給定決策表 DT=(U,C∪D,V,f),C 是條件屬性集,D是決策屬性集,B?C。若對(duì)于任意的屬性ai和aj,(D)>POSB∪{aj}(D)且 (U-(D))/(B∪{ai})?(U-(D))/(B∪{aj}),則

類似于定理3,容易證明定理5。
根據(jù)定理5可以得出,在約簡(jiǎn)過(guò)程中當(dāng)兩個(gè)屬性ai和aj分別加入到候選屬性子集B中,如果決策屬性集D關(guān)于B∪{ai}的相對(duì)正域比關(guān)于 B∪{aj}的相對(duì)正域大,且B∪{ai}對(duì)非正域部分的劃分比B∪{aj}非正域部分的劃分更細(xì),則在論域U下D關(guān)于B∪{ai}的互補(bǔ)條件熵較小。
因此,在約簡(jiǎn)過(guò)程中,出現(xiàn)情況3時(shí)利用正域和互補(bǔ)條件熵作為啟發(fā)信息,都會(huì)選擇并入屬性子集B使得相對(duì)正域更大的屬性ai。

在約簡(jiǎn)過(guò)程中,當(dāng)兩個(gè)屬性ai和aj分別加入的候選屬性子集B中,如果決策屬性集D關(guān)于B∪{ai}的相對(duì)正域比關(guān)于B∪{aj}產(chǎn)生的相對(duì)正域大,且B∪{ai}對(duì)非正域部分的劃分比B∪{aj}對(duì)非正域部分的劃分粗糙,則在論域U下屬性子集B∪{ai}的互補(bǔ)條件熵與屬性子集B∪{ai}關(guān)于決策表的互補(bǔ)條件熵大小關(guān)系無(wú)法確定。
因此,當(dāng)約簡(jiǎn)過(guò)程中出現(xiàn)情況4時(shí),若利用正域和互補(bǔ)條件熵作為啟發(fā)信息,則選擇產(chǎn)生相對(duì)正域較大的屬性ai并入屬性子集B;若利用互補(bǔ)條件熵作為啟發(fā)信息,則能夠綜合考慮屬性加入后新的屬性子集產(chǎn)生相對(duì)正域的大小和對(duì)于非正域部分劃分的粗細(xì)程度選擇屬性。這樣更有利于為約簡(jiǎn)過(guò)程的下一次迭代提供好的屬性。
根據(jù)上述分析,本文設(shè)計(jì)了以互補(bǔ)條件熵為啟發(fā)信息的正域約簡(jiǎn)算法,該算法的具體描述如下:
算法1以互補(bǔ)條件熵為啟發(fā)信息的正域約簡(jiǎn)算法(CE-PRAR)

表2 算法CE-PRAR和PR-PRAR運(yùn)行結(jié)果和運(yùn)行時(shí)間對(duì)比
輸入一個(gè)決策表T=(U,C∪D,V,f)
輸出決策表的相對(duì)約簡(jiǎn)red
步驟1 red←;//red用來(lái)存放候選屬性子集。
步驟2如果(D)-POSC(D)<0,則將ai放入red//計(jì)算核屬性。
步驟3當(dāng) POSred(D)≠POSC(D)時(shí),//停止條件執(zhí)行{red←red∪{a0},其中Sig(a0,red,D)={Sig(ak,red,D)}}。
步驟4返回red,結(jié)束。
下面分析該算法的時(shí)間復(fù)雜性。設(shè)DT=(U,C∪D,V,f),其中C∪D=?,C是條件屬性集合,D是決策屬性集合。若|C|=m,|U|=n,則算法的時(shí)間復(fù)雜度為O(mn2)+O(n3)。
為驗(yàn)證本文提出的CE-PRAR算法的性能,本文選取了UCI數(shù)據(jù)庫(kù)中的6組數(shù)據(jù)集進(jìn)行測(cè)試,分別比較了以互補(bǔ)條件熵為啟發(fā)信息的正域約簡(jiǎn)算法(CE-PRAR)和以正域?yàn)閱l(fā)信息正域約簡(jiǎn)(PR-PRAR)的約簡(jiǎn)結(jié)果和時(shí)間消耗。實(shí)驗(yàn)中使用的數(shù)據(jù)集的詳細(xì)信息見表1。

表1 實(shí)驗(yàn)用UCI數(shù)據(jù)集
實(shí)驗(yàn)在硬件配置為CPU Pentium 3.40 GHz、內(nèi)存2 GB的計(jì)算機(jī)上,用C#語(yǔ)言編程實(shí)現(xiàn)算法,開發(fā)和測(cè)試平臺(tái)為Microsoft Visual Studio 2005。
表2給出了利用算法CE-PRAR和PR-PRAR在表1中的6個(gè)UCI數(shù)據(jù)集上的約簡(jiǎn)結(jié)果和時(shí)間消耗。從表2中可以看出對(duì)于大多數(shù)數(shù)據(jù)集由算法CE-PRAR獲得的約簡(jiǎn)的屬性數(shù)量比利用算法PR-PRAR獲得的約簡(jiǎn)的屬性數(shù)量少,并且計(jì)算耗時(shí)也明顯變少。在Der、Flag、large、Waveform和Zoo數(shù)據(jù)集利用算法CE-PRAR得到的約簡(jiǎn)均比利用算法PR-PRAR得到的約簡(jiǎn)少1個(gè)屬性,而且算法CE-PRAR的時(shí)間消耗比算法PR-PRAR也要小。特別是在數(shù)據(jù)集Lung-cancer上效果更為明顯,算法CE-PRAR得到的約簡(jiǎn)屬性的數(shù)量比算法PR-PRAR得到的約簡(jiǎn)的屬性數(shù)量少兩個(gè),而且與算法CE-PRAR相比時(shí)間消耗明顯較小。
為了說(shuō)明算法CE-PRAR的有效性,利用文獻(xiàn)[17]中提出的決策表決策性能評(píng)價(jià)指標(biāo)(確定度α、協(xié)調(diào)度 β和支持度γ)對(duì)利用算法CE-PRAR和算法PR-PRAR約簡(jiǎn)后決策表的決策性能進(jìn)行了對(duì)比分析(如表3所示)。從實(shí)驗(yàn)結(jié)果中可以看出對(duì)于所有的實(shí)驗(yàn)數(shù)據(jù)集,經(jīng)算法CE-PRAR約簡(jiǎn)后的決策表的決策性能與經(jīng)算法PR-PRAR約簡(jiǎn)后決策表的確定度α、協(xié)調(diào)度 β和支持度γ的值均相同或相差很小,這說(shuō)明利用算法CE-PRAR和算法PR-PRAR得到的約簡(jiǎn)決策表的決策性能非常接近。

表3 經(jīng)算法CE-PRAR和PR-PRAR約簡(jiǎn)后決策表的決策性能對(duì)比
本文對(duì)常見的屬性約簡(jiǎn)方法進(jìn)行了深入分析,發(fā)現(xiàn)在其約簡(jiǎn)過(guò)程中,候選屬性子集的評(píng)價(jià)指標(biāo)和算法的停止條件都是使用相同的度量,而在正域約簡(jiǎn)中使用相對(duì)正域作為這兩個(gè)指標(biāo)。進(jìn)一步,根據(jù)互補(bǔ)熵的隨劃分的變化規(guī)律,分四種情況分析了約簡(jiǎn)過(guò)程中某個(gè)屬性加入候選屬性子集后,相對(duì)正域和互補(bǔ)條件熵的變化,發(fā)現(xiàn)以互補(bǔ)條件熵作為啟發(fā)信息不但可以反映約簡(jiǎn)過(guò)程中相對(duì)正域大小的變化,還能夠反映非正域部分的分布變化。最后,提出了一種以互補(bǔ)熵為啟發(fā)信息的正域?qū)傩约s簡(jiǎn)算法。實(shí)驗(yàn)結(jié)果表明,提出的新算法與以相對(duì)正域?yàn)閱l(fā)信息的正域約簡(jiǎn)算法相比,可獲得一個(gè)包含更少屬性且決策性能非常接近的約簡(jiǎn),而且新算法的時(shí)間消耗也明顯減少。
[1]張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京:科學(xué)出版社,2001.
[2]Pawlak Z.Rough sets theoretical aspects of reasoning about data[M].[S.l.]:Kluwer Academic Publishers,1991.
[3]張文修,梁怡,吳偉志.信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M].北京:科學(xué)出版社,2003:7-12.
[4]Pedrycz W,Vukovich G.Feature analysis through information granulation and fuzzy sets[J].Pattern Recognition,2002,35:825-834.
[5]Greco S,Pawlak Z,Slowinski R.Can Bayesian confirmation measures be useful for rough set decision rules[J].Engineering Applications of Artificial Intelligence,2004,17:345-361.
[6]Skowron A,Rauszer C.The discernibility matrices and functions in information tables[M]//Intelligent decision support:handbook of applications and advances of rough set theory. Dordrecht:Kluwer Academic Publishers,1992:331-362.
[7]Hu X H,Cercone N.Learning in relationaldatabases:a rough set approach[J].International Journal of Computational Intelligence,1995,11(2):323-338.
[8]王國(guó)胤.決策表核屬性的計(jì)算方法[J].計(jì)算機(jī)學(xué)報(bào),2003,26(5):611-615.
[9]王國(guó)胤,于洪,楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),2002,25(7):759-766.
[10]Liang J Y,Chin K S,Dang C Y,et al.A new method for measuring uncertainty and fuzziness in rough set theory[J]. InternationalJournalofGeneralSystems,2002,31(4):331-342.
[11]Wei W,Liang J Y,Qian Y H,et al.An attribute reduction approach and its accelerated version for hybrid data[C]// The 8th IEEE International Conference on Cognitive Informatics,2009:167-173.
[12]Wei W,Liang J Y,Qian Y H,et al.Comparative study of decision performance of decision tables induced by attribute reductions[J].International Journal of General Systems,2010,39(8):813-838.
[13]Wei W,Liang J Y,Qian Y H.A comparative study of rough sets for hybrid data[J].Information Sciences,2012,190(1):1-16.
[14]梁吉業(yè),魏巍,錢宇華.一種基于條件熵的增量核求解方法[J].系統(tǒng)工程理論與實(shí)踐,2008,28(4):81-89.
[15]梁吉業(yè),李德玉.信息系統(tǒng)中的不確定性與知識(shí)獲取[M].北京:科學(xué)出版社,2005:37-46.
[16]Qian Y H,Liang J Y,Pedrycz W,et al.Positive approximation:an accelerator for attribute reduction in rough set theory[J].Artificial Intelligences,2010,174(9/10):597-618.
[17]Qian Y H,Liang J Y,Li D Y,et al.Measures for evaluating the decision performance of a decision table in rough set theory[J].Information Sciences,2008,178(1):181-202.
以互補(bǔ)條件熵為啟發(fā)信息的正域?qū)傩约s簡(jiǎn)
魏 巍,陳紅星,王 鋒
WEI Wei,CHEN Hongxing,WANG Feng
Key Lab of MoE for Computation Intelligence&Chinese Information Processing,School of Computer&Information Technology, Shanxi University,Taiyuan 030006,China
Attribute reduction,as a special approach for feature selection,is a key concept in rough set theory.The positive-region reduction approach is a kind of common reduction approach,which is of greedy and forward search type.These approaches keep adding one attribute with high significance into a pool during each iteration until positive-region no longer changes.In this paper, by analyzing changes of complementary conditional entropy varying with partition,four situations about changes of positive-region and entropy induced by adding a new attribute to the candidate attribute set are introduced.Then,a positive-region reduction algorithm based on complementary entropy is developed.Experimental results show that compared with the traditional positiveregion reduction algorithm,the proposed algorithm can find a reduction including fewer attributes and possessing almost same decision performance in a significantly shorter time.
rough set;attribute reduction;complement entropy;positive region
屬性約簡(jiǎn)是一種特殊的特征選擇方法,是粗糙集理論中的核心內(nèi)容之一。正域約簡(jiǎn)是一類常見的啟發(fā)式的約簡(jiǎn)方法,它通常采用前向貪婪搜索策略產(chǎn)生候選的屬性子集,以相對(duì)正域作為啟發(fā)信息和停止條件。根據(jù)互補(bǔ)條件熵的隨劃分的變化規(guī)律,分四種情況分析了約簡(jiǎn)過(guò)程中某個(gè)屬性加入屬性子集后,相對(duì)正域和互補(bǔ)條件熵的變化,并在此基礎(chǔ)上提出了一種以互補(bǔ)熵為啟發(fā)信息的正域?qū)傩约s簡(jiǎn)方法。實(shí)驗(yàn)分析表明,新方法與傳統(tǒng)的正域約簡(jiǎn)算法相比,可以得到屬性數(shù)量更少且決策性能非常接近的約簡(jiǎn),同時(shí)可以有效地提高約簡(jiǎn)計(jì)算效率。
粗糙集;屬性約簡(jiǎn);互補(bǔ)熵;正域
A
TP393
10.3778/j.issn.1002-8331.1212-0094
WEI Wei,CHEN Hongxing,WANG Feng.Positive region attribute reduction utilizing complement condition entropy as heuristic information.Computer Engineering and Applications,2013,49(11):96-100.
國(guó)家自然科學(xué)基金(No.71031006,No.61202018,No.60970014);山西省自然科學(xué)基金(No.2010021017-3)。
魏?。?980—),男,博士,講師,主要研究方向?yàn)閿?shù)據(jù)挖掘、粒度計(jì)算;陳紅星(1963—),男,工程師,主要研究方向?yàn)楦拍罡?、?shù)據(jù)挖掘;王鋒(1984—),女,博士研究究生,主要研究方向?yàn)榱6扔?jì)算、模式識(shí)別。E-mail:weiwei@sxu.edu.cn
2012-12-10
2013-02-18
1002-8331(2013)11-0096-05