资源描述
粗糙集理论-研究现状与发展前景粗糙集理论-研究现状与发展前景主要内容研究背景粗糙集基本理论粗糙集与知识表达与其它处理不确定性问题方法的关系粗糙集理论的应用与发展前景参考文献主要内容研究背景研究背景粗糙集(RoughSets)是波兰数学家Z.Pawlak于1982年提出的1(为开发自动规则生成系统及研究软计算问题而引入)。由于最初关于粗糙集理论的研究大部分是用波兰语发表的,因此当时没有引起国际计算机学界和数学界的重视。研究地域也局限在东欧一些国家,直到80年代末才引起各国学者的注意。九十年代初,人们才逐渐认识到它的意义。1992年在波兰Kiekrz召开了第一届国际RS研讨会。这次会议着重讨论了集合近似定义的基本思想及应用,其中RS环境下的机器学习基础研究是这次会议的四个专题之一。研究背景粗糙集(RoughSets)是波研究背景(续)1993年在加拿大Banff召开第二届国际RS理论与知识发现研讨会。这次会议积极推动了国际上对RS理论与应用的研究。由于当时正值KDD(数据库知识发现)成为研究的热门话题,一些著名KDD学习者参加这次会议,并且介绍了许多应用扩展RS理论的知识发现方法与系统。1996年在日本东京召开了第5届国际RS研讨会,推动了亚洲地区对RS理论与应用的研究。1995年,ACMCommunication将其列为新浮现的计算机科学的研究课题。研究背景(续)1993年在加拿大Banff召开第二届研究背景(续)1998年,国际信息科学杂志(InformationSciences)为粗糙集理论的研究出了一期专辑2,3。第一届中国RS理论与软计算学术研讨会,于2001年5月在重庆举行。第二届中国RS理论与软计算学术研讨会,于2002年10月在苏州大学举行。第三届中国RS理论与软计算学术研讨会,于2003年8月在重庆举行。第四届中国RS理论与软计算学术研讨会,将于2004年在舟山举行。研究背景(续)1998年,国际信息科学杂志(Info粗糙集的理论及应用的文章主要发表在以下杂志国内:1模式识别与人工智能2软件学报3科学通报4计算机科学5计算机学报6模糊系统与数学7计算机应用与软件8计算机研究与发展9计算技术与自动化粗糙集的理论及应用的文章国内:1模式识别与人工粗糙集的理论及应用的文章主要发表在以下杂志(续)国际:1InformationSciences2Fuzzysetsandsystems3InternationalJournalofComputerandInformationSciences4CommunicationoftheACM5ComputationalIntelligence6Journalofcomputerandsystemsciences粗糙集的理论及应用的文章国际:1Informa7AIMagazine8AICommunications9EuropeanJournalofOperationalResearch10InternationalJournalofApproximateReasoning11Theoreticalcomputersciences12DecisionsupportSystems13InternationalJournalofMan-Machinestudies14FundamentaInformaticae15IntelligentAutomationSciences7AIMagazine粗糙集理论粗糙集理论是一种处理不精确、不确定与不完全数据的新的数学方法。由于它在机器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、模式识别等方面的广泛应用,现已成为一个热门的研究领域2。RS理论主要兴趣在于它恰好反映了人们用Rough集方法处理不分明问题的常规性,即以不完全信息或知识去处理一些不分明现象的能力。或依据观察,度量到的某些不确定的结果而进行分类数据的能力4。粗糙集理论粗糙集理论是一种处理不精确、不确定粗糙集理论的基本概念RS理论认为知识即是将对象进行分类的能力,假定我们起初对全域里的元素(对象)具有必要的信息、或知识,通过这些知识能够将其划分到不同的类别。若我们对两个元素具有相同的信息,则它们就是不可区分的(即根据已有的信息不能够将其划分开)。显然这是一种等价关系。不可区分关系是RS理论最基本概念。在此基础上引入了成员关系,上近似和下近似等概念来刻划不精确性与模糊性1,2,4,5。粗糙集理论的基本概念RS理论认为知识即是将对象进行样本粗糙集方法处理具有优化指标的样本评审样本学习样本数据预处理(粗糙集方法、模糊集方法)模糊、粗糙推理神经网络遗传算法智能信息系统样本粗糙集方法处理具有优化指标的样本评审样本学习样设U是非空有限论域(全域、集合),R是U上的二元等价关系(具有相反、对称、传递性的关系),R称为不可分辨关系。序对A=(U,R)称为近似空间。,若,则称对象x与y在近似空间A中是不可分辨的。U/R是U上由R生成的等价类全体,它构成U的一个划分,U上的划分可以与U上的二元等价关系之间建立一一对应。基本概念基本概念U/R中的元素(集合)称为U的基本集或原子集,任意有限个基本集的并称为可定义集,空集也称为可定义集(可定义集也称为精确集)。否则称为不可定义集。若将U中的集合称为概念或表示知识,则A=(U,R)称为知识库,原子集(基本集)表示基本概念或知识模块。那么精确集可以在知识库中被精确地定义或描述,可表示已知的知识。基本概念(续)基本概念(续)上近似,下近似对于一个近似空间A=(U,R),X是U的任意一个子集。X不一定能用知识库中的知识来精确地描述;即X可能为不可定义集,这时就用X关于A的一对下近似、上近似来“近似”地描述。下面表示x所在的R-等价类。称为集合X关于R的下近似。=称为集合X关于R的上近似。上近似,下近似对于一个近似空间A=(U,R),粗糙集理论-研究现状与发展前景课件例1给定一玩具积木的集合,并假设这些积木有不同的颜色(红、黄、蓝),形状(方、圆、三角)和体积(大、小)。积木的集合U可按颜色、形状、体积分类。:颜色关系,:形状关系,:体积。则例1给定一玩具积木的集合例1(续)取,那么例1(续)取下近似下近似也称为也称为X X关于近似空间关于近似空间A A的正域,的正域,记为记为pospos(X X)。)。解释为:由那些根据现有知识判断出肯定属于解释为:由那些根据现有知识判断出肯定属于X X的对象的对象所组成的最大集合。所组成的最大集合。上近似上近似可以解释为:由那些根据现有知识判断出可以解释为:由那些根据现有知识判断出可能属于可能属于X X的对象所组成的最小集合。的对象所组成的最小集合。称作称作X X关于关于A A的负域,记为的负域,记为neg(X)neg(X)。解释为:由那些根据现有知识判断肯定不属于解释为:由那些根据现有知识判断肯定不属于X X的对象的对象所组成的集合。所组成的集合。下近似也称为X关于近似空间A的正域,称作称作X X的边界(域)记为的边界(域)记为BND(X)BND(X)。解释为:由那些根据现有知识判断出可能属于解释为:由那些根据现有知识判断出可能属于X X但不能但不能完全肯定是否一定属于完全肯定是否一定属于X X的对象所组成的集合的对象所组成的集合55。(上下近似之差,即:上下近似之差,即:)X X是可定义是可定义;XX是不可定义的是不可定义的,此时称,此时称X X在近在近似空间似空间A A中是粗糙集。中是粗糙集。同时,同时,称为粗糙代数系统称为粗糙代数系统66,其中其中 表示集合补。表示集合补。粗糙集的几种表示称二元对为Rough集(粗糙集)可认为Rough集的另一种表示形式,这种定义方式可直接算出U上关于其子集X的含糊元素数目。这种边界区意味着由于掌握的知识不完全而存在不能辨别的区域,即bnd(X)上的元素不可分辨,所以U上子集X关于U上不分明关系R是Rough的,主要是,否则它是可分辨的。一个集合X的边界区域越大,则这个集合X的含糊元素也越多,这种思想可以用数值化的系数表示。粗糙集的几种表示称二元对粗糙集的几种表示(续),cardX表X的基数。称为X的近似精度,(粗糙程度。于是也可用来定义Rough集。当,称U上子集X关于U上不分明关系R是Rough的;当,称X关于R是精确的;可被用作Rough逻辑中的算子。粗糙集的几种表示(续)粗糙集的几种表示(续)在Rough集上也有元素隶属于集合的问题(与Fuzzy集一样)。设,则。称为Rough隶属函数,解释为一种条件概率,能从全域上的个体加以计算。Fuzzy集上的隶属函数则不然。用来定义Rough集,则得到Rough集的第四种表示形式。粗糙集的几种表示(续)在Rough集上也有元素隶属于集合的粗糙集的几种表示(续)若存在,有,称X关于R是Rough的,若对每个,有,则X关于R是精确的。相反地,Rough隶属函数可用来定义一个集合的上、下近似集及边界集粗糙集的几种表示(续)若存在,有粗糙集的几种表示(续)无论哪一种Rough集的表示形式都离不开全域U上的不分明关系R以及由R定义的下和上近似集。因此对Rough集理论中的不分明关系以及下和上近似集的研究尤其重要。定义观点的不同往往带来研究的侧重面的不同。粗糙集的几种表示(续)X关于A的度量X关于A的近似质量:近似质量反映了知识X中肯定在知识库中的部分在现有知识中的百分比。X关于A的粗糙性测度:则,且X是可定义的X是粗糙的。粗糙性测度反映了知识的不完全程度。X关于A的度量X关于A的近似质量:X关于A的度量(续)X关于A的近似精度:它反映了根据现有知识对X的了解程度2,5。X关于A的度量(续)X关于A的近似精度:集合类关于近似空间的下近似、上近似设是由U的子集所构成的集类。则F关于近似空间A的下近似F和上近似F:F关于A的近似精度集合类关于近似空间的下近似、上近似设集合类关于近似空间的下近似、上近似近似质量为当F也是U的划分时,F关于A的近似在判别一个决策表是否是协调的和规则提取中有重要作用。集合类关于近似空间的下近似、上近似近似质量为粗糙集理论中的知识表示v信息系统v属性的约简及核v规则的协调与提取粗糙集理论中的知识表示信息系统属性的约简 信息系统粗糙集理论中的知识表达方式一般采用信息表或称为信息系统的形式。信息表表示输入数据,这些数据是从任意领域中收集的。信息系统可用四元有序组表示,其中U是对象的全体,即论域;A是属性全体;,是属性a的值域;是一个信息函数,反映了对象x在K中的完全信息5,10。如下信息表:信息系统粗糙集理论中的知识表达方式一般采用信息表或称为对象 属性头痛 肌肉痛 体温 决策 流感是 是 正常 否是 是 高 是是 是 很高 是否 是 正常 否否 否 高 否否 是 很高 是表1信息表对象属性决策是是 信息系统(续)标记被称为实例(个体,实体,对象),记。识别两种变量:属性(有时称之为条件属性),决策(有时称之为决策属性)。例如:如果信息表描述一家医院,每个实例可能就是病人,属性是症状和检测,而决策是病症。如果信息表表示一个工业生产过程,则这些实例可代表在某些特定时刻及时采集的过程中的样品,属性是过程中的参数,而决策是由操作员(专家)采取的决定。信息系统(续)标记 信息系统(续)RS理论的一个重要概念是不分明关系,它通常与一属性集合联系在一起。如上表1中头痛、肌肉痛、体温均为属性。)头痛且肌肉痛决定不分明关系,则)集合根据属性头痛和肌肉痛是可定义的。)头痛和体温决定不分明关系,则信息系统(续)RS理论的一个重要概念是不分明关 信息系统(续)iv)头痛、体温、肌肉痛决定不分明关系,则于是说明肌肉痛是多余的属性。对于信息系统,每个属性子集都定义了论域上的一个等价关系。即,对信息系统(续)属性的约简及核粗糙集理论给出了对知识(或数据)的约简和求核的方法,从而提供了从信息系统中分析多余属性的能力2,5,9,10。信息系统类似于关系数据库模型的表达方式。有时属性集A还可分为条件属性C和决策(结论)属性D,这时的信息系统也称为决策表,常记为。无决策的数据分析和有决策的数据分析是粗糙集理论在数据分析中的两个主要应用。属性的约简及核粗糙集理论给出了对知识(定义:设是一个信息系统,由属性集所导出的等价关系为。)设,则称属性a是多余的(如表1中的肌肉痛)。)若在系统中没有多余属性,则称A是独立的iii)子集称为是A的约简。若,且B中没有多余属性。常记为A的全体约简,)A的所有约简的交集称为A的核,记为core(A)。一般来说:属性集的约简不唯一而核是唯一的。定义:设 例2(无决策情形的属性的约简、核)设,其中,信息函数见下表2例2(无决策情形的属性的约简、核)设 例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 2例2(续)例2(续)因此将对象及其信息压缩后得下面表3例2(续)因此将对象及其信息压缩后得下面表3 例2(续)表3信息系统U/A ,1 1 1 1 ,1 2 2 1 ,2 2 1 1 ,3 3 3 2且可验证属性是多余,且令。则有中没有多余属性。例2(续)例2(续)于是信息表2有三个属性的约简,即,从而可得信息系统的三个约简表如下。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的核:CoreA=头痛,体温。例2(续)于是信息表2有三个属性的约简,即 规则的协调与提取粗糙集理论除给出了对知识(或数据)的约简和求核的方法外,还提供了从决策表中抽取规则的能力,机器学习和从数据库中的机器发现就是基于这个能力。在一个决策表中,若,X关于由导出的近似空间的下近似和上近似相等,即,称条件属性子集关于决策属性是协调的。也称决策表是协调的,否则为不协调10。规则的协调与提取粗糙集理论除给出了对 规则的协调与提取(续)如果用包含度理论来解释,则决策表是协调的,当且仅当2,其中规则的协调与提取(续)如果用包含度理论来解释,规则的协调与提取(续)从协调的决策表中可以抽出确定性规则,而从不协调的决策表中只能抽出不确定性的规则或可能性规则,有时也称为广义决策规则,这是因为在不协调的系统中存在着矛盾的事例。决策表中的决策规则一般可以表示为形式5:其中称为规则的条件表示,称为规则的决策部分。决策规则即使是最优的也不一定唯一。规则的协调与提取(续)从协调的决策表中可以 规则的协调与提取(续)在决策表中抽取规则的一般方法为3:(1)在决策表中将信息相同(即具有相同描述)的对象及其信息删除只留其中一个得到压缩后的信息表,这一步称为删除多余事例;(2)删除多余的属性;(3)对每一个对象及其信息中将多余的属性值删除;(4)求出最小约简;(5)根据最小约简,求出逻辑规则。规则的协调与提取(续)在决策表中抽取规则的一般方法为 例3(决策情形)设,其中,具体的决策表见下面表4例3(决策情形)设 例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 2 1 1 2 2 1 3 2 4 3 5 3 5 4 5 4 5例3(续)例3(续)因此例3(续)因此 例3(续)从而对于它的决策子表(,V,),(,V,),我们可得到它们的一个约简表如下(一般不唯一)例3(续)从而对于它的决策子表(,例3(续)1 1 1 1 2 2 2 1 3 2 3 4 1 1 1 1 2 2 1 1 3 1 2 4 2 2 5 3 3 5表5表6例3(续)1111222 例3(续)且,故(,V,)是协调的。但,故(,V,)不协调的。例3(续)且,例3(续)由表5可得决策表(,V,)的四条最优决策规则。且这四条规则都是确定的。例3(续)由表5可得决策表(,V 例3(续)由表6(它是不协调的)也可得到决策表(,V,)的四条最优决策规则:其中是不确定的,而只有是确定的。例3(续)由表6(它是不协调的)也可得到决策表其中 与其他不确定性数学方法的关系RS理论与其他处理不确定和不精确问题理论的最显著的区别是无需提供问题所需处理的数据集合之外的任何先验信息即它不需要任何预备的或额外的有关数据信息。如统计学中的概率分布,Fuzzy理论中的隶属度函数等。所以RS理论对问题的不确定性的描述或处理可以说是比较客观的。与其他不确定性数学方法的关系RS理 与其他不确定性数学方法的关系由于这个理论未能包含处理不精确或不确定原始数据的机制,因此,单纯地使用这个理论不一定能有效地描述数据不精确或不确定的实际问题,而证据理论与模糊集理论等具有处理不精确或不确定数据的方法,所以这个理论与概率统计,模糊数学,证据理论等其他处理不精确或不确定问题的理论有很强的互补性。与其他不确定性数学方法的关系由于这 与其他不确定性数学方法的关系在粗糙集理论与其它处理模糊性或不确定性方法的理论研究中,主要集中在它与概率统计,模糊数学,DS证据理论和信息论的相应渗透与补充。下面从三方面进行比较。(1)与概率统计结合(2)与模糊数学(3)与DS证据理论(DempsterShafer证据理论)。与其他不确定性数学方法的关系在粗糙集 与概率统计结合在信息系统中,知识库的知识的类型一般有两类:一类库中所有对象的描述是完全已知的,Pawlak粗糙集模型和一般二元关系下的粗糙集模型的是属于这一种。另一类库中的对象的描述只有部分是已知的,即知识库中的知识是不确定的,它只能通过训练样本所提供的信息来刻画概念。与概率统计结合在信息系统中,知识库的知识 与概率统计结合(续)为了使从训练样本获得的规则符合整个论域的对象,在抽取样本时应符合统计规律性,粗糙集理论不管这一类工作,因些概率统计作为研究自然界,人类社会及技术过程中大量随机现象的规律性的一门学科,它与粗糙集理论的结合就显得非常自然2。与概率统计结合(续)为了使从训练样本获得的规则符合整 与模糊数学粗糙集理论用粗糙隶属函数来刻画知识的模糊性2,13,14。()这是对一般二元关系R下的近似空间A(,R)而言的。当R为等价关系时,。()与模糊数学粗糙集理论用粗糙隶属函数来 与模糊数学(续)在概率近似空间下,用它表示粗糙隶属函数。粗糙隶属一般不是Zadeh意义下的隶属函数。粗糙集理论和模糊集理论在处理不确定性和不精确性问题方面都推广了经典集合论,虽有一定的相容性和相似性,然后它们的侧重面不同。a)从知识的“粒度“的描述上来看,模糊集通过对象关于集合的隶属程度来近似描述;而粗糙集是通过一个集合关于某个可利用的知识库的一对上、下近似来描述的。与模糊数学(续)在概率近似空间下,用它表示粗 与模糊数学(续)b)从集合对象间的关系来看,模糊集强调的是集合边界的不分明性,而粗糙强调是是对象间的不可分辨性。c)从研究的对象来看,模糊集研究的是属于同一类的不同对象间的隶属关系,重在隶属程度,而粗糙集研究的是不同类中的对象组成的集合关系,重在分类。与模糊数学(续)b)从集合对象间的关系来看 与模糊数学(续)虽然模糊集的隶属函数和粗糙集的粗糙隶属函数都反映了概念的模糊性,直观上有一定的相似性,但模糊集的隶属函数大多是专家凭经验给出的,因此往往带有很强烈的主观意志,而粗糙的粗糙隶属函数的计算是从被分析的数据中直接获得的,非常客观。也正因为如此,将粗糙集理论和模糊集理论进行某些“整合”后去描述知识的不确定性和不精确性比它们各自描述知识的不确定性和不精确性可望显示更强的功能。(目前所见的模糊粗糙集模型是其中的一些成功范例)。与模糊数学(续)虽然模糊集的隶属函 与DS证据理论粗糙集理论是为开发规则的机器自动生成而提出的,而DS理论主要用于证据推理;RS理论用概念的一对上,下近对其进行描述,而DS证据理论是用一对信任函数和似然函数在给定证据下对假设进行估计和评价。RS理论中的下近似和上近似的概率恰好分别是信任函数和似然函数。然而生成信任函数和似然函数的基本概率分配函数(mass函数)方法是不同的。前者来自于系统中数据本身,比较客观,而后者往往来自于专家的经验,带有很强的主观性。RS理论与DS证据理论有很强的互补性15。与DS证据理论粗糙集理论是 与DS证据理论(续)粗糙集理论中知识的不确定性主要由两个原因产生2:(1)直接来自论域上的二元关系及其产生的知识模块,即近似空间本身。如果二元等价关系产生的每一个等价中只有一个元素,那么等价关系产生的划分不含有任何信息,划分越粗,每个知识模块越大,知识库中的知识越粗糙,相对于近似空间的概念和知识就越不确定。这时处理知识的不确定性的方法往往用香农信息熵来刻画,知识的粗糙性与信息熵的关系比较密切,知识的粗糙性实质上是其所含信息多少的更深层次刻画。单从这个角度来看,RS理论与信息论的关系就比较密切。与DS证据理论(续)粗糙集理论中知识的不确定性主要 与DS证据理论(续)粗糙集理论中知识的不确定性主要由两个原因产生2:(2)来自于给定论域里粗糙近似的边界。当边界为空集时知识就是完全确定的,边界越大知识就越粗糙或越模糊。至今,RS理论刻画概念X的不确定性用正则条件熵和粗糙性测度来实现的。但这两个度量并没有完全提供哪些完全属于X的下近似的区域里面与不可分辨关系的知识粒度有关的不确定性,于是有人引进了粗糙熵Er(X)的概念来刻画概念X的不确定性,所以,寻求一个合适的度量来刻画知识的不确定性也是RS理论研究的一个重要方向2,16。与DS证据理论(续)粗糙集理论中知识的不确定性主 粗集理论的应用及发展前景RS理论已经被证实在实践中是非常有用的。从大量的现实生活中应用的记录来看已经非常明显,这一理论对AI(人工智能)和认知科学尤为重要,在专家系统,决系表等方面都有有非常成功的应用实例。利用Rough集理论处理的主要问题包括:数据简化(即删除多余的数据),数据相关性的发现,数据意义的评估,由数据产生决策(控制)算法,数据的近似分类等。下面介绍两的应用和研究前景:粗集理论的应用及发展前景RS理论已经被证实在实(1)美国Kansas大学开发了基于RS方法学习的例子,并开发了基于Rough集方法的学习系统LERS(LearningfromExamplesbasedonRS)。这个系统的知识获取项对于用不完全信息工作的专家系统,帮助其建立知识库是一个十分恰当的规则归纳法的应用实例,它在NASASJohnson空间中心应用了多年,充分显示了它在开发专家系统进行全球气候变化的研究中起的作用,它是作为一种开发专家系统的工具被引用的。基于RS的典型系统(1)美国Kansas大学开发了基于RS方法学习的例子,LERS可以从信息表形式中给定的实例导出一套规则集,并且可以利用这一套规则分类新的实例,LERS还被用于两项医学方面,其一用来比较手术后的病人取暖设备的效果,其二用来评估孕妇超强度劳动的危险。还有一种很重要的LERS用途是全球气候变化的研究,描述对全球气温有影响的规则由一些属性所表征的数据引出。如太阳的能量释放,火山活动、美国南部的指针摇摆器、二氧化碳流向和二氧化碳的余量。这方面的专家依据获得的新数据把握地球气候变化的奥妙。基于RS的典型系统(续)LERS可以从信息表形式中给定的实例导出一套规 Rough Rough集理论之所以提供了集理论之所以提供了AIAI的有效方法,的有效方法,是因为实现它的程序可以很容易在平行机上运行。是因为实现它的程序可以很容易在平行机上运行。且基于且基于RoughRough集理论的集理论的RoughRough逻辑将使单调逻辑非单逻辑将使单调逻辑非单调化,从而在调化,从而在AIAI的近似或不精确推理中将发挥不可的近似或不精确推理中将发挥不可估量作用。估量作用。基于RS的典型系统(续)Rough集理论之所以提供了AI的有效方法,是 (2 2)RoughRough集方法用于决策分析已体现在波集方法用于决策分析已体现在波兰兰PoznanPoznan科技大学开发的计算机系统中,称之为科技大学开发的计算机系统中,称之为Rough DASRough DAS和和Rough ClassRough Class,它们对任务分别执行解它们对任务分别执行解释和描述。这两个系统已经在许多实际领域都有应释和描述。这两个系统已经在许多实际领域都有应用。(用。(Rough DASRough DAS执行信息系统数据分析任务,执行信息系统数据分析任务,Rough ClassRough Class支持新对象的分类,这两个软件都是支持新对象的分类,这两个软件都是基于基于DOSDOS操作系统的)操作系统的)44。基于RS的典型系统(续)(2)Rough集方法用于决策分析已体现在波兰P RS理论在AI中的应用可分为两大类:有决策的分析,无决策的分析。有决策的分析主要包括:监督学习与决策分析。RS理论在监督学习中的应用可分为两个方面:其一:对学习的训练集作预处理,这是考试到从实际测量中所获得的训练集,常包含有多余的属性,应用RS的属性约简可有效地去除冗余的属性。例如:对豌豆疾病的数据进行RS处理,使得原有属性数从35个约简到9个;对美国1984年众议案的投票数据的分析,则使属性从原有16个减少为9个。另外,每个属性的值域也会有冗余,同样应用RS方法中的约简技术可以删除某些属性的多余值。RS理论在AI中的应用可分为两大类:有决策的分析,无决 RS理论在AI中的应用(续)(续)其二应用RS方法获取规则:利用RS中提供的值约简方法由实例集直接获取规则,但是,由于从决策表中直接获取所有的值约简已被证明是一个NP完全问题,因此,利用领域独立的启发式算法求取最小约简是一个自然的方法。例如,通过值约简可将美国1984年众议案的投票数据由435个例子约简为44条规则。RS理论在AI中的应用(续)其二应用RS方法获取规 RS理论在AI中的应用(续)(续)RS理论应用于有决策分析还包括:(1)应用于决策不完全时的学习(利用RS理论中的上,下近似的概念表示不完全的决策,以及对学习效果所产生的影响)。(2)进行增量式学习(从RS理论中的差别矩阵出发,利用与或逻辑求取规则描述,对新的例子只需在差别矩阵上添加相应的行列,即可获取增量后的规则)。在决策分析的应用中,则是利用RS理论的属性约简,值约简及核等概念,对被决策的数据进行约简和寻找对于决策最有用的信息。RS理论在AI中的应用(续)RS理论应用于有决 RS理论在AI中的应用(续)(续)无决策的数据分析主要是:数据压缩、化简、聚类、模式发现与机器发现等。这类问题主要是利用属性的约简去除不必要的属性,利用值约简压缩数据及进行数据的聚类分析,由于无决策的数据的约简问题也是NP完全问题,因而仍要利用启发式知识求取最小约简。属于这类应用的典型AI分支是机器发现,特别是从大型数据库进行知识发现,RS被认为是一个非常有效的方法。RS理论在AI中的应用(续)无决策的数据分析主要 RS理论在AI中的应用(续)(续)近几年来,RS理论已在很多实际领域得到了成功应用。如美国的NASAJohnson空间中心利用LERS学习系统来发展空间自由行走的医学专家系统,希腊的工业发展银行ETEUA应用RS求取贷款信用,美国的环境保护署利用LERS来增进资源之间的协调等。目前,RS理论已在西方的研究机构和大学与大的公司得到较广泛的应用,前者侧重于将这个理论作为机制来研究、而后者则使用作为大规模数据的处理的工具3。RS理论在AI中的应用(续)近几年来,RS理论已研究领域与前景 Rough集理论除了朝着逻辑及其近似推理方向发展以外,近些年来出现了大量的Rough数及Rough函数的研究,发表了一系列关于Rough函数方面的论文,Rough函数的各种近似运算,Rough函数的基本性质,关于它的Rough连续,Rough数限,Rough可导Rough积分和Rough稳定性,Rough函数控制及建立由Rough实函数控制的离散动态系统都是典型的问题,这些问题都要求在Rough函数理论的模型下,给予公式化。这些问题的研究将有贡献于定性推理方法的研究。这种研究实质上是使连续数学离散化。如此,连续数学也能被现代计算机所接受。研究领域与前景Rough集理论除了朝着逻辑及其近似研究领域与前景(续)(续)目前,对RS理论研究集中在其数学性质,RS拓广,与其它不确定方法的关系和互补,及有效算法等方面。1)RS理论数学性质方面的研究,主要讨论RS的代数结构。拓扑结构,以及RS的收敛性问题。2)RS拓广方面的研究主要涉及广义RS模型(或称变精确性RS模型)与对连续属性的离散化等。3)RS理论与其他不确定性方法之间的关系的研究中,目前主要讨论它与模糊集理论和D-S证据理论的关系和互补。研究领域与前景(续)目前,对RS理论研究集中在其数学性质研究领域与前景(续)(续)4 4)在)在RSRS有效算法方面的研究,主要集中于有效算法方面的研究,主要集中于 (a a)导出规则的增量式算法:导出规则的增量式算法:原有的算法是在固定的数据集上进行的,当有原有的算法是在固定的数据集上进行的,当有新的数据增加到数据集时,若用原有算法导出规新的数据增加到数据集时,若用原有算法导出规则是相当麻烦的,增量式算法是对原有规则进行则是相当麻烦的,增量式算法是对原有规则进行修正,从而得出关于新数据集的规则的方法。修正,从而得出关于新数据集的规则的方法。研究领域与前景(续)4)在RS有效算法方面的研究,主要集研究领域与前景(续)(续)(b)约简的启发式算法对于一个信息系统来说,找出其所有约简是NP完全问题,很自然的想法是采用启发式方法找出最优或次优约简,这些算法的共同特点是利用属性的重要性作为启发式,去求约简,只是它们对属性重要性的度量不同。(c)RS基本运算的并行算法RS的基本性质决定,它的很多基本运算可以并行计算,由于RS研究的初衷就是试图为处理大量数据提供一个数学工具。由此,这些性质就显得十分重要了。研究领域与前景(续)(b)约简的启发式算法研究领域与前景(续)(续)5)基于RS的逻辑是关于RS的不确定推理的基础,发展这类逻辑的理论基础也是目前RS理论研究的重要课题。今后,围绕着其逻辑特点和知识处理机理,主要有下列研究方向值得注意。其一、是数学理论的系统化和形式化。尽管Rough集理论产生于真正的数学基础,但许多理论问题仍有待于真正澄清。Pawlak粗糙集模型的推广一直是RS理论研究的主流方向,目前主要有两种方法a)构造性方法b)代数性(公理化)方法。研究领域与前景(续)5)基于RS的逻辑是关于RS的不确定研究领域与前景(续)(续)其二、是算法的研究。RS理论中有效算法研究是粗糙集在人工智能方向上研究的一个主要方向。目前,RS理论中有效算法研究主要集中在导出规则的增量式算法,约简的启发式算法,粗糙集基本并行算法,以及与粗糙集有关的神经网络与遗传算法等。这些研究的成功应用有的已经获得了商业价值。其三、是面向粗糙集对象的专家系统和智能系统和粗糙集在工程技术方面的应用。研究领域与前景(续)其二、是算法的研究。RS理论中研究领域与前景(续)(续)其四、其四、是与其他数学理论的联系。从算子的观是与其他数学理论的联系。从算子的观点看点看RSRS理论,与之关系较紧的有拓扑空间,数理逻理论,与之关系较紧的有拓扑空间,数理逻辑,格与布尔代数,模态逻辑,算子代数等。从构辑,格与布尔代数,模态逻辑,算子代数等。从构造性和集合的观点来看,它与概率统计、模糊数学、造性和集合的观点来看,它与概率统计、模糊数学、证据理论、图论、信息论等联系较为密切。证据理论、图论、信息论等联系较为密切。RSRS理论理论研究不但需要以这些理论作为基础,同时也相应地研究不但需要以这些理论作为基础,同时也相应地带动这些理论的发展。随着带动这些理论的发展。随着RSRS结构与代数结构、拓结构与代数结构、拓扑结构、序结构等各种结构的不断整合,必将不断扑结构、序结构等各种结构的不断整合,必将不断涌现出新的富有生机的数学分支涌现出新的富有生机的数学分支22,1717。研究领域与前景(续)其四、是与其他数学理论的联系。参考文献 1PawlakZ.,RoughSetsJ,InternationalJournalofComputerandInformationSciences,11,1982:341-356.2张文修等,粗糙集理论介绍和研究综述J,模糊系统与数学,Vol.14,No.4,2000:1-12.3王珏等,关于RoughSet理论与应用的综述J,模式识别与人工智能,Vol.9,No.4,1996:337-344.4王志海等,基于粗糙集合理论的知识发现综述J,模式识别与人工智能,Vol.11,No.2,1998:176-183.参考文献1PawlakZ.,RoughSet5 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 刘真译,刘真译,RoughRough集集 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 Technical of the Polish Academy of Sciences Technical Sciences,Vol.34,No.9-10,1986.563-571 Sciences,Vol.34,No.9-10,1986.563-571 5曾黄麟,粗集理论及其应用M,重庆大学出版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 Superfluous 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.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,Vol.33,No.9-10,1985:481-485.485.10PawlakZ.,DecisionTable13 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 generalization of 14 Mohamed Quafafou,-RST:a generalization of rough set theoryJ,Information Sciences,124,rough set theoryJ,Information Sciences,124,2000:301-316.2000:301-316.15 15 魏长华,魏长华,人类自然语言不确定性及粗集理论的表人类自然语言不确定性及粗集理论的表示示 JJ,计算机科学,计算机科学,Vol.24,No.5,1997:1-5.Vol.24,No.5,1997:1-5.16 16 苗夺谦,王珏,粗糙集理论中知识粗糙性与信息苗夺谦,王珏,粗糙集理论中知识粗糙性与信息熵关系的讨论熵关系的讨论 JJ,模式识别与人工智能,模式识别与人工智能,Vol.11,No.1,1998Vol.11,No.1,1998:34-4034-40。17 17 刘健勤,刘健勤,粗糙集理论及其最新进展粗糙集理论及其最新进展 JJ,计算技计算技术与自动化,术与自动化,Vol.17,No.1,1998:43-48.Vol.17,No.1,1998:43-48.13Y.Y.Yao,Acomparativest1、刘清,Rough集理论与Rough推理,科学出版社,2001.2、曾黄麟,粗集理论及其应用,重庆大学出版社,1998。3、张文修等,粗糙集理论与方法,科学出版社,2001.4、王国胤等,Rough集理论与知识获取,西安交通大学出版社,2001国内出版的参考书:国内出版的参考书:http:/www2.cs.uregina.ca/yyao/主要网站:主要网站:谢谢大家!谢谢大家!
展开阅读全文