粗糙集理论的基本概念

1、 人的分类能力是对事物的认识能力，人的分类能力是对事物的认识能力， 是一种知识。从认知科学的观点来理解知是一种知识。从认知科学的观点来理解知 识，知识可以被理解为对事物的分类能力识，知识可以被理解为对事物的分类能力 及知识的分类能力可用知识系统的集合表及知识的分类能力可用知识系统的集合表 达形式来描述。知识在不同的范畴中有许达形式来描述。知识在不同的范畴中有许 不同的含义。粗糙集理论认为，知识直接不同的含义。粗糙集理论认为，知识直接 与真实或抽象世界的不同分类模式联系在与真实或抽象世界的不同分类模式联系在 一起。知识被看作是关于论域的划分，是一起。知识被看作是关于论域的划分，是 一种对对象进行

2、分类的能力。一种对对象进行分类的能力。 第第2章章 粗糙集理论的基本概念粗糙集理论的基本概念 2.1知识与知识库知识与知识库 定义定义1.1（知识和概念（范畴或信息粒）（知识和概念（范畴或信息粒） 设设U是给定研究对象的非空有限集合，称为是给定研究对象的非空有限集合，称为 一个论域。论域一个论域。论域U的任何一个子集的任何一个子集X U， 称为论域称为论域U的一个概念或范畴。论域的一个概念或范畴。论域U的一的一 个划分个划分X1, X2, Xn（概念簇）称为关于（概念簇）称为关于 U的抽象知识，简称知识。为了规范化，我的抽象知识，简称知识。为了规范化，我 们认为空集也是一个概念，称为空概念。们

3、认为空集也是一个概念，称为空概念。 在粗糙集理论中，主要讨论的是那些在粗糙集理论中，主要讨论的是那些 能够在论域能够在论域U上形成划分或覆盖的知识。上形成划分或覆盖的知识。 我们知道我们知道U的划分的划分X1, X2, Xn与与U上上 的等价关系的等价关系R一一对应，即给定一一对应，即给定U的一个划的一个划 分分X1, X2, Xn等同于给定等同于给定U上的一个等上的一个等 价关系价关系R，从数学的角度讲，关系的表示和，从数学的角度讲，关系的表示和 处理比分类的表示和处理简单得多，因此，处理比分类的表示和处理简单得多，因此， 我们通常用等价关系或关系来表示分类及知我们通常用等价关系或关系来表示

4、分类及知 识。因此知识也可以定义为，设识。因此知识也可以定义为，设R是是U上的上的 一个等价关系，一个等价关系，U/R =X1, X2, Xn 表示表示 R产生的分类，称为关于产生的分类，称为关于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-基本集基本集)。在不可能产。在不可能产 生混淆的情况下，即生混淆的情况下，即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的转化，或的转化，或S2为为S1的泛化。泛化意味着的泛化。泛化意味着 将某些范畴组合在一起，而特化则是将范畴分割成将某些范畴组合在一起，而特化则是将范畴分割成 更小的概念。如果上述两种情形都不满足，则称两更小的概念。如果上述两种情形都不满足，则称两 个知识库不能比较粗细。个知识库不能比较粗细。 128 2.1,., ( 2.1. Ux xx例给定一玩具积木的论域 并假设这些积木有不同的颜色 红、黄、蓝）， 形状（方形、圆形

11、、三角形），体积（小、大）， 见表因此，这些积木都可以用颜色、形状、 体积这些知识来描述，例如一块积木可以是红色、 小而圆的，或黄色、大而方的等。如果我们根据 某一属性描述这些积木的情形，就可以按颜色、 形状或体积分来。 表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 换句话说，的商集中的每一个 元素都是的商集中某一个元素 的子集或真子集。由此可得 当然， 所以根据定义可知，知识库与知识库不等价， 且知识库比知识库更细。 2.2粗糙集的基本定义及其性质粗糙集的基本定义及其性质 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 集合称为 的 边界域； 称为 的 正域； 称为 的 负域。显然， 下近似或正域是由哪些根据指示 判断肯定属于 的论域 中元素组成的集合；

20、上近似是由那些根据知识 判断肯定属于 或可能属于 的论域 中元素组成的集合； () () 2.1 R R RbnXR XXU RnegX RXU X 边界域是由那些根据知识 既不能判断 肯定属于 又不能判断肯定不属于 的论域 中 元素组成的集合； 负域是那些根据 知识 判断肯定不属于 的论域 中元素组成的 集合。集合 的上近似、下近似和边界域可用图 来表示。 2.6 , ()() ()() RU RXU R XR XXU RRR R XR XXU RRR R RRUR 定义（粗糙集和精确集）给定论域 和其上的一个等价关系 ， 若，称集合 是关于论域 的 相对于知识 的精确集或可定义集；若 ，则

21、称集合 是关于论域 的 相对于知识 的粗糙集或不可定义集。 事实上，任意有限个基本范畴的并，统称 为精确集或可定义集，当论域和 明 确时，可简称为精确集或可定义集。 ( , ) () () KU S RIND KXRX K RR URIND KX RXK 在知识库中，当存在等价关系 ，使得 是精确集，则称 是 知识库 中的精确集或可定义集。 精确集能够表达成某些 基本范畴的并， 它是论域 的子集。当， 都是 粗糙集，则称 是知识库 中的粗糙集或 不可定义集。 ()R X X X 对于粗糙集而言，它的下近似描述了 包含在 中的最大的可定义集，上近似描述 了包含 的最小的可定义集。这样，范畴就 是

22、可以用已知知识表达的信息项。换句话讲， 范畴就是用我们的知识可表达的具有相同性 质的对象的子集。一般地，在给定的知识库 中，并不是所有对象子集都可以构成范畴。 因此，这样的子集可视为粗范畴(即不精确 或近似范畴)，它只能用知识通过两个精确范畴， 即上近似和下近似集，粗糙地定义。 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 性质集合的下

23、近似和上近似算子的性质： （）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 （ ）。 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中的一个医疗诊断决策表中的一个医疗诊断决策表 论域论域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 解：首先计算论域 的所有基本集（商集） 所以 的基本集：，。 集合与基本集的关系如下： 根据定义可得： 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 这表明，集合的元素依据知识 判断 肯定属于概念 ；集合 的元素依据知识 既 不能判断肯定属于概念 ，也不能判断肯定 不属于概念集合的元素

28、依据知识 判断 肯定不属于概念 。 类似的，可以求得 ， ， 的下近似、 上近似、边界域，正域和负域。 这些概念是粗糙集理论与方法求解实际问题、 进行近似推理时可利用的知识。 UX () (),(2.4) () ()1().(2.5) R RR R X X R X XX 2.3粗糙集的特征粗糙集的特征 2.3.1粗糙集的数字特征粗糙集的数字特征 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)。实质上，。实质上， 它是论域它是论域U中所有根据分类中所有根据分类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时，上诉内容就退化为时，上诉内容就退化为2.6.1节节 的内容，也就是

36、说，相对核和相对约简的概念及其的内容，也就是说，相对核和相对约简的概念及其 性质就退化为何和约简的概念及其性质。性质就退化为何和约简的概念及其性质。 例例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 且且 所以，根据定义所以，根据定义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 所以，根据定义所以，根据定义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 所以，根据定义所以，根据定义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 所以，根据定义所以，根据定义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 所以，根据定义所以，根据定义2.212.21可知，可知，R3为为P中中Q必要的。必要的。 由此可知，知识由此可知，知识P=R1,R3 S是是S的的Q独立子族。独立子族

43、。 又因为又因为posIND(P)(Q)=posIND(S)(Q),因此因此P满足根据满足根据 定义定义2.22的条件，所以，知识的条件，所以，知识P=R1,R3 S是是S的的Q 约简。约简。 注意：本题的注意：本题的Q约简唯一。一般来讲，复杂的知约简唯一。一般来讲，复杂的知 识表达系统的约简或识表达系统的约简或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区别开来。区别开来。 ( )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, 所以根据定义所以根据定义2.24可知范畴可知范畴E1在在F中必要。中必要

52、。 从从F中删除中删除E2可知：可知： (F- -E2) = E1E3 = e1, e3=F, 所以根据定义所以根据定义2.242.24可知可知范畴范畴E2在在F中不必要。中不必要。 从从F中删除中删除E3可知：可知： (F- -E3) = E1E2 = e1, e3=F, 所以根据定义所以根据定义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是独立的。是独立的。 综上所述，根据定义综上所述，根据定义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是独立的。是独立的。 综上所述，根据定义综上所述，根据定义2.26可知，可知，H2 =E1,E3 F是知是知 识范畴识范畴F的一个约简。的一个约简。 显然，显然，F有两个约简有两个约简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，此题的求解过程留给读者。，此题的求解过程留给读者。 在决策系统中，我们经常会考虑一些范畴的并是在决策系统中，我们经常会考虑一些范畴的并是 否存在冗余？绝大多数情形下答案是否定的。出于否存在冗余？绝大多数情形下答案是否定的。出于 简化决策的需要，有必要研究并范畴的约简问题，简化决策的需要，有必要研究并范畴的约简问题， 这一问题

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区别开来。区别开来。 注意：知识范畴的核是唯一的。核是知识范畴中注意：知识范畴的核是唯一的。核是知识范畴中 最重要的部分最重要的部分, , 删除知识范畴核中任何一个范畴都删除知识范畴核中任何一个范畴都 会削弱该知识范畴对知识库中范畴的表达能力。会削弱该知识范畴对知识库中范畴的表达能力。 知识范畴并的核与约简的如下关系知识范畴并的核与约简的如下关系 (

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, 所以根据定义所以根据定义2.282.28可知可知范畴范畴E1在在F中必要。中必要。 从从F中删除中删除E2可知：可知： (F- -E2) = E1E3 E4= e1, e3=U=F,