第9章 粗糙集理论.ppt

1、第9章 粗糙集理论,粗糙集理论是一种刻划不完整性和不确定性的数学工具， 能有效地分析不精确、不一致和不完整等各种不完备的信息。 还可以对数据进行分析和推理，从中发现隐含的知识， 揭示潜在的规律。,9.1 粗糙集理论概述,9.1.1 粗糙集理论的产生,1970年，Z.Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集（Rough Set）理论的思想。 1982年，Z.Pawlak发表经典论文“Rough Sets”，标志着该理论正式诞生。 1991年，Z.Pawlak的第一本关于粗糙集理论的专著Rough sets：theoretical aspect

2、s of reasoning about data。,1992年，Slowinski主编的Intelligence decision support：handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。 1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的 Foundation of computingand decision sciences上。 1995年，Z.Pawlak等人在ACM Communications

3、上发表“Rough sets”，极大地扩大了该理论的国际影响。 19961999年，分别在日本、美国、美国、日本召开了第47届粗糙集理论国际研讨会。,目前，粗糙集理论受到了国际上越来越多的学者的关注，不仅在数学上具有独立的地位，并发展出Rough代数学、Rough逻辑学等，而且在智能数据分析、知识发现和数据挖掘中得到广泛的研究和应用。,9.1.2 粗糙集理论的特点,粗糙集理论是一种数据分析工具。 粗糙集理论不需要先验知识。 粗糙集理论是一种软计算方法。,9.1.3 粗糙集理论在数据挖掘中的应用,在数据预处理过程中，粗糙集理论可以用于对特征更准确的提取 在数据准备过程中，利用粗糙集理论的数据约简

4、特性，对数据集进行降维操作。 在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。 在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。,9.2 粗糙集理论中的基本概念,9.2.1 集合的基本概念,定义9.1 设R是集合U中的二元关系，若R是自反的、对称的和传递的，则称R是等价关系。,定义9.2 设R是非空集合U中的等价关系，对于任一确定的xU，均可构造一个U的子集xR。称为由x生成（或以x为代表元素）的R等价类： xR=y | yX且x R y 由此定义可知，集合U中与x有等价关系R的所有元素构成的集合就是xR。 等价关系也称为不可分辨关系，也就是说，x1xR，x2xR，则x1和x

5、2相对于等价关系R来说是不可分辨的。,定义9.3 设R是非空集合U中的等价关系。由U的各元素生成的R等价类所构成的集合xR | xU，称为U关于R的商集。记作U/R。,【例9.1】集合A=1，2，3，4，有二元关系： R1=(1，1)，(2，2)，(3，3)，(4，4)，(2，3)，(3，2)，(3，4)，(4，3)，(2，4)，(4，2)， R2=(1，1)，(2，2)，(3，3)，(4，4)，(1，2)，(2，1)，(1，3)，(3，1)，(2，3)，(3，2)， 显然R1和R2都是A上的等价关系。,【例9.2】 在例9.1中，则有： A/R1=1，2，3，4， A/R2=1，2，3，4。

6、,定义9.4 设U是非空集合。A=A1，A2，Am，其中集合AiU且Ai（i1，2，m）且=U，则称A是U的覆盖。,定义9.5 设A是U的覆盖，且满足AiAj=（ij），则称A是U的划分。A的任一元素ai，都称为A的一个类或划分的一个块。,R1关系的划分,R2关系的划分,定义9.6 设A=A1，A2，Am与B=B1，B2，Bn是非空集合U的两种划分。如果对于划分B的每一个类Bi，都存在划分A的一个类Aj，使得BiAj，则称B是A的细分。,定义9.7 设A=A1，A2，Am与B=B1，B2，Bn是非空集合U的两种划分，若U的划分C满足： （1）C是A和B的细分； （2）称C是划分A和B的积，记为

7、C=AB。且C=AB=AiBj | i=1，2，m，j=1，2，n，AiBj。,R1关系的划分,R2关系的划分,R1R2关系的划分,9.2.2 信息系统和粗糙集,定义9.8 信息系统I可以形式化表达为四元组I=(U，A，V，f)，其中，U为对象非空有限集合，称为论域，U中每个元素唯一标识一个对象； A为属性的非空有限集合，A=A1，A2，Am； V=Vi，Vi是属性Ai的值域； f：UAV是一个信息函数，它为每个对象的每个属性赋予一个信息值，即aA，xU，f(x，a)Va。,信息系统也称为知识表达系统或信息表，可以简记为I=（U，A），,如表9.1所示的是一个积木信息表I1，其中，U=1，2，

8、3，4，5，6，7，8，A=颜色，形状，大小，U=1，2，3，4，5，6，7，8。A=颜色，形状，大小。V颜色=红色，蓝色，黄色，V形状=圆形，方形，三角形，V大小=大，小。信息函数f对应该关系表。,定义9.9 设I=（U，A）是一个信息系统，对于PA， xi、 xj U，定义二元关系INDP称为等价关系：,称对象xi、 xj在信息系统I中关于属性集P是等价的，当且仅当p(xi)=p(xj)对所有的pP 成立，即xi、 xj不能用P 中的属性加以区别。 例如，表9.1中，对象4和8关于属性集颜色，形状是等价的，因为它们的颜色均为“蓝色”、形状均为“三角形”。,实际上，信息系统I中每个属性或者属

9、性子集都可以对所有的对象产生划分，也就是说可以将A中一个属性或者属性子集看成是一个等价关系。从中看到，等价关系体现出一种分类能力，所以说等价关系就是一种知识。 粗糙集理论就是建立在分类机制的基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。,定义9.10 设I=（U，A）是一个信息系统，使用等价关系R对U进行划分，产生的等价类集合称为关于U的知识库，记为K = (U，R)，其中每个等价类称为知识库K的知识。,由此可见，一个信息系统 I=（U，A），可以看作是一个知识库K=（U，A），若PA且P，则P（P中所有等价关系的交集）也是一个等价关系，P上的不可分辨关系IN

10、D(P)由以下等价类构成：,或者说：,【例9.4】 对于表9.1所示的信息表I1，定义这样的三个等价关系：R1=颜色，R2=形状，R3=大小，则： U/R1=1，3，7，2，4，5，6，8，对应知识库为K1=（U，R1） U/R2=1，5，2，6，3，4，7，8，对应知识库为K2=（U，R2） U/R3=2，7，8，1，3，4，5，6，对应知识库为K3=（U，R3）,而U/R1，R2，R3=U/R1U/R2U/R3=1，2，3，4，5，6，7，8。 所以说U/R1、U/R2和U/R3中的每个等价类是知识库K=(U，R1，R2，R3)中的初等概念。,基于R1的初等概念如下：,1，3，7：红色积木

11、 2，4：蓝色积木 5，6，8：黄色积木,基于R2的初等概念如下：,1，5：圆形积木 2，6：方形积木 3，4，7，8：三角形积木,基于R3的初等概念如下：,2，7，8：大积木 1，3，4，5，6：小积木,基本概念是初等概念的交集。基于R1，R2的基本概念如下：,1，3，71，5=1：红色圆形积木 1，3，73，4，7，8=3，7：红色三角形积木 2，42，6=2：蓝色方形积木 2，43，4，7，8=4：蓝色三角形积木 5，6，81，5=5：黄色圆形积木 5，6，82，6=6：黄色方形积木 5，6，83，4，7，8=8：黄色三角形积木,由U/R1、U/R2的初等概念构成U/R1，R2的基本概念

12、如下图所示。,定义9.11 设K=（U，R）是一个知识库，对于一个集合XU，当X能表达成某些基本等价类（初等概念）的并集时，称为可定义的；否则称为不可定义的。 R可定义集X能在这个知识库中被精确地定义，所以又称X为R精确集。R不可定义集X不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称X为R粗糙集。,例如，一个知识库为（U，R），并有U/R=1，4，8，2，5，7，3，6。 则集合X=2，3，5，7是R精确集，因为2，5，73=X，而2，5，7和3均为知识库中的知识； 而集合Y=1，7是R粗糙集，因为不能由U/R中任何等价类通过并集得到。,定义9.12 设K=（U，R）是一

13、个知识库，对于一个集合XU，则：,集合X的R下近似（集）定义为：R_(X)=yiU/R | yiX 集合X的R上近似（集）定义为：R-(X)=yiU/R | yiX 集合X的R边界域：BNR(X)= R-(X)-R_(X) 集合X的R正域：POSR(X)=R_(X) 集合X的R负域：NEGR(X)=U-R-(X),集合X是R精确的，当且仅当R-(X)=R_(X)。集合X是R粗糙的，当且仅当R-(X)R_(X)。,粗糙集中相关概念的示意图,【例9.5】 设论域U=1，2，3，4，5，6，7，8，U上有R1、R2和R三个等价关系，且R=R1R2： U/R1=1，2，3，4，5，6，7，8 U/R2

14、=1，2，3，4，5，6，7，8 问集合X=2，3，6，7，8关于R是否是精确的？如果不是，则求出相应的上近似、下近似、边界域和负区域。,由R=R1R2，可求出： U/R=U/R1，R2=1，2，3，4，5，6，7，8 因为X无法用U/R的等价类并集精确表示，所以X关于R是U上的一个粗糙集。 X的下近似集为： R_(X)=6，7，8 X的上近似集为： R-(X)=1，23，46，7，8=1，2，3，4，6，7，8 X的边界域： BNR(X)= R-(X)-R_(X)=1，2，3，4 X的负区域： NEGR(X)=U-R-(X)=5,定义9.13 设K=（U，R）是一个知识库，对于U中的两个集合

15、X和Y，当R_(X)= R_(Y)时，称集合X、Y为R下相等；当R-(X)= R-(Y)时，称集合X、Y为R上相等。 粗相等关系拓展了传统的相等关系，描述了任何不可分辨关系R的粗等价情况。,9.2.3 分类的近似度量,定义9.14 设K=（U，R）是一个知识库，对于U中的非空集合X，由等价关系R描述X的精确度定义为：,显然，0dR(X)1。 如果dR(X)=1，则称集合X相对于R是精确的，此时，X的R边界域为空，X为全部R可定义的。 如果dR(X)1，则称集合X相对于R是粗糙的。 如果dR(X)=0，则集合X是全部R不可定义的。,可用另一形式即X的R粗糙度rR(X)来定义X的不确定义，即：,X

16、的R粗糙度rR(X)与精确度dR(X)恰恰相反，它反映用R的类价类描述集合X的不完全程度。,【例9.6】设知识库K=（U，R），其中论域U=1，2，3，4，5，6，7，8，等价关系R为： U/R=1，4，8，2，5，7，3，6 计算以下集合的精确度和粗糙度。 （1）X1=1，4，5 （2）X2=3，5 （3）X3=3，6，8,其求解过程如下：,（1）对于集合X1=1，4，5，求得上、下近似如下： R-(X1)=1，4，82，5，7=1，2，4，5，7，8， R_(X1)= 则=0，rR(X1)=1- dR(X1)=1。,（2）对于集合X2=3，5，求得上、下近似如下： R-(X2)=2，5，7

17、3=2，3，5，7， R_(X2)=3 则，rR(X2)=1- dR(X2)=0.75。,（3）对于集合X3=3，6，8，求得上、下近似如下： R-(X3)=1，4，836=1，3，4，6，8， R_(X3)=3，6 则，rR(X3)=1- dR(X3)=0.25。,9.3 信息系统的属性约简,知识约简是粗糙集理论的核心内容之一。 众所周知，知识库中属性（知识）并不是同等重要的，甚至其中有些属性是冗余的。 所谓属性约简，就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的属性。,9.3.1 约简和核,定义9.15 设K=（U，R）是一个知识库，若rR，即r是R中的一个属性，如果有IN

18、D(R)=IND(R-r)或U/R=U/(R-r)成立，则称r为R中不必要的（或可约去的）；否则称r为R中必要的。 如果每一个rR都为R中必要的，则称R为独立的；否则称R为依赖的。,定义9.16 设K=（U，R）是一个知识库，若PR，P是独立的，且IND(P)=IND(R)，则称P是R的一个约简（Reduct），记为RED(R)。,定义9.17 设K=（U，R）是一个知识库，R可能有多种约简，R中所有必要属性组成的集合称为R的核（Core），记作CORE(R)。即CORE(R)=RED(R)。,【例9.7】有如表9.2所示的信息表I2，求它的所有约简和核。,从表中可求得： U/a=1，4，5，

19、2，8，3，6，7 U/b=1，3，5，6，2，4，7，8 U/c=2，5，1，7，8，3，4，6 则： U/a，b=1，2，8，3，4，5，6，7 U/b，c=1，2，3，4，5，6，7，8 U/a，c=1，2，3，4，5，6，7，8 U/R=R/a，b，c=1，2，3，4，5，6，7，8,考虑除掉属性a，则U/(R-a)= U/b，c=1，2，3，4，5，6，7，8，由于U/RU/(R-a)，所以属性a是不可省略的。 考虑除掉属性b，则U/(R-b)= U/a，c=1，2，3，4，5，6，7，8，由于U/RU/(R-b)，属性b是可省略的。 考虑除掉属性c，则U/(R-c)= U/a，b=

20、1，2，8，3，4，5，6，7，由于U/R=U/(R-c)，所以属性c是不可省略的。,则有RED(R)=a，c，CORE(R)=a，c。约简后的信息表如表9.3所示，两者的数据量不同，但分类能力是相同的。,属性约简,9.3.2 分辨矩阵求核,定义9.18 设I=（U，A）是一个信息系统，设U=x1，x2，xn，A=a1，a2，am，对应的分辨矩阵M=dij | i=1n，j=1m，其中dij定义如下：,dij=当i=j时 dij=ak当ij，且xi和xj在属性ak上取值不相同时,从中看到，dij是区分对象xi和xj的所有属性的集合。由于分辨矩阵M是一个nn的对称矩阵，通常仅考虑下三角或上三角部

21、分。,【例9.8】求如表9.2所示信息表的分辨矩阵M。,定义9.19 设I=（U，A）是一个信息系统，对于分辨矩阵M=dij | i=1n，j=1m，定义分辨函数f(M)如下：,也就是说，分辨函数f(M)表示为辨矩阵M中的所有元素的合取式。 分辨函数f(M)具有这样的性质：它的极小析取范式中的所有合取式是属性集A的所有约简。 换句话说，约简是满足能区别由整个属性集区别的所有对象的属性的极小子集。,而核是分辨矩阵M中所有单个元素组成的集合，即：,CORE(A)=aA | dij=a且xi、xjU,【例9.9】对于如表9.2所示的信息表，采用分辨矩阵的方法求它的所有约简和核。,分辨矩阵M，其中的单

22、个元素为a、c，所以有 CORE(A)=a，c 其分辨函数 f(M)=(abc)(ac)(bc)(abc)=ac。 所以只有一个约简a，c。,有关信息系统的属性约简和属性值约简算法这里不再介绍，主要在后面讨论决策表的属性约简和属性值约简算法。,9.4 决策表及其属性约简,9.4.1 决策表及相关概念,定义9.20 设I=（U，A，V，f）是一个信息系统，又设C、DA是属性集A的两个子集，分别称C和D为A的条件属性集和决策属性集，这样将I改写成T=（U，C，D，V，f）或简写为T=（U，C，D），则T称为决策表。,也就是说，在信息系统上指定条件属性集C和决策（类别或结论）属性集D，这样就构成了决

23、策表。IND(C)的等价类称为条件类，IND(D)的等价类称为决策类，它们都是U的知识。,定义9.21 给定决策表T=(U，C，D)，定义D的C正域POSC(D)为：,实际上，D的C正域就是等价类U/D关于C的正域，即U/C表达的知识能够确定地划入U/D类的对象的集合，它可由所有包含于D的C分类的基本集合的并集来计算。,【例9.10】对于如表9.4所示的决策表T1，C=头疼，肌肉疼，体温，D=流感，求POSC(D)。,U/D=1，4，5，2，3，6，设X1=1，4，5，X2=2，3，6 U/C=1，2，3，4，5，6 C_(X1)=145=1，4，5，即U/C的类价类准确地分类 到X1中的对象

24、集合 C_(X2)=236=2，3，6，即U/C的类价类准确地分类 到X2中的对象集合 则POSC(D)= C_(X1)C_(X2)=1，2，3，4，5，6=U。,定义9.22 给定决策表T=(U，C，D)，令：,称知识D依赖于知识C的依赖度为k。 依赖度k反映了根据知识C将对象分类到知识D的基本概念中去的能力：,当k=1时，称知识D完全依赖于知识C，记为C D。 当0k1时，称知识D部分依赖于知识C。 当k=1时，称知识D完全独立于知识C。,【例9.11】对于如表9.4所示的决策表，求依赖度rC(D)。,上例已求出POSC(D)=U，所以,定义9.23 设T = ( U，C，D) 是一个决策

25、表，如果有： POSC(D)=U 则决策表T是协调的或一致的；否则称T为不协调的决策表。,对于不协调的决策表，不能由条件属性导出结论属性之间的关系，应将其分解为完全协调和完全不协调的两个决策表。,定义9.24 设T = ( U，C，D) 是一个协调的决策表，属性rRC，R是条件属性集C的一个子集。如果r满足条件：,POSR(D)=POSR-r(D),那么属性r是条件属性子集R中相对于决策属性集D的不必要属性或冗余属性，否则称属性r是R中相对于决策属性D的必要属性。 如果RC且R中的每一个属性r都是R中相对于决策属性集D的必要属性，那么R称为相对于决策属性集D是独立的；否则，R称为相对于决策属性

26、集D是依赖的。,定义9.25 设T = ( U，C，D) 是一个协调的决策表，RC且R，如果有： （1）POSR(D)=POSC(D)。 （2）R相对于决策属性集D而言是独立的。 那么R是条件属性集C相对于决策属性集D而言的一个约简。,条件属性集合C中的所有相对于决策属性集D的必要属性的集合称为条件属性集合C相对于决策属性集D的核，记作COREC(D)。 与信息系统一致，由决策表确定的核是唯一的，但约简可能不止一个，根据约简和核的定义可知，约简和核之间存在如下关系： COREC(D)=REDC(D),ROSE2是波兰Poznan科技大学开发的一个粗糙集数据分析器，该系统提供了数据预处理（数据离

27、散化、缺省值补齐）、属性约简、规则生成和有效性分析的多种算法。 下面通过一个示例说明由用户设置的决策表来产生核、约简和规则的过程。,设置条件属性a,设置决策属性e,一个决策表,求出的核,求出的所有约简,产生决策表的规则,9.4.2 决策表的属性约简算法,1. 一般属性约简算法,该算法是一种最简单的粗糙集属性约简算法，检查条件属性集C是否满足独立性条件。 如果在C中发现不满足独立性条件的属性，则删除该属性，并对删除该属性后所得的条件属性子集重新检查独立性条件，直至条件属性子集中的所有属性均满足独立性条件为止。,输入：决策表T=（U，C，D） 输出：决策表T的一个相对约简R 方法：其过程描述如下：

28、,B=C，R=; for (rB-R) if (POSB-r(D)=POSB(D)/说明属性r相对决策属性D是不必要的 B=B-r; else/说明属性r相对决策属性D是必要的 R=Rr; if (B=R) brerk;/B=R时退出循环，算法结束 ,【例9.14】设决策表T4=（U，C，D）如表9.9所示。采用一般属性约简算法求属性约简R。,令B=C=a，b，c，d，R=。 在B-R=a，b，c，d中选择一个属性，假如选取属性d，求得： U/B=1，2，3，4， U/D=1，2，3，4， U/(B-d)=U/a，b，c=1，2，3，4， POSB(D)=1，2，3，4， POSB-d(D)=

29、1，2，3，4， 所以有：POSB(D)= POSB-d(D) 则：B=B-d=a，b，c，R=。, 在B-R=a，b，c中选择一个属性，假如选取属性b，求得： U/B=U/a，b，c=1，2，3，4， U/D=1，2，3，4， U/(B-b)=U/a，c=1，2，3，4， POSB(D)=1，2，3，4， POSB-b(D)=1，2，3，4， 所以有：POSB(D)= POSB-b(D) 则：B=B-b=a，c，R=。, 在B-R=a，c中选择一个属性，假如选取属性a，求得： U/B=U/a，c=1，2，3，4， U/D=1，2，3，4， U/(B-a)=U/c=1，2，3，4， POSB(

30、D)=1，2，3，4， POSB-a(D)=1， 所以有：POSB(D) POSB-a(D) 则：B=a，c，R=Ra=a。, 在B-R=c中选择一个属性，只能选取属性c，求得： U/B=U/a，c=1，2，3，4， U/D=1，2，3，4， U/(B-c)=U/a=1，3，4，2， POSB(D)=1，2，3，4， POSB-c(D)=2， 所以有：POSB(D) POSB-c(D) 则：B=a，c，R=Rc=a，c。 此时B=R，算法结束，R=a，c是决策表的一个约简。,2. 基于Pawlak属性重要度的属性约简算法,为了度量某个条件属性相对于决策属性的重要性，或者说是该属性在整个决策表中

31、的作用，粗糙集理论采用的方式是依次从决策表中删除该属性，然后观察该属性被删除之后，整个决策表的分类能力有没有发生变化，发生变化的幅度是多大。 如果变化越大，则说明，所删除的属性对原始决策表就越重要，反之，如果变化很小，说明所删除属性对原始决策表而言就不是很重要。,定义9.26 设T = ( U，C，D) 是一个协调的决策表，rC，该属性对条件属性全集C相对于决策属性D的重要度定义为：,BC，C-B，条件属性对条件属性集B相对于决策属性D的重要度定义为：,下面是基于Pawlak属性重要度的决策表的属性约简算法：,输入：决策表T=（U，C，D） 输出：决策表T的一个相对约简B 方法：其过程描述如下

32、：,计算C相对于D的核COREC(D); B=COREC(D); while (POSB(D)POSC(D) for (对于C-B中的属性ci) 计算： 求cm=arg max sig(ci，B；D); 若同时存在多个属性满足最大值，则从中选取一个与B的属性值组合数最少的属性作为cm; B=Bcm; ,【例9.15】对于如表9.9所示的决策表T4，采用基于Pawlak属性重要度的属性约简算法求相对属性约简R。 求解过程如下：, 计算核。 U/C=1，2，3，4 U/D=1，2，3，4 U/(D-a)=U/b，c，d=1，2，3，4 U/(D-b)=U/a，c，d=1，2，3，4 U/(D-c)

33、=U/a，b，d=1，4，2，3 U/(D-d)=U/a，b，c=1，2，3，4 POSC(D)=1，2，3，4 POSC-a(D)= 1，2，3，4= POSC(D) POSC-b(D)= 1，2，3，4= POSC(D) POSC-c(D)= 2，3POSC(D) POSC-d(D)= 1，2，3，4= POSC(D) 所以条件属性c是决策表的核值属性，即COREC(D)=c。, 令B=COREC(D)=c，POSB(D)=1POSC(D)，对于C-B=a，b，d中的每个属性ci有其重要度：,U/D=1，2，3，4 U/B=1，2，3，4 U/a，c=1，2，3，4 U/b，c=1，3，2

34、，4 U/d，c=1，2，3，4 POSB(D)=1 POSBa(D)=POSa，c(D)=1，2，3，4 POSBb(D)=POSb，c(D)=1，3 POSBd(D)=POSd，c(D)=1，2，3，4,现在取cm=arg max sig(ci，B；D)，可选的属性有a和d，所以B=a，c或d，c，而POSa，c(D)=POSC(D)或者，POSd，c(D)=POSC(D)均成立，所以算法结束。 输出的约简为B=a，c或d，c。,3. 基于分辨矩阵的决策表属性约简算法,定义9.27 设T = ( U，C，D) 是一个协调的决策表，设U=x1，x2，xn，A=a1，a2，am，对应的分辨矩阵

35、M=dij | i=1n，j=1m。由于分辨矩阵M是一个nn的对称矩阵，通常仅考虑下三角或上三角部分。其中dij定义如下：,dij=ak当xi和xj在D上属性值不相同且xi和xj在 属性ak上取值不相同时 dij=当xi和xj在D上属性值不相同且xi和xj在 C上所有属性值相同时 dij=-当xi和xj在D上所有属性值均相同时,【例9.16】对于如表9.9所示的决策表T4，求其分辨矩阵M。,定义9.28 设T = ( U，C，D) 是一个协调的决策表，对于分辨矩阵M=dij | i=1n，j=1m，定义分辨函数f(M)如下：,也就是说，分辨函数f(M)表示为辨矩阵M中的所有元素的合取式。分辨函

36、数f(M)具有这样的性质：它的极小析取范式中的所有合取式是C相对于D的所有约简。 而核是分辨矩阵M中所有单个元素组成的集合，即： COREC(D)=aC | dij=a且xi、xjU,下面给出基于分辨矩阵的决策表属性约简算法：,输入：决策表T=（U，C，D） 输出：决策表T的所有相对约简REDC(D) 方法：其过程描述如下：,计算决策表T的分辨矩阵M; 对于分辨矩阵M中所有取值非空集合的元素dij（dij且dij-），建立相应的析取值Lij; 对所有析取式Lij进行合取运算，得到一个合取范式L，即 将合取范式L转换为析取范式形式，得 输出REDC(D)=Lk;,【例9.17】对于如表9.9所示

37、的决策表T4，采用分辨矩阵的方法求它的所有相对属性约简和核。 上例已求该信息表的分辨矩阵M，其中的单个元素只有c，所以有COREC(D)= c。 其分辨函数f(M)=(bc)c(abd)(ad) =c(ad)=(ca)(cd)。 所以决策表T4有两个相对约简即a，c和c，d。,4. 基于信息增益的属性约简算法,该算法以信息增益值作为启发信息，每次选取信息增益值最大的条件属性，直到找到一个约简为止。,输入：决策表T=（U，C，D） 输出：决策表T的一个相对约简B 方法：其过程描述如下：, 计算C相对于D的核COREC(D); 令B= COREC(D) ，如果POSB(D)=POSC(D)，转;

38、任意属性rC-B，计算属性信息增益G(C，r)=E(C)-E(C，r)， 求得G(C，r最大的属性r; 若同时存在多个属性满足最大值，则从中选取一个与B的属性值组合数最少的属性作为r; 令B=Br; 如果POSB(D) POSC(D)，转；否则转; 输出，算法结束。,9.5 决策表的值约简及其算法,属性约简只是在一定程度上去掉了决策表中冗余属性，还是没有充分去掉决策表中的冗余信息。在判断某个对象属于某类时，其属性的取值不同，对分类产生的影响也不同。 例如，判断人的体形（瘦、中、胖）时，体重是主要属性。但若体重属性值为75kg时，此人的体形要结合其身高、性别等属性才能确定； 如果体重属性值为16

39、0kg时，几乎肯定其体形为胖，这时身高、性别已不重要，也就是说身高、性别的属性值是冗余的。 值约简是属性值约简的简称，其目标就是删除这些冗余的属性值并产生决策表的决策规则。,9.5.1 决策规则及其简化,定义9.29 设决策表T=（U，C，D）是协调的，对于xU，通常将决策规则rx描述成如下形式： rx： rx|Crx|D或 其中和分别称为决策规则rx的因（或前件）和果（或后件），也叫做CD决策规则，简称为规则。 为了简便，在、中，基本项用av表示属性a取值为v，而、是由基本项逻辑与/或组成的。,定义9.30 设是决策表T上的一条决策规则，条件属性值av（aC，av表示存在a=v的基本项）是可

40、被约去的（或可省略的，或av是冗余的），当且仅当()(-av)；否则称条件属性值av在该规则是必要的。,一条规则的某个条件属性值可被约去当且仅当约去后仍然保持规则的一致性。 所谓规则的一致性，是指条件属性值均相同的规则，其结论属性值也必须相同；否则称为不一致或冲突。,例如，有表9.12所示的决策表T6，对于第1条规则a1b0c2d1e1，其中a1是不必要的，因为删除a1后，b0c2d1e1是一致的，也就是说，a1b0c2d1e1b0c2d1e1。,没有冲突,定义9.31 规则中所有必要的条件属性值构成的集合称为该规则的核，记为CORE()。,【例9.19】对于如表9.12所示的决策表T6，求所

41、有规则的核值。 利用定义9.29求决策表T6中所有规则核值的过程如下。,产生如下决策规则：,（1）a1b0c2d1e1 （2）a2b1c0 d1e0 （3）a2b1c2 d0e2 （4）a1b2c2 d1e1 （5）a1b2c0 d0e2,求决策规则的核,（1）a1b0c2d1e1 有a1c2 d1e1 ，a1b0 d1e1 ，b0c2 d1e1，核为空。,除去属性b,除去属性c,除去属性a,（2）a2b1c0 d1e0,a2b0 d1e0 ，b1c0 d1e0 ，a2b1 d1e0 ，核为c0,除去属性b,除去属性a,除去属性c,最后得到仅包含决策规则的核值如下：,定义9.32 对于决策表T

42、=（U，C，D），xU，aCD，定义类集xa为U中所有a属性值与x对象a属性值相同的对象集合。若B CD，则,例如，对于表9.12所示的决策表T6，1a=1，4，5，1c=1，3，4，则1a，c=1，4，51，3，4=1，4。,定义9.33 对于决策表T=（U，C，D），设rx是一条进行属性约简后的规则，条件属性集C的等价类xC中： 任何最少属性a的等价类xa的交集相应决策类xD 则由此而得到的最小条件属性a组成的相应于rx的新规则rx称为rx的一个规则约简。,对于第一条：决策类1d,e=1,4; 1a=1,4,5，1b=1,4,5，1c=1,3,4 显然：1a 1d,e，1c 1d,e， 但

43、有：1b 1d,e，1a 1b=1,4 1d,e 所以得到两条约简的决策规则： 1：b0 d1e11：a1c2 d1e1,【例9.20】对于如表9.12所示的决策表T6，求所有规则的约简。,得到所有约简的决策规则：,9.5.2 决策规则的极小化,在前面介绍的方法产生的规则中，有些规则不是必要的，更确切地说，和相同决策类相结合的一些过剩的规则应该消去，而不影响规则的决策能力。,定义9.34 记F为所有具有后件的基本规则的集合，用P表示F中规则的所有前件的集合。 如果P=(P-)，则基本规则是可约去的，其中P表示P中所有基本项的析取，也可以看成是满足P中基本项条件的记录的并集；否则该规则是不能被约

44、去的。 如果F中所有规则都是不能被约去的，则它称为独立的，也就是极小化规则约简。,【例9.21】对于如表9.15所示的决策表T7，其中，C=a，b，c，d，D=e，求其极小规则约简。, 先通过上一节介绍的属性约简算法求出其属性约简REDC(D)=a，b，d。则删除条件属性c及该列后得到如表9.16所示的决策表T71。,r1：a1b0d1e1 r2：a1b0d0e1 r3：a0b0d0e0 r4：a1b1d1e0 r5：a1b1d2e2 r6：a2b1d2e2 r7：a2b2d2e2, 求决策表T71的所有规则的约简。它包含的规则如下：,考虑r1：a1b0d1e1，1e=1，2，1a=1，2，4

45、，5，1b=1，2，3，1d=1，4。有1a1b=1，21e，产生规则（1）a1b0e1；1b1d=11e，产生规则（1）b0d1e1，该规则的核=a1b0b0d1=b0。 考虑r3：a0b0d0e0，3e=3，4，3a=3，3b=1，2，3，3d=2，3。有3a3e，产生规则（3）a0e0。该规则的核为a0。 考虑r7：a2b2d2e2，7e=5，6，7，7a=6，7，7b=7，7d=5，6，7。有7a7e，产生规则（7）a2e2；7b7e，产生规则（7）b2e2；7c7e，产生规则（7）d2e2。显然该规则的核为空。,最后求出的所有规则的约简如表9.17所示。, 求极小规则约简 在9.17

46、中，共有3个决策类（e分别为1、0和2的类）。 对于e=1的类：,所以该类规则约简为：a1b0e1或b0d1a1d0e1。,对于e=0的类：,所以该类规则约简为：a0b1d1e0。,对于e=2的类：,所以该类规则约简为：d2e2。,最后得到以下两组极小规则约简：,a1b0e1 a0b1d1e0 d2e2,b0d1a1d0e1 a0b1d1e0 d2e2,归纳起来，利用属性约简后的决策表产生一组极小规则约简的算法如下：,输入：属性约简后的决策表T 输出：一组极小规则约简 方法：其过程描述如下：,（1）对决策表T中每个记录的每个条件属性a进行逐个考察，删除该记录的该属性值av，有3种可能的情况： 若产生冲突，说明该属性值是该记录的核，不能除去，恢复该属性值； 若未产生冲突，但决策表T中含有重复记录（在不考虑属性a时），说明删除该属性值不影响该记录的决策，可以删除该属性