粗糙集理论

《计算机学报》2009年7期粗糙集理论与应用研究综述王国胤1YiyuYao2于洪1,2(1重庆邮电大学计算机科学与技术研究所重庆400065)(2DepartmentofComputerScience,UniversityofRegina,Regina,CanadaS4S0A2){wanggy,yuhong}@cqupt.edu.cn,[e-mail]摘要本文在阐释粗糙集理论基本体系结构的基础上，从多个角度探讨粗糙集模型的研究思路，分析粗糙集理论与模糊集、证据理论、粒计算、形式概念分析、知识空间等其他理论之间的联系，介绍国内外关于粗糙集理论研究的主要方向和发展状况，讨论当前粗糙集理论研究的热点研究领域，以及将来需要重点研究的主要问题。关键词粗糙集，模糊集，粒计算，形式概念分析，知识空间，智能信息处理ASurveyonRoughSetTheoryandItsApplicationWangGuo-Yin1YaoYi-Yu2YuHong1,21InstituteofComputerScienceandTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing,4000652DepartmentofComputerScience,UniversityofRegina,Regina,Saskatchewan,Canada,S4S0A2AbstractThispaperintroducesthebasicideasandframeworkofroughsettheoryandthedifferentviewsofknowledgerepresentationinroughsettheory,andthendiscussestherelationsbetweentheroughsettheoryandtheothertheories,suchasfuzzyset,evidencetheory,granularcomputing,formalconceptanalyzing,knowledgespace,etc.Furthermore,thepaperreviewstherecentstudiesforthistheoryandasurveyonitsapplicationsisalsogiven.Thefuturedevelopmenttrendofroughsettheoryisalsodiscussed.Keywordsroughset,fuzzyset,granularcomputing,formalconceptanalyzing,knowledgespace,intelligentinformationprocessing1引言智能信息处理是当前信息科学理论和应用研究中的一个热点领域。由于计算机科学与技术的发展，特别是计算机网络的发展，每日每时为人们提供了大量的信息，信息量的不断增长，对信息分析工具的要求也越来越高，人们希望自动地从数据中获取其潜在的知识。特别是近20年间，知识发现（规则提取、数据挖掘、机器学习）受到人工智能学界的广泛重视，知识发现的各种不同方法应运而生。粗糙集（RoughSet，有时也称Rough集、粗集）理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具[1]。粗糙集理论最初的原型来源于比较简单的信息模型，它的基本思想是通过关系数据库分类归纳形成概念和规则，通过等价关系的分类以及分类对于目标的近似实现知识发现。由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种重要的智能信息处理技术[2-4]，该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用。目前，有三个有关粗糙集的系列国际会议，即：RSCTC、RSFDGrC和RSKT。中国学者在这方面也取得了很大的成果，从2001年开始每年召开中国粗糙集与软计算学术会议；RSFDGRC2003、IEEEGrC2005、RSKT2006、IFKT2008、RSKT2008、IEEEGrC2008等一系列国际学术会议在中国召开。粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子，即上近似算子和下近似算子（又称上、下近似集）。经典Pawlak模型中的不分明关系是一种等价关系，要求很高，限制了粗糙集模型的应用。因此，如何推广定义近似算子成为了粗糙集理论研究的一个重点。目前，常见的关于推广粗糙集理论的研究方法有两种，即：构造化方法和公理化方法。构造化方法是以论域上的二元关系、划分、覆盖、邻域系统、布尔子代数等作为基本要素，进而定义粗糙近似算子，从而导出粗糙集代数系统。公理化方法的基本要素是一对满足某些公理的一元集合算子，近似算子的某些公理能保证有一些特殊类型的二元关系的存在；反过来,由二元关系通过构造性方法导出的近似算子一定满足某些公理。事实上，有两种形式来描述粗糙集，一个是从集本论文得到国家自然科学基金(No.60573068&No.60773113)、重庆市自然科学基金(No.2008BA2017)和重庆市杰出青年科学基金显示桌面.scf(No.2008BA2041)资助.王国胤，男，1970年生，博士，教授，主要研究领域包括粗糙集、粒计算、神经网络、机器学习、数据挖掘、知识技术等。YiyuYao，男，1962年生，博士，教授，主要研究领域包括Rough集、粒计算、信息检索、WEB智能、认知信息学和数据挖掘等。《计算机学报》2009年7期合的观点来进行，一个是从算子的观点来进行。那么，从不同观点采用不同的研究方法就得到粗糙集的各种扩展模型。扩展模型的研究以及基于其上的应用研究已经成为新的研究热点。粗糙集理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的,由于这个理论未能包含处理不精确或不确定原始数据的机制,所以这个理论与概率论,模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性。因此，研究粗糙集理论和其他理论的关系也是粗糙集理论研究的重点之一。基于粗糙集理论的应用研究主要集中在属性约简、规则获取、基于粗糙集的计算智能算法研究等方面。由于属性约简是一个NP-Hard问题，许多学者进行了系统的研究。基于粗糙集的约简理论发展为数据挖掘提供了许多有效的新方法。比如，针对不同的信息系统（协调的和不协调的、完备的和不完备的），结合信息论、概念格、群体智能算法技术等都有了相应的研究成果。基于粗糙集理论的应用也涌现在各行各业。许多学者将粗糙集理论应用到了工业控制[5-8]、医学卫生及生物科学[9-11]、交通运输[12-14]、农业科学[15-16]、环境科学与环境保护管理[17]、安全科学[18]、社会科学[19]、航空、航天和军事等领域[20-21]。粗糙集理论发展二十余年来，无论在理论研究还是应用研究上都取得了很多成果。从认知科学的角度讲，我们如果要学习一个新的学科，就必须建立它的系统体系结构，同时学习思维及计算方法，这样我们就能从已知的结果推到未知的结果。本文将在总结已有的这些研究成果的基础上，帮助读者建立起一个这样的系统体系结构，同时指出进一步的研究方向。我们将这个理论目前的研究状况介绍给信息科学工作者,希望进一步推动并促进我国在这一领域的研究工作。本文组织结构如下：第二部分介绍粗糙集理论基础；第三部分介绍粗糙集模型研究，将从构造化方法和公理化方法、面向集合的观点和面向算子的观点来阐述；第四部分将探讨粗糙集理论和证据理论、模糊集、形式概念分析、知识空间等的关系；第五部分是基于粗糙集的研究以及应用。最后是总结和展望。2粗糙集理论基础本节在回顾粗糙集基础概念的基础上，说明常见的两种研究粗糙集的方法：构造化方法和公理化方法。并且，从集合观点和算子观点来解释粗糙集。2.1概念、可定义集为了对知识进行描述，首先需要知道什么是概念。从经典的角度来看，每个概念都包含其内涵和外延。为了给出概念内涵和外延的具体描述，我们考虑一个简单的知识表达系统，即信息表。信息表就是一组对象的集合，对象通过一组属性来描述。表1就是一个信息表的例子。信息表M可以形式化地表达为四元组(,,{|},{|})aaMUAtVaAtIaAt。表1中，126{,,...,}Uxxx是有限非空对象的集合，也称为论域，At＝{头疼，肌肉疼，体温，流感}是有限非空的属性集合。aV表示属性aAt的属性值的范围，即属性a的值域，:aaIUV是一个信息函数。如果AAt，则()AIx表示U中对象x在属性A上的属性值。表1信息表实例Table1AnInformationTable个体编号头疼肌肉疼体温流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是为了形式化地定义概念的内涵，可以采用决策逻辑语言[22]来分析信息表。我们定义和讨论的决策逻辑语言L由原子公式组成，公式是一种(属性，数据)对，用命题联词：与、或、非等通过标准的方法构成复合公式。公式是用来描述论域中对象的工具，可以用来描述论域中具有某些性质的对象的子集。例如在原子公式中，有序对(头疼,是)解释为在属性“a=头疼”上值为“v＝是”的所有对象的描述。当为信息表M中的一个公式时，集合(){,|}MmxUx称为M中公式的含义。含义()m的自变量是语言的公式，其值是信息表中对象集合的子集。()m就是那些具有公式的性质的对象的全体。换句话说，公式可以描述对象子集()m。这样，就建立起了公式和论域U的子集之间的关系。利用决策逻辑语言L，可以给出概念的形式描述：信息表M中的概念就是(,())m，其中L。概念(,())m的内涵是，表示M中对对象子集()m的描述；概念(,())m的外延是()m，其含义是满足公式的所有对象的全体。在粗糙集理论的很多应用中，经常考虑的只是一个属性子集AAt，即在决策逻辑语言中只考虑A中的属性。我们用符号()AL表示由属性子集A定义的语言。将前面讨论中出现的L用()AL来代替，相应的结论也都成立。考虑属性子集AAt及其相应的语言()AL，可定义集的形式化定义[23]如下。定义1在信息表M中，如果称子集XU是可被属性子集AAt定义的，当且仅当在语言()AL中存在一个公式使得()Xm。否则，X称为不可定义的。值得注意的是，这里谈到的可定义，是指在属性子集A上是可定义的。《计算机学报》2009年7期例如，表1中，我们考虑属性子集A={头疼，肌肉疼}，子集1123{,,}XxxxU＝，公式1:(头疼＝是)(肌肉疼＝是)。那么在语言()AL中，显然有11()Xm，子集123{,,}xxx是可定义集。而且，子集X2={x4,x6}、X3={x5}也是可定义集，满足的公式分别是：2:(头疼＝否)(肌肉疼＝是)；3:(头疼＝否)(肌肉疼＝否)。根据定义1，可定义集的全体表示为：(,()){()|()}.DefUAmALL如果概念的外延能用逻辑公式简洁地表达，那它就是一个可定义的概念；从这个角度讲，概念的外延就是可定义集。类似地，由语言()AL定义的概念集合表示为：(,()){(,())|()}.DefConUAmALL很明显，如果两个对象xi,xj是等价的，那么他们在语言()AL中由相同的公式描述，或者说他们在A上的各个属性值相同。刚才得到的可定义集就是在属性集合A上的等价关系()EA在论域U上产生的划分，记为：()/(){[]|}EAUEAxxU，()[]EAx是由关系()EA确定的等价类，同一个等价类中的对象是不可分辨的，所以，有时我们也称等价关系为不可分辨关系。上例中，U/E(A)={{x1,x2,x3},{x4,x6},{x5}}。等价类()[]EAx的并显然是可定义集。比如，考虑子集X={x1,x2,x3,x4,x6}