摘 要:最近几年,对于粗糙集的研究越来越多,尤其是粗糙集与其他软计算理论相结合的研究更为突出,取得了很多有意义的研究成果。因此,将此方面目前的主要研究情况进行一个总结,主要介绍了目前粗糙集与模糊集、神经网络、证据理论等一些其他软计算理论之间的结合研究情况,并对这方面未来的发展提出了自己的一些观点。
关键词:粗糙集; 软计算; 模糊集; 粗糙模糊集; 模糊粗糙集
Survey on combination of rough sets and other soft computing theories
TANG Jian-guo??1,2, William 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 Polytechnic, 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 the 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; fuzzy sets; rough-fuzzy sets; fuzzy-rough sets
0 引言
随着计算机技术和网络技术的迅速发展与广泛应用,人类社会进入了信息爆炸的时代,如何处理并有效利用这些信息已经成为世界各国学者研究的热点问题。软计算就是在这种需求背景下出现的一种新技术。软计算最初是由模糊集理论的创始人Zadeh[1]在1994年提出的,它是一种通过对不确定、不精确及不完全真值的数据进行容错处理从而取得低代价、易控制处理以及鲁棒性高的方法的集合。目前,软计算的理论与方法主要包括神经网络、模糊集、粗糙集、遗传算法、证据理论等。
粗糙集是在最近几年发展较快的一门理论,它是一种用于分析和处理不确定、不精确问题的数学理论,是由波兰数学家 Pawlak[2]在1982年提出的。它的基本思想是通过论域上的等价关系将论域划分成若干个等价类,然后利用这些知识对所需处理的不精确或不确定的事物进行一个近似的刻画。
粗糙集理论最大的特点是它对论域的划分只依赖于所需处理的数据集合本身,不需要任何先验信息,所以对问题不确定性的描述或处理是比较客观的。这一点也是它与其他软计算理论之间的显著区别。不过,粗糙集在原始数据不精确或不确定时,是无法处理数据的,这恰好与软计算中的其他理论有很强的互补性。因此,粗糙集与其他软计算理论和方法的结合已成为粗糙集研究中的一个重要内容。本文将对粗糙集与模糊集、神经网络、概念格以及证据理论等软计算理论的结合研究情况进行介绍,并指出这方面未来的研究发展方向。
1 粗糙集理论概述
粗糙集是一种用于解决不确定性问题的数学工具。粗糙集理论中知识被理解为对事物进行区分的能力,在形式上表现为对论域的划分,因而通过论域上的等价关系表示。粗糙集通过一对上、下近似算子来刻画事物,它不需要数据以外的任何先验知识,因此具有很高的客观性。目前,粗糙集被广泛用于决策分析、机器学习、数据挖掘等领域[3~8]。
1.1 粗糙集中的基本概念[9]
定义1 论域、概念。设U是所需研究的对象组成的非空有限集合,称为一个论域,即论域U。论域U的任意一个子集XU,称为论域U的一个概念。论域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上的一簇等价关系。对于?X∈U和论域U上的一个等价关系R∈IND(K),则X关于R的下近似和上近似分别为
下近似 R(X)=∪{Y∈U/R|YX}
上近似 R(X)=∪{Y∈U/R|Y∩X=?}
集合的上近似和下近似是粗糙集中最核心的概念,粗糙集的数字特征以及拓扑特征都是由它们来描述和刻画的。当R=(X)时,称X是R-精确集;当R(X)≠(X)时,称X是R-粗糙集,即X是粗糙集。
1.2 粗糙集中的知识约简
在一个信息系统中,有些描述对象的属性可能是不必要的,因此需要将这些冗余的属性予以删除来提高系统的效率。
给定一个知识库K=(U,S),对于PS,?R∈P,如果IND(P)=IND(P-{R})成立,则称R为P中不必要的,否则称R为P中必要的。如果P中的每个R都是必要的,则称P是独立的。
定义5 约简、核。给定一个知识库K=(U,S)和知识库上的一簇等价关系PS,对于任意GP,如果G是独立的,并且IND(G)=IND(P),则称G是P的一个约简,记为G∈RED(P)。P中所有必要的知识组成的集合称为P的核,记为Core(P)。约简与核的关系为Core(P)=∩RED(P),即核是约简的交集。
常见的粗糙集中知识约简的算法主要有盲目删除约简法、基于Pawlak属性重要度的约简法和基于差别矩阵的约简法。其中,盲目删除法是通过任意选择一个属性,看其是否是必要的,如果是必要的则保留,否则删除该属性,这种方法简单直观,但约简的结果却不一定让人满意;基于Pawlak属性重要度的方法是根据属性的重要度来进行约简,其特点是用这种方法可以得到信息系统的最优约简或次优约简,但它却存在找不到一个约简可能性;基于差别矩阵的方法是把论域中区分任意两个对象的属性集合用矩阵的形式表示出来,通过这个矩阵可以直观地得出信息系统的核和所有约简,这种方法虽然能很直观地得出信息系统的所有约简和核,但当问题规模较大时会产生组合爆炸。此外,也有学者对知识的约简提出了一些改进的新算法。文献[10, 11]基于邻域对粗糙集的属性和属性值的约简进行了优化处理;文献[12]提出了一种新的属性约简方法ReCA,提高了对连续性属性的数据的知识约简性能。
粗糙集在处理不确定问题中新颖独特的方法引起了大量学者的兴趣,很多学者对该理论作出了扩展性的研究[13~17],包括覆盖粗糙集[18~21]、变精度的粗糙集[22]等很多新的内容。文献[23]对粗集的公理化进行了深入的研究,得到了两个关于粗集的最小公理组;文献[24]通过松弛对象之间的不可分辨和相容性条件,给出了一种新的基于和谐关系的粗糙集模型;文献[25]构造了关于决策表对象的区分条件,并借助区分矩阵与区分函数提出了一种完备的约简方法;文献[16]将组合熵和组合粒度的概念引入到了粗糙集中,确立了两者之间的关系;文献[26]提出了在不协调目标信息系统中知识约简的新方法; 文献[27]提出了属性左划分和属性右划分的观点,设计了一种基于划分的属性约简算法ARABP;文献[28]从属性和信息熵的角度探讨了粗糙集的不确定性的度量。这些研究极大地推动了粗糙集理论的发展和应用。