粗糙集理论(Rough Set Theory RST)

智能决策方法2020/4/20粗糙集理论(RoughSetTheory)1粗糙集理论(RoughSetTheory:RST)电子商务研究所智能决策方法2020/4/20粗糙集理论(RoughSetTheory)2预备知识——相关名词解释论域：研究对象的全体成员构成的集合，一般用字母U表示；若XU，则称X是U的子集隶属度：描述一个对象x与某个子集X之间的隶属程度，一般用符号表示，若xX,则=1;若,则=0;其他：01;(常用某个函数加以描述，称为隶属度函数)Xx高斯函数智能决策方法2020/4/20粗糙集理论(RoughSetTheory)3预备知识——相关名词解释等价关系：R是U上的一个等价关系，当且仅当对于任意xU，均有xRx（自反性）对于任意x,yU，xRy↔yRx（对称性）对于任意x,y,zU，xRy∧yRz→xRz（传递性）等价类：若R是U上的一个等价关系，对于任意xU，称集合[x]={y|yRx,yU}为U关于R的一个等价类，记为[x]R。设X1,X2,…,Xn是U关于R的所有等价类，则有：Xi∩Xj=φ（i≠j，i,j=1,2,…,n）X1∪X2∪…∪Xn=U划分：所有等价类的集合称为U关于R的商集，它构成了U的一个划分，记为U/R。概念：具有相同特征值的一群对象称为一个概念（一个等价类就是一个概念）智能决策方法2020/4/20粗糙集理论(RoughSetTheory)4预备知识——相关名词解释piT1pjiifv(pi,T1)=v(pj,T1)，则T1是U上的一个等价关系（类似地可以定义T2,T3,E）X1=[p1]=[p4]=[p6]={p1,p4,p6}为U关于T1的一个等价类X2=[p2]=[p3]=[p5]={p2,p3,p5}为U关于T1的另一个等价类（T1有多少种取值就有多少个等价类）显然X1∩X2=φ;X1∪X2=U商集U/T1={X1,X2}UT1T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY智能决策方法2020/4/20粗糙集理论(RoughSetTheory)5预备知识——成员集合成员：明确的隶属关系模糊成员：概念模糊(如青年)导致成员模糊粗糙成员：概念清晰(如感冒)，成员模糊(是否感冒不清楚)，具有概率特征(隶属函数)，但不是概率问题，只是由于根据可用知识无法得到准确结论。智能决策方法2020/4/20粗糙集理论(RoughSetTheory)6粗糙集理论的经典模型——RST的提出粗糙集理论由Pawlak提出[1982,1991]。粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能力，或依据观察、度量到某些不精确的结果而进行分类数据的能力。PawlakZ.,Roughsets.InternationalJournalofComputerandInformationSciences,1982(11):341-356PawlakZ.,Roughset—TheoreticalAspectsofReasoningaboutData,Dordrecht,Boston,London:KluwerAcademicPublishers,1991智能决策方法2020/4/20粗糙集理论(RoughSetTheory)7粗糙集理论的经典模型——基本思想知识是主体对论域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠度越高分类能力受主体分辨能力的影响，因此分类具有近似性(粗糙集)影响分类能力的因素(在信息系统中常描述为属性)很多，不同的因素重要程度不同，其中某些因素起决定性作用(属性重要性：属性约简)具有相同属性的实体，属性取值的不同对分类能力也产生影响(值重要性：值约简)属性之间存在某种依赖关系(决策规则)智能决策方法2020/4/20粗糙集理论(RoughSetTheory)8粗糙集理论的经典模型——信息系统与知识信息系统I可以定义为四元组U,A,V,f，其中有限非空集合U是论域，A为关于U的属性集，，Va表示属性a的值域，映射f:U×A→V表示对xU，aA，有：f(x,a)V。决策表：若属性集合A可进一步分为两个属性子集的并：条件属性集C和决策属性集D，A=C∪D，C∩D=φ，则信息系统也被称为决策表。aAaVVUT1T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY智能决策方法2020/4/20粗糙集理论(RoughSetTheory)9粗糙集理论的经典模型——信息系统与知识A的任何一个子集B确定一个U上的二元关系IND(B)：对于任意aB，xIND(B)ya(x)=a(y)；x,yU；a(x)表示对象x的a属性值。则称IND(B)为不可分辨关系(?)。IND(B)是等价关系，IND(B)的所有等价类的集合记为U/B（称为知识B），含有元素x的等价类记为B(x)或[x]B，同一等价类中的元素是不可分辨的，称IND(B)等价类为初等集（范畴），它是知识库的基本结构单元即概念。设R是由属性集A的子集诱导的论域U上的等价关系族，则称R为U上的一个知识库，记为K=(U,R)。智能决策方法2020/4/20粗糙集理论(RoughSetTheory)10粗糙集理论的经典模型——粗糙集与近似对于U的任意子集X，若X恰能由知识R的若干个初等集的并构成，则称X为R-精确集，否则为R-粗糙集。每个粗糙集X都可用两个与之相关的精确集近似表示即X的上近似和下近似，他们是粗糙集理论的两个最基本运算。智能决策方法2020/4/20粗糙集理论(RoughSetTheory)11粗糙集理论的经典模型——粗糙集与近似下近似由所有包含于X的初等集合的并构成，X的下近似中的元素一定属于X。上近似由与X的交为非空的初等集合的并构成，而上近似中的元素可能属于X。上近似与下近似的差为边界域，粗糙集的边界域为非空，否则为精确集。边界域中的元素根据可用知识没有确定的分类，即它既不能划分到X中也不能划分到X的补集中。正域与负域YXxUxXRXYRUYR)()/(}][:{YXxUxXRXYRUYR)()/(}][:{XRXPOSR)(XRUXNegR)(智能决策方法2020/4/20粗糙集理论(RoughSetTheory)12粗糙集理论的经典模型——经典粗糙集模型论域U粗糙集X粗糙集X智能决策方法2020/4/20粗糙集理论(RoughSetTheory)13粗糙集理论的经典模型——经典粗糙集模型R1={T1}：U/R1={{p2,p3,p5}，{p1,p4,p6}}；R2={T2,T1}：U/R2={{p1,p4,p6},{p2,p5},{p3}}；R3={T1,T2,T3}：U/R3=({p1},{p3},{p6},{p2,p5},{p4}};F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R3粗糙集，X1的R3下近似是{p1,p3,p6}，R3上近似是{p1,p2,p3,p5,p6}，边界域为{p2,p5}；X2={p4,p5}也是R3粗糙集，X2的R3下近似是{p4}，X2的R3上近似是{p2,p4,p5}，而边界域是{p2,p5}。T1T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY智能决策方法2020/4/20粗糙集理论(RoughSetTheory)14粗糙集理论的经典模型——拓扑结构R粗糙可定义能准确确定某部分对象一定属于X，某部分对象一定不属于X，某部分对象可能属于X。R内不可定义能准确某部分对象一定不属于X，某部分对象可能属于X，而不能确定任何对象属于X。R外不可定义能准确确定某部分对象一定属于X，某部分对象可能属于X，不能确定任何对象不属于XR完全不可定义UXRXRUXRXRUXRXRUXRXR智能决策方法2020/4/20粗糙集理论(RoughSetTheory)15粗糙集理论的经典模型——粗糙集数字特征精度：X的R精度反映了我们对于了解集合X的知识的完全程度。αR(X)=1为精确集，0≤αR(X)1为粗糙集。粗糙度：X的R粗糙度反映了我们对于了解集合X的知识的不完全程度。(精度与概率或隶属度的区别)隶属度：是根据可用知识R，对象x隶属于概念X的条件概率。)()()()(XXRCardXRCardXR)(1)(XXRR|)(||)(|)(xRXxRxRX智能决策方法2020/4/20粗糙集理论(RoughSetTheory)16粗糙集理论的经典模型——粗糙集数字特征设F={X1，X2，…，Xn}是论域U上的一个划分，那么根据知识R，F的分类精度如何？F的近似精度：分类的近似精度给出了根据现有知识对对象进行分类时可能正确的决策的百分数。F的近似质量：近似质量给出了能正确分类的百分数。这是一个非常重要的特征数字，它反映了两种分类F和R之间的关系。如果将R看作决策表中的条件属性集，F看成决策属性集，近似质量反映了两者之间的依赖关系。CardUXRCardFniiR1)(niiniiRXRCardXRCardF11)(智能决策方法2020/4/20粗糙集理论(RoughSetTheory)17粗糙集理论的经典模型——粗糙集数字特征知识R={T1,T2,T3}：U/R=({p1},{p3},{p6},{p2,p5},{p4}};分类F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R粗糙集，X1的R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}，R精度为0.6；R粗糙度为0.4；X2={p4,p5}也是R粗糙集，X2的R下近似是{p4}，X2的R上近似是{p2,p4,p5}，R精度为0.333；R粗糙度为0.667；p2隶属于X1的隶属度为0.25。T1T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY智能决策方法2020/4/20粗糙集理论(RoughSetTheory)18粗糙集理论的经典模型——粗糙集数字特征知识R={T1,T2,T3}：U/R=({p1},{p3},{p6},{p2,p5},{p4}};分类F={E}：U/F={{p1,p2,p3,p6},{p4,p5}}X1={p1,p2,p3,p6}是R粗糙集，X1的R下近似是{p1,p3,p6}，R上近似是{p1,p2,p3,p5,p6}；X2={p4,p5}也是R粗糙集，X2的R下近似是{p4}，X2的R上近似是{p2,p4,p5}；F的近似精度为0.5；F的近似质量为0.667。T1T2T3Ep1NYNormalYp2YNNormalYp3YYHighYp4NYLowNp5YNNormalNp6NYHighY智能决策方法2020/4/20粗糙集理论(RoughSetTheory)19粗糙集理论的经典模型——知识依赖为了寻找“IF……THEN”形式的推理规则，在粗糙集理论体系中所采用的方法是从一个给定的知识，推导另一个知识。如果知识D的所有初等范畴都能用知识C的某些初等范畴来定义，则称知识D可由知识C推得，也称D完全依赖于C，记为CD。设信息系统I=U,A,V,f，A=C∪D，BC，则D的B正域定义为：D的B正域表示利用知识B，能正确地划分到U/D各等价类中的所有对象的集合XBDPOSDUXB/)(智能决策方法2020/4/20粗糙集理论(RoughSet