粗糙集理论及其应用.pptx

《粗糙集理论及其应用.pptx》由会员分享，可在线阅读，更多相关《粗糙集理论及其应用.pptx（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、OutlineRough sets理论的快速入门方法Rough sets理论的发展概述Rough setsRough sets理论的基本原理理论的基本原理计算举例计算举例课后研读论文第1页/共70页9.1Roughsets的快速入门方法的快速入门方法认真研读认真研读Rough Sets TheoryRough Sets Theory的创始人、波兰数学家的创始人、波兰数学家Z.Z.PawlakPawlak于于19821982年发表的第一篇论文年发表的第一篇论文“Rough SetsRough Sets”。【注】：最好直接阅读英文论文原文。研读王珏等人研读王珏等人19961996年在年在模式识别与

2、人工智能模式识别与人工智能上发表上发表的关于的关于Rough SetsRough Sets理论及其应用的综述性文章。理论及其应用的综述性文章。参考史忠植编著的参考史忠植编著的高级人工智能高级人工智能、知识发现知识发现等等教材中讨论粗糙集的有关章节。教材中讨论粗糙集的有关章节。【注】：国内王国胤、刘清、张文修、曾黄麟等人先后出版了关于Rough Sets的教材，也可适当参考。第2页/共70页Roughset快速入门方法（续）快速入门方法（续）认真研读如下认真研读如下3 3篇典型的论文：篇典型的论文：1 Pawlak,Z.,et al.Rough set approach to multi-att

3、ribute decisionanalysis.European Journal of Operational Research,72:443-459,19942Grzymala-Busse,D.M.,et al.Theusefulnessofamachinelearningapproach to knowledge acquisition.Computational Intelligence.11(2):268-279,19953Jelonek,J.,et al.Roughsetreductionofattributesandtheirdomainsfor neural networks.C

4、omputational Intelligence,11(2):339-347,1995第3页/共70页 9.2 9.2 粗糙集理论的发展概述粗糙集理论的发展概述粗糙集理论的提出粗糙集理论的提出自然界中大部分事物所呈现的信息都是：不完整的、不确定的、模糊的和含糊含糊的 经典逻辑无法准确、圆满地描述和解决粗糙集理论主要是为了描述并处理粗糙集理论主要是为了描述并处理“含糊含糊”信息。信息。“Blessedarethemerciful,fortheywillbeshownmercy.Blessedarethepureinheart,fortheywillseeGod.”From MATTHEW 5:

5、7-8 NIV 第4页/共70页粗糙集理论的提出（续粗糙集理论的提出（续1）“含糊含糊”（Vague）1904年谓词逻辑创始人G.Frege(弗雷格)首次提出将含糊性归结到“边界线区域边界线区域”(Boundaryregion)在全域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上“模糊集模糊集”（FuzzySets）1965年美国数学家L.A.Zadeh首次提出无法解决G.Frege提出的“含糊”问题未给出计算含糊元素数目的数学公式第5页/共70页粗糙集理论的提出（续粗糙集理论的提出（续2）“粗糙集粗糙集”（RoughSets）1982年波兰数学家Z.Pawlak首

6、次提出将边界线区域定义为“上近似集”与“下近似集”的差集指出在“真”、“假”二值之间的“含糊度”是可计算的给出计算含糊元素数目的计算公式借鉴了集合论中的“等价关系”（不可区分关系）求取大量数据中的最小不变集合（称为“核核”）求解最小规则集（称为“约简约简”）第6页/共70页粗糙集理论的提出（续粗糙集理论的提出（续3）粗糙集理论中的一些基本观点基本观点“概念”就是对象的集合“知识”就是将对象进行分类的能力(“各从其类各从其类”)“知识”是关于对象的属性、特征或描述的刻划不可区分关系表明两个对象具有相同的信息提出上近似集、下近似集、分类质量等概念“Godmadethewildanimalsacco

7、rdingtotheirkinds,thelivestockaccordingtotheirkinds,andallthecreaturesthatmovealongthegroundaccordingtotheirkinds.AndGodsawthatitwasgood.”From GENESIS 1:25 NIV 第7页/共70页粗糙集理论的发展历程粗糙集理论的发展历程1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。

8、1982年，Pawlak发表经典论文Roughsets，标志着该理论正式诞生。第8页/共70页粗糙集理论的发展历程（续粗糙集理论的发展历程（续1）1991年，Pawlak的第一本关于粗糙集理论的专著Rough sets:theoretical aspects of reasoning about data；1992年，Slowinski主编的Intelligence decision support:handbook of applications and advances of rough sets theory的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。19

9、92年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的Foundationofcomputinganddecisionsciences上。第9页/共70页粗糙集理论的发展历程（续粗糙集理论的发展历程（续2）1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。1995年，年，Pawlak等人在等人在ACMCommunications上上发表发表“Roughsets”，极大地扩大了该理论的国际影响。，极大地扩大了该理论的国际影响。19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。2000年

10、，在加拿大召开了第二届粗糙集与计算趋势国际会议。第10页/共70页粗糙集理论的发展历程（续粗糙集理论的发展历程（续3）20012002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（年会）。2005年，在加拿大召开RSFDGrC国际会议（年会）。第11页/共70页粗糙集理论的优点及局限性粗糙集理论的优点及局限性主要优点主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。“Nowfaith

11、isbeingsureofwhatwehopeforandcertainofwhatwedonotsee.”“AndwithoutfaithitisimpossibletopleaseGod,becauseanyonewhocomestohimmustbelievethatheexistsandthatherewardsthosewhoearnestlyseekhim.”From HEBREWS 11:1,6 NIV第12页/共70页粗糙集理论的优点及局限性（续）粗糙集理论的优点及局限性（续）局限性局限性缺乏处理不精确或不确定原始数据的机制对含糊概念的刻划过于简单无法解决所有含糊的、模糊的不确

12、定性问题需要其它方法的补充解决办法解决办法与模糊集理论相结合与Dempster-Shafer证据理论相结合第13页/共70页粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对遗粗糙集理论可以用于对遗失数据的填补。失数据的填补。在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则用于分类规则的发现。的发现。第14页/共70页粗糙集理论在知识发现中的作用（续）粗糙集理论在知识发现中的作用（续）在数据挖掘阶段的主要作用在数据挖掘阶段的主要作用通过布尔推理挖掘出约简的规则来解

13、释决策通过熵理论将规则的复杂性和预测的误差分析溶入到无条件的度量中与模糊集理论、证据理论构成复合分析方法搜寻隐含在数据中的确定性或非确定性的规则在解释与评估过程中，粗糙集理论可用于对所对所得到的结果进行统计评估。得到的结果进行统计评估。第15页/共70页粗糙集理论的研究现状粗糙集理论的研究现状在理论研究方面数学性质数学性质：研究其代数与拓扑结构、收敛性等粗糙集拓广粗糙集拓广：广义粗糙集模型、连续属性离散化与其它不确定性处理方法的关系和互补与其它不确定性处理方法的关系和互补：与模糊集理论、Dempster-Shafer证据理论的关系和互补粒度计算粒度计算：粗糙集理论是其重要组成之一高效算法高效算

14、法：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进第16页/共70页粗糙集理论的研究现状（续）粗糙集理论的研究现状（续）在数据挖掘领域的应用发现数据之间（精确或近似）的依赖关系评价某一分类（属性）的重要性剔除冗余属性数据集的降维发现数据模式挖掘决策规则在其它领域的应用金融商业第17页/共70页9.3粗糙集理论的基本原理粗糙集理论的基本原理“知识知识”的定义使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R)基本概念基本概念第18页/共70页基本概念（续基本概念（续1）“信

15、息系统信息系统”的形式化定义的形式化定义S=U,Q,V,f，U：对象的有限集Q：属性的有限集，Q=CD，C是条件属性子集，D是决策属性子集V：，Vp是属性P的域f：U A V是总函数，使得 对每个xi U,q A,有f(xi,q)Vq一个关系数据库可看作一个信息系统，其一个关系数据库可看作一个信息系统，其“列列”为为“属性属性”，“行行”为为“对象对象”。第19页/共70页基本概念（续基本概念（续2）基本集合基本集合（Elementaryset）/原子原子(Atom)关系R的等价类(Equivalenceclasses)U/R表示近似空间A上所有的基本集合（原子）不可区分（等价、不分明）关系不

16、可区分（等价、不分明）关系U为论域，R是UU上的等价(Equivalence)关系（即满足自反、对称、传递性质）A=U,R称为近似空间，R为不分明关系(indiscernibility，或不可区分关系、等价关系)若x,yU，(x,y)R，则x,y在A中是不分明的（不可区分的）第20页/共70页基本概念（续基本概念（续3）不可区分（等价、不分明）关系（续）不可区分（等价、不分明）关系（续）设PQ，xi,xj U,定义二元关系INDP称为不分不分明关系明关系为：称xi,xj在S中关于属性集P是不分明的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi,xj不能用P中的属性加以区别。若x,yU

17、，(x,y)R，则x,y在A中是不分明的（不可区分的）对所有的pP，INDP是U上一种的等价关系第21页/共70页factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6mistynot icynightno不可区分关系（等价关系）示例不可区分关系（等价关系）示例第22页/共70页可知，U=1,2,3,4,5,6R=2 weather,road,time,accident 若P=weather,road，则xIND(p)=

18、xINDweatherxINProad =1,3,6,2,5,4 1,2,4,3,5,6 =1,2,4,3,6,5 不可区分关系（等价关系）示例（续）不可区分关系（等价关系）示例（续）第23页/共70页集合的上近似集合的上近似&下近似下近似在信息系统S=U,Q,V,f中，设XU是个体全域上的子集，PQ则X的下和上近似集及边界区域分别为：PX是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集；X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。Bnd(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。第24页/共70页图9.1 集合的上、下近似概念示意X第2

19、5页/共70页上、下近似关系举例：上、下近似关系举例：X1=u|Flu(u)=yes=u2,u3,u6,u7RX1=u2,u3=u2,u3,u6,u7,u5,u8X2=u|Flu(u)=no=u1,u4,u5,u8RX2=u1,u4 =u1,u4,u5,u8,u6,u7TheindiscernibilityclassesdefinedbyR=Headache,Temp.are:u1,u2,u3,u4,u5,u7,u6,u8.第26页/共70页上、下近似集的图示：上、下近似集的图示：R=Headache,Temp.U/R=u1,u2,u3,u4,u5,u7,u6,X1=u|Flu(u)=yes=

20、u2,u3,u6,u7X2=u|Flu(u)=no=u1,u4,u5,u8RX1=u2,u3=u2,u3,u6,u7,u5,u8RX2=u1,u4 =u1,u4,u5,u8,u6,u7u1u4u3X1X2u5u7u2u6u8第27页/共70页近似精度近似精度&分类质量分类质量设S=U,Q,V,f为一信息系统，且XU，PQ，则S上X的近似精度近似精度为：设S为一信息系统，PQ，且令=X1,X2,Xn是U的一个分类（子集族），其中XiU，则的P-下近似和P-上近似分别表示为：第28页/共70页分类分类 的的近似精度近似精度为：为：由属性子集PQ确定的分类的分类质量分类质量为：分类质量分类质量表示通

21、过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。第29页/共70页 一个申请信用卡的训练集：一个申请信用卡的训练集：申请人申请人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(

22、1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝第30页/共70页原始属性集A=c1,c2,c3,c4的分类质量：令R=c2,c4，重新计算分类质量，得第31页/共70页属性约简属性约简&“核核”属属性性约约简简(AttributeReduction)：在一个信息系统S中，设是S上的一个分类，经约简后的最小属性子集具有同原始属性集相同的分类质量，即存在RPQ，使得R()=P()，称 之 为 属属 性性 集集 P P的的 -约约 简简，记 作REDU(P)。所 有-约 简 的 交 集 称 为 -核核，即 C

23、ORE(P)=REDU(P)，核是信息系统中一系列最重要的属性。【说说明明】：在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属属性性约约简简及及核核的的概概念念为为提提取取系系统统中中重重要要属属性性及及其其值值提提供供了了有有力力的的数数学学工工具具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。第32页/共70页关于核的计算，有人提出了差别矩阵（discernibilitymatrix，也译作可辨识矩阵）。在信息系统S=(U,CD,V,f)中，C为条件属性，D为决策属性，设为对象全集U按决策属性D被分成不相

24、交的类族，即=X1,X2,Xm，则S中C的差别矩阵M(C)=mi,jnxn定义为其中，1ijn。差别矩阵与信息系统的核有如下关系：对所有的cC,cCORE(C,D)的充要条件是，存在i,j(1ijn)，使得mi,j=c。“含糊”是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，xi,xj是含糊的充要条件是存在i,j(1 i j n)，使得mi,j=-1。第33页/共70页申请申请人人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(

25、300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝第34页/共70页 因决策d=接受，拒绝，故上表按决策属性d可分为两个等价类：x1,x4,x6,x7和x2,x3,x5,x8。根据差别矩阵的计算公式可得：差别矩阵与“核”有如下关系：属性c是条件属性C和决策属性D的“核”的充要条件是，存在i

26、,j(1ijn)，使得mij=c。由上述矩阵可知，存在i=4,j=5，使得m4,5=c2，故表1的“核”为c2。第35页/共70页 实例：考虑下面的决策表，条件属性为a,b,c,d，决策属性为e。U/Aabcdeu110210u200121u320210u400222u511210第36页/共70页uu1u2u3u4u5u1u2a,c,du3a,c,du4a,dca,du5a,b,c,da,b,d由上述差别矩阵很容易得到核为：c差别函数fM(S)为：c(ad)，即(ac)(cd)得到两个约简a,c和c,d第37页/共70页根据得到的两个约简，可得两个约简后的新决策表UAaceu1120u201

27、1u3220u4022u5120UAcdeu1210u2121u3210u4222U5210第38页/共70页例如：下表是医学诊断的一个信息系统I=(U,A)。其中，U=e1,e2,.,e7,A=A,TF。为方便表达，用1表示“是”，0表示“否”；2表示体温“很高”，1表示体温“高”，0表示体温“正常”，则表1.1的简化形式如表2所示。表医学诊断信息系统的描述实例头痛A体温T流感流感Fe1是正常否否e2是高是是e3是很高是是e4否正常否否e5否高否否e6否很高是是第39页/共70页表表简化后的决策系统简化后的决策系统UATFe1100e2111e3121e4000e5010e6021e1e4e

28、5e2(T,1)(A,1)(T,1)(A,1)e3(T,2)(A,1)(T,2)(A,1)(T,2)e6(A,0)(T,2)(T,2)(T,2)表表对应决策为对应决策为1的决策矩阵的决策矩阵第40页/共70页 将决策矩阵中的每行的元素进行合取，然后进行简化，得到相应的必然规则：(T,1)(A,1)(T,1)(A,1)(F,1)得(T,1)(A,1)(F,1)(1)(T,2)(A,1)(T,2)(A,1)(T,2)(F,1)得(T,2)(A,1)(F,1)(2)(A,0)(T,2)(T,2)(T,2)(F,1)得(T,2)(A,0)(F,1)(3)又由（2）和（3）式可知，不管属性A（头痛）是否

29、发生，只要属性T（体温）“很高”（值为2）时，则决策属性F（流感）一定为1，即表明一定是得了“流感”，故有(T,2)(F,1)(4)第41页/共70页属性之间的相关程度属性之间的相关程度在 信 息 系 统 S=(U,CD,V,f)中，设 D*=X1,X2,Xm，属性子集PC关于决策属性D的“正正区区域域”定义为：P关于D的正区域表示那些根据属性子集P就能正确分入的所有对象。条件属性子集PC与决策属性D的相相关关程程度度（也称依依赖赖程度程度）定义为：显然，0k(P,D)1。k(P,D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。第42页/共70页一个属性pPC的有效值有

30、效值(significantvalue)定义为：【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。属性的有效值（重要性）属性的有效值（重要性）第43页/共70页申请申请人人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝

31、拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝第44页/共70页已知上表的“核”CORE(C,D)=c2，设R=CORE(C,D)=c2，计算属性A的重要性程度：属性的重要性计算举例属性的重要性计算举例第45页/共70页属性的重要性计算举例（续）属性的重要性计算举例（续）第46页/共70页属属性性值值约约简简(AttributeValueReduction)也称最小复合(MinimalComplex)。设B是一个由决策值对(d,w)表示的所有对象（概念）的下或上近似，集合

32、B依赖于一个属性值对的集合T，当且仅当集合T是B的最小复合，当且仅当B依赖于T，且无ST，使得B依赖于S。属性值约简属性值约简第47页/共70页No.No.AgeAgepregnancpregnanciesiesbody-fatbody-fatCholestCholesterolerolBreast-Breast-cancercancer1 129.4129.411.41.418.2818.28188.197188.197nono2 242.5642.561.41.418.2818.28198.320198.320nono3 342.5642.560 029.3729.37198.320198

33、.320yesyes4 429.4129.410 029.3729.37198.320198.320yesyes5 557.6457.641.41.418.2818.28198.320198.320nono6 642.5642.561.41.418.2818.28188.197188.197yesyes7 729.4129.411.41.418.2818.28188.197188.197nono8 842.5642.561.41.429.3729.37198.320198.320yesyes9 957.6457.641.41.429.3729.37198.320198.320yesyes101

34、057.6457.641.41.418.2818.28188.197188.197nono第48页/共70页 设a=Age，b=pregnancies，c=body-fat，d=Cholesterol，条件属性C=a,b,c,d，决策属性D=Breast-cancer，得如下差别矩阵：得“核”CORE(C,D)=a,c,d。经属性约简后，删除多余属性c，即pregnancies，故得如下表所示的简化决策表。第49页/共70页No.Agebody-fatCholesterolBreast-cancer129.4118.28188.197no242.5618.28198.320no342.5629

35、.37198.320yes429.4129.37198.320yes557.6418.28198.320no642.5618.28188.197yes729.4118.28188.197no842.5629.37198.320yes957.6429.37198.320yes1057.6418.28188.197no第50页/共70页由上表可知，该表存在两个决策值对：(Breast-cancer,no)和(Breast-cancer,yes)，且D1=(Breast-cancer,no)=x1,x2,x5,x7,x10D2=(Breast-cancer,yes)=x3,x4,x6,x8,x9此外

36、，有如下属性值对：A1=(Age,29.41)=x1,x4,x7A2=(Age,42.56)=x2,x3,x6,x8A3=(Age,57.64)=x5,x9,x10B1=(body-fat,18.28)=x1,x2,x5,x6,x7,x10B2=(body-fat,29.37)=x3,x4,x8,x9C1=(Cholesterol,188.197)=x1,x6,x7,x10C2=(Cholesterol,198.320)=x2,x3,x4,x5,x8,x9第51页/共70页(1)因B2=(body-fat,29.37)=x3,x4,x8,x9 D2=(Breast-cancer)=x3,x4,

37、x6,x8,x9，令T=B2，T即为B的最小复合，故可得规则：(body-fat,29.37)(Breast-cancer,yes)(1)同时，根据最小复合的定义可知，任何与B2一起构成集合T的情况，均非最小复合。(2)由于A1D1且A1D2，B1D1且B1D2，令T=A1,B1，即T=A1,B1=x1,x4,x7,x1,x2,x5,x6,x7,x10，有且不存在T T，使得B依赖于T，故可得规则(Age,29.41)&(%body-fat,18.28)(Breast-cancer,no)(2)第52页/共70页(3)同理，令T=A1,C1，得【说明说明】：虽然T=A1,C1也是一个最小复合，

38、但由于交集x1,x7与(2)中相同，说明两者实际上是同一条规则，故应略去。要略去哪一条规则（或者说要保留哪一条规则），则还需考虑哪些属性更重要，即应取最关键的属性所组成的规则。在该例中，由差别矩阵的计算结果可知，属性body-fat的重要性大于属性Cholesterol，因此略去A1与C1组成的规则。属性值约简举例（续）属性值约简举例（续）第53页/共70页 (4)令T=A1,C2，得A1C2=x4B2，故此种情况已被B2所包含，故不必单独生成一条规则。(5)令T=A2,B1，得A2B1=x2,x6D1，且D2，故不能生成一条规则。(6)令T=A2,C1，得A2C1=x6D2=x3,x4,x6

39、,x8,x9，故有(Age,42.56)&(Cholesterol,188.197)(Breast-cancer,yes)(3)(7)令T=A2,C2，得A2C2=x2,x3,x8D1，且D2，故不能生成一条规则。(8)令T=A3,B1，得A3B1=x5,x10D1=x1,x2,x5,x7,x10，故有(Age,57.64)&(body-fat,18.28)(Breast-cancer,no)(4)第54页/共70页(9)令T=A3,C1，得A3C1=x10A3B1=x5,x10，故已被规则(4)所包含，无需生成一条规则。(10)令T=A3,C2，得A3C2=x5,x9D1，且D2，故不能生成

40、一条规则。(11)令T=B1,C1，得B1 C1=C1=x1,x6,x7,x10 D1，且 D2，故不能生成一条规则。(12)令T=B1,C2，得B1 C2=x2,x5 D1=x1,x2,x5,x7,x10，有(body-fat,18.28)&(Cholesterol,198.320)(Breast-cancer,no)(5)属性值约简举例（续）属性值约简举例（续）第55页/共70页因此，共得5条规则：(body-fat,29.37)(Breast-cancer,yes)(1)(Age,29.41)&(body-fat,18.28)(Breast-cancer,no)(2)(Age,42.56

41、)&(Cholesterol,188.197)(Breast-cancer,yes)(3)(Age,57.64)&(body-fat,18.28)(Breast-cancer,no)(4)(body-fat,18.28)&(Cholesterol,198.320)(Breast-cancer,no)(5)【注意注意】：若取T=A1,B1,C1，则必然存在T的真子集T，如T=A1,B1T，或A1,C1，使得即为上述步骤(2)和(3)两种情况，表明T=A1,B1,C1不是最小复合。其余情况类似，故不赘述。第56页/共70页属性可分为定量属性(Quantitativeattributes)和定性属性

42、(Qualitativeattributes)，其中定性属性又被分成有序定性属性(Orderedqualitativeattributes)和无序定性属性(Unorderedqualitativeattributes)。如“年龄”为有序定性属性，它可分为年轻、中年及老年等；而“性别”为无序定性属性，它包含男、女两种类型，但并无一定的顺序。针对无序定性属性，有人提出了属性域约简(AttributeDomainReduction，简称ADR)的概念。属性域约简的基本思想是，设某个需要约简的无序定性属性p的属性域基数card(Vp)为N，构造一个具有N个二进制属性(binaryattribute)的

43、表，原表中属性p的每个值就相应地转化为新表的一个二进制属性，然后对新表按照属性约简的方法进行约简，即得属性域约简的结果。【说明】：若有兴趣，请参见关于Rough sets的补充材料举例说明粗糙集理论的有关概念及公式。属性域约简属性域约简第57页/共70页9.4计算实例计算实例长期以来，中东局势一直动荡不安且变幻莫测，有人对该地区的局势进行了较深入的研究，并总结出中东局势所牵涉的主要国家/地区及其关心的主要问题，如下表所示。第58页/共70页主要主要问题问题国国家家地地区区建立自建立自治的巴勒治的巴勒斯坦国斯坦国(a)以色列以色列沿着约旦沿着约旦河部署军河部署军队（队（b）以占以占领东耶领东耶路

44、撒冷路撒冷(c)以军驻以军驻守在戈兰守在戈兰高地高地(d)承认巴勒承认巴勒斯坦人国籍斯坦人国籍(e)UN大会大会的决的决议议(f)1：以：以色列色列反对反对赞同赞同赞同赞同赞同赞同赞同赞同Reject2:埃埃及及赞同赞同中立中立反对反对反对反对反对反对Accept3：巴：巴勒斯坦勒斯坦赞同赞同反对反对反对反对反对反对中立中立Accept4：约：约旦旦中立中立反对反对反对反对中立中立反对反对Reject5：叙：叙利亚利亚赞同赞同反对反对反对反对反对反对反对反对Reject6：沙：沙特阿特阿拉拉伯伯中立中立赞同赞同反对反对中立中立赞同赞同Reject第59页/共70页其中，联合国（UN）大会的决议

45、(f)为决策属性，其它均为条件属性。问题1：请利用RoughSet理论中的相关原理及公式计算下列问题：（1）试写出根据决策属性f所得到的等价类。（2）设P=a,c，试分别计算决策属性f分别为Reject和Accept时的下近似PX和上近似P*X。【注意】：应该有四个近似集。（3）请写出差别矩阵（DiscernibilityMatrix），并给出“核”（Core）。（4）请根据差别函数计算属性约简，并给出最佳约简属性。第60页/共70页问题2：针对上表中的数据，试根据Shannon信息熵计算公式和决策树中的ID3算法求解下列问题：（1）请分别选择a,b,c,d,e作为测试属性时，试求出它们的条件

46、熵。（2）请画出依据信息熵和ID3算法对上表中给出的实例集所生成的决策树。问题3：请比较两种方法所得结果，并解释之。计算实例（续）计算实例（续）待求解问题待求解问题第61页/共70页实例分析（续）：关于问题实例分析（续）：关于问题(1)的解答的解答【问题问题(1)(1)】：试写出根据决策属性f所得到的等价类。【解答解答】：对决策属性f而言，有2个等价类，分别为对应于Reject：1,4,5对应于Accept：2,3,6第62页/共70页实例分析（续）：关于问题实例分析（续）：关于问题(2)的解答的解答【问题问题(2)(2)】：设P=a,c，试分别计算决策属性f分别为Reject和Accept时

47、的下近似PX和上近似P*X。【注意】：应该有四个近似集。【解答解答】：因P=a,c，故有U/P=1,2,3,5,4,6对应于Reject，因其等价类为1,4,5，故有下近似集：1上近似集：1,2,3,4,5,6对应于Accept，因其等价类为2,3,6，故有下近似集：上近似集：2,3,4,5,6第63页/共70页实例分析（续）：关于问题实例分析（续）：关于问题(3)的解答的解答【问题问题(3)(3)】：请写出差别矩阵（DiscernibilityMatrix），并给出“核”（Core）。【解答解答】：差别矩阵为：“核”为：b,e第64页/共70页实例分析（续）：关于问题实例分析（续）：关于问题

48、(4)的解答的解答【问题问题(4)(4)】：请根据差别函数计算属性约简，并给出最佳约简属性。【解答解答】：由分类质量计算公式可知，原始属性集的分类质量为1，又因“核”为b,e，故可能的属性约简为：a,b,eb,d,e根据分类质量计算公式可知，上述2种属性约简的分类质量均为1，都是最佳属性约简。第65页/共70页实例分析（续）：课后习题实例分析（续）：课后习题问题2：课后习题。问题3：课后习题。第66页/共70页课后研读论文课后研读论文1Pawlak,Z.,et al.Roughsetapproachtomulti-attributedecisionanalysis.European Journ

49、al of Operational Research,72:443-459,19942 Grzymala-Busse,D.M.,et al.The Usefulness of amachine learning approach to knowledge acquisition.Computational Intelligence.11(2):268-279,19953Jelonek,J.,et al.Roughsetreductionofattributesandtheir domains for neural networks.Computational Intelligence,11(2

50、):339-347,1995【说明】：文献1必读，文献2,3可选。第67页/共70页THANKSFORYOURPRESENCE!“ForsincethecreationoftheworldGodsinvisiblequalitieshiseternalpoweranddivinenaturehavebeenclearlyseen,beingunderstoodfromwhathasbeenmade,sothatmenarewithoutexcuse.”from ROMANS 1:20 NIV第68页/共70页谢谢提出宝贵意见！谢谢提出宝贵意见！第69页/共70页感谢您的观看。感谢您的观看。第7