第4讲粗糙集理论决策规则课件.ppt

1、1内容v1、回顾v2、引例v3、约简与核v4、约简与核的算例v5、依赖关系v6、知识表达v7、综合算例v8、粗糙集内涵总结21、回顾v下近似下近似中的对象反映了对象属于概念X的充分条件充分条件，因而形成分类分类规则。v上近似上近似中的对象反映了对象属于概念X的必要条件必要条件，因而形成特征特征规则。论域初等集粗糙集X下近似上近似边界域31、回顾充分条件，必要条件v下近似下近似中的对象反映了对象属于概念X的充分条件充分条件，因而形成分类分类规则。v如果有事物情况A，则必然有事物情况B；如果没有事物情况A而未必没有事物情况B，A就是B的充分而不必要的条件，简称充分条件充分条件。下近似中下近似中的对

2、象的对象对象属于对象属于粗糙集粗糙集XAB 满足满足A 必然必然B不满足不满足A 不必然不必然B充分条件充分条件41、回顾充分条件，必要条件v上近似上近似中的对象反映了对象属于概念X的必要条件必要条件，因而形成特征特征规则。v如果没有事物情况A，则必然没有事物情况B；如果有事物情况A而未必有事物情况B，A就是B的必要而不充分的条件，简称必要条件必要条件。上近似中上近似中的对象的对象对象属于对象属于粗糙集粗糙集XAB 不满足不满足A 必然不必然不B 满足满足A 不必然不必然B必要条件必要条件51、回顾v上下近似，边界域，正域，负域)()()()()(|/|/XbnXposXRUXRRXXRUXn

3、egRXXRXposUXXRRXXRXRXbnUXRXYRUYXRUXRXYRUYXRRRRRR中元素组成的集合的判断肯定不属于根据知识负域，的称为正域，的称为中元素组成的集合的又不能判断肯定属于，既不能判断肯定属于根据知识边界域，的称为中元素组成的集合的判断可能属于根据知识，中元素组成的集合的判断肯定属于根据知识，62、引例v病人的病历如下，如何找到规则，电脑可以看病？病人头痛肌肉痛体温流感1是是正常否2是是高是3是是很高是4否是正常否5否否高否6否是很高是7否否高是8否是很高否72、引例v头痛，肌肉痛，体温，都是流感的必然症状吗？（）v由头痛，肌肉痛，体温的相应值，是否就可以判断出病人流感

4、与否？（）属性属性规则规则83、约简与核v约简（reduct），核（core）v定义：令R为一族等价关系，rR，如果ind(R)=ind(R-r)，则称r为R中不必要的；否则称r为R中必要的。如果每一个rR都为R中必要的，则称R为独立独立的；否则称R为依赖依赖的。定理：如果R是独立的，P R，则P也是独立的。设Q P。如果Q是独立的，且ind(Q)=ind(P),则称Q为P的一个约简约简。P可以有多种约简。P的所有必要关系必要关系组成的集合称为P的核核，记作core(P)定理：core(P)=red(P)，red(P)表示P的所有约简93、约简与核v判断过程必要必要不必要不必要独立独立依赖依赖

5、约简约简核核104、约简与核的算例v4.1 计算必要与否v4.2 检验独立与否v4.3 确定约简与核114、约简与核的算例v设K=(U,R)是一个知识库，其中 U=x1,x2,x8,R=R1,R2,R3，等价关系R1,R2,R3有如下的等价类：vU/R1=x1,x4,x5,x2,x8,x3,x6,x7 vU/R2=x1,x3,x5,x6,x2,x4,x7,x8 vU/R3=x1,x5,x6,x2,x7,x8,x3,x4 v关系ind(R)有下列等价类vU/ind(R)=x1,x5,x2,x8,x3,x4,x6,x7 v判断判断R的核？的核？124.1 计算必要与否v如果ind(R)=ind(R

6、-r)，则称r为R中不必要不必要的v否则称r为R中必要必要的134.1 计算必要与否vU/ind(R-R1)，去掉R1后，R2与R3交集vU/ind(R-R1)=x1,x5,x2,x7,x8,x3,x4,x6 U/ind(R)关系R1为R中必要必要的vU/ind(R-R2)=x1,x5,x2,x8,x3,x4,x6,x7=U/ind(R)关系R2是R中不必要不必要的vU/ind(R-R3)=x1,x5,x2,x8,x3,x4,x6,x7=U/ind(R)关系R3是R中不必要不必要的144.1 计算必要与否v运算表明，通过等价关系R1，R2，R3的集合定义的分类与与根据R1和R2，或者R1和R3

7、，定义的分类相同，即表明该系统的知识可以通过 U/ind(R1，R2)或 U/ind(R1，R3)来表达。vR=R1,R2,R3的约简是什么？154.2 检验独立与否v如果每一个rR都为R中必要的，则称R为独立独立的；v否则称R为依赖依赖的。v定理：如果R是独立的，P R，则P也是独立的。164.2 检验独立与否v检验R1，R2和R1，R3是否为独立的？v因为：U/ind(R1，R2)U/ind(R1)且U/ind(R1，R2)U/ind(R2)v所以：R1，R2是独立的v同理，R1，R3是独立的174.3 确定约简与核v设Q P。如果Q是独立的，且ind(Q)=ind(P)，则称Q为P的一个

8、约简约简。vP可以有多种约简。vP的所有必要关系必要关系组成的集合称为P的核核，记作core(P)v核与约简的关系v定理：core(P)=red(P)，red(P)表示P的所有约简184.3 确定约简与核v两个约简约简vR1，R2为R的一个约简约简vR1，R3为R的一个约简约简v一个核核vcore(R)=R1，R2 R1，R3 =R119小结4、约简与核的算例v4.1 计算必要与否v4.2 检验独立与否v4.3 确定约简与核必要必要不必要不必要独立独立依赖依赖约简约简核核205、依赖关系v如果知识Q依赖于知识P，则在知识库中，知识Q是多余的。知识知识PUQ与知识知识P提供同样的对象特征。v令K

9、=(U,R)为一知识库，且P,Q R,当 k=rp(Q)=|posp(Q)|/|U|时，称知识Q是k(0 k 1)度依赖于知识P的，记作P kQ当k=1时，Q完全依赖于P当0k1时，Q粗糙（部分）依赖于P当k=0时，Q完全独立于Pv系数rp(Q)可看作Q和P间的依赖度215、依赖关系v系数rp(Q)可看作Q和P间的依赖度v一些决策类可能完全由P描述，但另一些可能仅仅由P部分描述。v系数rp(X)=|PX|/|X|，(XU/Q)v表明通过知识P能将U/Q中每个类的多少个元素正确划分。vrp(Q)和rp(X)，XU/Q，给出了知识P的“分类能力”关于分类U/Q的全部信息。225、依赖关系算例vU/

10、Q=x1,x2,x3,x4 x5,vx1=1vx2=2，7vx3=3，6vx4=4vx5=5，8vU/P=Y1,Y2,Y3,Y4 Y5,Y6,vY1=1，5vY2=2，8vY3=3vY4=4vY5=6vY6=7计算知识知识Q和知识知识P间的依赖性量度。假定U=1,2,3,4,5,6,7,8，并且已知如下。235、依赖关系算例v计算知识知识Q和知识知识P间的依赖性量度。vX的P下近似，PXn，那些根据知识P判断，肯定属于Xn的U中元素组成的集合。245、依赖关系算例vPX1=vPX2=Y6vPX3=Y3 UY5vPX4=Y4vPX5=vposp(Q)=Y3 UY4 UY5UY6=3,4,6,7,

11、即只有这些元素可以通过知识P划入到分类U/Q的模块。vQ和P间的依赖度为rp(Q)=4/8=0.5256、知识表达v四元组S=(U,A,V,f)是一个知识表达系统vU：对象的非空有限集合，称为论域vA：属性的非空有限集合VxfUxAVAUfVVVA),(:,，即性赋予一个信息值，它为每个对象的每个属是一个信息函数，的值域；是属性266、知识表达v知识表达系统的数据以关系表关系表的形式表示。v关系表关系表的行行对应要研究的对象，列列对应对象的属性，对象的信息是通过指定对象的各属性值属性值来表达。v一个属性对应一个等价关系，一个表可以看作是定义的一族等价关系，即知识库。v知识约简可转化为属性约简属

12、性约简。v设S=(U,A,V,f)为一知识表达系统，A=C D，C D=，C称为条件属性集，D称为决策属性集。v具有条件属性条件属性和决策属性决策属性的知识表达系统称为决策表决策表。277、综合算例v7.1 举例患者的知识表达系统v7.2 等价关系v7.3 依赖关系v7.4 约简与核v7.5 属性的重要性v7.6 决策规则287.1 举例患者的知识表达系统v关于某些病人的决策表，其中U=e1,e2,e8，C=头痛，肌肉痛，体温，D=流感条件属性条件属性决策属性决策属性病人病人头痛头痛肌肉痛肌肉痛体温体温流感流感e1是是是是正常正常否否e2是是是是高高是是e3是是是是很高很高是是e4否否是是正常

13、正常否否e5否否否否高高否否e6否否是是很高很高是是e7否否否否高高是是e8否否是是很高很高否否297.2 等价关系v令C1=头痛，C2=肌肉痛，C3=体温，则vU/C1=e1,e2,e3,e4,e5,e6,e7,e8,vU/C2=e1,e2,e3,e4,e6,e8,e5,e7,vU/C3=e1,e4,e2,e5,e7,e3,e6,e8,vU/C1,C2=e1,e2,e3,e4,e6,e8,e5,e7,vU/C1,C3=e1 ,e2 ,e3 ,e4 ,e5,e7 e6,e8,vU/C2,C3=e1,e4,e2 ,e5,e7,e3,e6,e8,vU/C=e1 ,e2 ,e3 ,e4 ,e5,e7

14、 e6,e8,vU/D=e2,e3,e6,e7 ,e1,e4,e5,e8 ，307.3 依赖关系v因为vPOSC(D)=e1 e2 e3 e4 =e1,e2,e3,e4 vk=rC(D)=|posC(D)|/|U|=4/8=0.5v所以D部分依赖（依赖度为0.5）于C317.4 约简与核v因为有：),()(),(,)(),()(),(,)(),(,)(),(41),()(4321)(421)(3212321DposDposDposeeDposDposDposDposeeeeDposDposeeeDposCCCCCCCCCCCCCCCCC所以C的D约简（相对约简）为C-C2=C1，C3,C的D核

15、（相对核）也为C1，C3。327.5 属性的重要性v在决策表中，不同的属性可能具有不同的重要性。v为了找出某些属性（或属性集）的重要性，从表中去掉一些属性，再来考察没有该属性后分类会怎样变化。v若去掉该属性相应分类变化较大，则说明该属性的强度大，即重要性高；反之，说明该属性的强度小，即重要性低。337.5 属性的重要性v令C和D分别为条件属性集和决策属性集）（）（）（的重要性为关于时，属性特别当）（）（）（的重要性定义为关于属性子集DDDCCDDCDCCCCCDCCCCD1在病例中，有，体温最重要，其次是头痛，肌肉痛是不重要的。8/408/4(08/48/4(8/18/38/4(体温）肌肉痛）

16、头痛）CDCDCD347.6 决策规则v决策表中，最重要的是决策规则决策规则的产生。v设S=(U,A,V,f)是一个决策表，A=C D，C D=，C为条件属性集，D为决策属性集。v令Xi和Yj分别代表U/C与U/D中各个等价类vdes(Xi)表示对等价类Xi的描述，即等价类Xi对于各条件属性值的特定取值。vdes(Yj)表示对等价类Yj的描述，即等价类Yj对于各决策属性值的特定取值。357.6 决策规则v决策规则定义：vrij:des(Xi)des(Yj),YjXi ,v规则的确定性因子为：是不确定的。，当是确定的，时，当，jijijijijiiijjirYXrYXYXXXYYX,1),(01

17、),(1),(0|/|),(在产生决策规则决策规则之前，可首先对决策表中的属性进行约简约简。367.6 决策规则v算例中，属性约简，U=e1,e2,e8，vC=头痛，体温，D=流感条件属性决策属性病人头痛肌肉痛体温流感e1是是正常否e2是是高是e3是是很高是e4否是正常否e5否否高否e6否是很高是e7否否高是e8否是很高否377.6 决策规则vU/C=X1，X2，X3，X4，X5，X6v其中，X1=e1，vX2=e2，vX3=e3，vX4=e4，vX5=e5，e7，vX6=e6，e8，vU/D=Y1，Y2v其中，Y1=e2，e3，e6，e7，vY2=e1，e4，e5，e8，387.6 决策规则

18、v确定性规则确定性规则有vr12:(头痛，是)且(体温，正常)(流感，否)vr21:(头痛，是)且(体温，高)(流感，是)vr31:(头痛，是)且(体温，很高)(流感，是)vr42:(头痛，否)且(体温，正常)(流感，否)v不确定性规则不确定性规则有vr51:(头痛，否)且(体温，高)(流感，是)vr52:(头痛，否)且(体温，高)(流感，否)vr61:(头痛，否)且(体温，很高)(流感，是)vr62:(头痛，否)且(体温，很高)(流感，否)v以上规则的确定性因子为0.539小结7、综合算例v7.1 举例患者的知识表达系统v7.2 等价关系v7.3 依赖关系v7.4 约简与核v7.5 属性的重

19、要性v7.6 决策规则408、粗糙集内涵总结求约简与核的过程知识库K=（U，R）等价类，U/R1,U/R2,U/Rn，U/ind(R)比较U/ind(R)，U/ind(R-Rn)，判别必要性独立的，必要的约简所有的必要关系组成的集合核418、粗糙集内涵总结求解决策规则知识表达系统S=(U,A,V,f),A=CD,CD=等价类U/C1,U/C2,U/Cn，U/C,U/DPOSC(D),依赖度k=rC(D)=|POSC(D)|/|U|比较POS(C-Cn)(D),POSC(D)，不等必要约简(相对)，核(相对)重要性）（）（）（DDCCCCCD11),(0|/|),(jiiijjiYXXXYYX，决策规则的确定性因子428、粗糙集内涵总结名词概念v知识表达v决策表v等价类v不可区分关系indv正域v约简v核v依赖度v重要性v规则确定性因子v决策规则438、粗糙集内涵总结v粗糙集v智能决策v数据挖掘定义定义规则规则现实世界现实世界逻辑世界逻辑世界智能决策智能决策数据挖掘数据挖掘44总结内容v1、回顾v2、引例v3、约简与核v4、约简与核的算例v5、依赖关系v6、知识表达v7、综合算例 决策规则v8、粗糙集内涵总结45Do you have made a progress today?