第9章 粗糙集理論.ppt

1、第9章 粗糙集理論,粗糙集理論是一種刻劃不完整性和不確定性的數(shù)學(xué)工具， 能有效地分析不精確、不一致和不完整等各種不完備的信息。 還可以對(duì)數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識(shí)， 揭示潛在的規(guī)律。,9.1 粗糙集理論概述,9.1.1 粗糙集理論的產(chǎn)生,1970年，Z.Pawlak和波蘭科學(xué)院、華沙大學(xué)的一些邏輯學(xué)家，在研究信息系統(tǒng)邏輯特性的基礎(chǔ)上，提出了粗糙集（Rough Set）理論的思想。 1982年，Z.Pawlak發(fā)表經(jīng)典論文“Rough Sets”，標(biāo)志著該理論正式誕生。 1991年，Z.Pawlak的第一本關(guān)于粗糙集理論的專著Rough sets：theoretical aspect

2、s of reasoning about data。,1992年，Slowinski主編的Intelligence decision support：handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理論的基礎(chǔ)，有力地推動(dòng)了國際粗糙集理論與應(yīng)用的深入研究。 1992年，在波蘭召開了第一屆國際粗糙集理論研討會(huì)，有15篇論文發(fā)表在1993年第18卷的 Foundation of computingand decision sciences上。 1995年，Z.Pawlak等人在ACM Communications

3、上發(fā)表“Rough sets”，極大地?cái)U(kuò)大了該理論的國際影響。 19961999年，分別在日本、美國、美國、日本召開了第47屆粗糙集理論國際研討會(huì)。,目前，粗糙集理論受到了國際上越來越多的學(xué)者的關(guān)注，不僅在數(shù)學(xué)上具有獨(dú)立的地位，并發(fā)展出Rough代數(shù)學(xué)、Rough邏輯學(xué)等，而且在智能數(shù)據(jù)分析、知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘中得到廣泛的研究和應(yīng)用。,9.1.2 粗糙集理論的特點(diǎn),粗糙集理論是一種數(shù)據(jù)分析工具。 粗糙集理論不需要先驗(yàn)知識(shí)。 粗糙集理論是一種軟計(jì)算方法。,9.1.3 粗糙集理論在數(shù)據(jù)挖掘中的應(yīng)用,在數(shù)據(jù)預(yù)處理過程中，粗糙集理論可以用于對(duì)特征更準(zhǔn)確的提取 在數(shù)據(jù)準(zhǔn)備過程中，利用粗糙集理論的數(shù)據(jù)約簡

4、特性，對(duì)數(shù)據(jù)集進(jìn)行降維操作。 在數(shù)據(jù)挖掘階段，可將粗糙集理論用于分類規(guī)則的發(fā)現(xiàn)。 在解釋與評(píng)估過程中，粗糙集理論可用于對(duì)所得到的結(jié)果進(jìn)行統(tǒng)計(jì)評(píng)估。,9.2 粗糙集理論中的基本概念,9.2.1 集合的基本概念,定義9.1 設(shè)R是集合U中的二元關(guān)系，若R是自反的、對(duì)稱的和傳遞的，則稱R是等價(jià)關(guān)系。,定義9.2 設(shè)R是非空集合U中的等價(jià)關(guān)系，對(duì)于任一確定的xU，均可構(gòu)造一個(gè)U的子集xR。稱為由x生成（或以x為代表元素）的R等價(jià)類： xR=y | yX且x R y 由此定義可知，集合U中與x有等價(jià)關(guān)系R的所有元素構(gòu)成的集合就是xR。 等價(jià)關(guān)系也稱為不可分辨關(guān)系，也就是說，x1xR，x2xR，則x1和x

5、2相對(duì)于等價(jià)關(guān)系R來說是不可分辨的。,定義9.3 設(shè)R是非空集合U中的等價(jià)關(guān)系。由U的各元素生成的R等價(jià)類所構(gòu)成的集合xR | xU，稱為U關(guān)于R的商集。記作U/R。,【例9.1】集合A=1，2，3，4，有二元關(guān)系： R1=(1，1)，(2，2)，(3，3)，(4，4)，(2，3)，(3，2)，(3，4)，(4，3)，(2，4)，(4，2)， R2=(1，1)，(2，2)，(3，3)，(4，4)，(1，2)，(2，1)，(1，3)，(3，1)，(2，3)，(3，2)， 顯然R1和R2都是A上的等價(jià)關(guān)系。,【例9.2】 在例9.1中，則有： A/R1=1，2，3，4， A/R2=1，2，3，4。

6、,定義9.4 設(shè)U是非空集合。A=A1，A2，Am，其中集合AiU且Ai（i1，2，m）且=U，則稱A是U的覆蓋。,定義9.5 設(shè)A是U的覆蓋，且滿足AiAj=（ij），則稱A是U的劃分。A的任一元素ai，都稱為A的一個(gè)類或劃分的一個(gè)塊。,R1關(guān)系的劃分,R2關(guān)系的劃分,定義9.6 設(shè)A=A1，A2，Am與B=B1，B2，Bn是非空集合U的兩種劃分。如果對(duì)于劃分B的每一個(gè)類Bi，都存在劃分A的一個(gè)類Aj，使得BiAj，則稱B是A的細(xì)分。,定義9.7 設(shè)A=A1，A2，Am與B=B1，B2，Bn是非空集合U的兩種劃分，若U的劃分C滿足： （1）C是A和B的細(xì)分； （2）稱C是劃分A和B的積，記為

7、C=AB。且C=AB=AiBj | i=1，2，m，j=1，2，n，AiBj。,R1關(guān)系的劃分,R2關(guān)系的劃分,R1R2關(guān)系的劃分,9.2.2 信息系統(tǒng)和粗糙集,定義9.8 信息系統(tǒng)I可以形式化表達(dá)為四元組I=(U，A，V，f)，其中，U為對(duì)象非空有限集合，稱為論域，U中每個(gè)元素唯一標(biāo)識(shí)一個(gè)對(duì)象； A為屬性的非空有限集合，A=A1，A2，Am； V=Vi，Vi是屬性Ai的值域； f：UAV是一個(gè)信息函數(shù)，它為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值，即aA，xU，f(x，a)Va。,信息系統(tǒng)也稱為知識(shí)表達(dá)系統(tǒng)或信息表，可以簡記為I=（U，A），,如表9.1所示的是一個(gè)積木信息表I1，其中，U=1，2，

8、3，4，5，6，7，8，A=顏色，形狀，大小，U=1，2，3，4，5，6，7，8。A=顏色，形狀，大小。V顏色=紅色，藍(lán)色，黃色，V形狀=圓形，方形，三角形，V大小=大，小。信息函數(shù)f對(duì)應(yīng)該關(guān)系表。,定義9.9 設(shè)I=（U，A）是一個(gè)信息系統(tǒng)，對(duì)于PA， xi、 xj U，定義二元關(guān)系INDP稱為等價(jià)關(guān)系：,稱對(duì)象xi、 xj在信息系統(tǒng)I中關(guān)于屬性集P是等價(jià)的，當(dāng)且僅當(dāng)p(xi)=p(xj)對(duì)所有的pP 成立，即xi、 xj不能用P 中的屬性加以區(qū)別。 例如，表9.1中，對(duì)象4和8關(guān)于屬性集顏色，形狀是等價(jià)的，因?yàn)樗鼈兊念伾鶠椤八{(lán)色”、形狀均為“三角形”。,實(shí)際上，信息系統(tǒng)I中每個(gè)屬性或者屬

9、性子集都可以對(duì)所有的對(duì)象產(chǎn)生劃分，也就是說可以將A中一個(gè)屬性或者屬性子集看成是一個(gè)等價(jià)關(guān)系。從中看到，等價(jià)關(guān)系體現(xiàn)出一種分類能力，所以說等價(jià)關(guān)系就是一種知識(shí)。 粗糙集理論就是建立在分類機(jī)制的基礎(chǔ)上的，它將分類理解為在特定空間上的等價(jià)關(guān)系，而等價(jià)關(guān)系構(gòu)成了對(duì)該空間的劃分。,定義9.10 設(shè)I=（U，A）是一個(gè)信息系統(tǒng)，使用等價(jià)關(guān)系R對(duì)U進(jìn)行劃分，產(chǎn)生的等價(jià)類集合稱為關(guān)于U的知識(shí)庫，記為K = (U，R)，其中每個(gè)等價(jià)類稱為知識(shí)庫K的知識(shí)。,由此可見，一個(gè)信息系統(tǒng) I=（U，A），可以看作是一個(gè)知識(shí)庫K=（U，A），若PA且P，則P（P中所有等價(jià)關(guān)系的交集）也是一個(gè)等價(jià)關(guān)系，P上的不可分辨關(guān)系IN

10、D(P)由以下等價(jià)類構(gòu)成：,或者說：,【例9.4】 對(duì)于表9.1所示的信息表I1，定義這樣的三個(gè)等價(jià)關(guān)系：R1=顏色，R2=形狀，R3=大小，則： U/R1=1，3，7，2，4，5，6，8，對(duì)應(yīng)知識(shí)庫為K1=（U，R1） U/R2=1，5，2，6，3，4，7，8，對(duì)應(yīng)知識(shí)庫為K2=（U，R2） U/R3=2，7，8，1，3，4，5，6，對(duì)應(yīng)知識(shí)庫為K3=（U，R3）,而U/R1，R2，R3=U/R1U/R2U/R3=1，2，3，4，5，6，7，8。 所以說U/R1、U/R2和U/R3中的每個(gè)等價(jià)類是知識(shí)庫K=(U，R1，R2，R3)中的初等概念。,基于R1的初等概念如下：,1，3，7：紅色積木

11、 2，4：藍(lán)色積木 5，6，8：黃色積木,基于R2的初等概念如下：,1，5：圓形積木 2，6：方形積木 3，4，7，8：三角形積木,基于R3的初等概念如下：,2，7，8：大積木 1，3，4，5，6：小積木,基本概念是初等概念的交集。基于R1，R2的基本概念如下：,1，3，71，5=1：紅色圓形積木 1，3，73，4，7，8=3，7：紅色三角形積木 2，42，6=2：藍(lán)色方形積木 2，43，4，7，8=4：藍(lán)色三角形積木 5，6，81，5=5：黃色圓形積木 5，6，82，6=6：黃色方形積木 5，6，83，4，7，8=8：黃色三角形積木,由U/R1、U/R2的初等概念構(gòu)成U/R1，R2的基本概念

12、如下圖所示。,定義9.11 設(shè)K=（U，R）是一個(gè)知識(shí)庫，對(duì)于一個(gè)集合XU，當(dāng)X能表達(dá)成某些基本等價(jià)類（初等概念）的并集時(shí)，稱為可定義的；否則稱為不可定義的。 R可定義集X能在這個(gè)知識(shí)庫中被精確地定義，所以又稱X為R精確集。R不可定義集X不能在這個(gè)知識(shí)庫中被精確定義，只能通過集合逼近的方式來刻畫，因此也稱X為R粗糙集。,例如，一個(gè)知識(shí)庫為（U，R），并有U/R=1，4，8，2，5，7，3，6。 則集合X=2，3，5，7是R精確集，因?yàn)?，5，73=X，而2，5，7和3均為知識(shí)庫中的知識(shí)； 而集合Y=1，7是R粗糙集，因?yàn)椴荒苡蒛/R中任何等價(jià)類通過并集得到。,定義9.12 設(shè)K=（U，R）是一

13、個(gè)知識(shí)庫，對(duì)于一個(gè)集合XU，則：,集合X的R下近似（集）定義為：R_(X)=yiU/R | yiX 集合X的R上近似（集）定義為：R-(X)=yiU/R | yiX 集合X的R邊界域：BNR(X)= R-(X)-R_(X) 集合X的R正域：POSR(X)=R_(X) 集合X的R負(fù)域：NEGR(X)=U-R-(X),集合X是R精確的，當(dāng)且僅當(dāng)R-(X)=R_(X)。集合X是R粗糙的，當(dāng)且僅當(dāng)R-(X)R_(X)。,粗糙集中相關(guān)概念的示意圖,【例9.5】 設(shè)論域U=1，2，3，4，5，6，7，8，U上有R1、R2和R三個(gè)等價(jià)關(guān)系，且R=R1R2： U/R1=1，2，3，4，5，6，7，8 U/R2

14、=1，2，3，4，5，6，7，8 問集合X=2，3，6，7，8關(guān)于R是否是精確的？如果不是，則求出相應(yīng)的上近似、下近似、邊界域和負(fù)區(qū)域。,由R=R1R2，可求出： U/R=U/R1，R2=1，2，3，4，5，6，7，8 因?yàn)閄無法用U/R的等價(jià)類并集精確表示，所以X關(guān)于R是U上的一個(gè)粗糙集。 X的下近似集為： R_(X)=6，7，8 X的上近似集為： R-(X)=1，23，46，7，8=1，2，3，4，6，7，8 X的邊界域： BNR(X)= R-(X)-R_(X)=1，2，3，4 X的負(fù)區(qū)域： NEGR(X)=U-R-(X)=5,定義9.13 設(shè)K=（U，R）是一個(gè)知識(shí)庫，對(duì)于U中的兩個(gè)集合

15、X和Y，當(dāng)R_(X)= R_(Y)時(shí)，稱集合X、Y為R下相等；當(dāng)R-(X)= R-(Y)時(shí)，稱集合X、Y為R上相等。 粗相等關(guān)系拓展了傳統(tǒng)的相等關(guān)系，描述了任何不可分辨關(guān)系R的粗等價(jià)情況。,9.2.3 分類的近似度量,定義9.14 設(shè)K=（U，R）是一個(gè)知識(shí)庫，對(duì)于U中的非空集合X，由等價(jià)關(guān)系R描述X的精確度定義為：,顯然，0dR(X)1。 如果dR(X)=1，則稱集合X相對(duì)于R是精確的，此時(shí)，X的R邊界域?yàn)榭?，X為全部R可定義的。 如果dR(X)1，則稱集合X相對(duì)于R是粗糙的。 如果dR(X)=0，則集合X是全部R不可定義的。,可用另一形式即X的R粗糙度rR(X)來定義X的不確定義，即：,X

16、的R粗糙度rR(X)與精確度dR(X)恰恰相反，它反映用R的類價(jià)類描述集合X的不完全程度。,【例9.6】設(shè)知識(shí)庫K=（U，R），其中論域U=1，2，3，4，5，6，7，8，等價(jià)關(guān)系R為： U/R=1，4，8，2，5，7，3，6 計(jì)算以下集合的精確度和粗糙度。 （1）X1=1，4，5 （2）X2=3，5 （3）X3=3，6，8,其求解過程如下：,（1）對(duì)于集合X1=1，4，5，求得上、下近似如下： R-(X1)=1，4，82，5，7=1，2，4，5，7，8， R_(X1)= 則=0，rR(X1)=1- dR(X1)=1。,（2）對(duì)于集合X2=3，5，求得上、下近似如下： R-(X2)=2，5，7

17、3=2，3，5，7， R_(X2)=3 則，rR(X2)=1- dR(X2)=0.75。,（3）對(duì)于集合X3=3，6，8，求得上、下近似如下： R-(X3)=1，4，836=1，3，4，6，8， R_(X3)=3，6 則，rR(X3)=1- dR(X3)=0.25。,9.3 信息系統(tǒng)的屬性約簡,知識(shí)約簡是粗糙集理論的核心內(nèi)容之一。 眾所周知，知識(shí)庫中屬性（知識(shí)）并不是同等重要的，甚至其中有些屬性是冗余的。 所謂屬性約簡，就是在保持知識(shí)庫分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性。,9.3.1 約簡和核,定義9.15 設(shè)K=（U，R）是一個(gè)知識(shí)庫，若rR，即r是R中的一個(gè)屬性，如果有IN

18、D(R)=IND(R-r)或U/R=U/(R-r)成立，則稱r為R中不必要的（或可約去的）；否則稱r為R中必要的。 如果每一個(gè)rR都為R中必要的，則稱R為獨(dú)立的；否則稱R為依賴的。,定義9.16 設(shè)K=（U，R）是一個(gè)知識(shí)庫，若PR，P是獨(dú)立的，且IND(P)=IND(R)，則稱P是R的一個(gè)約簡（Reduct），記為RED(R)。,定義9.17 設(shè)K=（U，R）是一個(gè)知識(shí)庫，R可能有多種約簡，R中所有必要屬性組成的集合稱為R的核（Core），記作CORE(R)。即CORE(R)=RED(R)。,【例9.7】有如表9.2所示的信息表I2，求它的所有約簡和核。,從表中可求得： U/a=1，4，5，

19、2，8，3，6，7 U/b=1，3，5，6，2，4，7，8 U/c=2，5，1，7，8，3，4，6 則： U/a，b=1，2，8，3，4，5，6，7 U/b，c=1，2，3，4，5，6，7，8 U/a，c=1，2，3，4，5，6，7，8 U/R=R/a，b，c=1，2，3，4，5，6，7，8,考慮除掉屬性a，則U/(R-a)= U/b，c=1，2，3，4，5，6，7，8，由于U/RU/(R-a)，所以屬性a是不可省略的。 考慮除掉屬性b，則U/(R-b)= U/a，c=1，2，3，4，5，6，7，8，由于U/RU/(R-b)，屬性b是可省略的。 考慮除掉屬性c，則U/(R-c)= U/a，b=

20、1，2，8，3，4，5，6，7，由于U/R=U/(R-c)，所以屬性c是不可省略的。,則有RED(R)=a，c，CORE(R)=a，c。約簡后的信息表如表9.3所示，兩者的數(shù)據(jù)量不同，但分類能力是相同的。,屬性約簡,9.3.2 分辨矩陣求核,定義9.18 設(shè)I=（U，A）是一個(gè)信息系統(tǒng)，設(shè)U=x1，x2，xn，A=a1，a2，am，對(duì)應(yīng)的分辨矩陣M=dij | i=1n，j=1m，其中dij定義如下：,dij=當(dāng)i=j時(shí) dij=ak當(dāng)ij，且xi和xj在屬性ak上取值不相同時(shí),從中看到，dij是區(qū)分對(duì)象xi和xj的所有屬性的集合。由于分辨矩陣M是一個(gè)nn的對(duì)稱矩陣，通常僅考慮下三角或上三角部

21、分。,【例9.8】求如表9.2所示信息表的分辨矩陣M。,定義9.19 設(shè)I=（U，A）是一個(gè)信息系統(tǒng)，對(duì)于分辨矩陣M=dij | i=1n，j=1m，定義分辨函數(shù)f(M)如下：,也就是說，分辨函數(shù)f(M)表示為辨矩陣M中的所有元素的合取式。 分辨函數(shù)f(M)具有這樣的性質(zhì)：它的極小析取范式中的所有合取式是屬性集A的所有約簡。 換句話說，約簡是滿足能區(qū)別由整個(gè)屬性集區(qū)別的所有對(duì)象的屬性的極小子集。,而核是分辨矩陣M中所有單個(gè)元素組成的集合，即：,CORE(A)=aA | dij=a且xi、xjU,【例9.9】對(duì)于如表9.2所示的信息表，采用分辨矩陣的方法求它的所有約簡和核。,分辨矩陣M，其中的單

22、個(gè)元素為a、c，所以有 CORE(A)=a，c 其分辨函數(shù) f(M)=(abc)(ac)(bc)(abc)=ac。 所以只有一個(gè)約簡a，c。,有關(guān)信息系統(tǒng)的屬性約簡和屬性值約簡算法這里不再介紹，主要在后面討論決策表的屬性約簡和屬性值約簡算法。,9.4 決策表及其屬性約簡,9.4.1 決策表及相關(guān)概念,定義9.20 設(shè)I=（U，A，V，f）是一個(gè)信息系統(tǒng)，又設(shè)C、DA是屬性集A的兩個(gè)子集，分別稱C和D為A的條件屬性集和決策屬性集，這樣將I改寫成T=（U，C，D，V，f）或簡寫為T=（U，C，D），則T稱為決策表。,也就是說，在信息系統(tǒng)上指定條件屬性集C和決策（類別或結(jié)論）屬性集D，這樣就構(gòu)成了決

23、策表。IND(C)的等價(jià)類稱為條件類，IND(D)的等價(jià)類稱為決策類，它們都是U的知識(shí)。,定義9.21 給定決策表T=(U，C，D)，定義D的C正域POSC(D)為：,實(shí)際上，D的C正域就是等價(jià)類U/D關(guān)于C的正域，即U/C表達(dá)的知識(shí)能夠確定地劃入U(xiǎn)/D類的對(duì)象的集合，它可由所有包含于D的C分類的基本集合的并集來計(jì)算。,【例9.10】對(duì)于如表9.4所示的決策表T1，C=頭疼，肌肉疼，體溫，D=流感，求POSC(D)。,U/D=1，4，5，2，3，6，設(shè)X1=1，4，5，X2=2，3，6 U/C=1，2，3，4，5，6 C_(X1)=145=1，4，5，即U/C的類價(jià)類準(zhǔn)確地分類 到X1中的對(duì)象

24、集合 C_(X2)=236=2，3，6，即U/C的類價(jià)類準(zhǔn)確地分類 到X2中的對(duì)象集合 則POSC(D)= C_(X1)C_(X2)=1，2，3，4，5，6=U。,定義9.22 給定決策表T=(U，C，D)，令：,稱知識(shí)D依賴于知識(shí)C的依賴度為k。 依賴度k反映了根據(jù)知識(shí)C將對(duì)象分類到知識(shí)D的基本概念中去的能力：,當(dāng)k=1時(shí)，稱知識(shí)D完全依賴于知識(shí)C，記為C D。 當(dāng)0k1時(shí)，稱知識(shí)D部分依賴于知識(shí)C。 當(dāng)k=1時(shí)，稱知識(shí)D完全獨(dú)立于知識(shí)C。,【例9.11】對(duì)于如表9.4所示的決策表，求依賴度rC(D)。,上例已求出POSC(D)=U，所以,定義9.23 設(shè)T = ( U，C，D) 是一個(gè)決策

25、表，如果有： POSC(D)=U 則決策表T是協(xié)調(diào)的或一致的；否則稱T為不協(xié)調(diào)的決策表。,對(duì)于不協(xié)調(diào)的決策表，不能由條件屬性導(dǎo)出結(jié)論屬性之間的關(guān)系，應(yīng)將其分解為完全協(xié)調(diào)和完全不協(xié)調(diào)的兩個(gè)決策表。,定義9.24 設(shè)T = ( U，C，D) 是一個(gè)協(xié)調(diào)的決策表，屬性rRC，R是條件屬性集C的一個(gè)子集。如果r滿足條件：,POSR(D)=POSR-r(D),那么屬性r是條件屬性子集R中相對(duì)于決策屬性集D的不必要屬性或冗余屬性，否則稱屬性r是R中相對(duì)于決策屬性D的必要屬性。 如果RC且R中的每一個(gè)屬性r都是R中相對(duì)于決策屬性集D的必要屬性，那么R稱為相對(duì)于決策屬性集D是獨(dú)立的；否則，R稱為相對(duì)于決策屬性

26、集D是依賴的。,定義9.25 設(shè)T = ( U，C，D) 是一個(gè)協(xié)調(diào)的決策表，RC且R，如果有： （1）POSR(D)=POSC(D)。 （2）R相對(duì)于決策屬性集D而言是獨(dú)立的。 那么R是條件屬性集C相對(duì)于決策屬性集D而言的一個(gè)約簡。,條件屬性集合C中的所有相對(duì)于決策屬性集D的必要屬性的集合稱為條件屬性集合C相對(duì)于決策屬性集D的核，記作COREC(D)。 與信息系統(tǒng)一致，由決策表確定的核是唯一的，但約簡可能不止一個(gè)，根據(jù)約簡和核的定義可知，約簡和核之間存在如下關(guān)系： COREC(D)=REDC(D),ROSE2是波蘭Poznan科技大學(xué)開發(fā)的一個(gè)粗糙集數(shù)據(jù)分析器，該系統(tǒng)提供了數(shù)據(jù)預(yù)處理（數(shù)據(jù)離

27、散化、缺省值補(bǔ)齊）、屬性約簡、規(guī)則生成和有效性分析的多種算法。 下面通過一個(gè)示例說明由用戶設(shè)置的決策表來產(chǎn)生核、約簡和規(guī)則的過程。,設(shè)置條件屬性a,設(shè)置決策屬性e,一個(gè)決策表,求出的核,求出的所有約簡,產(chǎn)生決策表的規(guī)則,9.4.2 決策表的屬性約簡算法,1. 一般屬性約簡算法,該算法是一種最簡單的粗糙集屬性約簡算法，檢查條件屬性集C是否滿足獨(dú)立性條件。 如果在C中發(fā)現(xiàn)不滿足獨(dú)立性條件的屬性，則刪除該屬性，并對(duì)刪除該屬性后所得的條件屬性子集重新檢查獨(dú)立性條件，直至條件屬性子集中的所有屬性均滿足獨(dú)立性條件為止。,輸入：決策表T=（U，C，D） 輸出：決策表T的一個(gè)相對(duì)約簡R 方法：其過程描述如下：

28、,B=C，R=; for (rB-R) if (POSB-r(D)=POSB(D)/說明屬性r相對(duì)決策屬性D是不必要的 B=B-r; else/說明屬性r相對(duì)決策屬性D是必要的 R=Rr; if (B=R) brerk;/B=R時(shí)退出循環(huán)，算法結(jié)束 ,【例9.14】設(shè)決策表T4=（U，C，D）如表9.9所示。采用一般屬性約簡算法求屬性約簡R。,令B=C=a，b，c，d，R=。 在B-R=a，b，c，d中選擇一個(gè)屬性，假如選取屬性d，求得： U/B=1，2，3，4， U/D=1，2，3，4， U/(B-d)=U/a，b，c=1，2，3，4， POSB(D)=1，2，3，4， POSB-d(D)=

29、1，2，3，4， 所以有：POSB(D)= POSB-d(D) 則：B=B-d=a，b，c，R=。, 在B-R=a，b，c中選擇一個(gè)屬性，假如選取屬性b，求得： U/B=U/a，b，c=1，2，3，4， U/D=1，2，3，4， U/(B-b)=U/a，c=1，2，3，4， POSB(D)=1，2，3，4， POSB-b(D)=1，2，3，4， 所以有：POSB(D)= POSB-b(D) 則：B=B-b=a，c，R=。, 在B-R=a，c中選擇一個(gè)屬性，假如選取屬性a，求得： U/B=U/a，c=1，2，3，4， U/D=1，2，3，4， U/(B-a)=U/c=1，2，3，4， POSB(

30、D)=1，2，3，4， POSB-a(D)=1， 所以有：POSB(D) POSB-a(D) 則：B=a，c，R=Ra=a。, 在B-R=c中選擇一個(gè)屬性，只能選取屬性c，求得： U/B=U/a，c=1，2，3，4， U/D=1，2，3，4， U/(B-c)=U/a=1，3，4，2， POSB(D)=1，2，3，4， POSB-c(D)=2， 所以有：POSB(D) POSB-c(D) 則：B=a，c，R=Rc=a，c。 此時(shí)B=R，算法結(jié)束，R=a，c是決策表的一個(gè)約簡。,2. 基于Pawlak屬性重要度的屬性約簡算法,為了度量某個(gè)條件屬性相對(duì)于決策屬性的重要性，或者說是該屬性在整個(gè)決策表中

31、的作用，粗糙集理論采用的方式是依次從決策表中刪除該屬性，然后觀察該屬性被刪除之后，整個(gè)決策表的分類能力有沒有發(fā)生變化，發(fā)生變化的幅度是多大。 如果變化越大，則說明，所刪除的屬性對(duì)原始決策表就越重要，反之，如果變化很小，說明所刪除屬性對(duì)原始決策表而言就不是很重要。,定義9.26 設(shè)T = ( U，C，D) 是一個(gè)協(xié)調(diào)的決策表，rC，該屬性對(duì)條件屬性全集C相對(duì)于決策屬性D的重要度定義為：,BC，C-B，條件屬性對(duì)條件屬性集B相對(duì)于決策屬性D的重要度定義為：,下面是基于Pawlak屬性重要度的決策表的屬性約簡算法：,輸入：決策表T=（U，C，D） 輸出：決策表T的一個(gè)相對(duì)約簡B 方法：其過程描述如下

32、：,計(jì)算C相對(duì)于D的核COREC(D); B=COREC(D); while (POSB(D)POSC(D) for (對(duì)于C-B中的屬性ci) 計(jì)算： 求cm=arg max sig(ci，B；D); 若同時(shí)存在多個(gè)屬性滿足最大值，則從中選取一個(gè)與B的屬性值組合數(shù)最少的屬性作為cm; B=Bcm; ,【例9.15】對(duì)于如表9.9所示的決策表T4，采用基于Pawlak屬性重要度的屬性約簡算法求相對(duì)屬性約簡R。 求解過程如下：, 計(jì)算核。 U/C=1，2，3，4 U/D=1，2，3，4 U/(D-a)=U/b，c，d=1，2，3，4 U/(D-b)=U/a，c，d=1，2，3，4 U/(D-c)

33、=U/a，b，d=1，4，2，3 U/(D-d)=U/a，b，c=1，2，3，4 POSC(D)=1，2，3，4 POSC-a(D)= 1，2，3，4= POSC(D) POSC-b(D)= 1，2，3，4= POSC(D) POSC-c(D)= 2，3POSC(D) POSC-d(D)= 1，2，3，4= POSC(D) 所以條件屬性c是決策表的核值屬性，即COREC(D)=c。, 令B=COREC(D)=c，POSB(D)=1POSC(D)，對(duì)于C-B=a，b，d中的每個(gè)屬性ci有其重要度：,U/D=1，2，3，4 U/B=1，2，3，4 U/a，c=1，2，3，4 U/b，c=1，3，2

34、，4 U/d，c=1，2，3，4 POSB(D)=1 POSBa(D)=POSa，c(D)=1，2，3，4 POSBb(D)=POSb，c(D)=1，3 POSBd(D)=POSd，c(D)=1，2，3，4,現(xiàn)在取cm=arg max sig(ci，B；D)，可選的屬性有a和d，所以B=a，c或d，c，而POSa，c(D)=POSC(D)或者，POSd，c(D)=POSC(D)均成立，所以算法結(jié)束。 輸出的約簡為B=a，c或d，c。,3. 基于分辨矩陣的決策表屬性約簡算法,定義9.27 設(shè)T = ( U，C，D) 是一個(gè)協(xié)調(diào)的決策表，設(shè)U=x1，x2，xn，A=a1，a2，am，對(duì)應(yīng)的分辨矩陣

35、M=dij | i=1n，j=1m。由于分辨矩陣M是一個(gè)nn的對(duì)稱矩陣，通常僅考慮下三角或上三角部分。其中dij定義如下：,dij=ak當(dāng)xi和xj在D上屬性值不相同且xi和xj在 屬性ak上取值不相同時(shí) dij=當(dāng)xi和xj在D上屬性值不相同且xi和xj在 C上所有屬性值相同時(shí) dij=-當(dāng)xi和xj在D上所有屬性值均相同時(shí),【例9.16】對(duì)于如表9.9所示的決策表T4，求其分辨矩陣M。,定義9.28 設(shè)T = ( U，C，D) 是一個(gè)協(xié)調(diào)的決策表，對(duì)于分辨矩陣M=dij | i=1n，j=1m，定義分辨函數(shù)f(M)如下：,也就是說，分辨函數(shù)f(M)表示為辨矩陣M中的所有元素的合取式。分辨函

36、數(shù)f(M)具有這樣的性質(zhì)：它的極小析取范式中的所有合取式是C相對(duì)于D的所有約簡。 而核是分辨矩陣M中所有單個(gè)元素組成的集合，即： COREC(D)=aC | dij=a且xi、xjU,下面給出基于分辨矩陣的決策表屬性約簡算法：,輸入：決策表T=（U，C，D） 輸出：決策表T的所有相對(duì)約簡REDC(D) 方法：其過程描述如下：,計(jì)算決策表T的分辨矩陣M; 對(duì)于分辨矩陣M中所有取值非空集合的元素dij（dij且dij-），建立相應(yīng)的析取值Lij; 對(duì)所有析取式Lij進(jìn)行合取運(yùn)算，得到一個(gè)合取范式L，即 將合取范式L轉(zhuǎn)換為析取范式形式，得 輸出REDC(D)=Lk;,【例9.17】對(duì)于如表9.9所示

37、的決策表T4，采用分辨矩陣的方法求它的所有相對(duì)屬性約簡和核。 上例已求該信息表的分辨矩陣M，其中的單個(gè)元素只有c，所以有COREC(D)= c。 其分辨函數(shù)f(M)=(bc)c(abd)(ad) =c(ad)=(ca)(cd)。 所以決策表T4有兩個(gè)相對(duì)約簡即a，c和c，d。,4. 基于信息增益的屬性約簡算法,該算法以信息增益值作為啟發(fā)信息，每次選取信息增益值最大的條件屬性，直到找到一個(gè)約簡為止。,輸入：決策表T=（U，C，D） 輸出：決策表T的一個(gè)相對(duì)約簡B 方法：其過程描述如下：, 計(jì)算C相對(duì)于D的核COREC(D); 令B= COREC(D) ，如果POSB(D)=POSC(D)，轉(zhuǎn);

38、任意屬性rC-B，計(jì)算屬性信息增益G(C，r)=E(C)-E(C，r)， 求得G(C，r最大的屬性r; 若同時(shí)存在多個(gè)屬性滿足最大值，則從中選取一個(gè)與B的屬性值組合數(shù)最少的屬性作為r; 令B=Br; 如果POSB(D) POSC(D)，轉(zhuǎn)；否則轉(zhuǎn); 輸出，算法結(jié)束。,9.5 決策表的值約簡及其算法,屬性約簡只是在一定程度上去掉了決策表中冗余屬性，還是沒有充分去掉決策表中的冗余信息。在判斷某個(gè)對(duì)象屬于某類時(shí)，其屬性的取值不同，對(duì)分類產(chǎn)生的影響也不同。 例如，判斷人的體形（瘦、中、胖）時(shí)，體重是主要屬性。但若體重屬性值為75kg時(shí)，此人的體形要結(jié)合其身高、性別等屬性才能確定； 如果體重屬性值為16

39、0kg時(shí)，幾乎肯定其體形為胖，這時(shí)身高、性別已不重要，也就是說身高、性別的屬性值是冗余的。 值約簡是屬性值約簡的簡稱，其目標(biāo)就是刪除這些冗余的屬性值并產(chǎn)生決策表的決策規(guī)則。,9.5.1 決策規(guī)則及其簡化,定義9.29 設(shè)決策表T=（U，C，D）是協(xié)調(diào)的，對(duì)于xU，通常將決策規(guī)則rx描述成如下形式： rx： rx|Crx|D或 其中和分別稱為決策規(guī)則rx的因（或前件）和果（或后件），也叫做CD決策規(guī)則，簡稱為規(guī)則。 為了簡便，在、中，基本項(xiàng)用av表示屬性a取值為v，而、是由基本項(xiàng)邏輯與/或組成的。,定義9.30 設(shè)是決策表T上的一條決策規(guī)則，條件屬性值av（aC，av表示存在a=v的基本項(xiàng)）是可

40、被約去的（或可省略的，或av是冗余的），當(dāng)且僅當(dāng)()(-av)；否則稱條件屬性值av在該規(guī)則是必要的。,一條規(guī)則的某個(gè)條件屬性值可被約去當(dāng)且僅當(dāng)約去后仍然保持規(guī)則的一致性。 所謂規(guī)則的一致性，是指條件屬性值均相同的規(guī)則，其結(jié)論屬性值也必須相同；否則稱為不一致或沖突。,例如，有表9.12所示的決策表T6，對(duì)于第1條規(guī)則a1b0c2d1e1，其中a1是不必要的，因?yàn)閯h除a1后，b0c2d1e1是一致的，也就是說，a1b0c2d1e1b0c2d1e1。,沒有沖突,定義9.31 規(guī)則中所有必要的條件屬性值構(gòu)成的集合稱為該規(guī)則的核，記為CORE()。,【例9.19】對(duì)于如表9.12所示的決策表T6，求所

41、有規(guī)則的核值。 利用定義9.29求決策表T6中所有規(guī)則核值的過程如下。,產(chǎn)生如下決策規(guī)則：,（1）a1b0c2d1e1 （2）a2b1c0 d1e0 （3）a2b1c2 d0e2 （4）a1b2c2 d1e1 （5）a1b2c0 d0e2,求決策規(guī)則的核,（1）a1b0c2d1e1 有a1c2 d1e1 ，a1b0 d1e1 ，b0c2 d1e1，核為空。,除去屬性b,除去屬性c,除去屬性a,（2）a2b1c0 d1e0,a2b0 d1e0 ，b1c0 d1e0 ，a2b1 d1e0 ，核為c0,除去屬性b,除去屬性a,除去屬性c,最后得到僅包含決策規(guī)則的核值如下：,定義9.32 對(duì)于決策表T

42、=（U，C，D），xU，aCD，定義類集xa為U中所有a屬性值與x對(duì)象a屬性值相同的對(duì)象集合。若B CD，則,例如，對(duì)于表9.12所示的決策表T6，1a=1，4，5，1c=1，3，4，則1a，c=1，4，51，3，4=1，4。,定義9.33 對(duì)于決策表T=（U，C，D），設(shè)rx是一條進(jìn)行屬性約簡后的規(guī)則，條件屬性集C的等價(jià)類xC中： 任何最少屬性a的等價(jià)類xa的交集相應(yīng)決策類xD 則由此而得到的最小條件屬性a組成的相應(yīng)于rx的新規(guī)則rx稱為rx的一個(gè)規(guī)則約簡。,對(duì)于第一條：決策類1d,e=1,4; 1a=1,4,5，1b=1,4,5，1c=1,3,4 顯然：1a 1d,e，1c 1d,e， 但

43、有：1b 1d,e，1a 1b=1,4 1d,e 所以得到兩條約簡的決策規(guī)則： 1：b0 d1e11：a1c2 d1e1,【例9.20】對(duì)于如表9.12所示的決策表T6，求所有規(guī)則的約簡。,得到所有約簡的決策規(guī)則：,9.5.2 決策規(guī)則的極小化,在前面介紹的方法產(chǎn)生的規(guī)則中，有些規(guī)則不是必要的，更確切地說，和相同決策類相結(jié)合的一些過剩的規(guī)則應(yīng)該消去，而不影響規(guī)則的決策能力。,定義9.34 記F為所有具有后件的基本規(guī)則的集合，用P表示F中規(guī)則的所有前件的集合。 如果P=(P-)，則基本規(guī)則是可約去的，其中P表示P中所有基本項(xiàng)的析取，也可以看成是滿足P中基本項(xiàng)條件的記錄的并集；否則該規(guī)則是不能被約

44、去的。 如果F中所有規(guī)則都是不能被約去的，則它稱為獨(dú)立的，也就是極小化規(guī)則約簡。,【例9.21】對(duì)于如表9.15所示的決策表T7，其中，C=a，b，c，d，D=e，求其極小規(guī)則約簡。, 先通過上一節(jié)介紹的屬性約簡算法求出其屬性約簡REDC(D)=a，b，d。則刪除條件屬性c及該列后得到如表9.16所示的決策表T71。,r1：a1b0d1e1 r2：a1b0d0e1 r3：a0b0d0e0 r4：a1b1d1e0 r5：a1b1d2e2 r6：a2b1d2e2 r7：a2b2d2e2, 求決策表T71的所有規(guī)則的約簡。它包含的規(guī)則如下：,考慮r1：a1b0d1e1，1e=1，2，1a=1，2，4

45、，5，1b=1，2，3，1d=1，4。有1a1b=1，21e，產(chǎn)生規(guī)則（1）a1b0e1；1b1d=11e，產(chǎn)生規(guī)則（1）b0d1e1，該規(guī)則的核=a1b0b0d1=b0。 考慮r3：a0b0d0e0，3e=3，4，3a=3，3b=1，2，3，3d=2，3。有3a3e，產(chǎn)生規(guī)則（3）a0e0。該規(guī)則的核為a0。 考慮r7：a2b2d2e2，7e=5，6，7，7a=6，7，7b=7，7d=5，6，7。有7a7e，產(chǎn)生規(guī)則（7）a2e2；7b7e，產(chǎn)生規(guī)則（7）b2e2；7c7e，產(chǎn)生規(guī)則（7）d2e2。顯然該規(guī)則的核為空。,最后求出的所有規(guī)則的約簡如表9.17所示。, 求極小規(guī)則約簡 在9.17

46、中，共有3個(gè)決策類（e分別為1、0和2的類）。 對(duì)于e=1的類：,所以該類規(guī)則約簡為：a1b0e1或b0d1a1d0e1。,對(duì)于e=0的類：,所以該類規(guī)則約簡為：a0b1d1e0。,對(duì)于e=2的類：,所以該類規(guī)則約簡為：d2e2。,最后得到以下兩組極小規(guī)則約簡：,a1b0e1 a0b1d1e0 d2e2,b0d1a1d0e1 a0b1d1e0 d2e2,歸納起來，利用屬性約簡后的決策表產(chǎn)生一組極小規(guī)則約簡的算法如下：,輸入：屬性約簡后的決策表T 輸出：一組極小規(guī)則約簡 方法：其過程描述如下：,（1）對(duì)決策表T中每個(gè)記錄的每個(gè)條件屬性a進(jìn)行逐個(gè)考察，刪除該記錄的該屬性值av，有3種可能的情況： 若產(chǎn)生沖突，說明該屬性值是該記錄的核，不能除去，恢復(fù)該屬性值； 若未產(chǎn)生沖突，但決策表T中含有重復(fù)記錄（在不考慮屬性a時(shí)），說明刪除該屬性值不影響該記錄的決策，可以刪除該屬性