曾凡智,盧炎生,黃國順,文 翰

(1.佛山科學(xué)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 佛山 528000;2.華中科技大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074;3. 佛山科學(xué)技術(shù)學(xué)院 理學(xué)院 ，廣東 佛山 528000)

粗糙集(Rough Set)理論是由波蘭數(shù)學(xué)家Pawlak[1]于20世紀(jì)80年代初提出的用于數(shù)據(jù)分析的理論，作為處理不確定信息的有效工具,粗糙集理論已被成功地應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)、模式識(shí)別等領(lǐng)域,成為當(dāng)前研究熱點(diǎn)之一。

屬性約簡是Rough 集理論的核心問題之一，也是知識(shí)獲取的關(guān)鍵步驟之一,因此屬性約簡研究深受各研究者的關(guān)注。目前已有多種屬性約簡方法被提出,歸納起來主要有Pawlak原始定義的屬性約簡,稱之為代數(shù)約簡； 基于條件信息熵的屬性約簡(稱之為信息熵約簡)[2-3]；基于包含度理論的分布約簡、最大分布約簡、分配約簡及近似約簡等[4]；基于D-S證據(jù)理論的屬性約簡方法等[5-7]。其中信息熵約簡與分布約簡是完全等價(jià)的[8]，分配約簡與近似約簡也完全等價(jià)。對于一致決策表,上述各約簡方法所得約簡結(jié)果是一致的,但在不一致決策表下,它們所得的各約簡結(jié)果及核屬性都不盡相同[9-12]。針對不一致決策表，目前通常的處理過程是將不一致決策表轉(zhuǎn)化為一致決策表，再對所得到的一致決策表計(jì)算其代數(shù)約簡[6-9]，其中文獻(xiàn)[6]的方法先將不一致決策表轉(zhuǎn)化為一致決策表，然后基于D-S證據(jù)理論求出其廣義決策約簡，然而具體的算例表明廣義決策約簡與原始決策表的代數(shù)約簡并不相同。本文的研究結(jié)果表明廣義決策約簡僅與分配約簡等價(jià)。與廣義決策約簡為了維持某種“不變”的判定指標(biāo)而人為去將不一致決策表轉(zhuǎn)化成一致決策表不同，本文修改了求屬性約簡的判定指標(biāo)，從而避免將不一致決策表轉(zhuǎn)化為一致決策表這一過程，提出一種不需轉(zhuǎn)換過程,直接針對不一致決策求出其代數(shù)約簡和代數(shù)核的新方法。

1 相關(guān)基本概念

定義1 決策表S=是一類特殊的信息系統(tǒng),其中U稱為論域，C為有限的條件屬性集,D為有限的決策屬性集，C∩D=?,V=∪a∈CVa,Va為屬性a的值域，f:U×(C∪D)→V是信息函數(shù)。對U上的任意屬性集B?C∪D,定義不可分辨關(guān)系ind(B)={(x,y)∈U2|?a∈B,f(x,a)=f(y,a)},關(guān)系ind(B)構(gòu)成U的一個(gè)劃分,簡記為U/B。U/B中的任何元素[x]B={y|?a∈B,f(x,a)=f(y,a)}稱為等價(jià)類，如果對于任意的Bi∈U/B,存在Dj∈U/D,使得Bi?Dj,稱B是比D更細(xì)的劃分,記作RB?X}為X關(guān)于B的下近似集為B關(guān)于D的正區(qū)域。

若POSC(D)=U稱其為一致決策表,如果POSC(D)=?稱其為完全不一致決策表,其余情形稱為部分不一致決策表。若POSB(D)=POSC(D)， 則稱B為C的代數(shù)協(xié)調(diào)集，若B是C的代數(shù)協(xié)調(diào)集且B的任何真子集都不是其代數(shù)協(xié)調(diào)集，則稱B為C相對于D的代數(shù)約簡。

由于判斷兩集合是否相等比較費(fèi)時(shí),文獻(xiàn)[13]提出一種簡化的判斷方法,即POSC(D)=POSB(D)的充分必要條件是|POSC(D)|=|POSB(D)|， 它將判斷一個(gè)屬性集B是否為條件屬性集C的代數(shù)協(xié)調(diào)集簡化為只需判斷兩集合的基數(shù)是否相等，從而大大簡化了計(jì)算過程，提高了計(jì)算效率。

定義2 給定決策表S=,設(shè)U/D={D1,D2,…,Dr},記δB(x)={Dj|[x]B∩Dj≠?},若對?x∈U,B?C,有δB(x)=δC(x),則稱B是分配協(xié)調(diào)集,若B是分配協(xié)調(diào)集且B的任何真子集都不是分配協(xié)調(diào)集,則稱B為C的分配約簡。

文獻(xiàn)[10]指出，當(dāng)時(shí)B?C,對任意的x∈U,δB(x)=δC(x)當(dāng)且僅當(dāng)?y∈[x]B,δB(y)=δC(x)。 這為分布約簡的判斷提供了途徑。

定理1[6]若S=是一致決策表,設(shè)U/D={D1,D2,…,Dr},B?C,則以下3個(gè)條件等價(jià)：

1)RBRD;

對于不一致決策表S=,B?C,如果RB則稱B是C的廣義決策協(xié)調(diào)集。 如果B是廣義決策協(xié)調(diào)集,且B的任意子集都不是廣義協(xié)調(diào)集,則稱B是C的廣義決策約簡。

定理2[6]設(shè)S=是不一致決策表,則以下3個(gè)條件等價(jià)：

1)B?C是C的廣義決策約簡;

2 廣義決策約簡等價(jià)于分配約簡

本節(jié)將首先通過具體的算例說明,在不一致決策表下,廣義決策約簡與代數(shù)約簡并不完全一致,然后從理論上證明廣義決策約簡實(shí)質(zhì)上只與分配約簡等價(jià)。

先考察文獻(xiàn)[14]的算例。

例1 在表1的決策表S1中,U={x1,x2,…,x6},C={a,b,c},D=syggg00。

表1 決策表S1

易得POSC(D)={x6},其代數(shù)約簡為。如果按照求廣義決策約簡的計(jì)算方法,其廣義決策值?C(x)如表2 所示。

表2 決策表S1的?C(x)

雖然廣義決策約簡與代數(shù)約簡在不一致決策表上所得的結(jié)果并不完全相同,下面結(jié)論指出廣義決策約簡和分配約簡是等價(jià)的。

定理3 給定決策表S=和B?C,則δB(x)=δC(x)的充要條件是RB

反之,若RB則對?x∈U,有某個(gè)存在,使得[x]B?又因決策表是一致的,具有唯一的廣義決策值,即有?B(x)=?C(x),從而[x]B與有相同的分配函數(shù),即對?y∈[x]B有δB(y)=δC(x),根據(jù)文獻(xiàn)[10]的結(jié)果，有δB(x)=δC(x),即B是C的分配協(xié)調(diào)集。

1)RB

根據(jù)定理3和4知,B?C是C的廣義決策協(xié)調(diào)集當(dāng)且僅當(dāng)它是C的分配協(xié)調(diào)集,從而知道廣義決策約簡與分配約簡是等價(jià)的。根據(jù)文獻(xiàn)[12]知,廣義協(xié)調(diào)集必為代數(shù)協(xié)調(diào)集,從而知，若存在一個(gè)代數(shù)約簡，則一定存在一個(gè)相應(yīng)的廣義決策約簡，使得該代數(shù)約簡是相應(yīng)廣義決策約簡的子集，但兩者并不完全一致，如例1中的決策表S1,其代數(shù)約簡為， 廣義決策約簡為{a,b}，?{a,b}。

3 基于D-S證據(jù)理論直接求代數(shù)約簡和代數(shù)核的方法

基于以上事實(shí)，下面提出一種求屬性約簡新的判定指標(biāo)，從而跳過將不一致決策表轉(zhuǎn)化為一致決策表這一過程，提高了計(jì)算效率。理論上證明了其計(jì)算過程一定能得到代數(shù)協(xié)調(diào)集和代數(shù)核。

屬性約簡新的判定指標(biāo)由下面的定理給出。

上述證明過程是可逆的,從而有結(jié)論成立。

證明根據(jù)代數(shù)協(xié)調(diào)集與代數(shù)約簡的定義及定理5知結(jié)論成立。

若決策表S的相對核為CORE(C,D)， 由此給出基于D-S證據(jù)理論的代數(shù)核屬性判斷準(zhǔn)則推論2。

證明根據(jù)定理5和相對核CORE(C,D)的定義即知結(jié)論成立。

4 計(jì)算實(shí)例

通過兩個(gè)算例說明采用新的屬性約簡的指標(biāo)函數(shù)，直接求代數(shù)約簡與代數(shù)核新方法的有效性。

例2 繼續(xù)考察例1決策表S1。

為進(jìn)一步說明廣義決策約簡、分配約簡與代數(shù)約簡之間的異同以及本文求代數(shù)約簡和代數(shù)核的新方法，引用文獻(xiàn)[10]的算例進(jìn)一步驗(yàn)證如下。

例3 給定決策表S2=如表3所示,其中U={x1,x2,…,x18},C={a,b,c,e,f,g},D=syggg00。

表3 決策表S2

表4 U/C等價(jià)類的分配函數(shù)值與廣義決策值

顯然δB(x)=δC(x),?B(x)=?C(x)，同理,若令B={a,c,e,g},知其也是廣義決策協(xié)調(diào)集.并且可驗(yàn)證它們都是C的分配約簡和廣義決策約簡。

表5 U/B等價(jià)類的分配函數(shù)值與廣義決策值

5 結(jié) 語

基于D-S證據(jù)理論的屬性約簡方法在一致決策表上所的結(jié)果與代數(shù)約簡的結(jié)果是一致的,對于不一致決策表,現(xiàn)有的方法是先將不一致決策表轉(zhuǎn)化成一致決策表，然后求其廣義決策表約簡，但它與代數(shù)約簡并不完全相一致.本文討論了這種不一致性問題,理論上證明了廣義決策約簡僅與分配約簡等價(jià),進(jìn)一步地，提出了一種在D-S證據(jù)理論下采用新的屬性約簡指標(biāo)直接求代數(shù)約簡和代數(shù)核的新方法,從而避免了不一致決策表轉(zhuǎn)化的問題，減少了轉(zhuǎn)換的復(fù)雜度與提了算法效率，為在不一致決策表下直接計(jì)算代數(shù)約簡的高效算法的探索打下了基礎(chǔ)。

參考文獻(xiàn)：

[1]PAWLAK Z. Rough sets [J]. International Journal of Information and Computer Science,1982,11(5):341-356.

[2]MIAO Duoqian,WANG Ju. An information represention of the concept and operations in rough set theory [J]. Journal of Software,1999,10(2):113-116.

[3]王國胤,于 洪,楊大春. 基于條件信息熵的決策表約簡[J].計(jì)算機(jī)學(xué)報(bào),2002,25(7):759-766.

[4]ZHANG Wenxiu,MI Jusheng,WU Weizhi. Approaches to knowledge reductions in inconsistent systems [J]. International Journal of Intelligent Systems,2003,18(4): 989-1000.

[5]ZHANG Mei,XU Lida,ZHANG Wenxiu,et al. A rough set approach to knowledge reduction based on inclusion degree and evidence reasoning theory [J]. Expert Systems,2003,20(5): 298-304.

[6]WU Weizhi,ZHANG Mei,LI Huaizu et al. Knowledge reduction in random information systems via Dempster-Shafer theory of evidence [J]. Information Sciences,2005,174: 143-164.

[7]曾凡智，盧炎生.不一致決策表下基于D-S證據(jù)理論的知識(shí)約簡[J] . 小型微型計(jì)算機(jī)系統(tǒng),2009,30(2): 317-321.

[8]袁修久,張文修.決策表的分布約簡和嚴(yán)凸函數(shù)下約簡的等價(jià)性[J].系統(tǒng)工程,2003,21(5): 5-7.

[9]WANG Guoyin,ZHAO Jun,AN Jiujiang et.al.. A comparative study of algebra viewpoint and information viewpoint in attribute reduction [J]. Fundamenta Informaticae,2005,68(6):289-301.

[10]李凡,劉啟和,葉茂,等. 不一致決策表的知識(shí)約簡方法研究[J]. 控制與決策,2006,21(8): 857-862.

[11]黃國順,劉云生. 不一致決策表信息熵約簡與代數(shù)約簡的核計(jì)算與轉(zhuǎn)化[J].小型微型計(jì)算機(jī)系統(tǒng),2008,29(2):308-312.

[12]黃國順,劉云生. 不一致決策表各種屬性約簡的不一致性分析與轉(zhuǎn)化[J]. 小型微型計(jì)算機(jī)系統(tǒng),2008,29(4): 703-708.

[13]黃國順. 基于數(shù)據(jù)庫系統(tǒng)的決策表核和屬性約簡算法[J]. 計(jì)算機(jī)應(yīng)用,2008,28(5):1180-1182.

[14]王國胤. 決策表核屬性的計(jì)算方法[J]. 計(jì)算機(jī)學(xué)報(bào),2003,26(5):611-615.