课件人工智能引论浙江大学研究生徐从富(Congfu Xu) PhD, Associate Professor Email: xucongfuzju.edu.cn Institute of Artificial Intelligence, College of Computer Science,Zhejiang University, Hangzhou 310027, P.R. ChinaNovember 18, 2002第一稿 September 30, 2006第四次修改稿第六讲 粗糙集理论及其应用 (Chapter6 Rough Sets Theory and Its Applications )OutlinenRough sets理论的快速入门方法nRough sets理论的发展概述nRough sets理论的基本原理n计算举例n课后研读论文6.1 Rough sets的快速入门方法n认真研读Rough Sets Theory的创始人、波兰数学家Z. Pawlak于1982年发表的第一篇论文“Rough Sets”。【 注】：最好直接阅读英文论文原文。 n研读王珏等人1996年在模式识别与人工智能上发表 的关于Rough Sets理论及其应用的综述性文章。n参考史忠植编著的高级人工智能、知识发现等 教材中讨论粗糙集的有关章节。【注】：国内王国胤、刘清 、张文修、曾黄麟等人先后出版了关于Rough Sets的教材，也可 适当参考。Rough set快速入门方法（续）认真研读如下3篇典型的论文： 1 Pawlak, Z., et al. Rough set approach to multi-attribute decision analysis. European Journal of Operational Research, 72: 443-459, 1994 2 Grzymala-Busse, D. M., et al. The usefulness of a machine learning approach to knowledge acquisition. Computational Intelligence. 11(2):268-279, 1995 3 Jelonek, J., et al. Rough set reduction of attributes and their domains for neural networks. Computational Intelligence, 11(2): 339-347, 1995结合本课件作者于2000年整理的举例说明粗糙集理 论的有关概念及公式 6.2 粗糙集理论的发展概述6.2.1 粗糙集理论的提出自然界中大部分事物所呈现的信息都是： 不完整的、不确定的、模糊的和含糊的 经典逻辑无法准确、圆满地描述和解决粗糙集理论主要是为了描述并处理“含糊”信息。“Blessed are the merciful, for they will be shown mercy. Blessed are the pure in heart, for they will see God.”From MATTHEW 5:7-8 NIV 粗糙集理论的提出（续1）n“含糊”（Vague）n1904年谓词逻辑创始人G. Frege (弗雷格)首次提出n将含糊性归结到 “边界线区域”(Boundary region)n在全域上存在一些个体，它既不能被分类到某一个 子集上，也不能被分类到该子集的补集上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粗糙集理论的提出（续3）n粗糙集理论中的一些基本观点n“概念”就是对象的集合n“知识”就是将对象进行分类的能力(“各从其类”)n“知识” 是关于对象的属性、特征或描述的刻划n不可区分关系表明两个对象具有相同的信息n提出上近似集、下近似集、分类质量等概念n“God made the wild animals according to their kinds, the livestock according to their kinds, and all the creatures that move along the ground according to their kinds. And God saw that it was good.”From GENESIS 1:25 NIV 6.2.2 粗糙集理论的发展历程n1970s，Pawlak和波兰科学院、华沙大学的一些逻辑学 家，在研究信息系统逻辑特性的基础上，提出了粗糙 集理论的思想。n在最初的几年里，由于大多数研究论文是用波兰文发 表的，所以未引起国际计算机界的重视，研究地域仅 限于东欧各国。n1982年，Pawlak发表经典论文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年，在波兰召开了第一届国际粗糙集理论研讨会 ，有15篇论文发表在1993年第18卷的 Foundation of computing and decision sciences上。粗糙集理论的发展历程（续2）n1993和1994年，分别在加拿大、美国召开第二、三届 国际粗糙集与知识发现（或软计算）研讨会。n1995年，Pawlak等人在ACM Communications上 发表“Rough sets”，极大地扩大了该理论的国际影响。n19961999年，分别在日本、美国、美国、日本召开 了第4-7届粗糙集理论国际研讨会。n2000年，在加拿大召开了第二届粗糙集与计算趋势国 际会议。粗糙集理论的发展历程（续3）n20012002，中国分别在重庆、苏州召开第一、二届 粗糙集与软计算学术会议。n2003年，在重庆召开粗糙集与软计算国际研讨会。n2004年，在瑞典召开RSCTC国际会议（年会） 。n2005年，在加拿大召开RSFDGrC国际会议（年会）。n6.2.3 粗糙集理论的优点及局限性n主要优点n除数据集之外，无需任何先验知识（或信息）n对不确定性的描述与处理相对客观n【说明】：Bayes理论、模糊集理论、证据理论等都 需要先验知识，具有很大的主观性。“Now faith is being sure of what we hope for and certain of what we do not see.” “And without faith it is impossible to please God, because anyone who comes to him must believe that he exists and that he rewards those who earnestly seek him.”From HEBREWS 11:1, 6 NIV粗糙集理论的优点及局限性（续）n局限性n缺乏处理不精确或不确定原始数据的机制n对含糊概念的刻划过于简单n无法解决所有含糊的、模糊的不确定性问题n需要其它方法的补充nn解决办法n与模糊集理论相结合n与Dempster-Shafer证据理论相结合n6.2.4 粗糙集理论在知识发现中的作用n在数据预处理过程中，粗糙集理论可以用于对 遗失数据的填补。n在数据准备过程中，利用粗糙集理论的数据约 简特性，对数据集进行降维操作。n在数据挖掘阶段，可将粗糙集理论用于分类规 则的发现。粗糙集理论在知识发现中的作用（续）n在数据挖掘阶段的主要作用n通过布尔推理挖掘出约简的规则来解释决策n通过熵理论将规则的复杂性和预测的误差分析溶入 到无条件的度量中n与模糊集理论、证据理论构成复合分析方法n搜寻隐含在数据中的确定性或非确定性的规则nn在解释与评估过程中，粗糙集理论可用于对所 得到的结果进行统计评估。6.2.5 粗糙集理论的研究现状n在理论研究方面n数学性质：研究其代数与拓扑结构、收敛性等n粗糙集拓广：广义粗糙集模型、连续属性离散化n与其它不确定性处理方法的关系和互补：与模糊集 理论、Dempster-Shafer证据理论的关系和互补n粒度计算：粗糙集理论是其重要组成之一n高效算法：导出规则的增量式算法、简约的启发式 算法、并行算法、现有算法的改进n粗糙集理论的研究现状（续）n在数据挖掘领域的应用n发现数据之间（精确或近似）的依赖关系n评价某一分类（属性）的重要性n剔除冗余属性n数据集的降维n发现数据模式n挖掘决策规则n在其它领域的应用n金融商业n6.3 粗糙集理论的基本原理n“知识”的定义n使用等价关系集R对离散表示的空间U进行 划分，知识就是R对U划分的结果。n“知识库”的形式化定义n等价关系集R中所有可能的关系对U的划分n表示为：K = (U, R)6.3.1 基本概念基本概念（续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一个关系数据库可看作一个信息系统，其“列”为“ 属性”，“行”为“对象”。基本概念（续2）n基本集合（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, 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上一种的等价关系factweatherroadtimeaccident1mistyicydayyes2foggyicynightyes3mistynot icynightyes4sunnyicydayno5foggynot icyduskyes6m