山西大學 計算機與信息技術學院 計算智能與中文信息處理教育部重點實驗室，太原 030006

山西大學 計算機與信息技術學院 計算智能與中文信息處理教育部重點實驗室，太原 030006

1 引言

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

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

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

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

圖1 屬性約簡過程示意圖

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

2 基本概念

設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負域。

若信息系統(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 關于C的相對正域記為POSC。若某個決策表的決策屬性集關于條件屬性集的相對正域為整個論域，則稱其為協(xié)調的決策表，否則稱其為不協(xié)調的決策表。

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

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

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

定理1[15]給定決策表 DT=(U，C∪D，V，f)，C 是條件屬性集，D是決策屬性集。若U/B?U/C，則

定理1表明隨著論域劃分的變細，決策表的互補條件熵將變小。

定理2[16]給定決策表 DT=(U，C∪D，V，f)，C 是條件屬性集，B?C，D是決策屬性集，則

定理2表明互補條件熵不僅與其正域部分的大小有關，還與其非正域部分的互補條件熵的大小有關。進一步結合定理1的結論可以得出非正域部分的條件熵的大小與其劃分的粗細程度有關。因此，利用互補條件熵作為啟發(fā)式信息，則不但可以反映正域部分大小，也可以反映非正域部分的分布情況（劃分的粗細程度）。

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

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

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

不失一般性，不妨設當前屬性子集為B，可選擇加入的屬性有ai和aj。

為了說明該情況時在論域U下互補條件熵的變化情況，給出下面的定理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可以得出，在約簡過程中當兩個屬性ai和aj分別加入的候選屬性子集B時，如果決策屬性集D關于B∪{ai}的相對正域與關于B∪{aj}的相對正域大小相等，且屬性B∪{ai}對非正域部分的劃分比B∪{aj}對非正域部分的劃分細，則在論域U下，D關于B∪{ai}的互補條件熵較小。

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

為了說明該情況時在論域U下互補條件熵的變化情況，給出下面的定理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表明在約簡過程中當兩個屬性ai和aj分別加入候選屬性子集B時，如果在決策表的非正域部分B∪{ai}關于決策屬性的互補條件熵與B∪{aj}關于決策屬性的互補條件熵相等，且在論域U上D關于B∪{ai}相對正域比D關于B∪{aj}相對正域大，則在論域U上D關于B∪{ai}關的互補條件熵較小。

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

為了說明該情況時在論域U下互補條件熵的變化情況，給出下面的定理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可以得出，在約簡過程中當兩個屬性ai和aj分別加入到候選屬性子集B中，如果決策屬性集D關于B∪{ai}的相對正域比關于 B∪{aj}的相對正域大，且B∪{ai}對非正域部分的劃分比B∪{aj}非正域部分的劃分更細，則在論域U下D關于B∪{ai}的互補條件熵較小。

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

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

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

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

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

表2 算法CE-PRAR和PR-PRAR運行結果和運行時間對比

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

輸出決策表的相對約簡red

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

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

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

步驟4返回red，結束。

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

4 實驗及分析

為驗證本文提出的CE-PRAR算法的性能，本文選取了UCI數(shù)據(jù)庫中的6組數(shù)據(jù)集進行測試，分別比較了以互補條件熵為啟發(fā)信息的正域約簡算法（CE-PRAR）和以正域為啟發(fā)信息正域約簡（PR-PRAR）的約簡結果和時間消耗。實驗中使用的數(shù)據(jù)集的詳細信息見表1。

表1 實驗用UCI數(shù)據(jù)集

實驗在硬件配置為CPU Pentium 3.40 GHz、內存2 GB的計算機上，用C#語言編程實現(xiàn)算法，開發(fā)和測試平臺為Microsoft Visual Studio 2005。

表2給出了利用算法CE-PRAR和PR-PRAR在表1中的6個UCI數(shù)據(jù)集上的約簡結果和時間消耗。從表2中可以看出對于大多數(shù)數(shù)據(jù)集由算法CE-PRAR獲得的約簡的屬性數(shù)量比利用算法PR-PRAR獲得的約簡的屬性數(shù)量少，并且計算耗時也明顯變少。在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的有效性，利用文獻[17]中提出的決策表決策性能評價指標（確定度α、協(xié)調度 β和支持度γ）對利用算法CE-PRAR和算法PR-PRAR約簡后決策表的決策性能進行了對比分析（如表3所示）。從實驗結果中可以看出對于所有的實驗數(shù)據(jù)集，經算法CE-PRAR約簡后的決策表的決策性能與經算法PR-PRAR約簡后決策表的確定度α、協(xié)調度 β和支持度γ的值均相同或相差很小，這說明利用算法CE-PRAR和算法PR-PRAR得到的約簡決策表的決策性能非常接近。

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

5 結論

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

[1]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學出版社，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].北京：科學出版社，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].計算機學報，2003，26（5）：611-615.

[9]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學報，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)工程理論與實踐，2008，28（4）：81-89.

[15]梁吉業(yè)，李德玉.信息系統(tǒng)中的不確定性與知識獲取[M].北京：科學出版社，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.

以互補條件熵為啟發(fā)信息的正域屬性約簡

魏 巍，陳紅星，王 鋒

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

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

粗糙集；屬性約簡；互補熵；正域

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.

國家自然科學基金（No.71031006，No.61202018，No.60970014）；山西省自然科學基金（No.2010021017-3）。

魏?。?980—），男，博士，講師，主要研究方向為數(shù)據(jù)挖掘、粒度計算；陳紅星（1963—），男，工程師，主要研究方向為概念格、數(shù)據(jù)挖掘；王鋒（1984—），女，博士研究究生，主要研究方向為粒度計算、模式識別。E-mail：weiwei@sxu.edu.cn

2012-12-10

2013-02-18

1002-8331（2013）11-0096-05