粗糙集理論的基本概念

1、 人的分類能力是對事物的認識能力，人的分類能力是對事物的認識能力， 是一種知識。從認知科學的觀點來理解知是一種知識。從認知科學的觀點來理解知 識，知識可以被理解為對事物的分類能力識，知識可以被理解為對事物的分類能力 及知識的分類能力可用知識系統(tǒng)的集合表及知識的分類能力可用知識系統(tǒng)的集合表 達形式來描述。知識在不同的范疇中有許達形式來描述。知識在不同的范疇中有許 不同的含義。粗糙集理論認為，知識直接不同的含義。粗糙集理論認為，知識直接 與真實或抽象世界的不同分類模式聯(lián)系在與真實或抽象世界的不同分類模式聯(lián)系在 一起。知識被看作是關于論域的劃分，是一起。知識被看作是關于論域的劃分，是 一種對對象進行

2、分類的能力。一種對對象進行分類的能力。 第第2章章 粗糙集理論的基本概念粗糙集理論的基本概念 2.1知識與知識庫知識與知識庫 定義定義1.1（知識和概念（范疇或信息粒）（知識和概念（范疇或信息粒） 設設U是給定研究對象的非空有限集合，稱為是給定研究對象的非空有限集合，稱為 一個論域。論域一個論域。論域U的任何一個子集的任何一個子集X U， 稱為論域稱為論域U的一個概念或范疇。論域的一個概念或范疇。論域U的一的一 個劃分個劃分X1, X2, Xn（概念簇）稱為關于（概念簇）稱為關于 U的抽象知識，簡稱知識。為了規(guī)范化，我的抽象知識，簡稱知識。為了規(guī)范化，我 們認為空集也是一個概念，稱為空概念。們

3、認為空集也是一個概念，稱為空概念。 在粗糙集理論中，主要討論的是那些在粗糙集理論中，主要討論的是那些 能夠在論域能夠在論域U上形成劃分或覆蓋的知識。上形成劃分或覆蓋的知識。 我們知道我們知道U的劃分的劃分X1, X2, Xn與與U上上 的等價關系的等價關系R一一對應，即給定一一對應，即給定U的一個劃的一個劃 分分X1, X2, Xn等同于給定等同于給定U上的一個等上的一個等 價關系價關系R，從數(shù)學的角度講，關系的表示和，從數(shù)學的角度講，關系的表示和 處理比分類的表示和處理簡單得多，因此，處理比分類的表示和處理簡單得多，因此， 我們通常用等價關系或關系來表示分類及知我們通常用等價關系或關系來表示

4、分類及知 識。因此知識也可以定義為，設識。因此知識也可以定義為，設R是是U上的上的 一個等價關系，一個等價關系，U/R =X1, X2, Xn 表示表示 R產(chǎn)生的分類，稱為關于產(chǎn)生的分類，稱為關于U的一個知識。的一個知識。 通常情形下，我們在問題求解的過程中，通常情形下，我們在問題求解的過程中， 處理的不是論域處理的不是論域U上的單一劃分（知識或分上的單一劃分（知識或分 類），而是論域類），而是論域U上的一簇劃分，這導致了上的一簇劃分，這導致了 知識庫的概念。知識庫的概念。 定義定義1.2（知識庫（知識庫) U為給定的一個論域，為給定的一個論域，S 是是U上的一簇等價關系，稱二元組上的一簇等價

5、關系，稱二元組K= （U,S）是關于論域）是關于論域U上的一個知識庫或近上的一個知識庫或近 似空間。似空間。 因此，論域上的等價關系就代表著劃因此，論域上的等價關系就代表著劃 分和知識。這樣，知識庫就表示了論域上分和知識。這樣，知識庫就表示了論域上 的由等價關系（這里指屬性特征及其有限的由等價關系（這里指屬性特征及其有限 個的交）導出的各種各樣的知識，即劃分個的交）導出的各種各樣的知識，即劃分 或分類模式，同時代表了對論域的分類能或分類模式，同時代表了對論域的分類能 力，并隱含著知識庫中概念之間存在的各力，并隱含著知識庫中概念之間存在的各 種關系。種關系。 () , (2.1) IND PPR

6、 R P xUxxx 定義定義2.3（不可分辨關系（不分明關系）（不可分辨關系（不分明關系） 給定一個論域給定一個論域U和和U上的一簇等價關系上的一簇等價關系S， 若若P S,且且P，則，則P(P中所有等價關系的中所有等價關系的 交集）仍然是論域交集）仍然是論域U上的一個等價關系，上的一個等價關系， 稱為稱為P上的不可分辨關系，記為上的不可分辨關系，記為IND(P)， 也常簡記為也常簡記為P。而且，。而且， 這樣，這樣，U/IND(P)= xIND(P) | x U 表示與表示與 等價關系等價關系IND(P)相關的知識，稱為知識庫相關的知識，稱為知識庫K=(U,S)中中 關于論域關于論域U的的

7、P-基本知識（基本知識（P-基本集基本集)。在不可能產(chǎn)。在不可能產(chǎn) 生混淆的情況下，即生混淆的情況下，即P,U和和K都明確時，為了簡便，都明確時，為了簡便， 我們可用我們可用P代替代替IND(P)。用。用U/P代替代替U/IND(P)， IND(P)的等價類也稱為知識的等價類也稱為知識P的基本概念或基本范的基本概念或基本范 疇。事實上，疇。事實上，P基本范疇擁有知識基本范疇擁有知識P的論域的基本特的論域的基本特 征，換句話說，他們是知識的基本模塊。特別地，征，換句話說，他們是知識的基本模塊。特別地， 如果如果Q S,則稱則稱Q是關于論域是關于論域U的的Q-初等知識，初等知識，Q的的 等價類為知

8、識等價類為知識S的的Q初等概念或初等范疇。初等概念或初等范疇。 我們用我們用IND(K)=IND(P)| P S表示知識庫表示知識庫 K=(U,S)中所有等價關系，他對于集合的交運算是封中所有等價關系，他對于集合的交運算是封 閉的。任意有限個閉的。任意有限個P-基本范疇的并，稱為基本范疇的并，稱為P-范疇；范疇； 知識庫知識庫K=(U,S)中所有的范疇稱為中所有的范疇稱為K-范疇。范疇。 定義定義2.4（兩個知識庫的關系）設（兩個知識庫的關系）設K1=(U,S1)和和 K2=(U,S2)為兩個知識庫，如果為兩個知識庫，如果IND(S1)=IND(S2)， 即即U/IND(S1)=U/IND(S

9、2)，則稱知識庫，則稱知識庫K1與與K2是等是等 價的，記為價的，記為K1 K2或者或者S1 S2。因此當兩個知識庫有。因此當兩個知識庫有 同樣的基本范疇集時，這兩個知識庫中的知識都能同樣的基本范疇集時，這兩個知識庫中的知識都能 使我們確切的表達關于論域的完全相同的事實。這使我們確切的表達關于論域的完全相同的事實。這 就意味著可以用不同的屬性集對論域的對象進行描就意味著可以用不同的屬性集對論域的對象進行描 述，以表達關于論域完全相同的知識。如果述，以表達關于論域完全相同的知識。如果 IND(S1) IND(S2)，我們稱知識庫，我們稱知識庫K1（知識（知識S1）比）比 知識庫知識庫K1（知識（

10、知識S2）更精細，或者說）更精細，或者說K2（知識（知識S2） 比比K1（知識（知識S1）更粗糙。當）更粗糙。當S1比比S2更精細時，我們更精細時，我們 也稱也稱S1為為S2的轉(zhuǎn)化，或的轉(zhuǎn)化，或S2為為S1的泛化。泛化意味著的泛化。泛化意味著 將某些范疇組合在一起，而特化則是將范疇分割成將某些范疇組合在一起，而特化則是將范疇分割成 更小的概念。如果上述兩種情形都不滿足，則稱兩更小的概念。如果上述兩種情形都不滿足，則稱兩 個知識庫不能比較粗細。個知識庫不能比較粗細。 128 2.1,., ( 2.1. Ux xx例給定一玩具積木的論域 并假設這些積木有不同的顏色 紅、黃、藍）， 形狀（方形、圓形

11、、三角形），體積（小、大）， 見表因此，這些積木都可以用顏色、形狀、 體積這些知識來描述，例如一塊積木可以是紅色、 小而圓的，或黃色、大而方的等。如果我們根據(jù) 某一屬性描述這些積木的情形，就可以按顏色、 形狀或體積分來。 表2.1積木的信息表 U(積木積木)R1 (顏色）顏色）R2（形狀（形狀) R3（體積）（體積） X1 X2 X3 X4 X5 X6 X7 X8 紅紅 藍藍 紅紅 藍藍 黃黃 黃黃 紅紅 黃黃 圓形圓形 方形方形 三角形三角形 三角形三角形 圓形圓形 方形方形 三角形三角形 三角形三角形 小小 大大 小小 小小 小小 小小 大大 大大 137 24568 15 263478

12、278 13456 1 23 ; , xxx xxxxx xx xxxxxx xxx xxxxx R RR 解：按顏色分類：紅， ， 藍，；黃， ，。 按形狀分類：圓形，； 方形，；三角形， ， ，。 按體積分類：大， ，； 小， ， ， ，。 換言之，三個屬性定義了三個等價關系：顏色 形狀，體積 ，通過這些等價關系，可以得到下面 用集合表示的論域的不同劃分。 113724568 215263478 327813456 123 13734783 / , / , /, , ( ,) 1 , U Rx x xx xx x x U Rx xx xx x xx U Rx xxx x x x x KUR

13、 R R x x xx x xxx ，。 ，。 ，。 這些等價類構成知識庫 中的初等概念(初等范疇)。 基本范疇是由初等范疇的交集構成的，例如： （） 7 24262 , 2 , , x x xx xx（ ） 56834788 12 132324262782 5683 3 , . , , (4) , 5 , 6 , x x xx x xxx R R R RR R x x xx x xxx xxx x xx xx xxx x x xx x （ ） 它們分別表示的基本范疇：紅色三角 形，藍色方形，黃色三角形。同樣，任何一 個人可以得到知識或的基本范疇。 （ ） （ ） 4

14、782788 123 , , xxx xxx R R R 它們分別表示知識的基本范疇： 紅色三角形，藍色大方形，黃色大三角形。 1372412347 2456824568 137568135678 7, 8, 9,. x x xx xx x x x x x xx x xx x x x x x x xx x xx x x x xx 下面考慮概念的組合： （ ） （ ） （ ） 1 23 R RR 它們分別表示知識的初等范疇：紅或藍 (非黃)，藍或黃(非紅)，紅或黃(非藍)。 同樣，通過分類我們可以獲得知識和 的初等范疇。 2415 13726 10 , , 11 ,. x xx x x x xx

15、 x 注意：有些范疇在這個知識庫中是無法得到 的，例如： （ ） （ ） 這也就是說，在這個知識庫中不存在藍色圓形 和紅色方形的范疇，它們是空范疇。 上述方法是利用集合的交合并運算來獲取知識 庫的概念，也可以直接利用不可分辨關系來直 接獲取知識概念。 1 123 13724568 215263478 327813456 1213 23 12123 / ,. / ,. /, ,. , , /, , , RRR U Rx x xx xx x x U Rx xx xx x xx U Rx xxx x x x x RRRR RR UR Rxxx x 關于顏色 ，形狀，體積 的初等范疇： 關于 顏色形狀

16、， 顏色體積， 形狀體積的基本范疇： 74568 1313245678 2315234678 , , , , . /, , , , , . /, , , ,. xxxx UR Rx xxxx xxx UR Rx xxx xxxx 123 123123456 78 , /, , , , , , , . RRR UR R Rxxxxxx xx 關于 顏色形狀體積的基本范疇： 上述概念是這個知識庫中所有可定義的概念， 它們是在求解相關問題時可利用的知識基礎。 類似地，我們可以討論更復雜的知識庫。 1123 212 12345 113245 212345 314235 2.2( ,) ( ,) , /

17、 , / , / ,. KUR R R KUR R Ux x x x x U Rx xx x x U Rxx x x x U Rx xx xx 例給定兩個知識庫 和， 其中論域，且 試分析這兩個知識庫的粗細關系。 33 12345 11 22 13245 11 3 1 2 1 /() , , , , , /() , ,. /() /() i i iR ii iR ii i i i i U INDRxxxxxx U INDRxxxx x x U INDR U INDR 解：因為 顯然，對于中任意一個元素， 都能在中找到一個元素，使得前者 包含或真包含于后者， 3 1 2 1 32 11 32 1

18、1 12 12 /() /() /()/(), /()/(), 2.4 i i i i ii ii ii ii U INDR U INDR U INDRU INDR U INDRU INDR KK KK 換句話說，的商集中的每一個 元素都是的商集中某一個元素 的子集或真子集。由此可得 當然， 所以根據(jù)定義可知，知識庫與知識庫不等價， 且知識庫比知識庫更細。 2.2粗糙集的基本定義及其性質(zhì)粗糙集的基本定義及其性質(zhì) 2.5 ( ( , ) () ()|()( ) |(/)(),(2.2) ()|()( ) |( R R KU SU SUXU URIND K X R R XXxUxX YYU RYX

19、 R XXxUxX YY 定義集合的下近似和上近似)給定知識庫 (近似空間)，其中， 為論域， 表示論域上的等價關系簇，則 和論域上的一個等價關系， 我們定義子集(概念或信息粒) 關于知識 的下近似和上近似分別為 /)(),(2.3)U RYX ()()() ()() ()() ()()(). ()() () R R R RR R bnXR XR XXR posXR XXR negXUR XXR R XposXbnX R XposX RXU R XR XU 集合稱為 的 邊界域； 稱為 的 正域； 稱為 的 負域。顯然， 下近似或正域是由哪些根據(jù)指示 判斷肯定屬于 的論域 中元素組成的集合；

20、上近似是由那些根據(jù)知識 判斷肯定屬于 或可能屬于 的論域 中元素組成的集合； () () 2.1 R R RbnXR XXU RnegX RXU X 邊界域是由那些根據(jù)知識 既不能判斷 肯定屬于 又不能判斷肯定不屬于 的論域 中 元素組成的集合； 負域是那些根據(jù) 知識 判斷肯定不屬于 的論域 中元素組成的 集合。集合 的上近似、下近似和邊界域可用圖 來表示。 2.6 , ()() ()() RU RXU R XR XXU RRR R XR XXU RRR R RRUR 定義（粗糙集和精確集）給定論域 和其上的一個等價關系 ， 若，稱集合 是關于論域 的 相對于知識 的精確集或可定義集；若 ，則

21、稱集合 是關于論域 的 相對于知識 的粗糙集或不可定義集。 事實上，任意有限個基本范疇的并，統(tǒng)稱 為精確集或可定義集，當論域和 明 確時，可簡稱為精確集或可定義集。 ( , ) () () KU S RIND KXRX K RR URIND KX RXK 在知識庫中，當存在等價關系 ，使得 是精確集，則稱 是 知識庫 中的精確集或可定義集。 精確集能夠表達成某些 基本范疇的并， 它是論域 的子集。當， 都是 粗糙集，則稱 是知識庫 中的粗糙集或 不可定義集。 ()R X X X 對于粗糙集而言，它的下近似描述了 包含在 中的最大的可定義集，上近似描述 了包含 的最小的可定義集。這樣，范疇就 是

22、可以用已知知識表達的信息項。換句話講， 范疇就是用我們的知識可表達的具有相同性 質(zhì)的對象的子集。一般地，在給定的知識庫 中，并不是所有對象子集都可以構成范疇。 因此，這樣的子集可視為粗范疇(即不精確 或近似范疇)，它只能用知識通過兩個精確范疇， 即上近似和下近似集，粗糙地定義。 2.1 1()() 2()(), ( )( ) 3()()( ) 4()()( ) 5()( ) 6()( ) 7()()( ) 8()()( ) R XXR X RRR UR UU R XYR XR Y R XYR XR Y XYR XR Y XYR XR Y R XYR XR Y R XYR XR Y 性質(zhì)集合的下

23、近似和上近似算子的性質(zhì)： （）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 9()() 10()() (11) ( ()( ()(). (12) ( ()( ()(). (13) ()(). (14) ()(). (15)( (). (16) ( (). RXR X RXR X R R XR R XR X R R XR R XR X R XRX R XRX XR R X R R XX （ ）。 （ ）。 其中，其中，X，Y為論域為論域U的子集，符號的子集，符號“” 表示集合的補運算。表示集合的補運算。 例例2.3如表如表2.2（一個決策表）所示，對于（一個決策表）所

24、示，對于 屬性子集（等價關系）屬性子集（等價關系）P=頭疼，肌肉疼頭疼，肌肉疼請判請判 斷論域的一個子集合斷論域的一個子集合X=e2, e3 , e5是否為是否為P的粗的粗 糙集。若不是，請說明理由；若是，請求出糙集。若不是，請說明理由；若是，請求出X 的的P-下近似集，上近似集，邊界域下近似集，上近似集，邊界域,正域正域,負域負域. 表表2.2 例例2.3中的一個醫(yī)療診斷決策表中的一個醫(yī)療診斷決策表 論域論域U 條件屬性條件屬性決策決策d 頭痛頭痛a1肌肉痛肌肉痛a2體溫體溫a3 e1 e2 e3 e4 e5 e6 是是 是是 是是 否否 否否 否否 是是 是是 是是 是是 否否 是是 正常

25、正常 高高 很高很高 正常正常 高高 很高很高 否否 是是 是是 否否 否否 是是 123465 123465 235 12323 46 55 - /( ) , , , , , , , ,; ,; . 2.6 UP U IND Pe e ee ee Pe e ee ee Xe e e Xe e ee e Xe e Xee 解：首先計算論域 的所有基本集（商集） 所以 的基本集：，。 集合與基本集的關系如下： 根據(jù)定義可得： 5 1235 123 5 46 235 -( ) -( ) , , -( )( )( ) , ; -( )( ) ; -( )( ) , ( )( ) , p p p XP

26、R Xe XPR Xe e e e XPbnXR XR Xe e e XPposXR Xe XPnegXUR Xe e R XR XXe eeP 的下近似集； 的上近似集； 的邊界域 的正域 的負域。 因為，所以，是 粗糙集。 129 123 12458213 3679 1135 2237 3235 41236 2.5 , /, , , , (1) , (2), (3), (4) , Ux xx RU RE E E Ex x x xEx x Ex xxR RRRR Yx x x Yx x x Yx x x Yx x x x 例給定一個論域和 論域上一個等價關系 ，且 其中， 。求下列集合的下近

27、似, 上近似,邊界域,正域和負域,其中 1 12 11 12 1111 112 113 :(1)( ) |()( ( ) |()( ( )( )-( ), ( )( ), ( )( ) R R R R R RR Y xxUxYE RR YxxUxY EE Rbn YR YR YE Rpos YR YE RnegYUR YE 解下近似 ）， 上近似） ， 邊界域 正域 負域。 2 11 1 13 1 234 ; ER YER Y YER Y YYYR RRRR 這表明，集合的元素依據(jù)知識 判斷 肯定屬于概念 ；集合 的元素依據(jù)知識 既 不能判斷肯定屬于概念 ，也不能判斷肯定 不屬于概念集合的元素

28、依據(jù)知識 判斷 肯定不屬于概念 。 類似的，可以求得 ， ， 的下近似、 上近似、邊界域，正域和負域。 這些概念是粗糙集理論與方法求解實際問題、 進行近似推理時可利用的知識。 UX () (),(2.4) () ()1().(2.5) R RR R X X R X XX 2.3粗糙集的特征粗糙集的特征 2.3.1粗糙集的數(shù)字特征粗糙集的數(shù)字特征 1. 集合的近似精度和粗糙度集合的近似精度和粗糙度 定義定義2.7（近似精度和粗糙度）給定一個論 域U和U上的一個等價關系R， 稱等價關系稱等價關系R定義的集合定義的集合X的近似精度的近似精度 和粗糙度分別為和粗糙度分別為 0()1()1 RR XUX

29、X，有。當時， () R X ()()1 RR X 集合（范疇或概念）的不精確性是由于邊界域的集合（范疇或概念）的不精確性是由于邊界域的 存在而引起的，集合的邊界域越大，其精確性則存在而引起的，集合的邊界域越大，其精確性則 越低。越低。 反應了在知識反應了在知識R下對于集合下對于集合X表達的范疇了解的表達的范疇了解的 程度。程度。 顯然，對每一個顯然，對每一個R和和 X的的R-邊界域為空集，所以集合邊界域為空集，所以集合X是是R-可定義的可定義的(R- 精確集精確集)；當；當 sig ( )sig ( ) （見例（見例2.10），但），但1, 3的分類能力大于的分類能力大于 2, 3。 2.6

30、.2知識的相對核和相對的約簡知識的相對核和相對的約簡 在許多實際應用中，一個分類相對于另一個分在許多實際應用中，一個分類相對于另一個分 類的關系非常重要，例如例類的關系非常重要，例如例2.3中的依屬性中的依屬性(知識知識 或等價關系或等價關系)體溫的分類對依決策屬性流感的分類體溫的分類對依決策屬性流感的分類 提供了最多的有用信息。下面我們將介紹知識的提供了最多的有用信息。下面我們將介紹知識的 相對約簡相對約簡(relative reduct)和相對核和相對核(relative core) 的概念。的概念。 類似地，我們先介紹知識的相對必要性和獨立類似地，我們先介紹知識的相對必要性和獨立 性。為

31、此需要回顧性。為此需要回顧“一個分類相對于另一個分類一個分類相對于另一個分類 的正域的概念的正域的概念”。知識。知識Q相對于知識相對于知識P的正域為：的正域為： / ( )(), P X U Q posQP X 或稱其為知識或稱其為知識Q的的P-正域，記為正域，記為posp(Q)。實質(zhì)上，。實質(zhì)上， 它是論域它是論域U中所有根據(jù)分類中所有根據(jù)分類U/P的信息可以準確的的信息可以準確的 劃分到關系劃分到關系Q的等價類中去的對象集合。的等價類中去的對象集合。 定義定義2.21 給定一個知識庫給定一個知識庫K = (U, S)和知識庫中和知識庫中 的兩個等價關系族的兩個等價關系族P，Q S， R P

32、，若，若 posIND(P)(IND(Q)= posIND(P-R)(IND(Q) (2.25) 成立，則稱知識成立，則稱知識R為為P中中Q不必要的，否則稱不必要的，否則稱R為為 P中中Q必要的。必要的。 為了簡便起見，常用為了簡便起見，常用posIND(P)(Q)代替代替 posIND(P)(IND(Q)。 如果對每一個如果對每一個R P，R都為都為P中中Q必要的，則稱必要的，則稱P 為為Q獨立的，或稱獨立的，或稱P相對于相對于Q獨立，否則稱獨立，否則稱P是是Q依依 賴的或賴的或Q不獨立的。不獨立的。 定理定理 2.12 如果知識如果知識P， G P，則稱，則稱G是是Q獨立的。獨立的。 證明

33、證明:利用反證法：假設利用反證法：假設 G P,G不是不是Q獨立的獨立的,則則 必存在必存在S G，使得，使得S是是Q獨立的獨立的, R (G-S)，有，有 posIND(P)(IND(Q)= posIND(P-R)(IND(Q)成立。因此，成立。因此， P不是不是Q獨立的，與已知矛盾，所以假設不成立。獨立的，與已知矛盾，所以假設不成立。 故故G是是Q獨立的。獨立的。 定義定義2.22（知識的相對約簡）（知識的相對約簡） 給定一個知識庫給定一個知識庫K = (U, S)和知識庫上的兩個等價關系族和知識庫上的兩個等價關系族P，Q S，對，對 任意的任意的G P，若，若G滿足以下兩條：滿足以下兩條

34、： (1) G是是Q獨立的，即獨立的，即G是是P的的Q獨立子族，獨立子族， (2) posG(Q)= posP(Q)。 則稱則稱G是是P的一個的一個Q約簡，或稱為約簡，或稱為G是是P相對于相對于Q的的 一個約簡，記為一個約簡，記為G REDQ(P)，其中，其中，REDQ(P)表示表示 P的全體的全體Q約簡組成的集合。約簡組成的集合。 定義定義2.23（知識的相對核）（知識的相對核） 給定一個知識庫給定一個知識庫 K=(U,S)和知識庫的兩個等價關系族和知識庫的兩個等價關系族P，Q S，對任，對任 意的意的RP，若，若R滿足滿足 posIND(P-R)(IND(Q)posIND(P)(IND(Q

35、) (2.26) 則稱則稱R為為P中中Q必要的，必要的，P中所有中所有Q必要的知識組成必要的知識組成 集合稱為集合稱為P的的Q核，或稱為核，或稱為P的相對于的相對于Q的核，也可的核，也可 稱為稱為P的相對的相對Q核，記為核，記為COREQ（P）。）。 注意：知識的相對核是唯一的。注意：知識的相對核是唯一的。 相對核與相對約簡的關系如下。相對核與相對約簡的關系如下。 定理定理2.13 COREQ(P)=REDQ（P）。）。 該定理的證明類似于定理該定理的證明類似于定理2.11，故從略。，故從略。 易知，當知識易知，當知識P=Q時，上訴內(nèi)容就退化為時，上訴內(nèi)容就退化為2.6.1節(jié)節(jié) 的內(nèi)容，也就是

36、說，相對核和相對約簡的概念及其的內(nèi)容，也就是說，相對核和相對約簡的概念及其 性質(zhì)就退化為何和約簡的概念及其性質(zhì)。性質(zhì)就退化為何和約簡的概念及其性質(zhì)。 例例2.22 給定一個知識庫給定一個知識庫K = (U, S)和知識庫中獨和知識庫中獨 立于立于S的知識的知識Q，其中，論域，其中，論域U = x0, x1, x2, x8， 且且S =R1, R2, R3，等價關系，等價關系R1, R2, R3和和IND(S)對應對應 的等價類分別為的等價類分別為 U/R1 =x1, x3, x4, x5, x6, x7,x2, x8； U/R2 =x1, x3, x4, x5,x2, x6, x7, x8；

37、U/R3=x1, x6, x5,x3, x4,x2, x7, x8； U/IND(S)=x1, x5,x2, x8,x3, x4,x6,x7； U/Q=x1, x5, x6,x2, x7,x3, x4,x8； 試討論試討論R1, R2, R3關于知識關于知識IND(S)是否是否Q必要，必要， 并求并求IND(S)的的Q核和所有核和所有Q約簡。約簡。 () / 153467 153467 ( ) ( )() , , ,. IND IR X U Q posIND Q IND SX x xx xxx x x x x x x 23 1 , 15346278 /() , , R RRR U IND SR

38、 x x xx xxx xx 解：首先求出知識解：首先求出知識IND(S)關于知識關于知識Q的正域：的正域： (1)討論是否討論是否Q獨立獨立 從從S中去掉知識中去掉知識R1可得，可得， 1 () 1 / 15346 15346 ( ) ( ) ()() , , ( ). IND SR X U Q IND S posIND Q IND SRX x xx xx x x x x x posIND Q 13 2 , 15634287 /() , , R RR R U IND SR x x x xx xx xx 且且 所以，根據(jù)定義所以，根據(jù)定義2.21可知，可知，R1為為IR中中Q必要的。必要的。

39、從從S中去掉知識中去掉知識R2可得劃分為可得劃分為 2 () 2 / 156347 153467 ( ) ( ) ()() , , ( ). IND SR X U Q IND S posIND Q IND SRX x x xx xx x x x xx x posIND Q 所以，根據(jù)定義所以，根據(jù)定義2.21可知，可知，R2為為S中中Q不必要的。不必要的。 且可導出關于知識且可導出關于知識Q正域為正域為 12 3 , 13452867 /() , R RR R U IND SR x x x x xx xx x 從從S中去掉知識中去掉知識R3可得劃分為可得劃分為 3 () 3 / ( ) ( )

40、 ()() ( ) IND SR X U Q IND S posIND Q IND SRX posIND Q 所以，根據(jù)定義所以，根據(jù)定義2.212.21可知，可知，R3為為S中中Q必要的。必要的。 且可導出關于知識且可導出關于知識Q正域為正域為 13 2 , 15634287 /() , R RR R U IND SRx x x xx xx xx () / 156347 153467 ( ) ( )() , ,. IND P X U Q posIND Q IND PX x x xx xx x x x x x x 下面求下面求S的的Q核和核和Q約簡。約簡。 (2)顯然，顯然，S的的Q核為核為C

41、ORECOREQ( (S)=)=R1,R3。 (3)因為因為 所以，知識所以，知識P =R1,R3 S的的Q正域為正域為 從從P中去掉知識中去掉知識R1可得，可得， U/IND(P- -R1)= U/ R3 = x1, x5, x6,x3, x4,x2, x7, x8， 且可導出關于知識且可導出關于知識Q正域為正域為 1 () 1 / 3 / 15634 15346 () ( ) ()() () , , ( ). IND PR X U Q X U Q IND P posIND Q IND SRX R X x x xx x x x x x x posIND Q 所以，根據(jù)定義所以，根據(jù)定義2.2

42、12.21可知，可知，R1為為P中中Q必要的。必要的。 從從P中去掉知識中去掉知識R3可得，可得， U/IND(P- -R3)= U/ R1 = x1, x3, x4, x5, x6, x7,x2, x8， 且可導出關于知識且可導出關于知識Q正域為正域為 3 () 3 / 1 / () ( ) ()() () ( ). IND PR X U Q X U Q IND P posIND Q IND IRRX R X posIND Q 所以，根據(jù)定義所以，根據(jù)定義2.212.21可知，可知，R3為為P中中Q必要的。必要的。 由此可知，知識由此可知，知識P=R1,R3 S是是S的的Q獨立子族。獨立子族

43、。 又因為又因為posIND(P)(Q)=posIND(S)(Q),因此因此P滿足根據(jù)滿足根據(jù) 定義定義2.22的條件，所以，知識的條件，所以，知識P=R1,R3 S是是S的的Q 約簡。約簡。 注意：本題的注意：本題的Q約簡唯一。一般來講，復雜的知約簡唯一。一般來講，復雜的知 識表達系統(tǒng)的約簡或識表達系統(tǒng)的約簡或Q約簡常常不是唯一的。約簡常常不是唯一的。 綜上所述，我們可知如果有綜上所述，我們可知如果有P中的知識對于將論中的知識對于將論 域域U中的對象正確地劃分到知識中的對象正確地劃分到知識Q的基本范疇的基本范疇 （IND(Q)等價類）都是必不可少的，那么知識等價類）都是必不可少的，那么知識P

44、就就 是是Q獨立的。知識獨立的。知識P的的Q核是知識核是知識P最基本的特征部分，最基本的特征部分， 如果刪除如果刪除P的的Q核中的任何一個元素都將會削弱將論核中的任何一個元素都將會削弱將論 域中的對象正確地劃分到知識域中的對象正確地劃分到知識Q的等價類的能力。的等價類的能力。 對知識對知識P而言，而言，P的的Q約簡是保持將約簡是保持將U中的對象正中的對象正 確地劃分到知識確地劃分到知識Q的基本范疇（的基本范疇（IND(Q)等價類）等價類） 分類能力不變的分類能力不變的P的的Q獨立子集，它不具有唯一獨立子集，它不具有唯一 性。在一定的意義下，只有一個性。在一定的意義下，只有一個Q約簡的知識約簡的

45、知識P， 我們認為它是確定的，因為當我們依照知識我們認為它是確定的，因為當我們依照知識P的的 基本范疇將論域中的對象劃分到知識基本范疇將論域中的對象劃分到知識Q的基本范的基本范 疇中時只有一種疇中時只有一種P的知識基（的知識基（P商集）可用。另商集）可用。另 一方面，當知識一方面，當知識P有多個有多個Q約簡時，我們認為它約簡時，我們認為它 是不確定的，因為當我們依照知識是不確定的，因為當我們依照知識P的基本范疇的基本范疇 將論域中的對象劃分到知識將論域中的對象劃分到知識Q的基本范疇中時有的基本范疇中時有 多種多種P的知識基（的知識基（P商集）可利用。當知識商集）可利用。當知識P的的Q 核為空集

46、時，知識核為空集時，知識P的不確定性達到最強。的不確定性達到最強。 2.6.3知識范疇的核和約簡知識范疇的核和約簡 知識的基本范疇是知識的基（知識基），也知識的基本范疇是知識的基（知識基），也 就是構建知識范疇的基本模塊。知識庫中的每一就是構建知識范疇的基本模塊。知識庫中的每一 個概念都可以通過知識的基本范疇精確或近似地個概念都可以通過知識的基本范疇精確或近似地 表達，反之，每一個基本范疇都是某些知識范疇表達，反之，每一個基本范疇都是某些知識范疇 的交集，這自然導致一個問題的交集，這自然導致一個問題“對于知識的基本對于知識的基本 范疇是否所有的范疇都是必要的？范疇是否所有的范疇都是必要的？”該

47、問題類似該問題類似 于知識庫中的知識，即一般情形下，知識的范疇于知識庫中的知識，即一般情形下，知識的范疇 存在著冗余。下面介紹知識范疇的核和約簡。存在著冗余。下面介紹知識范疇的核和約簡。 定義定義2.24（知識范疇的必要性）給定一（知識范疇的必要性）給定一 個知識庫個知識庫K = (U,S)和論域和論域U上的一個子集簇上的一個子集簇 Spos(U) = F = X1,X2, Xn, Xi F(i=1,2, ,n), 如果如果 (F-Xi)=F (2.27) 成立，則稱范疇（子集）成立，則稱范疇（子集）Xi 在在F中為不中為不 必要的，否則為必要的。必要的，否則為必要的。 定義定義2.25（知識

48、范疇的獨立性）給定一（知識范疇的獨立性）給定一 個知識庫個知識庫K = (U,S)和論域和論域U上的一個子集簇上的一個子集簇 Spos(U) = F = X1,X2, Xn, Xi F(i=1,2, ,n), 如果如果 (F-Xi)F (2.28) 成立，則稱成立，則稱F是獨立，否則為不獨立或是獨立，否則為不獨立或 依賴的。依賴的。 ( ),( )GRED FRED F記為其中， ( )RED F 定義定義2.262.26（知識范疇的約簡）給定一個知識（知識范疇的約簡）給定一個知識 庫庫K = (U,S)和和論域論域U上的一個子集上的一個子集簇簇Spos(U) = F = X1,X2, Xn,

49、 ,對任意的對任意的G P，若，若G滿足以滿足以 下兩個條件：下兩個條件： (1) (1) G是獨立的，是獨立的， (2) (2) G = =F, , 則稱則稱G是是F的一個約簡，的一個約簡， 表示表示F的全體約簡組成的集合的全體約簡組成的集合, , 表示知識表示知識 范疇的約簡，以便與知識的約簡范疇的約簡，以便與知識的約簡RED區(qū)別開來。區(qū)別開來。 ( )CORE F 。 ( )( )CORE FRED F 。 定義定義2.272.27（知識范疇的核）稱（知識范疇的核）稱F中所有必要的中所有必要的 知識范疇組成的集合稱為知識范疇組成的集合稱為F的核的核, ,記為記為 注意：知識范疇的核是唯一

50、的。核是知識范注意：知識范疇的核是唯一的。核是知識范 疇中最重要的部分疇中最重要的部分, , 刪除知識范疇核中任何一刪除知識范疇核中任何一 個范疇都會削弱該知識范疇對知識庫中范疇的個范疇都會削弱該知識范疇對知識庫中范疇的 表達能力。表達能力。 知識范疇的核與約簡的關系如下。知識范疇的核與約簡的關系如下。 定理定理2.14 2.14 例例2.23 給定一個知識庫給定一個知識庫K = (U,S)和論域和論域U上的一上的一 個子集簇（知識庫中的一簇范疇）個子集簇（知識庫中的一簇范疇）Sub(U) = F =E1,E2,E3，其中，其中， 論域論域U = e1, e2, e3, e4, e5, e6,

51、 e7, e8； E1 = e1, e3, e8；E2 = e1, e3, e4, e5, e6 ；E3 = e1, e3, e4, e6, e7。 試討論知識范疇試討論知識范疇Ei (i =1,2,3) 對對F是否必要是否必要,并求并求 出出F的約簡和核。的約簡和核。 解：首先求出解：首先求出F的交：的交：F = E1E2E3 =e1, e3。 (1) 知識范疇知識范疇Ei (i =1,2,3) 對對F是否必要是否必要 從從F中刪除中刪除E1可知：可知： (F-E1) = E2E3 = e1, e3, e4, e6F, 所以根據(jù)定義所以根據(jù)定義2.24可知范疇可知范疇E1在在F中必要。中必要

52、。 從從F中刪除中刪除E2可知：可知： (F- -E2) = E1E3 = e1, e3=F, 所以根據(jù)定義所以根據(jù)定義2.242.24可知可知范疇范疇E2在在F中不必要。中不必要。 從從F中刪除中刪除E3可知：可知： (F- -E3) = E1E2 = e1, e3=F, 所以根據(jù)定義所以根據(jù)定義2.242.24可知可知范疇范疇E3在在F中不必要。中不必要。 (2)(2) F的核顯然為的核顯然為 1 ( )CORE FE。 (3)(3) F的的約簡約簡 由于每一個約簡都包含核，因此下面我們考由于每一個約簡都包含核，因此下面我們考 慮慮H1 =E1,E2，H2 =E1,E3 F是否為是否為F的

53、的約簡約簡 。 對于對于H1 =E1,E2 F而言：而言： () H1 =E1E2 =F； ()(H1-E1) = E2 H1，所以，所以E1在在H1中必要；中必要； (H1-E2) = E1 H1，所以，所以E2在在H1中必要。由此中必要。由此 可知可知H1是獨立的。是獨立的。 綜上所述，根據(jù)定義綜上所述，根據(jù)定義2.26可知，可知，H1 =E1,E2 F是知是知 識范疇識范疇F的一個約簡。的一個約簡。 對于對于H2 =E1,E3 F而言：而言： () H2 =E1E3 =F； ()(H2-E1) = E3 H1，所以，所以E1在在H2中必要；中必要； (H2-E2) = E1 H2，所以，

54、所以E2在在H2中必要。由此中必要。由此 可知可知H2是獨立的。是獨立的。 綜上所述，根據(jù)定義綜上所述，根據(jù)定義2.26可知，可知，H2 =E1,E3 F是知是知 識范疇識范疇F的一個約簡。的一個約簡。 顯然，顯然，F(xiàn)有兩個約簡有兩個約簡H1 =E1,E2和和H2 =E1,E3。 例例2.24 給定一個知識庫給定一個知識庫K = (U,S)和論域和論域U上的一個上的一個 子集簇（知識庫中的一簇范疇）子集簇（知識庫中的一簇范疇）Sub(2U) = F =E1, E2, E3, E4，其中，其中， 論域論域U = e1, e2, e3, e4, e5, e6, e7, e8； E1 = e1, e

55、2, e5, e6；E2 = e2, e3, e5；E3 = e1, e3, e5, e6；E4 = e1, e5, e6。 試討論知識范疇試討論知識范疇Ei (i =1,2,3) 對對F是否必要是否必要,并求出并求出 F的約簡和核。的約簡和核。 類似于例類似于例2.23，此題的求解過程留給讀者。，此題的求解過程留給讀者。 在決策系統(tǒng)中，我們經(jīng)常會考慮一些范疇的并是在決策系統(tǒng)中，我們經(jīng)常會考慮一些范疇的并是 否存在冗余？絕大多數(shù)情形下答案是否定的。出于否存在冗余？絕大多數(shù)情形下答案是否定的。出于 簡化決策的需要，有必要研究并范疇的約簡問題，簡化決策的需要，有必要研究并范疇的約簡問題， 這一問題

56、類似于交范疇的約簡問題。這一問題類似于交范疇的約簡問題。 定義定義2.28（知識范疇并的必要性）給定一個（知識范疇并的必要性）給定一個 知識庫知識庫K = (U,S)和論域和論域U上的一個子集簇上的一個子集簇Spos(2U) = F = X1,X2, Xn, Xi F(i=1,2, ,n),如果如果 (F-Xi)=F (2.29) 成立，則稱范疇（子集）成立，則稱范疇（子集）Xi 在在F中為不必中為不必 要的，否則為必要的。要的，否則為必要的。 定義定義2.29（一簇知識范疇（一簇知識范疇F相對于它的并的獨相對于它的并的獨 立性）給定一個知識庫立性）給定一個知識庫K = (U,S)和論域和論域

57、U上的一個上的一個 子集簇子集簇S(2U) = F = X1,X2, Xn, Xi F(i=1,2, ,n), 如果如果 (F-Xi)F (2.30) 成立，則稱成立，則稱F在在F中是獨立，否則為不獨立中是獨立，否則為不獨立 或依賴的?；蛞蕾嚨?。 (),()GREDFREDF記為其中， ( )RED F 定義定義2.302.30（知識范疇（知識范疇并并的約簡）給定一個知識庫的約簡）給定一個知識庫 K = (U,S)和和論域論域U上的一個子集上的一個子集簇簇S(2U) = F = X1,X2, Xn, ,對任意的對任意的G F，若，若G滿足以下兩個滿足以下兩個 條件：條件： (1) (1) G在

58、在G中中是獨立的，是獨立的， (2) (2) G = =F, , 則稱則稱G是是F的一個約簡，的一個約簡， 表示表示F的全體的全體 約簡組成的集合約簡組成的集合, , 表示知識范疇的約簡，以便與知識的約表示知識范疇的約簡，以便與知識的約 簡簡RED區(qū)別開來。區(qū)別開來。 注意：知識范疇的核是唯一的。核是知識范疇中注意：知識范疇的核是唯一的。核是知識范疇中 最重要的部分最重要的部分, , 刪除知識范疇核中任何一個范疇都刪除知識范疇核中任何一個范疇都 會削弱該知識范疇對知識庫中范疇的表達能力。會削弱該知識范疇對知識庫中范疇的表達能力。 知識范疇并的核與約簡的如下關系知識范疇并的核與約簡的如下關系 (

59、)()COREFREDF 例例2.25 2.25 給定一個知識庫給定一個知識庫K = (U,S)和論域和論域U上的一上的一 個子集簇（知識庫中的一簇范疇）個子集簇（知識庫中的一簇范疇）Sub(2U) = F =E1, E2, E3, E4，其中，其中， 論域論域U = e1, e2, e3, e4, e5, e6, e7, e8； E1 = e1, e3, e8；E2 = e1, e2, e4, e5, e6；E3 = e1, e3, e4, e6, e7；E4 = e1, e2, e5, e7。 試討論知識范疇試討論知識范疇Ei (i =1,2,3) 對對F是否必要是否必要, ,并求并求 出

60、出F的約簡和核。的約簡和核。 不一定恒成立。不一定恒成立。 解：首先求出解：首先求出F的的并并：F = E1E2E3E4=e1, e2, e3, e4, e5, e6, e7, e8= U。 (1) (1) 判斷知識范疇判斷知識范疇Ei (i =1,2,3) 對對F是否必要是否必要 從從F中刪除中刪除E1可知：可知： (F- -E1) = E2E3E4 = e1, e2, e3, e4, e5, e6, e7F, 所以根據(jù)定義所以根據(jù)定義2.282.28可知可知范疇范疇E1在在F中必要。中必要。 從從F中刪除中刪除E2可知：可知： (F- -E2) = E1E3 E4= e1, e3=U=F,