粗糙集_学习笔记.pdf

大概 起源 概念 例子 知识的约简 决策表的约简 一、起源 含糊--模糊集--粗糙集 1、在 1904 年谓词逻辑的创始人 G.Frege 就提出了含糊(Vague)一词，他把它归结到边界线上， 也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类。 2、1965 年，Zadeh 提出了模糊集 ，不少理论计算机科学家和逻辑学家试图通过这一理论解决 G.Frege 的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者 由领域专家给出，所以具有相当的主观性。 3、20 世纪 80 年代初，波兰的 Pawlak 针对 G.Frege 的边界线区域思想提出了粗糙集 （Rough Set ）﹐他把那些无法确认的个体都归属于边界线区域 ，而这种边界线区域被定义为上近似集和下 近似集之差集。由于它有确定的数学公式描述，完全由数据决定，所以更有客观性 。粗糙集理论 的主要优势之一是它不需要任何预备的或额外的有关数据信息。 二、概念 1、粗糙集(Rough Set,也称 Rough 集、粗集)理论是 Pawlak 教授于 1982 年提出的一种能够定量 分析处理不精确、不一致、不完整信息与知识的数学工具. 2、粗糙集理论最初的原型来源于比较简单的信息模型,它的基本思想： 通过关系数据库分类归纳形成概念和规则, 通过等价关系的分类以及分类对于目标的近似实现知识发现. 3、基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。 4、全域或论域(universe) ：即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在 一起，这种特定部分称之为所讨论的全域或论域。 5、族集(family) ：事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集 ，这个族集提 供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。 6、一个近似空间(approximate space) （或知识库）定义为一个关系系统 （或二元组） K=(U,R) 其中 U 不为空集，是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R 是 U 上等价 关系的一个族集。 7、不可区分关系： 8、概念(concept) ：给定近似空间K=(U, R) ，子集X 称为 U 上的一个概念(concept) ，形式上， 空集也视为一个概念； 基本知识(basic knowledge) ：非空子族集P R 所产生的不分明关系 IND(P)的所有等价类关系 的集合即 U/IND(P) 相应的等价类称为基本概念 初等知识(elementary knowledge) ：特别地，若关系Q R ，则关系Q 就称为初等知识 初等概念(elementary concept) ：相应的等价类就称为初等概念 9、下近似与上近似 若边界区域不为空集，则集合 X 就是一个粗糙概念。 其中，下近似包含了所有使用知识 R 可确切分类到 X 的元素， 上近似则包含了所有那些可能是属于 X 的元素。 概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。 10、新型的隶属关系 其中 R 是不分明关系 可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率， 能够从全域上的个体加以计算，而不是主观给定的。 11、近似度 Accuracy of Approximation 其中，|X| denotes the cardinality(基数) of X 12、近似性质 Properties of Approximations where -X denotes U - X. 三、例子： 。 。。 四、知识的约简 （一）一般约简 1、定义 1 设 R 是等价关系的一个族集，且设 R R。若IND(R)=IND(R–R) ，则称关系R在族集 R 之中 是可省的(dispensable) ﹐否则就是不可省的。若族集 R 中的每个关系 R 都是不可省的﹐则称族集 R 是独立的(independent) ﹐否则就是依赖的或非独立的。 2、定义 2 若 Q P 是独立的，并且 IND(Q)=IND(P) ﹐则称Q 是关系族集 P 的一个约简(reduct) 。在 族集 P 中所有不可省的关系的集合称为 P 的核(core) ﹐以CORE(P)来表示。