粗糙集理论ppt课件.ppt

《粗糙集理论ppt课件.ppt》由会员分享，可在线阅读，更多相关《粗糙集理论ppt课件.ppt（110页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2011年年5月月粗糙集理论及其应用(Rough Sets Theory and Its Applications )中国民航大学中国民航大学粗糙集理论与机器学习粗糙集理论与机器学习研究生课件研究生课件Outline1.Rough sets1.Rough sets理论概述理论概述2.Rough sets2.Rough sets理论的基本原理理论的基本原理3. 3.信息系统约简信息系统约简4. 4.决策表约简决策表约简5. 5.离散化方法离散化方法1.1 Rough sets的快速入门方法的快速入门方法n认真研读认真研读Rough Sets TheoryRough Sets Theory的创始人

2、、波兰数学家的创始人、波兰数学家Z. Z. PawlakPawlak于于19821982年发表的第一篇论文年发表的第一篇论文“Rough SetsRough Sets”。【注】：最好直接阅读英文论文原文。 n研读王珏等人研读王珏等人19961996年在模式识别与人工智能上发年在模式识别与人工智能上发表的关于表的关于Rough SetsRough Sets理论及其应用的综述性文章。理论及其应用的综述性文章。n参考李德毅的参考李德毅的不确定性人工智能不确定性人工智能、杨善林的、杨善林的智能智能决策方法与智能决策支持系统决策方法与智能决策支持系统n参考史忠植编著的高级人工智能、知识发现等参考史忠植编

3、著的高级人工智能、知识发现等教材中讨论粗糙集的有关章节。教材中讨论粗糙集的有关章节。n【注】：国内王国胤、刘清、张文修、曾黄麟等人先后出版了关于Rough Sets的教材，也可适当参考。1.Rough sets1.Rough sets理论概述理论概述Rough set快速入门方法（续）快速入门方法（续）认真研读如下认真研读如下3 3篇典型的论文：篇典型的论文： 1 Pawlak, Z., et al. Rough set approach to multi-attribute decision analysis. European Journal of Operational Research

4、, 72: 443-459, 19942 Grzymala-Busse, D. M., et al. The usefulness of a machine learning approach to knowledge acquisition. Computational Intelligence. 11(2):268-279, 19953 Jelonek, J., et al. Rough set reduction of attributes and their domains for neural networks. Computational Intelligence, 11(2):

5、339-347, 1995 1.2 1.2 粗糙集理论概述粗糙集理论概述 1.2.1 粗糙集理论的提出粗糙集理论的提出 自然界中大部分事物所呈现的信息都是： 不完整的、不确定的、模糊的和含糊含糊的 经典逻辑无法准确、圆满地描述和解决 粗糙集理论主要是为了描述并处理粗糙集理论主要是为了描述并处理“含糊含糊”信息。信息。粗糙集理论的提出（续粗糙集理论的提出（续1）n“含糊含糊”（Vague）n1904年谓词逻辑创始人G. Frege (弗雷格)首次提出n将含糊性归结到 “边界线区域边界线区域”(Boundary region)n在全域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子

6、集的补集上nn“模糊集模糊集”（Fuzzy Sets）n1965年美国数学家L. A. Zadeh首次提出n无法解决G. Frege提出的“含糊”问题n未给出计算含糊元素数目的数学公式n粗糙集理论的提出（续粗糙集理论的提出（续2）n“粗糙集粗糙集”（Rough Sets）n1982年波兰数学家Z. Pawlak首次提出n将边界线区域定义为“上近似集”与“下近似集”的差集n指出在“真”、“假”二值之间的“含糊度”是可计算的n给出计算含糊元素数目的计算公式n借鉴了集合论中的“等价关系”（不可区分关系）n求取大量数据中的最小不变集合（称为“核核”）n求解最小规则集（称为“约简约简”）n粗糙集理论的提

7、出（续粗糙集理论的提出（续3）n粗糙集理论中的一些基本观点基本观点n“概念”就是对象的集合n“知识”就是将对象进行分类的能力( (“各从其类各从其类”) )n“知识” 是关于对象的属性、特征或描述的刻划n不可区分关系表明两个对象具有相同的信息n提出上近似集、下近似集、分类质量等概念n1.2.2 粗糙集理论的发展历程粗糙集理论的发展历程n1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。n在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。n1982年，Pawlak发表经典论

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

9、研讨会，有15篇论文发表在1993年第18卷的 Foundation of computing and decision sciences上。粗糙集理论的发展历程（续粗糙集理论的发展历程（续2）n1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。n1995年，年，Pawlak等人在等人在ACM Communications上上发表发表“Rough sets”，极大地扩大了该理论的国际影响，极大地扩大了该理论的国际影响。n19961999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。n2000年，在加拿大召开了第二届粗糙集与计算

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

11、）n局限性局限性n缺乏处理不精确或不确定原始数据的机制n对含糊概念的刻划过于简单n无法解决所有含糊的、模糊的不确定性问题n需要其它方法的补充nn解决办法解决办法n与模糊集理论相结合n与Dempster-Shafer证据理论相结合n1. 4 粗糙集理论在知识发现中的作用粗糙集理论在知识发现中的作用n在数据预处理过程中，粗糙集理论可以用于对粗糙集理论可以用于对遗失数据的填补。遗失数据的填补。n在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。对数据集进行降维操作。n在数据挖掘阶段，可将粗糙集理论用于分类规用于分类规则的发现。则的发现。粗糙集理论在知识发现中的作用（续）粗糙集理论

12、在知识发现中的作用（续）n在数据挖掘阶段的主要作用在数据挖掘阶段的主要作用n通过布尔推理挖掘出约简的规则来解释决策n通过熵理论将规则的复杂性和预测的误差分析溶入到无条件的度量中n与模糊集理论、证据理论构成复合分析方法n搜寻隐含在数据中的确定性或非确定性的规则nn在解释与评估过程中，粗糙集理论可用于对所对所得到的结果进行统计评估得到的结果进行统计评估。1. 5 粗糙集理论的研究现状粗糙集理论的研究现状n在理论研究方面n数学性质数学性质：研究其代数与拓扑结构、收敛性等n粗糙集拓广粗糙集拓广：广义粗糙集模型、连续属性离散化n与其它不确定性处理方法的关系和互补与其它不确定性处理方法的关系和互补：与模糊

13、集理论、Dempster-Shafer证据理论的关系和互补n粒度计算粒度计算：粗糙集理论是其重要组成之一n高效算法高效算法：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进n粗糙集理论的研究现状（续）粗糙集理论的研究现状（续）n在数据挖掘领域的应用n发现数据之间（精确或近似）的依赖关系n评价某一分类（属性）的重要性n剔除冗余属性n数据集的降维n发现数据模式n挖掘决策规则n在其它领域的应用n金融商业nn“知识知识”的定义n使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。n“知识库知识库”的形式化定义n等价关系集R中所有可能的关系对U的划分n表示为：K = (

14、U, R)2.1 2.1 基本概念基本概念2.Rough sets2.Rough sets理论的基本原理理论的基本原理基本概念（续基本概念（续1）n“信息系统信息系统”的形式化定义的形式化定义nS = U, Q, V, f，nU：对象的有限集nQ：属性的有限集，Q=CD，C是条件属性子集，D是决策属性子集nV： ， Vp是属性P的域nf：U A V是总函数，使得 对每个xi U, q A, 有f(xi, q) Vqn一个关系数据库可看作一个信息系统，其一个关系数据库可看作一个信息系统，其“列列”为为“属性属性”，“行行”为为“对象对象”。PApVV基本概念（续基本概念（续2）n基本集合基本集合

15、（Elementary set）/ 原子原子(Atom)n关系R的等价类(Equivalence classes)nU/R表示近似空间A上所有的基本集合（原子）n不可区分（等价、不分明）关系不可区分（等价、不分明）关系nU为论域，R是UU上的等价(Equivalence)关系（即满足自反、对称、传递性质）nA=U, R称为近似空间，R为不分明关系 (indiscernibility，或不可区分关系、等价关系)n若x, yU，(x, y)R，则x, y在A中是不分明的（不可区分的）基本概念（续基本概念（续3）n不可区分（等价、不分明）关系（续）不可区分（等价、不分明）关系（续）n设PQ， xi,

16、 xj U, 定义二元关系INDP称为不分明不分明关系关系为：n称xi, xj在S中关于属性集P是不分明的，当且仅当p(xi)=p(xj)对所有的pP成立，即xi, xj不能用P中的属性加以区别。n若x, yU，(x, y) R，则x, y在A中是不分明的（不可区分的）n对所有的pP，INDP是U上一种的等价关系)()(,|),()(jijixpxpPpUUxxPINDfactweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes

17、6mistynot icynightno不可区分关系（等价关系）示例不可区分关系（等价关系）示例可知，U = 1, 2, 3, 4, 5, 6R = 2 weather, road, time, accident 若P = weather, road，则xIND(p) = x INDweather xINProad = 1, 3, 6, 2, 5, 4 1, 2, 4, 3, 5, 6 = 1, 2, 4, 3, 6, 5 不可区分关系（等价关系）示例（续）不可区分关系（等价关系）示例（续）在信息系统S = U, Q, V, f中，设XU是个体全域上的子集，PQ则X的下和上近似集及边界区域分别

18、为：:/XYPUYXP:/XYPUYXPXPXPXBndP)( PX是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集； X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。 Bnd(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。P2.2 2.2 集合的上近似集合的上近似 & & 下近似下近似 图6.1 集合的上、下近似概念示意 XAprA XAprAX上、下近似关系举例：上、下近似关系举例： X1 = u | Flu(u) = yes = u2, u3, u6, u7 RX1 = u2, u3 = u2, u3, u6, u7, u5, u8X2 =

19、 u | Flu(u) = no = u1, u4, u5, u8 RX2 = u1, u4 = u1, u4, u5, u8, u6, u7X2RU Headache Temp. Flu U1 Yes Normal No U2 Yes High Yes U3 Yes Very-high Yes U4 No Normal No U5 N N No o o H H Hi i ig g gh h h N N No o o U6 No Very-high Yes U7 N N No o o H H Hi i ig g gh h h Y Y Ye e es s s U8 No Very-high No

20、 The indiscernibility classes defined by R = Headache, Temp. are:u1, u2, u3, u4, u5, u7, u6, u8.X1R上、下近似集的图示：上、下近似集的图示：R = Headache, Temp.U/R = u1, u2, u3, u4, u5, u7, u6, u8 X1 = u | Flu(u) = yes = u2,u3,u6,u7X2 = u | Flu(u) = no = u1,u4,u5,u8RX1 = u2, u3 = u2, u3, u6, u7, u5, u8RX2 = u1, u4 = u1,

21、u4, u5, u8, u6, u7X1RX2Ru1u4u3X1X2u5u7u2u6u82.3.1 集合的近似精度和粗糙度集合的近似精度和粗糙度 & 分类质量分类质量 设S = U, Q, V, f为一信息系统，且XU， PQ，则S上X的近似精度近似精度为：)()()()()(XPcardXPcardXXXPPP 设S为一信息系统，PQ，且令=X1,X2, , Xn是U的一个分类（子集族），其中XiU，则的P-下近似和P-上近似分别表示为：,21nXPXPXPP,21nXPXPXPP2.3 2.3 粗糙粗糙集的数字特征集的数字特征分类分类 的的近似精度近似精度为：为： )(1)(1)(iXPn

22、icardXPnicardiP由属性子集PQ确定的分类的分类质量分类质量为 ：)()(1)(UcardXPnicardiP 分类质量分类质量表示通过属性子集P正确分类的对象数与信息系统中所有对象数的比值。这是评价属性子集P的重要性的关键指标之一。 2.3.2 近似分类精度和近似分类质量近似分类精度和近似分类质量 一个申请信用卡的训练集：一个申请信用卡的训练集：申请人申请人编号编号条件属性条件属性决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3

23、3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝 原始属性集A = c1, c2, c3, c4的分类质量：)()(1)(UcardXPnicardiP188)(81)(0UcardiiXAcard令R = c2, c4，重新计算分类质量 ，得188)()4, 2 (814, 2UcardXccicardcci给定

24、K=（U,S），R IND(K), 对于集合X关于 系统参数R的重要度为()()RRUb nXs igXU-=2.3.3 系统参数的重要度系统参数的重要度 1()()nRiiRUb nXs igUn Up=-=划分关于 系统参数R的重要度给定K=（U,S）， P, Q IND(K), 定义/()()()pXUQPUPXp o sQQkUUg=2.3.4 知识的依赖度知识的依赖度 为知识Q依赖于知识P的程度，简记为：kPQ衡量通过知识衡量通过知识P准确划入到分类准确划入到分类U/Q的等价类中的程度。的等价类中的程度。2.3.5 包含度包含度用于变精度模型、概率模型等用于变精度模型、概率模型等2.

25、3.6 知识的不确定型的度量知识的不确定型的度量信息熵、条件熵、信息熵、条件熵、互信息等互信息等 2.3.5 包含度包含度用于变精度模型、概率模型等用于变精度模型、概率模型等 2.3.6 知识的不确定型的度量知识的不确定型的度量信息熵、条件熵、信息熵、条件熵、互信息等互信息等 知识必要性知识必要性：给定知识库K=（U,S）和等价关系簇PS, R P,若 IND(P) = IND( P-R ) 成立，则称知识R为P中必要的，否则称R为P中不必要的。 如果每一个RP, R 都是P中必要的，则P为独立的，否P为不独立的依赖的。2.4 2.4 知识约简知识约简2.4.1 知识的约简和知识的约简和“核核

26、”知识约简知识约简：给定知识库 K=（U,S）和等价关系簇PS, 对任意的G P, 若G满足：（1）G是独立的（2）IND(G)=IND(P)则称G是P的一个约简， GRED(P) RED(P)表示P的全体约简组成的集合。知识的核知识的核：给定知识库 K=（U,S）和等价关系簇PS, 对任意的 R P , 若R满足：()()IN D PIN D PR-则称知识R为P中必要的，P中所有必要的知识组成的集合称为P的核，记为CORE(P)()()C O RE PRED P= 定理定理由于R1必要的R2、R3不必要的，CORE(S) = R1RED(S)= R1,R2, R1, R3 2.4 2.4

27、知识约简知识约简2.4.2 知识的相对核知识的相对核 和和 相对约简相对约简知识的相对必要性知识的相对必要性回顾回顾知识的相对约简知识的相对约简：给定知识库 K=（U,S）和等价关系簇P，QS, 对任意的G P, 若G满足：（1）G是Q独立的，即G为P的Q独立子族（2）则称G是P的一个Q约简， ()()GPposQposQ=()QGREDP3. 3.信息系统约简信息系统约简3.1 3.1 知识表达系统知识表达系统: IS: DTn代数关系：经典信息系统、模糊信息系统n数据完备性：完备的和不完备的信息系统n数据分布：随机信息系统和非随机信息系统n属性值：格值信息系统3.2 3.2 信息系统的类型

28、信息系统的类型3.3 3.3 信息系统的属性约简算法信息系统的属性约简算法由于盲目删除属性约简算法，得到所有约简时需要的时间和空间代价太大，需要启发式策略缩短搜索路径。( ) |()()( )ijijn nijCORE CaaCc cMca=钨$钨=案例3.4 3.4 信息系统的值约简信息系统的值约简Outline1.Rough sets1.Rough sets理论概述理论概述2.Rough sets2.Rough sets理论的基本原理理论的基本原理3. 3.信息系统约简信息系统约简4. 4.决策表约简决策表约简5. 5.离散化方法离散化方法4. 4.决策表的知识约简决策表的知识约简4.1

29、4.1 知识表达系统知识表达系统: IS: DT 关于核的计算，有人提出了差别矩阵（discernibility matrix，也译作可辨识矩阵）。在信息系统S = (U, CD, V, f)中，C为条件属性，D为决策属性，设为对象全集U按决策属性D被分成不相交的类族，即 = X1,X2,Xm，则S中C的差别矩阵M(C) = mi,jnxn定义为, , 1, , ( , )( ,) : ( , )( ,), ,iji jijijijijx xDmx xDcC f c xf c xcC f c xf c xx xD 的同一等价类的不同等价类，对 的不同等价类其中，1 i j n。 差别矩阵与信息

30、系统的核有如下关系：对所有的cC, cCORE(C,D)的充要条件是，存在i, j(1 i j n)，使得mi,j = c。“含糊”是指分别属于两个不同类的对象具有完全相同的条件属性，在差别矩阵中，xi, xj是含糊的充要条件是存在i, j(1 i j n)，使得mi,j = -1。 申请申请人人编号编号条件属性条件属性 决策决策属性属性d dc1c1账号账号c2c2余额余额c3c3职业职业c4c4月消费月消费1 1银行银行中中(700)(700)有有低低接受接受2 2银行银行低低(300)(300)有有高高拒绝拒绝3 3无无低低(0)(0)有有中中拒绝拒绝4 4其它机构其它机构高高(1200

31、)(1200)有有高高接受接受5 5其它机构其它机构中中(800)(800)有有高高拒绝拒绝6 6其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中接受接受8 8无无低低(0)(0)无无低低拒绝拒绝 因决策d = 接受，拒绝，故上表按决策属性d可分为两个等价类：x1, x4, x6, x7和x2, x3, x5, x8。根据差别矩阵的计算公式可得： 4, 2, 1 3, 2, 14, 3, 2, 14, 24, 3, 2, 12 3, 2, 14, 2, 14, 2, 14, 3, 24, 2, 12, 1 3, 2, 14, 14,

32、 2, 14, 2cccccccccccccccccccccccccccccccccccccccccccc 差别矩阵与“核”有如下关系：属性c是条件属性C和决策属性D的“核”的充要条件是，存在i, j(1ijn)，使得mij = c。由上述矩阵可知，存在i=4, j=5，使得m4,5 = c2，故表1的“核”为c2。 实例：考虑下面的决策表，条件属性为a,b,c,d，决策属性为e。U/Aabcdeu110210u200121u320210u400222u511210uu1u2u3u4u5u1 u2a, c, d u3 a, c, d u4a, dca, d u5 a, b, c, d a, b

33、, d 由上述差别矩阵很容易得到核为：c差别函数fM(S)为：c(ad)，即(ac)(cd)得到两个约简a, c和c, d 根据得到的两个约简，可得两个约简后的新决策表UAaceu1120u2011u3220u4022u5120UAcdeu1210u2121u3210u4222U5210例如：下表是医学诊断的一个信息系统I=(U, A) 。其中，U = e1, e2, ., e7, A = A, T F。为方便表达，用1表示“是”，0表示“否”；2表示体温“很高”，1表示体温“高”，0表示体温“正常”，则表1.1的简化形式如表2所示。表 医学诊断信息系统的描述实例头痛A体温T流感流感Fe1是正

34、常否否e2是高是是e3是很高是是e4否正常否否e5否高否否e6否很高是是表表 简化后的决策系统简化后的决策系统UATFe1100e2111e3121e4000e5010e6021e1e4e5e2(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的决策矩阵的决策矩阵 将决策矩阵中的每行的元素进行合取，然后进行简化，得到相应的必然规则： (T, 1) (A, 1) (T, 1) (A, 1) (F, 1)得 (T, 1) (A, 1) (F, 1)

35、(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)1.3.5 属性之间的相关程度属性之间的相关程度 在信息系统S=(U, CD, V, f)中，设D*= X1,X2,Xm，属性子集PC关于决策属性D的“

36、正区域正区域”定义为： :)(DXXBDPOSPP关于D的正区域表示那些根据属性子集P就能正确分入的所有对象。 条件属性子集PC与决策属性D的相关程度相关程度（也称依赖依赖程度程度）定义为：)()(),(UcardDPOScardDPkP显然，0 k(P, D) 1。k(P, D)为计算条件属性子集P与决策属性D之间的相关程度提供了非常有力的手段。一个属性pPC的有效值有效值(significant value)定义为：),(),(),(DpPKDPkDPpSGF)()()(UcardDPOScardDPOScardpPP【说明】：属性p的有效值越大，说明其对条件属性与决策属性之间的影响越大，

37、即其重要性也越大。 1.3.6 属性的有效值（重要性）属性的有效值（重要性） 申请申请人人编号编号条件属性条件属性 决策决策属性属性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其它机构其它机构高高(1600)(1600)有有低低接受接受7 7银行银行高高(3000)(3000)无无中中

38、接受接受8 8无无低低(0)(0)无无低低拒绝拒绝已知上表的“核”CORE(C, D) = c2，设R = CORE(C, D) = c2，计算属性A的重要性程度： RaRgain8811 1, 2 2( 1, 2)( 2) 1( )iiiic cccard c cXcard cXgain crcard U属性的重要性计算举例属性的重要性计算举例6211 1, 2 2( 1, 2)( 2) 1( )( 1).( 7) ( 2, 3, 8)( 4, 6, 7)( )(1 1 22 1 1)(3 3)8 60.2588iiiic cccard c c Xcard c Xgain crcard Uc

39、ard xcard xcard x x xcard x x xcard U 属性的重要性计算举例（续）属性的重要性计算举例（续） 属性值约简属性值约简(Attribute Value Reduction)也称最小复合(Minimal Complex)。设B是一个由决策值对(d, w)表示的所有对象（概念）的下或上近似，集合B依赖于一个属性值对的集合T，当且仅当集合T是B的最小复合，当且仅当B依赖于T，且无ST，使得B依赖于S。BtTt1.3.7 属性值约简属性值约简No.No.AgeAgepregnancpregnanciesiesbody-fatbody-fatCholestCholeste

40、rolerolBreast-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.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.1

41、97188.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.320yesyes101057.6457.641.41.418.2818.28188.197188.197nono 设a = Age，b = pregnancies，c = body-fat，d = Cholesterol，条件属性C = a, b, c, d，决策属性D = Breast-can

42、cer，得如下差别矩阵： ,dcdcadcadcaaaccadadcbadcbcbadcbadcbacbacacdcbacbdcadcaadcbdcba得“核”CORE(C, D) = a, c, d。经属性约简后，删除多余属性c，即pregnancies，故得如下表所示的简化决策表。 No.Agebody-fatCholesterolBreast-cancer129.4118.28188.197no242.5618.28198.320no342.5629.37198.320yes429.4129.37198.320yes557.6418.28198.320no642.5618.28188.1

43、97yes729.4118.28188.197no842.5629.37198.320yes957.6429.37198.320yes1057.6418.28188.197no 由上表可知，该表存在两个决策值对：(Breast-cancer, no)和(Breast-cancer, yes)，且D1 = (Breast-cancer, no) = x1, x2, x5, x7, x10D2 = (Breast-cancer, yes) = x3, x4, x6, x8, x9 此外，有如下属性值对：A1 = (Age, 29.41) = x1, x4, x7A2 = (Age, 42.56)

44、= 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, x9 C1 = (Cholesterol, 188.197) = x1, x6, x7, x10C2 = (Cholesterol, 198.320) = x2, x3, x4, x5, x8, x9(1) 因B2 = (body-fat, 29.37) = x3, x4, x8, x9 D2 = (Breast-cancer) =

45、x3, x4, 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，有10, 7, 5, 2, 1),(17, 111xxxxxnocancerBreastDxxBAtTt且不存在T T，使得B依赖于T，故可得规则(Age, 29.41) &

46、 (%body-fat, 18.28) (Breast-cancer, no) (2)(3) 同理，令T = A1, C1，得1117, 111DBAxxCAtTt【说明说明】： 虽然T = A1, C1也是一个最小复合，但由于交集x1, x7与(2)中相同，说明两者实际上是同一条规则，故应略去。 要略去哪一条规则（或者说要保留哪一条规则），则还需考虑哪些属性更重要，即应取最关键的属性所组成的规则。 在该例中，由差别矩阵的计算结果可知，属性body-fat的重要性大于属性Cholesterol，因此略去A1与C1组成的规则。 属性值约简举例（续）属性值约简举例（续） (4) 令T = A1,

47、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 D

48、1 = x1, x2, x5, x7,x10，故有(Age, 57.64) & (body-fat, 18.28) (Breast-cancer, no) (4) (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

49、D1 = x1, x2, x5, x7,x10，有(body-fat, 18.28) & (Cholesterol, 198.320) (Breast-cancer, no)(5)属性值约简举例（续）属性值约简举例（续）因此，共得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

50、-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，使得BtTt即为上述步骤(2)和(3)两种情况，表明T = A1, B1, C1不是最小复合。其余情况类似，故不赘述。 属性可分为定量属性(Quantitative attributes)和定性属性(Qualitative attributes)，其中定性属性又被分成有序定性