粗糙集理论的基本概念.ppt

《粗糙集理论的基本概念.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论的基本概念.ppt（225页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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上的一簇等价关系，称二元组上的一簇等价关系，称二元组K=（U,S）是关于论域）是关于论域U上的一个知识库上的一个知识库或近似空

5、间。或近似空间。因此，论域上的等价关系就代表着划因此，论域上的等价关系就代表着划分和知识。这样，知识库就表示了论域上分和知识。这样，知识库就表示了论域上的由等价关系（这里指属性特征及其有限的由等价关系（这里指属性特征及其有限个的交）导出的各种各样的知识，即划分个的交）导出的各种各样的知识，即划分或分类模式，同时代表了对论域的分类能或分类模式，同时代表了对论域的分类能力，并隐含着知识库中概念之间存在的各力，并隐含着知识库中概念之间存在的各种关系。种关系。定定义义2.3（不可分辨关系（不分明关系）（不可分辨关系（不分明关系）给给定一个定一个论论域域U和和U上的一簇等价关系上的一簇等价关系S，若若P

6、S,且且P，则则P(P中所有等价关系的中所有等价关系的交集）仍然是交集）仍然是论论域域U上的一个等价关系，上的一个等价关系，称称为为P上的不可分辨关系，上的不可分辨关系，记为记为IND(P)，也常也常简记为简记为P。而且，。而且，这样，这样，U/IND(P)=xIND(P)|x U 表示与表示与等价关系等价关系IND(P)相关的知识，称为知识库相关的知识，称为知识库K=(U,S)中中关于论域关于论域U的的P-基本知识（基本知识（P-基本集基本集)。在不可能产。在不可能产生混淆的情况下，即生混淆的情况下，即P,U和和K都明确时，为了简便，都明确时，为了简便，我们可用我们可用P代替代替IND(P)

7、。用。用U/P代替代替U/IND(P)，IND(P)的等价类也称为知识的等价类也称为知识P的基本概念或基本范畴。的基本概念或基本范畴。事实上，事实上，P基本范畴拥有知识基本范畴拥有知识P的论域的基本特征，的论域的基本特征，换句话说，他们是知识的基本模块。特别地，如果换句话说，他们是知识的基本模块。特别地，如果Q S,则称则称Q是关于论域是关于论域U的的Q-初等知识，初等知识，Q的等价的等价类为知识类为知识S的的Q初等概念或初等范畴。初等概念或初等范畴。我们用我们用IND(K)=IND(P)|P S表示知识库表示知识库K=(U,S)中所有等价关系，他对于集合的交运算是封中所有等价关系，他对于集合

8、的交运算是封闭的。任意有限个闭的。任意有限个P-基本范畴的并，称为基本范畴的并，称为P-范畴；范畴；知识库知识库K=(U,S)中所有的范畴称为中所有的范畴称为K-范畴。范畴。定义定义2.4（两个知识库的关系）设（两个知识库的关系）设K1=(U,S1)和和K2=(U,S2)为两个知识库，如果为两个知识库，如果IND(S1)=IND(S2)，即即U/IND(S1)=U/IND(S2)，则称知识库，则称知识库K1与与K2是等是等价的，记为价的，记为K1K2或者或者S1S2。因此当两个知识库。因此当两个知识库有同样的基本范畴集时，这两个知识库中的知识都有同样的基本范畴集时，这两个知识库中的知识都能使我

9、们确切的表达关于论域的完全相同的事实。能使我们确切的表达关于论域的完全相同的事实。这就意味着可以用不同的属性集对论域的对象进行这就意味着可以用不同的属性集对论域的对象进行描述，以表达关于论域完全相同的知识。如果描述，以表达关于论域完全相同的知识。如果IND(S1)IND(S2)，我们称知识库，我们称知识库K1（知识（知识S1）比知识）比知识库库K1（知识（知识S2）更精细，或者说）更精细，或者说K2（知识（知识S2）比）比K1（知识（知识S1）更粗糙。当）更粗糙。当S1比比S2更精细时，我们也称更精细时，我们也称S1为为S2的转化，或的转化，或S2为为S1的泛化。泛化意味着将某的泛化。泛化意味

10、着将某些范畴组合在一起，而特化则是将范畴分割成更小些范畴组合在一起，而特化则是将范畴分割成更小的概念。如果上述两种情形都不满足，则称两个知的概念。如果上述两种情形都不满足，则称两个知识库不能比较粗细。识库不能比较粗细。表2.1积木的信息表 U(积积木木)R1(颜颜色）色）R2（形状（形状)R3（体（体积积）X1X2X3X4X5X6X7X8红红蓝蓝红红蓝蓝黄黄黄黄红红黄黄圆圆形形方形方形三角形三角形三角形三角形圆圆形形方形方形三角形三角形三角形三角形小小大大小小小小小小小小大大大大2.2粗糙集的基本定义及其性质粗糙集的基本定义及其性质其中，其中，X，Y为论域为论域U的子集，符号的子集，符号“”表

11、示集合的补运算。表示集合的补运算。例例2.3如表如表2.2（一个决策表）所示，（一个决策表）所示，对对于于属性子集（等价关系）属性子集（等价关系）P=头头疼，肌肉疼疼，肌肉疼请请判判断断论论域的一个子集合域的一个子集合X=e2,e3,e5是否是否为为P的粗的粗糙集。若不是，糙集。若不是，请说请说明理由；若是，明理由；若是，请请求出求出X的的P-下近似集，上近似集，下近似集，上近似集，边边界域界域,正域正域,负负域域.表表2.2 例例2.3中的一个医中的一个医疗诊疗诊断决策表断决策表论论域域U条件属性条件属性决策决策d头头痛痛a1肌肉痛肌肉痛a2体温体温a3e1e2e3e4e5e6是是是是是是否

12、否否否否否是是是是是是是是否否是是正常正常高高很高很高正常正常高高很高很高否否是是是是否否否否是是2.3粗糙集的特征粗糙集的特征粗糙集的数字特征粗糙集的数字特征1.集合的近似精度和粗糙度集合的近似精度和粗糙度定定义义2.7（近似精度和粗糙度）给定一个论域U和U上的一个等价关系R，称等价关系称等价关系R定定义义的集合的集合X的近似精度的近似精度和粗糙度分和粗糙度分别为别为集合（范畴或概念）的不精确性是由于集合（范畴或概念）的不精确性是由于边边界域的界域的存在而引起的，集合的存在而引起的，集合的边边界域越大，其精确性界域越大，其精确性则则越低。越低。反反应应了在知了在知识识R下下对对于集合于集合X

13、表达的范畴了解的程表达的范畴了解的程度。度。显显然，然，对对每一个每一个R和和X的的R-边边界域界域为为空集，所以集合空集，所以集合X是是R-可定可定义义的的(R-精精确集确集)；当；当 1时，集合时，集合X有非空有非空R-边界域，边界域，所以集合所以集合X是是R-不可定不可定义义的（的（R-粗糙集）；粗糙集）；X的的R-粗糙度与精度恰恰相反，它反映了我粗糙度与精度恰恰相反，它反映了我们们在知在知识识R下下对对于集合于集合X表达的范畴了解的不完全程度。表达的范畴了解的不完全程度。当当X为空集时，我们规定为空集时，我们规定例例2.6 给给定一个知定一个知识库识库K=(U,S)和知和知识库识库中一

14、中一个等价关系个等价关系R IND(K),它它导导出的等价出的等价类类如如下：下：Y1=x1,x4,x8,Y2=x2,x5,x7,Y3=x3,Y4=x6。其中，。其中，论论域域U=x1,x2,x8。试计试计算下列集合的算下列集合的R-近似精度和粗糙度，近似精度和粗糙度，其中，其中，直观上看，粗糙集理论对事情的不精确性表直观上看，粗糙集理论对事情的不精确性表述不需要任何假定的先验知识，而只是依赖述不需要任何假定的先验知识，而只是依赖于所给定的知识表达系统，通过上、下近似于所给定的知识表达系统，通过上、下近似算子直接计算得到的，这一点与概率论和模算子直接计算得到的，这一点与概率论和模糊集合论是完全

15、不同的。从粗糙集理论的角糊集合论是完全不同的。从粗糙集理论的角度看，客观事物的不精确性是由于我们所掌度看，客观事物的不精确性是由于我们所掌握知识的有限性所导致，换句话说，是由对握知识的有限性所导致，换句话说，是由对事物所包含对象的分类能力有限的结果所引事物所包含对象的分类能力有限的结果所引起的。因此，人们在没有任何先验知识的条起的。因此，人们在没有任何先验知识的条件下，可以通过分类的手段来处理不精确的件下，可以通过分类的手段来处理不精确的数值特征，进而表示概念得精确程度。数值特征，进而表示概念得精确程度。2.近似分类精度和近似分类质量近似分类精度和近似分类质量类别类别样样品品特征特征W1W2x

16、1x2x3 x4x5x6x7x8x9x10R10.360.400.200.180.270.540.520.680.490.81R20.100.200.300.402.500.600.700.800.900.50 定理定理 2.8 给给定一个定一个论论域域U和其上的一个等价和其上的一个等价关系（知关系（知识识）R,其其对应对应的划分或商集的划分或商集为为。如果。如果，都有，都有成立，成立，则对则对于任意于任意，都有，都有 至此，我们已经介绍了两种刻画粗糙集的方法。至此，我们已经介绍了两种刻画粗糙集的方法。其一为用近似程度的精确度来表示粗糙集的数字其一为用近似程度的精确度来表示粗糙集的数字特征；其

17、二为用粗糙集的分类表示粗糙集的拓扑特征；其二为用粗糙集的分类表示粗糙集的拓扑特征。粗糙集的数字特征表示了集合边界域的大特征。粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域地结构；而粗糙集的拓扑小，但没有说明边界域地结构；而粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边特征没有给出边界域大小的信息，它提供的是边界域的结构。界域的结构。此外，粗糙集的数字特征和粗糙集的拓扑特征此外，粗糙集的数字特征和粗糙集的拓扑特征之间存在一种关系。首先，如果集合为内不可定之间存在一种关系。首先，如果集合为内不可定义或全不可定义，则其精度为义或全不可定义，则其精度为0；其次，当集合为；其次，当集合

18、为外不可定义或全不可定义时，则它的补集的精度外不可定义或全不可定义时，则它的补集的精度为为0。这样，即使知道了集合的近似精度，我们也。这样，即使知道了集合的近似精度，我们也不能确定它的拓扑结构；反过来，集合的拓扑结不能确定它的拓扑结构；反过来，集合的拓扑结构也不具备精度的信息。构也不具备精度的信息。因此，在粗糙集的因此，在粗糙集的实际应实际应用中，我用中，我们们需要将需要将边边界界域的两种信息域的两种信息结结合起来，既要考合起来，既要考虑虑近似精度因素，近似精度因素，也要考也要考虑虑到集合的拓扑到集合的拓扑结结构。构。下面再通下面再通过过一个例子来一个例子来说说明明这这两种表示之两种表示之间间

19、的的关系。关系。例例 2.17 给给定一个知定一个知识库识库和一个等价关系和一个等价关系.其中其中论论域域为为且且R的等价的等价类为类为：试计试计算和算和讨论讨论下列集合的数字特征和拓扑特征。下列集合的数字特征和拓扑特征。解：（1）对集合下近似下近似 上近似上近似 因因为为是是R-可定义集，可定义集，边边界域界域 近似精度近似精度 （2）对对集合集合下近似下近似 上近似上近似而言：因因为为，同，同时时边边界域界域近似精度近似精度（3）对对集合集合下近似下近似上近似上近似根据定根据定义义2.12可知，集合可知，集合X3为为R-内不可定内不可定义义。近似精度近似精度所以所以X2是是R-粗糙可定义。

20、粗糙可定义。边界域边界域（4）对对于集合于集合下近似下近似上近似上近似根据定根据定义义2.12可知，集合可知，集合X4为为R-外不可定外不可定义义。（5）对对于集合于集合下近似下近似上近似上近似根据定根据定义义2.12可知，集合可知，集合X5为为R-全不可定全不可定义义；近似精度近似精度边界域边界域近似精度近似精度边界域边界域2.4 粗糙集中的隶属关系粗糙集中的隶属关系 在集合论中，成员与集合的隶属关系（成员关在集合论中，成员与集合的隶属关系（成员关系）是所有关系中最基本的关系。对隶属关系的系）是所有关系中最基本的关系。对隶属关系的分析是我们进行计算、推理的基础。本节主要介分析是我们进行计算、

21、推理的基础。本节主要介绍粗糙集中的隶属关系。绍粗糙集中的隶属关系。粗糙集合论的成员关系粗糙集合论的成员关系定定义义2.14给给定一个知定一个知识库识库（近似空（近似空间间）(,)，其中，其中，为论为论域上的等价关域上的等价关 系簇或系簇或单单个的等价关系。个的等价关系。则则定定义义(.)为为元素关于知元素关于知识识的隶属于集合粗糙隶属的隶属于集合粗糙隶属度，也称度，也称为为集合的集合的-粗糙隶属函数，其中，粗糙隶属函数，其中，|表示集合的基数，表示集合的基数，xR表示元素关于知表示元素关于知识识R的等的等价价类类。注：在粗糙集理论中，隶属度函数（成员关系）依注：在粗糙集理论中，隶属度函数（成员

22、关系）依赖于我们的知识赖于我们的知识R，即一个对象是否属于一个集合，即一个对象是否属于一个集合依赖于我们所掌握的知识依赖于我们所掌握的知识R，成员关系并不是绝对，成员关系并不是绝对的。的。性性质质2.4 2.4 粗糙集理粗糙集理论论中成中成员员关系（隶属度函数）关系（隶属度函数）的性的性质质 值值越大越大说说明明对对象象x属于集合属于集合X的的程度就越高。当程度就越高。当 时时，表明，表明对对象象x依据知依据知识识R判断肯定不属于集合判断肯定不属于集合X；当；当 时时，表明，表明对对象象x依据知依据知识识R判断肯定属于集合判断肯定属于集合X；当隶属度；当隶属度时时，表明，表明对对象象x依据知依

23、据知识识R判断有可能属于集合判断有可能属于集合X,同同时时也有可能不属于集合也有可能不属于集合X，即，即对对象象x落入集落入集合合X的的-边边界域。界域。这这足以足以说说明集合明集合X的模糊性的模糊性完全是由完全是由边边界域不空引起的。界域不空引起的。(2)对对象象x依据知依据知识识R判断肯定属于集合判断肯定属于集合对对象象x依据知依据知识识R判断可能属于集合判断可能属于集合 对对象象x依据知依据知识识R判断肯定不属于集合判断肯定不属于集合 就是集合就是集合X的特征函数。的特征函数。提供的不可区分关系提供的不可区分关系是一个等价关系。是一个等价关系。是是论论域域U中两两互中两两互不相交的集合不

24、相交的集合组组成的集合簇，成的集合簇，则则 xU U，其隶属度，其隶属度函数定函数定义为义为 （2.17）我我们们可以利用粗糙隶属度函数来定可以利用粗糙隶属度函数来定义义粗糙集合粗糙集合论论的基本概念，例如上近似、下近似、的基本概念，例如上近似、下近似、边边界域、正域、界域、正域、负负域等。域等。定定义义 2.15 给给定一个定一个论论域域U和和U上的一个等价关系上的一个等价关系R，xU U，我，我们们如下定如下定义义集合集合X的的R-下近似集，下近似集，R-边边界域，界域，R-正域，正域，R-负负域。域。由此可以看出，粗糙集定由此可以看出，粗糙集定义义的两种方法的两种方法都是都是强强调调粗糙

25、集概念的各个方面。由近粗糙集概念的各个方面。由近似定似定义诱导义诱导出粗糙集的拓扑出粗糙集的拓扑结结构，而隶构，而隶属度函数的方法属度函数的方法则则强强调调它的数它的数值值性性质质,用用概率概率论术语论术语可以解可以解释为释为：在粗糙集理在粗糙集理论论中，一个中，一个对对象是否隶属于某象是否隶属于某一集合（概念），不是一集合（概念），不是该该元素的客元素的客观观性性质质，而且取决于我而且取决于我们对们对它的了解程度，即知它的了解程度，即知识识的分的分类类能力。能力。这这更符合人更符合人类类的的认认知知过过程。程。.粗糙集中的集合关系粗糙集中的集合关系.集合的粗糙包含关系集合的粗糙包含关系粗糙集

26、合论的基本概念之一是粗糙包含关系。类似地，我们可以通过上近似和下近似来定义粗糙包含关系。显然，集合的包含关系不同于集合的粗糙包含关显然，集合的包含关系不同于集合的粗糙包含关系，下面给出一个例子来描述粗糙包含关系。系，下面给出一个例子来描述粗糙包含关系。性性质质2.5粗糙包含关系的性粗糙包含关系的性质质2.5.2 集合的粗糙相等关系集合的粗糙相等关系 集合的粗糙相等不同于一般的相等关系。集合的粗糙相等不同于一般的相等关系。在许多实际问题的求解过程中，我们利用所在许多实际问题的求解过程中，我们利用所掌握的知识很难判断两个范畴之间是否完全掌握的知识很难判断两个范畴之间是否完全相同，通常只能够判断两者

27、之间是否存在较相同，通常只能够判断两者之间是否存在较大的差异（粗糙不等）或较小的差异或极小大的差异（粗糙不等）或较小的差异或极小的差异或极其微小的差异（粗糙相等，也就的差异或极其微小的差异（粗糙相等，也就是说两个范畴的特征之间只有微小的差异）。是说两个范畴的特征之间只有微小的差异）。有时，可能还要分别考虑概念的正例、反例有时，可能还要分别考虑概念的正例、反例之间存在的关系，这可以通过下粗相等或上之间存在的关系，这可以通过下粗相等或上粗相等关系来刻画。集合的粗糙相等关系对粗相等关系来刻画。集合的粗糙相等关系对实际问题的求解有应用价值。下面将介绍这实际问题的求解有应用价值。下面将介绍这些内容。些内

28、容。实际上，集合的粗糙相等关系主要是比较实际上，集合的粗糙相等关系主要是比较集合的拓扑结构，而不是集合的元素。在一个给集合的拓扑结构，而不是集合的元素。在一个给定的知识库中，基于不同的知识，两个集合可能定的知识库中，基于不同的知识，两个集合可能是精确相等，也可能是粗糙（近似）相等，或许是精确相等，也可能是粗糙（近似）相等，或许是粗糙不相等。从粗糙集的观点看，集合的相等是粗糙不相等。从粗糙集的观点看，集合的相等是一个相对概念，不是绝对的，它与我们所掌握是一个相对概念，不是绝对的，它与我们所掌握的知识、或者说对事物的了解程度密切相关。的知识、或者说对事物的了解程度密切相关。综上所述，粗糙集的基本性

29、质，诸如成员综上所述，粗糙集的基本性质，诸如成员的隶属关系、集合的包含关系、集合的相等关系的隶属关系、集合的包含关系、集合的相等关系等都是相对的，都与我们所掌握的知识等都是相对的，都与我们所掌握的知识R相关。相关。因此，在这样的意义下，可以认为粗糙集的方法因此，在这样的意义下，可以认为粗糙集的方法是经典集合论方法的主观认识。是经典集合论方法的主观认识。2.6 知识约简知识约简 知识约简在智能信息或数据的处理中占有十知识约简在智能信息或数据的处理中占有十分重要的地位，也是粗糙集理论的核心内容之一。分重要的地位，也是粗糙集理论的核心内容之一。一般来讲，知识库中的知识（属性或等价关系）并一般来讲，知

30、识库中的知识（属性或等价关系）并不是同等重要的，甚至其中某些知识是不必要的，不是同等重要的，甚至其中某些知识是不必要的，或者说是冗余的。所谓的知识约简是指在保持知识或者说是冗余的。所谓的知识约简是指在保持知识库的分类能力不变的条件下，删除其中不必要的知库的分类能力不变的条件下，删除其中不必要的知识。本节主要介绍知识的约简和核，还包括概念簇识。本节主要介绍知识的约简和核，还包括概念簇的约简。的约简。2.6.1 知识的约简与核知识的约简与核 知识约简中有两个最基本的概念：约简知识约简中有两个最基本的概念：约简（reduction）与核（）与核（core）。由于它涉及知识的独）。由于它涉及知识的独立

31、性，所以我们先介绍知识独立性的定义。立性，所以我们先介绍知识独立性的定义。如果对每一个如果对每一个R P，R都为都为P中必要的，则称中必要的，则称P为独立的，否则称为独立的，否则称P是依赖的或不独立的。是依赖的或不独立的。定理定理2.10 如果知识如果知识P是独立的，是独立的，GP，则，则G一定一定也是独立的。也是独立的。定义定义2.19（知识的约简）给定一个知识库（知识的约简）给定一个知识库K=(U,S)和知识库上的等价关系和知识库上的等价关系PS，对任意的，对任意的GP，若，若G满足以下两条：满足以下两条：(1)G是独立的，是独立的，(2)IND(G)=IND(P)。则称则称G是是P的一个

32、约简，记为的一个约简，记为G RED(P)，其中，其中，RED(P)表示表示P的全体约简组成的集合。的全体约简组成的集合。显然，知识的任何一个约简与知识本身对显然，知识的任何一个约简与知识本身对知识库中的任意一个范畴的表达都是等同的，即知识库中的任意一个范畴的表达都是等同的，即它们对论语的分类能力相同。一般而言，知识的它们对论语的分类能力相同。一般而言，知识的约简不唯一，可以有多种约简。约简不唯一，可以有多种约简。定义定义2.20（知识的核）给定一个知识库（知识的核）给定一个知识库K=(U,S)和知识库上的一族等价关系和知识库上的一族等价关系PS，对任意的，对任意的R P，若，若R满足满足 I

33、ND(P-R)IND(P)，（2.24）则称则称R为为P中必要的中必要的,P中所有必要的知识组成的集中所有必要的知识组成的集合称为合称为P的核的核,记为记为CORE(P)。注意，核具有唯一性。注意，核具有唯一性。核与约简的关系如下所述。核与约简的关系如下所述。定理：定理：2.11 CORE(P)=RED(P)。定理定理2.11表明表明,知识的核等于知识的所有约简知识的核等于知识的所有约简的交集，意味着核包含在知识的每一个约简之中，的交集，意味着核包含在知识的每一个约简之中，是约简的最基础部分。是约简的最基础部分。直观上讲直观上讲,知识的核是它最重要的部分。核概知识的核是它最重要的部分。核概念有

34、两方面的作用：其一是核可以作为有所约简的念有两方面的作用：其一是核可以作为有所约简的计算基础，因为知识的核包含在知识的每一个约简计算基础，因为知识的核包含在知识的每一个约简之中，且计算可以直接进行；其二是核可以解释为之中，且计算可以直接进行；其二是核可以解释为知识特征的最主要部分知识特征的最主要部分,在知识约简时它不能被删除，在知识约简时它不能被删除，否则将减弱知识的分类能力。否则将减弱知识的分类能力。例例2.20 给定一个知识库给定一个知识库K=(U,S)，其中，论域为，其中，论域为U=x0,x1,x2,x8,且且S=R1,R2,R3，等价关系，等价关系R1,R2,R3和和IND(IR)对应

35、的等价类分别为：对应的等价类分别为：U/R1=x1,x4,x5,x2,x8,x3,x6,x7；U/R2=x1,x3,x5,x6,x2,x4,x7,x8；U/R3=x1,x5,x6,x2,x7,x8,x3,x4；U/IND(S)=x1,x5,x2,x8,x3,x4,x6,x7；试讨论试讨论R1,R2,R3对知识对知识IND(S)是否必要是否必要,并求并求IND(S)的核和所有约简。的核和所有约简。解：解：因为所以，所以，R 2为为S中不必要的。中不必要的。所以，所以，R 1为为S中必要的。中必要的。因为因为因因为为所以，所以，R 3为为S中不必要的。中不必要的。下面求下面求S的核和约简：的核和约

36、简：显然，显然，CORE(S)=R1。因为因为 显显然，然，U/IND(R1,R2)U/R1，说说明明R1在在IND(R1,R2)中中为为必要的，必要的，U/IND(R1,R2)U/R2，说说明明R2在在IND(R1,R2)中中为为必要的。必要的。因此，知因此，知识识R1,R2R1,R2,R3满满足定足定义义2.19的条件，所以它是知的条件，所以它是知识识 R1,R2,R3的一个的一个约简约简。因为因为 显显然，然，U/IND(R1,R3)U/R1，说说明明R1在在IND(R1,R3)中中为为必要的，必要的，U/IND(R1,R3)U/R2，说说明明R3在在IND(R1,R3)中中为为必要的。

37、必要的。由此可知，知识由此可知，知识 R1,R3独立的。因此，知识独立的。因此，知识 R1,R3 R1,R2,R3满足定义满足定义2.19的条件，所以的条件，所以它也是知识它也是知识 R1,R2,R3的一个约简。的一个约简。综上所述，知识综上所述，知识S=R1,R2,R3有两个约简有两个约简分别为分别为R1,R2和和 R1,R3，这三个知识对论域，这三个知识对论域U具具有相同的分类能力，但通过约简表达的知识更简单，有相同的分类能力，但通过约简表达的知识更简单，更易理解，适用性更强。更易理解，适用性更强。不难验证：不难验证：R1,R2 R1,R3=R1，即定，即定理理2.11成立。成立。例例2.

38、21 在不考虑决策属性前提下在不考虑决策属性前提下,试分别讨论试分别讨论2.3中条中条件属性（知识）件属性（知识）1,2,3对知识对知识1,2,3是否必是否必要，并求出知识要，并求出知识1,2,3的核和所有约简。其中，的核和所有约简。其中，论域论域U=e1,e2,e6；知识知识1的分类的分类U/1=X1,X2=e1,e2,e3,e4,e5,e6；知识知识2的分类的分类U/2=Y1,Y2=e1,e2,e3,e4,e6,e5；知识知识3的分类的分类U/3=C1,C2,C3=e1,e4,e2,e5,e3,e6；知识知识1,2,3的分类的分类U/IND (1,2,3)=e1,e2,e3,e4,e5,e

39、6。注意：这里集合中元素的对等关系按序排列。注意：这里集合中元素的对等关系按序排列。解：（解：（1）考虑属性）考虑属性1（头痛），因（头痛），因为为U/IND(1,2,3-1)=U/IND(2,3)=e1,e4,e2,e3,e6,e5 U/IND(1,2,3)，所以属性所以属性1在在1,2,3中是必中是必要的。要的。（2）考虑属性）考虑属性2（肌肉痛），因（肌肉痛），因为为U/IND(1,2,3-1)=U/IND(1,3)=e1,e2,e3,e4,e5,e6 =U/IND(1,2,3)，所以属性所以属性2在在1,2,3中是必中是必要的。要的。（3）考虑属性）考虑属性3（体温），因为（体温），因

40、为U/IND(1,2,3-3)=U/IND(1,2)=e1,e2,e3,e4,e6,e5 U/IND(1,2,3)，所以属性所以属性3在在1,2,3中是必要的。中是必要的。根据定义根据定义2.20 可知：可知：CORE(1,2,3)=1,3。以下求出知识以下求出知识1,2,3的所有约简，因为的所有约简，因为U/IND(1,3-1)=U/IND(3)U/IND(1),说明说明1在在U/IND(1,3)中为必要的。中为必要的。U/IND(1,3-3)=U/IND(1)U/IND(3),说明说明3在在U/IND(1,3)中为必要的。由此可知中为必要的。由此可知1,3是独立的。这样，是独立的。这样，1

41、,31,2,3 满足定义满足定义2.19的条件，因的条件，因此，此，1,3是是1,2,3的唯一的一个约简。的唯一的一个约简。对对于本于本题题而言，核与而言，核与约简约简是相同的，但是相同的，但在复在复杂杂的知的知识识表达系表达系统统中，二者通常不同。中，二者通常不同。注：当知注：当知识识本身独立本身独立时时，则则知知识识本身就是它本身就是它的的约简约简，且唯一。也就是，且唯一。也就是说说它不能被它不能被简简化。化。本例本例题题揭示了揭示了这样这样一个道理：将参数重要度一个道理：将参数重要度强强的知的知识结识结合在一起，分合在一起，分类类能力不一定就能力不一定就强强。例如重要度的排序例如重要度的

42、排序（见见例例2.10），但），但1,3的分的分类类能力大于能力大于2,3。知识的相对核和相对的约简知识的相对核和相对的约简在在许许多多实际应实际应用中，一个分用中，一个分类类相相对对于另一个分于另一个分类类的关系非常重要，例如例的关系非常重要，例如例2.3中的依属性中的依属性(知知识识或或等价关系等价关系)体温的分体温的分类对类对依决策属性流感的分依决策属性流感的分类类提提供了最多的有用信息。下面我供了最多的有用信息。下面我们们将介将介绍绍知知识识的相的相对约简对约简(relative reduct)和相和相对对核核(relative core)的的概念。概念。类类似地，我似地，我们们先介先

43、介绍绍知知识识的相的相对对必要性和独立必要性和独立性。性。为为此需要回此需要回顾顾“一个分一个分类类相相对对于另一个分于另一个分类类的的正域的概念正域的概念”。知。知识识Q相相对对于知于知识识P的正域的正域为为：或称其或称其为为知知识识Q的的P-正域，正域，记为记为posp(Q)。实质实质上，上，它是它是论论域域U中所有根据分中所有根据分类类U/P的信息可以准确的的信息可以准确的划分到关系划分到关系Q的等价的等价类类中去的中去的对对象集合。象集合。定义定义2.21 给定一个知识库给定一个知识库K=(U,S)和知识库中和知识库中的两个等价关系族的两个等价关系族P，QS，R P，若，若posIND

44、(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，GP，则称，则称G是是Q独立的。独立的。证明证明:利用反证法：假设利用反证法：假设 GP,G

45、不是不是Q独立的独立的,则则必存在必存在SG，使得，使得S是是Q独立的独立的,R (G-S)，有，有posIND(P)(IND(Q)=posIND(P-R)(IND(Q)成立。因此，成立。因此，P不是不是Q独立的，与已知矛盾，所以假设不成立。故独立的，与已知矛盾，所以假设不成立。故G是是Q独立的。独立的。定义定义2.22（知识的相对约简）（知识的相对约简）给定一个知识库给定一个知识库K=(U,S)和知识库上的两个等价关系族和知识库上的两个等价关系族P，QS，对任，对任意的意的GP，若，若G满足以下两条：满足以下两条：(1)G是是Q独立的，即独立的，即G是是P的的Q独立子族，独立子族，(2)po

46、sG(Q)=posP(Q)。则称则称G是是P的一个的一个Q约简，或称为约简，或称为G是是P相对于相对于Q的的一个约简，记为一个约简，记为G REDQ(P)，其中，其中，REDQ(P)表表示示P的全体的全体Q约简组成的集合。约简组成的集合。定义定义2.23（知识的相对核）（知识的相对核）给定一个知识库给定一个知识库K=(U,S)和知识库的两个等价关系族和知识库的两个等价关系族P，QS，对任，对任意的意的RP，若，若R满足满足posIND(P-R)(IND(Q)posIND(P)(IND(Q)(2.26)则称则称R为为P中中Q必要的，必要的，P中所有中所有Q必要的知识组成必要的知识组成集合称为集合

47、称为P的的Q核，或称为核，或称为P的相对于的相对于Q的核，也可的核，也可称为称为P的相对的相对Q核，记为核，记为COREQ（P）。）。注意：知识的相对核是唯一的。注意：知识的相对核是唯一的。相对核与相对约简的关系如下。相对核与相对约简的关系如下。定理定理2.13 COREQ(P)=REDQ（P）。）。该定理的证明类似于定理该定理的证明类似于定理2.11，故从略。，故从略。易知，当知识易知，当知识P=Q时，上诉内容就退化为节的内时，上诉内容就退化为节的内容，也就是说，相对核和相对约简的概念及其性质容，也就是说，相对核和相对约简的概念及其性质就退化为何和约简的概念及其性质。就退化为何和约简的概念及

48、其性质。例例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；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,R

49、3关于知识关于知识IND(S)是否是否Q必要，必要，并求并求IND(S)的的Q核和所有核和所有Q约简。约简。解：首先求出知解：首先求出知识识IND(S)关于知关于知识识Q的正域：的正域：(1)讨论是否讨论是否Q独立独立从从S中去掉知识中去掉知识R1可得，可得，且且所以，根据定义所以，根据定义2.21可知，可知，R1为为IR中中Q必要的。必要的。从从S中去掉知识中去掉知识R2可得划分为可得划分为所以，根据定所以，根据定义义2.21可知，可知，R2为为S中中Q不必要的。不必要的。且可导出关于知识且可导出关于知识Q正域为正域为 从从S中去掉知识中去掉知识R3可得划分为可得划分为所以，根据定所以，根据

50、定义义2.212.21可知，可知，R3为为S中中Q必要的。必要的。且可导出关于知识且可导出关于知识Q正域为正域为下面求下面求S的的Q核和核和Q约简约简。(2)显显然，然，S的的Q核核为为CORECOREQ(S)=)=R1,R3。(3)因因为为所以，知所以，知识识P=R1,R3S的的Q正域正域为为从从P中去掉知中去掉知识识R1可得，可得，U/IND(P-R1)=U/R3=x1,x5,x6,x3,x4,x2,x7,x8，且可且可导导出关于知出关于知识识Q正域正域为为所以，根据定所以，根据定义义2.212.21可知，可知，R1为为P中中Q必要的。必要的。从从P中去掉知中去掉知识识R3可得，可得，U/