第5章5.3.1粗糙集

1、 第第 5 章章 機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘 5.3.1節(jié)節(jié)5.3基于集合論的歸納學(xué)習(xí)方法基于集合論的歸納學(xué)習(xí)方法 5.3.1 粗糙集方法粗糙集方法5.3.1粗糙集方法粗糙集方法 n粗糙集（粗糙集（Rough Set）是波蘭數(shù)學(xué)家是波蘭數(shù)學(xué)家Z.Pawlak于于1982年提出的。年提出的。n粗糙集以等價(jià)關(guān)系（不可分辨關(guān)系）為基礎(chǔ)，用于粗糙集以等價(jià)關(guān)系（不可分辨關(guān)系）為基礎(chǔ)，用于分類(lèi)問(wèn)題。分類(lèi)問(wèn)題。n它用上、下近似兩個(gè)集合來(lái)逼近任意一個(gè)集合，它用上、下近似兩個(gè)集合來(lái)逼近任意一個(gè)集合，n該集合的邊界線(xiàn)區(qū)域被定義為上近似集和下近似集該集合的邊界線(xiàn)區(qū)域被定義為上近似集和下近似集之差集。之差集

2、。n上、下近似集可以通過(guò)等價(jià)關(guān)系給出確上、下近似集可以通過(guò)等價(jià)關(guān)系給出確定的描述，邊界域的含糊元素?cái)?shù)目可以定的描述，邊界域的含糊元素?cái)?shù)目可以被計(jì)算出來(lái)。被計(jì)算出來(lái)。n模糊集（模糊集（Fuzzy）是用隸屬度來(lái)描述集是用隸屬度來(lái)描述集合邊界的不確定性，隸屬度是人為給定合邊界的不確定性，隸屬度是人為給定的，不是計(jì)算出來(lái)的。的，不是計(jì)算出來(lái)的。n粗糙集理論用在數(shù)據(jù)庫(kù)中的粗糙集理論用在數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)知識(shí)發(fā)現(xiàn)主要主要體現(xiàn)在：體現(xiàn)在：n（1）利用等價(jià)關(guān)系對(duì)數(shù)據(jù)庫(kù)進(jìn)行屬性約簡(jiǎn)。）利用等價(jià)關(guān)系對(duì)數(shù)據(jù)庫(kù)進(jìn)行屬性約簡(jiǎn)。n（2）利用集合的上、下近似關(guān)系獲取分）利用集合的上、下近似關(guān)系獲取分 類(lèi)規(guī)則。類(lèi)規(guī)則。 (1

3、)信息表定義信息表定義信息表信息表S=(U，R，V， )的定義為的定義為:U:是一個(gè)非空有限對(duì)象是一個(gè)非空有限對(duì)象(元組元組)集合集合, U=x1 x2 xn,其中其中xi為對(duì)象為對(duì)象(元組元組)。R:是對(duì)象的屬性集合是對(duì)象的屬性集合,分為兩個(gè)不相交的子集分為兩個(gè)不相交的子集,即條即條件屬性件屬性C和決策屬性和決策屬性D, R=C DV:是屬性值的集合，是屬性值的集合， V a是屬性的值域。是屬性的值域。 ：是：是 的一個(gè)信息函數(shù)，它為每個(gè)對(duì)象的一個(gè)信息函數(shù)，它為每個(gè)對(duì)象x的的每個(gè)屬性每個(gè)屬性a賦予一個(gè)屬性值，即賦予一個(gè)屬性值，即fVRUaaVxfUxRa)(,（2）等價(jià)關(guān)系定義）等價(jià)關(guān)系定義

4、對(duì) 于對(duì) 于 （A中 包 含 一 個(gè) 或 多 個(gè) 屬中 包 含 一 個(gè) 或 多 個(gè) 屬性），性）， ，它們的屬性值相同，即：，它們的屬性值相同，即：成立，稱(chēng)對(duì)象成立，稱(chēng)對(duì)象x和和y是對(duì)屬性是對(duì)屬性A 的等價(jià)關(guān)系，表的等價(jià)關(guān)系，表示為：示為：Aa UyUxRA,)()(yfxfaa)()(,),( | ),()(yfxfAaUUyxyxAINDaa （3）等價(jià)類(lèi)定義）等價(jià)類(lèi)定義在在U中，對(duì)屬性集中，對(duì)屬性集A中具有相同等價(jià)關(guān)系的中具有相同等價(jià)關(guān)系的元素集合稱(chēng)為等價(jià)關(guān)系元素集合稱(chēng)為等價(jià)關(guān)系 的等價(jià)類(lèi)，的等價(jià)類(lèi)，表示為：表示為：)(AIND)(),( |AINDyxyxA（4）劃分的定義）劃分的定義

5、在在U中對(duì)屬性中對(duì)屬性A的所有等價(jià)類(lèi)形成的劃分表的所有等價(jià)類(lèi)形成的劃分表示為：示為：具有特性：具有特性：（i.） （ii.）當(dāng)當(dāng) 時(shí)，時(shí)，（iii.）.21i|，AiixEEAiEji jiEE iEU例例1 U =a(體溫正常），體溫正常），b（體溫正常），（體溫正常），c（體溫正常），（體溫正常），d（體溫高），（體溫高），e（體溫高），（體溫高），f（體溫很高（體溫很高 對(duì)于屬性對(duì)于屬性A（體溫）的等價(jià)關(guān)系有：體溫）的等價(jià)關(guān)系有： ),(),(),(),(),(),(),(),(),(),(),()(ffeeddccbbaadeedcbcabaAIND屬性屬性A的等價(jià)類(lèi)有：的等價(jià)類(lèi)有：U

6、中對(duì)屬性中對(duì)屬性A的劃分為：的劃分為：,1cbacbaEAAA,2ededEAA3ffEA,321fedcbaEEEA（1）集合）集合X的下近似定義的下近似定義 對(duì)任意一個(gè)子集對(duì)任意一個(gè)子集 屬性屬性A的等價(jià)類(lèi)的等價(jià)類(lèi) ，有：，有：或或表示等價(jià)類(lèi)表示等價(jià)類(lèi) 中的元素中的元素x都屬于都屬于X，即即 ，則，則x一定屬于一定屬于X。UX XEAEEXAiii|)(XxxXAA |)(AixE)(XAx iAEx(2)集合集合X的上近似定義的上近似定義 對(duì)任意一個(gè)子集對(duì)任意一個(gè)子集 ，屬性，屬性A的等價(jià)類(lèi)的等價(jià)類(lèi) 有：有：或或表示等價(jià)類(lèi)表示等價(jià)類(lèi) 中的元素中的元素x可能屬于可能屬于X，即即 ，則，則x

7、可能屬于可能屬于X，也可能不屬于也可能不屬于X。UX iAExXEAEEXAiii|)(XxxXAA |)(AixE)(XAx（3）正域，負(fù)域和邊界的定義）正域，負(fù)域和邊界的定義 全集全集U可以劃分為三個(gè)不相交的區(qū)域，即正域可以劃分為三個(gè)不相交的區(qū)域，即正域（Pos），），負(fù)域（負(fù)域（NEG）和邊界（和邊界（BND）：）：從上面可見(jiàn)：從上面可見(jiàn)：)()(XAXPosA)()(XAUXNEGA)()()(XAXAXBNDA)()()(XBNDXAXAA 圖示：圖示： 正域、負(fù)域和邊界正域、負(fù)域和邊界用圖說(shuō)明正域、負(fù)域和邊界，每一個(gè)小長(zhǎng)方形表示用圖說(shuō)明正域、負(fù)域和邊界，每一個(gè)小長(zhǎng)方形表示一個(gè)等價(jià)類(lèi)

8、。一個(gè)等價(jià)類(lèi)。NEG（X）Pos（X）=BND（X）X 正域 負(fù)域 邊界)(XA 任意一個(gè)元素任意一個(gè)元素 ，它一定屬于，它一定屬于X；任意一個(gè)元素任意一個(gè)元素 ，它一定不屬于，它一定不屬于X；集集合合X的上近似是其正域和邊界的并集，即的上近似是其正域和邊界的并集，即 對(duì)于元素對(duì)于元素 ，是無(wú)法確定其是否屬于，是無(wú)法確定其是否屬于X，因此對(duì)任意元素因此對(duì)任意元素 ，只知道，只知道x可能屬可能屬于于X。)(XPosx)(XNEGx)()()(XBNDXPosXAAA)(XBNDx)(XAx（4）粗糙集定義）粗糙集定義 若若 ，即，即 即邊界為空，即邊界為空， 稱(chēng)稱(chēng)X為為A的可定義集；的可定義集；

9、否則否則X為為A不可定義的，不可定義的，即即 稱(chēng)稱(chēng)X為為A的的Rough集（粗糙集）集（粗糙集）)()(XAXA)(XBND)()(XAXA例例 2 對(duì)上例對(duì)上例1 的等價(jià)關(guān)系的等價(jià)關(guān)系A(chǔ)有集合有集合是粗糙集，計(jì)算集合是粗糙集，計(jì)算集合X的下近似、上近似、正域、負(fù)的下近似、上近似、正域、負(fù)域和邊界。域和邊界。U中關(guān)于中關(guān)于A的劃分為：的劃分為：有：有：,fcbX , , , , , Aa b cd ef,ebcbaX 可知有：可知有： ,edX ffX )(fXA,)(fcbafcbaXA()()APosXAXf,)()(edXAUXNEGA,)()()(cbaXAXAXBNDA5.3.1.2

10、 屬性約簡(jiǎn)的粗糙集理論屬性約簡(jiǎn)的粗糙集理論 屬性約簡(jiǎn)概念屬性約簡(jiǎn)概念 在信息表中根據(jù)等價(jià)關(guān)系，我們可以用等價(jià)類(lèi)在信息表中根據(jù)等價(jià)關(guān)系，我們可以用等價(jià)類(lèi)中的一個(gè)對(duì)象（元組）來(lái)代表整個(gè)等價(jià)類(lèi)，這實(shí)中的一個(gè)對(duì)象（元組）來(lái)代表整個(gè)等價(jià)類(lèi)，這實(shí)際上是按縱方向約簡(jiǎn)了信息表中數(shù)據(jù)。際上是按縱方向約簡(jiǎn)了信息表中數(shù)據(jù)。 對(duì)信息表中的數(shù)據(jù)按橫方向進(jìn)行約簡(jiǎn)就是看信對(duì)信息表中的數(shù)據(jù)按橫方向進(jìn)行約簡(jiǎn)就是看信息表中有無(wú)冗余的屬性，即去除這些屬性后能保息表中有無(wú)冗余的屬性，即去除這些屬性后能保持等價(jià)性，使對(duì)象分類(lèi)能力不會(huì)下降。持等價(jià)性，使對(duì)象分類(lèi)能力不會(huì)下降。 約簡(jiǎn)后的屬性集稱(chēng)作屬性約簡(jiǎn)集，約簡(jiǎn)集通常約簡(jiǎn)后的屬性集稱(chēng)作屬性

11、約簡(jiǎn)集，約簡(jiǎn)集通常不唯一。不唯一。 求最小約簡(jiǎn)集（含屬性個(gè)數(shù)最少的約簡(jiǎn)集）同求最小約簡(jiǎn)集（含屬性個(gè)數(shù)最少的約簡(jiǎn)集）同樣是一個(gè)困難問(wèn)題，實(shí)際上它是一個(gè)樣是一個(gè)困難問(wèn)題，實(shí)際上它是一個(gè)NP-hard問(wèn)問(wèn)題。題。 研究者提出了很多啟發(fā)式算法，如基于遺傳算研究者提出了很多啟發(fā)式算法，如基于遺傳算法的方法等。法的方法等。（1）約簡(jiǎn)定義）約簡(jiǎn)定義給定一個(gè)信息表給定一個(gè)信息表IT（U，A），），若有屬性集若有屬性集 且滿(mǎn)足：且滿(mǎn)足：稱(chēng)稱(chēng)B為為A的一個(gè)約簡(jiǎn)。記為的一個(gè)約簡(jiǎn)。記為red（A） B=red(A)AB)()(AINDBIND（2）核定義）核定義屬性集屬性集A的所有約簡(jiǎn)的交集稱(chēng)為的所有約簡(jiǎn)的交集稱(chēng)為A

12、的核。記作的核。記作 Core(A)是是A中為保證信息表中對(duì)象可精確定義中為保證信息表中對(duì)象可精確定義的必要屬性組成的集合，為的必要屬性組成的集合，為A中不能約簡(jiǎn)的重要中不能約簡(jiǎn)的重要屬性，它是進(jìn)行屬性約簡(jiǎn)的基礎(chǔ)。屬性，它是進(jìn)行屬性約簡(jiǎn)的基礎(chǔ)。( )( )core Ared A （3）正域定義）正域定義 設(shè)決策屬性設(shè)決策屬性D的劃分的劃分 ，條件屬性，條件屬性C相對(duì)于決策屬性相對(duì)于決策屬性D的正域定義為：的正域定義為： （4）條件屬性）條件屬性C相對(duì)于決策屬性相對(duì)于決策屬性D的約簡(jiǎn)定義的約簡(jiǎn)定義 若若 ，如果，如果 ，則稱(chēng)則稱(chēng)c是是C中相對(duì)于中相對(duì)于D不必要的，即可約簡(jiǎn)的，不必要的，即可約簡(jiǎn)的

13、，否則稱(chēng)否則稱(chēng)c是是C中相對(duì)于中相對(duì)于D必要的。必要的。12 ,. nAy yy)_()(jCyCDPosCc)()()(DPosDPosCcC（5）條件屬性）條件屬性C相對(duì)于決策屬性相對(duì)于決策屬性D的核定義的核定義若若 ，如果，如果R中每一個(gè)都是相對(duì)于中每一個(gè)都是相對(duì)于D必要的，必要的，則稱(chēng)則稱(chēng)R是相對(duì)于是相對(duì)于D獨(dú)立的。如果獨(dú)立的。如果R相對(duì)于相對(duì)于D獨(dú)獨(dú)立的，且立的，且 ，則稱(chēng)，則稱(chēng)R是是C中相對(duì)于中相對(duì)于D的約簡(jiǎn)，記為的約簡(jiǎn)，記為 ，所有這樣簡(jiǎn)約的交稱(chēng)為，所有這樣簡(jiǎn)約的交稱(chēng)為C的的D核，記為：核，記為：一般情況下，信息系統(tǒng)的屬性約簡(jiǎn)集有多個(gè)，但約簡(jiǎn)一般情況下，信息系統(tǒng)的屬性約簡(jiǎn)集有多個(gè)

14、，但約簡(jiǎn)集中屬性個(gè)數(shù)最少的最有意義。集中屬性個(gè)數(shù)最少的最有意義。CR)()(DPosDPosCR)(CredD)()(CredCCoreDD屬性約簡(jiǎn)實(shí)例：屬性約簡(jiǎn)實(shí)例： 氣候信息表是氣候信息表是 4個(gè)條件屬性（天氣個(gè)條件屬性（天氣a1，溫度溫度a2，濕度濕度a3，風(fēng)風(fēng)a4） 和和 1個(gè)決策屬性（類(lèi)別個(gè)決策屬性（類(lèi)別d）。 見(jiàn)下表見(jiàn)下表。NO.屬性類(lèi)別天氣氣溫濕度風(fēng)1晴熱高無(wú)風(fēng)N2晴熱高有風(fēng)N3多云熱高無(wú)風(fēng)P4雨適中高無(wú)風(fēng)P5雨冷正常無(wú)風(fēng)P6雨冷正常有風(fēng)N7多云冷正常有風(fēng)P8晴適中高無(wú)風(fēng)N9晴冷正常無(wú)風(fēng)P10雨適中正常無(wú)風(fēng)P11晴適中正常有風(fēng)P12多云適中高有風(fēng)P13多云熱正常無(wú)風(fēng)P14雨適中高

15、有風(fēng)N令1 1）計(jì)算缺少一個(gè)屬性的等價(jià)關(guān)系）計(jì)算缺少一個(gè)屬性的等價(jià)關(guān)系 ,4321dDaaaaC14,13,12,11,10,9,8,7,6,5,4,3,2,1)(CIND13,12,11,10,9 ,7 ,5 ,4, 3,14,8 ,6 ,2, 1)(DINDUDPosC)(13,14,12,11,10,7 . 6,9 , 5,8 , 4,2,3 , 1)(1aCIND14,13,12,11,9,7,6,10, 5,4,3,2,8 , 1)(2aCIND14,13,12,11,9,8,7,6,5,10, 4,13, 3,2,1)(3aCIND13,12,11,10,9,8,7,6 , 5,1

16、4, 4,3,2 , 1)(4aCIND計(jì)算減少一個(gè)條件屬性相對(duì)決策屬性的正域計(jì)算減少一個(gè)條件屬性相對(duì)決策屬性的正域由此可知，屬性由此可知，屬性a2，a3是相對(duì)于決策屬性是相對(duì)于決策屬性d可省略的，可省略的，但不一定可以同時(shí)省略，但不一定可以同時(shí)省略，屬性屬性a1和和a4是相對(duì)決策屬性不可省略的，因此：是相對(duì)決策屬性不可省略的，因此：UDPosaC11,10, 9 , 5 , 2)() (1)()() (2DPosUDPoscaC)()() (3DPosUDPoscaCUDPosaC13,12,11,10, 9 , 8 , 7 , 3 , 2 , 1)() (4,)(41aacCore2）計(jì)算

17、同時(shí)減少）計(jì)算同時(shí)減少a2,a3的等價(jià)關(guān)系和正域的等價(jià)關(guān)系和正域 說(shuō)明說(shuō)明a2,a3同時(shí)是不可省略的。同時(shí)是不可省略的。12, 7,14, 6,10, 5 , 4,13, 3.11, 2,9 , 8 , 1),(32aaCINDUDPosaaC14,13,12,10, 7 , 6 , 5 , 4 , 3)(), (323） 在在a2，a3中只能刪除一個(gè)屬性中只能刪除一個(gè)屬性即存在兩個(gè)約簡(jiǎn)：即存在兩個(gè)約簡(jiǎn)：從實(shí)例計(jì)算可以看出，信息表的屬性約簡(jiǎn)是在從實(shí)例計(jì)算可以看出，信息表的屬性約簡(jiǎn)是在保持條件屬性相對(duì)決策屬性的分類(lèi)能力不變的保持條件屬性相對(duì)決策屬性的分類(lèi)能力不變的條件下，刪除不必要的或不重要的屬

18、性。條件下，刪除不必要的或不重要的屬性。一般來(lái)講：一般來(lái)講： 條件屬性對(duì)于決策屬性的相對(duì)約簡(jiǎn)不是唯一的，條件屬性對(duì)于決策屬性的相對(duì)約簡(jiǎn)不是唯一的，即可能存在多個(gè)相對(duì)約簡(jiǎn)。即可能存在多個(gè)相對(duì)約簡(jiǎn)。 ,)(421321aaaaaaCredD5.3.1.3 屬性約簡(jiǎn)的粗糙集方法屬性約簡(jiǎn)的粗糙集方法1屬性依賴(lài)度定義屬性依賴(lài)度定義信息表中條件屬性信息表中條件屬性C和決策屬性和決策屬性D，屬性屬性D依賴(lài)屬性依賴(lài)屬性C的的 依賴(lài)度為：依賴(lài)度為： 其中其中 表示正域表示正域 的元素個(gè)數(shù)，的元素個(gè)數(shù)， 表示整個(gè)對(duì)象集合的個(gè)數(shù)。表示整個(gè)對(duì)象集合的個(gè)數(shù)。| / | )(|),(UDPosDCC| )(|DPosC)

19、(DPosC|U 的性質(zhì)的性質(zhì) 若若 1 1，意味著，意味著 ，即已知條，即已知條件件C C下，可將下，可將U U上全部個(gè)體準(zhǔn)確分類(lèi)到?jīng)Q策屬性上全部個(gè)體準(zhǔn)確分類(lèi)到?jīng)Q策屬性D D的類(lèi)別中去，即的類(lèi)別中去，即D D完全依賴(lài)于完全依賴(lài)于C C。若若0 1,0 1,則稱(chēng)則稱(chēng)D D部分依賴(lài)于部分依賴(lài)于C C（D D RoughRough依賴(lài)于依賴(lài)于C C），），即在已知條件即在已知條件C C下，只能將下，只能將U U上那些屬于正上那些屬于正域的個(gè)體分類(lèi)到?jīng)Q策屬性域的個(gè)體分類(lèi)到?jīng)Q策屬性D D的類(lèi)別中去。的類(lèi)別中去。),( DC)()(DINDCIND若若 0 0，則稱(chēng)，則稱(chēng)D D完全不依賴(lài)完全不依賴(lài)C C

20、，即利用條件即利用條件C C不不能分類(lèi)到能分類(lèi)到D D中的類(lèi)別中去。中的類(lèi)別中去。2.2.屬性重要度定義屬性重要度定義C C,D AD A，C C為條件屬性集，為條件屬性集，D D為決策屬性集，為決策屬性集，aaC C ，屬性屬性a a關(guān)于關(guān)于D D 的重要度定義為：的重要度定義為：其中其中 表示在中缺少屬性表示在中缺少屬性a a 后，條件屬性與后，條件屬性與決策屬性的依賴(lài)程度。決策屬性的依賴(lài)程度。 表示表示 C C 中缺少屬性中缺少屬性a a 后，導(dǎo)致不能被準(zhǔn)后，導(dǎo)致不能被準(zhǔn)確分類(lèi)的對(duì)象在系統(tǒng)中所占的比例。確分類(lèi)的對(duì)象在系統(tǒng)中所占的比例。),(),(),(DaCDCDCaSGF),(DaC

21、),(DCaSGF2. 2. 性質(zhì)性質(zhì)（1 1） 0 0，11 （2 2）若）若 = 0= 0，表示屬性，表示屬性a a關(guān)于關(guān)于D D是可省的。是可省的。因?yàn)閺膶傩约腥コ龑傩砸驗(yàn)閺膶傩约腥コ龑傩詀 a后，后，C-aC-a中的信息，中的信息，原來(lái)可被準(zhǔn)確分類(lèi)所有對(duì)象仍能準(zhǔn)確劃分到各原來(lái)可被準(zhǔn)確分類(lèi)所有對(duì)象仍能準(zhǔn)確劃分到各決策類(lèi)中去。決策類(lèi)中去。),(DCaSGF),(DCaSGF),(DCaSGF（3 3） 0 0，表示屬性，表示屬性a a關(guān)于關(guān)于D D是不可省的。是不可省的。 因?yàn)闉閺膶傩约驗(yàn)闉閺膶傩约疌 C中去除屬性中去除屬性a a后，某些原來(lái)可被后，某些原來(lái)可被準(zhǔn)確分類(lèi)的對(duì)象不再能被

22、準(zhǔn)確劃分。準(zhǔn)確分類(lèi)的對(duì)象不再能被準(zhǔn)確劃分。),(DCaSGF3.最小屬性集概念最小屬性集概念 大多數(shù)情況下，數(shù)據(jù)庫(kù)中存在一些不重要屬大多數(shù)情況下，數(shù)據(jù)庫(kù)中存在一些不重要屬性，我們希望找到一個(gè)最小的相關(guān)屬性集，它性，我們希望找到一個(gè)最小的相關(guān)屬性集，它具有與全部條件屬性同樣的區(qū)分決策屬性所劃具有與全部條件屬性同樣的區(qū)分決策屬性所劃分的決策類(lèi)的能力。分的決策類(lèi)的能力。從最小屬性集中產(chǎn)生的規(guī)則會(huì)更簡(jiǎn)練和更有意義。從最小屬性集中產(chǎn)生的規(guī)則會(huì)更簡(jiǎn)練和更有意義。最小屬性集定義：最小屬性集定義： 設(shè)設(shè)C，D分別是條件屬性集和決策屬性集，屬性分別是條件屬性集和決策屬性集，屬性集集 是是C的一個(gè)最小屬性集，當(dāng)且

23、僅當(dāng)?shù)囊粋€(gè)最小屬性集，當(dāng)且僅當(dāng)并且并且 若若P是是C的最小屬性集，則的最小屬性集，則P具有與具有與C同樣的區(qū)分同樣的區(qū)分決策類(lèi)的能力。決策類(lèi)的能力。)(CPP),(),(DCDP),(),(,DPDPPP 需要注意的是，需要注意的是，C的最小屬性集一般是不唯一的最小屬性集一般是不唯一的，而要找到所有的最小屬性集是一個(gè)的，而要找到所有的最小屬性集是一個(gè)NP問(wèn)題。問(wèn)題。 在大多數(shù)應(yīng)用中，沒(méi)有必要找到所有的最小屬在大多數(shù)應(yīng)用中，沒(méi)有必要找到所有的最小屬性集。用戶(hù)可以根據(jù)不同的原則來(lái)選擇一個(gè)他認(rèn)性集。用戶(hù)可以根據(jù)不同的原則來(lái)選擇一個(gè)他認(rèn)為最好的最小屬性集。為最好的最小屬性集。5.3.1.4 粗糙集方法

24、的規(guī)則獲取粗糙集方法的規(guī)則獲取 通過(guò)分析通過(guò)分析U U中的兩個(gè)劃分中的兩個(gè)劃分 和和 之間的關(guān)系，之間的關(guān)系， 把把C視為分類(lèi)條件，視為分類(lèi)條件，D視為分類(lèi)結(jié)論，我們可視為分類(lèi)結(jié)論，我們可以得到下面的分類(lèi)規(guī)則：以得到下面的分類(lèi)規(guī)則：iCEjDY（1）當(dāng)）當(dāng)E YE Yj j 時(shí)，則有：時(shí)，則有：rij： 和和 分別是等價(jià)集分別是等價(jià)集E Ei i和等價(jià)集和等價(jià)集Y Yj j中的特征描述。中的特征描述。 ()()ijD es ED es Y()iDes E()jDes YI當(dāng)當(dāng)E YE Yj j=E=Ei i時(shí)（時(shí)（E Ei i完全被完全被Y Yj j包含）即下近似，包含）即下近似，建立的規(guī)則建

25、立的規(guī)則rij是確定的，規(guī)則的可信度是確定的，規(guī)則的可信度 cf =1.0。當(dāng)當(dāng)E YE Yj j E Ei i時(shí)（時(shí)（E Ei i部分被部分被Y Yj j包含）即上近似，包含）即上近似，建立的規(guī)則建立的規(guī)則rij是不確定的，規(guī)則的可信度為：是不確定的，規(guī)則的可信度為： CF=IijiEYEI（2）當(dāng)當(dāng)E Ei i Y Yj j= =時(shí)（時(shí)（E Ei i不被不被Y Yj j包含），包含），E Ei i和和Y Yj j不能建立規(guī)則。不能建立規(guī)則。I圖示：圖示： Ei 和和Yj 的上、下近似關(guān)系的上、下近似關(guān)系1EjY2E3E5.3.1.5 粗糙集方法的應(yīng)用實(shí)例粗糙集方法的應(yīng)用實(shí)例通過(guò)實(shí)例說(shuō)明屬性

26、約簡(jiǎn)和規(guī)則獲取方法。有下表的數(shù)據(jù)：通過(guò)實(shí)例說(shuō)明屬性約簡(jiǎn)和規(guī)則獲取方法。有下表的數(shù)據(jù)： C（條件屬性） D（決策屬性）U頭痛（a）肌肉痛（b）體溫（c）流感（d）e1是（1）是（1）正常（0）否（0）e2是（1）是（1）高（1）是（1）e3是（1）是（1）很高（2）是（1）e4否（0）是（1）正常（0）否（0）e5否（0）否（0）高（1）否（0）e6否（0）是（1）很高（2）是（1）e7是（1）否（0）高（1）是（1）1等價(jià)集下近似和依賴(lài)度的計(jì)算等價(jià)集下近似和依賴(lài)度的計(jì)算（1 1）條件屬性）條件屬性C C（a a，b b，c c）的等價(jià)集的等價(jià)集 由于各元組（對(duì)象）之間不存在等價(jià)關(guān)系，由于各元組

27、（對(duì)象）之間不存在等價(jià)關(guān)系， 每個(gè)元組組成一個(gè)等價(jià)集，共七個(gè)：每個(gè)元組組成一個(gè)等價(jià)集，共七個(gè)：E E1 1ee1 1 ，E E2 2ee2 2 ，E E3 3ee3 3 ，E E4 4ee4 4 ，E E5 5ee5 5 ，E E6 6ee6 6,E,E7 7ee7 7 。（2 2）決策屬性決策屬性D D（d d）的等價(jià)集的等價(jià)集 按屬性取值，共有兩個(gè)等價(jià)集：按屬性取值，共有兩個(gè)等價(jià)集： Y Y1 1：ee1 1，e e4 4，e e5 5 ；Y Y2 2：ee2 2，e e3 3，e e6 6，e e7 7 。 （3 3）決策屬性的各等價(jià)集的下近似集為）決策屬性的各等價(jià)集的下近似集為C_YC

28、_Y1 1=E=E1 1，E E4 4，E E5 5=e=e1 1，e e4 4，e e5 5 C_YC_Y2 2=E=E2 2，E E3 3，E E6 6，E E7 7=e=e2 2，e e3 3，e e6 6，e e7 7 此例不存在上近似集。此例不存在上近似集。 121234567( ,)_ , ( ,)7,7,( ,)1POS C DC YC Ye e e e e e ePOS C DUC D（4 4）計(jì)算）計(jì)算 和和 ( ,)POS C D( ,)C D2各屬性重要度計(jì)算各屬性重要度計(jì)算（1 1）a a的重要度計(jì)算的重要度計(jì)算l 條件屬性C(b,c)的等價(jià)集 E1e1，e4 ，E2e

29、2，E3e3,e6，E4e5，e7l 決策屬性 D(d )的等價(jià)集 Y1 = e1, e4, e5 , Y2= e2, e3, e6, e7 l 決策屬性的各等價(jià)集的下近似集 C_Y1=E1=e1，e4 C_Y2=E2,E3=e2，e3，e6 計(jì)算計(jì)算 和和( ,)POS CaD( ,)CaD1212346( ,)_ ,( ,)5( ,)5/7POS CaDCYCYe e e e ePOS CaDCaD 屬性屬性a a的重要程度的重要程度: :SGFSGF（C-a,DC-a,D）= (C,D)- (C-a,D)=2/7 0= (C,D)- (C-a,D)=2/7 0 結(jié)論：屬性結(jié)論：屬性a a

30、是不可省略的是不可省略的 （2 2）b b的重要度計(jì)算的重要度計(jì)算l 條件屬性條件屬性C(aC(a，c)c)的等價(jià)集的等價(jià)集 去掉屬性去掉屬性b b后，元組中只出現(xiàn)后，元組中只出現(xiàn)e e2 2和和e e7 7的等價(jià)，其他元的等價(jià)，其他元組組 均不等價(jià)，等價(jià)集共均不等價(jià)，等價(jià)集共6 6個(gè)個(gè): : E E1 1ee1 1 ，E E2 2ee2 2，e e7 7 ，E E3 3ee3 3 ，E E4 4ee4 4 ，E E5 5ee5 5 ，E E6 6ee6 6 。l l 決策屬性決策屬性D D（d d）的等價(jià)集的等價(jià)集 Y Y1 1 = e = e1 1, e, e4 4, e, e5 5 ,

31、Y , Y2 2= e= e2 2, e, e3 3, e, e6 6, e, e7 7 l l 決策屬性的各等價(jià)集的下近似集決策屬性的各等價(jià)集的下近似集 C_Y C_Y1 1=E=E1 1, E, E4 4,E,E5 5=(e=(e1 1,e,e4 4,e,e5 5) ) C_Y C_Y2 2=E=E2 2, E, E3 3, E, E6 6=(e=(e2 2,e,e7 7,e,e3 3,e,e6 6) )POS(C-bPOS(C-b，D)= =(eD)= =(e1 1，e e2 2，e e3 3，e e4 4，e e5 5，e e6 6，e e7 7) )|POS(C-b|POS(C-b，D)|=7D)|=7， (C-a,D)=1 (C-a,D)=1 屬性屬性b b的重要度的重要度SGF(C-b,D)= (C,D)- (C-a,D)=0SGF(C-b,D)= (C,D)- (C-a,D)=0l 計(jì)算計(jì)算POS (C-b,D) 結(jié)論：屬性結(jié)論：屬性b b是可省略的是可省略的 12CYCY3簡(jiǎn)化數(shù)據(jù)表簡(jiǎn)化數(shù)據(jù)表 在原數(shù)據(jù)表中刪除肌肉痛在原數(shù)據(jù)表中刪除肌肉痛( (b)b)屬性后，元組屬性后，元組e e7 7和和e e2 2相同，合并成相同，合并成簡(jiǎn)化數(shù)據(jù)表。簡(jiǎn)化數(shù)據(jù)表。流感數(shù)據(jù)簡(jiǎn)化表流感數(shù)據(jù)簡(jiǎn)化表