第11章粗糙集理论概述.ppt

数据挖掘原理与SPSS Clementine应用宝典 元昌安 主编　 邓　松　李文敬　刘海涛　编著 电子工业出版社 第11章 粗糙集理论 本章包括： 粗糙集的基本概念 知识表达 粗糙集在数据预处理中的应用 粗糙集理论是由波兰华沙理工大学Pawlak教授于20世纪80年代初提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，它是一种刻画不完整性和不确定性的数学工具，能有效地分析不精确、不一致(inconslsteni)、不完整(incomPlete)等各种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。 粗糙集在机器学习、决策支持系统、机器发现、归纳推理、数据库中的知识发现、模式识别等领域都得到了广泛的应用。 11.1粗糙集基本概念 粗糙集应用于数据挖掘领域，能提高对大型数据库中的不完整数据进行分析和学习的能力，具有广泛的应用前景和实用价值。 粗糙集方法仅利用数据本身提供的信息，无须任何先验知识。 粗糙集是一个强大的数据分析工具，它能表达和处理不完备信息；能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估数据之间的依赖关系，揭示出概念的简单模式；能从经验数据中获取易于证实的规则知识。 粗糙集的研究对象是由一个多值属性(特征、症状、特性等)集合描述的一个对象(观察、病历等)集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符是表达决策问题的3个基本要素。 粗糙集理论逐渐应用于数据挖掘领域中，并在对大型数据库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙集理论及数据挖掘的研究成为热点领域。最近几年，粗糙集理论越来越受到众多研究人员的重视，它的应用研究得到了很大的发展。 11.1.1 知识和知识库 知识是人类通过实践对客观世界的运动规律的认识，是人类实践经验的总结和提炼，具有抽象和普遍的特性。 从认知科学的观点来看，知识来源于人类对客观事物的分类能力，概念是事物类别的描述或者符号，知识则是概念之间的关系和联系。任何一个物种都是由一些知识来描述与分类的，利用物种的不同属性知识描述来产生对物种的不同分类。 集合上的等价关系和集合上的划分是一一对应，相互唯一决定的。从数学意义上讲，集合上的等价关系和集合的划分是等价的概念，即划分就是分类。 定义11-1 设　讨论的对象组成的有限集合，称为论域(Universe)，对于论域中由等价关系划分出来的任意子集，都可以称为论域U中的一个概念(concept)或范畴(category)。为规范起见，认为空集必也是一个概念。论域U中的任意概念族称为关于论域的抽象知识，它代表了对论域中个体的分类，简称为知识。 定义11-2 K=(U,R)其中K为知识库，U为全体对象的集合称为论域，R为论域U上的等价关系(等价关系与分类的概念等同)，它是一种属性或多种属性的集合。可以根据不同的R对U进行不同形式的分类。知识库也被称作近似空间。 定义11-3 K=(U,P)和M=(U,Q)是两个知识库，若IND(P)=IND(Q)，则称K和M(或Q和P)是等价的， 记作 (或者) 。因此，当K和M是同样的基本范畴集时，知识库K和M中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事实。 对于两个知识库K=(U,P)和M=(U,Q)，当 时，称知识库P比知识库Q更精细，或者说Q比P更粗糙。当P比Q更精细时，我们称P为Q的特化，Q为P的推广。由以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。 11.1.2 不可分辨关系 在粗糙集理论中，“知识”被认为是一种分类的能力。不可分辨关系的概念是粗糙集理论的基石，它揭示出论域知识的颗粒状结构。假定关于论域的某种知识，并使用属性和属性值来描述论域中的对象，如果两个对象(或对象集合)具有相同的属性和属性值，则它们之间具有不可分辨关系。 定义11-4　设R是非空集合U上的二元系，如果它是自反的、对称的和可传递的，则称R为U上的等价关系。若， 则称x与y有关系，记为 ；若 ，则称x与y没有关系，记为 。等价关系的一个重要特点是用它可以构成U的一个划分。划分即是分类，将研究对象分成不同的类，这些类之间互不相交，且每一对象均包含在某一类中。 定义11-5　设U是一个论域，R是U上的等价关系，U/R