粗糙集理论.docx

粗糙集理论与应用研究综述王国胤1 Yiyu Yao2 于洪1,2(1重庆邮电大学计算机科学与技术研究所 重庆 400065)(2Department of Computer Science, University of Regina, Regina, Canada S4S 0A2){wanggy, yuhong}@, yyao@cs.uregina.ca摘要 本文在阐释粗糙集理论基本体系结构的基础上，从多个角度探讨粗糙集模型的研究思路，分析粗糙 集理论与模糊集、证据理论、粒计算、形式概念分析、知识空间等其他理论之间的联系，介绍国内外关于 粗糙集理论研究的主要方向和发展状况，讨论当前粗糙集理论研究的热点研究领域，以及将来需要重点研 究的主要问题关键词 粗糙集，模糊集，粒计算，形式概念分析，知识空间，智能信息处理A Survey on Rough Set Theory and Its ApplicationWang Guo-Yin1 Yao Yi-Yu2 Yu Hong1,21 Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, 4000652 Department of Computer Science, University of Regina, Regina, Saskatchewan, Canada, S4S 0A2Abstract This paper introduces the basic ideas and framework of rough set theory and the different views of knowledge representation in rough set theory, and then discusses the relations between the rough set theory and the other theories, such as fuzzy set, evidence theory, granular computing, formal concept analyzing, knowledge space, etc. Furthermore, the paper reviews the recent studies for this theory and a survey on its applications is also given. The future development trend of rough set theory is also discussed.Keywords rough set, fuzzy set, granular computing, formal concept analyzing, knowledge space, intelligent information processing本论文得到国家自然科学基金(N o. 60573068&N o. 60773113)、重庆市自然科学基金(N O.2008BA2017)和重庆市杰出青年科学基金显示桌面.scf(No.2008BA2041)资助.王国胤，男，1970年生，博士，教授，主要研究领域包括粗糙集、粒计算、神经网络、机器学习、数据挖掘、知识技术等。

1 引言智能信息处理是当前信息科学理论和应用研究中 的一个热点领域由于计算机科学与技术的发展，特 别是计算机网络的发展，每日每时为人们提供了大量 的信息，信息量的不断增长，对信息分析工具的要求 也越来越高，人们希望自动地从数据中获取其潜在的 知识特别是近20年间，知识发现(规则提取、数据 挖掘、机器学习)受到人工智能学界的广泛重视，知 识发现的各种不同方法应运而生粗糙集(Rough Set，有时也称Rough集、粗集) 理论是Pawlak教授于1982年提出的一种能够定量分析 处理不精确、不一致、不完整信息与知识的数学工具［1］ 粗糙集理论最初的原型来源于比较简单的信息模型， 它的基本思想是通过关系数据库分类归纳形成概念和 规则，通过等价关系的分类以及分类对于目标的近似 实现知识发现由于粗糙集理论思想新颖、方法独特，粗糙集理 论已成为一种重要的智能信息处理技术［2-4］，该理论已 经在机器学习与知识发现、数据挖掘、决策支持与分 析等方面得到广泛应用目前，有三个有关粗糙集的 系列国际会议，即：RSCTC、RSFDGrC和RSKT中 国学者在这方面也取得了很大的成果，从2001年开始 每年召开中国粗糙集与软计算学术会议； RSFDGRC2003 、 IEEE GrC2005 、 RSKT2006 、 IFKT2008、RSKT2008、IEEE GrC2008等一系列国际 学术会议在中国召开。

粗糙集理论与应用的核心基础是从近似空间导出 的一对近似算子，即上近似算子和下近似算子(又称 上、下近似集)经典Pawlak模型中的不分明关系是 一种等价关系，要求很高，限制了粗糙集模型的应用 因此，如何推广定义近似算子成为了粗糙集理论研究 的一个重点目前，常见的关于推广粗糙集理论的研究方法有 两种，即：构造化方法和公理化方法构造化方法是 以论域上的二元关系、划分、覆盖、邻域系统、布尔 子代数等作为基本要素，进而定义粗糙近似算子，从 而导出粗糙集代数系统公理化方法的基本要素是一 对满足某些公理的一元集合算子，近似算子的某些公 理能保证有一些特殊类型的二元关系的存在；反过来, 由二元关系通过构造性方法导出的近似算子一定满足 某些公理事实上，有两种形式来描述粗糙集，一个是从集 合的观点来进行，一个是从算子的观点来进行那么， 从不同观点采用不同的研究方法就得到粗糙集的各种 扩展模型扩展模型的研究以及基于其上的应用研究 已经成为新的研究热点粗糙集理论与其他处理不确定和不精确问题理论 的最显著的区别是它无需提供问题所需处理的数据集 合之外的任何先验信息 , 所以对问题的不确定性的描 述或处理可以说是比较客观的 , 由于这个理论未能包 含处理不精确或不确定原始数据的机制 , 所以这个理 论与概率论 , 模糊数学和证据理论等其他处理不确定 或不精确问题的理论有很强的互补性。

因此，研究粗 糙集理论和其他理论的关系也是粗糙集理论研究的重 点之一基于粗糙集理论的应用研究主要集中在属性约 简、规则获取、基于粗糙集的计算智能算法研究等方 面由于属性约简是一个NP-Hard问题，许多学者进行 了系统的研究基于粗糙集的约简理论发展为数据挖 掘提供了许多有效的新方法比如，针对不同的信息 系统（协调的和不协调的、完备的和不完备的），结 合信息论、概念格、群体智能算法技术等都有了相应 的研究成果基于粗糙集理论的应用也涌现在各行各业许多 学者将粗糙集理论应用到了工业控制［5-8］、医学卫生及 生物科学［9-11］、交通运输［12-14］、农业科学［15-16］、环境科 学与环境保护管理［17］、安全科学［18］、社会科学［19］、航 空、航天和军事等领域［20-21］粗糙集理论发展二十余年来，无论在理论研究还 是应用研究上都取得了很多成果从认知科学的角度 讲，我们如果要学习一个新的学科，就必须建立它的 系统体系结构，同时学习思维及计算方法，这样我们 就能从已知的结果推到未知的结果本文将在总结已 有的这些研究成果的基础上，帮助读者建立起一个这 样的系统体系结构，同时指出进一步的研究方向。

我 们将这个理论目前的研究状况介绍给信息科学工作者, 希望进一步推动并促进我国在这一领域的研究工作本文组织结构如下：第二部分介绍粗糙集理论基 础；第三部分介绍粗糙集模型研究，将从构造化方法 和公理化方法、面向集合的观点和面向算子的观点来 阐述；第四部分将探讨粗糙集理论和证据理论、模糊 集、形式概念分析、知识空间等的关系；第五部分是 基于粗糙集的研究以及应用最后是总结和展望2 粗糙集理论基础本节在回顾粗糙集基础概念的基础上，说明常见 的两种研究粗糙集的方法：构造化方法和公理化方法 并且，从集合观点和算子观点来解释粗糙集2.1 概念、可定义集为了对知识进行描述，首先需要知道什么是概念 从经典的角度来看，每个概念都包含其内涵和外延 为了给出概念内涵和外延的具体描述，我们考虑一个 简单的知识表达系统，即信息表信息表就是一组对 象的集合，对象通过一组属性来描述表1就是一个信息表的例子信息表 M 可以形式 化地表达 为四元组M 二（U, At,{V I a e At},{I I a e At}）表 1 中，aaU二{ x , x , ... x是有限非空对象的集合，也称为论1 2 6域，At ={头疼，肌肉疼，体温，流感}是有限非空的 属性集合。

V表示属性a e At的属性值的范围，即属 a性a的值域，I : U T V是一个信息函数如果 aaA匸At，则I （x）表示U中对象x在属性A上的属性A值表1 信息表实例Table 1 Ain Information1 Table个体编号头疼肌肉疼休温流感x是是1 I 1.1 1 1 1. 正常否1是是高是A2是是很高是x3否是正常否山4否否1 1 - 1 1 ”高否I x —否———是 彳艮高 —是—为了形式化地定义概念的内涵，可以采用决策逻 辑语言［22］来分析信息表我们定义和讨论的决策逻辑 语言L由原子公式组成，公式是一种（属性，数据）对, 用命题联词：与、或、非等通过标准的方法构成复合 公式公式是用来描述论域中对象的工具，可以用来 描述论域中具有某些性质的对象的子集例如在原子 公式中，有序对（头疼，是）解释为在属性a =头疼上值 为v二是的所有对象的描述当0为信息表M中的一个公式时，集合 m（e ）= {xe U ,片I 0称为M中公式°的含义含 M义m（0）的自变量是语言的公式，其值是信息表中对象 集合的子集m（0）就是那些具有公式0的性质的对象 的全体换句话说，公式0可以描述对象子集m（0）。

这样，就建立起了公式0和论域U的子集之间的关系利用决策逻辑语言 L ，可以给出概念的形式描 述：信息表M中的概念就是（0,m（0）），其中0 eL 概念（札m（0 ））的内涵是0，表示M中对对象子集 m®）的描述；概念他,m（0））的外延是m®），其含义 是满足公式0的所有对象的全体在粗糙集理论的很多应用中，经常考虑的只是一 个属性子集A匸At，即在决策逻辑语言中只考虑A中 的属性我们用符号L （A）表示由属性子集A定义的 语言将前面讨论中出现的L用L （A）来代替，相应 的结论也都成立考虑属性子集A匸At及其相应的语言L （A），可 定义集的形式化定义［23］如下定义1在信息表M中，如果称子集X匸U是可 被属性子集A匸At定义的，当且仅当在语言L （A）中 存在一个公式0使得X二m（0）否则，X称为不可 定义的值得注意的是，这里谈到的可定义，是指在属性 子集 A 上是可定义的例如，表1中，我们考虑属性子集 A ={头疼，肌肉 疼},子集X ={ x , x , x匕U,公式o：(头疼=1 1 2 3 1是)A(肌肉疼=是)那么在语言L (A)中，显然有 X = m3 )，子集{x , x , x }是可定义集。

而且，子1 1 1 2 3。