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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人的分类能力是对事物的认识能力，是一种知识。从认知科学的观点来理解知识，知识可以被理解为对事物的分类能力及知识的分类能力可用知识系统的集合表达形式来描述。知识在不同的范畴中有许不同的含义。粗糙集理论认为，知识直接与真实或抽象世界的不同分类模式联系在一起。知识被看作是关于论域的划分，是一种对对象进行分类的能力。,第,2,章 粗糙集理论的基本概念,2.1,知识与知识库,1,定义,1.1,（知识和概念（范畴或信息粒）设,U,是给定研究对象的非空有限集合，称为一个论域。论域,U,的任何一个子集,X,U,，称为论域,U,的一个概念或范畴。论域,U,的一个划分,X,1,X,2,Xn,（概念簇）称为关于,U,的抽象知识，简称知识。为了规范化，我们认为空集也是一个概念，称为空概念。,在粗糙集理论中，主要讨论的是那些能够在论域,U,上形成划分或覆盖的知识。,2,我们知道,U,的划分,X1,X2,Xn,与,U,上的等价关系,R,一一对应，即给定,U,的一个划分,X1,X2,Xn,等同于给定,U,上的一个等价关系,R,，从数学的角度讲，关系的表示和处理比分类的表示和处理简单得多，因此，我们通常用等价关系或关系来表示分类及知识。因此知识也可以定义为，设,R,是,U,上的一个等价关系，,U/R=X1,X2,Xn,表示,R产生的分类，称为关于,U,的一个知识。,通常情形下，我们在问题求解的过程中，处理的不是论域,U,上的单一划分（知识或分类），而是论域,U,上的一簇划分，这导致了知识库的概念。,3,定义,1.2,（知识库,)U,为给定的一个论域，,S,是,U,上的一簇等价关系，称二元组,K=,（,U,S,）是关于论域,U,上的一个知识库或近似空间。,因此，论域上的等价关系就代表着划分和知识。这样，知识库就表示了论域上的由等价关系（这里指属性特征及其有限个的交）导出的各种各样的知识，即划分或分类模式，同时代表了对论域的分类能力，并隐含着知识库中概念之间存在的各种关系。,4,定义,2.3,（不可分辨关系（不分明关系）给定一个论域,U,和,U,上的一簇等价关系,S,，若,P,S,且,P,，则,P(P,中所有等价关系的交集）仍然是论域,U,上的一个等价关系，称为,P,上的不可分辨关系，记为,IND(P),，也常简记为,P,。而且，,5,这样，,U/IND(P)=x,IND(P),|,x,U,表示与等价关系,IND(P),相关的知识，称为知识库,K=(U,S),中关于论域,U,的,P-,基本知识（,P-,基本集,),。在不可能产生混淆的情况下，即,P,U,和,K,都明确时，为了简便，我们可用,P,代替,IND(P),。用,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),中所有等价关系，他对于集合的交运算是封闭的。任意有限个,P-,基本范畴的并，称为,P-,范畴；知识库,K=(U,S),中所有的范畴称为,K-,范畴。,6,定义,2.4,（两个知识库的关系）设,K,1,=(U,S,1,),和,K,2,=(U,S,2,),为两个知识库，如果,IND(S,1,)=IND(S,2),，即,U/IND(S,1,)=U/IND(S,2,),，则称知识库,K,1,与,K,2,是等价的，记为,K,1,K,2,或者,S,1,S,2,。因此当两个知识库有同样的基本范畴集时，这两个知识库中的知识都能使我们确切的表达关于论域的完全相同的事实。这就意味着可以用不同的属性集对论域的对象进行描述，以表达关于论域完全相同的知识。如果,IND(S,1,),IND,(S,2,),，我们称知识库,K,1,（知识,S,1,）比知识库,K,1,（知识,S,2,）更精细，或者说,K,2,（知识,S,2,）比,K,1,（知识,S,1,）更粗糙。当,S,1,比,S,2,更精细时，我们也称,S,1,为,S,2,的转化，或,S,2,为,S,1,的泛化。泛化意味着将某些范畴组合在一起，而特化则是将范畴分割成更小的概念。如果上述两种情形都不满足，则称两个知识库不能比较粗细。,7,8,表,2.1,积木的信息表,U(,积木,),R,1,(,颜色）,R,2,（形状,),R,3,（体积）,X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,红,蓝,红,蓝,黄,黄,红,黄,圆形,方形,三角形,三角形,圆形,方形,三角形,三角形,小,大,小,小,小,小,大,大,9,10,11,12,13,14,15,16,17,18,19,2.2,粗糙集的基本定义及其性质,20,21,22,23,24,25,26,27,其中，,X,，,Y,为论域,U,的子集，符号“,”,表示集合的补运算。,28,例,2.3,如表,2.2,（一个决策表）所示，对于属性子集（等价关系）,P=,头疼，肌肉疼,请判断论域的一个子集合,X=e,2,e,3,e,5,是否为,P,的粗糙集。若不是，请说明理由；若是，请求出,X,的,P-,下近似集，上近似集，边界域,正域,负域,.,表,2.2,例,2.3,中的一个医疗诊断决策表,论域,U,条件属性,决策,d,头痛,a1,肌肉痛,a2,体温,a3,e,1,e,2,e,3,e,4,e,5,e,6,是,是,是,否,否,否,是,是,是,是,否,是,正常,高,很高,正常,高,很高,否,是,是,否,否,是,29,30,31,32,33,34,2.3,粗糙集的特征,2.3.1,粗糙集的数字特征,1.,集合的近似精度和粗糙度,定义,2.7,（近似精度和粗糙度）给定一个论域,U,和,U,上的一个等价关系,R,，,称等价关系,R,定义的集合,X,的近似精度和粗糙度分别为,35,集合（范畴或概念）的不精确性是由于边界域的存在而引起的，集合的边界域越大，其精确性则越低。,反应了在知识,R,下对于集合,X,表达的范畴了解的程度。,显然，对每一个,R,和,X,的,R-,边界域为空集，所以集合,X,是,R-,可定义的,(R-,精确集,),；当,1,时，集合,X,有非空,R-,边界域，,所以集合,X,是,R不可定义的（,R-,粗糙集）；,X,的,R-,粗糙度与精度恰恰相反，它反映了我们在知识,R,下对于集合,X,表达的范畴了解的不完全程度。,当,X,为空集时，我们规定,36,例,2.6,给定一个知识库,K=(U,S),和知识库中一个等价关系,R,IND(K),它导出的等价类如下：,Y,1,=,x,1,x,4,x,8,Y,2,=,x,2,x,5,x,7,Y,3,=,x,3,Y,4,=,x,6,。其中，论域,U,=,x,1,x,2,x,8,。,试计算下列集合的,R-,近似精度和粗糙度，其中，,37,38,39,40,直观上看，粗糙集理论对事情的不精确性表述不需要任何假定的先验知识，而只是依赖于所给定的知识表达系统，通过上、下近似算子直接计算得到的，这一点与概率论和模糊集合论是完全不同的。从粗糙集理论的角度看，客观事物的不精确性是由于我们所掌握知识的有限性所导致，换句话说，是由对事物所包含对象的分类能力有限的结果所引起的。因此，人们在没有任何先验知识的条件下，可以通过分类的手段来处理不精确的数值特征，进而表示概念得精确程度。,41,2.,近似分类精度和近似分类质量,42,43,44,45,46,47,48,49,50,51,52,53,54,类别,样品,特征,W,1,W,2,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,x,10,R,1,0.36,0.40,020,0.18,0.27,0.54,0.52,0.68,0.49,0.81,R,2,0.10,0.20,0.30,0.40,2.50,0.60,0.70,0.80,0.90,0.50,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,定理,2.8,给定一个论域,U,和其上的一个等价关系（知识）,R,其对应的划分或商集为,。如果,，都有,成立，则对于任意,，都有,140,至此，我们已经介绍了两种刻画粗糙集的方法。其一为用近似程度的精确度来表示粗糙集的数字特征；其二为用粗糙集的分类表示粗糙集的拓扑特征。粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域地结构；而粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边界域的结构。,此外，粗糙集的数字特征和粗糙集的拓扑特征之间存在一种关系。首先，如果集合为内不可定义或全不可定义，则其精度为,0,；其次，当集合为外不可定义或全不可定义时，则它的补集的精度为,0,。这样，即使知道了集合的近似精度，我们也不能确定它的拓扑结构；反过来，集合的拓扑结构也不具备精度的信息。,141,因此，在粗糙集的实际应用中，我们需要将边界域的两种信息结合起来，既要考虑近似精度因素，也要考虑到集合的拓扑结构。,下面再通过一个例子来说明这两种表示之间的关系。,例,2.17,给定一个知识库,和一个等价关系,.,其中论域为,且,R,的等价类为：,试计算和讨论下列集合的数字特征和拓扑特征。,142,解：（,1,）对集合,下近似上近似,因为,是,R-,可定义集，,边界域,近似精度,（,2,）对集合,下近似,上近似,而言：,143,因为,，同时,边界域,近似精度,（,3,）对集合,下近似,上近似,根据定义,2.12,可知，集合,X,3,为,R-,内不可定义。,近似精度,所以,X2,是,R-,粗糙可定义。,边界域,144,（,4,）对于集合,下近似,上近似,根据定义,2.12,可知，集合,X,4,为,R-,外不可定义。,（,5,）对于集合,下近似,上近似,根据定义,2.12,可知，集合,X,5,为,R-,全不可定义；,近似精度,边界域,近似精度,边界域,145,2.4,粗糙集中的隶属关系,在集合论中，成员与集合的隶属关系（成员关系）是所有关系中最基本的关系。对隶属关系的分析是我们进行计算、推理的基础。本节主要介绍粗糙集中的隶属关系。,2.4.3,粗糙集合论的成员关系,定义,2.14,给定一个知识库（近似空间）,(,),，其中，为论域上的等价关 系簇或单个的等价关系。,则定义,(,.,),146,为元素关于知识的隶属于集合粗糙隶属度，也称为集合的,-,粗糙隶属函数，其中，,|,|,表示集合的基数，,x,R,表示元素关于知识,R,的等价类。,注：在粗糙集理论中，隶属度函数（成员关系）依赖于我们的知识,R,，即一个对象是否属于一个集合依赖于我们所掌握的知识,R,，成员关系并不是绝对的。,147,性质,2.4,粗糙集理论中成员关系（隶属度函数）,的性质,值越大说明对象,x,属于集合,X,的,程度就越高。当,时，表明对象,x,依据知识,R,判断肯定不属于集合,X,；当,时，表明对象,x,依据知识,R,判断肯定属于集合,X,；当隶属度,时，表明对象,x,依据知识,R,判断有可能属于集合,X,同时也有可能不属于集合,X,，即对象,x,落入集合,X,的,-,边界域。这足以说明集合,X,的模糊性完全是由边界域不空引起的。,148,(2),对象,x,依据知识,R,判断肯定属于集合,对象,x,依据知识,R,判断可能属于集合,对象,x,依据知识,R,判断肯定不属于集合,149,就是集合,X,的特征函数。,提供的不可区分关系,是一个等价关系。,150,是论域,U,中两两互不相交的集合组成的集合簇，则,x,U,，其隶属度函数定义为,（,2.17,）,151,我们可以利用粗糙隶属度函数来定义粗糙集合论的基本概念，例如上近似、下近似、边界域、正域、负域等。,定义,2.15,给定一个论域,U,和,U,上的一个等价关系,R,，,x,U,，我们如下定义集合,X,的,R-,下近似集，,R-,边界域，,R-,正域，,R-,负域。,152,由此可以看出，粗糙集定义的两种方法都是强调粗糙集概念的各个方面。由近似定义诱导出粗糙集的拓扑结构，而隶属度函数的方法则强调它的数值性质,用概率论术语可以解释为：,在粗糙集理论中，一个对象是否隶属于某一集合（概念），不是该元素的客观性质，而且取决于我们对它的了解程度，即知识的分类能力。这更符合人类的认知过程。,153,.,粗糙集中的集合关系,.,.,集合的粗糙包含关系,粗糙集合论的基本概念之一是粗糙包含关系。类似地，我们可以通过上近似和下近似来定义粗糙包含关系。,154,155,显然，集合的包含关系不同于集合的粗糙包含关系，下面给出一个例子来描述粗糙包含关系。,156,157,158,159,160,性质,2.5,粗糙包含关系的性质,161,2.5.2,集合的粗糙相等关系,集合的粗糙相等不同于一般的相等关系。在许多实际问题的求解过程中，我们利用所掌握的知识很难判断两个范畴之间是否完全相同，通常只能够判断两者之间是否存在较大的差异（粗糙不等）或较小的差异或极小的差异或极其微小的差异（粗糙相等，也就是说两个范畴的特征之间只有微小的差异）。有时，可能还要分别考虑概念的正例、反例之间存在的关系，这可以通过下粗相等或上粗相等关系来刻画。集合的粗糙相等关系对实际问题的求解有应用价值。下面将介绍这些内容。,162,163,164,165,166,167,168,169,170,171,172,173,174,实际上，集合的粗糙相等关系主要是比较集合的拓扑结构，而不是集合的元素。在一个给定的知识库中，基于不同的知识，两个集合可能是精确相等，也可能是粗糙（近似）相等，或许是粗糙不相等。从粗糙集的观点看，集合的相等是一个相对概念，不是绝对的，它与我们所掌握的知识、或者说对事物的了解程度密切相关。,综上所述，粗糙集的基本性质，诸如成员的隶属关系、集合的包含关系、集合的相等关系等都是相对的，都与我们所掌握的知识,R,相关。因此，在这样的意义下，可以认为粗糙集的方法是经典集合论方法的主观认识。,175,2.6,知识约简,知识约简在智能信息或数据的处理中占有十分重要的地位，也是粗糙集理论的核心内容之一。一般来讲，知识库中的知识（属性或等价关系）并不是同等重要的，甚至其中某些知识是不必要的，或者说是冗余的。所谓的知识约简是指在保持知识库的分类能力不变的条件下，删除其中不必要的知识。本节主要介绍知识的约简和核，还包括概念簇的约简。,2.6.1,知识的约简与核,知识约简中有两个最基本的概念：约简（,reduction,）与核（,core,）。由于它涉及知识的独立性，所以我们先介绍知识独立性的定义。,176,如果对每一个,R,P,，,R,都为,P,中必要的，则称,P,为独立的，否则称,P,是依赖的或不独立的。,定理,2.10,如果知识,P,是独立的，,G,P,，则,G,一定也是独立的。,177,定义,2.19,（知识的约简）给定一个知识库,K,=(,U,S,),和知识库上的等价关系,P,S,，对任意的,G,P,，若,G,满足以下两条：,(1),G,是独立的，,(2)IND(,G,)IND(,P,),。,则称,G,是,P,的一个约简，记为,G,RED,(,P,),，其中，,RED(,P,),表示,P,的全体约简组成的集合。,显然，知识的任何一个约简与知识本身对知识库中的任意一个范畴的表达都是等同的，即它们对论语的分类能力相同。一般而言，知识的约简不唯一，可以有多种约简。,178,定义,2.20,（知识的核）给定一个知识库,K,=(,U,S,),和知识库上的一族等价关系,P,S,，对任意的,R,P,，若,R,满足,IND(,P,-,R,)IND(,P,),，（,2.24,）,则称,R,为,P,中必要的,P,中所有必要的知识组成的集合称为,P,的核,记为,CORE(,P,)注意，核具有唯一性。,核与约简的关系如下所述。,定理：,2.11 CORE(,P,)=RED(,P,),。,定理,2.11,表明,知识的核等于知识的所有约简的交集，意味着核包含在知识的每一个约简之中，是约简的最基础部分。,179,直观上讲,知识的核是它最重要的部分。核概念有两方面的作用：其一是核可以作为有所约简的计算基础，因为知识的核包含在知识的每一个约简之中，且计算可以直接进行；其二是核可以解释为知识特征的最主要部分,在知识约简时它不能被删除，否则将减弱知识的分类能力。,例,2.20,给定一个知识库,K,=(,U,S,),，其中，论域为,U,=,x,0,x,1,x,2,x,8,且,S,R,1,R,2,R,3,，等价关系,R,1,R,2,R,3,和,IND(,IR,),对应的等价类分别为：,U,/,R,1,=,x,1,x,4,x,5,x,2,x,8,x,3,x,6,x,7,；,U,/,R,2,=,x,1,x,3,x,5,x,6,x,2,x,4,x,7,x,8,；,U,/,R,3,=,x,1,x,5,x,6,x,2,x,7,x,8,x,3,x,4,；,U,/IND(,S,)=,x,1,x,5,x,2,x,8,x,3,x,4,x,6,x,7,；,试讨论,R,1,R,2,R,3,对知识,IND(,S,),是否必要,并求,IND(,S,),的核和所有约简。,180,解：,因为,所以，,R,2,为,S,中不必要的。,所以，,R,1,为,S,中必要的。,因为,181,因为,所以，,R,3,为,S,中不必要的。,下面求,S,的核和约简：,显然，,CORE(,S,)=,R,1,。,因为,182,显然，,U,/IND(,R,1,R,2,),U,/,R,1,，说明,R,1,在,IND(,R,1,R,2,),中为必要的，,U,/IND(,R,1,R,2,),U,/,R,2,，说明,R,2,在,IND(,R,1,R,2,),中为必要的。,因此，知识,R,1,R,2,R,1,R,2,R,3,满足定义,2.19,的条件，所以它是知识,R,1,R,2,R,3,的一个约简。,因为,183,显然，,U,/IND(,R,1,R,3,),U,/,R,1,，说明,R,1,在,IND(,R,1,R,3,),中为必要的，,U/IND(,R,1,R,3,),U,/,R,2,，说明,R,3,在,IND(,R,1,R,3,),中为必要的。,由此可知，知识,R,1,R,3,独立的。因此，知识,R,1,R,3,R,1,R,2,R,3,满足定义,2.19,的条件，所以它也是知识,R,1,R,2,R,3,的一个约简。,综上所述，知识,S,=,R,1,R,2,R,3,有两个约简分别为,R,1,R,2,和,R,1,R,3,，这三个知识对论域,U,具有相同的分类能力，但通过约简表达的知识更简单，更易理解，适用性更强。,不难验证：,R,1,R,2,R,1,R,3,=,R,1,，即定理,2.11,成立。,184,例,2.21,在不考虑决策属性前提下,试分别讨论,2.3,中条件属性（知识）,1,2,3,对知识,1,2,3,是否必要，并求出知识,1,2,3,的核和所有约简。其中，论域,U,=,e,1,e,2,e,6,；,知识,1,的分类,U,/,1,=,X,1,X,2,=,e,1,e,2,e,3,e,4,e,5,e,6,；,知识,2,的分类,U,/,2,=,Y,1,Y,2,=,e,1,e,2,e,3,e,4,e,6,e,5,；,知识,3,的分类,U,/,3,=,C,1,C,2,C,3,=,e,1,e,4,e2,e,5,e,3,e,6,；,知识,1,2,3,的分类,U/IND (,1,2,3,)=,e,1,e,2,e,3,e,4,e,5,e,6,。,注意：这里集合中元素的对等关系按序排列。,185,解：（,1,）考虑属性,1,（头痛），因为,U,/IND(,1,2,3,-,1,),=,U,/IND(,2,3,),=,e,1,e,4,e,2,e,3,e,6,e,5,U,/IND(,1,2,3,),，,所以属性,1,在,1,2,3,中是必要的。,（,2,）考虑属性,2,（肌肉痛），因为,U,/IND(,1,2,3,-,1,),=,U,/IND(,1,3,),=,e,1,e,2,e,3,e,4,e,5e,6,=,U,/IND(,1,2,3,),，,所以属性,2,在,1,2,3,中是必要的。,186,（,3,）考虑属性,3,（体温），因为,U,/IND(,1,2,3,-,3,)=,U,/IND(,1,2,),=,e,1,e,2,e,3,e,4,e,6,e,5,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,3,1,2,3,满足定义,2.19,的条件，因此，,1,3,是,1,2,3,的唯一的一个约简。,187,对于本题而言，核与约简是相同的，但在复杂的知识表达系统中，二者通常不同。,注：当知识本身独立时，则知识本身就是它的约简，且唯一。也就是说它不能被简化。,本例题揭示了这样一个道理：将参数重要度强的知识结合在一起，分类能力不一定就强。例如重要度的排序,（见例,2.10,），但,1,3,的分类能力大于,2,3,。,188,26.2,知识的相对核和相对的约简,在许多实际应用中，一个分类相对于另一个分类的关系非常重要，例如例,2.3,中的依属性,(,知识或等价关系,),体温的分类对依决策属性流感的分类提供了最多的有用信息。下面我们将介绍知识的相对约简,(relative reduct),和相对核,(relative core),的概念。,类似地，我们先介绍知识的相对必要性和独立性。为此需要回顾,“,一个分类相对于另一个分类的正域的概念,”,。知识,Q,相对于知识,P,的正域为：,或称其为知识,Q,的,P,-,正域，记为,pos,p,(,Q,),。实质上，它是论域,U,中所有根据分类,U,/,P,的信息可以准确的划分到关系,Q,的等价类中去的对象集合。,189,定义,2.21,给定一个知识库,K,=(,U,S,),和知识库中的两个等价关系族,P,，,Q,S,，,R,P,，若,pos,IND(,P,),(IND(,Q,)=pos,IND(,P,-,R,),(IND(,Q,)(2.25),成立，则称知识,R,为,P,中,Q,不必要的，否则称,R,为,P,中,Q,必要的。,为了简便起见，常用,posIND(,P,)(,Q,),代替,pos,IND(,P,),(IND(,Q,),。,如果对每一个,R,P,，,R,都为,P,中,Q,必要的，则称,P,为,Q,独立的，或称,P,相对于,Q,独立，否则称,P,是,Q,依赖的或,Q,不独立的。,190,定理,2.12,如果知识,P,，,G,P,，则称,G,是,Q,独立的。,证明,:,利用反证法：假设,G,P,G,不是,Q,独立的,则必存在,S,G,，使得,S,是,Q,独立的,R,(,G,-,S,),，有,pos,IND(,P,),(IND(,Q,)=pos,IND(,P,-,R,),(IND(,Q,),成立。因此，,P,不是,Q,独立的，与已知矛盾，所以假设不成立。故,G,是,Q,独立的。,定义,2.22,（知识的相对约简）给定一个知识库,K,=(,U,S,),和知识库上的两个等价关系族,P,，,Q,S,，对任意的,G,P,，若,G,满足以下两条：,(1),G是,Q,独立的，即,G,是,P,的,Q,独立子族，,(2)pos,G,(,Q,)=pos,P,(,Q,),。,则称,G,是,P,的一个,Q,约简，或称为,G,是,P,相对于,Q,的一个约简，记为,G,RED,Q,(,P,),，其中，,RED,Q,(,P,),表示,P,的全体,Q,约简组成的集合。,191,定义,2.23,（知识的相对核）给定一个知识库,K=(U,S),和知识库的两个等价关系族,P,，,Q,S,，对任意的,RP,，若,R,满足,posIND(P-R)(IND(Q)posIND(P)(IND(Q)(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,节的内容，也就是说，相对核和相对约简的概念及其性质就退化为何和约简的概念及其性质。,192,例,2.22,给定一个知识库,K,=(,U,S,),和知识库中独立于,S,的知识,Q,，其中，论域,U,=,x,0,x,1,x,2,x,8,，且,S,=,R,1,R,2,R3,，等价关系,R,1,R,2,R,3,和,IND(,S,),对应的等价类分别为,U,/,R,1=,x,1,x,3,x,4,x,5,x,6,x,7,x,2,x,8,；,U,/,R,2=,x,1,x,3,x,4,x,5,x,2,x,6,x,7,x,8,；,U,/,R,3=,x,1,x,6,x,5,x,3,x,4,x,2,x,7,x,8,；,U,/IND(,S,)=,x,1,x,5,x,2,x,8,x,3,x,4,x,6,x,7,；,U,/,Q,=,x,1,x,5,x,6,x,2,x,7,x,3,x,4,x,8,；,试讨论,R,1,R,2,R,3,关于知识,IND(,S,),是否,Q,必要，并求IND(,S,),的,Q,核和所有,Q,约简。,193,解：首先求出知识,IND(,S,),关于知识,Q,的正域：,(1),讨论是否,Q,独立,从,S,中去掉知识,R,1,可得，,194,且,所以，根据定义,2.21,可知，,R,1,为,IR,中,Q,必要的。,从,S,中去掉知识,R,2,可得划分为,195,所以，根据定义,2.21,可知，,R,2,为,S,中,Q,不必要的。,且可导出关于知识,Q,正域为,196,从,S,中去掉知识,R,3,可得划分为,所以，根据定义,2.21,可知，,R,3,为,S,中,Q,必要的。,且可导出关于知识,Q,正域为,197,下面求,S,的,Q,核和,Q,约简2),显然，,S,的,Q,核为,CORE,Q,(,S,)=,R,1,R,3,。,(3),因为,所以，知识,P,=,R,1,R,3,S,的,Q,正域为,198,从,P,中去掉知识,R,1,可得，,U,/IND(,P,-,R,1,)=,U,/,R,3,=,x,1,x,5,x,6,x,3,x,4,x,2,x,7,x,8,，,且可导出关于知识,Q,正域为,所以，根据定义,2.21,可知，,R,1,为,P,中,Q,必要的。,199,从,P,中去掉知识,R,3,可得，,U,/IND(,P,-,R,3,)=,U,/,R,1,=,x,1,x,3,x,4,x,5,x,6,x,7,x,2,x,8,，,且可导出关于知识,Q,正域为,所以，根据定义,2.21,可知，,R,3,为,P,中,Q,必要的。,200,由此可知，知识,P,=,R,1,R,3,S,是,S,的,Q,独立子族。,又因为,pos,IND(,P,),(,Q,)=pos,IND(,S,),(,Q,),因此,P,满足根据定义,2.22,的条件，所以，知识,P,=,R,1,R,3,S,是,S,的,Q,约简。,注意：本题的,Q,约简唯一。一般来讲，复杂的知识表达系统的约简或,Q,约简常常不是唯一的。,综上所述，我们可知如果有,P,中的知识对于将论域,U,中的对象正确地划分到知识,Q,的基本范畴（,IND(,Q,),等价类）都是必不可少的，那么知识,P,就是,Q,独立的。知识,P,的,Q,核是知识,P,最基本的特征部分，如果删除,P,的,Q,核中的任何一个元素都将会削弱将论域中的对象正确地划分到知识,Q,的等价类的能力。,201,对知识,P,而言，,P,的,Q,约简是保持将,U,中的对象正确地划分到知识,Q,的基本范畴（,IND(,Q,),等价类）分类能力不变的,P,的,Q,独立子集，它不具有唯一性。在一定的意义下，只有一个,Q,约简的知识,P,，我们认为它是确定的，因为当我们依照知识,P,的基本范畴将论域中的对象划分到知识,Q,的基本范畴中时只有一种,P,的知识基（,P,商集）可用。另一方面，当知识,P,有多个,Q,约简时，我们认为它是不确定的，因为当我们依照知识,P,的基本范畴将论域中的对象划分到知识,Q,的基本范畴中时有多种,P,的知识基（,P,商集）可利用。当知识,P,的,Q,核为空集时，知识,P,的不确定性达到最强。,202,2.6.3,知识范畴的核和约简,知识的基本范畴是知识的基（知识基），也就是构建知识范畴的基本模块。知识库中的每一个概念都可以通过知识的基本范畴精确或近似地表达，反之，每一个基本范畴都是某些知识范畴的交集，这自然导致一个问题“对于知识的基本范畴是否所有的范畴都是必要的？”该问题类似于知识库中的知识，即一般情形下，知识的范畴存在着冗余。下面介绍知识范畴的核和约简。,203,定义,2.24,（知识范畴的必要性）给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇,S,pos,(,U,)=,F,=,X,1,X,2,X,n,X,i,F,(,i,=1,2,n,),如果,(,F,-,X,i,)=,F,(2.27),成立，则称范畴（子集）,X,i,在,F,中为不必要的，否则为必要的。,定义,2.25,（知识范畴的独立性）给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇,S,pos,(,U,)=,F,=,X,1,X,2,X,n,X,i,F,(,i,=1,2,n,),如果,(,F,-,X,i,),F,(2.28),成立，则称,F,是独立，否则为不独立或依赖的。,204,定义,2.26,（知识范畴的约简）给定一个知识库,K,=(,U,S,),和,论域,U,上的一个子集,簇,S,pos,(,U,)=,F,=,X,1,X,2,X,n,对任意的,G,P,，若,G,满足以下两个条件：,(1),G,是独立的，,(2),G,=,F,则称,G,是,F,的一个约简，,表示,F,的全体约简组成的集合,表示知识范畴的约简，以便与知识的约简,RED,区别开来。,205,定义,2.27,（知识范畴的核）称,F,中所有必要的知识范畴组成的集合称为,F,的核,记为,注意：知识范畴的核是唯一的。核是知识范畴中最重要的部分,删除知识范畴核中任何一个范畴都会削弱该知识范畴对知识库中范畴的表达能力知识范畴的核与约简的关系如下。,定理,2.14,206,例,2.23,给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇（知识库中的一簇范畴）,Sub(,U,)=,F,=,E,1,E,2,E,3,，其中，,论域,U,=,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,；,E,1,=,e,1,e,3,e,8,；,E,2,=,e,1,e,3,e,4,e,5,e,6,；,E,3,=,e,1,e,3,e,4,e,6,e,7,。,试讨论知识范畴,E,i,(,i,=1,2,3),对,F,是否必要,并求出,F,的约简和核。,解：首先求出,F,的交：,F,=,E,1,E,2,E,3,=,e,1,e,3,。,(1),知识范畴,E,i,(,i,=1,2,3),对,F,是否必要,从,F,中删除,E,1,可知：,(,F,-,E,1,)=,E,2,E,3,=,e,1,e,3,e,4,e,6,F,所以根据定义,2.24,可知范畴,E,1,在,F,中必要。,207,从,F,中删除,E,2,可知：,(,F,-,E,2,)=,E,1,E,3,=,e,1,e,3,=,F,所以根据定义,2.24,可知,范畴,E,2,在,F,中不必要。,从,F,中删除,E,3,可知：,(,F,-,E,3,)=,E,1,E,2,=,e,1,e,3,=,F,所以根据定义,2.24,可知,范畴,E,3,在,F中不必要。,(2),F,的核显然为,(3),F,的,约简,由于每一个约简都包含核，因此下面我们考虑,H,1,=,E,1,E,2,，,H,2,=,E,1,E,3,F,是否为,F,的,约简。,对于,H,1,=,E,1,E,2,F,而言：,(),H,1,=,E,1,E,2,=,F,；,208,()(,H,1,-,E,1,)=,E,2,H,1,，所以,E,1,在,H,1,中必要；,(,H,1,-,E,2,)=,E,1,H,1,，所以,E,2,在,H,1,中必要。由此可知,H,1,是独立的。,综上所述，根据定义,2.26,可知，,H,1,=,E,1,E,2,F,是知识范畴,F,的一个约简。,对于,H,2,=,E,1,E,3,F,而言：,(),H,2,=,E,1,E,3,=,F,；,()(,H,2,-,E,1,)=,E,3,H,1,，所以,E,1,在,H,2,中必要；,(,H,2,-,E,2,)=,E,1,H,2,，所以,E,2,在,H,2,中必要。由此可知,H,2,是独立的。,综上所述，根据定义,2.26,可知，,H,2,=,E,1,E,3,F,是知识范畴,F,的一个约简。,显然，,F,有两个约简,H,1,=,E,1,E,2,和,H,2,=,E,1,E,3,。,209,例,2.24,给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇（知识库中的一簇范畴）,Sub(2,U,)=F,=,E,1,E,2,E,3,E,4,，其中，,论域,U,=,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,；,E,1,=,e,1,e,2,e,5,e,6,；,E,2,=,e,2,e,3,e,5,；,E,3,=,e,1,e,3,e,5,e,6,；,E,4,=,e,1,e,5,e,6,。,试讨论知识范畴,Ei,(,i,=1,2,3),对,F,是否必要,并求出,F,的约简和核。,类似于例,2.23,，此题的求解过程留给读者。,在决策系统中，我们经常会考虑一些范畴的并是否存在冗余？绝大多数情形下答案是否定的。出于简化决策的需要，有必要研究并范畴的约简问题，这一问题类似于交范畴的约简问题。,210,定义,2.28,（知识范畴并的必要性）给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇,S,pos,(2,U,)=,F,=,X,1,X,2,X,n,X,i,F,(,i,=1,2,n,),如果,(,F,-,Xi,)=,F,(2.29),成立，则称范畴（子集）,X,i,在,F,中为不必要的，否则为必要的。,定义,2.29,（一簇知识范畴,F,相对于它的并的独立性）给定一个知识库,K,=(,U,S,),和论域,U,上的一个子集簇,S,(2,U,)=,F,=,X,1,X,2,X,n,X,i,F,(,i,=1,2,n,),如果,(,F,-,X,i,),F,(2.30)