第04讲-智能决策理论与方法-1(2)解析.ppt

1、2020/7/19,粗糙集理论(Rough Set Theory),1,粗糙集理论(Rough Set Theory: RST),电子商务研究所,2020/7/19,粗糙集理论(Rough Set Theory),2,预备知识相关名词解释,论域：研究对象的全体成员构成的集合，一般用字母U表示；若XU，则称X是U的子集 隶属度：描述一个对象x与某个子集X之间的隶属程度，一般用符号表示， 若xX, 则=1; 若 ,则=0; 其他： 01;(常用某个函数加以描述，称为隶属度函数),高斯函数,2020/7/19,粗糙集理论(Rough Set Theory),3,预备知识相关名词解释,等价关系：R是U

2、上的一个等价关系，当且仅当 对于任意xU，均有x R x（自反性） 对于任意x, yU，x R yy R x（对称性） 对于任意x, y, zU，x R y y R zx R z（传递性） 等价类：若R是U上的一个等价关系，对于任意xU，称集合x=y| y R x, y U为U关于R的一个等价类，记为xR。设X1, X2, , Xn是U关于R的所有等价类，则有： XiXj=（ij，i, j=1,2,n） X1X2Xn=U 划分：所有等价类的集合称为U关于R的商集，它构成了U的一个划分，记为U/R。 概念：具有相同特征值的一群对象称为一个概念（一个等价类就是一个概念）,2020/7/19,粗糙集

3、理论(Rough Set Theory),4,预备知识相关名词解释,pi T1 pj iif v(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有多少种取值就有多少个等价类） 显然 X1X2=; X1X2=U 商集U/T1=X1, X2,2020/7/19,粗糙集理论(Rough Set Theory),5,预备知识成员,集合成员：明确的隶属关系 模糊成员：概念模糊(如青年)导致成员模糊 粗糙成员

4、：概念清晰(如感冒)，成员模糊(是否感冒不清楚)，具有概率特征(隶属函数)，但不是概率问题，只是由于根据可用知识无法得到准确结论。,2020/7/19,粗糙集理论(Rough Set Theory),6,粗糙集理论的经典模型RST的提出,粗糙集理论由Pawlak提出1982,1991。粗糙集理论反映了人们以不完全信息或知识去处理一些不可分辨现象的能力，或依据观察、度量到某些不精确的结果而进行分类数据的能力。 Pawlak Z., Rough sets. International Journal of Computer and Information Sciences, 1982(11): 3

5、41-356 Pawlak Z., Rough setTheoretical Aspects of Reasoning about Data, Dordrecht, Boston, London: Kluwer Academic Publishers,1991,2020/7/19,粗糙集理论(Rough Set Theory),7,粗糙集理论的经典模型基本思想,知识是主体对论域中的客体进行分类的能力，分类能力越强，主体所具备知识的可靠度越高 分类能力受主体分辨能力的影响，因此分类具有近似性 (粗糙集) 影响分类能力的因素(在信息系统中常描述为属性)很多，不同的因素重要程度不同，其中某些因素起决

6、定性作用 (属性重要性：属性约简) 具有相同属性的实体，属性取值的不同对分类能力也产生影响 (值重要性：值约简) 属性之间存在某种依赖关系(决策规则),2020/7/19,粗糙集理论(Rough Set Theory),8,粗糙集理论的经典模型信息系统与知识,信息系统I可以定义为四元组，其中有限非空集合U是论域，A为关于U的属性集， ，Va表示属性a的值域，映射f: UAV表示对xU，aA，有： f(x, a)V。 决策表：若属性集合A可进 一步分为两个属性子集的并： 条件属性集C和决策属性集D， A=CD，CD=，则信息 系统也被称为决策表。,2020/7/19,粗糙集理论(Rough Se

7、t Theory),9,粗糙集理论的经典模型信息系统与知识,A的任何一个子集B确定一个U上的二元关系IND(B)：对于任意aB，xIND(B)ya(x)=a(y)；x, yU；a(x)表示对象x的a属性值。则称IND(B)为不可分辨关系(?)。 IND(B)是等价关系，IND(B)的所有等价类的集合记为U/B（称为知识B），含有元素x的等价类记为B(x)或xB，同一等价类中的元素是不可分辨的，称IND(B)等价类为初等集（范畴），它是知识库的基本结构单元即概念。 设R是由属性集A的子集诱导的论域U上的等价关系族，则称R为U上的一个知识库，记为K=(U, R)。,2020/7/19,粗糙集理论(

8、Rough Set Theory),10,粗糙集理论的经典模型粗糙集与近似,对于U的任意子集X，若X恰能由知识R的若干个初等集的并构成，则称X为R-精确集，否则为R-粗糙集。 每个粗糙集X都可用两个与之相关的精确集近似表示即X的上近似和下近似，他们是粗糙集理论的两个最基本运算。,2020/7/19,粗糙集理论(Rough Set Theory),11,粗糙集理论的经典模型粗糙集与近似,下近似 由所有包含于X的初等集合的并构成， X的下近似中的元素一定属于X。 上近似 由与X的交为非空的初等集合的并构成，而上近似中的元素可能属于X。 上近似与下近似的差为边界域，粗糙集的边界域为非空，否则为精确集

9、。边界域中的元素根据可用知识没有确定的分类，即它既不能划分到X中也不能划分到X的补集中。 正域与负域,2020/7/19,粗糙集理论(Rough Set Theory),12,粗糙集理论的经典模型经典粗糙集模型,2020/7/19,粗糙集理论(Rough Set Theory),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,

10、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。,2020/7/19,粗糙集理论(Rough Set Theory),14,粗糙集理论的经典模型拓扑结构,R粗糙可定义 能准确确定某部分对象一定属于X，某部分对象一定不属于X，某部分对象可能属于X。 R内不可定义 能准确某部分对象一定不属于X，某部分对象可能属于X，而不能确定任何对象属于X。 R外不可

11、定义 能准确确定某部分对象一定属于X，某部分对象可能属于X ，不能确定任何对象不属于X R完全不可定义,2020/7/19,粗糙集理论(Rough Set Theory),15,粗糙集理论的经典模型粗糙集数字特征,精度： X的R精度反映了我们对于了解集合X的知识的完全程度。R(X)=1为精确集， 0R(X)1为粗糙集。 粗糙度：X的R粗糙度反映了我们对于了解集合X的知识的不完全程度。(精度与概率或隶属度的区别) 隶属度：是根据可用知识R，对象x隶属于概念X的条件概率。,2020/7/19,粗糙集理论(Rough Set Theory),16,粗糙集理论的经典模型粗糙集数字特征,设F=X1，X2

12、，Xn是论域U上的一个划分，那么根据知识R，F的分类精度如何？ F的近似精度：分类的近似精度给出了根据现有知识对对象进行分类时可能正确的决策的百分数。 F的近似质量：近似质量给出了能正确分类的百分数。这是一个非常重要的特征数字，它反映了两种分类F和R之间的关系。如果将R看作决策表中的条件属性集，F看成决策属性集，近似质量反映了两者之间的依赖关系。,2020/7/19,粗糙集理论(Rough Set Theory),17,粗糙集理论的经典模型粗糙集数字特征,知识R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分类F=E：U/F=p1, p2, p3, p6, p

13、4, 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。,2020/7/19,粗糙集理论(Rough Set Theory),18,粗糙集理论的经典模型粗糙集数字特征,知识R=T1, T2, T3：U/R=(p1, p3, p6, p2, p5,p4; 分类F=E：U/F=p1, p2, p3, p6,

14、 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。,2020/7/19,粗糙集理论(Rough Set Theory),19,粗糙集理论的经典模型知识依赖,为了寻找“IFTHEN”形式的推理规则，在粗糙集理论体系中所采用的方法是从一个给定的知识，推导另一个知识。如果知识D的所有初等范畴都能用知识C的某些初等范畴来定义，则称知识D可由知识C推得，也称D完

15、全依赖于C，记为CD。 设信息系统I=，A=CD，BC，则D的B正域定义为： D的B正域表示利用知识B，能正确地划分到U/D各等价类中的所有对象的集合,2020/7/19,粗糙集理论(Rough Set Theory),20,粗糙集理论的经典模型知识依赖,设信息系统I=， D完全依赖于C当且仅当 D等价于C当且仅当(CD) (DC)； D独立于C当且仅当(CD) (DC)。 如果知识D的部分初等范畴能用知识C的某些初等范畴来定义，称知识D部分依赖于知识C。 设信息系统I=，有： 则称D是k(0k1)度依赖于C，记为CkD。,2020/7/19,粗糙集理论(Rough Set Theory),2

16、1,粗糙集理论的经典模型知识依赖,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 ； X2=p4, p5也是R3粗糙集，X2的R3下近似是p4，X2的R3上近似是p2, p4, p5 。 F的R3正域是p1, p3,

17、p4, p6, 所以F对R3的依赖度是2/3。,2020/7/19,粗糙集理论(Rough Set Theory),22,粗糙集理论的经典模型知识约简,为什么要约简知识？ 判别：根据条件属性取值确定对象所属的类。 实际：确定对象所属的类只需其中几个属性甚至一个属性，而不需要知道对象所有的属性，这与人类对实体的识别是一致的。 表明：不同属性在分类时所起的作用是不同的。 什么是知识约简？ 将知识库中某些不必要的等价关系（知识）移去的过程。 设信息系统I=，BC，若C(D)=B(D)且B是D独立的，则B为C的D约简，记为REDD(C)。 C的D约简是不含任何冗余知识且与C具有相同分类能力的子集（用知

18、识C将对象划分到知识D的初等范畴中的能力）。,2020/7/19,粗糙集理论(Rough Set Theory),23,粗糙集理论的经典模型属性重要性与属性核,在确定某个决策目标时，不同属性的重要性是不同的，在一般分析中常用事先假设的权重来描述。粗糙集理论并不使用事先假设的信息，而是根据各属性的分类能力不同，确定该属性的重要性。处理方法是将该属性从信息表中移去，分析其对分类能力的影响，影响越大，属性越重要。 设信息系统I=，对于C的非空子集B，其重要度为 若B的重要度为，则表示B可以从C中移去，也即B是冗余的。重要度可理解为移去B时所产生的分类误差。 设信息系统I=，C中所有D不可省略的元素构

19、成的集合称为C的D核，记作CoreD(C)。,2020/7/19,粗糙集理论(Rough Set Theory),24,粗糙集理论的经典模型分辨矩阵,分辨矩阵 为了简化核、约简及其它概念的计算，Skowron在1991年提出了分辨矩阵的概念。 设 ，BA的分辨矩阵M(B)定义为： B核是M(B)中全部含有单个元素的条目的并即：,2020/7/19,粗糙集理论(Rough Set Theory),25,粗糙集理论的经典模型分辨矩阵,若存在一个B的最小子集 ，使得对于M(B)中的任意非空条目 有 ，则 是B的约简。 相对约简和相对核：设C、D是A的两个非空子集，C为条件属性，D为决策属性，则C的分

20、辨矩阵定义为：,2020/7/19,粗糙集理论(Rough Set Theory),26,粗糙集理论的经典模型分辨矩阵,的意义：表示两个对象有且只有一个存在于POSC(D)中，或者若二者均存在于POSC(D)中，但二者对属性集D不等价。如果D诱导的划分可由知识C定义即所有对象均属于POSC(D)，则 可简化为 C的D核：是MD(C)中所有含单个元素的条目的并 C的D约简：若存在一个C的最小子集 ，使得对于MD(C)中的任意非空条目 有 ， 则 是C的D约简。 按定义，C的D分辨矩阵为主对角线为空集的对称阵：,2020/7/19,粗糙集理论(Rough Set Theory),27,粗糙集理论的

21、经典模型分辨矩阵,2020/7/19,粗糙集理论(Rough Set Theory),28,粗糙集理论的经典模型知识约简算法,基于属性依赖度的属性约简：设决策表T=，C,D分别为条件属性和决策属性，B是C的任一非空子集，对于粗糙集的VP-MD模型，D对B的依赖度为： 则在B中增加某个属性pC-B所引起的k的变化大小为： p(D|B)= Bp(D)-B(D) p(D|B)越大，说明在已知属性B的条件下，p对决策D越重要。基于属性依赖度的属性约简算法就是将p(D|B)作为寻找最小属性约简的启发式信息。,2020/7/19,粗糙集理论(Rough Set Theory),29,粗糙集理论的经典模型知

22、识约简算法,基于属性互信息的属性约简：苗夺谦等人将条件属性与决策属性的依赖度转变成互信息，在决策表中增加某个属性所引起互信息变化的大小作为属性重要性的度量。 设决策表T=，C,D分别为条件属性和决策属性，B是C的任一非空子集，在B中增加某个属性pC-B所引起的互信息增量为： I(p;D|B)=I(Bp;D)I(B;D)=H(D|B)H(D|Bp) 该增量越大，说明在已知属性B的条件下，p对决策D越重要。基于互信息的属性约简算法就是将I(p;D|B)作为寻找最小属性约简时的启发式信息,2020/7/19,粗糙集理论(Rough Set Theory),30,粗糙集理论的经典模型知识约简算法,基于

23、分辨矩阵的约简算法： 分辨函数：=(T1T2)(T3) (T1 T2) (T2 T3) (T1 T2 T3) (T1 T2 T3) (T1 T3) (T2 T3) (T1 T2 T3) (T3) (T1 T2 T3) =(T1T2) (T3) =(T1 T3 )(T2T3),2020/7/19,粗糙集理论(Rough Set Theory),31,粗糙集理论的经典模型值约简,为什么要约简属性值？ 在判断某个对象属于某类时，某个属性的取值不同，对分类产生的影响也不相同。例如，判断人的体形(瘦、中、胖)时，体重是重要属性。但若体重属性值为60Kg时，此人的体形要结合其身高、性别才能确定，但若体重属

24、性值为150Kg时，我们几乎肯定他是个胖子，这时身高、性别已不重要，也就是说身高、性别的属性值是冗余的。 什么是值约简？ 值约简就是移去对分类没有实际价值的冗余的属性值。,2020/7/19,粗糙集理论(Rough Set Theory),32,粗糙集理论的经典模型约简示例,IF (T1, No) AND (T3, Normal) THEN (E, Yes) IF (T1, Yes) AND (T3, Normal) THEN (E, Yes) IF (T3, High) THEN (E, Yes) IF (T3, Low) THEN (E, No) IF (T1, Yes) AND (T3,

25、 Normal) THEN (E, No) IF (T3, High) THEN (E, Yes),2020/7/19,粗糙集理论(Rough Set Theory),33,粗糙集理论的经典模型约简示例,IF (T2, Yes) AND (T3, Normal) THEN (E, Yes) IF (T2, No) AND (T3, Normal) THEN (E, Yes) IF (T3, High) THEN (E, Yes) IF (T3, Low) THEN (E, No) IF (T2, No) AND (T3, Normal) THEN (E, No) IF (T3, High) THEN (E, Yes),2020/7/19,粗糙集理论(Rough Set Theory),34,扩展粗糙集模型-扩展的背景,为什么要研究RST的拓展模型？ 经典粗糙集理论假设信息系统仅包含精确(准确、可靠)数据，任何对象的任何属性都有一个唯一的精确