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

《粗糙集理论的基本概念.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论的基本概念.ppt（225页珍藏版）》请在三一办公上搜索。

1、人的分类能力是对事物的认识能力，是一种知识。从认知科学的观点来理解知识，知识可以被理解为对事物的分类能力及知识的分类能力可用知识系统的集合表达形式来描述。知识在不同的范畴中有许不同的含义。粗糙集理论认为，知识直接与真实或抽象世界的不同分类模式联系在一起。知识被看作是关于论域的划分，是一种对对象进行分类的能力。,第2章 粗糙集理论的基本概念2.1知识与知识库,定义1.1（知识和概念（范畴或信息粒）设U是给定研究对象的非空有限集合，称为一个论域。论域U的任何一个子集X U，称为论域U的一个概念或范畴。论域U的一个划分X1,X2,Xn（概念簇）称为关于U的抽象知识，简称知识。为了规范化，我们认为空集

2、也是一个概念，称为空概念。在粗糙集理论中，主要讨论的是那些能够在论域U上形成划分或覆盖的知识。,我们知道U的划分X1,X2,Xn与U上的等价关系R一一对应，即给定U的一个划分X1,X2,Xn等同于给定U上的一个等价关系R，从数学的角度讲，关系的表示和处理比分类的表示和处理简单得多，因此，我们通常用等价关系或关系来表示分类及知识。因此知识也可以定义为，设R是U上的一个等价关系，U/R=X1,X2,Xn 表示R产生的分类，称为关于U的一个知识。通常情形下，我们在问题求解的过程中，处理的不是论域U上的单一划分（知识或分类），而是论域U上的一簇划分，这导致了知识库的概念。,定义1.2（知识库)U为给定

3、的一个论域，S是U上的一簇等价关系，称二元组K=（U,S）是关于论域U上的一个知识库或近似空间。因此，论域上的等价关系就代表着划分和知识。这样，知识库就表示了论域上的由等价关系（这里指属性特征及其有限个的交）导出的各种各样的知识，即划分或分类模式，同时代表了对论域的分类能力，并隐含着知识库中概念之间存在的各种关系。,定义2.3（不可分辨关系（不分明关系）给定一个论域U和U上的一簇等价关系S，若PS,且P，则P(P中所有等价关系的交集）仍然是论域U上的一个等价关系，称为P上的不可分辨关系，记为IND(P)，也常简记为P。而且，,这样，U/IND(P)=xIND(P)|xU 表示与等价关系IND(

4、P)相关的知识，称为知识库K=(U,S)中关于论域U的P-基本知识（P-基本集)。在不可能产生混淆的情况下，即P,U和K都明确时，为了简便，我们可用P代替IND(P)。用U/P代替U/IND(P)，IND(P)的等价类也称为知识P的基本概念或基本范畴。事实上，P基本范畴拥有知识P的论域的基本特征，换句话说，他们是知识的基本模块。特别地，如果QS,则称Q是关于论域U的Q-初等知识，Q的等价类为知识S的Q初等概念或初等范畴。我们用IND(K)=IND(P)|P S表示知识库K=(U,S)中所有等价关系，他对于集合的交运算是封闭的。任意有限个P-基本范畴的并，称为P-范畴；知识库K=(U,S)中所有

5、的范畴称为K-范畴。,定义2.4（两个知识库的关系）设K1=(U,S1)和K2=(U,S2)为两个知识库，如果IND(S1)=IND(S2)，即U/IND(S1)=U/IND(S2)，则称知识库K1与K2是等价的，记为K1K2或者S1S2。因此当两个知识库有同样的基本范畴集时，这两个知识库中的知识都能使我们确切的表达关于论域的完全相同的事实。这就意味着可以用不同的属性集对论域的对象进行描述，以表达关于论域完全相同的知识。如果IND(S1)IND(S2)，我们称知识库K1（知识S1）比知识库K1（知识S2）更精细，或者说K2（知识S2）比K1（知识S1）更粗糙。当S1比S2更精细时，我们也称S1

6、为S2的转化，或S2为S1的泛化。泛化意味着将某些范畴组合在一起，而特化则是将范畴分割成更小的概念。如果上述两种情形都不满足，则称两个知识库不能比较粗细。,表2.1积木的信息表,2.2粗糙集的基本定义及其性质,其中，X，Y为论域U的子集，符号“”表示集合的补运算。,例2.3如表2.2（一个决策表）所示，对于属性子集（等价关系）P=头疼，肌肉疼请判断论域的一个子集合X=e2,e3,e5是否为P的粗糙集。若不是，请说明理由；若是，请求出X的P-下近似集，上近似集，边界域,正域,负域.表2.2 例2.3中的一个医疗诊断决策表,2.3粗糙集的特征粗糙集的数字特征1.集合的近似精度和粗糙度定义2.7（近

7、似精度和粗糙度）给定一个论域U和U上的一个等价关系R，,称等价关系R定义的集合X的近似精度和粗糙度分别为,集合（范畴或概念）的不精确性是由于边界域的存在而引起的，集合的边界域越大，其精确性则越低。,反应了在知识R下对于集合X表达的范畴了解的程度。显然，对每一个R和,X的R-边界域为空集，所以集合X是R-可定义的(R-精确集)；当 1时，集合X有非空R-边界域，,所以集合X是R-不可定义的（R-粗糙集）；,X的R-粗糙度与精度恰恰相反，它反映了我们在知识R下对于集合X表达的范畴了解的不完全程度。,当X为空集时，我们规定,例2.6 给定一个知识库K=(U,S)和知识库中一个等价关系RIND(K),

8、它导出的等价类如下：Y1=x1,x4,x8,Y2=x2,x5,x7,Y3=x3,Y4=x6。其中，论域U=x1,x2,x8。试计算下列集合的R-近似精度和粗糙度，其中，,直观上看，粗糙集理论对事情的不精确性表述不需要任何假定的先验知识，而只是依赖于所给定的知识表达系统，通过上、下近似算子直接计算得到的，这一点与概率论和模糊集合论是完全不同的。从粗糙集理论的角度看，客观事物的不精确性是由于我们所掌握知识的有限性所导致，换句话说，是由对事物所包含对象的分类能力有限的结果所引起的。因此，人们在没有任何先验知识的条件下，可以通过分类的手段来处理不精确的数值特征，进而表示概念得精确程度。,2.近似分类精

9、度和近似分类质量,定理 2.8 给定一个论域U和其上的一个等价关系（知识）R,其对应的划分或商集为,。如果,，都有,成立，则对于任意,，都有,至此，我们已经介绍了两种刻画粗糙集的方法。其一为用近似程度的精确度来表示粗糙集的数字特征；其二为用粗糙集的分类表示粗糙集的拓扑特征。粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域地结构；而粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边界域的结构。此外，粗糙集的数字特征和粗糙集的拓扑特征之间存在一种关系。首先，如果集合为内不可定义或全不可定义，则其精度为0；其次，当集合为外不可定义或全不可定义时，则它的补集的精度为0。这样，即使知道了集合

10、的近似精度，我们也不能确定它的拓扑结构；反过来，集合的拓扑结构也不具备精度的信息。,因此，在粗糙集的实际应用中，我们需要将边界域的两种信息结合起来，既要考虑近似精度因素，也要考虑到集合的拓扑结构。下面再通过一个例子来说明这两种表示之间的关系。例 2.17 给定一个知识库,和一个等价关系,.其中论域为,且R的等价类为：,试计算和讨论下列集合的数字特征和拓扑特征。,解：（1）对集合,下近似,上近似,因为,是R-可定义集，,边界域,近似精度,（2）对集合,下近似,上近似,而言：,因为,，同时,边界域,近似精度,（3）对集合,下近似,上近似,根据定义2.12可知，集合X3为R-内不可定义。,近似精度,

11、所以X2是R-粗糙可定义。,边界域,（4）对于集合,下近似,上近似,根据定义2.12可知，集合X4为R-外不可定义。,（5）对于集合,下近似,上近似,根据定义2.12可知，集合X5为R-全不可定义；,近似精度,边界域,近似精度,边界域,2.4 粗糙集中的隶属关系 在集合论中，成员与集合的隶属关系（成员关系）是所有关系中最基本的关系。对隶属关系的分析是我们进行计算、推理的基础。本节主要介绍粗糙集中的隶属关系。,粗糙集合论的成员关系,定义2.14给定一个知识库（近似空间）(,)，其中，为论域上的等价关 系簇或单个的等价关系。,则定义,(.),为元素关于知识的隶属于集合粗糙隶属度，也称为集合的-粗糙

12、隶属函数，其中，|表示集合的基数，xR表示元素关于知识R的等价类。,注：在粗糙集理论中，隶属度函数（成员关系）依赖于我们的知识R，即一个对象是否属于一个集合依赖于我们所掌握的知识R，成员关系并不是绝对的。,性质2.4 粗糙集理论中成员关系（隶属度函数）的性质,值越大说明对象x属于集合X的程度就越高。当,时，表明对象x依据知识R判断肯定不属于集合X；当,时，表明对象x依据知识R判断肯定属于集合X；当隶属度,时，表明对象x依据知识R判断有可能属于集合X,同时也有可能不属于集合X，即对象x落入集合X的-边界域。这足以说明集合X的模糊性完全是由边界域不空引起的。,(2)对象x依据知识R判断肯定属于集合

13、,对象x依据知识R判断可能属于集合,对象x依据知识R判断肯定不属于集合,就是集合X的特征函数。,提供的不可区分关系,是一个等价关系。,是论域U中两两互不相交的集合组成的集合簇，则xU，其隶属度函数定义为,（2.17）,我们可以利用粗糙隶属度函数来定义粗糙集合论的基本概念，例如上近似、下近似、边界域、正域、负域等。定义 2.15 给定一个论域U和U上的一个等价关系R，xU，我们如下定义集合X的R-下近似集，R-边界域，R-正域，R-负域。,由此可以看出，粗糙集定义的两种方法都是强调粗糙集概念的各个方面。由近似定义诱导出粗糙集的拓扑结构，而隶属度函数的方法则强调它的数值性质,用概率论术语可以解释为

14、：,在粗糙集理论中，一个对象是否隶属于某一集合（概念），不是该元素的客观性质，而且取决于我们对它的了解程度，即知识的分类能力。这更符合人类的认知过程。,.粗糙集中的集合关系,.集合的粗糙包含关系粗糙集合论的基本概念之一是粗糙包含关系。类似地，我们可以通过上近似和下近似来定义粗糙包含关系。,显然，集合的包含关系不同于集合的粗糙包含关系，下面给出一个例子来描述粗糙包含关系。,性质2.5粗糙包含关系的性质,2.5.2 集合的粗糙相等关系 集合的粗糙相等不同于一般的相等关系。在许多实际问题的求解过程中，我们利用所掌握的知识很难判断两个范畴之间是否完全相同，通常只能够判断两者之间是否存在较大的差异（粗糙

15、不等）或较小的差异或极小的差异或极其微小的差异（粗糙相等，也就是说两个范畴的特征之间只有微小的差异）。有时，可能还要分别考虑概念的正例、反例之间存在的关系，这可以通过下粗相等或上粗相等关系来刻画。集合的粗糙相等关系对实际问题的求解有应用价值。下面将介绍这些内容。,实际上，集合的粗糙相等关系主要是比较集合的拓扑结构，而不是集合的元素。在一个给定的知识库中，基于不同的知识，两个集合可能是精确相等，也可能是粗糙（近似）相等，或许是粗糙不相等。从粗糙集的观点看，集合的相等是一个相对概念，不是绝对的，它与我们所掌握的知识、或者说对事物的了解程度密切相关。综上所述，粗糙集的基本性质，诸如成员的隶属关系、集

16、合的包含关系、集合的相等关系等都是相对的，都与我们所掌握的知识R相关。因此，在这样的意义下，可以认为粗糙集的方法是经典集合论方法的主观认识。,2.6 知识约简 知识约简在智能信息或数据的处理中占有十分重要的地位，也是粗糙集理论的核心内容之一。一般来讲，知识库中的知识（属性或等价关系）并不是同等重要的，甚至其中某些知识是不必要的，或者说是冗余的。所谓的知识约简是指在保持知识库的分类能力不变的条件下，删除其中不必要的知识。本节主要介绍知识的约简和核，还包括概念簇的约简。2.6.1 知识的约简与核 知识约简中有两个最基本的概念：约简（reduction）与核（core）。由于它涉及知识的独立性，所以

17、我们先介绍知识独立性的定义。,如果对每一个RP，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的一个约简，记为GRED(P)，其中，RED(P)表示P的全体约简组成的集合。显然，知识的任何一个约简与知识本身对知识库中的任意一个范畴的表达都是等同的，即它们对论语的分类能力相同。一般而言，知识的约简不唯一，可以有多种约简。,定义2.20（知识的核）给

18、定一个知识库K=(U,S)和知识库上的一族等价关系PS，对任意的RP，若R满足 IND(P-R)IND(P)，（2.24）则称R为P中必要的,P中所有必要的知识组成的集合称为P的核,记为CORE(P)。注意，核具有唯一性。核与约简的关系如下所述。定理：2.11 CORE(P)=RED(P)。定理2.11表明,知识的核等于知识的所有约简的交集，意味着核包含在知识的每一个约简之中，是约简的最基础部分。,直观上讲,知识的核是它最重要的部分。核概念有两方面的作用：其一是核可以作为有所约简的计算基础，因为知识的核包含在知识的每一个约简之中，且计算可以直接进行；其二是核可以解释为知识特征的最主要部分,在知

19、识约简时它不能被删除，否则将减弱知识的分类能力。例2.20 给定一个知识库K=(U,S)，其中，论域为U=x0,x1,x2,x8,且S=R1,R2,R3，等价关系R1,R2,R3和IND(IR)对应的等价类分别为：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中必要

20、的。,因为,因为,所以，R 3为S中不必要的。下面求S的核和约简：显然，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)中为必要的。,由此可知，知识 R1,R3独立的。因此，知识 R1,R3 R1,R2,R

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

22、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,e6。注意：这里集合中元素的对等关系按序排列。,解：（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（体温），因为U

23、/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,31,2,3 满足定义2.19的条件，因此，1,3是1,2,3的唯一的一个约简。,对于本题而言，核与约简是相同的，但在复杂的知

24、识表达系统中，二者通常不同。注：当知识本身独立时，则知识本身就是它的约简，且唯一。也就是说它不能被简化。本例题揭示了这样一个道理：将参数重要度强的知识结合在一起，分类能力不一定就强。例如重要度的排序,（见例2.10），但1,3的分类能力大于2,3。,知识的相对核和相对的约简在许多实际应用中，一个分类相对于另一个分类的关系非常重要，例如例2.3中的依属性(知识或等价关系)体温的分类对依决策属性流感的分类提供了最多的有用信息。下面我们将介绍知识的相对约简(relative reduct)和相对核(relative core)的概念。类似地，我们先介绍知识的相对必要性和独立性。为此需要回顾“一个分类

25、相对于另一个分类的正域的概念”。知识Q相对于知识P的正域为：,或称其为知识Q的P-正域，记为posp(Q)。实质上，它是论域U中所有根据分类U/P的信息可以准确的划分到关系Q的等价类中去的对象集合。,定义2.21 给定一个知识库K=(U,S)和知识库中的两个等价关系族P，QS，RP，若posIND(P)(IND(Q)=posIND(P-R)(IND(Q)(2.25)成立，则称知识R为P中Q不必要的，否则称R为P中Q必要的。为了简便起见，常用posIND(P)(Q)代替posIND(P)(IND(Q)。如果对每一个RP，R都为P中Q必要的，则称P为Q独立的，或称P相对于Q独立，否则称P是Q依赖的

26、或Q不独立的。,定理 2.12 如果知识P，GP，则称G是Q独立的。证明:利用反证法：假设GP,G不是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)posG(Q)=posP(Q)。则称G是P的一个Q约简，或称为G是P相对于Q的一个约简，记为GREDQ(P)，其中，REDQ

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

28、为何和约简的概念及其性质。,例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,R3关于知识IND(S)是否Q必要，并求IND(S)的Q核和所有Q约简。

29、,解：首先求出知识IND(S)关于知识Q的正域：,(1)讨论是否Q独立从S中去掉知识R1可得，,且,所以，根据定义2.21可知，R1为IR中Q必要的。从S中去掉知识R2可得划分为,所以，根据定义2.21可知，R2为S中Q不必要的。,且可导出关于知识Q正域为,从S中去掉知识R3可得划分为,所以，根据定义2.21可知，R3为S中Q必要的。,且可导出关于知识Q正域为,下面求S的Q核和Q约简。(2)显然，S的Q核为COREQ(S)=R1,R3。(3)因为,所以，知识P=R1,R3S的Q正域为,从P中去掉知识R1可得，U/IND(P-R1)=U/R3=x1,x5,x6,x3,x4,x2,x7,x8，且可

30、导出关于知识Q正域为,所以，根据定义2.21可知，R1为P中Q必要的。,从P中去掉知识R3可得，U/IND(P-R3)=U/R1=x1,x3,x4,x5,x6,x7,x2,x8，且可导出关于知识Q正域为,所以，根据定义2.21可知，R3为P中Q必要的。,由此可知，知识P=R1,R3S是S的Q独立子族。又因为posIND(P)(Q)=posIND(S)(Q),因此P满足根据定义2.22的条件，所以，知识P=R1,R3S是S的Q约简。注意：本题的Q约简唯一。一般来讲，复杂的知识表达系统的约简或Q约简常常不是唯一的。,综上所述，我们可知如果有P中的知识对于将论域U中的对象正确地划分到知识Q的基本范畴

31、（IND(Q)等价类）都是必不可少的，那么知识P就是Q独立的。知识P的Q核是知识P最基本的特征部分，如果删除P的Q核中的任何一个元素都将会削弱将论域中的对象正确地划分到知识Q的等价类的能力。,对知识P而言，P的Q约简是保持将U中的对象正确地划分到知识Q的基本范畴（IND(Q)等价类）分类能力不变的P的Q独立子集，它不具有唯一性。在一定的意义下，只有一个Q约简的知识P，我们认为它是确定的，因为当我们依照知识P的基本范畴将论域中的对象划分到知识Q的基本范畴中时只有一种P的知识基（P商集）可用。另一方面，当知识P有多个Q约简时，我们认为它是不确定的，因为当我们依照知识P的基本范畴将论域中的对象划分到

32、知识Q的基本范畴中时有多种P的知识基（P商集）可利用。当知识P的Q核为空集时，知识P的不确定性达到最强。,知识范畴的核和约简,知识的基本范畴是知识的基（知识基），也就是构建知识范畴的基本模块。知识库中的每一个概念都可以通过知识的基本范畴精确或近似地表达，反之，每一个基本范畴都是某些知识范畴的交集，这自然导致一个问题“对于知识的基本范畴是否所有的范畴都是必要的？”该问题类似于知识库中的知识，即一般情形下，知识的范畴存在着冗余。下面介绍知识范畴的核和约简。,定义2.24（知识范畴的必要性）给定一个知识库K=(U,S)和论域U上的一个子集簇Spos(U)=F=X1,X2,Xn,XiF(i=1,2,n

33、),如果(F-Xi)=F(2.27)成立，则称范畴（子集）Xi 在F中为不必要的，否则为必要的。定义2.25（知识范畴的独立性）给定一个知识库K=(U,S)和论域U上的一个子集簇Spos(U)=F=X1,X2,Xn,XiF(i=1,2,n),如果(F-Xi)F(2.28)成立，则称F是独立，否则为不独立或依赖的。,定义2.26（知识范畴的约简）给定一个知识库K=(U,S)和论域U上的一个子集簇Spos(U)=F=X1,X2,Xn,对任意的GP，若G满足以下两个条件：(1)G是独立的，(2)G=F,则称G是F的一个约简，,表示F的全体约简组成的集合,表示知识范畴的约简，以便与知识的约简RED区别

34、开来。,定义2.27（知识范畴的核）称F中所有必要的知识范畴组成的集合称为F的核,记为,注意：知识范畴的核是唯一的。核是知识范畴中最重要的部分,删除知识范畴核中任何一个范畴都会削弱该知识范畴对知识库中范畴的表达能力。知识范畴的核与约简的关系如下。定理2.14,例2.23 给定一个知识库K=(U,S)和论域U上的一个子集簇（知识库中的一簇范畴）Sub(U)=F=E1,E2,E3，其中，论域U=e1,e2,e3,e4,e5,e6,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的约

35、简和核。解：首先求出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中必要。,从F中删除E2可知：(F-E2)=E1E3=e1,e3=F,所以根据定义2.24可知范畴E2在F中不必要。从F中删除E3可知：(F-E3)=E1E2=e1,e3=F,所以根据定义2.24可知范畴E3在F中不必要。(2)F的核显然为,(3)F的约简由于每一个约简都包含核，因此下面我们考虑H1=E1,E2，H2=E1,E3F是否为F的约简。,对于H1=E1,E2F而言：()H1=

36、E1E2=F；,()(H1-E1)=E2 H1，所以E1在H1中必要；(H1-E2)=E1 H1，所以E2在H1中必要。由此可知H1是独立的。综上所述，根据定义2.26可知，H1=E1,E2F是知识范畴F的一个约简。对于H2=E1,E3F而言：()H2=E1E3=F；()(H2-E1)=E3 H1，所以E1在H2中必要；(H2-E2)=E1 H2，所以E2在H2中必要。由此可知H2是独立的。综上所述，根据定义2.26可知，H2=E1,E3F是知识范畴F的一个约简。显然，F有两个约简H1=E1,E2和H2=E1,E3。,例2.24 给定一个知识库K=(U,S)和论域U上的一个子集簇（知识库中的一

37、簇范畴）Sub(2U)=F=E1,E2,E3,E4，其中，论域U=e1,e2,e3,e4,e5,e6,e7,e8；E1=e1,e2,e5,e6；E2=e2,e3,e5；E3=e1,e3,e5,e6；E4=e1,e5,e6。试讨论知识范畴Ei(i=1,2,3)对F是否必要,并求出F的约简和核。类似于例2.23，此题的求解过程留给读者。在决策系统中，我们经常会考虑一些范畴的并是否存在冗余？绝大多数情形下答案是否定的。出于简化决策的需要，有必要研究并范畴的约简问题，这一问题类似于交范畴的约简问题。,定义2.28（知识范畴并的必要性）给定一个知识库K=(U,S)和论域U上的一个子集簇Spos(2U)=

38、F=X1,X2,Xn,XiF(i=1,2,n),如果(F-Xi)=F(2.29)成立，则称范畴（子集）Xi 在F中为不必要的，否则为必要的。定义2.29（一簇知识范畴F相对于它的并的独立性）给定一个知识库K=(U,S)和论域U上的一个子集簇S(2U)=F=X1,X2,Xn,XiF(i=1,2,n),如果(F-Xi)F(2.30)成立，则称F在F中是独立，否则为不独立或依赖的。,定义2.30（知识范畴并的约简）给定一个知识库K=(U,S)和论域U上的一个子集簇S(2U)=F=X1,X2,Xn,对任意的G F，若G满足以下两个条件：(1)G在G中是独立的，(2)G=F,则称G是F的一个约简，,表示

39、F的全体约简组成的集合,表示知识范畴的约简，以便与知识的约简RED区别开来。,注意：知识范畴的核是唯一的。核是知识范畴中最重要的部分,删除知识范畴核中任何一个范畴都会削弱该知识范畴对知识库中范畴的表达能力。知识范畴并的核与约简的如下关系,例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是否必

40、要,并求出F的约简和核。,不一定恒成立。,解：首先求出F的并：F=E1E2E3E4=e1,e2,e3,e4,e5,e6,e7,e8=U。(1)判断知识范畴Ei(i=1,2,3)对F是否必要从F中删除E1可知：(F-E1)=E2E3E4=e1,e2,e3,e4,e5,e6,e7F,所以根据定义2.28可知范畴E1在F中必要。从F中删除E2可知：(F-E2)=E1E3 E4=e1,e3=U=F,所以根据定义2.28可知范畴E2在F中不必要。从F中删除E3可知：(F-E3)=E1E2 E4=U=F,所以根据定义2.28可知范畴E3在F中不必要。,从F中删除E4可知：(F-E4)=E1E2 E3=U=

41、F,所以根据定义2.28可知范畴E4在F中不必要。(2)F的核：显然有,(3)F的约简由于每一个约简都包含核，因此下面我们考虑H1=E1,E2,E3，H2=E1,E2,E4，H3=E1,E3,E4F是否为F的约简。对于H1=E1,E2,E3F而言：H1=E1E2E3=U=F；(H1-E1)=E2E3=e1,e2,e3,e4,e5,e6,e7 H1，所以E1在H1中必要；(H1-E2)=E1=e1,e3,e4,e6,e7,e8 H1，所以E2在H1中必要。,(H1-E3)=E1E2=e1,e2,e3,e4,e5,e6,e8 H1，所以E3在H1中必要。由此可知H1关于H1是独立的。综上所述，根据

42、定义2.30可知，H1=E1,E2,E3是F的一个约简。同理可证H2=E1,E2,E4和H3=E1,E3,E4均为F的约简。这意味着由范畴E1,E2,E3,E4的并构成的概念或范畴F可以简单等价地表成这些范畴一部分的并。,知识范畴的相对核和相对约简 为了研究哪些知识对于保持某些范畴的性质是必要的，我们需要推广范畴的核和约简的概念-关于一个特定范畴的核和约简，即知识范畴的相对核和相对约简。定义2.32（知识范畴的相对必要性）给定一个知识库K=(U,S)，论域U上的一个子集簇Sub(2U)=F=X1,X2,Xn和一个集合Y U,且F Y，XiF(i=1,2,n)，如果(F-Xi)Y(2.31)成立

43、，则称范畴（子集）Xi 在F中相对于Y是不必要的，否则相对于Y是必要的。,定义2.33（知识范畴的相对独立性）给定一个知识库K=(U,S)和论域U上的一个子集簇Sub(2U)=F=X1,X2,Xn和一个集合Y U,且F Y，XiF(i=1,2,n),如果(F-Xi)Y(2.32)成立，则称F在F中是相对于Y独立的，否则为相对于Y不独立或依赖的。定义2.34（知识范畴的相对约简）给定一个知识库K=(U,S)和论域U上的一个子集簇Sub(2U)=F=X1,X2,Xn和一个集合Y U,且F Y，对任意的GP，若G满足以下两个条件：(1)G在F中相对于Y是独立的，(2)G Y,则称G是F的一个Y约简，

44、,表示F的全体Y约简组成的集合,表示知识范畴的相对于Y约简，以便与知识的相对约简REDQ区别开来。显然，知识范畴的交范畴的任何一个Y约简与知识范畴本身对知识库中的该知识的基本范畴的表达都是等同的，即它们对知识范畴的基本范畴的定义是相同的。一般而言，知识范畴的约简不唯一，可以有多个。定义2.35（知识范畴的相对核）称F的在F中所有相对于Y必要的知识范畴组成的集合称为F的相对Y核,记为,注意：知识范畴的相对核是唯一的。相对核与相对约简的关系如下：,定理2.15,该定理的证明类似于定理2.11，故从略。例2.27 给定一个知识库K=(U,S)，论域U上的一个子集簇（知识库中的一簇范畴）Sub(2U)

45、=F=E1,E2,E3，知识库中的指定范畴T=e1,e2和Y=e1,e3,e6，其中论域U=e1,e2,e3,e4,e5,e6,e7,e8；E1=e1,e3,e8；E2=e1,e3,e4,e5,e6；E3=e1,e3,e4,e6,e7。试分别讨论知识范畴Ei(i=1,2,3)在F中是否T和Y必要,并求出F的相对约简和相对核。,解：首先求出F的交。(1)T=F=e1,e2，根据定义2.322.35和例2.20的结果可得：E1在F中关于T是不独立德（依赖的）；F在F中的T-核,F在F中的T-约简有两个，分别为E1,E2，E1,E3，即,显然，定理2.15对于本例成立。下面考虑指定范畴不同于F的情形

46、。(2)先讨论知识范畴Ei(i=1,2,3)在F中相对Y是否必要。因为F=E1E2E3=e1,e3，指定范畴 Y=e1,e3,e6F，又因为,从F中删除E1可知：(F-E1)=E2E3=e1,e3,e4,e6 Y,所以根据定义2.32可知范畴E1在F中关于Y是必要的。,从F中删除E2可知：(F-E2)=E1E3=e1,e3Y,所以根据定义2.32可知范畴E2在F中关于Y是不必要的。从F中删除E3可知：(F-E3)=E1E2=e1,e3Y,所以根据定义2.32可知范畴E3在F中关于Y是不必要的。(3)F的相对Y核：显然有,(4)F的相对Y约简由于每一个相对约简都包含相对核，因此下面我们考虑包含F

47、的相对核的子集簇H1=E1,E2，H2=E1,E3F是否为F的相对Y约简。对于H1=E1,E2F而言，有()H1=E1E2=FY；()(H1-E1)=E2 Y，所以E1在H1中相对Y是必要的；(H1-E2)=E1 Y，所以E2在H1中相对Y是必要的。由此可知H1是独立的。综上所述，根据定义2.34可知，H1=E1,E2F是知识范畴F的一个Y约简。,对于H2=E1,E3F而言，有()H2=E1E3 Y；()(H2-E1)=E3 Y，所以E1在H2中相对Y是必要的；(H2-E2)=E1 Y，所以E2在H2中相对Y是必要的。由此可知H2是独立的。综上所述，根据定义2.34可知，H2=E1,E3F是知识范畴F的一个相对Y约简。显然，F有两个相对Y约简H1=E1,E2和H2=E1,E3，且满足定理2.14。注意：当指定的范畴与F相同时，F的相对约简和相对与其对应的约简和核结果相同。,类似于知识的约简，通过范畴的约简可以从知识库中删除那些冗余的初等范畴。总之，在一个知识库中，知识的约简主要包括特征属性的约简和初等范畴的约简且方法类似。通过约简就可以删除知识库中所有不必要的知识（冗余的知识），而只保留知识或信息中真正有用的部分。这样的思想和方法有极其重要的应用价值，我们将在信息系统和决策表的信息智能处理中更加详细地阐述该思想及其方法。,