第11章粗糙集理論

1、數(shù)據(jù)挖掘原理與數(shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典應(yīng)用寶典 元昌安元昌安 主編主編 鄧松李文敬劉海濤編著鄧松李文敬劉海濤編著 電子工業(yè)出版社電子工業(yè)出版社 本章包括本章包括： 粗糙集的基本概念粗糙集的基本概念 知識(shí)表達(dá)知識(shí)表達(dá) 粗糙集在數(shù)據(jù)預(yù)處理中的應(yīng)用粗糙集在數(shù)據(jù)預(yù)處理中的應(yīng)用v粗糙集理論是由波蘭華沙理工大學(xué)粗糙集理論是由波蘭華沙理工大學(xué)PawlakPawlak教教授于授于2020世紀(jì)世紀(jì)8080年代初提出的一種研究不完整、年代初提出的一種研究不完整、不確定知識(shí)和數(shù)據(jù)的表達(dá)、學(xué)習(xí)、歸納的理不確定知識(shí)和數(shù)據(jù)的表達(dá)、學(xué)習(xí)、歸納的理論方法，它是一種刻畫(huà)不完整性和不確定性論方法，它是

2、一種刻畫(huà)不完整性和不確定性的數(shù)學(xué)工具，能有效地分析不精確、不一致的數(shù)學(xué)工具，能有效地分析不精確、不一致( (inconslsteniinconslsteni) )、不完整不完整( (incomPleteincomPlete) )等各等各種不完備的信息，還可以對(duì)數(shù)據(jù)進(jìn)行分析和種不完備的信息，還可以對(duì)數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)推理，從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。律。v粗糙集在機(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)域都納推理、數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)、模式識(shí)別等領(lǐng)域都得到了廣泛的應(yīng)用。得到了廣

3、泛的應(yīng)用。v粗糙集應(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)行分析和學(xué)習(xí)的能力，具有廣泛的應(yīng)用前景和實(shí)用價(jià)值。的應(yīng)用前景和實(shí)用價(jià)值。v粗糙集方法僅利用數(shù)據(jù)本身提供的信息，無(wú)須任何粗糙集方法僅利用數(shù)據(jù)本身提供的信息，無(wú)須任何先驗(yàn)知識(shí)。先驗(yàn)知識(shí)。v粗糙集是一個(gè)強(qiáng)大的數(shù)據(jù)分析工具，它能表達(dá)和處粗糙集是一個(gè)強(qiáng)大的數(shù)據(jù)分析工具，它能表達(dá)和處理不完備信息；能在保留關(guān)鍵信息的前提下對(duì)數(shù)據(jù)理不完備信息；能在保留關(guān)鍵信息的前提下對(duì)數(shù)據(jù)進(jìn)行化簡(jiǎn)并求得知識(shí)的最小表達(dá)式；能識(shí)別并評(píng)估進(jìn)行化簡(jiǎn)并求得知識(shí)的最小表達(dá)式；能識(shí)

4、別并評(píng)估數(shù)據(jù)之間的依賴關(guān)系，揭示出概念的簡(jiǎn)單模式；能數(shù)據(jù)之間的依賴關(guān)系，揭示出概念的簡(jiǎn)單模式；能從經(jīng)驗(yàn)數(shù)據(jù)中獲取易于證實(shí)的規(guī)則知識(shí)。從經(jīng)驗(yàn)數(shù)據(jù)中獲取易于證實(shí)的規(guī)則知識(shí)。v粗糙集的研究對(duì)象是由一個(gè)多值屬性粗糙集的研究對(duì)象是由一個(gè)多值屬性( (特征、癥狀、特征、癥狀、特性等特性等) )集合描述的一個(gè)對(duì)象集合描述的一個(gè)對(duì)象( (觀察、病歷等觀察、病歷等) )集合，集合，對(duì)于每個(gè)對(duì)象及其屬性都有一個(gè)值作為其描述符號(hào)，對(duì)于每個(gè)對(duì)象及其屬性都有一個(gè)值作為其描述符號(hào)，對(duì)象、屬性和描述符是表達(dá)決策問(wèn)題的對(duì)象、屬性和描述符是表達(dá)決策問(wèn)題的3 3個(gè)基本要個(gè)基本要素。素。v粗糙集理論逐漸應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域中，并在對(duì)

5、大粗糙集理論逐漸應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域中，并在對(duì)大型數(shù)據(jù)庫(kù)中不完整數(shù)據(jù)進(jìn)行分析和學(xué)習(xí)方面取得了型數(shù)據(jù)庫(kù)中不完整數(shù)據(jù)進(jìn)行分析和學(xué)習(xí)方面取得了顯著的成果，使得粗糙集理論及數(shù)據(jù)挖掘的研究成顯著的成果，使得粗糙集理論及數(shù)據(jù)挖掘的研究成為熱點(diǎn)領(lǐng)域。最近幾年，粗糙集理論越來(lái)越受到眾為熱點(diǎn)領(lǐng)域。最近幾年，粗糙集理論越來(lái)越受到眾多研究人員的重視，它的應(yīng)用研究得到了很大的發(fā)多研究人員的重視，它的應(yīng)用研究得到了很大的發(fā)展。展。 v 知識(shí)是人類通過(guò)實(shí)踐對(duì)客觀世界的運(yùn)動(dòng)規(guī)律的知識(shí)是人類通過(guò)實(shí)踐對(duì)客觀世界的運(yùn)動(dòng)規(guī)律的認(rèn)識(shí)，是人類實(shí)踐經(jīng)驗(yàn)的總結(jié)和提煉，具有抽象和認(rèn)識(shí)，是人類實(shí)踐經(jīng)驗(yàn)的總結(jié)和提煉，具有抽象和普遍的特性。普遍的特

6、性。v 從認(rèn)知科學(xué)的觀點(diǎn)來(lái)看，知識(shí)來(lái)源于人類對(duì)客從認(rèn)知科學(xué)的觀點(diǎn)來(lái)看，知識(shí)來(lái)源于人類對(duì)客觀事物的分類能力，概念是事物類別的描述或者符觀事物的分類能力，概念是事物類別的描述或者符號(hào)，知識(shí)則是概念之間的關(guān)系和聯(lián)系。任何一個(gè)物號(hào)，知識(shí)則是概念之間的關(guān)系和聯(lián)系。任何一個(gè)物種都是由一些知識(shí)來(lái)描述與分類的，利用物種的不種都是由一些知識(shí)來(lái)描述與分類的，利用物種的不同屬性知識(shí)描述來(lái)產(chǎn)生對(duì)物種的不同分類。同屬性知識(shí)描述來(lái)產(chǎn)生對(duì)物種的不同分類。v集合上的等價(jià)關(guān)系和集合上的劃分是一一對(duì)應(yīng)，相集合上的等價(jià)關(guān)系和集合上的劃分是一一對(duì)應(yīng)，相互唯一決定的。從數(shù)學(xué)意義上講，集合上的等價(jià)關(guān)互唯一決定的。從數(shù)學(xué)意義上講，集合上的

7、等價(jià)關(guān)系和集合的劃分是等價(jià)的概念，即劃分就是分類。系和集合的劃分是等價(jià)的概念，即劃分就是分類。v定義定義11-1 11-1 設(shè)討論的對(duì)象組成的有限集合，稱為設(shè)討論的對(duì)象組成的有限集合，稱為論域論域( (Universe)Universe)，對(duì)于論域中由等價(jià)關(guān)系劃分出來(lái)對(duì)于論域中由等價(jià)關(guān)系劃分出來(lái)的任意子集，都可以稱為論域的任意子集，都可以稱為論域U U中的一個(gè)概念中的一個(gè)概念( (concept)concept)或范疇或范疇( (category)category)。為規(guī)范起見(jiàn)，認(rèn)為為規(guī)范起見(jiàn)，認(rèn)為空集必也是一個(gè)概念。論域空集必也是一個(gè)概念。論域U U中的任意概念族稱為中的任意概念族稱為關(guān)于論

8、域的抽象知識(shí)，它代表了對(duì)論域中個(gè)體的分關(guān)于論域的抽象知識(shí)，它代表了對(duì)論域中個(gè)體的分類，簡(jiǎn)稱為知識(shí)。類，簡(jiǎn)稱為知識(shí)。v定義定義11-2 11-2 K=(U,R)K=(U,R)其中其中K K為知識(shí)庫(kù)，為知識(shí)庫(kù)，U U為全體對(duì)象為全體對(duì)象的集合稱為論域，的集合稱為論域，R R為論域?yàn)檎撚騏 U上的等價(jià)關(guān)系上的等價(jià)關(guān)系( (等價(jià)關(guān)等價(jià)關(guān)系與分類的概念等同系與分類的概念等同) )，它是一種屬性或多種屬性，它是一種屬性或多種屬性的集合?？梢愿鶕?jù)不同的的集合?？梢愿鶕?jù)不同的R R對(duì)對(duì)U U進(jìn)行不同形式的分類。進(jìn)行不同形式的分類。知識(shí)庫(kù)也被稱作近似空間。知識(shí)庫(kù)也被稱作近似空間。Uv定義定義11-3 11-3

9、K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)是兩個(gè)知識(shí)庫(kù)，若是兩個(gè)知識(shí)庫(kù)，若IND(P)=IND(Q)IND(P)=IND(Q)，則稱則稱K K和和M(M(或或Q Q和和P)P)是等價(jià)的，是等價(jià)的， 記作記作 ( (或者或者) ) 。因此，當(dāng)。因此，當(dāng)K K和和M M是同樣的基本是同樣的基本范疇集時(shí)，知識(shí)庫(kù)范疇集時(shí)，知識(shí)庫(kù)K K和和M M中的知識(shí)都能使我們確切地中的知識(shí)都能使我們確切地表達(dá)關(guān)于論域的完全相同的事實(shí)。這個(gè)概念意味著表達(dá)關(guān)于論域的完全相同的事實(shí)。這個(gè)概念意味著可以用不同的屬性集對(duì)對(duì)象進(jìn)行描述，以表達(dá)關(guān)于可以用不同的屬性集對(duì)對(duì)象進(jìn)行描述，以表達(dá)關(guān)于論域的完全相同的事實(shí)

10、。論域的完全相同的事實(shí)。v對(duì)于兩個(gè)知識(shí)庫(kù)對(duì)于兩個(gè)知識(shí)庫(kù)K=(U,P)K=(U,P)和和M=(U,Q)M=(U,Q)，當(dāng)當(dāng) 時(shí)，稱知識(shí)庫(kù)時(shí)，稱知識(shí)庫(kù)P P比知識(shí)庫(kù)比知識(shí)庫(kù)Q Q更精細(xì)，或者說(shuō)更精細(xì)，或者說(shuō)Q Q比比P P更粗更粗糙。當(dāng)糙。當(dāng)P P比比Q Q更精細(xì)時(shí)，我們稱更精細(xì)時(shí)，我們稱P P為為Q Q的特化，的特化，Q Q為為P P的的推廣。由以上可知，推廣是將某些范疇組合在一起，推廣。由以上可知，推廣是將某些范疇組合在一起，而特化則是將范疇分割成更小的單元。而特化則是將范疇分割成更小的單元。KMPQIND(P)IND(Q)v在粗糙集理論中，在粗糙集理論中，“知識(shí)知識(shí)”被認(rèn)為是一種分類的能被認(rèn)

11、為是一種分類的能力。不可分辨關(guān)系的概念是粗糙集理論的基石，它力。不可分辨關(guān)系的概念是粗糙集理論的基石，它揭示出論域知識(shí)的顆粒狀結(jié)構(gòu)。假定關(guān)于論域的某揭示出論域知識(shí)的顆粒狀結(jié)構(gòu)。假定關(guān)于論域的某種知識(shí)，并使用屬性和屬性值來(lái)描述論域中的對(duì)象，種知識(shí)，并使用屬性和屬性值來(lái)描述論域中的對(duì)象，如果兩個(gè)對(duì)象如果兩個(gè)對(duì)象( (或?qū)ο蠹匣驅(qū)ο蠹? )具有相同的屬性和屬性具有相同的屬性和屬性值，則它們之間具有不可分辨關(guān)系。值，則它們之間具有不可分辨關(guān)系。v定義定義11-411-4設(shè)R是非空集合U上的二元系，如果它是自反的、對(duì)稱的和可傳遞的，則稱R為U上的等價(jià)關(guān)系。若， 則稱x與y有關(guān)系，記為 ；若 ，則稱x

12、與y沒(méi)有關(guān)系，記為 。等價(jià)關(guān)系的一個(gè)重要特點(diǎn)是用它可以構(gòu)成U的一個(gè)劃分。劃分即是分類，將研究對(duì)象分成不同的類，這些類之間互不相交，且每一對(duì)象均包含在某一類中。 xRy(x,y) R(x,y) R_x Ryv定義定義11-511-5設(shè)U是一個(gè)論域，R是U上的等價(jià)關(guān)系，U/R表示U上由R導(dǎo)出的所有等價(jià)類。v 表示包含元素xU的R等價(jià)類。一個(gè)知識(shí)庫(kù)就是一個(gè)關(guān)系系統(tǒng)K =U ,P，其中U是論域，P是U上的一個(gè)等價(jià)類簇。如果 且 ，則 (Q的所有等價(jià)類的交也是一個(gè)等價(jià)關(guān)系)，稱Q為不可分辨關(guān)系,記作IND(Q)。 RxQPQQv給定論域給定論域U U，一族等價(jià)關(guān)系一族等價(jià)關(guān)系R R將將U U劃分為互不相

13、交的劃分為互不相交的基本等價(jià)類基本等價(jià)類U/RU/R。令令 XgUXgU為為R R上的一個(gè)等價(jià)關(guān)系。上的一個(gè)等價(jià)關(guān)系。v當(dāng)能表達(dá)成某些基本等價(jià)類的并集時(shí)，稱為可定義當(dāng)能表達(dá)成某些基本等價(jià)類的并集時(shí)，稱為可定義的；否則稱為不可定義的。的；否則稱為不可定義的。R R可定義集能在這個(gè)知可定義集能在這個(gè)知識(shí)庫(kù)中被精確地定義，所以又稱為識(shí)庫(kù)中被精確地定義，所以又稱為R R精確集。精確集。vR R不可定義集不能在這個(gè)知識(shí)庫(kù)中被精確定義，只不可定義集不能在這個(gè)知識(shí)庫(kù)中被精確定義，只能通過(guò)集合逼近的方式來(lái)刻畫(huà)，因此也稱為能通過(guò)集合逼近的方式來(lái)刻畫(huà)，因此也稱為R R粗糙粗糙集集 ( (RoughsetRough

14、set) )。v兩個(gè)精確集，兩個(gè)精確集，v即粗糙集的上近似集即粗糙集的上近似集 ( (UpperApproximationUpperApproximation) )和下和下近似集近似集 ( (LowerApproximationLowerApproximation) )來(lái)近似地定義粗糙來(lái)近似地定義粗糙集。集。v粗糙集理論引入上近似和下近似等概念來(lái)刻畫(huà)知識(shí)粗糙集理論引入上近似和下近似等概念來(lái)刻畫(huà)知識(shí)的不確定性和模糊性。的不確定性和模糊性。v定義11-6設(shè)集合 ，R是一個(gè)等價(jià)關(guān)系，稱 v 為集合X的R下近似集；v稱 為集合X的R上近似集；v稱集合 為X的R邊界域；v稱 為X的R正域；v稱 為X的R

15、負(fù)域。X URRX= x |x U |, xX且RRX= x |xU |,xX且()RBNXRXRXRPOS (X)=RXRNEG (X)=U-RXv例例11-1 11-1 設(shè)論域 ，U上的一族等價(jià)關(guān)系R=R1,R2,R1和R2是兩個(gè)等價(jià)關(guān)系。根據(jù)這兩個(gè)等價(jià)關(guān)系可以將論域U進(jìn)行劃分：v 和 。U/R1中的 ，代表 的等價(jià)類。v論域U被R劃分的基本等價(jià)類為: v集合 是U上的一個(gè)子集。則X無(wú)法用基本等價(jià)類U/R的并集精確表示，所以X是U上的一個(gè)粗糙集合。故有:vX的下近似集為: ；vX的上近似集為: ；vX的負(fù)區(qū)域: 。12345678U=e ,e ,e ,e ,e ,e ,e ,e 21234

16、5678U/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 v知識(shí)表達(dá)在智能數(shù)據(jù)處理中占有十分重要的地位。知識(shí)表達(dá)在智能數(shù)據(jù)處理中占有十分重要的地位。在智能系統(tǒng)中，經(jīng)常會(huì)碰到要處理的對(duì)象可能是用在智能系統(tǒng)中，經(jīng)常會(huì)碰到要處理的對(duì)象可

17、能是用語(yǔ)言方式表達(dá)，也可能使用數(shù)據(jù)表達(dá)；可能是精確語(yǔ)言方式表達(dá)，也可能使用數(shù)據(jù)表達(dá)；可能是精確的數(shù)據(jù)，可能會(huì)有一些缺省的信息或者相互矛盾的的數(shù)據(jù)，可能會(huì)有一些缺省的信息或者相互矛盾的信息。信息。v為了處理這些數(shù)據(jù)，我們需要進(jìn)行知識(shí)的表達(dá)，即為了處理這些數(shù)據(jù)，我們需要進(jìn)行知識(shí)的表達(dá)，即知識(shí)表達(dá)系統(tǒng)。決策表是特殊的知識(shí)表達(dá)系統(tǒng)。知識(shí)表達(dá)系統(tǒng)。決策表是特殊的知識(shí)表達(dá)系統(tǒng)。 v定義定義11-711-7一個(gè)知識(shí)表達(dá)系統(tǒng)一個(gè)知識(shí)表達(dá)系統(tǒng)S S可以定義為，其中可以定義為，其中U U為對(duì)象的集合，稱為論域；為對(duì)象的集合，稱為論域；= =R R為屬性集合；子集為屬性集合；子集C C和和D D分別稱為條件屬性和決

18、策屬性；分別稱為條件屬性和決策屬性； 為屬性值的集為屬性值的集合；表示了屬性的屬性值范圍；是一個(gè)信息函數(shù)，合；表示了屬性的屬性值范圍；是一個(gè)信息函數(shù)，它指定了它指定了U U中每一對(duì)象中每一對(duì)象x x的屬性值。的屬性值。v知識(shí)表達(dá)系統(tǒng)的數(shù)據(jù)以知識(shí)表達(dá)系統(tǒng)的數(shù)據(jù)以關(guān)系表關(guān)系表的形式表示，關(guān)系表的形式表示，關(guān)系表的行對(duì)應(yīng)要研究的對(duì)象，列對(duì)應(yīng)對(duì)象的屬性，對(duì)象的行對(duì)應(yīng)要研究的對(duì)象，列對(duì)應(yīng)對(duì)象的屬性，對(duì)象的信息是通過(guò)指定對(duì)象的各屬性值來(lái)表達(dá)的信息是通過(guò)指定對(duì)象的各屬性值來(lái)表達(dá)。v例例11-211-2：表11.1是一個(gè)轎車信息決策表，條件屬性集為e1,e2,e3,e4分別代表價(jià)格、油耗、速度和安全性，決策屬

19、性為d，表示質(zhì)量。 表表11.1 轎車信息決策表轎車信息決策表車型車型U Ue1e1e2e2e3e3e4e4d d1 1高低快好高2 2低高中差低3 3中中慢一般低4 4中高慢一般中5 5低高中差低6高低快好高v決策表包含了某一領(lǐng)域的大量數(shù)據(jù)，是領(lǐng)域的樣本決策表包含了某一領(lǐng)域的大量數(shù)據(jù)，是領(lǐng)域的樣本數(shù)據(jù)庫(kù)。它記錄了大量樣本的屬性值和決策情況，數(shù)據(jù)庫(kù)。它記錄了大量樣本的屬性值和決策情況，是領(lǐng)域知識(shí)的載體。是領(lǐng)域知識(shí)的載體。v知識(shí)獲取的目的就是要通過(guò)分析這個(gè)實(shí)例庫(kù)來(lái)得到知識(shí)獲取的目的就是要通過(guò)分析這個(gè)實(shí)例庫(kù)來(lái)得到該領(lǐng)域中有用的、規(guī)律性知識(shí)。決策表在決策應(yīng)用該領(lǐng)域中有用的、規(guī)律性知識(shí)。決策表在決策應(yīng)

20、用中有十分重要的地位，可用于表達(dá)絕大多數(shù)決策問(wèn)中有十分重要的地位，可用于表達(dá)絕大多數(shù)決策問(wèn)題。對(duì)于決策表，最重要的是決策規(guī)則的生成。題。對(duì)于決策表，最重要的是決策規(guī)則的生成。v定義定義11-811-8 設(shè)U=U1，U2，U3，Un 是一個(gè)論域 ,U (i=1,2,，n)是研究對(duì)象。 P是屬性集, P = C + D , C 為條件屬性集, D 為決策屬性集,T = ( U , P , C , D) 是決策表。決策表中每一行就是一條決策規(guī)則: dx| C -dx | D , dx | B 表示個(gè)體x關(guān)于屬性集B 的值。v定義定義11-911-9 若決策表T 中任意的dxdy,由dx | C =

21、dy | C ,可得dx| D = dy| D ,則稱決策規(guī)則dx 是一致的,否則,稱決策規(guī)則dx 是不一致的。如果T 中每條決策規(guī)則都是一致的,則稱決策表T 是一致的,否則稱決策表T是不一致的。v定義定義11-1011-10 設(shè)T = ( U , P, C , D) 是決策表,如果去掉條件屬性Pi，得到的表T1 = ( U , P -Pi , C - Pi , D) 與表T 相比,有PosC ( D) = Pos ( D)，則稱屬性Pi是關(guān)于D可省的,否則稱屬性Pi 是關(guān)于D 不可省的, 是D 關(guān)于B 的正區(qū)域，其中 。 PosB (D) = YU/IND(D)B(Y)B (Y) = X U

22、/IND(B) : X Yv定義定義11-1111-11 如果決策表中每個(gè)條件屬性都是關(guān)于D 不可省的,則稱條件屬性集C 是關(guān)于D獨(dú)立的，否則稱C 是關(guān)于D 依賴的。v定義定義11-1211-12 決策表T = ( U ,P , C , D) 中條件屬性集C 的一個(gè)子集B 是關(guān)于D 獨(dú)立的,并且PosB ( D) = PosC ( D) ,則稱B 是C 的一個(gè)D約簡(jiǎn)。v所謂屬性約簡(jiǎn)，就是在保持知識(shí)庫(kù)分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性。v一個(gè)屬性集合可能有多個(gè)約簡(jiǎn)。v屬性約簡(jiǎn)的目標(biāo)就是要從條件屬性集合中發(fā)現(xiàn)部分必要的條件屬性，使得根據(jù)這部分條件屬性形成的相對(duì)于決策屬性的分類和所有

23、條件屬性所形成的相對(duì)于決策屬性的分類一致，即和所有條件屬性相對(duì)于決策屬性D有相同的分類能力。v屬性集合P的所有約簡(jiǎn)的交集定義為P的核(Core)，記作core(P)，核是表達(dá)知識(shí)必不可少的重要屬性集。v核的概念具有兩方面的意義:v(l)因?yàn)楹税谒屑s簡(jiǎn)之中，所以核可以作為所有約簡(jiǎn)的計(jì)算基礎(chǔ)。v(2)核在知識(shí)約簡(jiǎn)中是不能消去的特征集合。v直接由分辨矩陣來(lái)求取系統(tǒng)的核集Pc。不失一般性, 假定系統(tǒng)T 對(duì)于屬性集P 是可分辨的。則系統(tǒng)的核集由以下定理1確定。v定理定理11-111-1P 中任一屬性P Pc, 充要條件為:D(P)中至少存在一個(gè)元素 , 滿足 。其中， 元素都是屬性集P的一個(gè)子集，

24、元素Dij定義如下：v 其中i,j=1,2,3,，m。（1）v （2）ijD (P)ijkD (P ) = P ijDijij1ij2ij3ijnD =d ,d ,d ,d ijk,d=1,2,3, .,ikjkkikjkUUknP UUv命題命題11-111-1從信息系統(tǒng)的決策表中將屬性集P中逐一移去, 每移去一個(gè)屬性即刻檢查其決策表, 如果不出現(xiàn)新的不一致, 則屬性是可被約去的；否則屬性不能約去。v命題命題11-211-2 全體不可約去屬性集稱為核集。v屬性集合的約簡(jiǎn)和核的關(guān)系如下:v式中red(P)表示P的所有約簡(jiǎn)。core(P)含有P的全部約簡(jiǎn)中共同的等價(jià)關(guān)系，是屬性集合P中不可缺少的

25、重要屬性集。core(P)=red(P)v屬性約簡(jiǎn)只是在一定程度上去掉了決策表中冗余屬性，還是沒(méi)有充分去掉決策表中的冗余信息。在判斷某個(gè)對(duì)象屬于某類時(shí)，其屬性的取值不同，對(duì)分類產(chǎn)生的影響也不同。v例如，判斷人的體形(瘦、中、胖)時(shí)，體重是主要屬性。但若體重屬性值為75Kg時(shí)，此人的體形要結(jié)合其身高、性別等屬性才能確定。如果體重屬性值為160Kg時(shí)，幾乎肯定其體形為胖，這時(shí)身高、性別已不重要。v命題11-3設(shè) 是決策表上的一條決策規(guī)則, 屬性值v 是一可被約去當(dāng)且僅當(dāng) , 其中 和 均為決策表上的邏輯公式8。( ) ( -v) v決策表包含了某一領(lǐng)域的大量數(shù)據(jù)，是領(lǐng)域的樣本數(shù)據(jù)庫(kù)。它記錄了大量樣

26、本的屬性值和決策情況，是領(lǐng)域知識(shí)的載體。v知識(shí)獲取的目的就是要通過(guò)分析這個(gè)實(shí)例庫(kù)來(lái)得到該領(lǐng)域中有用的、規(guī)律性知識(shí)。v從決策表分析得到的規(guī)律性知識(shí)，通常采用決策規(guī)則的形式記錄下來(lái)。下面給出決策規(guī)則的形式化描述。v定義定義11-1311-13定義公式如下：v(1)(a,v)(或?qū)憺閍v，aA，vVa，表示屬性a的取值為v)是公式且是原子公式。v(2)如果A和B都是公式，那么 ,AB都是公式。v(3)只有按定義(1)和(2)所組成的式子是公式。v對(duì)于決策表 是決策表，A=CD屬性集合，子集 和 分別為條件屬性集和決策屬性集，有關(guān)決策規(guī)則的定義如下：T = ( U , P , C , D)A,A B,

27、A B,(A)iC=c |i=1,2,njD=d |j=1,2,mv定義定義11-1411-14公式 稱為P基本公式，這里 ， P， 。v定義定義11-1511-1511公式 稱為Q基本公式，這里 ， 。v定義定義11-1611-1611公式AB為決策規(guī)則，如果A是P基本公式且B是Q基本公式，則AB是基本決策規(guī)則。1122nn(c ,v )(c ,v )(c ,v )iicvV12nc ,c ,c PC1122mm(d ,v )(d ,v )(d ,v )jjdvV12md ,d ,d Q,QDv可辨識(shí)矩陣（也稱分明矩陣）是由波蘭數(shù)學(xué)家Skowron.A教授提出的。v定義定義11-1711-1

28、7設(shè)相容決策表T=，A=CD， 和D=d分別為條件屬性集和決策屬性集， 是論域， 是樣本 在屬性上的取值。 表示可辨識(shí)矩陣中第i行j列的對(duì)象，則可辨識(shí)矩陣定義為：其中， iCc |i=1,2,m12U=x ,nxxijc (x )jxDM (i,j)kkjijDijc |cC( )(x ),d(x )d(x )M (i,j)=0 , d(x )d(x ) kikcxc,1,2,i jnv由上述定義可以看出，可辨識(shí)矩陣是一個(gè)對(duì)稱矩陣。當(dāng)兩個(gè)樣本的決策屬性取同時(shí)，對(duì)象值為0；當(dāng)兩個(gè)樣本的決策屬性不同且可以通過(guò)某些條件屬性的取值加以區(qū)分時(shí)，對(duì)象值為這兩個(gè)樣本屬性值不同的條件屬性集合。v一個(gè)數(shù)據(jù)集的所

29、有約簡(jiǎn)可以通過(guò)構(gòu)造可辨識(shí)并且化簡(jiǎn)由可辨識(shí)矩陣導(dǎo)出的區(qū)分函數(shù)而得到，所有的蘊(yùn)含式包含的屬性就是決策表的所有約簡(jiǎn)集合。v算法算法11-111-1可辨識(shí)矩陣屬性約簡(jiǎn)算法可辨識(shí)矩陣屬性約簡(jiǎn)算法 v輸入輸入：相容決策表DT=，A=CD是屬性集合；v輸出輸出：約簡(jiǎn)的屬性集。v步驟：步驟：vStep1計(jì)算決策表的可辨識(shí)矩陣 ；/根據(jù)分辨矩陣的定義求元素vStep 2對(duì)于可辨識(shí)矩陣中所有取值為非空集合的對(duì)象 ，建立相應(yīng)的析取邏輯表達(dá)式,v , ；DMijMijTijTiijcMicvStep 3將所有的析取邏輯表達(dá)式 進(jìn)行合取運(yùn)算，得一個(gè)合取范式T，即 ；vStep 4將合取范式L轉(zhuǎn)換為析取范式的形式，得 ；

30、vStep 5輸出屬性約簡(jiǎn)結(jié)果。v基于可辨識(shí)矩陣和邏輯運(yùn)算的屬性約簡(jiǎn)算法可以得到?jīng)Q策表的所有可能的屬性約簡(jiǎn)結(jié)果，它實(shí)際上是將對(duì)屬性組合情況的搜索演變成為邏輯公式的簡(jiǎn)化 0TijMijTijTTiiTv信息熵是信息論的核心內(nèi)容，它最早應(yīng)用于通信領(lǐng)域。由于信息熵可以刻畫(huà)信息劃分粒度的大小，也被廣泛應(yīng)用于信息不確定性的度量。v設(shè)U為一個(gè)論域,可以認(rèn)為U上任一屬性集合(知識(shí)、等價(jià)關(guān)系簇)是定義在U上的子集組成的R代數(shù)上的一個(gè)隨機(jī)變量,其概率分布可通過(guò)如下方法來(lái)確定。v定義定義11-1811-18設(shè)P,Q在U上導(dǎo)出的劃分分別為X,Yv則P,Q在U的子集組成的代數(shù)上的概率分布為12,nXX XX12 ,m

31、YY YY1212:()()()nnXXXXpp Xp Xp X1212:( )()()mmYYYYpp Yp Yp Y其中， ； v定義定義11-1911-19知識(shí)P的熵H(P)定義為 。(),1,2,iiXp XinU(),1,2,jjYp YjmU1( )()log( ()niiiH Pp Xp X v定義定義11-2011-20決策信息系統(tǒng)S=(U,A=CD,V,F),C、D為U上的一個(gè)等價(jià)關(guān)系集合，C、D在U上導(dǎo)出的劃分分別為:v則D相對(duì)于C的條件信息熵H(D|C)為：v其中，12U/IND(C)=,nXXX12U/IND(D)= ,mY YYU/C/ii=11H(D|C)=-p(X

32、 )(|)log( (|)U Djijijp YXp YX(|)jijiiYXp YXXv定理定理11-211-2在信息系統(tǒng)S=(U,A=CD,V,F)中， ，若H(D|B)=H(D|(B-b)則稱b為B中相對(duì)于D是可省的（不必要的）；否則b為B中相對(duì)于D是不可省的。對(duì) ,若其任一元素D都是必要的，則稱B相對(duì)于D是獨(dú)立的。v定義定義11-2111-21在決策信息系統(tǒng)S（U,A=CD,V,F）中，若 , H(D|B)=H(D|C)且B相對(duì)與D是獨(dú)立的，則稱B是C關(guān)于D的屬性約簡(jiǎn)。v推論推論11-111-1如果一個(gè)屬性a不能為屬性子集R的分類增加任何信息，即 ，就可以將這個(gè)屬性約簡(jiǎn)。bBC BCB

33、CH (D |R a)= H (D|R)v算法算法11-211-2信息熵的求核算法信息熵的求核算法v輸入輸入：相容決策表T=，A=CD是屬性集合；子集 和D=d分別為條件屬性集和決策屬性集；v輸出輸出：信息熵定義下的核屬性 ；v步驟：步驟：vBeginBegin (1) ；v (2)對(duì)于條件屬性集C中的所有屬性r,如果H(D|C)H(D|C-r),則 ； End EndiCc |i=1,2,mDCO RE(C)DCORE (C)=DDCORE (C)=CORE (C)rCEBARKCC算法是一種比較典型的基于信息熵的屬性約簡(jiǎn)算法。該算法是建立在決策屬性集相對(duì)于條件屬性集的條件熵的基礎(chǔ)上的，以H

34、(D|Ba)作為啟發(fā)式信息，以H(D|B)=H(D|C)作為算法的終止條件。CEBARKCC算法以決策表核屬性集為起點(diǎn)，逐次選擇使H(D|Ba)最小的非核條件屬性a添加到核屬性集中，直到滿足終止條件H(D|B)=H(D|C)v算法算法11-311-3CEBARKCCCEBARKCC算法算法v輸入：輸入：相容決策表T=，A=CD是屬性集合；子集v 和D=d分別為條件屬性集和決策屬性集；v輸出：輸出：該決策表的一個(gè)相對(duì)約簡(jiǎn)B。v步驟：步驟：vStep1計(jì)算決策表S中決策屬性集D相對(duì)條件屬性集C的條件熵H(D|C)；vStep 2計(jì)算條件屬性集C中相對(duì)于決策屬性集D的核屬性Co；vStep 3令B=

35、C0iCc |i=1,2,m a 如果|B|!=0,則計(jì)算條件熵H(D|B),轉(zhuǎn)d)；v b 對(duì)每個(gè)屬性 ,計(jì)算決策屬性集D相對(duì)條件屬性集的條件熵 ；v c 選擇使 c(若同時(shí)有多個(gè)屬性達(dá)到則從中選取一個(gè)與B的屬性值組合數(shù)最少的屬性), , ；vd IF H (D |B )H (D |C) Then b)0icCC(| )iH D Bc(| )iH D Bc0CC iBBcv定義定義11-2211-22設(shè)S=(U,A=CD,V,F)是一個(gè)決策信息系統(tǒng)，其中C是條件屬性集合，D是決策屬性集合，且 ,則對(duì)于任意屬性aC-R的重要度的定義為：v = ,v其中 。RCSGF(a,R,D)=K (R a

36、 ,D )-K (R, D)H(D|R)-H(D|Ra)RK (R, D)=POS (D)/( )CPOS Dv算法算法11-411-4信息熵的屬性約簡(jiǎn)改進(jìn)算法信息熵的屬性約簡(jiǎn)改進(jìn)算法v輸入：輸入：相容決策表T=，A=CD是屬性集合；v子集 和D=d分別為條件屬性集和決策屬性集；v輸出：輸出：決策表T的一個(gè)相對(duì)約簡(jiǎn)P。v步驟：步驟：vStep1計(jì)算決策表T中決策屬性集D相對(duì)條件屬性集C的條件熵H(D|C)；vStep 2計(jì)算條件屬性集C中相對(duì)于決策屬性集D的核屬性Co； Step 3 計(jì)算條件信息熵H(D|P)，轉(zhuǎn)Step 6；iCc |i=1,2,mvStep 4 對(duì)i=1.n,biB中的每

37、個(gè)屬性計(jì)算條件熵H(D|Pbi)，求vSGF（bi,P,D）=H(D|P)-H(D|Pbi)得到屬性bi的重要度SGF（bi,P,D）；vStep 5選擇使SGF（bi,P,D）最大的屬性bi（若同時(shí)有多個(gè)屬性達(dá)到最小值，則從中選取一個(gè)與P的屬性值組合數(shù)最少的屬性），把bi從B中刪除，并把bi增加到P的尾部；同時(shí)從B中刪除使SGF的值為零的屬性bi；vStep 6如果H(D|P)H(D|C) Then Step 4 Step 7從P的尾部開(kāi)始，從后向前判別每個(gè)屬性的a是否可約。如果 ，則從a開(kāi)始向前的屬性都是核屬性，不可約，算法終止；否則，如果H(D|P-a)=H(D|C)，則a是可約簡(jiǎn)的，把

38、a從A中刪除。Cacore ( D)v例11-4：根據(jù)表11.5決策表所示，根據(jù)算法11-4進(jìn)行信息熵的屬性約簡(jiǎn)計(jì)算。表表11.5決策表決策表vU a b c d e fU a b c d e fve1 1 0 1 1 2 1ve2 0 0 1 1 1 0ve3 1 1 0 1 2 0ve4 0 1 0 1 1 1ve5 1 2 2 1 2 0ve6 2 1 0 1 0 1vStep1求出H(D|C)=0；vStep2利用求核算法求出 ；情形一：Step3求出H(D|P)=1;轉(zhuǎn)Step 6,if H(D|P)H(D|C) Then Step4Step4SGF(a,P,D)=H(D)-H(D|

39、a)=0.2075;SGF(b,P,D)=H(D)-H(D|b)=0.2075;SGF(c,P,D)=H(D)-H(D|c)0.2075;SGF(d,P,D)=H(D)-H(D|d)=0;SGF(e,P,D)=H(D)-H(D|e)=0.2705;P=a,B=b,c,e;Step5 選擇屬性a同時(shí)刪除不必要的屬性d。00C =;P=C ;B=a,b,c,d,e情形二：Step3 H(D|P)=0.7925; 轉(zhuǎn)Step 6,if H(D|P)H(D|C) Then Step4Step4 SGF(b,P,D)=H(D|a)-H(D|a,b)=0.7925;SGF(c,P,D)=H(D|a)-H(

40、D|a,c)=0.7925;SGF(e,P,D)=H(D|a)-H(D|a,e)=0；P=a,b,B=c;Step5 選擇屬性b的同時(shí)刪除不必要的屬性e。H（D|P）=H（D|C）=0Step6 P中沒(méi)有可刪除屬性。則相對(duì)約簡(jiǎn)集為P=a,b。v基于粗糙集理論的數(shù)據(jù)預(yù)處理方法，首先對(duì)原始數(shù)據(jù)（原始決策表）進(jìn)行離散化，然后可以通過(guò)兩種方法對(duì)離散化的決策表進(jìn)行屬性約簡(jiǎn)，最后進(jìn)行屬性值的約簡(jiǎn)。我們以一個(gè)醫(yī)療數(shù)據(jù)記錄決策表為例子，給出屬性約簡(jiǎn)求核和屬性值約簡(jiǎn)的過(guò)程。v本節(jié)介紹屬性約簡(jiǎn)的兩種方法：分辨矩陣求核約簡(jiǎn)方法、直接求核集方法。v方法一，分辨矩陣求核約簡(jiǎn)方法方法一，分辨矩陣求核約簡(jiǎn)方法：設(shè)D是一個(gè)m

41、*m階矩陣，其中每一個(gè)元素Dij都是P的一個(gè)子集，元素Dij定義如下：vDij=dij1,dij2,dij3,dijn v 其中i,j=1,2,3,，m。 (1) (2)v說(shuō)明：U,U表示決策表中第i行和第j行兩個(gè)屬性的值；k表示決策表的研究對(duì)象的個(gè)數(shù)，分辨矩陣D是一個(gè)對(duì)角線為0的對(duì)稱矩陣。ijk,d =1,2,3, .,ikjkkikjkUUknP UUv方法二，直接求核集方法方法二，直接求核集方法：用命題11-1、命題11-2直接求核集。 例例11-311-3以下決策表11.2給出了一個(gè)醫(yī)療數(shù)據(jù)記錄表，通過(guò)測(cè)量人的體溫、咳嗽、頭痛、周身痛等癥狀來(lái)確定是否患了流感。表表11.2醫(yī)療記錄表醫(yī)療

42、記錄表v U U 體溫體溫 咳嗽咳嗽 頭痛頭痛 周身痛周身痛 流感流感v1 正常 無(wú) 無(wú) 有 無(wú)v2 正常 無(wú) 有 無(wú) 無(wú)v3 偏高 無(wú) 有 無(wú) 有v4 高 有 有 無(wú) 有v5 高 有 無(wú) 無(wú) 有v6 偏高 有 有 無(wú) 有v其中屬性及屬性值的含義為：v體溫a，正常0，偏高1，高2；咳嗽b，無(wú)0，有1；頭痛c, 無(wú)0，有1；周身痛d，無(wú)1，有1；流感e，無(wú)0，有1。v表表11.3醫(yī)療決策表醫(yī)療決策表vU a b c d eU a b c d ev1 0 0 0 1 0v2 0 0 1 0 0v3 1 0 1 0 1v4 2 1 1 0 1v5 2 1 0 0 1v6 1 1 1 0 1v其中：條

43、件屬性集為a,b,c,d，決策屬性集為e。 根據(jù)粗糙集理論對(duì)表11.3醫(yī)療決策表進(jìn)行數(shù)據(jù)預(yù)處理，處理過(guò)程分兩個(gè)步驟進(jìn)行，一是對(duì)決策表?xiàng)l件屬性集進(jìn)行約簡(jiǎn)求核；二是對(duì)條件屬性值進(jìn)行約簡(jiǎn)。 v下面討論屬性約簡(jiǎn)求核的兩種方法：分辨矩陣直接求核約簡(jiǎn)法和用命題11-1、命題11-2求核約簡(jiǎn)法。v首先，用分辨矩陣直接求核集。用以下舉例說(shuō)明分辨矩陣求核約簡(jiǎn)的方法，如表11.3醫(yī)療決策表所示是一個(gè)知識(shí)系統(tǒng)，U=U1,U2,，Un是論域，C=a,b,c,d 是條件屬性集，D= e 是決策屬性集，。則其相應(yīng)的分辨矩陣為：vD= acacbabcababeabceabeaeabcdeabdeabcdeacdecdv從

44、上述分辨矩陣中可以得出：由于D=e是決策集，不需要約簡(jiǎn)，約簡(jiǎn)的是條件集合C，根據(jù)定理11-1直接求出該知識(shí)系統(tǒng)的核集為 a,b,c 。該約簡(jiǎn)求核集的方法便于計(jì)算機(jī)上實(shí)現(xiàn)。v其次，用方法二直接求核集集。還是以決策表11.3作為知識(shí)系統(tǒng)的例子，求核集的步驟為：v（1）去掉屬性a,對(duì)比每一行屬性值，第4、6行發(fā)生沖突，則屬性a不可約； v（2）去掉屬性b,對(duì)比每一行屬性值，第4、6行發(fā)生沖突，則屬性b不可約； v（3）去掉屬性c,對(duì)比每一行屬性值，第4、5行發(fā)生沖突，則屬性c不可約； v（4）去掉屬性d,對(duì)比每一行屬性值，沒(méi)有發(fā)生沖突，則屬性d可約；v若還有條件屬性，則依次類推。經(jīng)過(guò)約簡(jiǎn)后得到的核集

45、為a,b,c 。v比較兩種求核集的方法，對(duì)于數(shù)據(jù)量大，采用分辨矩陣來(lái)求核集，方便計(jì)算機(jī)來(lái)實(shí)現(xiàn)；第二種方法簡(jiǎn)單易行，方便人工處理。v 屬性值約簡(jiǎn)是在核集基礎(chǔ)上進(jìn)行的，經(jīng)約簡(jiǎn)后的核集用表11.4醫(yī)療核集決策表表示如下：表表11.4醫(yī)療核集決策表醫(yī)療核集決策表 U a b c eU a b c e1 0 0 0 01 0 0 0 02 0 0 1 02 0 0 1 03 1 0 1 13 1 0 1 14 2 1 1 14 2 1 1 15 2 1 0 15 2 1 0 16 1 1 1 16 1 1 1 1根據(jù)命題11-3計(jì)算決策規(guī)則中條件屬性的核值,并確定出一個(gè)最小決策算法，用邏輯語(yǔ)義表示。 v

46、對(duì)于決策規(guī)則1，1a=1,2,1b =1,2,3,1c=1,5,1e=1,2v其中：1a 1b=1,21,2,3=1,2 1e，則c0（表示c屬性值為0）可約；v1a 1c=1,2 1,5=1 1e,則b0（表示b屬性值為0）可約；v1b 1c=1,2,31,5=1 1e,則a0（表示a屬性值為0）可約；v對(duì)于決策規(guī)則2，2a=1,2,2b=1,2,3,2c=2,3,4,6,2e=1,2v其中：2a 2b=1,2 1,2,3=1,2 2,則c1是可約的；v 2a 2c=1,2 2,3,4,6=2 2,則b0是可約的；v 2b 2c=1,2,3 2,3,4,6=2,3 2,則a0不可約；v其邏輯

47、語(yǔ)義表示為：a0b0Va0c1e0v同理，決策規(guī)則3推出：a1不可約，b0可約,c1不可約，其邏輯語(yǔ)義為：a1b0Va1c1Vb0c1e1v決策規(guī)則4推出：a1,b1,c1均可約；v決策規(guī)則5推出：a2,b1,c0均可約；v決策規(guī)則6推出：a1,b1,c1均可約。v經(jīng)過(guò)上述屬性和屬性值的約簡(jiǎn)，得到了最小決策算法 ， 它 的 邏 輯 語(yǔ) 義 為 ： a0b0Va0c1- e0和a1b0Va1c1Vb0c1-e1。相應(yīng)的自然語(yǔ)言的語(yǔ)義是體溫正常且不咳嗽或者體溫正常且頭痛的不患流感；體溫偏高且不咳嗽或者體溫偏高且頭痛或者不咳嗽且頭痛的患流感。v數(shù)據(jù)表示方法越明顯，冗余數(shù)據(jù)越少，神經(jīng)網(wǎng)絡(luò)就越容易學(xué)習(xí)；神經(jīng)網(wǎng)絡(luò)的神經(jīng)元節(jié)點(diǎn)個(gè)數(shù)越多，權(quán)值的個(gè)數(shù)越多，則它的訓(xùn)練時(shí)間就越長(zhǎng)，而且神經(jīng)網(wǎng)絡(luò)的泛化能力就越差。v通過(guò)粗糙集對(duì)數(shù)據(jù)進(jìn)行約簡(jiǎn)，用約簡(jiǎn)后的數(shù)據(jù)集作為BP神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)依據(jù)及訓(xùn)練數(shù)據(jù)。這樣得到的訓(xùn)練數(shù)據(jù)表示清晰，從而使得兩種方