[理学]DATA MININGCH8.ppt

第8章 粗糙集 《数据挖掘与知识发现》(第2版) 吉林大学计算机科学与技术学院 李雄飞 粗糙集 粗糙集(Rough Set)理论是一种新的处理含糊性和不确定性问题的数学工具。本章介绍粗糙集基本理论和方法，具体包括： 近似空间 近似与粗糙集 粗糙集特征描述 知识约简 知识依赖性 信息系统 决策表 决策规则 扩展的粗糙集模型 引言 粗糙集(Rough Set)理论是波兰数学家Z.Pawlak于1982年提出的，是一种新的处理含糊性(Vagueness)和不确定性(Uncertainty)问题的数学工具。 1991年，Z.Pawlak教授撰写专著《Rough Sets——Theoretical Aspects of Reasoning about Data》。 1992年在波兰召开了第一届国际粗糙集研讨会，以后每年都有以粗糙集理论为主题的国际研论会。 1995年，第11期的ACM Communication将粗糙集列为人工智能及认知科学领域新的研究课题。 粗糙集理论的主要优势之一就在于它不需要关于数据的任何预备的或额外的信息。 粗糙集理论应用领域 知识发现 机器学习 决策支持 模式识别 专家系统 归纳推理等。 近似空间 定义8.1 设U为所讨论对象的非空有限集合，称为论域；R为建立在U上的一个等价关系，称二元有序组AS=(U, R)为近似空间（Approximate Space）。 近似空间构成论域U的一个划分；若R是U上的一个等价关系，以[x]R表示x的R等价类，U／R表示R的所有等价类构成的集合，即商集；R的所有等价类构成U的一个划分，划分块与等价类相对应。 定义8.2 令R为等价关系族，设P?R，且P??，则P中所有等价关系的交集称为P上的不可分辨关系（Indiscernibility Relation），记作IND(P)，即有： （8.1） 显然，IND(P)也是等价关系。 近似空间 例8.1 设论域U={x1, x2, x3, x4, x5}，R={R1, R2, R3}，I是恒等关系，R1，R2，R3定义如下： R1={＜x1, x2＞, ＜x2, x1＞, ＜x3, x4＞,＜x4, x3＞?I R2={＜x1, x2＞, ＜x2, x1＞, ＜x4, x5＞, ＜x5, x4＞?I R3={＜x1, x2＞, ＜x2, x1＞, ＜x1, x3＞, ＜x3, x1＞, ＜x2, x3＞, ＜x3, x2＞, ＜x4, x5＞, ＜x5, x4＞}?I 若P={R1, R2}?R，则由定义可知： IND(P)=R1 ? R2={＜x1, x2＞, ＜x2, x1＞}?I IND(R)=R1 ? R2 ? R3 ={＜x1, x2＞, ＜x2, x1＞}?I 利用等价关系对应的商集来间接描述不可分辨关系。 若有R1，R2，R3，P按上述方式给出，则有： U／R1={{x1, x2}, {x3, x4}, {x5}} U／R2={{x1, x2}, {x3}, {x4, x5}} U／R3={{x1, x2, x3}, {x4, x5}} 不可分辨关系IND(P)和IND(R)的等价类的集合为： U／IND(P)=U／{R1, R2}={{x1, x2}, {x3},{x4}, {x5}} U／IND(R)=U／{R1, R2, R3}={{x1, x2}, {x3}, {x4}, {x5}} 近似空间 粗糙集理论将分类方法看成知识，分类方法的族集是知识库。等价关系对应论域U的一个划分，即关于论域中对象的一个分类。 定义8.3 称论域U的子集为U上的概念（Concept），约定?也是一个概念，概念的族集称为U上的知识；U上知识（分类）的族集构成关于U的知识库，也就是说，知识库是分类方法的集合。 定义8.4 设U为论域，R为等价关系族，P?R且P??，则不可分辨关系IND(P)的所有等价类的集合，即商集U／IND(P)称为U的P基本知识，相应等价类称为知识P的基本概念。特别地，若等价关系Q?R，则称U／Q为U的Q初等知识，相应等价类称为Q初等概念。由于选取R的不同子集P可以得到U上的不同知识，故称K=(U, R)为知识库（Knowledge Base）。 为简单起见，用U／P代替U／IND(P)。 P基本概念与P基本集相对应。 给定知识库K=(U, R)，知识库的知识粒度由不可分辨关系IND(R)的等价类反映。 不难证