浙江大学研究生《人工智能引论》课件-第六讲-粗糙集理论及其应用

浙江大学研究生《人工智能引论》课件

PhD,AssociateProfessorEmail:InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaNovember18,2002第一稿September30,2006第四次修改稿第六讲粗糙集理论及其应用

(Chapter6RoughSetsTheoryandItsApplications)1感谢你的观看2019年8月23浙江大学研究生《人工智能引论》课件PhD,AssociaOutlineRoughsets理论的快速入门方法Roughsets理论的发展概述Roughsets理论的基本原理计算举例课后研读论文2感谢你的观看2019年8月23OutlineRoughsets理论的快速入门方法2感谢你6.1Roughsets的快速入门方法认真研读RoughSetsTheory的创始人、波兰数学家Z.Pawlak于1982年发表的第一篇论文“RoughSets”。【注】：最好直接阅读英文论文原文。

研读王珏等人1996年在《模式识别与人工智能》上发表的关于RoughSets理论及其应用的综述性文章。参考史忠植编著的《高级人工智能》、《知识发现》等教材中讨论粗糙集的有关章节。【注】：国内王国胤、刘清、张文修、曾黄麟等人先后出版了关于RoughSets的教材，也可适当参考。3感谢你的观看2019年8月236.1Roughsets的快速入门方法认真研读RougRoughset快速入门方法（续）认真研读如下3篇典型的论文：

[1]Pawlak,Z.,etal.Roughsetapproachtomulti-attributedecisionanalysis.EuropeanJournalofOperationalResearch,72:443-459,1994[2]Grzymala-Busse,D.M.,etal.Theusefulnessofamachinelearningapproachtoknowledgeacquisition.ComputationalIntelligence.11(2):268-279,1995[3]Jelonek,J.,etal.Roughsetreductionofattributesandtheirdomainsforneuralnetworks.ComputationalIntelligence,11(2):339-347,1995结合本课件作者于2000年整理的《举例说明粗糙集理论的有关概念及公式》

4感谢你的观看2019年8月23Roughset快速入门方法（续）认真研读如下3篇典型的论

6.2粗糙集理论的发展概述

6.2.1粗糙集理论的提出

自然界中大部分事物所呈现的信息都是：

◆

不完整的、不确定的、模糊的和含糊的

◆经典逻辑无法准确、圆满地描述和解决

粗糙集理论主要是为了描述并处理“含糊”信息。“Blessedarethemerciful,fortheywillbeshownmercy.Blessedarethepureinheart,fortheywillseeGod.”

FromMATTHEW5:7-8NIV

5感谢你的观看2019年8月236.2粗糙集理论的发展概述“Blessedaret粗糙集理论的提出（续1）“含糊”（Vague）1904年谓词逻辑创始人G.Frege(弗雷格)首次提出将含糊性归结到“边界线区域”(Boundaryregion)在全域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上……“模糊集”（FuzzySets）1965年美国数学家L.A.Zadeh首次提出无法解决G.Frege提出的“含糊”问题未给出计算含糊元素数目的数学公式……6感谢你的观看2019年8月23粗糙集理论的提出（续1）“含糊”（Vague）6感谢你的观看粗糙集理论的提出（续2）“粗糙集”（RoughSets）1982年波兰数学家Z.Pawlak首次提出将边界线区域定义为“上近似集”与“下近似集”的差集指出在“真”、“假”二值之间的“含糊度”是可计算的给出计算含糊元素数目的计算公式借鉴了集合论中的“等价关系”（不可区分关系）求取大量数据中的最小不变集合（称为“核”）求解最小规则集（称为“约简”）……7感谢你的观看2019年8月23粗糙集理论的提出（续2）“粗糙集”（RoughSets）7粗糙集理论的提出（续3）粗糙集理论中的一些基本观点“概念”就是对象的集合“知识”就是将对象进行分类的能力(“各从其类”)“知识”是关于对象的属性、特征或描述的刻划不可区分关系表明两个对象具有相同的信息提出上近似集、下近似集、分类质量等概念……“Godmadethewildanimalsaccordingtotheirkinds,thelivestockaccordingtotheirkinds,andallthecreaturesthatmovealongthegroundaccordingtotheirkinds.AndGodsawthatitwasgood.”

FromGENESIS1:25NIV

8感谢你的观看2019年8月23粗糙集理论的提出（续3）粗糙集理论中的一些基本观点“God6.2.2粗糙集理论的发展历程1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。1982年，Pawlak发表经典论文《Roughsets》，标志着该理论正式诞生。9感谢你的观看2019年8月236.2.2粗糙集理论的发展历程1970s，Pawlak和粗糙集理论的发展历程（续1）1991年，Pawlak的第一本关于粗糙集理论的专著《Roughsets:theoreticalaspectsofreasoningaboutdata》；1992年，Slowinski主编的《Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的《Foundationofcomputinganddecisionsciences》上。10感谢你的观看2019年8月23粗糙集理论的发展历程（续1）1991年，Pawlak的第一本粗糙集理论的发展历程（续2）1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。1995年，Pawlak等人在《ACMCommunications》上发表“Roughsets”，极大地扩大了该理论的国际影响。1996～1999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。2000年，在加拿大召开了第二届粗糙集与计算趋势国际会议。11感谢你的观看2019年8月23粗糙集理论的发展历程（续2）1993和1994年，分别在加拿粗糙集理论的发展历程（续3）2001～2002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（年会）。2005年，在加拿大召开RSFDGrC国际会议（年会）。……12感谢你的观看2019年8月23粗糙集理论的发展历程（续3）2001～2002，中国分别在重6.2.3粗糙集理论的优点及局限性主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观……【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。“Nowfaithisbeingsureofwhatwehopeforandcertainofwhatwedonotsee.”“AndwithoutfaithitisimpossibletopleaseGod,becauseanyonewhocomestohimmustbelievethatheexistsandthatherewardsthosewhoearnestlyseekhim.”FromHEBREWS11:1,6NIV13感谢你的观看2019年8月236.2.3粗糙集理论的优点及局限性主要优点“Nowfa粗糙集理论的优点及局限性（续）局限性缺乏处理不精确或不确定原始数据的机制对含糊概念的刻划过于简单无法解决所有含糊的、模糊的不确定性问题需要其它方法的补充……解决办法与模糊集理论相结合与Dempster-Shafer证据理论相结合……14感谢你的观看2019年8月23粗糙集理论的优点及局限性（续）局限性14感谢你的观看20196.2.4粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对遗失数据的填补。在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。15感谢你的观看2019年8月236.2.4粗糙集理论在知识发现中的作用在数据预处理过程中粗糙集理论在知识发现中的作用（续）在数据挖掘阶段的主要作用通过布尔推理挖掘出约简的规则来解释决策通过熵理论将规则的复杂性和预测的误差分析溶入到无条件的度量中与模糊集理论、证据理论构成复合分析方法搜寻隐含在数据中的确定性或非确定性的规则……在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。16感谢你的观看2019年8月23粗糙集理论在知识发现中的作用（续）在数据挖掘阶段的主要作用16.2.5粗糙集理论的研究现状在理论研究方面数学性质：研究其代数与拓扑结构、收敛性等粗糙集拓广：广义粗糙集模型、连续属性离散化与其它不确定性处理方法的关系和互补：与模糊集理论、Dempster-Shafer证据理论的关系和互补粒度计算：粗糙集理论是其重要组成之一高效算法：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进……17感谢你的观看2019年8月236.2.5粗糙集理论的研究现状在理论研究方面17感谢你的粗糙集理论的研究现状（续）在数据挖掘领域的应用发现数据之间（精确或近似）的依赖关系评价某一分类（属性）的重要性剔除冗余属性数据集的降维发现数据模式挖掘决策规则在其它领域的应用金融商业……18感谢你的观看2019年8月23粗糙集理论的研究现状（续）在数据挖掘领域的应用18感谢你的观6.3粗糙集理论的基本原理“知识”的定义使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R)6.3.1基本概念19感谢你的观看2019年8月236.3粗糙集理论的基本原理“知识”的定义6.3.1基基本概念（续1）“信息系统”的形式化定义S={U,Q,V,f}，U：对象的有限集Q：属性的有限集，Q=C

D，C是条件属性子集，D是决策属性子集V：，Vp是属性P的域f：U×A→

V是总函数，使得

对每个xi

U,q

A,有f(xi,q)Vq一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“对象”。20感谢你的观看2019年8月23基本概念（续1）“信息系统”的形式化定义20感谢你的观看20基本概念（续2）基本集合（Elementaryset）/原子(Atom)关系R的等价类(Equivalenceclasses)U/R表示近似空间A上所有的基本集合（原子）不可区分（等价、不分明）关系U为论域，R是U

U上的等价(Equivalence)关系（即满足自反、对称、传递性质）A={U,R}称为近似空间，R为不分明关系(indiscernibility，或不可区分关系、等价关系)若x,y

U，(x,y)

R，则x,y在A中是不分明的（不可区分的）21感谢你的观看2019年8月23基本概念（续2）基本集合（Elementaryset）/基本概念（续3）不可区分（等价、不分明）关系（续）设P

Q，xi,xj

U,定义二元关系IND

P

称为不分明关系为：称xi,xj在S中关于属性集P是不分明的，当且仅当p(xi)=p(xj)对所有的p

P成立，即xi,xj不能用P中的属性加以区别。若x,y

U，(x,y)

R，则x,y在A中是不分明的（不可区分的）对所有的p

P，IND

P

是U上一种的等价关系22感谢你的观看2019年8月23基本概念（续3）不可区分（等价、不分明）关系（续）22感谢你不可区分关系（等价关系）示例23感谢你的观看2019年8月23不可区分关系（等价关系）示例23感谢你的观看2019年8月2可知，U={1,2,3,4,5,6}R=2{weather,road,time,accident}若P={weather,road}，则[x]IND(p)=[x]IND{weather}

[x]INP{road}={{1,3,6},{2,5},{4}}

{{1,2,4},{3,5,6}}={{1},{2},{4},{3,6},{5}}不可区分关系（等价关系）示例（续）24感谢你的观看2019年8月23可知，不可区分关系（等价关系）示例（续）24感谢你的观看206.3.2集合的上近似&下近似

在信息系统S={U,Q,V,f}中，设X

U是个体全域上的子集，P

Q则X的下和上近似集及边界区域分别为：

PX是X

U上必然被分类的那些元素的集合，即包含在X内的最大可定义集；

X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。Bnd(X)是既不能在X

U上被分类，又不能在U-X上被分类的那些元素的集合。25感谢你的观看2019年8月236.3.2集合的上近似&下近似PX是XU上必然

图6.1集合的上、下近似概念示意X26感谢你的观看2019年8月23 X26感谢你的观看2019年8月23上、下近似关系举例：

X1={u|Flu(u)=yes}={u2,u3,u6,u7}

RX1={u2,u3}

={u2,u3,u6,u7,u5,u8}X2={u|Flu(u)=no}={u1,u4,u5,u8}

RX2={u1,u4}

={u1,u4,u5,u8,

u6,u7}TheindiscernibilityclassesdefinedbyR={Headache,Temp.}are:{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.27感谢你的观看2019年8月23上、下近似关系举例：X1={u|Flu(u)=上、下近似集的图示：R={Headache,Temp.}U/R={{u1},{u2},{u3},{u4},{u5,u7},{u6,X1={u|Flu(u)=yes}={u2,u3,u6,u7}X2={u|Flu(u)=no}={u1,u4,u5,u8}RX1={u2,u3}

={u2,u3,u6,u7,u5,u8}RX2={u1,u4}={u1,u4,u5,u8,u6,u7}u1u4u3X1X2u5u7u2u6u828感谢你的观看2019年8月23上、下近似集的图示：RX1={u2,u3}RX26.3.3近似精度&分类质量

设S={U,Q,V,f}为一信息系统，且X

U，P

Q，则S上X的近似精度为：设S为一信息系统，P

Q，且令

={X1,X2,…,Xn}是U的一个分类（子集族），其中Xi

U，则

的P-下近似和P-上近似分别表示为：29感谢你的观看2019年8月236.3.3近似精度&分类质量设S为一信息分类

的近似精度为：

由属性子集P

Q确定的分类

的分类质量为：分类质量表示通过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。

30感谢你的观看2019年8月23分类的近似精度为：由属性子集PQ确定的分类的分类质量

一个申请信用卡的训练集：申请人编号条件属性决策属性dc1账号c2余额c3职业c4月消费1银行中(700)有低接受2银行低(300)有高拒绝3无低(0)有中拒绝4其它机构高(1200)有高接受5其它机构中(800)有高拒绝6其它机构高(1600)有低接受7银行高(3000)无中接受8无低(0)无低拒绝

31感谢你的观看2019年8月23

一个申请信用卡的训练集：申请人条件属性决策属性c1c2c原始属性集A={c1,c2,c3,c4}的分类质量：令R={c2,c4}，重新计算分类质量，得32感谢你的观看2019年8月23原始属性集A={c1,c2,c3,c4}的分类质量

6.3.4属性约简&“核”

属性约简(AttributeReduction)：在一个信息系统S中，设

是S上的一个分类，经约简后的最小属性子集具有同原始属性集相同的分类质量，即存在R

P

Q，使得

R()=P()，称之为属性集P的

-约简，记作REDU

(P)。所有

-约简的交集称为

-核，即CORE

(P)=

REDU

(P)，核是信息系统中一系列最重要的属性。

【说明】：在大多数情况下，分类是由几个甚至一个属性来决定的，而不是由关系数据库中的所有属性的微小差异来决定。属性约简及核的概念为提取系统中重要属性及其值提供了有力的数学工具，而且这种约简是本着不破坏原始数据集的分类质量的，通俗地说，它是完全“保真”的。33感谢你的观看2019年8月236.3.4属性约简&“核”33感谢你的观看

关于核的计算，有人提出了差别矩阵（discernibilitymatrix，也译作可辨识矩阵）。在信息系统S=(U,C

D,V,f)中，C为条件属性，D为决策属性，设为对象全集U按决策属性D被分成不相交的类族，即={X1,X2,…,Xm}，则S中C的差别矩阵M(C)={mi,j}nxn定义为其中，1

i

j

n。

差别矩阵与信息系统的核有如下关系：对所有的c

C,c

CORE(C,D)的充要条件是，存在i,j(1

i

j

n)，使得mi,j={c}。“含糊”是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，xi,xj是含糊的充要条件是存在i,j(1

i

j

n)，使得mi,j={-1}。

34感谢你的观看2019年8月23关于核的计算，有人提出了差别矩阵（discernib

申请人编号条件属性

决策属性dc1账号c2余额c3职业c4月消费1银行中(700)有低接受2银行低(300)有高拒绝3无低(0)有中拒绝4其它机构高(1200)有高接受5其它机构中(800)有高拒绝6其它机构高(1600)有低接受7银行高(3000)无中接受8无低(0)无低拒绝35感谢你的观看2019年8月23

条件属性

c1c2c3c41银行中(700)有低接受2银行

因决策d={接受，拒绝}，故上表按决策属性d可分为两个等价类：{x1,x4,x6,x7}和{x2,x3,x5,x8}。根据差别矩阵的计算公式可得：

差别矩阵与“核”有如下关系：属性c是条件属性C和决策属性D的“核”的充要条件是，存在i,j(1<i<j<n)，使得mij={c}。由上述矩阵可知，存在i=4,j=5，使得m4,5={c2}，故表1的“核”为{c2}。36感谢你的观看2019年8月23因决策d={接受，拒绝}，故上表按决策属性d可分

实例：考虑下面的决策表，条件属性为a,b,c,d，决策属性为e。U/Aabcdeu110210u200121u320210u400222u51121037感谢你的观看2019年8月23实例：考虑下面的决策表，条件属性为a,b,c,d，决策uu1u2u3u4u5u1

u2a,c,d

u3

a,c,d

u4a,dca,d

u5

a,b,c,d

a,b,d

由上述差别矩阵很容易得到核为：{c}差别函数fM(S)为：c∧(a∨d)，即(a∧c)∨(c∧d)得到两个约简{a,c}和{c,d}38感谢你的观看2019年8月23uu1u2u3u4u5u1

u2a,c,d

根据得到的两个约简，可得两个约简后的新决策表U\Aaceu1120u2011u3220u4022u5120U\Acdeu1210u2121u3210u4222U521039感谢你的观看2019年8月23根据得到的两个约简，可得两个约简后的新决策表U\Aaceu1例如：下表是医学诊断的一个信息系统I=(U,A) 。其中，U={e1,e2,...,e7},A={A,T}

{F}。为方便表达，用1表示“是”，0表示“否”；2表示体温“很高”，1表示体温“高”，0表示体温“正常”，则表1.1的简化形式如表2所示。表医学诊断信息系统的描述40感谢你的观看2019年8月23例如：下表是医学诊断的一个信息系统I=(U,A) 。其中，表简化后的决策系统表对应决策为1的决策矩阵41感谢你的观看2019年8月23表简化后的决策系统表对应决策为1的决策矩阵41感

将决策矩阵中的每行的元素进行合取，然后进行简化，得到相应的必然规则：(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（头痛）是否发生，只要属性T（体温）“很高”（值为2）时，则决策属性F（流感）一定为1，即表明一定是得了“流感”，故有

(T,2)(F,1) (4)42感谢你的观看2019年8月23将决策矩阵中的每行的元素进行合取，然后进行简化，得到相6.3.5属性之间的相关程度

在信息系统S=(U,C

D,V,f)中，设D*={X1,X2,…,Xm}，属性子集P

C关于决策属性D的“正区域”定义为：

P关于D的正区域表示那些根据属性子集P就能正确分入的所有对象。条件属性子集P

C与决策属性D的相关程度（也称依赖程度）定义为：显然，0

k(P,D)

1。k(P,D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。43感谢你的观看2019年8月236.3.5属性之间的相关程度P关于D的正区域表示那些根一个属性p

P

C的有效值(significantvalue)定义为：【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，即其重要性也越大。6.3.6属性的有效值（重要性）44感谢你的观看2019年8月23一个属性pPC的有效值(significantvalu

申请人编号条件属性

决策属性dc1账号c2余额c3职业c4月消费1银行中(700)有低接受2银行低(300)有高拒绝3无低(0)有中拒绝4其它机构高(1200)有高接受5其它机构中(800)有高拒绝6其它机构高(1600)有低接受7银行高(3000)无中接受8无低(0)无低拒绝45感谢你的观看2019年8月23

条件属性

c1c2c3c41银行中(700)有低接受2银行已知上表的“核”CORE(C,D)={c2}，设R=CORE(C,D)={c2}，计算属性A的重要性程度：属性的重要性计算举例46感谢你的观看2019年8月23已知上表的“核”CORE(C,D)={c2}，属性的重属性的重要性计算举例（续）47感谢你的观看2019年8月23属性的重要性计算举例（续）47感谢你的观看2019年8月23属性值约简(AttributeValueReduction)也称最小复合(MinimalComplex)。设B是一个由决策值对(d,w)表示的所有对象（概念）的下或上近似，集合B依赖于一个属性值对的集合T，当且仅当集合T是B的最小复合，当且仅当B依赖于T，且无S

T，使得B依赖于S。6.3.7属性值约简48感谢你的观看2019年8月23属性值约简(AttributeValueNo.Agepregnanciesbody-fatCholesterolBreast-cancer129..411..418..28188..197no242..561..418..28198..320no342..56029..37198..320yes429..41029..37198..320yes557..641..418..28198..320no642..561..418..28188..197yes729..411..418..28188..197no842..561..429..37198..320yes957..641..429..37198..320yes1057..641..418..28188..197no49感谢你的观看2019年8月23No.Agepregnanciesbody-fatChole

设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，故得如下表所示的简化决策表。50感谢你的观看2019年8月23设a=Age，b=pregnancies，cNo.Agebody-fatCholesterolBreast-cancer129..4118..28188..197no242..5618..28198..320no342..5629..37198..320yes429..4129..37198..320yes557..6418..28198..320no642..5618..28188..197yes729..4118..28188..197no842..5629..37198..320yes957..6429..37198..320yes1057..6418..28188..197no51感谢你的观看2019年8月23No.Agebody-fatCholesterolBreas由上表可知，该表存在两个决策值对：(Breast-cancer,no)和(Breast-cancer,yes)，且

D1=(Breast-cancer,no)={x1,x2,x5,x7,x10} D2=(Breast-cancer,yes)={x3,x4,x6,x8,x9}

此外，有如下属性值对：A1=(Age,29..41)={x1,x4,x7}A2=(Age,42..56)={x2,x3,x6,x8}A3=(Age,57..64)={x5,x9,x10}B1=(body-fat,18..28)={x1,x2,x5,x6,x7,x10}B2=(body-fat,29..37)={x3,x4,x8,x9}

C1=(Cholesterol,188..197)={x1,x6,x7,x10}C2=(Cholesterol,198..320)={x2,x3,x4,x5,x8,x9}52感谢你的观看2019年8月23由上表可知，该表存在两个决策值对：(Breast(1)因B2=(body-fat,29..37)={x3,x4,x8,x9}

D2=(Breast-cancer)={x3,x4,x6,x8,x9}，令T=B2，T即为B的最小复合，故可得规则：(body-fat,29..37)

(Breast-cancer,yes) (1)

同时，根据最小复合的定义可知，任何与B2一起构成集合T的情况，均非最小复合。

(2)由于A1

D1且A1

D2，B1

D1且B1

D2，令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)53感谢你的观看2019年8月23(1)因B2=(body-fat,29..37)=(3)同理，令T={A1,C1}，得【说明】：

虽然T={A1,C1}也是一个最小复合，但由于交集{x1,x7}与(2)中相同，说明两者实际上是同一条规则，故应略去。

要略去哪一条规则（或者说要保留哪一条规则），则还需考虑哪些属性更重要，即应取最关键的属性所组成的规则。

在该例中，由差别矩阵的计算结果可知，属性body-fat的重要性大于属性Cholesterol，因此略去A1与C1组成的规则。属性值约简举例（续）54感谢你的观看2019年8月23(3)同理，令T={A1,C1}，得【说明】：属性值

(4)令T={A1,C2}，得A1

C2={x4}

B2，故此种情况已被B2所包含，故不必单独生成一条规则。(5)令T={A2,B1}，得A2

B1={x2,x6}

D1，且

D2，故不能生成一条规则。(6)令T={A2,C1}，得A2

C1={x6}

D2={x3,x4,x6,x8,x9}，故有(Age,42..56)&(Cholesterol,188..197)

(Breast-cancer,yes)(3)

(7)令T={A2,C2}，得A2

C2={x2,x3,x8}

D1，且

D2，故不能生成一条规则。(8)令T={A3,B1}，得A3

B1={x5,x10}

D1={x1,x2,x5,x7,x10}，故有(Age,57..64)&(body-fat,18..28)

(Breast-cancer,no)(4)55感谢你的观看2019年8月23(4)令T={A1,C2}，得A1C2=

(9)令T={A3,C1}，得A3

C1={x10}

A3

B1={x5,x10}，故已被规则(4)所包含，无需生成一条规则。(10)令T={A3,C2}，得A3

C2={x5,x9}

D1，且

D2，故不能生成一条规则。(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)属性值约简举例（续）56感谢你的观看2019年8月23(9)令T={A3,C1}，得A3C1=因此，共得5条规则：(body-fat,29..37)

(Breast-cancer,yes) (1)(Age,29..41)&(body-fat,18..28)

(Breast-cancer,no)(2)(Age,42..56)&(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,B1}

T，或{A1,C1}，使得即为上述步骤(2)和(3)两种情况，表明T={A1,B1,C1}不是最小复合。其余情况类似，故不赘述。57感谢你的观看2019年8月23因此，共得5条规则：即为上述步骤(2)和(3)两种情况，表明属性可分为定量属性(Quantitativeattributes)和定性属性(Qualitativeattributes)，其中定性属性又被分成有序定性属性(Orderedqualitativeattributes)和无序定性属性(Unorderedqualitativeattributes)。如“年龄”为有序定性属性，它可分为年轻、中年及老年等；而“性别”为无序定性属性，它包含男、女两种类型，但并无一定的顺序。针对无序定性属性，有人提出了属性域约简(AttributeDomainReduction，简称ADR)的概念。

属性域约简的基本思想是，设某个需要约简的无序定性属性p的属性域基数card(Vp)为N，构造一个具有N个二进制属性(binaryattribute)的表，原表中属性p的每个值就相应地转化为新表的一个二进制属性，然后对新表按照属性约简的方法进行约简，即得属性域约简的结果。【说明】：若有兴趣，请参见关于Roughsets的补充材料《举例说明粗糙集理论的有关概念及公式》。6.3.8属性域约简58感谢你的观看2019年8月23属性可分为定量属性(Quantitative6.4计算实例长期以来，中东局势一直动荡不安且变幻莫测，有人对该地区的局势进行了较深入的研究，并总结出中东局势所牵涉的主要国家/地区及其关心的主要问题，如下表所示。59感谢你的观看2019年8月236.4计算实例长期以来，中东局势一直动荡不安且变幻莫测主要问题国家地区建立自治的巴勒斯坦国(a)以色列沿着约旦河部署军队（b）以占领东耶路撒冷(c)以军驻守在戈兰高地(d)承认巴勒斯坦人国籍(e)UN大会的决议(f)1：以色列反对赞同赞同赞同赞同Reject2:埃及赞同中立反对反对反对Accept3：巴勒斯坦赞同反对反对反对中立Accept4：约旦中立反对反对中立反对Reject5：叙利亚赞同反对反对反对反对Reject6：沙特阿拉伯中立赞同反对中立赞同Reject60感谢你的观看2019年8月23主要建立自治的巴勒斯坦国(a)以色列沿着约旦河部署军队（b）其中，联合国（UN）大会的决议(f)为决策属性，其它均为条件属性。

问题1：请利用RoughSet理论中的相关原理及公式计算下列问题：（1）试写出根据决策属性f所得到的等价类。（2）设P={a,c}，试分别计算决策属性f分别为Reject和Accept时的下近似PX和上近似P*X。【注意】：应该有四个近似集。（3）请写出差别矩阵（DiscernibilityMatrix），并给出“核”（Core）。（4）请根据差别函数计算属性约简，并给出最佳约简属性。61感谢你的观看2019年8月23其中，联合国（UN）大会的决议(f)为决策属性，其它均为条

问题2：针对上表中的数据，试根据Shannon信息熵计算公式和决策树中的ID3算法求解下列问题：（1）请分别选择a,b,c,d,e作为测试属性时，试求出它们的条件熵。（2）请画出依据信息熵和ID3算法对上表中给出的实例集所生成的决策树