以互補(bǔ)條件熵為啟發(fā)信息的正域?qū)傩约s簡

山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

1 引言

粗糙集理論是一種處理不精確、不確定與不完全數(shù)據(jù)的數(shù)學(xué)工具[1-2]，其主要思想是：在保持信息系統(tǒng)分類能力不變的前提下，經(jīng)過屬性約簡導(dǎo)出分類或決策規(guī)則。目前，粗糙集理論已經(jīng)被廣泛地應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識別、故障診斷等領(lǐng)域[3-5]。

特征選擇是指在不改變原始特征空間性質(zhì)的前提下，從原始特征空間中選擇一部分重要的特征，組成一個新的低維特征空間的過程。屬性約簡是在保持原始數(shù)據(jù)的屬性區(qū)分能力不變的前提下，選擇具有最小屬性（特征）數(shù)量的屬性子集的過程，是一種特定背景下的特征選擇方法。屬性約簡是粗糙集理論中的核心內(nèi)容之一。

目前，研究者已經(jīng)提出了許多屬性約簡方法[6-8]。Skowron[6]提出了區(qū)分矩陣屬性約簡方法，該方法可以得到信息系統(tǒng)的所有約簡，但是這種算法的復(fù)雜度過高（已經(jīng)被證明為NP-Hard問題）。為了提高約簡算法的效率，許多學(xué)者應(yīng)用啟發(fā)式的搜索策略求解屬性約簡，從而有效地降低約簡算法的耗時。Hu和Cercone[7]將相對正域引入到屬性約簡中，提出了一種啟發(fā)式屬性約簡算法。王國胤等[8-9]將Shannon信息熵用于屬性子集評價，提出相應(yīng)的啟發(fā)式屬性約簡，該方法的停止條件也是利用Shannon條件熵。梁吉業(yè)等[10-14]將互補(bǔ)熵引入粗糙集理論用于度量信息系統(tǒng)的不確定性，并提出利用互補(bǔ)熵評價屬性子集的屬性約簡算法。

上述啟發(fā)式屬性約簡方法都是先根據(jù)前向貪婪搜索策略產(chǎn)生候選的屬性子集，然后利用某種度量對候選屬性子集進(jìn)行評價，如果某個屬性子集與原始屬性集的區(qū)分能力相同（即滿足停止條件），則得到屬性約簡，否則重復(fù)前面的過程直至滿足停止條件（如圖1所示）。這些算法都使用相同的度量作為屬性子集的評價指標(biāo)和算法的停止條件。評價指標(biāo)決定著算法的收斂方向，而停止條件決定著算法得到的約簡的性質(zhì)，因此這兩者并不必須使用相同的度量。

圖1 屬性約簡過程示意圖

根據(jù)上述分析，本文根據(jù)互補(bǔ)熵的隨劃分的變化規(guī)律，分四種情況分析了約簡過程中當(dāng)某個屬性加入屬性子集后，相對正域和互補(bǔ)條件熵的變化。并提出了一種以互補(bǔ)條件熵為啟發(fā)信息、以相對正域?yàn)橥Ｖ箺l件的屬性約簡方法，與傳統(tǒng)的以相對正域?yàn)閱l(fā)信息的正域約簡算法相比，該算法可以得到屬性數(shù)量更少的約簡，同時計(jì)算約簡的時間消耗也更少。

2 基本概念

設(shè)S=(U，A，V，f)為一個信息系統(tǒng)，其中U為非空有限對象集合，稱為論域；A為非空有限屬性集合；對任意a∈A有 a:U→Va，其中Va稱為屬性 a 的值域，V=∪a∈AVa，f:U×A=V是一個函數(shù)，對于任意的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)稱為一個決策表，記為DT=(U，C∪D，V，f)。如果其中條件屬性集C對論域U的劃分為={X1，X2，…，Xm}，決策屬性集D對論域U的劃分為={Y1，Y2，…，Yn}，則 D 關(guān)于C的相對正域記為POSC。若某個決策表的決策屬性集關(guān)于條件屬性集的相對正域?yàn)檎麄€論域，則稱其為協(xié)調(diào)的決策表，否則稱其為不協(xié)調(diào)的決策表。

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

3 以互補(bǔ)熵為啟發(fā)信息的屬性約簡

為了給出新的屬性約簡算法，首先引入下面的定理。

定理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ì)程度）。

在屬性約簡的過程中，決策屬性關(guān)于當(dāng)前屬性集的非正域部分中對象將會成為下一次迭代時相對正域中的對象，如圖2所示，圖中決策屬性關(guān)于屬性集B的非正域中的一些對象（陰影部分）在條件屬性集為B∪{ai}時進(jìn)入了相對正域。因此，決策屬性集關(guān)于某一條件屬性集的非正域中的對象的分布情況也會對約簡過程中屬性的選擇產(chǎn)生重要的影響，進(jìn)而影響約簡算法收斂的方向和速度。

圖2 約簡過程中相對正域和非正域的變化

為了更好地說明約簡過程中以互補(bǔ)條件熵為啟發(fā)信息和以正域?yàn)閱l(fā)信息的區(qū)別，下面分四種情況來分析。

不失一般性，不妨設(shè)當(dāng)前屬性子集為B，可選擇加入的屬性有ai和aj。

為了說明該情況時在論域U下互補(bǔ)條件熵的變化情況，給出下面的定理3。

定理3 給定決策表 DT=(U，C∪D，V，f)，C 是條件屬性集，D是決策屬性集，B?C。若對于任意的屬性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可以得出，在約簡過程中當(dāng)兩個屬性ai和aj分別加入的候選屬性子集B時，如果決策屬性集D關(guān)于B∪{ai}的相對正域與關(guān)于B∪{aj}的相對正域大小相等，且屬性B∪{ai}對非正域部分的劃分比B∪{aj}對非正域部分的劃分細(xì)，則在論域U下，D關(guān)于B∪{ai}的互補(bǔ)條件熵較小。

因此，在約簡過程中，出現(xiàn)情況1時，若選擇正域作為啟發(fā)式信息，則屬性ai和aj的重要程度相同，只能任意選擇一個。而選擇互補(bǔ)條件熵為啟發(fā)信息則可以選擇到對非正域部分劃分更細(xì)的屬性，為約簡過程的下一次迭代奠定更好基礎(chǔ)。

為了說明該情況時在論域U下互補(bǔ)條件熵的變化情況，給出下面的定理4。

定理4 給定決策表 DT=(U，C∪D，V，f)，C 是條件屬性集，D是決策屬性集，B?C。若對于任意的屬性ai和aj，POSB∪{ai}(D)＞ POSB∪{aj}(D) 且(D|B ∪{ai})=(D|B ∪{aj})，則

類似于定理3，容易證明定理4。

定理4表明在約簡過程中當(dāng)兩個屬性ai和aj分別加入候選屬性子集B時，如果在決策表的非正域部分B∪{ai}關(guān)于決策屬性的互補(bǔ)條件熵與B∪{aj}關(guān)于決策屬性的互補(bǔ)條件熵相等，且在論域U上D關(guān)于B∪{ai}相對正域比D關(guān)于B∪{aj}相對正域大，則在論域U上D關(guān)于B∪{ai}關(guān)的互補(bǔ)條件熵較小。

因此，在約簡過程中，出現(xiàn)情況2時利用正域和互補(bǔ)條件熵作為啟發(fā)信息，都會選擇并入屬性子集B后使得相對正域更大的屬性ai。

為了說明該情況時在論域U下互補(bǔ)條件熵的變化情況，給出下面的定理5。

定理5 給定決策表 DT=(U，C∪D，V，f)，C 是條件屬性集，D是決策屬性集，B?C。若對于任意的屬性ai和aj，(D)＞POSB∪{aj}(D)且 (U-(D))/(B∪{ai})?(U-(D))/(B∪{aj})，則

類似于定理3，容易證明定理5。

根據(jù)定理5可以得出，在約簡過程中當(dāng)兩個屬性ai和aj分別加入到候選屬性子集B中，如果決策屬性集D關(guān)于B∪{ai}的相對正域比關(guān)于 B∪{aj}的相對正域大，且B∪{ai}對非正域部分的劃分比B∪{aj}非正域部分的劃分更細(xì)，則在論域U下D關(guān)于B∪{ai}的互補(bǔ)條件熵較小。

因此，在約簡過程中，出現(xiàn)情況3時利用正域和互補(bǔ)條件熵作為啟發(fā)信息，都會選擇并入屬性子集B使得相對正域更大的屬性ai。

在約簡過程中，當(dāng)兩個屬性ai和aj分別加入的候選屬性子集B中，如果決策屬性集D關(guān)于B∪{ai}的相對正域比關(guān)于B∪{aj}產(chǎn)生的相對正域大，且B∪{ai}對非正域部分的劃分比B∪{aj}對非正域部分的劃分粗糙，則在論域U下屬性子集B∪{ai}的互補(bǔ)條件熵與屬性子集B∪{ai}關(guān)于決策表的互補(bǔ)條件熵大小關(guān)系無法確定。

因此，當(dāng)約簡過程中出現(xiàn)情況4時，若利用正域和互補(bǔ)條件熵作為啟發(fā)信息，則選擇產(chǎn)生相對正域較大的屬性ai并入屬性子集B；若利用互補(bǔ)條件熵作為啟發(fā)信息，則能夠綜合考慮屬性加入后新的屬性子集產(chǎn)生相對正域的大小和對于非正域部分劃分的粗細(xì)程度選擇屬性。這樣更有利于為約簡過程的下一次迭代提供好的屬性。

根據(jù)上述分析，本文設(shè)計(jì)了以互補(bǔ)條件熵為啟發(fā)信息的正域約簡算法，該算法的具體描述如下：

算法1以互補(bǔ)條件熵為啟發(fā)信息的正域約簡算法（CE-PRAR）

表2 算法CE-PRAR和PR-PRAR運(yùn)行結(jié)果和運(yùn)行時間對比

輸入一個決策表T=(U，C∪D，V，f)

輸出決策表的相對約簡red

步驟1 red←;//red用來存放候選屬性子集。

步驟2如果(D)-POSC(D)＜0，則將ai放入red//計(jì)算核屬性。

步驟3當(dāng) POSred(D)≠POSC(D)時，//停止條件執(zhí)行{red←red∪{a0}，其中Sig(a0，red，D)={Sig(ak，red，D)}}。

步驟4返回red，結(jié)束。

下面分析該算法的時間復(fù)雜性。設(shè)DT=(U，C∪D，V，f)，其中C∪D=?，C是條件屬性集合，D是決策屬性集合。若|C|=m，|U|=n，則算法的時間復(fù)雜度為O(mn2)+O(n3)。

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

為驗(yàn)證本文提出的CE-PRAR算法的性能，本文選取了UCI數(shù)據(jù)庫中的6組數(shù)據(jù)集進(jìn)行測試，分別比較了以互補(bǔ)條件熵為啟發(fā)信息的正域約簡算法（CE-PRAR）和以正域?yàn)閱l(fā)信息正域約簡（PR-PRAR）的約簡結(jié)果和時間消耗。實(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#語言編程實(shí)現(xiàn)算法，開發(fā)和測試平臺為Microsoft Visual Studio 2005。

表2給出了利用算法CE-PRAR和PR-PRAR在表1中的6個UCI數(shù)據(jù)集上的約簡結(jié)果和時間消耗。從表2中可以看出對于大多數(shù)數(shù)據(jù)集由算法CE-PRAR獲得的約簡的屬性數(shù)量比利用算法PR-PRAR獲得的約簡的屬性數(shù)量少，并且計(jì)算耗時也明顯變少。在Der、Flag、large、Waveform和Zoo數(shù)據(jù)集利用算法CE-PRAR得到的約簡均比利用算法PR-PRAR得到的約簡少1個屬性，而且算法CE-PRAR的時間消耗比算法PR-PRAR也要小。特別是在數(shù)據(jù)集Lung-cancer上效果更為明顯，算法CE-PRAR得到的約簡屬性的數(shù)量比算法PR-PRAR得到的約簡的屬性數(shù)量少兩個，而且與算法CE-PRAR相比時間消耗明顯較小。

為了說明算法CE-PRAR的有效性，利用文獻(xiàn)[17]中提出的決策表決策性能評價指標(biāo)（確定度α、協(xié)調(diào)度 β和支持度γ）對利用算法CE-PRAR和算法PR-PRAR約簡后決策表的決策性能進(jìn)行了對比分析（如表3所示）。從實(shí)驗(yàn)結(jié)果中可以看出對于所有的實(shí)驗(yàn)數(shù)據(jù)集，經(jīng)算法CE-PRAR約簡后的決策表的決策性能與經(jīng)算法PR-PRAR約簡后決策表的確定度α、協(xié)調(diào)度 β和支持度γ的值均相同或相差很小，這說明利用算法CE-PRAR和算法PR-PRAR得到的約簡決策表的決策性能非常接近。

表3 經(jīng)算法CE-PRAR和PR-PRAR約簡后決策表的決策性能對比

5 結(jié)論

本文對常見的屬性約簡方法進(jìn)行了深入分析，發(fā)現(xiàn)在其約簡過程中，候選屬性子集的評價指標(biāo)和算法的停止條件都是使用相同的度量，而在正域約簡中使用相對正域作為這兩個指標(biāo)。進(jìn)一步，根據(jù)互補(bǔ)熵的隨劃分的變化規(guī)律，分四種情況分析了約簡過程中某個屬性加入候選屬性子集后，相對正域和互補(bǔ)條件熵的變化，發(fā)現(xiàn)以互補(bǔ)條件熵作為啟發(fā)信息不但可以反映約簡過程中相對正域大小的變化，還能夠反映非正域部分的分布變化。最后，提出了一種以互補(bǔ)熵為啟發(fā)信息的正域?qū)傩约s簡算法。實(shí)驗(yàn)結(jié)果表明，提出的新算法與以相對正域?yàn)閱l(fā)信息的正域約簡算法相比，可獲得一個包含更少屬性且決策性能非常接近的約簡，而且新算法的時間消耗也明顯減少。

[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)與知識發(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]王國胤.決策表核屬性的計(jì)算方法[J].計(jì)算機(jī)學(xué)報(bào)，2003，26（5）：611-615.

[9]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[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)中的不確定性與知識獲取[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簡

魏 巍，陳紅星，王 鋒

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

屬性約簡是一種特殊的特征選擇方法，是粗糙集理論中的核心內(nèi)容之一。正域約簡是一類常見的啟發(fā)式的約簡方法，它通常采用前向貪婪搜索策略產(chǎn)生候選的屬性子集，以相對正域作為啟發(fā)信息和停止條件。根據(jù)互補(bǔ)條件熵的隨劃分的變化規(guī)律，分四種情況分析了約簡過程中某個屬性加入屬性子集后，相對正域和互補(bǔ)條件熵的變化，并在此基礎(chǔ)上提出了一種以互補(bǔ)熵為啟發(fā)信息的正域?qū)傩约s簡方法。實(shí)驗(yàn)分析表明，新方法與傳統(tǒng)的正域約簡算法相比，可以得到屬性數(shù)量更少且決策性能非常接近的約簡，同時可以有效地提高約簡計(jì)算效率。

粗糙集；屬性約簡；互補(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.

國家自然科學(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)榱６扔?jì)算、模式識別。E-mail：weiwei@sxu.edu.cn

2012-12-10

2013-02-18

1002-8331（2013）11-0096-05