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

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

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

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

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

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

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

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

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

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

10、狀、形狀R2和大和大小小R3，通過(guò)這樣的分類，可以，通過(guò)這樣的分類，可以得到以下三個(gè)等價(jià)類：得到以下三個(gè)等價(jià)類：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這些等價(jià)類是知識(shí)庫(kù)這些等價(jià)類是知識(shí)庫(kù)K=(U,R1,R2,R3)中的初等概念。所以：中的初等概念。所以：基于基于R1的初等概念有：的初等概念有：1,3,7：紅色積木：紅色積木2,4：藍(lán)色積木：藍(lán)色積木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藍(lán)色藍(lán)色方形方形大大3紅色紅色三角形三角形小小4藍(lán)色藍(lán)色三角形三角形小小5黃色黃色圓形圓形小小6黃色黃色方形方形小小7紅色紅色三角形三角形大大8藍(lán)色藍(lán)色三角形三角形大大基本概念是初等概念的交集?；靖拍钍浅醯雀拍畹慕患??；诨赗1,R2的基本概念有：的基本概念有：1,3,71,5=1：紅色圓形積木：紅色圓形積木1,3,73,4,7,8=3,7：紅色三角形積木：紅色三角形積木2,42,6=2：藍(lán)色方形積木：藍(lán)色方形積木2,43,4,7,8=4

12、：藍(lán)色三角形積木：藍(lán)色三角形積木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：藍(lán)色大積木：藍(lán)色大積木2,41,3,4,5,6=4：藍(lán)色小積木：藍(lán)色小積木5,6,82,7,8=8：黃色大積木：黃色大積木5,6,81,3,4,5,6=5,6：黃色小積木：黃色小積木1,4,7找不出共找不出共同特點(diǎn)，不能稱同特點(diǎn)，不能稱

13、為一個(gè)概念。為一個(gè)概念。2. 不可分辨關(guān)系不可分辨關(guān)系 n在粗糙集理論中，在粗糙集理論中，“知識(shí)知識(shí)”被認(rèn)為是一種分類的能力。被認(rèn)為是一種分類的能力。不可分辨關(guān)系的概念是粗糙集理論的基石，它揭示出不可分辨關(guān)系的概念是粗糙集理論的基石，它揭示出論域知識(shí)的顆粒狀結(jié)構(gòu)。論域知識(shí)的顆粒狀結(jié)構(gòu)。n假定關(guān)于論域的某種知識(shí)，并使用屬性和屬性值來(lái)描假定關(guān)于論域的某種知識(shí)，并使用屬性和屬性值來(lái)描述論域中的對(duì)象，如果兩個(gè)對(duì)象述論域中的對(duì)象，如果兩個(gè)對(duì)象(或?qū)ο蠹匣驅(qū)ο蠹?具有相具有相同的屬性和屬性值，則它們之間具有同的屬性和屬性值，則它們之間具有不可分辨關(guān)系不可分辨關(guān)系。n定義定義設(shè)設(shè)R是非空集合是非空集合U

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

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

16、等價(jià)關(guān)系）稱是一個(gè)等價(jià)關(guān)系）稱Q為為不可分辨關(guān)系不可分辨關(guān)系,記作記作IND(Q)。QPQQIND(Q)=(x,y) | 所有的所有的a Q，f(x,a)=f(y,a)其中，其中，x、y為知識(shí)庫(kù)中的記錄或?qū)ο?，為知識(shí)庫(kù)中的記錄或?qū)ο?，Q是屬性對(duì)是屬性對(duì)應(yīng)的等價(jià)類。應(yīng)的等價(jià)類。簡(jiǎn)記為簡(jiǎn)記為U/QU/Q=xQ | x Ux元素的等價(jià)類元素的等價(jià)類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不可分辨關(guān)系不可分辨關(guān)系U顏色顏色R1形狀形狀R2大小大小R31紅色紅色圓形圓形小小2藍(lán)色藍(lán)色方形方形大大3紅色

17、紅色三角形三角形小小4藍(lán)色藍(lán)色三角形三角形小小5黃色黃色圓形圓形小小6黃色黃色方形方形小小7紅色紅色三角形三角形大大8藍(lán)色藍(lán)色三角形三角形大大關(guān)系關(guān)系R的粒（初等概念），其他知識(shí)都是由粒構(gòu)成的。的粒（初等概念），其他知識(shí)都是由粒構(gòu)成的。如何求所有的等價(jià)關(guān)系的算法：如何求所有的等價(jià)關(guān)系的算法：設(shè)設(shè)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設(shè)設(shè)a、b、c是屬性。是屬性。滿足交換律滿足交換律算法如何實(shí)現(xiàn)？算法如何實(shí)現(xiàn)？9.1.2集合近似與粗糙概念集合近似與

18、粗糙概念n給定論域給定論域U，一簇等價(jià)關(guān)系一簇等價(jià)關(guān)系R將將U劃分為互不相交的基劃分為互不相交的基本等價(jià)類本等價(jià)類U/R。n當(dāng)能表達(dá)成某些基本等價(jià)類（初等概念）的并集時(shí)，當(dāng)能表達(dá)成某些基本等價(jià)類（初等概念）的并集時(shí)，稱為稱為可定義的可定義的；否則稱為；否則稱為不可定義的不可定義的。R可定義集能可定義集能在這個(gè)知識(shí)庫(kù)中被精確地定義，所以又稱為在這個(gè)知識(shí)庫(kù)中被精確地定義，所以又稱為R精確集精確集。nR不可定義集不能在這個(gè)知識(shí)庫(kù)中被精確定義，只能不可定義集不能在這個(gè)知識(shí)庫(kù)中被精確定義，只能通過(guò)集合逼近的方式來(lái)刻畫，因此也稱為通過(guò)集合逼近的方式來(lái)刻畫，因此也稱為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信息粒信息粒知識(shí)庫(kù)的等價(jià)性知識(shí)庫(kù)的等價(jià)性設(shè)設(shè)K=(U,P)和和K=(U,Q)為兩個(gè)知識(shí)庫(kù)，當(dāng)：為兩個(gè)知識(shí)庫(kù)，當(dāng)：U/P=U/Q則兩個(gè)知識(shí)庫(kù)則兩個(gè)知識(shí)庫(kù)K和和K是等價(jià)的。是等價(jià)的。若若U/P U/Q，則稱知識(shí)，則稱知識(shí)P比知識(shí)比知識(shí)Q更精細(xì)。更精細(xì)。含義是什么？含義是什么？n粗糙集的上近似集粗糙集的上近似集 （UpperA

20、pproximation）和下近）和下近似集（似集（LowerApproximation）來(lái)近似地定義粗糙集。）來(lái)近似地定義粗糙集。n粗糙集理論引入上近似和下近似等概念來(lái)刻畫知識(shí)粗糙集理論引入上近似和下近似等概念來(lái)刻畫知識(shí)的不確定性和模糊性。的不確定性和模糊性。 2. 上、下近似集上、下近似集定義定義設(shè)集合設(shè)集合X U，R是一個(gè)等價(jià)關(guān)系，并且有：是一個(gè)等價(jià)關(guān)系，并且有：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負(fù)域：負(fù)域：NEGR=U- -R(X)R(X)R(X)下近似、正域：表示下近似、正域：表示X劃入劃入U(xiǎn)/R的初等范疇的情況?；虻某醯确懂牭那闆r?；蛘哂谜哂肬/R的初等范疇表示的初等范疇表示X的情況。的情況。設(shè)設(shè) X =x1,x4,x6，則，則R_(X)=x1,x6R(X)=x1,x3,x4,x6BNR(X)=x3,x4U- -R(X)=x2,x5,x7X集合集合是粗糙的是粗糙的,因?yàn)槠溥吔绮灰驗(yàn)槠溥吔绮粸榭諡榭铡?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設(shè)設(shè)R=Age,LEMSU/R=x1,x2,x3,x4,x5,x7,x6分類知識(shí)分類知識(shí)yesyes/nonox1,x6x3,x4x2, x5,x7R_(X)R(X)X=x | Walk=yes=x1,x4,x6U集合集合U/RR : 屬性子集屬性子集R_()R()- -X所有分類都是相對(duì)所有分類都是相對(duì)R而言的，而言的，U/R或或R就是一種知識(shí)。就是一種知識(shí)。IND(R)n例如，設(shè)論域例如，設(shè)論域 ，U上的一族等價(jià)關(guān)系

23、上的一族等價(jià)關(guān)系R=R1,R2,R1和和R2是兩個(gè)等價(jià)關(guān)系。根據(jù)這兩個(gè)等價(jià)關(guān)系是兩個(gè)等價(jià)關(guān)系。根據(jù)這兩個(gè)等價(jià)關(guān)系可以將論域可以將論域U進(jìn)行劃分：進(jìn)行劃分：n 和和 U/R1中的中的 ，代表，代表 的等價(jià)類。的等價(jià)類。n論域論域U被被R劃分的基本等價(jià)類為劃分的基本等價(jià)類為: n集合集合 是是U上的一個(gè)子集。則上的一個(gè)子集。則X無(wú)法用基本等價(jià)無(wú)法用基本等價(jià)類類U/R的并集精確表示，所以的并集精確表示，所以X是是U上的一個(gè)上的一個(gè)粗糙集合粗糙集合。故。故有有:nX的下近似集為的下近似集為: ；nX的上近似集為的上近似集為: ；nX的負(fù)區(qū)域的負(fù)區(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是精確的，當(dāng)且僅當(dāng)是精確的，當(dāng)且僅當(dāng)R(X)=R_(X)（2）X是粗糙的，當(dāng)且僅當(dāng)是粗糙的，當(dāng)且僅當(dāng)R(X) R_(X)集合集合

25、X=2,3,5,7是是R精確集。精確集。集合集合Y=1,7是粗糙集。是粗糙集。如何如何計(jì)算？計(jì)算？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 集合近似及分類近似的度量集合近似及分類近似的度量定義定義，由等價(jià)關(guān)系，由等價(jià)關(guān)系R描述集合描述集合X的的近似精度近似精度定義為定義為:| )(| )(|)(XRXRXdRX相對(duì)相對(duì)R的的粗糙度粗糙度定義為定義為: rR(X)=1- -dR(X) 例如，設(shè)某知識(shí)庫(kù)例如，設(shè)某知識(shí)庫(kù)K=(U,R),其中其中U=x1,x2,.,x8,一一個(gè)等價(jià)關(guān)系個(gè)等價(jià)關(guān)系R定義分類對(duì)象的等價(jià)類如下定義分類對(duì)象的等價(jià)類如下:y1=x1,x4,x8,y2=x2,

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

28、(R)=IND(R- -r)稱屬性稱屬性r為為R中可省略的。中可省略的。對(duì)于任一對(duì)于任一r R，若，若R不可省略，則稱不可省略，則稱R是獨(dú)立的。是獨(dú)立的。9.2 知識(shí)庫(kù)的簡(jiǎn)化知識(shí)庫(kù)的簡(jiǎn)化表示刪除屬性表示刪除屬性r，不影響記錄之間，不影響記錄之間的區(qū)分（分辨）。的區(qū)分（分辨）。Uabc11122231331341335121642374328232一個(gè)知識(shí)表一個(gè)知識(shí)表除掉屬性除掉屬性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是可省略的是可省略的定義，定義，對(duì)于屬性子集對(duì)于屬性子集P R，若存在，若存在Q=P- -r

29、，且且IND(Q)=IND(P)，且，且Q為最小子集，則為最小子集，則Q稱為稱為P的的簡(jiǎn)化，用簡(jiǎn)化，用red(P)表示。表示。一個(gè)屬性集合一個(gè)屬性集合P可能有多種簡(jiǎn)化?？赡苡卸喾N簡(jiǎn)化。P中所有簡(jiǎn)化屬性集中都包含的不可省略關(guān)系的中所有簡(jiǎn)化屬性集中都包含的不可省略關(guān)系的集合，即簡(jiǎn)化集集合，即簡(jiǎn)化集red(P)的交稱為的交稱為P的核的核。記作。記作core(P)。core(P)= red(P)Uabc11122231331341335121642374328232一個(gè)知識(shí)表一個(gè)知識(shí)表除掉屬性除掉屬性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）因?yàn)楹税谒屑s簡(jiǎn)之中，所以核可以作為所）因?yàn)楹税谒屑s簡(jiǎn)之中，所以核可以作為所有約簡(jiǎn)的計(jì)算基礎(chǔ)。有約簡(jiǎn)的計(jì)算基礎(chǔ)。 （2）核在知識(shí)約簡(jiǎn)中是不能消去的特征集合。）核在知識(shí)約簡(jiǎn)中是不能消去的特征集合。 可以直接由可以直接由分辨矩陣分辨矩陣來(lái)求取系統(tǒng)的核集來(lái)求取系統(tǒng)的核集Pc。不失一般不失一般性性, 假定系統(tǒng)假定系統(tǒng)T 對(duì)于屬性集對(duì)于屬性集P 是可分辨的。則系統(tǒng)的核集是可分辨的。則系統(tǒng)的核集由以下定理確定。由以下定理確定。分辨矩陣定義：分辨矩陣定義：設(shè)設(shè)U=x1,x2,xn，分辨矩陣，分辨矩陣D=dijdij=當(dāng)當(dāng)i=j時(shí)時(shí)ak

32、當(dāng)當(dāng)ij，且，且xi和和xj在屬性在屬性ak上不相同時(shí)上不相同時(shí)分辨函數(shù)分辨函數(shù)f(D)=所有非空項(xiàng)的合取所有非空項(xiàng)的合取求出最簡(jiǎn)合取范式，得到所有屬性約簡(jiǎn)，求出最簡(jiǎn)合取范式，得到所有屬性約簡(jiǎn)，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。一個(gè)屬性約簡(jiǎn)一個(gè)屬性約簡(jiǎn)核是分辨矩陣中所有單個(gè)元素組成的集合。核是分辨矩陣中所有單個(gè)元素組成的集合。12345678約簡(jiǎn)的含義約簡(jiǎn)的含義Uabc11122231331341335121642374328232Uac112221333413511643742822等價(jià)等價(jià)例如，一個(gè)信息表如下：例如，一個(gè)信息表如下：Uabcd1012021202310104210151102分辨矩陣：分辨矩陣：1234512abcd3abcbcd4acdabdabcd5acdbbcdadf(D)=(abcd) (abc) (acd)(acd) (bcd)(abd)b (abcd)(bcd) ( ad) =(

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

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

36、。定義定義，給定決策表，給定決策表T=(U,R)，等價(jià)關(guān)系，等價(jià)關(guān)系R的子集的子集C和和D，定義，定義D的的C正域正域POSC(D)為：為： POSC(D)=C(X)， XU/DU的所有的所有D分類（分類（U/D）劃入到）劃入到U的的C分類（分類（U/C）的情況。的情況。Uabc11122231331341335121642374328232一個(gè)決策表：一個(gè)決策表：設(shè)設(shè)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對(duì)于屬性集合對(duì)于屬性集合D有一個(gè)分類有一個(gè)分類U/C。U對(duì)于屬性集合對(duì)于屬性集合C有一個(gè)分類有一個(gè)分類U/D。POSC(D)表示這兩種分類之間的關(guān)系。表示這兩種分類之間的關(guān)系。表示表示U/D的分類在的分類在U/C中的不確定性。中的不確定性。如果如果POSC(D)=U，表示兩種分類是一致的。，表示兩種分類是一致的。U/CU/DPOSC(D)U/C、U/D均為知識(shí)，知識(shí)之間通過(guò)均為知識(shí)，知識(shí)之間通過(guò)POSC(D)關(guān)聯(lián)，構(gòu)成一種知識(shí)體系結(jié)構(gòu)。關(guān)聯(lián)，構(gòu)成一種知識(shí)體系結(jié)構(gòu)。知識(shí)知識(shí)5知識(shí)知識(shí)6知識(shí)知識(shí)7知識(shí)知識(shí)8知識(shí)知識(shí)2知識(shí)知識(shí)3知

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

39、的初始概念。一個(gè)汽車決策表：一個(gè)汽車決策表：U條件屬性條件屬性決策屬性決策屬性類型類型a機(jī)型機(jī)型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。也就是說(shuō)，由類型、機(jī)型和顏色可以也就是說(shuō)，由類型、機(jī)型和顏色可以50來(lái)確定速度來(lái)確定速度和加速屬性。和加速屬性。定義定義，屬性，屬性a的重要性度量：的重要性度量：Ia(S)=rR(S)-rR-a(S) ，其中，其中S為屬性為屬性a的分類結(jié)果的分類結(jié)果設(shè)設(shè)(U,CD)是一個(gè)決策表。是一個(gè)決策表。一個(gè)決策表如下，求屬性一個(gè)決策表如下，求屬性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 屬性約簡(jiǎn)、核集的求取屬性約簡(jiǎn)、核集的求取 n所謂所謂屬性約簡(jiǎn)（決策表）屬性約簡(jiǎn)（決策表），就是在保持知識(shí)庫(kù)分類能，就是在保持知識(shí)庫(kù)分類

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

43、決策表，如果有：是決策表，如果有：POSC(D)=U則決策表則決策表T是協(xié)調(diào)的或一致的；否則稱是協(xié)調(diào)的或一致的；否則稱T為不協(xié)調(diào)的決為不協(xié)調(diào)的決策表。策表。對(duì)于不協(xié)調(diào)的決策表，不能由條件屬性導(dǎo)出結(jié)對(duì)于不協(xié)調(diào)的決策表，不能由條件屬性導(dǎo)出結(jié)論屬性之間的關(guān)系，應(yīng)將其分解為完全協(xié)調(diào)和完全論屬性之間的關(guān)系，應(yīng)將其分解為完全協(xié)調(diào)和完全不協(xié)調(diào)的兩個(gè)決策表。不協(xié)調(diào)的兩個(gè)決策表。1. 協(xié)調(diào)的決策表協(xié)調(diào)的決策表U條件屬性條件屬性結(jié)論屬性結(jié)論屬性頭疼頭疼肌肉疼肌肉疼體溫體溫流感流感1是是是是正常正常否否2是是是是高高是是3是是是是很高很高是是4否否是是正常正常否否5否否否否高高否否6否否是是很高很高是是設(shè)設(shè)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é)調(diào)的。該決策表是協(xié)調(diào)的。定義定義，設(shè)，設(shè)T = ( U , C D) 是決策表，如果去掉條件屬性是決策表，如果去掉條件屬性c，得到的表得到的表T1 = (U , Cc , D) 與表與表T 相比，有：相比，有：POSC-c( D) = POSC(D)則稱條件屬性則稱條件屬性c是關(guān)于是關(guān)于D可省的，否則稱條件屬性可省的，否則稱條件屬性c是關(guān)于是關(guān)于

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

46、e110220201112320011411022510201622011721112801101一個(gè)決策表：一個(gè)決策表：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é)調(diào)的。，不是協(xié)調(diào)的。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矛盾矛盾矛盾矛盾分解為如下兩個(gè)表：分解為如下兩個(gè)表：Uabcde3200114110226220

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

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

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

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

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

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

53、的析取邏輯表達(dá)式。（3）將所有的析取邏輯表達(dá)式進(jìn)行合取運(yùn)算，得）將所有的析取邏輯表達(dá)式進(jìn)行合取運(yùn)算，得一個(gè)最簡(jiǎn)合取范式一個(gè)最簡(jiǎn)合取范式T。（4）將合取范式）將合取范式T轉(zhuǎn)換為析取范式的形式。轉(zhuǎn)換為析取范式的形式。（5）輸出屬性約簡(jiǎn)結(jié)果。）輸出屬性約簡(jiǎn)結(jié)果。基于分辨矩陣和邏輯運(yùn)算的屬性約簡(jiǎn)算法可以得到基于分辨矩陣和邏輯運(yùn)算的屬性約簡(jiǎn)算法可以得到?jīng)Q策表的所有可能的屬性約簡(jiǎn)結(jié)果，它實(shí)際上是將對(duì)屬?zèng)Q策表的所有可能的屬性約簡(jiǎn)結(jié)果，它實(shí)際上是將對(duì)屬性組合情況的搜索演變成為邏輯公式的簡(jiǎn)化性組合情況的搜索演變成為邏輯公式的簡(jiǎn)化 。時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(2m)，屬，屬NP問(wèn)題。問(wèn)題。一個(gè)氣象決策表一個(gè)氣象

54、決策表U條件屬性條件屬性結(jié)論屬性結(jié)論屬性天氣天氣a溫度溫度b濕度濕度 c有風(fēng)否有風(fēng)否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é)調(diào)的。，是協(xié)調(diào)的。12345678910111213141aababcabcdbcabcbcdabd

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

56、10320P11121P12221P13210P14321N約簡(jiǎn)結(jié)果約簡(jiǎn)結(jié)果2：a,c,dU條件屬性條件屬性結(jié)論屬性結(jié)論屬性天氣天氣a濕度濕度 c有風(fēng)否有風(fēng)否de1110N2111N3210P4310P5320P6321N7221P8110N9120P10320P11121P12211P13220P14311N利用分辨矩陣求核利用分辨矩陣求核命題：命題：在分辨矩陣中，所有單項(xiàng)屬性構(gòu)成決策表的在分辨矩陣中，所有單項(xiàng)屬性構(gòu)成決策表的核。核。12345678910111213141aababcabcdbcabcbcdabdac2adabdabcdabcbcdabcdbcabacd3abcdababd

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

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

59、算法歸納屬性約簡(jiǎn)算法 算法描述：算法描述： 步驟步驟1：求核：求核COREC(D)；步驟步驟2：求：求最小屬性約簡(jiǎn)最小屬性約簡(jiǎn)minC(D); （1）令）令X=COREC(D)，L=D- -X=a1,a2,a3am，T(L)表示表示L的的冪集，冪集，Ti(L)為為L(zhǎng)的的i（1im）階冪字集；）階冪字集；（2）如果）如果DOSX(D)=DOSC(D)，則，則minC(D)=X，轉(zhuǎn)，轉(zhuǎn)(10)；（3）i=1，F(xiàn)lag=0；（4）Y=Ti(L)；（5）任意取）任意取yY，A=Xy，計(jì)算，計(jì)算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，轉(zhuǎn)，轉(zhuǎn)(5)；（8）如果）如果Flag=1,則則minC(D)=Z，轉(zhuǎn)（，轉(zhuǎn)（10）;（9）i = i+1,如果如果im，則轉(zhuǎn)（，則轉(zhuǎn)（4）；）；（10）結(jié)束）結(jié)束添加添加y找到一個(gè)約簡(jiǎn)找到一個(gè)約簡(jiǎn)9.4.5 基于屬性重要性的屬性約簡(jiǎn)基于屬性重要性的屬性約簡(jiǎn)輸入輸入：決策表：決策表S=。輸出輸出：條件屬性：條件屬性C相對(duì)于決策屬性相對(duì)于決策屬性D的一個(gè)相對(duì)約簡(jiǎn)。的一個(gè)相對(duì)約簡(jiǎn)。（1）計(jì)算）計(jì)算C相對(duì)于相對(duì)于D的核的核COREC(D)；（2）令）令B=COREC(D)，如果，轉(zhuǎn)到（，如果，轉(zhuǎn)到（5）（3）對(duì)于）對(duì)于C