[粗糙集算法.docxVIP

DUFE管理科学与工程研究方法概论粗糙集理论 学号： 2013100654专业： 电子商务 姓名： 徐麟 粗糙集理论一、粗糙集的来源与发展智能信息处理是当前信息科学理论和应用研究中的一个热点领域。由于计算机科学与技术的发展，特别是计算机网络的发展，每日每时为人们提供了大量的信息。信息量的不断增长，对信息分析工具的要求也越来越高，人们希望自动地从数据中获取其潜在的知识。特别是近20年间，知识发现(规则提取、数据挖掘、机器学习)受到人工智能学界的广泛重视，知识发现的各种不同方法应运而生。粗糙集(RoughSet，也称Rough集、粗集)理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具。粗糙集理论最初的原型来源于比较简单的信息模型，它的基本思想是通过关系数据库分类归纳形成概念和规则，通过等价关系的分类以及分类对于目标的近似实现知识发现。由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种重要的智能信息处理技术，该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子(又称上、下近似集)。经典Pawlak模型中的不分明关系是一种等价关系，要求很高，限制了粗糙集模型的应用。二、粗糙集的理论基础1、概念、可定义集从经典的角度来看，每个概念都包含其内涵和外延。为了给出概念内涵和外延的具体描述，我们考虑一个简单的知识表达系统，即信息表。信息表就是一组对象的集合，对象通过一组属性来描述。表1就是一个信息表的例子。个体编号头疼肌肉疼体温流感X1是是正常否X2是是高是X3是是很高是X4否是正常否X5否否高否X6否是很高是表1信息实例可定义集的形式化定义如下：在信息表M中，如果称子集XAU是可被属性子集AAAt定义的，当且仅当在语言L(A)中存在一个公式使得X=m()。否则，X称为不可定义的。2、近似空间语言L(A)的所有可定义集正好构造成一个R代数R(U/E(A))，即Def(U，L(A))=R(U/E(A))。序对apr=(U，E(A))称为一个Pawlak近似空间，简称近似空间。所以，也可以将语言L(A)的所有可定义集记为Def(U，L(A))=Def(apr)。通过U/E(A)，可以构造一个R代数，即R(U/E(A))，它包含空集á和等价关系E(A)构成的等价类及其并，并且在交、并和补运算上是封闭的。那么，Pawlak近似空间也唯一确定了一个拓扑空间(U，R(U/E(A)))。3、上下近似针对不可定义集，显然不可能构造一个公式来精确描述，只能通过上下界逼近的方式来刻画，这就是粗糙集理论中的上下近似算子。设E(A)是信息表M上的等价关系，XAU，上下近似算子aprE(A)，aprE(A)(下文我们采用缩写形式apr，apr)定义为apr(X)=G{Y|YIR(U/E(A))，YHXXá}=H{Y|YIDef(U，L(A)，XAY}；apr(X)=G{Y|YIR(U/E(A))，YAX}=G{Y|YIDef(U，L(A)，YAX}。上近似apr(X)是包含X的最小可定义集，下近似apr(X)是包含在X中的最大可定义集。4、粗糙集Pawlak[1，22]定义由等价关系确定的等价类[x]E(A)的集合就组成了P12粗糙集集合(P12RoughSet，PRS1)。显然，P12粗糙集集合是子集集合，即PRS1={[x]E(A)|XA2U}。借助上下近似的描述，也可以给出和PRS1等价的关于粗糙集的另外一种定义，称为P22粗糙集集合。即PRS2={3X1，X24}={3apr(X)，apr(X)4}。PRS1和PRS2通称为Pawlak粗糙集。以上对粗糙集的解释都是从集合的观点进行的；还存在另外一种观点，即从算子的观点来解释粗糙集。在面向算子的观点中，上下近似被看作是论域幂集空间2U上的一对一元算子L和H。也就是说，粗糙集理论中研究的系统(2U，~，H，G，L，H)是标准集合系统(2U，~，H，G)附加了两个近似算子的扩展。三、粗糙集的研究方法经典粗糙集理论的基本思想是基于等价关系的粒化与近似的数据分析方法。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子(又称上、下近似集)。目前，主要有两种研究方法来定义近似算子：构造化方法和公理化方法。构造化方法是以论域上的二元关系、划分、覆盖、邻域系统、布尔子代数等作为基本要素进而定义粗糙近似算子，从而导出粗糙集代数系统。公理化方法的基本要素是一对满足某些公理的一元集合算子，近似算子的某些公理能保证有一些特殊类型的二元关系的存在；反过来，由二元关系通过构造性方法导出的近似算子一定满足某些公理。事实上，有两种形式来描述粗