粗糙集与其他软计算理论结合情况进行综述研究
摘 要:最近几年,对于粗糙集的研究越来越多,尤其是粗糙集与其他软计算理论相结合的研究更为突出,取得了很多有意义的研究成果。因此,将此方面目前的主要研究情况进行一个总结,主要介绍了目前粗糙集与模糊集、神经网络、证据理论等一些其他软计算理论之间的结合研究情况,并对这方面未来的发展提出了自己的一些观点。
关键词:粗糙集; 软计算; 模糊集; 粗糙模糊集; 模糊粗糙集
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]从属性和信息熵的角度探讨了粗糙集的不确定性的度量。这些研究极大地推动了粗糙集理论的发展和应用。
2 粗糙集与模糊集
模糊集理论是由美国学者Zadeh于1965年提出的,模糊集指的是这样一种集合,这个集合中的每个元素都是在一定程度上隶属于或者不隶属于这个集合,用于衡量这种隶属程度的函数被称为隶属函数。模糊集中的任意一个元素都是通过隶属函数来确定一个隶属度与之一一对应。
2.1 模糊集理论的基本概念
定义6 隶属度、隶属函数。设U是一个论域,A是U上的一个模糊集,如果?x∈U,均能确定一个数μ?A(x)∈[0,1]来表示x隶属于A的程度,称这个数是x对A的隶属度。其中μ?A(x)是这样一个映射:μ?A:U→[0,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 模糊集与粗糙集的互补性
在模糊集中,隶属函数一般是根据专家的经验知识或者通过一些统计数据结果来确定,具有很大的主观性,而缺乏一定的客观性,这也是模糊集的一个根本缺陷。粗糙集中的上近似和下近似是由已知知识库中客观存在的对象来确定的,不需要任何先前的假设条件,具有很强的客观性。但是,在实际的生活中,有很多已知的、确定的而无须再去进行判断的先验知识,如果能直接利用这些知识来解决问题,会带来很高的效率,而这一点又正是粗糙集所欠缺的。由此可见,粗糙集与模糊集各自的特点之间具有很强的互补性,把它们结合起来解决问题通常都会比单独使用它们更为有效。在这方面的研究已经有了很大的进展和很多的具体应用,粗糙模糊集和模糊粗糙集[29]便是其中两个重要的研究成果。
粗糙模糊集主要是通过对模糊集中的隶属函数采用粗糙集中集合的上近似与下近似的方法来进行描述,以此来增强模糊集处理问题的客观性。它是把粗糙集中的上下近似的特点融入到了模糊集当中,将模糊集中的隶属函数概念扩展成上近似的隶属函数和下近似的隶属函数,由这两个隶属函数所确定的隶属度值来形成一个区间;用这个区间来描述一个元素隶属于一个模糊集的可能性范围,而不再是之前的元素与隶属度之间一一对应的情况,即x∈A的隶属度不再是μ?A(x)∈[0,1],而是在[下近似的隶属度,上近似的隶属度]这个区间。粗糙模糊集的基本定义如下:
定义7 粗糙模糊集。设U是一个论域,R是U上的一个等价关系,A是U上的一个模糊集,μ?A(x)是A的隶属度函数,R(A)和(A)分别表示A的上近似和下近似,它们对应的隶属函数是:
a)下近似的隶属函数μR(A)([x]?R)=inf{μ?A(x)|x∈[x]?R},?x∈X;
b)上近似的隶属函数μ(A)=sup{μ?A(x)|x∈[x]?R},??x∈X。
称R(X)=(R(X),(X))为粗糙模糊集。
模糊粗糙集是把模糊集中的隶属函数的概念应用到了粗糙集当中,根据模糊集中的隶属函数来确定粗糙集中的一个等价关系,即把由隶属函数得到的隶属度相同的元素归属于同一等价类,从而得到论域U上的一个划分。这其实就是将模糊集中已知的、确定的而无须再判断的知识转变为粗糙集中的等价关系,得到粗糙集上的一簇等价类,提高粗糙集处理问题的效率。模糊粗糙集的基本概念定义如下:
定义8 模糊粗糙集。给定一个论域U,A是U的一个模糊集,μ?A(x)是A的隶属函数。设R?A为U上的一个等价关系,且满足对于?x,y∈U,xR?Ay?μ?A(x)=μ?A(y)。令[x]R??A表示以x为代表元素的等价类,若XU,X≠?,则X关于R?A的下近似和上近似分别为
下近似 R?A(X)=∪{[x]R??A|[x]R??AX}
上近似 ?A(X)=∪{[x]R??A|[x]R??A∩X≠?}
若R?A(X)=?A(X),称X是R?A-可定义集;若R?A(X)≠?A(X),称X是R?A-模糊粗糙集。
粗糙模糊集和模糊粗糙集对粗糙集和模糊集进行很好的互补性处理,已经在很多领域得到了实际应用[30~33],并取得了很好的效果。有很多学者对它们进行了进一步的比较研究[34~37],作了一些改进和扩展。文献[38]在覆盖粗糙集的基础上,结合模糊集的最近寻常集,引入了覆盖广义粗糙集模糊度的概念,给出了一种模糊度计算方法,并证明了该模糊度的一些重要性质;文献[39]提出了模糊不可分辨关系的概念,加强了粗糙集对模糊值属性处理能力。
3 粗糙集与神经网络
神经网络是在现代神经生物学研究成果的基础上发展起来的一种模仿人脑信息处理机制的网络系统。它具有在有监督或无监督的情况下从输入数据中进行学习的能力,被广泛地应用于数据挖掘[40~42]、模式识别[43~47]、信号处理[48,49]、预测[50, 51]等领域。
3.1 神经网络基本知识
神经网络[52]是一个由简单处理单元构成的规模宏大的并行分布式处理器,天然具有存储经验知识和使之可用的特性。神经元是神经网络最基本的信息处理单元,它具有接收和传递信息的功能。一个神经网络是由众多的神经元组成,每个神经元接收其他神经元和外界的输入信息。神经网络的结构通常都是以层的方式来组织的,一般包含一个输入层、任意多个隐藏层和一个输出层,每层都由众多的神经元组成。其基本原理是输入层神经元接收外界环境的信息输入,隐藏层神经元将隐藏层单元的信息输出至输出层,输出层将信息输出至外界。根据神经元信息的输出是否存在反馈,又将神经网络分为前馈神经网络和递归神经网络。
3.2 粗糙集与神经网络的联系
粗糙集对事物的识别和判断是基于论域上的不可辨关系,它不需要任何先验的信息。通过系统参数的重要度函数来获得描述事物各个属性的重要度,依此不仅可以进行属性的约简,而且也可以用于把握事物的主要特征,提高识别能力。粗糙集可以实现对信息系统的知识约简,去除冗余的信息,减少输入信息的空间文度,提高处理效率。不过粗糙集的抗干扰能力较差,对于噪声较为敏感,在噪声较大的环境中就表现得不尽如人意。
神经网络的特点就是通过训练和学习产生一个非线性的映射,模拟人的思文方式,具有很好的自适应性,可以实现有监督和无监督的学习,并能够对信息进行并行处理;同时,它具有很好的抑制噪声的能力。但是神经网络也有很明显的缺陷,它无法对输入的信息进行有用性或冗余性的判断,因此不能对输入的信息进行简化,这使得它在处理空间文数较大的信息时会很困难和低效。
粗糙集与神经网络各自的长处和短处让人们发现它们具有很好的互补性;另外,从对人类思文模拟的角度看,粗糙集方法模拟人类的抽象逻辑思文,而神经网络方法模拟人类的形象直觉思文。因此,将两者结合起来,用粗糙集的特点去弥补神经网络在处理髙文度数据上的不足,而用神经网络的抗干扰强的特性去弥补粗糙集对噪声的敏感性,将模拟人的抽象思文与形象直觉思文相结合,就会得到更好的效果。目前,这方面的研究已成为一个重要的研究方向。
3.3 粗糙集与神经网络的结合
粗糙集与神经网络最常见的结合方式主要有两种:a)将粗糙集作为神经网络的前端处理器[53],通过利用粗糙集先对原始信息进行属性及属性值的约简,去除冗余信息,降低信息空间的文度,为神经网络提供一个较为简化的训练集,然后再构建和训练神经网络。这样的结合方式不仅缩短了神经网络的学习和训练的时间,提高了系统反应速度,而且也可以充分发挥神经网络在抗噪性和容错性的优势,达到提高神经网络整体性能的目的。b)通过在神经网络中引入一种粗糙神经元来进行,将粗糙神经元与普通神经元混合起来使用构成粗糙神经网络。
粗糙神经元是Lingras[54]设计的一种由一对重叠的普通神经元——上神经元和下神经元r组成,如图1所示。粗糙神经元中上神经元和下神经元r整体看成是一个神经元r,神经元之间的连线表示信息的相互交换。图2~4分别表示粗糙神经r与s之间的全连接、抑制连接和激励连接三种常见连接方式。粗糙神经元的输出是具有上近似和下近似的一对数值,而普通神经元只有一个输出值。下近似或上近似的神经元输入根据以下公式计算权值:
input?i=?nj=1wji×output?j
其中:wji为神经元j到i神经元间的连接权值,n表示i与j间存在的连接个数。
若f(u)为神经元激励函数,则粗糙神经元的上下神经元的输出值分别为
output?=max(f(input?), f(inputr))
output?r=min(f(input?), f(inputr))
计算普通神经元i的单个输出值的公式:
output?i=f(input?i)
函数f(input)为sigmoid型函数,定义如下:
f(u)=1/(1+e??-gain×u)
其中:增益系数gain是由系统的设计者确定的斜率。f(u)采用sigmoid型转移函数是因这种转移函数在0~1具有连续的取值。
有关粗糙集与神经网络的结合研究,还有其他学者研究提出的一些新的结合方式,如强耦合集成[55]方式,为解决神经网络设计中的网络的隐层数、隐层节点数和初始权值的确定及网络语义提供了一种便于实现的新思路。随着软计算理论中的各种理论和技术的不断发展和创新,将神经网络与诸如进化算法、概念格、证据理论及混沌学等加强结合研究,相信会取得更加让人振奋的成就。
4 粗糙集与遗传算法
遗传算法[56]是一种自然进化系统的计算机模型,也是一种通用的求解优化问题的适应性搜索方法。它的本质特征在于群体搜索策略和简单的遗传算子,是目前进化算法中最为重要的一种算法,广泛地应用于人工智能、数据挖掘、自动控制及商业等领域。
4.1 遗传算法基本原理
遗传算法通过模拟自然选择和遗传机制,以迭代的方式对其研究的对象群体进行适应性评价、选择、重组,直到目标群体满足预定的要求或者达到最大迭代次数,从而得到其希望的最优解。遗传算法的关键问题是对问题空间中个体的编码方式的选择、适应函数的确定,以及遗传策略中选择、交叉、变异三个遗传算子和选择概率p?s、交叉概率p?c、变异概率p?m等遗传参数的确定。下面是一个标准遗传算法的算法描述[56]:
迭代开始(iteration):t=0
初始化(initialize):P(0)={a?1(0),a?2(0),…,a?n(0)}
适应性评价(evaluate):P(0)={f(a?1(0)),…, f(a?n(0))}
while(循环)T(P(t))≠true do
选择(select):P′(t)=s(P(t),p?s)
交叉(crossover):P″(t)=c(P′(t),p?c)
变异(mutate):P?(t)=m(P″(t),p?m)
新一代群体:P(t+1)=P?(t),t=t+1
适应性评价(evaluate):
P(t+1)={f(a?1(t+1)),…, f(a?n(t+1))}
结束(end do)
4.2 粗糙集与遗传算法的结合
粗糙集与遗传算法的结合主要应用在属性的约简[57~59]、数据挖掘[60]等方面。粗糙集中对于属性的约简通常采用启发式算法,如基于Pawlak属性重要度的属性约简算法、基于差别矩阵的属性约简算法等。这种方法在一定的问题规模范围内会较为有效,但随着问题的规模增大,其最小约简的求解难度也会大幅增加。遗传约简算法是求取信息系统最小约简或者相对最小约简的一种算法。所谓最小约简或者相对最小约简,就是属性集的所有约简或者相对约简中,包含属性个数最少的属性集。由于遗传算法是一种基于全局优化的搜索方法,并具有并行性和很好的鲁棒性,能够防止搜索陷入局部最优解的困境,更利于处理大规模问题的约简。
文献[57]根据可辨别关系的下三角矩阵,利用遗传算法提出一种基于遗传算法的粗糙集知识约简算法,这种算法不仅可以得到正确的约简,而且也能解决粗糙集中启发式算法无法求解的部分问题;文献[61]将信息论角度定义的属性重要性度量作为启发式信息引入遗传算法,并构造一个新的算子modifypop(t+1)来对种群进行修复,既保证了算法的整体优化性,也提高了算法的收敛速度。在数据挖掘方面,文献[60]将粗糙集与遗传算法相结合,提出一种从大型数据表中获取决策规则的方法。该方法利用粗糙集中属性的重要度和核的思想得到属性的约简,然后借助遗传算法来求得最优解。
此外,对连续属性的离散化处理是粗糙集中的一个重要问题。属性离散化处理的关键在于选取合适的断点对条件属性构成的空间进行划分以减少搜索空间。文献[62]针对该问题利用遗传算法将最小断点集作为优化目标,并构造一个新的算子来保证所选断点能保持原决策系统的不可分辩关系。
5 粗糙集与概念格
概念格理论也被称做形式概念分析理论,是由德国数学家While提出的一种基于概念和概念层次的数学化表达[63],对于数据分析和规则提取非常有效。目前广泛应用于机器学习[64]、软件工程[65]等领域。
5.1 概念格理论的基本知识
定义9[66] 形式背景。称(U,A,I)为一个形式背景,其中U={x?1,x?2,…,x?n}为对象集,每个x?i(i≤n)称为一个对象;A={a?1,a?2,…,a?n}为属性集,每个a?j(j≤m)称为一个属性;I为U与A之间的二元关系,IU×A。若(x,a)∈I ,则说x具有属性a,记为xIa。
在形式背景(U,A,I)下,若对象子集XU,属性子集BA,分别定义运算算子X?*和B?*为
X?*={a|a∈A,?x∈X,xIa}
B?*={x|x∈U,?a∈B,xIa}
其中:X?*表示X中所有对象共同具有的属性的集合,B?*表示共同具有B中所有属性的对象集合。
定义10 形式概念。设(U,A,I)为形式背景,如果一个二元组(X,B)满足X?*=B且B?*=X,则称(X,B)是一个形式概念,简称概念。其中,X称为概念的外延,B称为概念的内涵。
定义11[67] 子概念、父概念。如果(X?1,B?1)≤(X?2,B?2),且两者之间不存在与它们不同的概念(Y,C),满足(X?1,?B?1)≤(Y,C)≤(X?2,B?2),则称(X?1,B?1)是(X?2,B?2)的子概念,(X?2,B?2)是(X?1,B?1)的父概念。
5.2 粗糙集与概念格的联系
粗糙集与概念格之间都是基于二元关系的数据表来展开研究的。粗糙集是根据其论域上的不可辨关系实现对论域的划分,产生若干个等价类。概念格是基于形式概念,结合序理论和完备格理论进行概念分层讨论。概念格的每个概念就是具有最大共同属性的对象的集合,这一点与粗糙集的等价类非常相似。在形式背景中,外延即是由内涵所确定的等价类。因此,粗糙集的一些性质包括等价类,上、下近似等都可以通过概念来描述;同时,利用概念格的特殊结构可以得到函数依赖,从而可以用概念格来直观地进行条件属性的约简。
粗糙集与概念格的相似性让两个理论之间有了密切的联系,很多学者将它们结合起来研究。魏玲等人[67]分析研究了形式概念与等价类、概念格与划分之间的相互关系,得出粗糙集中的划分和概念格理论中的概念格可以进行相互转换的结论;文献[68]将粗糙集理论中属性约简和辨识矩阵的概念引入到形式概念分析中,实现了形式背景中冗余知识的约简;Yao[69,70]基于对象定向概念的概念格讨论了概念格和粗糙集理论之间的对应关系,将粗糙集理论中上下近似的思想引入到形式概念分析中,分别讨论了形式概念分析中的几种近似算子。文献[71]将包含度和偏序集的概念引入到形式概念分析中,对形式概念分析中的一些基本概念分别用包含度和偏序集加以表示。文献[72]利用形式概念分析中的名义梯级背景(nominal scale)和平面梯级(plain scaling)的概念,论证了粗糙集理论中的上下近似、属性依赖等核心概念都可以在相应的衍生背景中进行表示,并指出利用梯级的概念可以对粗糙集理论进行扩展,为两者的融合提供了一个理论平台。文献[73]的研究结合粗糙集与概念格理论,给出了在形式背景下概念集合上的元素之间的二元运算,使一般意义下的概念格成为带有算子的概念格。
6 粗糙集与证据理论
证据理论[74]也常称做D-S理论,是一种利用一组函数来处理不确定性问题的理论。证据理论中的证据指的是研究对象的属性或者专家经验等。
6.1 证据理论基础
设Θ表示对一个问题的所有可能答案的集合,其中的每一个答案θ都是Θ的一个子集,子集之间是无交集的,称Θ为辨识框架。
定义12[75] 基本可信度分配函数。设Θ是一个辨识框架,如果集函数m:2?Θ→[0,1]满足m(Φ)=0,并且?A?Θm(A)=1,则称m为Θ上的基本可信度分配函数;?A?Θ,m(A)称为A的基本可信度。
在定义12的基础上,本文定义Θ的幂集2?Θ上的三个测度?函数:
a)信任函数Bel,Bel(X)=?AXm(A),?XΘ;
b)似然函数pl,pl(X)=?A∩X≠?m(A);
c)公共函数Q,Q(X)=?X?Am(X)。
其中:信任函数Bel表达了对每个命题的信度;似然函数pl(X)表示对命题X不怀疑的程度;公共函数Q(X)反映了包含X的集合的所有基本可信度之和。
6.2 粗糙集与证据理论的联系
证据理论根据可信度分配函数来定义信任函数、似然函数,通过这对函数在给定证据下对假设进行估计和评价。在证据理论中,证据主要是已知的事物的属性或者专家经验等一些先验知识,这使得证据推理具有较强主观性,限制了其使用范围。证据理论的这些特征与粗糙集存在明显的互补性和相似性。粗糙集对于问题的解决是基于一对客观的近似算子,具有很强的客观性;而粗糙集中的下、上近似与证据理论中的信任函数、似然函数在形式上又有着一定的相似性。将两者的优势进行互补以及相似性进行结合的研究,已成为这个领域的一个重要方向。
文献[76,77]通过在一个随机近似空间上进行粗糙集与证据理论的相似性研究,得出结论:证据理论中的信任函数与似然函数可以用粗糙集中下近似与上近似的概率来描述:
Bel(X)=|R(X)|/|U|,pl(X)=|(X)|/|U|
文献[78]也对粗糙集与证据理论之间的关系进行了进一步的研究,认为不同的辨识框架与有着不同下、上近似的各种粗糙近似空间之间有着密切联系,并可以用这种联系来解释辨识框架上的信任函数与似然函数,以加深对这两个理论的?认识。
7 结束语
科技的发展让人们对于生活、学习、科学研究等各种现代化工具的期望趋于自动化、便捷化、智能化、高速化。而客观的现实是人们获得和需要处理的数据不仅数量庞大复杂,而且绝大部分都是不确定的、不完整的或者是不全真的。如何有效地、快速地从中提取出人们需要的信息就成了亟待解决的问题。软计算理论的出现帮助人们在这一方面取得了巨大的成就,粗糙集的迅速发展也为软计算理论的应用与研究提供了强大支持和扩展。随着对软计算理论不断深入的研究和发展,人们发现单个的软计算理论在理论上和应用上都存在着这样或那样的不足,而这些理论之间很强的互补特性则可以弥补这些不足。因此,将不同的软计算理论结合起来研究已成为当前学术界的共识。
本文主要描述了近年来发展较快并具有非常新颖特点的粗糙集与软计算理论中的一些其他理论结合的研究情况,从中可以看到这种结合在人工智能、数据挖掘、知识发现、属性约简、自动控制以及医学等方面所取得的显著成就。此外,词计算[79]逐渐成为了人工智能领域的研究热点,词计算是以词或文字术语为对象,而不是数值为对象的计算方法,而词或文字本身就具有不确定意义的特点,这恰好与粗糙集对问题的描述特点很相似,因此,将粗糙集与词计算结合研究也将是未来粗糙集研究发展的一个内容。这让笔者相信,随着对软计算理论结合研究的不断深入,将会看到更为令人欣喜的成功。
目前软计算理论相互结合的研究一般只局限于其中某两个理论之间来展开,而笔者在实际研究中也发现,即使这样的两两结合也存在很多有待完善和改进的地方,这就需要在以后的研究中能将更多的软计算理论结合在一起来研究,取长补短、优势互补,提高这一领域的研究水平。
参考文献:
[1]ZADEH L A.Fuzzy logic,neural networks and soft computing[J].Communications of the ACM,1994,37(3):77-84.
[2]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
[3]ALVATORE G,BENTTOM,ROMAN S.Rough set theory for multi criteria decision analysis[J].European Journal of Operational Research,2001,129(1):1-47.
[4]安利平,陈增强,袁著祉.基于粗集理论的多属性决策分析[J].控制与决策,2005,20(3):294-298.
[5]李永敏,朱善君,陈湘晖,等.基于粗糙集理论的数据挖掘模型[J].清华大学学报:自然科学版,1999(1):111-114.
[6]刘清,黄兆华,刘少辉,等.带Rough算子的决策规则及数据挖掘中的软计算[J].计算机研究与发展,1999,36(7):33-37.
[7]张文宇,薛惠锋,张洪才,等.粗糙集在数据挖掘分类规则中的应用研究[J].西北工业大学学报, 2002,20(3):430-434.
[8]陶多秀,吕跃进,邓春燕.基于粗糙集的多文关联规则挖掘方法[J].计算机应用,2009,29(5):1405-1408.
[9] 苗夺谦,李道国.粗糙集理论、算法与应用[M].北京:清华大学出版社,2008.
[10]胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-649.
[11]胡清华,赵辉,于达仁. 基于邻域粗糙集的符号与数值属性快速约简算法[J].模式识别与人工智能,2008,21(6):732-738.
[12]商琳,万琼,姚望舒,等.一种连续值属性约简方法ReCA[J].计算机研究与发展, 2005,42(7):1217-1224.
[13]YAO Yi-yu.Three-way decisions with probabilistic rough sets[J].Information Sciences,2010,180(3):341-353.
[14]CHEN Yu-min,MIAO Duo-qian,WANG Rui-zhi.A rough set approach to feature selection based on ant colony optimization[J].Pattern Recognition Letters,2010,31(3):226-233.
[15]LIANG Ji-ye,WANG Jun-hong,QIAN Yu-hua.A new measure of uncertainty based on knowledge granulation for rough sets[J].Information Sciences,2009,179(4):458-470.
[16]QIAN Yu-hua,LIANG Ji-ye.Combination entropy and combination granulation in rough set theory[J].International Journal of Uncertainty, Fuzziness and Knowlege-based Systems,2008,16(2):179-193.
[17]BASZCZYNSKI J,GRECO S,SOWINSKI R,et al.Monotonic variable consistency rough set approaches[J].International Journal of Approximate Reasoning,2009,50(7):979-999.
[18]ZHU W,WANG Fei-yue.A new type of covering rough set[C]//Proc of the 3rd International IEEE Conference on Intelligent Systems.2006:444-449.
[19]ZHU W,WANG Fei-yue.Reduction and axiomization of covering ?generalized rough sets[J].Information Sciences,2003,152(1):?217-230.
[20]ZHU W.Topological approaches to covering rough sets[J].Information Sciences,2007,177(6):1499-1508.
[21]LIU Gui-long,SAI Ying.A comparison of two types of rough sets induced by coverings[J].International Journal of Approximate Reasoning,2009,50(3):521-528.
[22]SLEZAK D,ZIARKO W.Variable precision Bayesian rough set model[C]//Proc of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Comuting.Berlin:Springer-Verlag,2003:312-315.
[23]祝峰,何华灿.粗集的公理化[J].计算机学报,2000,23(3):330-333.
[24]王珏,刘三阳,王建新.粗糙集理论的扩展模型研究[J].同济大学学报:自然科学版,2006,34(9):1251-1255.
[25]秦克云,高岩.决策表的正域约简及核的计算[J].西南交通大学学报,2007,42(1):125-128.
[26]张文修,米据生,吴伟志.不协调目标信息系统的知识约简[J].计算机学报,2003,26(1):12-18.
[27]张海云,梁吉业,钱宇华.基于划分的信息系统属性约简[J].计算机应用,2006,26(12):2961-2963.
[28]王国胤,张清华.不同知识粒度下粗糙集的不确定性研究[J]. 计算机学报, 2008,31(9):1588-1598.
[29]DUBOIS D,PRADE H.Rough fuzzy set and fuzzy rough sets[J].International Journal of General Systems,1990(17):191-209.
[30]邱卫根.基于随机模糊集的不完全信息系统粗集模型[J].模式识别与人工智能,2009,22(1):53-59.
[31]HONG T,TSENG L,CHIEN B.Mining from incomplete quantitative data by fuzzy rough sets[J].Expert Systems with Applications,2010,37(3):2644-2653.
[32]LI Jiang-ping,PAN Bao-chang,WEI Yu-ke.Tongue image segmentation based on fuzzy rough sets[C]//Proc ofInternational Conference on Environmental Science and Information Application Technology.Washington DC:IEEE Computer Society,2009:367-369.
[33]PETROSINO A,FERONE A.Rough fuzzy set-based image compression[J].Fuzzy Sets and Systems,2009,160(10):1485-1506.
[34]YAO Yi-yu.Combination of rough and fuzzy sets based on α-level sets[M]//Rough Sets and Data Mining:Analysis for Imprecise Data.Boston:Kluwer Academic Publishers, 1997:301-321.
[35]YAO Yi-yu.A comparative study of fuzzy sets and rough sets[J].Information Science,1998,109(1-4):227-242.
[36]HU Qing-hua,YU Da-ren,WU Cong-xin.Fuzzy preference relation rough sets[C]//Proc ofIEEE International Conference on Granular Computing.2008:300-305.
[37]WU Wei-zhi.Fuzzy rough sets determined by fuzzy implication operators[C]//Proc ofIEEE International Conference on Granular Computing.Washington DC:IEEE Computer Society,2009:596-601.
[38]徐伟华,张文修.覆盖广义粗糙集的模糊性[J].模糊系统与数学,2006,20(6):115-121.
[39]王熙照,赵素云,王静红.基于Rough集理论的模糊值属性信息表简化方法[J].计算机研究与发展,2004,41(11):1974-1981.
[40]宋擒豹,沈钧毅.神经网络数据挖掘方法中的数据准备问题[J].计算机工程与应用,2000,36(12):102-104.
[41]徐建军.医学影像数据挖掘中的人工神经网络方法研究[J].实用放射学杂志, 2006,22(11):1416-1418.
[42]周序生,王志明.粗糙集和神经网络方法在数据挖掘中的应用[J].计算机工程与应用,2009,45(7):146-149.
[43]刘政凯,章杨清.利用分文向量改进神经网络在遥感模式识别中的分类精度[J]. 遥感学报, 1994,9(1):68-72.
[44]周洪宝,闵珍,宫宁生. 基于粗糙集的神经网络在模式识别中的应用[J].计算机工程与设计,2007,28(22):5464-5467.
[45]王守觉,李卫军,赵顾良,等.模式识别专用神经网络计算机系统及应用方法:北京,CN1700250[P].2005:11-23.
[46]周志华,皇甫杰,张宏江,等.基于神经网络集成的多视角人脸识别[J].计算机研究与发展,2001,38(10):1204-1210.
[47]周志华,李宁,杨育彬,等.基于神经网络集成的肺癌早期诊断[J].计算机研究与发展,2002,39(10):1248-1253.
[48]黄春琳,邱玲,沈振康.数字调制信号的神经网络识别方法[J].国防科技大学学报,1999,21(2):61-64.
[49]游荣义,陈忠.基于小波变换的盲信号分离的神经网络方法[J].仪器仪表学报,2005,26(4):415-418.
[50]XIAO Zhi,YE Shi-jie,ZHONG Bo,et al.BP neural network with rough set for short term load forecasting[J].Expert Systems with Applications,2009,36(1):273-279.
[51]LIU Hui,KONG Wei,QIU Tian-shuang,et al.A neural network based on rough set(RSNN) for prediction of solitary pulmonary nodules[C]//Proc ofInternational Joint Conference on Bioinformatics, Systems Biology and Intelligent Computing.Washington DC:IEEE Computer Society,2009:135-138.
[52]SIMON H.神经网络原理[M].叶世伟,史忠植,译.北京:机械工业出版社,2004.
[53]JELONEK J,KRAWIEC K,SLOWINSKI R.Rough set reduction of attributes and their domains for neural networks[J].Computational Intelligence,1995,11(2):339-347.
[54]LINGRAS P J.Rough neural networks[C]//Proc of the 6th International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems.1996:1445-1450.
[55]张东波,王耀南,易灵芝.粗集神经网络及其在智能信息处理领域的应用[J].控制与决策, 2005,20(2):121-126.
[56]李敏强,寇纪淞,林丹,等.遗传算法的基本理论与应用[M].北京:科学出版社,2002.
[57]王文辉,周东华.基于遗传算法的一种粗糙集知识约简算法[J].系统仿真学报,2001,13(Z1):91-93.
[58]赵敏,罗可,廖喜讯.基于免疫遗传算法的粗糙集属性约简算法[J].计算机工程与应用,2007,43(23):171-173.
[59]王萍,王学峰,吴谷丰.基于遗传算法的粗糙集属性约简算法[J].计算机应用与软件,2008,27(5):42-44.
[60]胡彧,张亦军,杨冬梅.粗糙集结合遗传算法在数据挖掘中的应用[J].计算机应用,2006,26(1):98-99.
[61]代建华,李元香.粗集中属性约简的一种启发式遗传算法[J].西安交通大学学报,2002,36(12):1286-1290.
[62]代建华,李元香,刘群.粗糙集理论中基于遗传算法的离散化方法[J].计算机工程与应用, 2003,39(8):13-14.
[63]苗夺谦,王国胤,刘清,等.粒计算:过去、现在与展望[M].北京:科学出版社,2007.
[64]ZUPANA B,BOHANEC M,DEMAR J,et al.Learning by discovering concept hierarchies[J].Artificial Intelligence,1999,109(1):211-242.
[65]DEKEL U,GIL Y.Revealing class structure with concept lattices[C]//Proc of the 10th Working Conference on Reverse Engineering.Washington DC:IEEE Computer Society,2003:353.
[66]GANTER B,WHILE R.Formal concept analysis:mathematical foundations[M].Berlin:Springer,1999.
[67]魏玲,祁建军,张文修.概念格与粗糙集的关系研究[J].计算机科学,2006(3):18-21.
[68]ZHANG Wen-xiu,WEI Ling,QI Jian-jun.Attribute reduction in concept lattice based on discernibility matrix[C]//Proc of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing.Berlin:Springer,2005:157-165.
[69]YAO Yi-yu.Concept lattices in rough set theory[C]//Proc of Annual Meeting of the North American Fuzzy Information Processing Society.2004:796-801. http://www.751com.cn
[70]YAO Yi-yu.A comparative study of formal concept analysis and rough set theory in data analysis[C]//Proc of the 4th International Confe-?rence on Rough Sets and Current Trends in Computing.Berlin:Sprin-?ger,2004:59-68.
[71]曲开社,翟岩慧.偏序集、包含度与形式概念分析[J].计算机学报,2006,29(2):219-226.
[72]曲开社,翟岩慧,梁吉业,等. 形式概念分析对粗糙集理论的表示及扩展[J].软件学报,2007,18(9):2174-2182.
[73]梁吉业.基于粗糙集与概念格的智能数据分析方法研究[D]. 北京: 中国科学院计算技术研究所,2004.
[74]SHAFER G.A mathematical theory of evidence[M].Princeton:Princeton University Press,1976.
[75]单渊达,倪明.证据理论及其应用[J].电力系统自动化,1996(3):76-80.
[76]SKOWRON A.The relationship between the rough set theory and evidence theory[J].Bulletin of the Polish Academy of Sciences Mathematics,1989,37(1):87-90.
[77]FAGIN R,HALPERN J Y.Uncertainty,belief,and probability[J].Computational Intelligence,1991(7):160-173.
[78]WU Wei-zhi,LEUNG Y,ZHANG Wen-xiu.Connections between rough set theory and Dempster-Shafer theory of evidence[J].International Journal of General Systems,2002,31(4):405-430.
[79]WANG Fei-yue.On the abstraction of conventional dynamic systems:from numerical analysis to linguistic analysis[J].Information ?Sciences,2005,171(1-3):233-259.