粗糙集理論(武漢大學-李春葆)

1、第第9章章 粗糙集理論粗糙集理論 參考書：參考書：1 智能計算，曾黃麟，重慶大學出版社，智能計算，曾黃麟，重慶大學出版社，20042 苗奪謙等，粗糙集理論、算法與應用，清華大學苗奪謙等，粗糙集理論、算法與應用，清華大學出版社，出版社，2008n粗糙集理論是由波蘭華沙理工大學粗糙集理論是由波蘭華沙理工大學Pawlak教授于教授于20世紀世紀80年代初提出的一種研究不完整、不確定知識和數(shù)據(jù)的表達、年代初提出的一種研究不完整、不確定知識和數(shù)據(jù)的表達、學習、歸納的理論方法，它是一種刻畫不完整性和不確定學習、歸納的理論方法，它是一種刻畫不完整性和不確定性的數(shù)學工具，能有效地分析不精確、不一致、不完整等性

2、的數(shù)學工具，能有效地分析不精確、不一致、不完整等各種不完備的信息，還可以對數(shù)據(jù)進行分析和推理，從中各種不完備的信息，還可以對數(shù)據(jù)進行分析和推理，從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律。發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律。n粗糙集在機器學習、決策支持系統(tǒng)、機器發(fā)現(xiàn)、歸納推理、粗糙集在機器學習、決策支持系統(tǒng)、機器發(fā)現(xiàn)、歸納推理、數(shù)據(jù)庫中的知識發(fā)現(xiàn)、模式識別等領域都得到了廣泛的應用。數(shù)據(jù)庫中的知識發(fā)現(xiàn)、模式識別等領域都得到了廣泛的應用。n粗糙集理論逐漸應用于數(shù)據(jù)挖掘領域中，并在對大型數(shù)據(jù)庫粗糙集理論逐漸應用于數(shù)據(jù)挖掘領域中，并在對大型數(shù)據(jù)庫中不完整數(shù)據(jù)進行分析和學習方面取得了顯著的成果，使得中不完整數(shù)據(jù)進行

3、分析和學習方面取得了顯著的成果，使得粗糙集理論及數(shù)據(jù)挖掘的研究成為熱點領域。最近幾年，粗粗糙集理論及數(shù)據(jù)挖掘的研究成為熱點領域。最近幾年，粗糙集理論越來越受到眾多研究人員的重視，它的應用研究得糙集理論越來越受到眾多研究人員的重視，它的應用研究得到了很大的發(fā)展。到了很大的發(fā)展。 n粗糙集方法僅利用數(shù)據(jù)本身提供的信息，無須任何先驗知識。粗糙集方法僅利用數(shù)據(jù)本身提供的信息，無須任何先驗知識。數(shù)據(jù)數(shù)據(jù)規(guī)則規(guī)則精確的數(shù)學方法精確的數(shù)學方法9.1粗糙集基本概念粗糙集基本概念 粗糙集理論是在經(jīng)典集合論基礎上發(fā)展而來的。粗糙集理論是在經(jīng)典集合論基礎上發(fā)展而來的。利用不確定性、不完整的經(jīng)驗知識進行推理。利用不確

4、定性、不完整的經(jīng)驗知識進行推理。知識庫知識庫9.1.1 知識和分類知識和分類 n知識是人類通過實踐對客觀世界的運動規(guī)律的認識，知識是人類通過實踐對客觀世界的運動規(guī)律的認識，是人類實踐經(jīng)驗的總結和提煉，具有是人類實踐經(jīng)驗的總結和提煉，具有抽象和普遍抽象和普遍的特的特性。性。n從認知科學的觀點來看，知識是從認知科學的觀點來看，知識是人類對客觀事物的分人類對客觀事物的分類能力類能力，概念是事物類別的描述或者符號。知識是概，概念是事物類別的描述或者符號。知識是概念之間的關系和聯(lián)系。任何一個物種都是由一些知識念之間的關系和聯(lián)系。任何一個物種都是由一些知識來描述與分類的，利用物種的不同屬性知識描述來產(chǎn)來描

5、述與分類的，利用物種的不同屬性知識描述來產(chǎn)生對物種的不同分類。生對物種的不同分類。1. 知識的分類表達形式知識的分類表達形式集合理論為描述世界中各種事件提供了一個十分集合理論為描述世界中各種事件提供了一個十分有用的基礎，千差萬別的事物都可以用集合論的有用的基礎，千差萬別的事物都可以用集合論的方法加以描述。方法加以描述。知識表達系統(tǒng)采用集合表達知識表達系統(tǒng)采用集合表達。知識分類知識分類利用事件不同的屬性的知識描述，對利用事件不同的屬性的知識描述，對事物可以產(chǎn)生不同的分類事物可以產(chǎn)生不同的分類。 定義，定義， 知識表達系統(tǒng)（知識庫）知識表達系統(tǒng)（知識庫）M可以形式化表達為可以形式化表達為四元組：四

6、元組：M=(U,A,V,f)，其中其中U為對象非空有限集合，稱為論域；為對象非空有限集合，稱為論域；A為屬性的非為屬性的非空有限集合，空有限集合，A=A1,A2,Am；V= Vi，Vi是屬性是屬性Ai的值域；的值域；f：UAV是一個信息函數(shù)，它為每個對象的每個屬性賦是一個信息函數(shù)，它為每個對象的每個屬性賦予一個信息值，即予一個信息值，即 a A，x U，f(x,a) Va。知識表達系統(tǒng)知識表達系統(tǒng)稱為（或稱為（或信息表信息表），其數(shù)據(jù)以關系表的），其數(shù)據(jù)以關系表的形式表示，關系表的行對應要研究的對象，列對應對象的形式表示，關系表的行對應要研究的對象，列對應對象的屬性，對象的信息是通過指定對象的

7、各屬性值來表達。屬性，對象的信息是通過指定對象的各屬性值來表達。一個信息表一個信息表 U顏色顏色R1形狀形狀R2大小大小R31紅色紅色圓形圓形小小2藍色藍色方形方形大大3紅色紅色三角形三角形小小4藍色藍色三角形三角形小小5黃色黃色圓形圓形小小6黃色黃色方形方形小小7紅色紅色三角形三角形大大8藍色藍色三角形三角形大大下面的表是一個信息表的例子，是一個玩具積木下面的表是一個信息表的例子，是一個玩具積木的集合。其中：的集合。其中：U=1,2,3,4,5,6,7,8，A=顏色顏色,形狀形狀,大小大小，V顏色顏色=紅色紅色,藍色藍色,黃色黃色，V形狀形狀=圓形圓形,方形方形,三角形三角形，V大小大小=大

8、大,小小。n定義定義 設設U,討論的對象組成的有限集合，稱為論域討論的對象組成的有限集合，稱為論域（Universe），對于論域中由等價關系劃分出來的任意子集，對于論域中由等價關系劃分出來的任意子集，都可以稱為論域都可以稱為論域U中的一個概念（中的一個概念（concept）或范疇）或范疇（category）。 為規(guī)范起見，認為空集必也是一個概念。論域為規(guī)范起見，認為空集必也是一個概念。論域U中的任中的任意概念族稱為關于論域的抽象知識，它代表了對論域中個體意概念族稱為關于論域的抽象知識，它代表了對論域中個體的分類，簡稱為的分類，簡稱為知識知識。1,3,7就是一個概念紅色積木。就是一個概念紅色積木

9、。1,3,7,2,4,5,6,8就是一個知識按顏色分類。就是一個知識按顏色分類。蘋果蘋果,梨梨,葡萄葡萄,柿子柿子,水果按味道水果按味道分類分類味甘味甘 味澀味澀 概念（共同特點）概念（共同特點）知識知識按顏色分類：按顏色分類：1，3，7：紅色積木：紅色積木2，4：藍色積木：藍色積木5，6，8：黃色積木：黃色積木按形狀分類：按形狀分類：1，5：圓形積木：圓形積木2，6：方形積木：方形積木3，4，7，8：三角形積木：三角形積木按大小分類：按大小分類：2，7，8：大積木：大積木1，3，4，5，6：小積木：小積木換言之，定義了三個等價關系換言之，定義了三個等價關系(即屬性即屬性)：顏色：顏色R1、形

10、狀、形狀R2和大和大小小R3，通過這樣的分類，可以，通過這樣的分類，可以得到以下三個等價類：得到以下三個等價類：U/R1=1,3,7，2,4，5,6,8U/R2=1,5，2,6，3,4,7,8U/R3=2,7,8，1,3,4,5,6這些等價類是知識庫這些等價類是知識庫K=(U,R1,R2,R3)中的初等概念。所以：中的初等概念。所以：基于基于R1的初等概念有：的初等概念有：1,3,7：紅色積木：紅色積木2,4：藍色積木：藍色積木5,6,8：黃色積木：黃色積木基于基于R2的初等概念有：的初等概念有：1,5：圓形積木：圓形積木2,6：方形積木：方形積木3,4,7,8：三角形積木：三角形積木基于基于

11、R3的初等概念有：的初等概念有：2,7,8：大積木：大積木1,3,4,5,6：小積木：小積木U顏色顏色R1形狀形狀R2大小大小R31紅色紅色圓形圓形小小2藍色藍色方形方形大大3紅色紅色三角形三角形小小4藍色藍色三角形三角形小小5黃色黃色圓形圓形小小6黃色黃色方形方形小小7紅色紅色三角形三角形大大8藍色藍色三角形三角形大大基本概念是初等概念的交集?；靖拍钍浅醯雀拍畹慕患；诨赗1,R2的基本概念有：的基本概念有：1,3,71,5=1：紅色圓形積木：紅色圓形積木1,3,73,4,7,8=3,7：紅色三角形積木：紅色三角形積木2,42,6=2：藍色方形積木：藍色方形積木2,43,4,7,8=4

12、：藍色三角形積木：藍色三角形積木5,6,81,5=5：黃色圓形積木：黃色圓形積木5,6,82,6=6：黃色方形積木：黃色方形積木5,6,83,4,7,8=8：黃色三角形積木：黃色三角形積木基于基于R1,R3的基本概念有：的基本概念有：1,3,72,7,8=7：紅色大積木：紅色大積木1,3,71,3,4,5,6=1,3：紅色小積木：紅色小積木2,42,7,8=2：藍色大積木：藍色大積木2,41,3,4,5,6=4：藍色小積木：藍色小積木5,6,82,7,8=8：黃色大積木：黃色大積木5,6,81,3,4,5,6=5,6：黃色小積木：黃色小積木1,4,7找不出共找不出共同特點，不能稱同特點，不能稱

13、為一個概念。為一個概念。2. 不可分辨關系不可分辨關系 n在粗糙集理論中，在粗糙集理論中，“知識知識”被認為是一種分類的能力。被認為是一種分類的能力。不可分辨關系的概念是粗糙集理論的基石，它揭示出不可分辨關系的概念是粗糙集理論的基石，它揭示出論域知識的顆粒狀結構。論域知識的顆粒狀結構。n假定關于論域的某種知識，并使用屬性和屬性值來描假定關于論域的某種知識，并使用屬性和屬性值來描述論域中的對象，如果兩個對象述論域中的對象，如果兩個對象(或對象集合或對象集合)具有相具有相同的屬性和屬性值，則它們之間具有同的屬性和屬性值，則它們之間具有不可分辨關系不可分辨關系。n定義定義設設R是非空集合是非空集合U

14、上的二元系，如果它是自反的、對上的二元系，如果它是自反的、對稱的和可傳遞的，則稱稱的和可傳遞的，則稱R為為U上的等價關系。若上的等價關系。若 則稱則稱x與與y有關系，記為有關系，記為 ；若若 ，則稱，則稱x與與y沒有關系，記為沒有關系，記為 。等價關。等價關系的一個重要特點是用它可以構成系的一個重要特點是用它可以構成U的一個劃分。劃分即是的一個劃分。劃分即是分類，將研究對象分成不同的類，這些類之間互不相交，分類，將研究對象分成不同的類，這些類之間互不相交，且每一對象均包含在某一類中。且每一對象均包含在某一類中。 xRy(x,y) R(x,y) R_x Ry根據(jù)等價關系的定義，同一等價類內的元素

15、是不可分根據(jù)等價關系的定義，同一等價類內的元素是不可分辨的，對信息的處理可以在等價類的粒度上進行，由此可辨的，對信息的處理可以在等價類的粒度上進行，由此可以達到對信息進行簡化的目的。以達到對信息進行簡化的目的。n定義定義 設設U是一個論域，是一個論域，R是是U上的等價關系，上的等價關系，U/R表示表示U上由上由R導出的所有等價類。導出的所有等價類。 表示包含元素表示包含元素xU的的R等價類。一個知識庫就是一等價類。一個知識庫就是一個關系系統(tǒng)個關系系統(tǒng)K，其中其中U是論域，是論域，P是是U上的一個等價類簇。上的一個等價類簇。如果如果 且且 ，則，則 （Q的所有等價類的交也的所有等價類的交也是一個

16、等價關系）稱是一個等價關系）稱Q為為不可分辨關系不可分辨關系,記作記作IND(Q)。QPQQIND(Q)=(x,y) | 所有的所有的a Q，f(x,a)=f(y,a)其中，其中，x、y為知識庫中的記錄或對象，為知識庫中的記錄或對象，Q是屬性對是屬性對應的等價類。應的等價類。簡記為簡記為U/QU/Q=xQ | x Ux元素的等價類元素的等價類U/R1,R3=1,3,2,7,4,5,6,8U/R2,R3=1,5,2,3,4,7,8,6U/R1,R2,R3=1,2,3,4,5,6,7,8不可分辨關系不可分辨關系U顏色顏色R1形狀形狀R2大小大小R31紅色紅色圓形圓形小小2藍色藍色方形方形大大3紅色

17、紅色三角形三角形小小4藍色藍色三角形三角形小小5黃色黃色圓形圓形小小6黃色黃色方形方形小小7紅色紅色三角形三角形大大8藍色藍色三角形三角形大大關系關系R的粒（初等概念），其他知識都是由粒構成的。的粒（初等概念），其他知識都是由粒構成的。如何求所有的等價關系的算法：如何求所有的等價關系的算法：設設U/a=x1,x2,xm， U/b=y1,y2,yn則：則：U/a,b=zk | zk=xi yj，i=1,m，j=1 ,n，zk U/a,b,c=U/a,b U/c或或U/c U/a,b設設a、b、c是屬性。是屬性。滿足交換律滿足交換律算法如何實現(xiàn)？算法如何實現(xiàn)？9.1.2集合近似與粗糙概念集合近似與

18、粗糙概念n給定論域給定論域U，一簇等價關系一簇等價關系R將將U劃分為互不相交的基劃分為互不相交的基本等價類本等價類U/R。n當能表達成某些基本等價類（初等概念）的并集時，當能表達成某些基本等價類（初等概念）的并集時，稱為稱為可定義的可定義的；否則稱為；否則稱為不可定義的不可定義的。R可定義集能可定義集能在這個知識庫中被精確地定義，所以又稱為在這個知識庫中被精確地定義，所以又稱為R精確集精確集。nR不可定義集不能在這個知識庫中被精確定義，只能不可定義集不能在這個知識庫中被精確定義，只能通過集合逼近的方式來刻畫，因此也稱為通過集合逼近的方式來刻畫，因此也稱為R粗糙集粗糙集 （Rough set）。

19、1. 集合的近似與粗糙集集合的近似與粗糙集UR1122334152647281初等概念：初等概念：U/R=1,4,8,2,5,7,3,6集合集合X=2,3,5,7是是R精確集。精確集。集合集合Y=1,7是是R粗糙集。粗糙集。不能由任何分類得到。不能由任何分類得到。2,5,7 3信息粒信息粒知識庫的等價性知識庫的等價性設設K=(U,P)和和K=(U,Q)為兩個知識庫，當：為兩個知識庫，當：U/P=U/Q則兩個知識庫則兩個知識庫K和和K是等價的。是等價的。若若U/P U/Q，則稱知識，則稱知識P比知識比知識Q更精細。更精細。含義是什么？含義是什么？n粗糙集的上近似集粗糙集的上近似集 （UpperA

20、pproximation）和下近）和下近似集（似集（LowerApproximation）來近似地定義粗糙集。）來近似地定義粗糙集。n粗糙集理論引入上近似和下近似等概念來刻畫知識粗糙集理論引入上近似和下近似等概念來刻畫知識的不確定性和模糊性。的不確定性和模糊性。 2. 上、下近似集上、下近似集定義定義設集合設集合X U，R是一個等價關系，并且有：是一個等價關系，并且有：U/R=y1,y2,yn，則：，則： l集合集合X的的R下近似集：下近似集：R_(X)=yi U | IND(R):yi Xl集合集合X的的R上近似集：上近似集：R(X)=yi U | IND(R):yiXlX的的R邊界域：邊界

21、域：BNR= R(X)- -R_(X)lX的的R正域：正域：POSR(X)=R_(X)l為為X的的R負域：負域：NEGR=U- -R(X)R(X)R(X)下近似、正域：表示下近似、正域：表示X劃入劃入U/R的初等范疇的情況?；虻某醯确懂牭那闆r?；蛘哂谜哂肬/R的初等范疇表示的初等范疇表示X的情況。的情況。設設 X =x1,x4,x6，則，則R_(X)=x1,x6R(X)=x1,x3,x4,x6BNR(X)=x3,x4U- -R(X)=x2,x5,x7X集合集合是粗糙的是粗糙的,因為其邊界不因為其邊界不為空為空。 U Age LEMS Walkx 16-30 50 yes x2 16-30 0

22、no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no設設R=Age,LEMSU/R=x1,x2,x3,x4,x5,x7,x6分類知識分類知識yesyes/nonox1,x6x3,x4x2, x5,x7R_(X)R(X)X=x | Walk=yes=x1,x4,x6U集合集合U/RR : 屬性子集屬性子集R_()R()- -X所有分類都是相對所有分類都是相對R而言的，而言的，U/R或或R就是一種知識。就是一種知識。IND(R)n例如，設論域例如，設論域 ，U上的一族等價關系

23、上的一族等價關系R=R1,R2,R1和和R2是兩個等價關系。根據(jù)這兩個等價關系是兩個等價關系。根據(jù)這兩個等價關系可以將論域可以將論域U進行劃分：進行劃分：n 和和 U/R1中的中的 ，代表，代表 的等價類。的等價類。n論域論域U被被R劃分的基本等價類為劃分的基本等價類為: n集合集合 是是U上的一個子集。則上的一個子集。則X無法用基本等價無法用基本等價類類U/R的并集精確表示，所以的并集精確表示，所以X是是U上的一個上的一個粗糙集合粗糙集合。故。故有有:nX的下近似集為的下近似集為: ；nX的上近似集為的上近似集為: ；nX的負區(qū)域的負區(qū)域: 。12345678U=e ,e ,e ,e ,e

24、,e ,e ,e 212345678U/R =e,e ,e ,e ,e ,e ,e ,e1234e ,e ,e ,e 11 Re12345678U/R =e ,e ,e ,e ,e ,e ,e ,e 23678X=e ,e ,e ,e ,e 678Pos(X)=R(X)=e ,e ,e 12345678R(X)=e,e ,e ,e ,e ,e ,e ,e R5NEG (X)=e 112345678U/R =e ,e ,e ,e ,e ,e ,e ,e 定理定理（1）X是精確的，當且僅當是精確的，當且僅當R(X)=R_(X)（2）X是粗糙的，當且僅當是粗糙的，當且僅當R(X) R_(X)集合集合

25、X=2,3,5,7是是R精確集。精確集。集合集合Y=1,7是粗糙集。是粗糙集。如何如何計算？計算？Ua1122334152647281U/R= 1,4,8,2,5,7,3,6R(X)=yi U | IND(R):yiX=y2y3=2,3,5,7R_(X)=yi U | IND(R):yi X= y2y3=2,3,5,7NEGR(X)=，所以，所以X是精確的。是精確的。IND(R)y1 y2 y3 y4R(Y)=yi U | IND(R):yiY=y1y2=1,4,8,2,5,7R_(X)=yi U | IND(R):yi X= NEGR(X) ，所以，所以X是粗糙的。是粗糙的。R=a定理：定理

26、：（1）R_(X) X R(X)（2）R(X Y)=R(X) R(Y)（3）R_(XY)=R_(X) R_(Y)（4）X Y R_(X) R_(Y)9.1.3 集合近似及分類近似的度量集合近似及分類近似的度量定義定義，由等價關系，由等價關系R描述集合描述集合X的的近似精度近似精度定義為定義為:| )(| )(|)(XRXRXdRX相對相對R的的粗糙度粗糙度定義為定義為: rR(X)=1- -dR(X) 例如，設某知識庫例如，設某知識庫K=(U,R),其中其中U=x1,x2,.,x8,一一個等價關系個等價關系R定義分類對象的等價類如下定義分類對象的等價類如下:y1=x1,x4,x8,y2=x2,

27、x5,x7,y3=x3,y4=x6對于集合對于集合X1=x1,x4,x5,則則: dR(X1)=0/6=0，rR(X1)=1。表示根據(jù)表示根據(jù)R的基本集合描述集合的基本集合描述集合X1的近似精度為的近似精度為0，粗，粗糙度為糙度為1。對于集合對于集合X2=x3,x5,則則: dR(X2)=1/4，rR(X2)=3/4。表示根據(jù)表示根據(jù)R的基本集合描述集合的基本集合描述集合X2的近似精度為的近似精度為0.25，粗糙度為粗糙度為75%。9.2.1. 知識的簡化知識的簡化定義定義，給定知識庫，給定知識庫K=(U,R)，定義一個等價關系，定義一個等價關系R，有屬性有屬性r R，若存在：，若存在：IND

28、(R)=IND(R- -r)稱屬性稱屬性r為為R中可省略的。中可省略的。對于任一對于任一r R，若，若R不可省略，則稱不可省略，則稱R是獨立的。是獨立的。9.2 知識庫的簡化知識庫的簡化表示刪除屬性表示刪除屬性r，不影響記錄之間，不影響記錄之間的區(qū)分（分辨）。的區(qū)分（分辨）。Uabc11122231331341335121642374328232一個知識表一個知識表除掉屬性除掉屬性b：U/R=1,2,3,4,5,6,7,8U/R-b)=1,2,3,4,5,6,7,8U/R等于等于U/R-b)，屬性屬性b是可省略的是可省略的定義，定義，對于屬性子集對于屬性子集P R，若存在，若存在Q=P- -r

29、，且且IND(Q)=IND(P)，且，且Q為最小子集，則為最小子集，則Q稱為稱為P的的簡化，用簡化，用red(P)表示。表示。一個屬性集合一個屬性集合P可能有多種簡化?？赡苡卸喾N簡化。P中所有簡化屬性集中都包含的不可省略關系的中所有簡化屬性集中都包含的不可省略關系的集合，即簡化集集合，即簡化集red(P)的交稱為的交稱為P的核的核。記作。記作core(P)。core(P)= red(P)Uabc11122231331341335121642374328232一個知識表一個知識表除掉屬性除掉屬性a：Ubc112231313433521623732832U/R=1,2,3,4,5,6,7,8U/R

30、- -a)=1,2,3,4,5,6,7,8U/R不等于不等于U/R-a),屬性屬性a是不可省略的是不可省略的Uac112221333413511643742822除掉屬性除掉屬性b：U/R=1,2,3,4,5,6,7,8U/R- -b)=1,2,3,4,5,6,7,8U/R等于等于U/R- -b),屬性屬性b是可省略的是可省略的Uab111223331413512642743823除掉屬性除掉屬性c：U/R=1,2,3,4,5,6,7,8U/R- -c)=1,2,8,3,4,5,6,7U/R等于等于U/R-c),屬性屬性c是不可省略的是不可省略的則：則： redR=a,c，core(R)=a,

31、c。n核核的概念具有兩方面的意義的概念具有兩方面的意義: （1）因為核包含于所有約簡之中，所以核可以作為所）因為核包含于所有約簡之中，所以核可以作為所有約簡的計算基礎。有約簡的計算基礎。 （2）核在知識約簡中是不能消去的特征集合。）核在知識約簡中是不能消去的特征集合。 可以直接由可以直接由分辨矩陣分辨矩陣來求取系統(tǒng)的核集來求取系統(tǒng)的核集Pc。不失一般不失一般性性, 假定系統(tǒng)假定系統(tǒng)T 對于屬性集對于屬性集P 是可分辨的。則系統(tǒng)的核集是可分辨的。則系統(tǒng)的核集由以下定理確定。由以下定理確定。分辨矩陣定義：分辨矩陣定義：設設U=x1,x2,xn，分辨矩陣，分辨矩陣D=dijdij=當當i=j時時ak

32、當當ij，且，且xi和和xj在屬性在屬性ak上不相同時上不相同時分辨函數(shù)分辨函數(shù)f(D)=所有非空項的合取所有非空項的合取求出最簡合取范式，得到所有屬性約簡，求出最簡合取范式，得到所有屬性約簡，Uabc11122231331341335121642374328232D=1 2 3 4 5 6 7 8 abc ac bc bc abc ab ab abc ac ab abc ac c ab abc ab abc abc bc ab ac ac ac abc abc bc abc a利用分辨矩陣求核：利用分辨矩陣求核：f(D)=(abc) (ac) (bc) (abc) =ac。core(R)=a

33、,c。一個屬性約簡一個屬性約簡核是分辨矩陣中所有單個元素組成的集合。核是分辨矩陣中所有單個元素組成的集合。12345678約簡的含義約簡的含義Uabc11122231331341335121642374328232Uac112221333413511643742822等價等價例如，一個信息表如下：例如，一個信息表如下：Uabcd1012021202310104210151102分辨矩陣：分辨矩陣：1234512abcd3abcbcd4acdabdabcd5acdbbcdadf(D)=(abcd) (abc) (acd)(acd) (bcd)(abd)b (abcd)(bcd) ( ad) =(

34、a b) (b d) 兩個約簡兩個約簡a,b和和b,d，核為，核為b。求解求解f(D)可以得到所有可以得到所有的約簡和核的約簡和核NP問題，問題，即即m個屬性其時間復個屬性其時間復雜度為雜度為O(2m)。9.3決策表決策表 決策表決策表包含了某一領域的大量數(shù)據(jù)，是領域的樣本包含了某一領域的大量數(shù)據(jù)，是領域的樣本數(shù)據(jù)庫。它記錄了大量樣本的屬性值和決策情況，是數(shù)據(jù)庫。它記錄了大量樣本的屬性值和決策情況，是領域知識的載體。領域知識的載體。知識獲取的目的就是要通過分析這個實例庫來得到知識獲取的目的就是要通過分析這個實例庫來得到該領域中有用的、規(guī)律性知識。決策表在決策應用中該領域中有用的、規(guī)律性知識。決

35、策表在決策應用中有十分重要的地位，可用于表達絕大多數(shù)決策問題。有十分重要的地位，可用于表達絕大多數(shù)決策問題。對于決策表，最重要的是決策規(guī)則的生成。對于決策表，最重要的是決策規(guī)則的生成。數(shù)據(jù)庫數(shù)據(jù)庫決策表決策表規(guī)則規(guī)則在信息表（知識庫）上指定條件屬性集合在信息表（知識庫）上指定條件屬性集合C和和結論（決策）屬性集合結論（決策）屬性集合D，這樣就構成了，這樣就構成了決策表決策表。利用粗糙集理論進行數(shù)據(jù)挖掘的過程利用粗糙集理論進行數(shù)據(jù)挖掘的過程決策表決策表決策表決策表規(guī)則規(guī)則屬性約簡屬性約簡值約簡值約簡9.3.1 知識的相對簡化知識的相對簡化一個分類相對另一個分類的正域。一個分類相對另一個分類的正域

36、。定義定義，給定決策表，給定決策表T=(U,R)，等價關系，等價關系R的子集的子集C和和D，定義，定義D的的C正域正域POSC(D)為：為： POSC(D)=C(X)， XU/DU的所有的所有D分類（分類（U/D）劃入到）劃入到U的的C分類（分類（U/C）的情況。的情況。Uabc11122231331341335121642374328232一個決策表：一個決策表：設設C=a,b，D=c，求求POSC(D)=?U/D=1,7,8,2,5,3,4,6U/C=1,2,8,3,4,5,6,7R_(1,7,8)=1,7R_(2,5)=5R_(3,4,6)=3,4,6POSC(D)=1,753,4,6

37、=1,3,4,5,6,7 POSC(D)的含義是什么？的含義是什么？U對于屬性集合對于屬性集合D有一個分類有一個分類U/C。U對于屬性集合對于屬性集合C有一個分類有一個分類U/D。POSC(D)表示這兩種分類之間的關系。表示這兩種分類之間的關系。表示表示U/D的分類在的分類在U/C中的不確定性。中的不確定性。如果如果POSC(D)=U，表示兩種分類是一致的。，表示兩種分類是一致的。U/CU/DPOSC(D)U/C、U/D均為知識，知識之間通過均為知識，知識之間通過POSC(D)關聯(lián)，構成一種知識體系結構。關聯(lián)，構成一種知識體系結構。知識知識5知識知識6知識知識7知識知識8知識知識2知識知識3知

38、識知識4知識知識1知識體系結構知識體系結構粒計算的研究方粒計算的研究方向之一向之一定義定義C D依賴性度量：依賴性度量：| )(|)(UDPOSDrkCC設設(U,CD)是一個決策表。是一個決策表。9.3.2 知識的依賴性和屬性的重要性知識的依賴性和屬性的重要性k可以看成可以看成D和和C之間依賴性的量度，也可解釋為對對之間依賴性的量度，也可解釋為對對象的分類的能力。象的分類的能力。當當k=1時，則時，則U的全部記錄都可以通過知識的全部記錄都可以通過知識C劃入劃入U/D的初始概念。的初始概念。當當k1時，只有屬于正域的記錄可以通過知識時，只有屬于正域的記錄可以通過知識C劃入劃入U/D的初始概念。

39、的初始概念。一個汽車決策表：一個汽車決策表：U條件屬性條件屬性決策屬性決策屬性類型類型a機型機型b顏色顏色c速度速度d加速加速e1中中柴油柴油灰色灰色中中差差2小小汽油汽油白色白色高高極好極好3大大柴油柴油黑色黑色高高好好4中中汽油汽油黑色黑色中中極好極好5中中柴油柴油灰色灰色低低好好6大大混合混合黑色黑色高高好好7大大汽油汽油白色白色高高極好極好8小小汽油汽油白色白色低低好好U/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8C_(1)=，C_(2,7)=7，C_(3,6)=3,6C_(4)=4，C_(5,8)=，POSC(D)=73,64=3,4,6,7k=|POS

40、C(D)|/|U|=4/8=0.5。 兩者之間的依賴度為兩者之間的依賴度為50。也就是說，由類型、機型和顏色可以也就是說，由類型、機型和顏色可以50來確定速度來確定速度和加速屬性。和加速屬性。定義定義，屬性，屬性a的重要性度量：的重要性度量：Ia(S)=rR(S)-rR-a(S) ，其中，其中S為屬性為屬性a的分類結果的分類結果設設(U,CD)是一個決策表。是一個決策表。一個決策表如下，求屬性一個決策表如下，求屬性a、b、c的重要性？的重要性？U條件屬性條件屬性決策屬性決策屬性abcde122100211301331211422210521112633211732301812312U/a,b,

41、c=1,2,3,4,5,6,7,8，U/d,e=1,2,7,3,6,4,5,8，POSC(D)=1,2,3,4,5,6,7,8，POSC-a(D)=1,2,3,4,5,6,7,8POSC-b(D)=3,4,6,7，POSC-c(D)=2,3,5,6,7,8，Ia(D)=8/8- -8/8=0；Ib(D)=8/8- -4/8=0.5；Ic(D)=8/8- -6/8=0.125。屬性屬性a最不重要，可以刪除，屬性最不重要，可以刪除，屬性b最重要。最重要。9.3.3 屬性約簡、核集的求取屬性約簡、核集的求取 n所謂所謂屬性約簡（決策表）屬性約簡（決策表），就是在保持知識庫分類能，就是在保持知識庫分類

42、能力不變的條件下，刪除其中不相關或不重要的屬性。力不變的條件下，刪除其中不相關或不重要的屬性。n一個屬性集合可能有多個約簡。一個屬性集合可能有多個約簡。n屬性約簡的目標就是要從條件屬性集合中發(fā)現(xiàn)部分必屬性約簡的目標就是要從條件屬性集合中發(fā)現(xiàn)部分必要的條件屬性，使得根據(jù)這部分條件屬性形成的相對要的條件屬性，使得根據(jù)這部分條件屬性形成的相對于決策屬性的分類和所有條件屬性所形成的相對于決于決策屬性的分類和所有條件屬性所形成的相對于決策屬性的分類一致，即和所有條件屬性相對于決策屬策屬性的分類一致，即和所有條件屬性相對于決策屬性性D有相同的分類能力。有相同的分類能力。設設T = ( U , C D) 是

43、決策表，如果有：是決策表，如果有：POSC(D)=U則決策表則決策表T是協(xié)調的或一致的；否則稱是協(xié)調的或一致的；否則稱T為不協(xié)調的決為不協(xié)調的決策表。策表。對于不協(xié)調的決策表，不能由條件屬性導出結對于不協(xié)調的決策表，不能由條件屬性導出結論屬性之間的關系，應將其分解為完全協(xié)調和完全論屬性之間的關系，應將其分解為完全協(xié)調和完全不協(xié)調的兩個決策表。不協(xié)調的兩個決策表。1. 協(xié)調的決策表協(xié)調的決策表U條件屬性條件屬性結論屬性結論屬性頭疼頭疼肌肉疼肌肉疼體溫體溫流感流感1是是是是正常正常否否2是是是是高高是是3是是是是很高很高是是4否否是是正常正常否否5否否否否高高否否6否否是是很高很高是是設設C=頭疼

44、頭疼,肌肉疼肌肉疼,體溫體溫，D=流感流感U/流感流感=1,4,5,2,3,6U/頭疼頭疼,肌肉疼肌肉疼,體溫體溫=1,2,3,4,5,6POSC(D)=C(1,4,5) C(2,3,6) =1,4,5 2,3,6=1,2,3,4,5,6U該決策表是協(xié)調的。該決策表是協(xié)調的。定義定義，設，設T = ( U , C D) 是決策表，如果去掉條件屬性是決策表，如果去掉條件屬性c，得到的表得到的表T1 = (U , Cc , D) 與表與表T 相比，有：相比，有：POSC-c( D) = POSC(D)則稱條件屬性則稱條件屬性c是關于是關于D可省的，否則稱條件屬性可省的，否則稱條件屬性c是關于是關于

45、D 不可省的。不可省的。決策表決策表T決策表決策表T1刪除條件屬性刪除條件屬性c并并合并記錄合并記錄2. 條件屬性的可省略性條件屬性的可省略性n定義定義，如果決策表，如果決策表T中每個條件屬性都是關于中每個條件屬性都是關于D 不可不可省的，則稱條件屬性集省的，則稱條件屬性集C 是關于是關于D獨立的，否則稱獨立的，否則稱C 是關于是關于D 依賴的。依賴的。n定義定義，決策表，決策表T = (U, C D) 中條件屬性集中條件屬性集C 的一個的一個子集子集B 是關于是關于D 獨立的，并且獨立的，并且POSB(D) = POSC(D)，則稱則稱B 是是C 的一個的一個D屬性約簡。屬性約簡。Uabcd

46、e110220201112320011411022510201622011721112801101一個決策表：一個決策表：C=a,b,c， D=d,eU/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8POSC(D)=3,4,6,7rC(D)=4/81，不是協(xié)調的。，不是協(xié)調的。DesC(1)=1,0,2 DesD(1)=2,0DesC(5)=1,0,2 DesD(5)=0,1DesC(2)=0,1,1 DesD(2)=1,2DesC(8)=0,1,1 DesD(8)=0,1矛盾矛盾矛盾矛盾分解為如下兩個表：分解為如下兩個表：Uabcde3200114110226220

47、11721112完全協(xié)調的決策表完全協(xié)調的決策表Uabcde110220201112510201801101完全不協(xié)調的決策表完全不協(xié)調的決策表DesC(x)表示元素表示元素x的條件屬性值。的條件屬性值。DesD(x)表示元素表示元素x的決策屬性值。的決策屬性值。Uabcde320011411022622011721112完全協(xié)調的決策表完全協(xié)調的決策表U/C=3,4,6,7，U/D=3,6,4,7POSC(D)=3,4,6,7，rC(D)=4/4=1，數(shù)據(jù)是協(xié)調的。，數(shù)據(jù)是協(xié)調的。U/(C- -a)=3,4,6,7，POSC-a(D)=3,4,6,7,rC-a=1，是協(xié)調的。，是協(xié)調的。U/

48、(C-b)=3,6,4,7，POSC-b(D)=3,4,6,7,rC-b=1，是協(xié)調的。，是協(xié)調的。U/(C-c)=3,4,6,7，POSC-c(D)=3,4,6,7,rC-c=1，是協(xié)調的。，是協(xié)調的。U/(C-a,b)=3,4,6,7，POSC-a,b(D)=7,rC-a,b=1/4，是不協(xié)調的。，是不協(xié)調的。U/(C-b,c)=3,6,7,4，POSC-b,c(D)=4,rC-b,c=1/4，是不協(xié)調的。，是不協(xié)調的。U/(C-a,c)=36,4,7，POSC-a,c(D)=3,6,rC-a,c=2/4，是不協(xié)調的。，是不協(xié)調的。所以所以a,b、a,c、b,c都是不可省略的，則：都是不可

49、省略的，則：redC(D)=a,b,a,c,b,c。9.4 常用的決策表屬性約簡算法常用的決策表屬性約簡算法 對于決策表中的每一個條件屬性對于決策表中的每一個條件屬性a進行如下過程，直到條件屬性集進行如下過程，直到條件屬性集合不再發(fā)生變化為止。合不再發(fā)生變化為止。 如果刪除該屬性如果刪除該屬性a 使得使得POSC-a(D)=POSC(D)，則說明該屬性是相，則說明該屬性是相對決策屬性對決策屬性D不必要的，從不必要的，從 決策表中刪除該屬性所在的列并將重復的決策表中刪除該屬性所在的列并將重復的行進行合并；行進行合并； 否則，說明該屬性是相對決策屬性否則，說明該屬性是相對決策屬性d必要的，不能刪除

50、。必要的，不能刪除。9.4.1 一般屬性約簡算法一般屬性約簡算法算法描述算法描述:9.4.2 基于可辨識矩陣屬性約簡算法基于可辨識矩陣屬性約簡算法 n分辨矩陣（也稱分明矩陣）是由波蘭數(shù)學家分辨矩陣（也稱分明矩陣）是由波蘭數(shù)學家Skowron.A教授提出的。教授提出的。n定義定義，設相容決策表，設相容決策表T=，U=x1,x2, ,xn，C=ci | i=1,2,m和和D=d分別為條件屬性集和決策屬分別為條件屬性集和決策屬性集。分辨矩陣定義為：性集。分辨矩陣定義為：dij 當當d(xi)=d(xj)ck| ck(xi) ck(xj) 當當d(xi) d(xj)和信息表求分辨矩陣有什么不同？和信息

51、表求分辨矩陣有什么不同？U條件屬性條件屬性結論屬性結論屬性abc11122231331341335121一個決策表一個決策表求求分辨矩陣：分辨矩陣：123451ababb2aba3ab4b5n由上述定義可以看出，分辨矩陣是一個對稱矩陣。當由上述定義可以看出，分辨矩陣是一個對稱矩陣。當兩個樣本的決策屬性取同時，對象值為兩個樣本的決策屬性取同時，對象值為；當兩個樣；當兩個樣本的決策屬性不同且可以通過某些條件屬性的取值加本的決策屬性不同且可以通過某些條件屬性的取值加以區(qū)分時，對象值為這兩個樣本屬性值不同的條件屬以區(qū)分時，對象值為這兩個樣本屬性值不同的條件屬性集合。性集合。n一個數(shù)據(jù)集的所有約簡可以通

52、過構造可辨識并且化簡一個數(shù)據(jù)集的所有約簡可以通過構造可辨識并且化簡由可辨識矩陣導出的區(qū)分函數(shù)而得到，所有的蘊含式由可辨識矩陣導出的區(qū)分函數(shù)而得到，所有的蘊含式包含的屬性就是決策表的所有約簡集合。包含的屬性就是決策表的所有約簡集合。算法分辨矩陣屬性約簡算法算法分辨矩陣屬性約簡算法 輸入：相容決策表輸入：相容決策表DT=；輸出：約簡的屬性集。輸出：約簡的屬性集。步驟：步驟：（1）計算決策表的分辨矩陣；）計算決策表的分辨矩陣；/根據(jù)分辨矩陣的定義求根據(jù)分辨矩陣的定義求元素元素（2）對于可辨識矩陣中所有取值為非空集合的對象，建）對于可辨識矩陣中所有取值為非空集合的對象，建立相應的析取邏輯表達式。立相應

53、的析取邏輯表達式。（3）將所有的析取邏輯表達式進行合取運算，得）將所有的析取邏輯表達式進行合取運算，得一個最簡合取范式一個最簡合取范式T。（4）將合取范式）將合取范式T轉換為析取范式的形式。轉換為析取范式的形式。（5）輸出屬性約簡結果。）輸出屬性約簡結果?；诜直婢仃嚭瓦壿嬤\算的屬性約簡算法可以得到基于分辨矩陣和邏輯運算的屬性約簡算法可以得到?jīng)Q策表的所有可能的屬性約簡結果，它實際上是將對屬決策表的所有可能的屬性約簡結果，它實際上是將對屬性組合情況的搜索演變成為邏輯公式的簡化性組合情況的搜索演變成為邏輯公式的簡化 。時間復雜度為時間復雜度為O(2m)，屬，屬NP問題。問題。一個氣象決策表一個氣象

54、決策表U條件屬性條件屬性結論屬性結論屬性天氣天氣a溫度溫度b濕度濕度 c有風否有風否de11110N21111N32110P43210P53320P63321N72321P81210N91320P103220P111221P122211P132120P143211NU/C=1,2,3,4,5,6,7,8,9,10,11,12,13,14U/D=1,2,6,8,14,3,4,5,7,9,10,11,12,13POSC(D)=1,2,3,4,5,6,7,8,9,10,11,12,13,14=U，是協(xié)調的。，是協(xié)調的。12345678910111213141aababcabcdbcabcbcdabd

55、ac2adabdabcdabcbcdabcdbcabacd3abcdababd4bcdabd5dacbcd6aadbdababdabd7abcdabc8bcaccdcdabc9abcd10cd11ac12ad13abcd14分辯矩陣：分辯矩陣：d1,3=a,d2,3=add1,4=abf(D)=d1,3d2,3a1,4 =(abd) (acd)兩個約簡為兩個約簡為a,b,d和和a,c,d，核為，核為a,d。約簡結果約簡結果1：a,b,dU條件屬性條件屬性結論屬性結論屬性天氣天氣a溫度溫度b有風否有風否de1110N2111N3210P4320P5330P6331N7231P8120N9130P

56、10320P11121P12221P13210P14321N約簡結果約簡結果2：a,c,dU條件屬性條件屬性結論屬性結論屬性天氣天氣a濕度濕度 c有風否有風否de1110N2111N3210P4310P5320P6321N7221P8110N9120P10320P11121P12211P13220P14311N利用分辨矩陣求核利用分辨矩陣求核命題：命題：在分辨矩陣中，所有單項屬性構成決策表的在分辨矩陣中，所有單項屬性構成決策表的核。核。12345678910111213141aababcabcdbcabcbcdabdac2adabdabcdabcbcdabcdbcabacd3abcdababd

57、4bcdabd5dacbcd6aadbdababdabd7abcdabc8bcaccdcdabc9abcd10cd11ac12ad13abcd14上例的分辯矩陣：上例的分辯矩陣：其中單項屬性為其中單項屬性為a和和d，則核為，則核為a,d設決策表中元素個數(shù)為設決策表中元素個數(shù)為n，求核的算法時間復雜度為求核的算法時間復雜度為O(n2)。9.4.3一般約簡算法一般約簡算法 對于決策表中的每一個條件屬性對于決策表中的每一個條件屬性ai，進行如下過程，進行如下過程，直至條件屬性集合不再發(fā)生變化為止。直至條件屬性集合不再發(fā)生變化為止。如果刪除該屬性如果刪除該屬性ai使得使得POS(C-ai)(D)=PO

58、SC(D)，則，則說明屬性說明屬性ai是相對于決策屬性是相對于決策屬性d不必要的，從決策表中刪不必要的，從決策表中刪除屬性除屬性ai所在列并將重復的行進行合并；所在列并將重復的行進行合并；否則，說明屬性否則，說明屬性ai是相對于決策屬性是相對于決策屬性D必要的，不能必要的，不能刪除。刪除。對于有限元素集合對于有限元素集合A=a1,a2,am，如果按照某種，如果按照某種屬性重要性度量方法得到重要性由大到小的一個排列屬性重要性度量方法得到重要性由大到小的一個排列a1,a2,am，就可以得到序集，就可以得到序集a1,a2,am，再得到，再得到相應地各階冪集。相應地各階冪集。 9.4.4 歸納屬性約簡

59、算法歸納屬性約簡算法 算法描述：算法描述： 步驟步驟1：求核：求核COREC(D)；步驟步驟2：求：求最小屬性約簡最小屬性約簡minC(D); （1）令）令X=COREC(D)，L=D- -X=a1,a2,a3am，T(L)表示表示L的的冪集，冪集，Ti(L)為為L的的i（1im）階冪字集；）階冪字集；（2）如果）如果DOSX(D)=DOSC(D)，則，則minC(D)=X，轉，轉(10)；（3）i=1，F(xiàn)lag=0；（4）Y=Ti(L)；（5）任意?。┤我馊Y，A=Xy，計算，計算POSA(D)=POSC(D)？若相等：若相等：如果如果Flag=0，則，則Z=A，F(xiàn)lag=1，否則，如否則

60、，如|U/Z|U/A|，則，則Z=A；（6）Y=Y- -y;（7）如果）如果Y，轉，轉(5)；（8）如果）如果Flag=1,則則minC(D)=Z，轉（，轉（10）;（9）i = i+1,如果如果im，則轉（，則轉（4）；）；（10）結束）結束添加添加y找到一個約簡找到一個約簡9.4.5 基于屬性重要性的屬性約簡基于屬性重要性的屬性約簡輸入輸入：決策表：決策表S=。輸出輸出：條件屬性：條件屬性C相對于決策屬性相對于決策屬性D的一個相對約簡。的一個相對約簡。（1）計算）計算C相對于相對于D的核的核COREC(D)；（2）令）令B=COREC(D)，如果，轉到（，如果，轉到（5）（3）對于）對于C