3-粗糙集理论

2011年5月粗糙集理论及其应用(RoughSetsTheoryandItsApplications)中国民航大学《粗糙集理论与机器学习》研究生课件Outline1.Roughsets理论概述2.Roughsets理论的基本原理3.信息系统约简4.决策表约简5.离散化方法1.1Roughsets的快速入门方法认真研读RoughSetsTheory的创始人、波兰数学家Z.Pawlak于1982年发表的第一篇论文“RoughSets”。【注】：最好直接阅读英文论文原文。研读王珏等人1996年在《模式识别与人工智能》上发表的关于RoughSets理论及其应用的综述性文章。参考李德毅的《不确定性人工智能》、杨善林的《智能决策方法与智能决策支持系统》参考史忠植编著的《高级人工智能》、《知识发现》等教材中讨论粗糙集的有关章节。【注】：国内王国胤、刘清、张文修、曾黄麟等人先后出版了关于RoughSets的教材，也可适当参考。1.Roughsets理论概述Roughset快速入门方法（续）认真研读如下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,19951.2粗糙集理论概述1.2.1粗糙集理论的提出自然界中大部分事物所呈现的信息都是：◆不完整的、不确定的、模糊的和含糊的◆经典逻辑无法准确、圆满地描述和解决粗糙集理论主要是为了描述并处理“含糊”信息。粗糙集理论的提出（续1）“含糊”（Vague）1904年谓词逻辑创始人G.Frege(弗雷格)首次提出将含糊性归结到“边界线区域”(Boundaryregion)在全域上存在一些个体，它既不能被分类到某一个子集上，也不能被分类到该子集的补集上……“模糊集”（FuzzySets）1965年美国数学家L.A.Zadeh首次提出无法解决G.Frege提出的“含糊”问题未给出计算含糊元素数目的数学公式……粗糙集理论的提出（续2）“粗糙集”（RoughSets）1982年波兰数学家Z.Pawlak首次提出将边界线区域定义为“上近似集”与“下近似集”的差集指出在“真”、“假”二值之间的“含糊度”是可计算的给出计算含糊元素数目的计算公式借鉴了集合论中的“等价关系”（不可区分关系）求取大量数据中的最小不变集合（称为“核”）求解最小规则集（称为“约简”）……粗糙集理论的提出（续3）粗糙集理论中的一些基本观点“概念”就是对象的集合“知识”就是将对象进行分类的能力(“各从其类”)“知识”是关于对象的属性、特征或描述的刻划不可区分关系表明两个对象具有相同的信息提出上近似集、下近似集、分类质量等概念……1.2.2粗糙集理论的发展历程1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学家，在研究信息系统逻辑特性的基础上，提出了粗糙集理论的思想。在最初的几年里，由于大多数研究论文是用波兰文发表的，所以未引起国际计算机界的重视，研究地域仅限于东欧各国。1982年，Pawlak发表经典论文《Roughsets》，标志着该理论正式诞生。粗糙集理论的发展历程（续1）1991年，Pawlak的第一本关于粗糙集理论的专著《Roughsets:theoreticalaspectsofreasoningaboutdata》；1992年，Slowinski主编的《Intelligencedecisionsupport:handbookofapplicationsandadvancesofroughsetstheory》的出版，奠定了粗糙集理论的基础，有力地推动了国际粗糙集理论与应用的深入研究。1992年，在波兰召开了第一届国际粗糙集理论研讨会，有15篇论文发表在1993年第18卷的《Foundationofcomputinganddecisionsciences》上。粗糙集理论的发展历程（续2）1993和1994年，分别在加拿大、美国召开第二、三届国际粗糙集与知识发现（或软计算）研讨会。1995年，Pawlak等人在《ACMCommunications》上发表“Roughsets”，极大地扩大了该理论的国际影响。1996～1999年，分别在日本、美国、美国、日本召开了第4-7届粗糙集理论国际研讨会。2000年，在加拿大召开了第二届粗糙集与计算趋势国际会议。粗糙集理论的发展历程（续3）2001～2002，中国分别在重庆、苏州召开第一、二届粗糙集与软计算学术会议。2003年，在重庆召开粗糙集与软计算国际研讨会。2004年，在瑞典召开RSCTC国际会议（年会）。2005年，在加拿大召开RSFDGrC国际会议（年会）。……1.3粗糙集理论的优点及局限性主要优点除数据集之外，无需任何先验知识（或信息）对不确定性的描述与处理相对客观……【说明】：Bayes理论、模糊集理论、证据理论等都需要先验知识，具有很大的主观性。粗糙集理论的优点及局限性（续）局限性缺乏处理不精确或不确定原始数据的机制对含糊概念的刻划过于简单无法解决所有含糊的、模糊的不确定性问题需要其它方法的补充……解决办法与模糊集理论相结合与Dempster-Shafer证据理论相结合……1.4粗糙集理论在知识发现中的作用在数据预处理过程中，粗糙集理论可以用于对遗失数据的填补。在数据准备过程中，利用粗糙集理论的数据约简特性，对数据集进行降维操作。在数据挖掘阶段，可将粗糙集理论用于分类规则的发现。粗糙集理论在知识发现中的作用（续）在数据挖掘阶段的主要作用通过布尔推理挖掘出约简的规则来解释决策通过熵理论将规则的复杂性和预测的误差分析溶入到无条件的度量中与模糊集理论、证据理论构成复合分析方法搜寻隐含在数据中的确定性或非确定性的规则……在解释与评估过程中，粗糙集理论可用于对所得到的结果进行统计评估。1.5粗糙集理论的研究现状在理论研究方面数学性质：研究其代数与拓扑结构、收敛性等粗糙集拓广：广义粗糙集模型、连续属性离散化与其它不确定性处理方法的关系和互补：与模糊集理论、Dempster-Shafer证据理论的关系和互补粒度计算：粗糙集理论是其重要组成之一高效算法：导出规则的增量式算法、简约的启发式算法、并行算法、现有算法的改进……粗糙集理论的研究现状（续）在数据挖掘领域的应用发现数据之间（精确或近似）的依赖关系评价某一分类（属性）的重要性剔除冗余属性数据集的降维发现数据模式挖掘决策规则在其它领域的应用金融商业……“知识”的定义使用等价关系集R对离散表示的空间U进行划分，知识就是R对U划分的结果。“知识库”的形式化定义等价关系集R中所有可能的关系对U的划分表示为：K=(U,R)2.1基本概念2.Roughsets理论的基本原理基本概念（续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一个关系数据库可看作一个信息系统，其“列”为“属性”，“行”为“对象”。PApVV基本概念（续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中是不分明的（不可区分的）基本概念（续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上一种的等价关系)}()(,|),{()(jijixpxpPpUUxxPINDfactweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynoticynightyes4sunnyicydayno5foggynoticyduskyes6mistynoticynightno不可区分关系（等价关系）示例可知，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}}不可区分关系（等价关系）示例（续）在信息系统S={U,Q,V,f}中，设XU是个体全域上的子集，PQ则X的下和上近似集及边界区域分别为：}:/{XYPUYXP}:/{XYPUYXPXPXPXBndP)(•PX是XU上必然被分类的那些元素的集合，即包含在X内的最大可定义集；•X是U上可能被分类的那些元素的集合，即包含X的最小可定义集。•Bnd(X)是既不能在XU上被分类，又不能在U-X上被分类的那些元素的集合。P2.2集合的上近似&下近似图6.1集合的上、下近似概念示意XAprAXAprAX上、下近似关系举例：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}X2RUHeadacheTemp.FluU1YesNormalNoU2YesHighYesU3YesVery-highYesU4NoNormalNoU5NNNoooHHHiiiggghhhNNNoooU6NoVery-highYesU7NNNoooHHHiiiggghhhYYYeeesssU8NoVery-highNoTheindiscernibilityclassesdefinedbyR={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,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}X1RX2Ru1u4u3X1X2u5u7u2u6u82.3.1集合的近