1、 粗 糙 集 理 论 -研究现状与发展前景主要内容 粗糙集(Rough Sets)是波兰数学家Z. Pawlak于1982年提出的1(为开发自动规则生成系统及研究软计算问题而引入)。由于最初关于粗糙集理论的研究大部分是用波兰语发表的,因此当时没有引起国际计算机学界和数学界的重视。研究地域也局限在东欧一些国家,直到80年代末才引起各国学者的注意。九十年代初,人们才逐渐认识到它的意义。 1992年在波兰Kiekrz召开了第一届国际RS研讨会。这次会议着重讨论了集合近似定义的基本思想及应用,其中RS环境下的机器学习基础研究是这次会议的四个专题之一。 1993年在加拿大Banff召开第二届国际RS理论
2、与知识发现研讨会。这次会议积极推动了国际上对RS理论与应用的研究。由于当时正值KDD(数据库知识发现)成为研究的热门话题,一些著名KDD学习者参加这次会议,并且介绍了许多应用扩展RS理论的知识发现方法与系统。 1996年在日本东京召开了第5届国际RS研讨会,推动了亚洲地区对RS理论与应用的研究。 1995年,ACM Communication将其列为新浮现的计算机科学的研究课题。 1998年,国际信息科学杂志(Information Sciences)为粗糙集理论的研究出了一期专辑2,3。第一届中国RS理论与软计算学术研讨会,于2001年5月在重庆举行。第二届中国RS理论与软计算学术研讨会,于
3、2002年10月在苏州大学举行。第三届中国RS理论与软计算学术研讨会,于2003年8月在重庆举行。第四届中国RS理论与软计算学术研讨会,将于2004年在舟山举行。 粗糙集的理论及应用的文章 主要发表在以下杂志国内: 1模式识别与人工智能 2软件学报 3科学通报 4计算机科学 5计算机学报 6模糊系统与数学 7计算机应用与软件 8计算机研究与发展 9计算技术与自动化 粗糙集的理论及应用的文章 主要发表在以下杂志(续)国际: 1Information Sciences 2Fuzzy sets and systems 3International Journal of Computer and In
4、formation Sciences 4Communication of the ACM 5Computational Intelligence 6Journal of computer and system sciences 7 AI Magazine8 AI Communications9 European Journal of Operational Research10International Journal of Approximate Reasoning11Theoretical computer sciences12Decision support Systems13Inter
5、national Journal of Man-Machine studies 14Fundamenta Informaticae15Intelligent Automation Sciences 粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法。由于它在机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别等方面的广泛应用,现已成为一个热门的研究领域2。 RS理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性,即以不完全信息或知识去处理一些不分明现象的能力。或依据观察,度量到的某些不确定的结果而进行分类数据的能力4。 RS理论认为知识即是
6、将对象进行分类的能力,假定我们起初对全域里的元素(对象)具有必要的信息、或知识,通过这些知识能够将其划分到不同的类别。若我们对两个元素具有相同的信息,则它们就是不可区分的(即根据已有的信息不能够将其划分开)。显然这是一种等价关系。不可区分关系是RS理论最基本概念。在此基础上引入了成员关系,上近似和下近似等概念来刻划不精确性与模糊性1,2,4,5。样本 粗糙集方法处理 具有优化指标的样本 评审样本学习样本 数据预处理(粗糙集方法、模糊集方法)模糊、粗糙推理神经网络遗传算法智能信息系统 设U是非空有限论域(全域、集合),R是U上的二元等价关系(具有相反、对称、传递性的关系),R称为不可分辨关系。
7、序对A=(U,R)称为近似空间。 ,若 ,则称对象x与y在近似空间A中是不可分辨的。 U/R是U上由R生成的等价类全体,它构成U的一个划分,U上的划分可以与U上的二元等价关系之间建立一一对应。 基本概念UUyx ,Ryx, U/R中的元素(集合)称为U的基本集或原子集,任意有限个基本集的并称为可定义集,空集也称为可定义集( 可定义集也称为精确集)。否则称为不可定义集。 若将U中的集合称为概念或表示知识,则A=(U,R)称为知识库,原子集(基本集)表示基本概念或知识模块。那么精确集可以在知识库中被精确地定义或描述,可表示已知的知识。 基本概念(续) 上近似,下近似 对于一个近似空间A=(U,R)
8、,X是U的任意一个子集。X不一定能用知识库中的知识来精确地描述;即X可能为不可定义集,这时就用X关于A的一对下近似、上近似来“近似”地描述。下面 表示x所在的R-等价类。 称为集合X关于R的下近似。 =称为集合X关于R的上近似。 XxxXRXaprRR XxUxxR, XxxXRXaprRR XxUxxR,Rx 例1 给定一玩具积木的集合 ,并假设这些积木有不同的颜色(红、黄、蓝),形状(方、圆、三角)和体积(大、小)。积木的集合U可按颜色、形状、体积分类。:颜色关系, :形状关系, :体积。则 1R2R3R821,xxxU865427311,/xxxxxxxxRU874362512,/xxx
9、xxxxxRU654318723,/xxxxxxxxRU 例1(续) 取 ,那么 742,xxxX 42,1xxXaprR 73142,1xxxxxXaprR73142,xxxxxXaprR2874362,2xxxxxxXaprRXaprR3UXaprR3XaprXaprXaprU XaprXaprXaprXaprXaprXaprapraprU,2XaprXapr称二元对 为Rough集(粗糙集)XaprXapr, 可认为Rough集的另一种 表示形式,这种定义方式可直接算出U上关于其 子集X的含糊元素数目。这种边界区意味着由于掌握的知识不完全而存在不能辨别的区域,即bnd(X)上的元素不可分
10、辨,所以U上子集X关于U上不分明关系R是Rough的,主要是 ,否则它是可分辨的。一个集合X的边界区域越大,则这个集合X的含糊元素也越多,这种思想可以用数值化的系数表示。 XaprXaprXBND Xbnd , card X表X的基数。称 为X的近似精度, (粗糙程度。于是也可用 来定义Rough集。当 ,称U上子集X关于U上不分明关系R是 Rough的;当 ,称X关于R是精确的; 可被用作Rough逻辑中的算子。 XaprcardXaprcardXR)(XR 10XR)(XR 1XR 1XR在Rough集上也有元素隶属于集合的问题(与Fuzzy 集一样)。设 , ,则 。称 为Rough隶属
11、函数,解释为一种条件概率,能从全域上的个体加以计算。Fuzzy集上的隶属函数则不然。用 来定义Rough集,则得到Rough集的第四种表示形式。UX RRRXxcardxXcardx 10 xXRX xRX若存在 ,有 ,称X关于R是Rough的,若对每个 ,有 ,则X关于R是精确的。相反地,Rough隶属函数可用来定义一个集合 的上、下近似集及边界集 UXx 1xRXUXx 1xRX 1,xUxXaprRX 0,xUxXaprRX 10 ,xUxXbnRXUX 无论哪一种Rough集的表示形式都离不开全域U上的不分明关系R以及由R定义的下和上近似集。因此对Rough集理论中的不分明关系以及下
12、和上近似集的研究尤其重要。定义观点的不同往往带来研究的侧重面的不同。 X关于A的近似质量: 近似质量 反映了知识X中肯定在知识库中的部分在现有知识中的百分比。X关于A的粗糙性测度:则 ,且X是可定义的 X是粗糙的 。粗糙性测度反映了知识的不完全程度。 UXaprUcardXaprcardXrA)(XrA 1XaprXaprXA 10XA 0XA 0XA X关于A的近似精度: 它反映了根据现有知识对X的了解程度2,5。 XaprXaprXA设 是由U的子集所构成的集类。则F关于近似空间A的下近似 F和上近似 F:F关于A的近似精度 nXXXF,21,21nXaprXaprXaprFaprapra
13、prnXaprXaprXaprFapr,21 niniAXiaprXiaprF11近似质量为当F也是U的划分时,F关于A的近似在判别一个决策表是否是协调的和规则提取中有重要作用。 UXiaprFrniA1v信息系统v属性的约简及核 v规则的协调与提取 信息系统粗糙集理论中的知识表达方式一般采用信息表或称为信息系统的形式。信息表表示输入数据,这些数据是从任意领域中收集的。信息系统可用四元有序组 表示,其中U是对象的全体,即论域;A是属性全体; , 是属性a的值域; 是一个信息函数, 反映了对象x在K中的完全信息 5,10。 如下信息表: ,VAUK aAaVV aVVAU:UxVAx,: axa
14、x,对象 属性头痛 肌肉痛 体温 决策 流感是 是 正常 否是 是 高 是是 是 很高 是否 是 正常 否否 否 高 否否 是 很高 是1e1e1e2e3e4e5e6e表1 信息表 信息系统(续)标记 被称为实例(个体,实体,对象), 记 。识别两种变量:属性(有时称之为条件属性), 决策(有时称之为决策属性)。例如:如果信息表描述一家医院,每个实例可能就是病人,属性是症状和检测,而决策是病症。如果信息表表示一个工业生产过程,则这些实例可代表在某些特定时刻及时采集的过程中的样品,属性是过程中的参数,而决策是由操作员(专家)采取的决定。654321,eeeeee,654321eeeeeeU 信息
15、系统(续) RS理论的一个重要概念是不分明关系,它通常与一属性集合联系在一起。如上表1中头痛、肌肉痛、体温均为属性。)头痛且肌肉痛决定不分明关系 ,则)集合 根据属性头痛和肌肉痛是可定 义的。)头痛和体温决定不分明关系 ,则 1R 5643211,/eeeeeeRU5321,eeee2R 信息系统(续) iv)头痛、体温、肌肉痛决定不分明关系 ,则 于是说明肌肉痛是多余的属性。对于信息系统,每个属性子集都定义了论域上的一个等价关系。即 ,对 6543212,/eeeeeeRU3R 6543213,/eeeeeeRUaRAa决定等价关系aBaBRRAB决定等价关系属性的约简及核 粗糙集理论给出了
16、对知识(或数据)的约简和求核的方法,从而提供了从信息系统中分析多余属性的能力2,5,9,10。 信息系统类似于关系数据库模型的表达方式。有时属性集A还可分为条件属性C和决策(结论)属性D,这时的信息系统也称为决策表,常记为 。 无决策的数据分析和有决策的数据分析是粗糙集理论在数据分析中的两个主要应用。 ,VDCU定义:设 是一个信息系统,由属性集 所导出的等价关系为 。)设 ,则称属性a是多余的 (如表1中的肌肉痛)。)若在系统中没有多余属性,则称A是独立的iii)子集 称为是A的约简。若 , 且B中没有多余属性。常记 为A的全体约简,)A的所有约简的交集称为A的核,记为core (A)。一般
17、来说:属性集的约简不唯一而核是唯一的。,VAUK AB BR aAARRAa , 若AB ABRR Ared例2(无决策情形的属性的约简、核 ) 设 ,其中 , , 信息函数 见下表2 ,VAUS 821,xxxU, , , V , , 43214321vvvvccccA属性集 2 , 1 , 3 , 2 , 14321vvvv其中例2(续) 表2 信息系统U 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 2 2 1 1 2 2 1 1 3 3 3 2 3 3 3 21x2x3x4x5x6x7x8x1c2c3c4c例2(续) 因此 876543211,/xxxxxxxxcU8
18、76542312,/xxxxxxxxcU874265313,/xxxxxxxxcU876543214,/xxxxxxxxcU87654231,/xxxxxxxxAU将对象及其信息压缩后得下面表3 例2(续) 表3 信息系统U/A , 1 1 1 1 , 1 2 2 1 , 2 2 1 1 , 3 3 3 21x2x3x4x5x6x7x8x1c2c3c4c且可验证属性 是多余,且令 。则有 中没有多余属性。 4c321321,/BBBAUBUBUBU且313322211, , , , ,ccBccBccB例2(续) 1c2c3c于是信息表2有三个属性的约简,即 ,从而可得信息系统的三个约简表如下
19、。321,BBB1c2c3c 1 1 2 2 2 1 2 3 1 1 1 2 2 2 3 3 1 1 1 2 2 1 3 3而且 。 表1的核:Core A=头痛,体温。CoreA规则的协调与提取 粗糙集理论除给出了对知识(或数据)的约简和求核的方法外,还提供了从决策表中抽取规则的能力,机器学习和从数据库中的机器发现就是基于这个能力。 在一个决策表 中,若 ,X关于由 导出的近似空间的下近似和上近似相等,即 ,称条件属性子集 关于决策属性 是协调的。也称决策表 是协调的,否则为不协调10。 ,VDCU1/DUX 1CXaprXaprCC11CC 1DD 1,11VDCU规则的协调与提取(续)
20、如果用包含度理论来解释,则决策表 是协调的,当且仅当 2,其中 ,11VDCU1/11CDD1111/11DUaprDUaprCDDCC规则的协调与提取(续) 从协调的决策表中可以抽出确定性规则,而从不协调的决策表中只能抽出不确定性的规则或可能性规则,有时也称为广义决策规则,这是因为在不协调的系统中存在着矛盾的事例。决策表中的决策规则一般可以表示为形式5:其中 称为规则的条件表示, 称为规则的决策部分。 决策规则即使是最优的也不一定唯一。wdc,;,cVwVCcd wd,规则的协调与提取(续) 在决策表中抽取规则的一般方法为3:(1)在决策表中将信息相同(即具有相同描述)的对 象及其信息删除只
21、留其中一个得到压缩后的信息 表,这一步称为删除多余事例;(2)删除多余的属性;(3)对每一个对象及其信息中将多余的属性值删除;(4)求出最小约简;(5)根据最小约简,求出逻辑规则。例3(决策情形) 设 ,其中 , 具体的决策表见下面表4 821,xxxU,VDCU,dD, , 214321dccccC决策属性集条件属性集例3(续) 表4 决策表U 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 2 2 1 1 2 2 1 1 3 3 3 2 3 3 3 21x2x3x4x5x6x7x8x1c2c3c4c 1 1 2 2 1 3 2 4 3 5 3 5 4 5 4 51d2d例3
22、(续) 因此 876543211,/xxxxxxxxcU876542312,/xxxxxxxxcU874265313,/xxxxxxxxcU876543214,/xxxxxxxxcU ,876542311xxxxxxxxdU,876543212xxxxxxxxdU例3(续) 从而 对于它的决策子表(, ,V, ), (, ,V, ),我们可得到它们的一个约简表如下(一般不唯一) 1dC 2dC CUdccUdccUdccUccUccUccU132131121323121例3(续) 1c2c3c1c 1 1 1 1 2 2 2 1 3 2 3 4 1 1 1 1 2 2 1 1 3 1 2 4
23、2 2 5 3 3 5表5表6 1d2d例3(续) 且 , ,故(, ,V, )是协调的。 1dC 2dC 1dUX XXaprXaprcc但 , , , 故(, ,V, )不协调的。 21dUxXXaprc,31xxXaprc例3(续) 由表5可得决策表(, ,V , )的四条最优决策规则。且这四条规则都是确定的。 1dC )2 ,()2 ,() 1 ,( :1311dccr)2 ,()2 ,() 1 ,( :1312dccr)3 ,()2 ,( :113dcr)4 ,()3 ,( :114dcr例3(续) 由表6(它是不协调的)也可得到决策表(, ,V, )的四条最优决策规则:2dC )3
24、 ,() 1 ,() 1 ,() 1 ,( :22211ddccr)4 ,()2 ,()2 ,() 1 ,( :22212ddccr)5 ,()2 ,( :213dcr)5 ,()3 ,( :214dcr21,rr43,rr其中 是不确定的,而只有 是确定的。与其他不确定性数学方法的关系 RS理论与其他处理不确定和不精确问题理论的最显著的区别是无需提供问题所需处理的数据集合之外的任何先验信息即它不需要任何预备的或额外的有关数据信息。 如统计学中的概率分布,Fuzzy理论中的隶属度函数等。 所以RS理论对问题的不确定性的描述或处理可以说是比较客观的。与其他不确定性数学方法的关系 由于这个理论未能
25、包含处理不精确或不确定原始数据的机制,因此,单纯地使用这个理论不一定能有效地描述数据不精确或不确定的实际问题,而证据理论与模糊集理论等具有处理不精确或不确定数据的方法,所以这个理论与概率统计,模糊数学,证据理论等其他处理不精确或不确定问题的理论有很强的互补性。与其他不确定性数学方法的关系 在粗糙集理论与其它处理模糊性或不确定性方法的理论研究中,主要集中在它与概率统计,模糊数学,DS证据理论和信息论的相应渗透与补充。下面从三方面进行比较。(1)与概率统计结合 (2)与模糊数学 (3)与DS证据理论 (DempsterShafer证据理论) 。与概率统计结合 在信息系统中,知识库的知识的类型一般有
26、两类: 一类库中所有对象的描述是完全已知的,Pawlak粗糙集模型和一般二元关系下的粗糙集模型的是属于这一种。 另一类库中的对象的描述只有部分是已知的,即知识库中的知识是不确定的,它只能通过训练样本所提供的信息来刻画概念。与概率统计结合(续) 为了使从训练样本获得的规则符合整个论域的对象,在抽取样本时应符合统计规律性,粗糙集理论不管这一类工作,因些概率统计作为研究自然界,人类社会及技术过程中大量随机现象的规律性的一门学科,它与粗糙集理论的结合就显得非常自然2。 与模糊数学 粗糙集理论用粗糙隶属函数来刻画知识的模糊性2,13,14。 () 这是对一般二元关系R下的近似空间A(,R)而言的。当R为
27、等价关系时, 。 () | )(| )(|)(xRxRXxSSXRSXxR)()()()(xRPxRXPxSSX与模糊数学(续) 在概率近似空间下,用它表示粗糙隶属函数。粗糙隶属一般不是Zadeh意义下的隶属函数。 粗糙集理论和模糊集理论在处理不确定性和不精确性问题方面都推广了经典集合论,虽有一定的相容性和相似性,然后它们的侧重面不同。 a)从知识的“粒度“的描述上来看,模糊集通过对象关于集合的隶属程度来近似描述;而粗糙集是通过一个集合关于某个可利用的知识库的一对上、下近似来描述的。 与模糊数学(续) b)从集合对象间的关系来看,模糊集强调的是集合边界的不分明性,而粗糙强调是是对象间的不可分辨
28、性。 c)从研究的对象来看,模糊集研究的是属于同一类的不同对象间的隶属关系,重在隶属程度,而粗糙集研究的是不同类中的对象组成的集合关系,重在分类。 与模糊数学(续) 虽然模糊集的隶属函数和粗糙集的粗糙隶属函数都反映了概念的模糊性,直观上有一定的相似性,但模糊集的隶属函数大多是专家凭经验给出的,因此往往带有很强烈的主观意志,而粗糙的粗糙隶属函数的计算是从被分析的数据中直接获得的,非常客观。也正因为如此,将粗糙集理论和模糊集理论进行某些“整合”后去描述知识的不确定性和不精确性比它们各自描述知识的不确定性和不精确性可望显示更强的功能。(目前所见的模糊粗糙集模型是其中的一些成功范例)。 与DS证据理论
29、 粗糙集理论是为开发规则的机器自动生成而提出的, 而DS理论主要用于证据推理;RS理论用概念的一对上,下近对其进行描述,而DS证据理论是用一对信任函数和似然函数在给定证据下对假设进行估计和评价。RS理论中的下近似和上近似的概率恰好分别是信任函数和似然函数。然而生成信任函数和似然函数的基本概率分配函数(mass函数)方法是不同的。前者来自于系统中数据本身,比较客观,而后者往往来自于专家的经验,带有很强的主观性。RS理论与DS证据理论有很强的互补性15。 与DS证据理论(续) 粗糙集理论中知识的不确定性主要由两个原因产生2:(1)直接来自论域上的二元关系及其产生的知识模块,即近似空间本身。如果二元
30、等价关系产生的每一个等价中只有一个元素,那么等价关系产生的划分不含有任何信息,划分越粗,每个知识模块越大,知识库中的知识越粗糙,相对于近似空间的概念和知识就越不确定。这时处理知识的不确定性的方法往往用香农信息熵来刻画,知识的粗糙性与信息熵的关系比较密切,知识的粗糙性实质上是其所含信息多少的更深层次刻画。单从这个角度来看,RS理论与信息论的关系就比较密切。 与DS证据理论(续) 粗糙集理论中知识的不确定性主要由两个原因产生2:(2)来自于给定论域里粗糙近似的边界。当边界为空集时知识就是完全确定的,边界越大知识就越粗糙或越模糊。至今,RS理论刻画概念X的不确定性用正则条件熵和粗糙性测度 来实现的。
31、但这两个度量并没有完全提供哪些完全属于X的下近似的区域里面与不可分辨关系的知识粒度有关的不确定性,于是有人引进了粗糙熵Er(X)的概念来刻画概念X的不确定性,所以,寻求一个合适的度量来刻画知识的不确定性也是RS理论研究的一个重要方向2,16。)(XPA粗集理论的应用及发展前景 RS理论已经被证实在实践中是非常有用的。从大量的现实生活中应用的记录来看已经非常明显,这一理论对AI(人工智能)和认知科学尤为重要,在专家系统,决系表等方面都有有非常成功的应用实例。 利用Rough集理论处理的主要问题包括:数据简化(即删除多余的数据),数据相关性的发现,数据意义的评估,由数据产生决策(控制)算法,数据的
32、近似分类等。 下面介绍两的应用和研究前景:(1)美国Kansas大学开发了基于RS方法学习的例子,并开发了基于Rough集方法的学习系统LERS(Learning from Examples based on RS)。这个系统的知识获取项对于用不完全信息工作的专家系统,帮助其建立知识库是一个十分恰当的规则归纳法的应用实例,它在NASAS Johnson空间中心应用了多年,充分显示了它在开发专家系统进行全球气候变化的研究中起的作用,它是作为一种开发专家系统的工具被引用的。 基于RS的典型系统 LERS可以从信息表形式中给定的实例导出一套规则集,并且可以利用这一套规则分类新的实例,LERS还被用于
33、两项医学方面,其一用来比较手术后的病人取暖设备的效果,其二用来评估孕妇超强度劳动的危险。还有一种很重要的LERS用途是全球气候变化的研究,描述对全球气温有影响的规则由一些属性所表征的数据引出。如太阳的能量释放,火山活动、美国南部的指针摇摆器、二氧化碳流向和二氧化碳的余量。这方面的专家依据获得的新数据把握地球气候变化的奥妙。 基于RS的典型系统(续) Rough Rough集理论之所以提供了集理论之所以提供了AIAI的有效方法,的有效方法,是因为实现它的程序可以很容易在平行机上运行。是因为实现它的程序可以很容易在平行机上运行。且基于且基于RoughRough集理论的集理论的RoughRough逻
34、辑将使单调逻辑非单逻辑将使单调逻辑非单调化,从而在调化,从而在AIAI的近似或不精确推理中将发挥不可的近似或不精确推理中将发挥不可估量作用。估量作用。 基于RS的典型系统(续) (2 2)RoughRough集方法用于决策分析已体现在波集方法用于决策分析已体现在波兰兰PoznanPoznan科技大学开发的计算机系统中,称之为科技大学开发的计算机系统中,称之为Rough DASRough DAS和和Rough ClassRough Class,它们对任务分别执行解它们对任务分别执行解释和描述。这两个系统已经在许多实际领域都有应释和描述。这两个系统已经在许多实际领域都有应用。(用。( Rough
35、DASRough DAS执行信息系统数据分析任务,执行信息系统数据分析任务,Rough ClassRough Class支持新对象的分类,这两个软件都是支持新对象的分类,这两个软件都是基于基于DOSDOS操作系统的)操作系统的)44。 基于RS的典型系统(续) 可分为两大类:有决策的分析,无决策的分析。有决策的分析主要包括:监督学习与决策分析。RS理论在监督学习中的应用可分为两个方面:其一:对学习的训练集作预处理,这是考试到从实际测量中所获得的训练集,常包含有多余的属性,应用RS的属性约简可有效地去除冗余的属性。例如:对豌豆疾病的数据进行RS处理,使得原有属性数从35个约简到9个;对美国198
36、4年众议案的投票数据的分析,则使属性从原有16个减少为9个。另外,每个属性的值域也会有冗余,同样应用RS方法中的约简技术可以删除某些属性的多余值。 其二应用RS方法获取规则:利用RS中提供的值约简方法由实例集直接获取规则,但是,由于从决策表中直接获取所有的值约简已被证明是一个NP完全问题,因此,利用领域独立的启发式算法求取最小约简是一个自然的方法。例如,通过值约简可将美国1984年众议案的投票数据由435个例子约简为44条规则。 RS理论应用于有决策分析还包括:(1)应用于决策不完全时的学习(利用RS理论中的上,下近似的概念表示不完全的决策,以及对学习效果所产生的影响)。(2)进行增量式学习(
37、从RS理论中的差别矩阵出发,利用与或逻辑求取规则描述,对新的例子只需在差别矩阵上添加相应的行列,即可获取增量后的规则)。在决策分析的应用中,则是利用RS理论的属性约简,值约简及核等概念,对被决策的数据进行约简和寻找对于决策最有用的信息。 无决策的数据分析主要是:数据压缩、化简、聚类、模式发现与机器发现等。这类问题主要是利用属性的约简去除不必要的属性,利用值约简压缩数据及进行数据的聚类分析,由于无决策的数据的约简问题也是NP完全问题,因而仍要利用启发式知识求取最小约简。属于这类应用的典型AI分支是机器发现,特别是从大型数据库进行知识发现,RS被认为是一个非常有效的方法。 近几年来,RS理论已在很
38、多实际领域得到了成功应用。如美国的NASA Johnson空间中心利用LERS学习系统来发展空间自由行走的医学专家系统,希腊的工业发展银行ETEUA应用RS求取贷款信用,美国的环境保护署利用LERS来增进资源之间的协调等。目前,RS理论已在西方的研究机构和大学与大的公司得到较广泛的应用,前者侧重于将这个理论作为机制来研究、而后者则使用作为大规模数据的处理的工具3。 Rough集理论除了朝着逻辑及其近似推理方向发展以外,近些年来出现了大量的Rough数及Rough函数的研究,发表了一系列关于Rough函数方面的论文,Rough函数的各种近似运算,Rough函数的基本性质,关于它的Rough连续,
39、Rough数限,Rough可导Rough积分和Rough稳定性,Rough函数控制及建立由Rough实函数控制的离散动态系统都是典型的问题,这些问题都要求在Rough函数理论的模型下,给予公式化。这些问题的研究将有贡献于定性推理方法的研究。这种研究实质上是使连续数学离散化。如此,连续数学也能被现代计算机所接受。 目前,对RS理论研究集中在其数学性质,RS拓广,与其它不确定方法的关系和互补,及有效算法等方面。1)RS理论数学性质方面的研究,主要讨论RS的代 数结构。拓扑结构,以及RS的收敛性问题。2)RS拓广方面的研究主要涉及广义RS模型(或称 变精确性RS模型)与对连续属性的离散化等。3)RS
40、理论与其他不确定性方法之间的关系的研究 中,目前主要讨论它与模糊集理论和D-S证据理 论的关系和互补。 4 4)在)在RSRS有效算法方面的研究,主要集中于有效算法方面的研究,主要集中于 (a a)导出规则的增量式算法:导出规则的增量式算法:原有的算法是在固定的数据集上进行的,当有原有的算法是在固定的数据集上进行的,当有新的数据增加到数据集时,若用原有算法导出规新的数据增加到数据集时,若用原有算法导出规则是相当麻烦的,增量式算法是对原有规则进行则是相当麻烦的,增量式算法是对原有规则进行修正,从而得出关于新数据集的规则的方法。修正,从而得出关于新数据集的规则的方法。 (b)约简的启发式算法对于一
41、个信息系统来说,找出其所有约简是NP完全问题,很自然的想法是采用启发式方法找出最优或次优约简,这些算法的共同特点是利用属性的重要性作为启发式,去求约简,只是它们对属性重要性的度量不同。 (c)RS基本运算的并行算法RS的基本性质决定,它的很多基本运算可以并行计算,由于RS研究的初衷就是试图为处理大量数据提供一个数学工具。由此,这些性质就显得十分重要了。 5)基于RS的逻辑是关于RS的不确定推理的基础,发展这类逻辑的理论基础也是目前RS理论研究的重要课题。今后,围绕着其逻辑特点和知识处理机理,主要有下列研究方向值得注意。其一、是数学理论的系统化和形式化。尽管Rough集理论产生于真正的数学基础,
42、但许多理论问题仍有待于真正澄清。Pawlak粗糙集模型的推广一直是RS理论研究的主流方向,目前主要有两种方法 a)构造性方法 b)代数性(公理化)方法。 其二、是算法的研究。RS理论中有效算法研究是粗糙集在人工智能方向上研究的一个主要方向。目前,RS理论中有效算法研究主要集中在导出规则的增量式算法,约简的启发式算法,粗糙集基本并行算法,以及与粗糙集有关的神经网络与遗传算法等。这些研究的成功应用有的已经获得了商业价值。 其三、是面向粗糙集对象的专家系统和智能系统和粗糙集在工程技术方面的应用。 其四、其四、是与其他数学理论的联系。从算子的观是与其他数学理论的联系。从算子的观点看点看RSRS理论,与
43、之关系较紧的有拓扑空间,数理逻理论,与之关系较紧的有拓扑空间,数理逻辑,格与布尔代数,模态逻辑,算子代数等。从构辑,格与布尔代数,模态逻辑,算子代数等。从构造性和集合的观点来看,它与概率统计、模糊数学、造性和集合的观点来看,它与概率统计、模糊数学、证据理论、图论、信息论等联系较为密切。证据理论、图论、信息论等联系较为密切。RSRS理论理论研究不但需要以这些理论作为基础,同时也相应地研究不但需要以这些理论作为基础,同时也相应地带动这些理论的发展。随着带动这些理论的发展。随着RSRS结构与代数结构、拓结构与代数结构、拓扑结构、序结构等各种结构的不断整合,必将不断扑结构、序结构等各种结构的不断整合,
44、必将不断涌现出新的富有生机的数学分支涌现出新的富有生机的数学分支22,1717。 1 Pawlak Z.,Rough SetsJ, International Journal of Computer and Information Sciences, 11,1982:341-356.2 张文修等,粗糙集理论介绍和研究综述J,模 糊系统与数学,Vol.14,No.4,2000:1-12.3 王珏等,关于Rough Set理论与应用的综述J, 模式识别与人工智能,Vol.9,No.4,1996:337-344.4王志海等,基于粗糙集合理论的知识发现综述J, 模式识别与人工智能,Vol.11,No.
45、2,1998:176-183. 5 5 曾黄麟,粗集理论及其应用曾黄麟,粗集理论及其应用 MM,重庆大学出版重庆大学出版 社,社, 1998 1998。6 6 刘文奇,刘文奇,PawlakPawlak代数及其性质代数及其性质 JJ,模糊系统与模糊系统与 数学,数学,Vol.13, No.2,1999:78-84.Vol.13, No.2,1999:78-84.7 7 刘清等,刘清等,RoughRough集理论:现状与前景集理论:现状与前景 JJ,计算机计算机 科学,科学,Vol.24,No.4,1997:1-5.Vol.24,No.4,1997:1-5.8 8 刘真译,刘真译,RoughRou
46、gh集集 JJ,计算机科学,计算机科学, Vol.24,No.1,1997:15-19. Vol.24,No.1,1997:15-19.9 Pawlak Z.,On Decision TablesJ, Bulletin 9 Pawlak Z.,On Decision TablesJ, Bulletin of the Polish Academy of Sciences of the Polish Academy of Sciences Technical Sciences, Vol.34,No.9-10,1986.563-571 Technical Sciences, Vol.34,No.9-
47、10,1986.563-571 10 10 Pawlak Z.,Decision Table ComputerJ, Pawlak Z.,Decision Table ComputerJ, Bulletin of the Polish Academy of Sciences Bulletin of the Polish Academy of Sciences Technical Sciences, Vol.34,No.9-10,1986:591-Technical Sciences, Vol.34,No.9-10,1986:591-595.595.11 Pawlak Z.,On Superflu
48、ous Attributes in 11 Pawlak Z.,On Superfluous Attributes in Knowledge Representation SystemJ, Bulletin Knowledge Representation SystemJ, Bulletin of the Polish Academy of Sciences Technical of the Polish Academy of Sciences Technical Sciences, Vol.32,No.3-4,1984.211-213.Sciences, Vol.32,No.3-4,1984.
49、211-213.12 Pawlak Z.,On Rough Dependency of 12 Pawlak Z.,On Rough Dependency of attributes in Information SystemsJ, attributes in Information SystemsJ, Bulletin of the Polish Academy of Sciences Bulletin of the Polish Academy of Sciences Technical Sciences, Vol.33,No.9-10,1985:481-Technical Sciences
50、, Vol.33,No.9-10,1985:481-485.485. 13 13 Y.Y.Yao, A comparative study of fuzzy sets Y.Y.Yao, A comparative study of fuzzy sets and rough setsJ, Journal of Information and rough setsJ, Journal of Information Sciences ,109,1998 :227-242.Sciences ,109,1998 :227-242.14 Mohamed Quafafou, -RST: a generali