粗糙集算法

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)附加了两个近似算子的扩展。

三、粗糙集的研究方法

经典粗糙集理论的基本思想是基于等价关系的粒化与近似的数据分析方法。

粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子

和下近似算子(又称上、下近似集)。目前，主要有两种研究方法来定义近似算子：

构造化方法和公理化方法。构造化方法是以论域上的二元关系、划分、覆盖、邻

域系统、布尔子代数等作为基本要素进而定义粗糙近似算子，从而导出粗糙集代

数系统。公理化方法的基本要素是一对满足某些公理的一元集合算子，近似算子

的某些公理能保证有一些特殊类型的二元关系的存在；反过来，由二元关系通过

构造性方法导出的近似算子一定满足某些公理。事实上，有两种形式来描述粗糙

集，一个是从集合的观点来进行，一个是从算子的观点来进行。那么，从不同观

点采用不同的研究方法就得到粗糙集的各种扩展模型。粗糙集理论与其它处理不

确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合

之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比较客观的，

由于这个理论未能包含处理不精确或不确定原始数据的机制，所以这个理论与概

率论、模糊数学和证据理论等其它处理不确定或不精确问题的理论有很强的互补

性。基于粗糙集理论的应用研究主要集中在属性约简、规则获取、基于粗糙集的

计算智能算法研究等方面。由于属性约简是一个NP2Hard问题，许多学者进行了

系统的研究。基于粗糙集的约简理论发展为数据挖掘提供了许多有效的新方法。

公理化方法也称为代数方法，有时也称为算子方法，这种方法不像构造化方

法中是以二元关系为基本要素的，它的基本要素是一对满足某些公理的一元近似

算子L，H：2Uy2U，即粗糙代数系统(2U，~，H，G，L，H)中近似算子L和H是

事先给定的。然后再去找二元关系使得由该二元关系及其生成的近似空间按构造

化方法导出的近似算子恰好就是给定的由公理化方法定义的集合算子。近似算子

的某些特殊公理能保证有一些特殊类型的二元关系存在，使这些关系能够通过构

造方法产生给定的算子；反之，由二元关系通过构镇的英文 造方法导出的近似算子一定满

足某些公理，使这些公理通过代数方法产生给定的二元关系。

四、粗糙集与其它不确定信息处理理论的联系

随着对粗糙集理论研究的不断深入，与其它数学分支的联系也更加紧密。粗

糙集理论研究不但需要以这些理论作为基础，同时也相应地推动这些理论的发展。

1、粗糙集和模糊集

模糊集和粗糙集理论在处理不确定性和不精确性问题方面都推广了经典集

合论，两个理论的比较和融合一直是人们感兴趣的话题。粗糙模糊集是模糊粗糙

集的特例。

2、粗糙集和知识空间

粗糙集理论和知识空间理论都是研究知识结构的理论；但他们用于解决不同

的实际问题。粗糙集主要研究如何对数据进行分析及知识发现；而知识空间着重

对问题集进行分析，从而对个体知识状态进行评估。如何将知识空间和粗糙集理

论结合正在成为一个新的研究方向。虽然粗糙集和知识空间研究对象不同，但从

粒计算的角度来看，它们都可看成由一些基本粒通过不同的方式构造粒结构的过

程。K其实是对知识从不同大小的粒度进行多层次的描述。

3、粗糙集和粒计算

粒计算是一门飞速发展的新学科。它融合了粗糙集、模糊集及人工智能等多

种理论的研究成果。词计算模型、粗糙集模型和商空间模型是3个主要的粒计算

(GranularCompuing，GrC)模型。粗糙集理论已经成为研究粒计算的重要工具。

基于粗日常随笔200字 糙桥的英语怎么说 集模型的粒计算，它的粒是一个划分，是一个特别的粒计算结构。基本

知识粒度的构造和知识表示方法的拓广，实质是将粗糙集的商集扩展成一个拓扑

空间，以此保证运算的封闭性，即用R(U/R)代替U/R，它是布尔代数(2U

，~，H，G)的一个子代数，则(U，R(U/R))构成一个拓扑空间。结合粗糙集理论

的粒计算方法已经在机器学习、数据分析、数据挖掘、规则提取、智能数据处理

和粒逻辑等方面取得了一定的应用。

五、粗糙集的应用研究

目前，基于粗糙集理论的应用研究主要集中在知识获取、基于粗糙集的计算

智能算法研究等方面。这些研究成果成功应用在许多领域，有的已经获得了商业

价值。

1、知识获取

知识获取是发现存在于数据库中有效的、新颖的、具有潜在效用的乃至最终

可理解的模式的非平凡过程。粗糙集理论可支持知识获取的多个步骤，如数据预

处理、属性约简、规则生成、数据依赖关系获取等。基于粗糙集的知识约简理论

发展为数据挖掘提供了许多有效的新方法。针对协调决策表，现已提出了求属性

约简的许多算法，如数据分析法、基于信息熵的属性约简算法、动态约简算法、

增量式算法、可辨识矩阵算法等。同时，讨论的信息系统的形式也越来越多，如

连续值信息系统、区间值信息系统、模糊值信息系统、集值信息系统等，并且相

应系统的约简理论也得到了发展。另一方面，随着概念格、偏序集等理论与粗糙

集理论的结合，基于概念格的约简方法、广义协调决策形式背景知识约简方法、

偏序关系下的决策形式背景规则提取与属性约简、对象概念格的属性约简方法、

基于用户偏好的属性约简、属性序下的快速约简算法、权值约简、基于群体智能

算法的属性方法等新方法也大量涌现。

2、面向领域的数据驱动的数据挖掘

简而言之，数据挖掘的目的就是从数据中挖掘出知识。在机器学习的许多方

法中，我们往往依赖于一些先验知识，比如：贝叶斯概率方法依赖于先验概率；

模糊集理论依赖于成员隶属度函数；多专家决策系统依赖于专家的权值属性。毫

无疑问地，依靠这些先验知识的帮助我们成功地解决了许多问题。但是，有些领

域的先验知识很难获得，比如网络入侵检测；另外，像外太空探索等新兴问题，

要获得其先验知识也是很困难的。因此，如何建立根据问题已有的信息，而不依

赖于先验知识获得问题解的计算模型具有非常重要的价值，可为真正的智能化数

据挖掘提供理论支撑。为此，有学者提出领域(用户)驱动的数据挖掘模型、数据

驱动的数据挖掘模型等，取得了一些初步研究成果。

3、其它应用领域

从应用的领域来看，基于粗糙集理论的应用除了我们上文提到的信息科学等

方面，还遍及其它许多领域。许多学者将粗糙集理论成功应用到了工业控制、医

学卫生及生物科学、交通运输、农业科学、环境科学与环境保护管理、安全科学、

社会科学、航空、航天和军事等领域。比如:电厂气温过热控制、虚拟现实的可

视化、对原棉纱线强度和纤维性能之间的知识规则提取、手写体识别、胸部X

线数字图像滤波增强、湖泊生态系统健康评定指数法的评价、医疗图像处理、遥

感数据处理、综合分类器设计与实现、铁路行车调度指挥、食品安全综合评价、

昆虫总科阶元分类、泥石流危险度区划指标选取、网络故障诊断、上市公司违规

行为预警、武器系统灰色关联评估和航空控制等等。

六、粗糙集未来展望

虽然粗糙集理论从提出至今只有二十几年的发展历史，但取得的研究成果是

令人瞩目的。在基于数据的决策与分析、机器学习、模式识别等计算机领域的成

功应用，逐渐被人们所重视。粗糙集理论研究目前正成为信息科学中的一个热点，

我们将这个理论小舟简笔画 目前的研究状况归纳总结并介绍给读者，希望我国更多的感兴趣

的研究同行更多地了解这个理论的研究工作，促进这一理论及其相关研究在我国

的发展。

参考文献

[1]王燕,王国胤,邓维斌.基于概念格的数据自主式不确定知识获取.模式识别与人工智

能,2007,20(5):6362642

[2]覃政仁.基于RoughSet的海量数据挖掘算法研究.重庆邮电大学,重庆,2004

[3]王志海,胡可云等.概念格上规则提取的一般算法与渐进式算法.计算机学

报,1999,22(1):66270

[4]刘少辉,盛秋戬,吴斌,史忠植,胡斐.Rough集高效算法的研究.计算机学

报,2003,26(5):5242529

[5]张铃,张钹.模糊商空间理论(模糊粒度计算方法).软件学报,2003,14(4):7702776