第5章5.3.1粗糙集

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

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

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

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

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

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

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

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

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

10、 屬性約簡的粗糙集理論屬性約簡的粗糙集理論 屬性約簡概念屬性約簡概念 在信息表中根據等價關系，我們可以用等價類在信息表中根據等價關系，我們可以用等價類中的一個對象（元組）來代表整個等價類，這實中的一個對象（元組）來代表整個等價類，這實際上是按縱方向約簡了信息表中數據。際上是按縱方向約簡了信息表中數據。 對信息表中的數據按橫方向進行約簡就是看信對信息表中的數據按橫方向進行約簡就是看信息表中有無冗余的屬性，即去除這些屬性后能保息表中有無冗余的屬性，即去除這些屬性后能保持等價性，使對象分類能力不會下降。持等價性，使對象分類能力不會下降。 約簡后的屬性集稱作屬性約簡集，約簡集通常約簡后的屬性集稱作屬性

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

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

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

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

15、有風N令1 1）計算缺少一個屬性的等價關系）計算缺少一個屬性的等價關系 ,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計算減少一個條件屬性相對決策屬性的正域計算減少一個條件屬性相對決策屬性的正域由此可知，屬性由此可知，屬性a2，a3是相對于決策屬性是相對于決策屬性d可省略的，可省略的，但不一定可以同時省略，但不一定可以同時省略，屬性屬性a1和和a4是相對決策屬性不可省略的，因此：是相對決策屬性不可省略的，因此：UDPosaC11,10, 9 , 5 , 2)() (1)()() (2DPosUDPoscaC)()() (3DPosUDPoscaCUDPosaC13,12,11,10, 9 , 8 , 7 , 3 , 2 , 1)() (4,)(41aacCore2）計算

17、同時減少）計算同時減少a2,a3的等價關系和正域的等價關系和正域 說明說明a2,a3同時是不可省略的。同時是不可省略的。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中只能刪除一個屬性中只能刪除一個屬性即存在兩個約簡：即存在兩個約簡：從實例計算可以看出，信息表的屬性約簡是在從實例計算可以看出，信息表的屬性約簡是在保持條件屬性相對決策屬性的分類能力不變的保持條件屬性相對決策屬性的分類能力不變的條件下，刪除不必要的或不重要的屬

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

19、(DPosC|U 的性質的性質 若若 1 1，意味著，意味著 ，即已知條，即已知條件件C C下，可將下，可將U U上全部個體準確分類到決策屬性上全部個體準確分類到決策屬性D D的類別中去，即的類別中去，即D D完全依賴于完全依賴于C C。若若0 1,0 1,則稱則稱D D部分依賴于部分依賴于C C（D D RoughRough依賴于依賴于C C），），即在已知條件即在已知條件C C下，只能將下，只能將U U上那些屬于正上那些屬于正域的個體分類到決策屬性域的個體分類到決策屬性D D的類別中去。的類別中去。),( DC)()(DINDCIND若若 0 0，則稱，則稱D D完全不依賴完全不依賴C C

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

21、),(DCaSGF2. 2. 性質性質（1 1） 0 0，11 （2 2）若）若 = 0= 0，表示屬性，表示屬性a a關于關于D D是可省的。是可省的。因為從屬性集中去除屬性因為從屬性集中去除屬性a a后，后，C-aC-a中的信息，中的信息，原來可被準確分類所有對象仍能準確劃分到各原來可被準確分類所有對象仍能準確劃分到各決策類中去。決策類中去。),(DCaSGF),(DCaSGF),(DCaSGF（3 3） 0 0，表示屬性，表示屬性a a關于關于D D是不可省的。是不可省的。 因為為從屬性集因為為從屬性集C C中去除屬性中去除屬性a a后，某些原來可被后，某些原來可被準確分類的對象不再能被

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

23、僅當的一個最小屬性集，當且僅當并且并且 若若P是是C的最小屬性集，則的最小屬性集，則P具有與具有與C同樣的區(qū)分同樣的區(qū)分決策類的能力。決策類的能力。)(CPP),(),(DCDP),(),(,DPDPPP 需要注意的是，需要注意的是，C的最小屬性集一般是不唯一的最小屬性集一般是不唯一的，而要找到所有的最小屬性集是一個的，而要找到所有的最小屬性集是一個NP問題。問題。 在大多數應用中，沒有必要找到所有的最小屬在大多數應用中，沒有必要找到所有的最小屬性集。用戶可以根據不同的原則來選擇一個他認性集。用戶可以根據不同的原則來選擇一個他認為最好的最小屬性集。為最好的最小屬性集。5.3.1.4 粗糙集方法

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

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

26、約簡和規(guī)則獲取方法。有下表的數據：通過實例說明屬性約簡和規(guī)則獲取方法。有下表的數據： 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等價集下近似和依賴度的計算等價集下近似和依賴度的計算（1 1）條件屬性）條件屬性C C（a a，b b，c c）的等價集的等價集 由于各元組（對象）之間不存在等價關系，由于各元組

27、（對象）之間不存在等價關系， 每個元組組成一個等價集，共七個：每個元組組成一個等價集，共七個：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）的等價集的等價集 按屬性取值，共有兩個等價集：按屬性取值，共有兩個等價集： 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）決策屬性的各等價集的下近似集為）決策屬性的各等價集的下近似集為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）計算）計算 和和 ( ,)POS C D( ,)C D2各屬性重要度計算各屬性重要度計算（1 1）a a的重要度計算的重要度計算l 條件屬性C(b,c)的等價集 E1e1，e4 ，E2e

29、2，E3e3,e6，E4e5，e7l 決策屬性 D(d )的等價集 Y1 = e1, e4, e5 , Y2= e2, e3, e6, e7 l 決策屬性的各等價集的下近似集 C_Y1=E1=e1，e4 C_Y2=E2,E3=e2，e3，e6 計算計算 和和( ,)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 結論：屬性結論：屬性a a

30、是不可省略的是不可省略的 （2 2）b b的重要度計算的重要度計算l 條件屬性條件屬性C(aC(a，c)c)的等價集的等價集 去掉屬性去掉屬性b b后，元組中只出現后，元組中只出現e e2 2和和e e7 7的等價，其他元的等價，其他元組組 均不等價，等價集共均不等價，等價集共6 6個個: : 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）的等價集的等價集 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 決策屬性的各等價集的下近似集決策屬性的各等價集的下近似集 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 計算計算POS (C-b,D) 結論：屬性結論：屬性b b是可省略的是可省略的 12CYCY3簡化數據表簡化數據表 在原數據表中刪除肌肉痛在原數據表中刪除肌肉痛( (b)b)屬性后，元組屬性后，元組e e7 7和和e e2 2相同，合并成相同，合并成簡化數據表。簡化數據表。流感數據簡化表流感數據簡化表