粗糙集理论(武汉大学-李春葆)

1、第第9章章 粗糙集理论粗糙集理论 参考书：参考书：1 智能计算，曾黄麟，重庆大学出版社，智能计算，曾黄麟，重庆大学出版社，20042 苗夺谦等，粗糙集理论、算法与应用，清华大学苗夺谦等，粗糙集理论、算法与应用，清华大学出版社，出版社，2008n粗糙集理论是由波兰华沙理工大学粗糙集理论是由波兰华沙理工大学Pawlak教授于教授于20世纪世纪80年代初提出的一种研究不完整、不确定知识和数据的表达、年代初提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，它是一种刻画不完整性和不确定学习、归纳的理论方法，它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致、不完整等性

2、的数学工具，能有效地分析不精确、不一致、不完整等各种不完备的信息，还可以对数据进行分析和推理，从中各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。发现隐含的知识，揭示潜在的规律。n粗糙集在机器学习、决策支持系统、机器发现、归纳推理、粗糙集在机器学习、决策支持系统、机器发现、归纳推理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。数据库中的知识发现、模式识别等领域都得到了广泛的应用。n粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据库粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据库中不完整数据进行分析和学习方面取得了显著的成果，使得中不完整数据进行

3、分析和学习方面取得了显著的成果，使得粗糙集理论及数据挖掘的研究成为热点领域。最近几年，粗粗糙集理论及数据挖掘的研究成为热点领域。最近几年，粗糙集理论越来越受到众多研究人员的重视，它的应用研究得糙集理论越来越受到众多研究人员的重视，它的应用研究得到了很大的发展。到了很大的发展。 n粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。数据数据规则规则精确的数学方法精确的数学方法9.1粗糙集基本概念粗糙集基本概念 粗糙集理论是在经典集合论基础上发展而来的。粗糙集理论是在经典集合论基础上发展而来的。利用不确定性、不完整的经验知识进行推理。利用不确

4、定性、不完整的经验知识进行推理。知识库知识库9.1.1 知识和分类知识和分类 n知识是人类通过实践对客观世界的运动规律的认识，知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有是人类实践经验的总结和提炼，具有抽象和普遍抽象和普遍的特的特性。性。n从认知科学的观点来看，知识是从认知科学的观点来看，知识是人类对客观事物的分人类对客观事物的分类能力类能力，概念是事物类别的描述或者符号。知识是概，概念是事物类别的描述或者符号。知识是概念之间的关系和联系。任何一个物种都是由一些知识念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产来描

5、述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。生对物种的不同分类。1. 知识的分类表达形式知识的分类表达形式集合理论为描述世界中各种事件提供了一个十分集合理论为描述世界中各种事件提供了一个十分有用的基础，千差万别的事物都可以用集合论的有用的基础，千差万别的事物都可以用集合论的方法加以描述。方法加以描述。知识表达系统采用集合表达知识表达系统采用集合表达。知识分类知识分类利用事件不同的属性的知识描述，对利用事件不同的属性的知识描述，对事物可以产生不同的分类事物可以产生不同的分类。 定义，定义， 知识表达系统（知识库）知识表达系统（知识库）M可以形式化表达为可以形式化表达为四元组：四

6、元组：M=(U,A,V,f)，其中其中U为对象非空有限集合，称为论域；为对象非空有限集合，称为论域；A为属性的非为属性的非空有限集合，空有限集合，A=A1,A2,Am；V= Vi，Vi是属性是属性Ai的值域；的值域；f：UAV是一个信息函数，它为每个对象的每个属性赋是一个信息函数，它为每个对象的每个属性赋予一个信息值，即予一个信息值，即 a A，x U，f(x,a) Va。知识表达系统知识表达系统称为（或称为（或信息表信息表），其数据以关系表的），其数据以关系表的形式表示，关系表的行对应要研究的对象，列对应对象的形式表示，关系表的行对应要研究的对象，列对应对象的属性，对象的信息是通过指定对象的

7、各属性值来表达。属性，对象的信息是通过指定对象的各属性值来表达。一个信息表一个信息表 U颜色颜色R1形状形状R2大小大小R31红色红色圆形圆形小小2蓝色蓝色方形方形大大3红色红色三角形三角形小小4蓝色蓝色三角形三角形小小5黄色黄色圆形圆形小小6黄色黄色方形方形小小7红色红色三角形三角形大大8蓝色蓝色三角形三角形大大下面的表是一个信息表的例子，是一个玩具积木下面的表是一个信息表的例子，是一个玩具积木的集合。其中：的集合。其中：U=1,2,3,4,5,6,7,8，A=颜色颜色,形状形状,大小大小，V颜色颜色=红色红色,蓝色蓝色,黄色黄色，V形状形状=圆形圆形,方形方形,三角形三角形，V大小大小=大

8、大,小小。n定义定义 设设U,讨论的对象组成的有限集合，称为论域讨论的对象组成的有限集合，称为论域（Universe），对于论域中由等价关系划分出来的任意子集，对于论域中由等价关系划分出来的任意子集，都可以称为论域都可以称为论域U中的一个概念（中的一个概念（concept）或范畴）或范畴（category）。 为规范起见，认为空集必也是一个概念。论域为规范起见，认为空集必也是一个概念。论域U中的任中的任意概念族称为关于论域的抽象知识，它代表了对论域中个体意概念族称为关于论域的抽象知识，它代表了对论域中个体的分类，简称为的分类，简称为知识知识。1,3,7就是一个概念红色积木。就是一个概念红色积木

9、。1,3,7,2,4,5,6,8就是一个知识按颜色分类。就是一个知识按颜色分类。苹果苹果,梨梨,葡萄葡萄,柿子柿子,水果按味道水果按味道分类分类味甘味甘 味涩味涩 概念（共同特点）概念（共同特点）知识知识按颜色分类：按颜色分类：1，3，7：红色积木：红色积木2，4：蓝色积木：蓝色积木5，6，8：黄色积木：黄色积木按形状分类：按形状分类：1，5：圆形积木：圆形积木2，6：方形积木：方形积木3，4，7，8：三角形积木：三角形积木按大小分类：按大小分类：2，7，8：大积木：大积木1，3，4，5，6：小积木：小积木换言之，定义了三个等价关系换言之，定义了三个等价关系(即属性即属性)：颜色：颜色R1、形

10、状、形状R2和大和大小小R3，通过这样的分类，可以，通过这样的分类，可以得到以下三个等价类：得到以下三个等价类：U/R1=1,3,7，2,4，5,6,8U/R2=1,5，2,6，3,4,7,8U/R3=2,7,8，1,3,4,5,6这些等价类是知识库这些等价类是知识库K=(U,R1,R2,R3)中的初等概念。所以：中的初等概念。所以：基于基于R1的初等概念有：的初等概念有：1,3,7：红色积木：红色积木2,4：蓝色积木：蓝色积木5,6,8：黄色积木：黄色积木基于基于R2的初等概念有：的初等概念有：1,5：圆形积木：圆形积木2,6：方形积木：方形积木3,4,7,8：三角形积木：三角形积木基于基于

11、R3的初等概念有：的初等概念有：2,7,8：大积木：大积木1,3,4,5,6：小积木：小积木U颜色颜色R1形状形状R2大小大小R31红色红色圆形圆形小小2蓝色蓝色方形方形大大3红色红色三角形三角形小小4蓝色蓝色三角形三角形小小5黄色黄色圆形圆形小小6黄色黄色方形方形小小7红色红色三角形三角形大大8蓝色蓝色三角形三角形大大基本概念是初等概念的交集。基本概念是初等概念的交集。基于基于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

12、：蓝色三角形积木：蓝色三角形积木5,6,81,5=5：黄色圆形积木：黄色圆形积木5,6,82,6=6：黄色方形积木：黄色方形积木5,6,83,4,7,8=8：黄色三角形积木：黄色三角形积木基于基于R1,R3的基本概念有：的基本概念有：1,3,72,7,8=7：红色大积木：红色大积木1,3,71,3,4,5,6=1,3：红色小积木：红色小积木2,42,7,8=2：蓝色大积木：蓝色大积木2,41,3,4,5,6=4：蓝色小积木：蓝色小积木5,6,82,7,8=8：黄色大积木：黄色大积木5,6,81,3,4,5,6=5,6：黄色小积木：黄色小积木1,4,7找不出共找不出共同特点，不能称同特点，不能称

13、为一个概念。为一个概念。2. 不可分辨关系不可分辨关系 n在粗糙集理论中，在粗糙集理论中，“知识知识”被认为是一种分类的能力。被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它揭示出不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。论域知识的颗粒状结构。n假定关于论域的某种知识，并使用属性和属性值来描假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，如果两个对象述论域中的对象，如果两个对象(或对象集合或对象集合)具有相具有相同的属性和属性值，则它们之间具有同的属性和属性值，则它们之间具有不可分辨关系不可分辨关系。n定义定义设设R是非空集合是非空集合U

14、上的二元系，如果它是自反的、对上的二元系，如果它是自反的、对称的和可传递的，则称称的和可传递的，则称R为为U上的等价关系。若上的等价关系。若 则称则称x与与y有关系，记为有关系，记为 ；若若 ，则称，则称x与与y没有关系，记为没有关系，记为 。等价关。等价关系的一个重要特点是用它可以构成系的一个重要特点是用它可以构成U的一个划分。划分即是的一个划分。划分即是分类，将研究对象分成不同的类，这些类之间互不相交，分类，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。且每一对象均包含在某一类中。 xRy(x,y) R(x,y) R_x Ry根据等价关系的定义，同一等价类内的元素

15、是不可分根据等价关系的定义，同一等价类内的元素是不可分辨的，对信息的处理可以在等价类的粒度上进行，由此可辨的，对信息的处理可以在等价类的粒度上进行，由此可以达到对信息进行简化的目的。以达到对信息进行简化的目的。n定义定义 设设U是一个论域，是一个论域，R是是U上的等价关系，上的等价关系，U/R表示表示U上由上由R导出的所有等价类。导出的所有等价类。 表示包含元素表示包含元素xU的的R等价类。一个知识库就是一等价类。一个知识库就是一个关系系统个关系系统K，其中其中U是论域，是论域，P是是U上的一个等价类簇。上的一个等价类簇。如果如果 且且 ，则，则 （Q的所有等价类的交也的所有等价类的交也是一个

16、等价关系）称是一个等价关系）称Q为为不可分辨关系不可分辨关系,记作记作IND(Q)。QPQQIND(Q)=(x,y) | 所有的所有的a Q，f(x,a)=f(y,a)其中，其中，x、y为知识库中的记录或对象，为知识库中的记录或对象，Q是属性对是属性对应的等价类。应的等价类。简记为简记为U/QU/Q=xQ | x Ux元素的等价类元素的等价类U/R1,R3=1,3,2,7,4,5,6,8U/R2,R3=1,5,2,3,4,7,8,6U/R1,R2,R3=1,2,3,4,5,6,7,8不可分辨关系不可分辨关系U颜色颜色R1形状形状R2大小大小R31红色红色圆形圆形小小2蓝色蓝色方形方形大大3红色

17、红色三角形三角形小小4蓝色蓝色三角形三角形小小5黄色黄色圆形圆形小小6黄色黄色方形方形小小7红色红色三角形三角形大大8蓝色蓝色三角形三角形大大关系关系R的粒（初等概念），其他知识都是由粒构成的。的粒（初等概念），其他知识都是由粒构成的。如何求所有的等价关系的算法：如何求所有的等价关系的算法：设设U/a=x1,x2,xm， U/b=y1,y2,yn则：则：U/a,b=zk | zk=xi yj，i=1,m，j=1 ,n，zk U/a,b,c=U/a,b U/c或或U/c U/a,b设设a、b、c是属性。是属性。满足交换律满足交换律算法如何实现？算法如何实现？9.1.2集合近似与粗糙概念集合近似与

18、粗糙概念n给定论域给定论域U，一簇等价关系一簇等价关系R将将U划分为互不相交的基划分为互不相交的基本等价类本等价类U/R。n当能表达成某些基本等价类（初等概念）的并集时，当能表达成某些基本等价类（初等概念）的并集时，称为称为可定义的可定义的；否则称为；否则称为不可定义的不可定义的。R可定义集能可定义集能在这个知识库中被精确地定义，所以又称为在这个知识库中被精确地定义，所以又称为R精确集精确集。nR不可定义集不能在这个知识库中被精确定义，只能不可定义集不能在这个知识库中被精确定义，只能通过集合逼近的方式来刻画，因此也称为通过集合逼近的方式来刻画，因此也称为R粗糙集粗糙集 （Rough set）。

19、1. 集合的近似与粗糙集集合的近似与粗糙集UR1122334152647281初等概念：初等概念：U/R=1,4,8,2,5,7,3,6集合集合X=2,3,5,7是是R精确集。精确集。集合集合Y=1,7是是R粗糙集。粗糙集。不能由任何分类得到。不能由任何分类得到。2,5,7 3信息粒信息粒知识库的等价性知识库的等价性设设K=(U,P)和和K=(U,Q)为两个知识库，当：为两个知识库，当：U/P=U/Q则两个知识库则两个知识库K和和K是等价的。是等价的。若若U/P U/Q，则称知识，则称知识P比知识比知识Q更精细。更精细。含义是什么？含义是什么？n粗糙集的上近似集粗糙集的上近似集 （UpperA

20、pproximation）和下近）和下近似集（似集（LowerApproximation）来近似地定义粗糙集。）来近似地定义粗糙集。n粗糙集理论引入上近似和下近似等概念来刻画知识粗糙集理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性。的不确定性和模糊性。 2. 上、下近似集上、下近似集定义定义设集合设集合X U，R是一个等价关系，并且有：是一个等价关系，并且有：U/R=y1,y2,yn，则：，则： l集合集合X的的R下近似集：下近似集：R_(X)=yi U | IND(R):yi Xl集合集合X的的R上近似集：上近似集：R(X)=yi U | IND(R):yiXlX的的R边界域：边界

21、域：BNR= R(X)- -R_(X)lX的的R正域：正域：POSR(X)=R_(X)l为为X的的R负域：负域：NEGR=U- -R(X)R(X)R(X)下近似、正域：表示下近似、正域：表示X划入划入U/R的初等范畴的情况。或的初等范畴的情况。或者用者用U/R的初等范畴表示的初等范畴表示X的情况。的情况。设设 X =x1,x4,x6，则，则R_(X)=x1,x6R(X)=x1,x3,x4,x6BNR(X)=x3,x4U- -R(X)=x2,x5,x7X集合集合是粗糙的是粗糙的,因为其边界不因为其边界不为空为空。 U Age LEMS Walkx 16-30 50 yes x2 16-30 0

22、no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no设设R=Age,LEMSU/R=x1,x2,x3,x4,x5,x7,x6分类知识分类知识yesyes/nonox1,x6x3,x4x2, x5,x7R_(X)R(X)X=x | Walk=yes=x1,x4,x6U集合集合U/RR : 属性子集属性子集R_()R()- -X所有分类都是相对所有分类都是相对R而言的，而言的，U/R或或R就是一种知识。就是一种知识。IND(R)n例如，设论域例如，设论域 ，U上的一族等价关系

23、上的一族等价关系R=R1,R2,R1和和R2是两个等价关系。根据这两个等价关系是两个等价关系。根据这两个等价关系可以将论域可以将论域U进行划分：进行划分：n 和和 U/R1中的中的 ，代表，代表 的等价类。的等价类。n论域论域U被被R划分的基本等价类为划分的基本等价类为: n集合集合 是是U上的一个子集。则上的一个子集。则X无法用基本等价无法用基本等价类类U/R的并集精确表示，所以的并集精确表示，所以X是是U上的一个上的一个粗糙集合粗糙集合。故。故有有:nX的下近似集为的下近似集为: ；nX的上近似集为的上近似集为: ；nX的负区域的负区域: 。12345678U=e ,e ,e ,e ,e

24、,e ,e ,e 212345678U/R =e,e ,e ,e ,e ,e ,e ,e1234e ,e ,e ,e 11 Re12345678U/R =e ,e ,e ,e ,e ,e ,e ,e 23678X=e ,e ,e ,e ,e 678Pos(X)=R(X)=e ,e ,e 12345678R(X)=e,e ,e ,e ,e ,e ,e ,e R5NEG (X)=e 112345678U/R =e ,e ,e ,e ,e ,e ,e ,e 定理定理（1）X是精确的，当且仅当是精确的，当且仅当R(X)=R_(X)（2）X是粗糙的，当且仅当是粗糙的，当且仅当R(X) R_(X)集合集合

25、X=2,3,5,7是是R精确集。精确集。集合集合Y=1,7是粗糙集。是粗糙集。如何如何计算？计算？Ua1122334152647281U/R= 1,4,8,2,5,7,3,6R(X)=yi U | IND(R):yiX=y2y3=2,3,5,7R_(X)=yi U | IND(R):yi X= y2y3=2,3,5,7NEGR(X)=，所以，所以X是精确的。是精确的。IND(R)y1 y2 y3 y4R(Y)=yi U | IND(R):yiY=y1y2=1,4,8,2,5,7R_(X)=yi U | IND(R):yi X= NEGR(X) ，所以，所以X是粗糙的。是粗糙的。R=a定理：定理

26、：（1）R_(X) X R(X)（2）R(X Y)=R(X) R(Y)（3）R_(XY)=R_(X) R_(Y)（4）X Y R_(X) R_(Y)9.1.3 集合近似及分类近似的度量集合近似及分类近似的度量定义定义，由等价关系，由等价关系R描述集合描述集合X的的近似精度近似精度定义为定义为:| )(| )(|)(XRXRXdRX相对相对R的的粗糙度粗糙度定义为定义为: rR(X)=1- -dR(X) 例如，设某知识库例如，设某知识库K=(U,R),其中其中U=x1,x2,.,x8,一一个等价关系个等价关系R定义分类对象的等价类如下定义分类对象的等价类如下:y1=x1,x4,x8,y2=x2,

27、x5,x7,y3=x3,y4=x6对于集合对于集合X1=x1,x4,x5,则则: dR(X1)=0/6=0，rR(X1)=1。表示根据表示根据R的基本集合描述集合的基本集合描述集合X1的近似精度为的近似精度为0，粗，粗糙度为糙度为1。对于集合对于集合X2=x3,x5,则则: dR(X2)=1/4，rR(X2)=3/4。表示根据表示根据R的基本集合描述集合的基本集合描述集合X2的近似精度为的近似精度为0.25，粗糙度为粗糙度为75%。9.2.1. 知识的简化知识的简化定义定义，给定知识库，给定知识库K=(U,R)，定义一个等价关系，定义一个等价关系R，有属性有属性r R，若存在：，若存在：IND

28、(R)=IND(R- -r)称属性称属性r为为R中可省略的。中可省略的。对于任一对于任一r R，若，若R不可省略，则称不可省略，则称R是独立的。是独立的。9.2 知识库的简化知识库的简化表示删除属性表示删除属性r，不影响记录之间，不影响记录之间的区分（分辨）。的区分（分辨）。Uabc11122231331341335121642374328232一个知识表一个知识表除掉属性除掉属性b：U/R=1,2,3,4,5,6,7,8U/R-b)=1,2,3,4,5,6,7,8U/R等于等于U/R-b)，属性属性b是可省略的是可省略的定义，定义，对于属性子集对于属性子集P R，若存在，若存在Q=P- -r

29、，且且IND(Q)=IND(P)，且，且Q为最小子集，则为最小子集，则Q称为称为P的的简化，用简化，用red(P)表示。表示。一个属性集合一个属性集合P可能有多种简化。可能有多种简化。P中所有简化属性集中都包含的不可省略关系的中所有简化属性集中都包含的不可省略关系的集合，即简化集集合，即简化集red(P)的交称为的交称为P的核的核。记作。记作core(P)。core(P)= red(P)Uabc11122231331341335121642374328232一个知识表一个知识表除掉属性除掉属性a：Ubc112231313433521623732832U/R=1,2,3,4,5,6,7,8U/R

30、- -a)=1,2,3,4,5,6,7,8U/R不等于不等于U/R-a),属性属性a是不可省略的是不可省略的Uac112221333413511643742822除掉属性除掉属性b：U/R=1,2,3,4,5,6,7,8U/R- -b)=1,2,3,4,5,6,7,8U/R等于等于U/R- -b),属性属性b是可省略的是可省略的Uab111223331413512642743823除掉属性除掉属性c：U/R=1,2,3,4,5,6,7,8U/R- -c)=1,2,8,3,4,5,6,7U/R等于等于U/R-c),属性属性c是不可省略的是不可省略的则：则： redR=a,c，core(R)=a,

31、c。n核核的概念具有两方面的意义的概念具有两方面的意义: （1）因为核包含于所有约简之中，所以核可以作为所）因为核包含于所有约简之中，所以核可以作为所有约简的计算基础。有约简的计算基础。 （2）核在知识约简中是不能消去的特征集合。）核在知识约简中是不能消去的特征集合。 可以直接由可以直接由分辨矩阵分辨矩阵来求取系统的核集来求取系统的核集Pc。不失一般不失一般性性, 假定系统假定系统T 对于属性集对于属性集P 是可分辨的。则系统的核集是可分辨的。则系统的核集由以下定理确定。由以下定理确定。分辨矩阵定义：分辨矩阵定义：设设U=x1,x2,xn，分辨矩阵，分辨矩阵D=dijdij=当当i=j时时ak

32、当当ij，且，且xi和和xj在属性在属性ak上不相同时上不相同时分辨函数分辨函数f(D)=所有非空项的合取所有非空项的合取求出最简合取范式，得到所有属性约简，求出最简合取范式，得到所有属性约简，Uabc11122231331341335121642374328232D=1 2 3 4 5 6 7 8 abc ac bc bc abc ab ab abc ac ab abc ac c ab abc ab abc abc bc ab ac ac ac abc abc bc abc a利用分辨矩阵求核：利用分辨矩阵求核：f(D)=(abc) (ac) (bc) (abc) =ac。core(R)=a

33、,c。一个属性约简一个属性约简核是分辨矩阵中所有单个元素组成的集合。核是分辨矩阵中所有单个元素组成的集合。12345678约简的含义约简的含义Uabc11122231331341335121642374328232Uac112221333413511643742822等价等价例如，一个信息表如下：例如，一个信息表如下：Uabcd1012021202310104210151102分辨矩阵：分辨矩阵：1234512abcd3abcbcd4acdabdabcd5acdbbcdadf(D)=(abcd) (abc) (acd)(acd) (bcd)(abd)b (abcd)(bcd) ( ad) =(

34、a b) (b d) 两个约简两个约简a,b和和b,d，核为，核为b。求解求解f(D)可以得到所有可以得到所有的约简和核的约简和核NP问题，问题，即即m个属性其时间复个属性其时间复杂度为杂度为O(2m)。9.3决策表决策表 决策表决策表包含了某一领域的大量数据，是领域的样本包含了某一领域的大量数据，是领域的样本数据库。它记录了大量样本的属性值和决策情况，是数据库。它记录了大量样本的属性值和决策情况，是领域知识的载体。领域知识的载体。知识获取的目的就是要通过分析这个实例库来得到知识获取的目的就是要通过分析这个实例库来得到该领域中有用的、规律性知识。决策表在决策应用中该领域中有用的、规律性知识。决

35、策表在决策应用中有十分重要的地位，可用于表达绝大多数决策问题。有十分重要的地位，可用于表达绝大多数决策问题。对于决策表，最重要的是决策规则的生成。对于决策表，最重要的是决策规则的生成。数据库数据库决策表决策表规则规则在信息表（知识库）上指定条件属性集合在信息表（知识库）上指定条件属性集合C和和结论（决策）属性集合结论（决策）属性集合D，这样就构成了，这样就构成了决策表决策表。利用粗糙集理论进行数据挖掘的过程利用粗糙集理论进行数据挖掘的过程决策表决策表决策表决策表规则规则属性约简属性约简值约简值约简9.3.1 知识的相对简化知识的相对简化一个分类相对另一个分类的正域。一个分类相对另一个分类的正域

36、。定义定义，给定决策表，给定决策表T=(U,R)，等价关系，等价关系R的子集的子集C和和D，定义，定义D的的C正域正域POSC(D)为：为： POSC(D)=C(X)， XU/DU的所有的所有D分类（分类（U/D）划入到）划入到U的的C分类（分类（U/C）的情况。的情况。Uabc11122231331341335121642374328232一个决策表：一个决策表：设设C=a,b，D=c，求求POSC(D)=?U/D=1,7,8,2,5,3,4,6U/C=1,2,8,3,4,5,6,7R_(1,7,8)=1,7R_(2,5)=5R_(3,4,6)=3,4,6POSC(D)=1,753,4,6

37、=1,3,4,5,6,7 POSC(D)的含义是什么？的含义是什么？U对于属性集合对于属性集合D有一个分类有一个分类U/C。U对于属性集合对于属性集合C有一个分类有一个分类U/D。POSC(D)表示这两种分类之间的关系。表示这两种分类之间的关系。表示表示U/D的分类在的分类在U/C中的不确定性。中的不确定性。如果如果POSC(D)=U，表示两种分类是一致的。，表示两种分类是一致的。U/CU/DPOSC(D)U/C、U/D均为知识，知识之间通过均为知识，知识之间通过POSC(D)关联，构成一种知识体系结构。关联，构成一种知识体系结构。知识知识5知识知识6知识知识7知识知识8知识知识2知识知识3知

38、识知识4知识知识1知识体系结构知识体系结构粒计算的研究方粒计算的研究方向之一向之一定义定义C D依赖性度量：依赖性度量：| )(|)(UDPOSDrkCC设设(U,CD)是一个决策表。是一个决策表。9.3.2 知识的依赖性和属性的重要性知识的依赖性和属性的重要性k可以看成可以看成D和和C之间依赖性的量度，也可解释为对对之间依赖性的量度，也可解释为对对象的分类的能力。象的分类的能力。当当k=1时，则时，则U的全部记录都可以通过知识的全部记录都可以通过知识C划入划入U/D的初始概念。的初始概念。当当k1时，只有属于正域的记录可以通过知识时，只有属于正域的记录可以通过知识C划入划入U/D的初始概念。

39、的初始概念。一个汽车决策表：一个汽车决策表：U条件属性条件属性决策属性决策属性类型类型a机型机型b颜色颜色c速度速度d加速加速e1中中柴油柴油灰色灰色中中差差2小小汽油汽油白色白色高高极好极好3大大柴油柴油黑色黑色高高好好4中中汽油汽油黑色黑色中中极好极好5中中柴油柴油灰色灰色低低好好6大大混合混合黑色黑色高高好好7大大汽油汽油白色白色高高极好极好8小小汽油汽油白色白色低低好好U/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8C_(1)=，C_(2,7)=7，C_(3,6)=3,6C_(4)=4，C_(5,8)=，POSC(D)=73,64=3,4,6,7k=|POS

40、C(D)|/|U|=4/8=0.5。 两者之间的依赖度为两者之间的依赖度为50。也就是说，由类型、机型和颜色可以也就是说，由类型、机型和颜色可以50来确定速度来确定速度和加速属性。和加速属性。定义定义，属性，属性a的重要性度量：的重要性度量：Ia(S)=rR(S)-rR-a(S) ，其中，其中S为属性为属性a的分类结果的分类结果设设(U,CD)是一个决策表。是一个决策表。一个决策表如下，求属性一个决策表如下，求属性a、b、c的重要性？的重要性？U条件属性条件属性决策属性决策属性abcde122100211301331211422210521112633211732301812312U/a,b,

41、c=1,2,3,4,5,6,7,8，U/d,e=1,2,7,3,6,4,5,8，POSC(D)=1,2,3,4,5,6,7,8，POSC-a(D)=1,2,3,4,5,6,7,8POSC-b(D)=3,4,6,7，POSC-c(D)=2,3,5,6,7,8，Ia(D)=8/8- -8/8=0；Ib(D)=8/8- -4/8=0.5；Ic(D)=8/8- -6/8=0.125。属性属性a最不重要，可以删除，属性最不重要，可以删除，属性b最重要。最重要。9.3.3 属性约简、核集的求取属性约简、核集的求取 n所谓所谓属性约简（决策表）属性约简（决策表），就是在保持知识库分类能，就是在保持知识库分类

42、能力不变的条件下，删除其中不相关或不重要的属性。力不变的条件下，删除其中不相关或不重要的属性。n一个属性集合可能有多个约简。一个属性集合可能有多个约简。n属性约简的目标就是要从条件属性集合中发现部分必属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属策属性的分类一致，即和所有条件属性相对于决策属性性D有相同的分类能力。有相同的分类能力。设设T = ( U , C D) 是

43、决策表，如果有：是决策表，如果有：POSC(D)=U则决策表则决策表T是协调的或一致的；否则称是协调的或一致的；否则称T为不协调的决为不协调的决策表。策表。对于不协调的决策表，不能由条件属性导出结对于不协调的决策表，不能由条件属性导出结论属性之间的关系，应将其分解为完全协调和完全论属性之间的关系，应将其分解为完全协调和完全不协调的两个决策表。不协调的两个决策表。1. 协调的决策表协调的决策表U条件属性条件属性结论属性结论属性头疼头疼肌肉疼肌肉疼体温体温流感流感1是是是是正常正常否否2是是是是高高是是3是是是是很高很高是是4否否是是正常正常否否5否否否否高高否否6否否是是很高很高是是设设C=头疼

44、头疼,肌肉疼肌肉疼,体温体温，D=流感流感U/流感流感=1,4,5,2,3,6U/头疼头疼,肌肉疼肌肉疼,体温体温=1,2,3,4,5,6POSC(D)=C(1,4,5) C(2,3,6) =1,4,5 2,3,6=1,2,3,4,5,6U该决策表是协调的。该决策表是协调的。定义定义，设，设T = ( U , C D) 是决策表，如果去掉条件属性是决策表，如果去掉条件属性c，得到的表得到的表T1 = (U , Cc , D) 与表与表T 相比，有：相比，有：POSC-c( D) = POSC(D)则称条件属性则称条件属性c是关于是关于D可省的，否则称条件属性可省的，否则称条件属性c是关于是关于

45、D 不可省的。不可省的。决策表决策表T决策表决策表T1删除条件属性删除条件属性c并并合并记录合并记录2. 条件属性的可省略性条件属性的可省略性n定义定义，如果决策表，如果决策表T中每个条件属性都是关于中每个条件属性都是关于D 不可不可省的，则称条件属性集省的，则称条件属性集C 是关于是关于D独立的，否则称独立的，否则称C 是关于是关于D 依赖的。依赖的。n定义定义，决策表，决策表T = (U, C D) 中条件属性集中条件属性集C 的一个的一个子集子集B 是关于是关于D 独立的，并且独立的，并且POSB(D) = POSC(D)，则称则称B 是是C 的一个的一个D属性约简。属性约简。Uabcd

46、e110220201112320011411022510201622011721112801101一个决策表：一个决策表：C=a,b,c， D=d,eU/C=1,5,2,8,3,4,6,7U/D=1,2,7,3,6,4,5,8POSC(D)=3,4,6,7rC(D)=4/81，不是协调的。，不是协调的。DesC(1)=1,0,2 DesD(1)=2,0DesC(5)=1,0,2 DesD(5)=0,1DesC(2)=0,1,1 DesD(2)=1,2DesC(8)=0,1,1 DesD(8)=0,1矛盾矛盾矛盾矛盾分解为如下两个表：分解为如下两个表：Uabcde3200114110226220

47、11721112完全协调的决策表完全协调的决策表Uabcde110220201112510201801101完全不协调的决策表完全不协调的决策表DesC(x)表示元素表示元素x的条件属性值。的条件属性值。DesD(x)表示元素表示元素x的决策属性值。的决策属性值。Uabcde320011411022622011721112完全协调的决策表完全协调的决策表U/C=3,4,6,7，U/D=3,6,4,7POSC(D)=3,4,6,7，rC(D)=4/4=1，数据是协调的。，数据是协调的。U/(C- -a)=3,4,6,7，POSC-a(D)=3,4,6,7,rC-a=1，是协调的。，是协调的。U/

48、(C-b)=3,6,4,7，POSC-b(D)=3,4,6,7,rC-b=1，是协调的。，是协调的。U/(C-c)=3,4,6,7，POSC-c(D)=3,4,6,7,rC-c=1，是协调的。，是协调的。U/(C-a,b)=3,4,6,7，POSC-a,b(D)=7,rC-a,b=1/4，是不协调的。，是不协调的。U/(C-b,c)=3,6,7,4，POSC-b,c(D)=4,rC-b,c=1/4，是不协调的。，是不协调的。U/(C-a,c)=36,4,7，POSC-a,c(D)=3,6,rC-a,c=2/4，是不协调的。，是不协调的。所以所以a,b、a,c、b,c都是不可省略的，则：都是不可

49、省略的，则：redC(D)=a,b,a,c,b,c。9.4 常用的决策表属性约简算法常用的决策表属性约简算法 对于决策表中的每一个条件属性对于决策表中的每一个条件属性a进行如下过程，直到条件属性集进行如下过程，直到条件属性集合不再发生变化为止。合不再发生变化为止。 如果删除该属性如果删除该属性a 使得使得POSC-a(D)=POSC(D)，则说明该属性是相，则说明该属性是相对决策属性对决策属性D不必要的，从不必要的，从 决策表中删除该属性所在的列并将重复的决策表中删除该属性所在的列并将重复的行进行合并；行进行合并； 否则，说明该属性是相对决策属性否则，说明该属性是相对决策属性d必要的，不能删除

50、。必要的，不能删除。9.4.1 一般属性约简算法一般属性约简算法算法描述算法描述:9.4.2 基于可辨识矩阵属性约简算法基于可辨识矩阵属性约简算法 n分辨矩阵（也称分明矩阵）是由波兰数学家分辨矩阵（也称分明矩阵）是由波兰数学家Skowron.A教授提出的。教授提出的。n定义定义，设相容决策表，设相容决策表T=，U=x1,x2, ,xn，C=ci | i=1,2,m和和D=d分别为条件属性集和决策属分别为条件属性集和决策属性集。分辨矩阵定义为：性集。分辨矩阵定义为：dij 当当d(xi)=d(xj)ck| ck(xi) ck(xj) 当当d(xi) d(xj)和信息表求分辨矩阵有什么不同？和信息

51、表求分辨矩阵有什么不同？U条件属性条件属性结论属性结论属性abc11122231331341335121一个决策表一个决策表求求分辨矩阵：分辨矩阵：123451ababb2aba3ab4b5n由上述定义可以看出，分辨矩阵是一个对称矩阵。当由上述定义可以看出，分辨矩阵是一个对称矩阵。当两个样本的决策属性取同时，对象值为两个样本的决策属性取同时，对象值为；当两个样；当两个样本的决策属性不同且可以通过某些条件属性的取值加本的决策属性不同且可以通过某些条件属性的取值加以区分时，对象值为这两个样本属性值不同的条件属以区分时，对象值为这两个样本属性值不同的条件属性集合。性集合。n一个数据集的所有约简可以通

52、过构造可辨识并且化简一个数据集的所有约简可以通过构造可辨识并且化简由可辨识矩阵导出的区分函数而得到，所有的蕴含式由可辨识矩阵导出的区分函数而得到，所有的蕴含式包含的属性就是决策表的所有约简集合。包含的属性就是决策表的所有约简集合。算法分辨矩阵属性约简算法算法分辨矩阵属性约简算法 输入：相容决策表输入：相容决策表DT=；输出：约简的属性集。输出：约简的属性集。步骤：步骤：（1）计算决策表的分辨矩阵；）计算决策表的分辨矩阵；/根据分辨矩阵的定义求根据分辨矩阵的定义求元素元素（2）对于可辨识矩阵中所有取值为非空集合的对象，建）对于可辨识矩阵中所有取值为非空集合的对象，建立相应的析取逻辑表达式。立相应

53、的析取逻辑表达式。（3）将所有的析取逻辑表达式进行合取运算，得）将所有的析取逻辑表达式进行合取运算，得一个最简合取范式一个最简合取范式T。（4）将合取范式）将合取范式T转换为析取范式的形式。转换为析取范式的形式。（5）输出属性约简结果。）输出属性约简结果。基于分辨矩阵和逻辑运算的属性约简算法可以得到基于分辨矩阵和逻辑运算的属性约简算法可以得到决策表的所有可能的属性约简结果，它实际上是将对属决策表的所有可能的属性约简结果，它实际上是将对属性组合情况的搜索演变成为逻辑公式的简化性组合情况的搜索演变成为逻辑公式的简化 。时间复杂度为时间复杂度为O(2m)，属，属NP问题。问题。一个气象决策表一个气象

54、决策表U条件属性条件属性结论属性结论属性天气天气a温度温度b湿度湿度 c有风否有风否de11110N21111N32110P43210P53320P63321N72321P81210N91320P103220P111221P122211P132120P143211NU/C=1,2,3,4,5,6,7,8,9,10,11,12,13,14U/D=1,2,6,8,14,3,4,5,7,9,10,11,12,13POSC(D)=1,2,3,4,5,6,7,8,9,10,11,12,13,14=U，是协调的。，是协调的。12345678910111213141aababcabcdbcabcbcdabd

55、ac2adabdabcdabcbcdabcdbcabacd3abcdababd4bcdabd5dacbcd6aadbdababdabd7abcdabc8bcaccdcdabc9abcd10cd11ac12ad13abcd14分辩矩阵：分辩矩阵：d1,3=a,d2,3=add1,4=abf(D)=d1,3d2,3a1,4 =(abd) (acd)两个约简为两个约简为a,b,d和和a,c,d，核为，核为a,d。约简结果约简结果1：a,b,dU条件属性条件属性结论属性结论属性天气天气a温度温度b有风否有风否de1110N2111N3210P4320P5330P6331N7231P8120N9130P

56、10320P11121P12221P13210P14321N约简结果约简结果2：a,c,dU条件属性条件属性结论属性结论属性天气天气a湿度湿度 c有风否有风否de1110N2111N3210P4310P5320P6321N7221P8110N9120P10320P11121P12211P13220P14311N利用分辨矩阵求核利用分辨矩阵求核命题：命题：在分辨矩阵中，所有单项属性构成决策表的在分辨矩阵中，所有单项属性构成决策表的核。核。12345678910111213141aababcabcdbcabcbcdabdac2adabdabcdabcbcdabcdbcabacd3abcdababd

57、4bcdabd5dacbcd6aadbdababdabd7abcdabc8bcaccdcdabc9abcd10cd11ac12ad13abcd14上例的分辩矩阵：上例的分辩矩阵：其中单项属性为其中单项属性为a和和d，则核为，则核为a,d设决策表中元素个数为设决策表中元素个数为n，求核的算法时间复杂度为求核的算法时间复杂度为O(n2)。9.4.3一般约简算法一般约简算法 对于决策表中的每一个条件属性对于决策表中的每一个条件属性ai，进行如下过程，进行如下过程，直至条件属性集合不再发生变化为止。直至条件属性集合不再发生变化为止。如果删除该属性如果删除该属性ai使得使得POS(C-ai)(D)=PO

58、SC(D)，则，则说明属性说明属性ai是相对于决策属性是相对于决策属性d不必要的，从决策表中删不必要的，从决策表中删除属性除属性ai所在列并将重复的行进行合并；所在列并将重复的行进行合并；否则，说明属性否则，说明属性ai是相对于决策属性是相对于决策属性D必要的，不能必要的，不能删除。删除。对于有限元素集合对于有限元素集合A=a1,a2,am，如果按照某种，如果按照某种属性重要性度量方法得到重要性由大到小的一个排列属性重要性度量方法得到重要性由大到小的一个排列a1,a2,am，就可以得到序集，就可以得到序集a1,a2,am，再得到，再得到相应地各阶幂集。相应地各阶幂集。 9.4.4 归纳属性约简

59、算法归纳属性约简算法 算法描述：算法描述： 步骤步骤1：求核：求核COREC(D)；步骤步骤2：求：求最小属性约简最小属性约简minC(D); （1）令）令X=COREC(D)，L=D- -X=a1,a2,a3am，T(L)表示表示L的的幂集，幂集，Ti(L)为为L的的i（1im）阶幂字集；）阶幂字集；（2）如果）如果DOSX(D)=DOSC(D)，则，则minC(D)=X，转，转(10)；（3）i=1，Flag=0；（4）Y=Ti(L)；（5）任意取）任意取yY，A=Xy，计算，计算POSA(D)=POSC(D)？若相等：若相等：如果如果Flag=0，则，则Z=A，Flag=1，否则，如否则

60、，如|U/Z|U/A|，则，则Z=A；（6）Y=Y- -y;（7）如果）如果Y，转，转(5)；（8）如果）如果Flag=1,则则minC(D)=Z，转（，转（10）;（9）i = i+1,如果如果im，则转（，则转（4）；）；（10）结束）结束添加添加y找到一个约简找到一个约简9.4.5 基于属性重要性的属性约简基于属性重要性的属性约简输入输入：决策表：决策表S=。输出输出：条件属性：条件属性C相对于决策属性相对于决策属性D的一个相对约简。的一个相对约简。（1）计算）计算C相对于相对于D的核的核COREC(D)；（2）令）令B=COREC(D)，如果，转到（，如果，转到（5）（3）对于）对于C