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

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

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

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

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

1 相關基本概念

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

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

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

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

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

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

1)RBRD;

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

定理2[6]設S=是不一致決策表,則以下3個條件等價：

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

2 廣義決策約簡等價于分配約簡

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

先考察文獻[14]的算例。

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

表1 決策表S1

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

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

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

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

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

1)RB

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

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

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

屬性約簡新的判定指標由下面的定理給出。

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

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

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

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

4 計算實例

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

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

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

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

表3 決策表S2

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

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

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

5 結 語

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

參考文獻：

[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].計算機學報,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ù)理論的知識約簡[J] . 小型微型計算機系統(tǒng),2009,30(2): 317-321.

[8]袁修久,張文修.決策表的分布約簡和嚴凸函數(shù)下約簡的等價性[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]李凡,劉啟和,葉茂,等. 不一致決策表的知識約簡方法研究[J]. 控制與決策,2006,21(8): 857-862.

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

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

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

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