粗糙集与其他软计算理论结合情况进行综述研究.doc

1、粗糙集与其他软计算理论结合情况进行综述研究摘 要:最近几年,对于粗糙集的研究越来越多,尤其是粗糙集与其他软计算理论相结合的研究更为突出,取得了很多有意义的研究成果。因此,将此方面目前的主要研究情况进行一个总结,主要介绍了目前粗糙集与模糊集、神经网络、证据理论等一些其他软计算理论之间的结合研究情况,并对这方面未来的发展提出了自己的一些观点。 关键词:粗糙集; 软计算; 模糊集; 粗糙模糊集; 模糊粗糙集 Survey on combination of rough sets and other soft computing theories TANG Jian-guo?1,2, William

2、ZHU?1,SHE Kun?1, CHEN Wen?1,3 (1.School of Computer Science Engineering, University of Electronic Science Technology of China, Chengdu 611731, China;2.School of Computer Science Engineering, Xinjiang University of Finance Economics, Urumqi 830012, China;3.Dept. of Computer Science, Fuzhou Polytechni

3、c, Fuzhou 350108, China)?Abstract:In recent years, there are more and more research on rough sets.Especially,the combinations of rough sets and other soft computing theories have became more prominent,and have made a lot of meaningful research results. In view of this, this paper gave a summary of t

4、he current status of these major researchs.It focused on the combination of rough sets and other soft computing theories such as fuzzy sets,neural net,evidence theory,and so on. In the end, it put forward the own viewpoint of the future development in this area. Key words:rough sets; soft computing;

5、 fuzzy sets; rough-fuzzy sets; fuzzy-rough sets 0 引言 随着计算机技术和网络技术的迅速发展与广泛应用,人类社会进入了信息爆炸的时代,如何处理并有效利用这些信息已经成为世界各国学者研究的热点问题。软计算就是在这种需求背景下出现的一种新技术。软计算最初是由模糊集理论的创始人 Zadeh1在 1994 年提出的,它是一种通过对不确定、不精确及不完全真值的数据进行容错处理从而取得低代价、易控制处理以及鲁棒性高的方法的集合。目前,软计算的理论与方法主要包括神经网络、模糊集、粗糙集、遗传算法、证据理论等。 粗糙集是在最近几年发展较快的一门理论,它是一种用于

6、分析和处理不确定、不精确问题的数学理论,是由波兰数学家 Pawlak2在 1982 年提出的。它的基本思想是通过论域上的等价关系将论域划分成若干个等价类,然后利用这些知识对所需处理的不精确或不确定的事物进行一个近似的刻画。 粗糙集理论最大的特点是它对论域的划分只依赖于所需处理的数据集合本身,不需要任何先验信息,所以对问题不确定性的描述或处理是比较客观的。这一点也是它与其他软计算理论之间的显著区别。不过,粗糙集在原始数据不精确或不确定时,是无法处理数据的,这恰好与软计算中的其他理论有很强的互补性。因此,粗糙集与其他软计算理论和方法的结合已成为粗糙集研究中的一个重要内容。本文将对粗糙集与模糊集、神

7、经网络、概念格以及证据理论等软计算理论的结合研究情况进行介绍,并指出这方面未来的研究发展方向。 1 粗糙集理论概述 粗糙集是一种用于解决不确定性问题的数学工具。粗糙集理论中知识被理解为对事物进行区分的能力,在形式上表现为对论域的划分,因而通过论域上的等价关系表示。粗糙集通过一对上、下近似算子来刻画事物,它不需要数据以外的任何先验知识,因此具有很高的客观性。目前,粗糙集被广泛用于决策分析、机器学习、数据挖掘等领域38。 1.1 粗糙集中的基本概念9 定义 1 论域、概念。设 U 是所需研究的对象组成的非空有限集合,称为一个论域,即论域 U。论域 U 的任意一个子集 XU,称为论域 U 的一个概念

8、。论域 U 中任意一个子集簇称为关于 U 的知识。 定义 2 知识库。给定一个论域 U 和 U 上的一簇等价关系 S,称二元组K=(U,S)是关于论域 U 的知识库或近似空间。 定义 3 不可分辨关系。给定一个论域 U 和 U 上的一簇等价关系 S,若PS,且 P?,则P 仍然是论域 U 上的一个等价关系,称为 P 上的不可分辨关系,记做 IND(P)。 称划分 U/IND(P)为知识库 K=(U,S)中关于论域 U 的 P-基本知识。 定义 4 上近似、下近似。设有知识库 K=(U,S)。其中 U 为论域,S 为U 上的一簇等价关系。对于?XU 和论域 U 上的一个等价关系 RIND(K),

9、则 X 关于 R 的下近似和上近似分别为 下近似 R(X)=YU/R|YX 上近似 R(X)=YU/R|YX=? 集合的上近似和下近似是粗糙集中最核心的概念,粗糙集的数字特征以及拓扑特征都是由它们来描述和刻画的。当 R=(X)时,称 X 是 R-精确集;当R(X)(X)时,称 X 是 R-粗糙集,即 X 是粗糙集。 1.2 粗糙集中的知识约简 在一个信息系统中,有些描述对象的属性可能是不必要的,因此需要将这些冗余的属性予以删除来提高系统的效率。 给定一个知识库 K=(U,S),对于 PS,?RP,如果 IND(P)=IND(P-R)成立,则称 R 为 P 中不必要的,否则称 R 为 P 中必要

10、的。如果 P 中的每个 R都是必要的,则称 P 是独立的。 定义 5 约简、核。给定一个知识库 K=(U,S)和知识库上的一簇等价关系 PS,对于任意 GP,如果 G 是独立的,并且 IND(G)=IND(P),则称 G 是 P的一个约简,记为 GRED(P)。P 中所有必要的知识组成的集合称为 P 的核,记为 Core(P)。约简与核的关系为 Core(P)=RED(P),即核是约简的交集。 常见的粗糙集中知识约简的算法主要有盲目删除约简法、基于Pawlak 属性重要度的约简法和基于差别矩阵的约简法。其中,盲目删除法是通过任意选择一个属性,看其是否是必要的,如果是必要的则保留,否则删除该属性

11、,这种方法简单直观,但约简的结果却不一定让人满意;基于Pawlak 属性重要度的方法是根据属性的重要度来进行约简,其特点是用这种方法可以得到信息系统的最优约简或次优约简,但它却存在找不到一个约简可能性;基于差别矩阵的方法是把论域中区分任意两个对象的属性集合用矩阵的形式表示出来,通过这个矩阵可以直观地得出信息系统的核和所有约简,这种方法虽然能很直观地得出信息系统的所有约简和核,但当问题规模较大时会产生组合爆炸。此外,也有学者对知识的约简提出了一些改进的新算法。文献10, 11基于邻域对粗糙集的属性和属性值的约简进行了优化处理;文献12提出了一种新的属性约简方法 ReCA,提高了对连续性属性的数据

12、的知识约简性能。粗糙集在处理不确定问题中新颖独特的方法引起了大量学者的兴趣,很多学者对该理论作出了扩展性的研究1317,包括覆盖粗糙集1821、变精度的粗糙集22等很多新的内容。文献23对粗集的公理化进行了深入的研究,得到了两个关于粗集的最小公理组;文献24通过松弛对象之间的不可分辨和相容性条件,给出了一种新的基于和谐关系的粗糙集模型;文献25构造了关于决策表对象的区分条件,并借助区分矩阵与区分函数提出了一种完备的约简方法;文献16将组合熵和组合粒度的概念引入到了粗糙集中,确立了两者之间的关系;文献26提出了在不协调目标信息系统中知识约简的新方法;文献27提出了属性左划分和属性右划分的观点,设

13、计了一种基于划分的属性约简算法 ARABP;文献28从属性和信息熵的角度探讨了粗糙集的不确定性的度量。这些研究极大地推动了粗糙集理论的发展和应用。 2 粗糙集与模糊集 模糊集理论是由美国学者 Zadeh 于 1965 年提出的,模糊集指的是这样一种集合,这个集合中的每个元素都是在一定程度上隶属于或者不隶属于这个集合,用于衡量这种隶属程度的函数被称为隶属函数。模糊集中的任意一个元素都是通过隶属函数来确定一个隶属度与之一一对应。 2.1 模糊集理论的基本概念 定义 6 隶属度、隶属函数。设 U 是一个论域,A 是 U 上的一个模糊集,如果?xU,均能确定一个数 ?A(x)0,1来表示 x 隶属于

14、A 的程度,称这个数是 x 对 A 的隶属度。其中 ?A(x)是这样一个映射:?A:U0,1,x|?A(x)0,1,?A(x)称为 A 的隶属函数。 隶属函数是模糊集的核心基础概念,由它来确定和描述一个模糊集。对于同一个论域,不同的隶属函数确定不同的模糊集,如 ?A(x)和?B(x)是论域 U 上的两个不同的隶属函数,则由它们可以确定两个不同的模糊集 A 和 B。模糊集是经典集合理论的扩展,当一个模糊集的隶属度只能取 0 或 1 时,即 ?A(x)0,1,模糊集 A 便退化为一个经典集合论中的普通集合。 2.2 模糊集与粗糙集的互补性 在模糊集中,隶属函数一般是根据专家的经验知识或者通过一些统

15、计数据结果来确定,具有很大的主观性,而缺乏一定的客观性,这也是模糊集的一个根本缺陷。粗糙集中的上近似和下近似是由已知知识库中客观存在的对象来确定的,不需要任何先前的假设条件,具有很强的客观性。但是,在实际的生活中,有很多已知的、确定的而无须再去进行判断的先验知识,如果能直接利用这些知识来解决问题,会带来很高的效率,而这一点又正是粗糙集所欠缺的。由此可见,粗糙集与模糊集各自的特点之间具有很强的互补性,把它们结合起来解决问题通常都会比单独使用它们更为有效。在这方面的研究已经有了很大的进展和很多的具体应用,粗糙模糊集和模糊粗糙集29便是其中两个重要的研究成果。 粗糙模糊集主要是通过对模糊集中的隶属函

16、数采用粗糙集中集合的上近似与下近似的方法来进行描述,以此来增强模糊集处理问题的客观性。它是把粗糙集中的上下近似的特点融入到了模糊集当中,将模糊集中的隶属函数概念扩展成上近似的隶属函数和下近似的隶属函数,由这两个隶属函数所确定的隶属度值来形成一个区间;用这个区间来描述一个元素隶属于一个模糊集的可能性范围,而不再是之前的元素与隶属度之间一一对应的情况,即 xA 的隶属度不再是 ?A(x)0,1,而是在下近似的隶属度,上近似的隶属度这个区间。粗糙模糊集的基本定义如下: 定义 7 粗糙模糊集。设 U 是一个论域,R 是 U 上的一个等价关系,A是 U 上的一个模糊集,?A(x)是 A 的隶属度函数,R

17、(A)和(A)分别表示 A的上近似和下近似,它们对应的隶属函数是: a)下近似的隶属函数 R(A)(x?R)=inf?A(x)|xx?R,?xX; b)上近似的隶属函数 (A)=sup?A(x)|xx?R,?xX。 称 R(X)=(R(X),(X)为粗糙模糊集。 模糊粗糙集是把模糊集中的隶属函数的概念应用到了粗糙集当中,根据模糊集中的隶属函数来确定粗糙集中的一个等价关系,即把由隶属函数得到的隶属度相同的元素归属于同一等价类,从而得到论域 U 上的一个划分。这其实就是将模糊集中已知的、确定的而无须再判断的知识转变为粗糙集中的等价关系,得到粗糙集上的一簇等价类,提高粗糙集处理问题的效率。模糊粗糙集

18、的基本概念定义如下: 定义 8 模糊粗糙集。给定一个论域 U,A 是 U 的一个模糊集,?A(x)是 A 的隶属函数。设 R?A 为 U 上的一个等价关系,且满足对于?x,yU,xR?Ay?A(x)=?A(y)。令xR?A 表示以 x 为代表元素的等价类,若 XU,X?,则 X 关于 R?A 的下近似和上近似分别为 下近似 R?A(X)=xR?A|xR?AX 上近似 ?A(X)=xR?A|xR?AX? 若 R?A(X)=?A(X),称 X 是 R?A-可定义集;若 R?A(X)?A(X),称 X 是R?A-模糊粗糙集。 粗糙模糊集和模糊粗糙集对粗糙集和模糊集进行很好的互补性处理,已经在很多领域

19、得到了实际应用3033,并取得了很好的效果。有很多学者对它们进行了进一步的比较研究3437,作了一些改进和扩展。文献38在覆盖粗糙集的基础上,结合模糊集的最近寻常集,引入了覆盖广义粗糙集模糊度的概念,给出了一种模糊度计算方法,并证明了该模糊度的一些重要性质;文献39提出了模糊不可分辨关系的概念,加强了粗糙集对模糊值属性处理能力。 3 粗糙集与神经网络 神经网络是在现代神经生物学研究成果的基础上发展起来的一种模仿人脑信息处理机制的网络系统。它具有在有监督或无监督的情况下从输入数据中进行学习的能力,被广泛地应用于数据挖掘4042、模式识别4347、信号处理48,49、预测50, 51等领域。 3.

20、1 神经网络基本知识 神经网络52是一个由简单处理单元构成的规模宏大的并行分布式处理器,天然具有存储经验知识和使之可用的特性。神经元是神经网络最基本的信息处理单元,它具有接收和传递信息的功能。一个神经网络是由众多的神经元组成,每个神经元接收其他神经元和外界的输入信息。神经网络的结构通常都是以层的方式来组织的,一般包含一个输入层、任意多个隐藏层和一个输出层,每层都由众多的神经元组成。其基本原理是输入层神经元接收外界环境的信息输入,隐藏层神经元将隐藏层单元的信息输出至输出层,输出层将信息输出至外界。根据神经元信息的输出是否存在反馈,又将神经网络分为前馈神经网络和递归神经网络。3.2 粗糙集与神经网

21、络的联系 粗糙集对事物的识别和判断是基于论域上的不可辨关系,它不需要任何先验的信息。通过系统参数的重要度函数来获得描述事物各个属性的重要度,依此不仅可以进行属性的约简,而且也可以用于把握事物的主要特征,提高识别能力。粗糙集可以实现对信息系统的知识约简,去除冗余的信息,减少输入信息的空间维度,提高处理效率。不过粗糙集的抗干扰能力较差,对于噪声较为敏感,在噪声较大的环境中就表现得不尽如人意。神经网络的特点就是通过训练和学习产生一个非线性的映射,模拟人的思维方式,具有很好的自适应性,可以实现有监督和无监督的学习,并能够对信息进行并行处理;同时,它具有很好的抑制噪声的能力。但是神经网络也有很明显的缺陷,它无法对输入的信息进行有用性或冗余性的判断,因此不能对输入的信息进行简化,这使得它在处理空间维数较大的信息时会很困难和低效。 粗糙集与神经网络各自的长处和短处让人们发现它们具有很好的互补性;另外,从对人类思维模拟的角度看,粗糙集方法模拟人类的抽象逻辑思维,而神经网络方法模拟人类的形象直觉思维。因此,将两者结合起来,用粗糙集的特点去弥补神经网络在处理髙维度数据上的不足,而用神经网络的抗干扰强的特性去弥补粗糙集对噪声的敏感性,将模拟人的抽象思维与形象直觉思维相结合,就会得到更好的效果。目前,这方面的研究已成为一个重要的研究方向。