高级人工智能第十一部分.ppt
《高级人工智能第十一部分.ppt》由会员分享,可在线阅读,更多相关《高级人工智能第十一部分.ppt(86页珍藏版)》请在三一办公上搜索。
1、2023/10/27,高级人工智能 史忠植,1,高级人工智能第十一章,史忠植 中国科学院计算技术研究所,粗 糙 集 Rough Set,2023/10/27,高级人工智能 史忠植,2,内容提要,一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统七、粒度计算简介,2023/10/27,高级人工智能 史忠植,3,一、概述,现实生活中有许多含糊现象并不能简单地用真、假值来表示如何表示和处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词,他把它归结到边界线上,也就是说在全域上存在一些个体既不能在其某个子集上
2、分类,也不能在该子集的补集上分类。,2023/10/27,高级人工智能 史忠植,4,模糊集,1965年,Zadeh提出了模糊集,不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念,但模糊集理论采用隶属度函数来处理模糊性,而基本的隶属度是凭经验或者由领域专家给出,所以具有相当的主观性。,2023/10/27,高级人工智能 史忠植,5,粗糙集的提出,20世纪80年代初,波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集(Rough Set)他把那些无法确认的个体都归属于边界线区域,而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述,完
3、全由数据决定,所以更有客观性。,2023/10/27,高级人工智能 史忠植,6,粗糙集的研究,粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来,许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究,使之在理论上日趋完善,特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。,2023/10/27,高级人工智能 史忠植,7,粗糙集的研究,1991年波兰Pawlak教授的第一本关于粗糙集的专著Rough Sets:Theoretical Aspects of Reasoning about Data 和1992
4、年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版,推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。,2023/10/27,高级人工智能 史忠植,8,研究现状分析,2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”,邀请了创始人Z.Pawlak教授做大会报告;2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆 第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005
5、年8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会(CRSSC2005)2006第六届中国粗糙集与软计算学术研讨会在 浙江师范大学,2023/10/27,高级人工智能 史忠植,9,研究现状分析,2007年粗糙集与软计算、Web智能、粒计算联合学术会议,山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议(CRSSC-CWI-CGrC2008),河南师范大学 中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学、上海大学,2023/10/27,高级人工
6、智能 史忠植,10,研究现状分析,曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社,1998刘清.Rough Set及Rough推理.北京:科学出版社,2001张文修等.Rough Set理论与方法.北京:科学出版社,2001王国胤.Rough Set理论与知识获取.西安:西安交通大学出版社,2001史忠植.知识发现.北京:清华大学出版社,2002苗夺谦/王国胤/刘清/林早阳/姚一 豫.粒计算-过去现在与展望.科学出版社,2007,2023/10/27,高级人工智能 史忠植,11,二、知识分类,基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。例如,在现实世界中关于环境的知识主
7、要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式,就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此,粗糙集理论假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物,比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起,这种特定部分称之为所讨论的全域或论域(universe)。对于全域及知识的特性并没有任何特别假设。事实上,知识构成了某一感兴趣领域中各种分类模式的一个族集(family),这个族集提供了关于现实的显事实,以及能够从这些显事实中推导出
8、隐事实的推理能力。,2023/10/27,高级人工智能 史忠植,12,二、知识分类,为数学处理方便起见,在下面的定义中用等价关系来代替分类。一个近似空间(approximate space)(或知识库)定义为一个关系系统(或二元组)K=(U,R)其中U(为空集)是一个被称为全域或论域(universe)的所有要讨论的个体的集合,R是U上等价关系的一个族集。,2023/10/27,高级人工智能 史忠植,13,二、知识分类,设PR,且P,P中所有等价关系的交集称为P上的一种不可区分关系(indiscernbility relation)(或称难区分关系),记作IND(P),即 xIND(p)=xR
9、 RP 注意,IND(P)也是等价关系且是唯一的。,2023/10/27,高级人工智能 史忠植,14,二、知识分类,给定近似空间K=(U,R),子集XU称为U上的一个概念(concept),形式上,空集也视为一个概念;非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P),称为基本知识(basic knowledge),相应的等价类称为基本概念(basic concept);特别地,若关系QR,则关系Q就称为初等知识(elementary knowledge),相应的等价类就称为初等概念(elementary concept)。一般用大写字母P,Q,R等表示一个关
10、系,用大写黑体字母P,Q,R等表示关系的族集;xR或R(x)表示关系R中包含元素xU的概念或等价类。为了简便起见,有时用P代替IND(P)。根据上述定义可知,概念即对象的集合,概念的族集(分类)就是U上的知识,U上分类的族集可以认为是U上的一个知识库,或说知识库即是分类方法的集合。,2023/10/27,高级人工智能 史忠植,15,二、知识分类,粗糙集理论与传统的集合理论有着相似之处,但是它们的出发点完全不同。传统集合论认为,一个集合完全是由其元素所决定,一个元素要么属于这个集合,要么不属于这个集合,即它的隶属函数X(x)0,1。模糊集合对此做了拓广,它给成员赋予一个隶属度,即X(x)0,1,
11、使得模糊集合能够处理一定的模糊和不确定数据,但是其模糊隶属度的确定往往具有人为因素,这给其应用带来了一定的不便。而且,传统集合论和模糊集合论都是把隶属关系作为原始概念来处理,集合的并和交就建立在其元素的隶属度max和min操作上,因此其隶属度必须事先给定(传统集合默认隶属度为1或0)。在粗糙集中,隶属关系不再是一个原始概念,因此无需人为给元素指定一个隶属度,从而避免了主观因素的影响。,2023/10/27,高级人工智能 史忠植,16,Information Systems/Tables,IS is a pair(U,A)U is a non-empty finite set of object
12、s.A is a non-empty finite set of attributes such that for every is called the value set of a.,Age LEMS,x 16-30 50 x2 16-30 0 x3 31-45 1-25x4 31-45 1-25x5 46-60 26-49x6 16-30 26-49x7 46-60 26-49,2023/10/27,高级人工智能 史忠植,17,Decision Systems/Tables,DS:is the decision attribute(instead of one we can consid
13、er more decision attributes).The elements of A are called the condition attributes.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2023/10/27,高级人工智能 史忠植,18,Issues in the Decision Table,相同或不可区分的对象可能被表示多次The same or indi
14、scernible objects may be represented several times.有些属性可能是多余的 Some of the attributes may be superfluous.,2023/10/27,高级人工智能 史忠植,19,不可区分性Indiscernibility,The equivalence relation A binary relation which is reflexive(xRx for any object x),symmetric(if xRy then yRx),and transitive(if xRy and yRz then xR
15、z).The equivalence class of an element consists of all objects such that xRy.,2023/10/27,高级人工智能 史忠植,20,不可区分性Indiscernibility(2),Let IS=(U,A)be an information system,then with any there is an associated equivalence relation:where is called the B-indiscernibility relation.If then objects x and x are i
16、ndiscernible from each other by attributes from B.The equivalence classes of the B-indiscernibility relation are denoted by,2023/10/27,高级人工智能 史忠植,21,不可区分性实例 Indiscernibility,The non-empty subsets of the condition attributes are Age,LEMS,and Age,LEMS.IND(Age)=x1,x2,x6,x3,x4,x5,x7IND(LEMS)=x1,x2,x3,x4
17、,x5,x6,x7IND(Age,LEMS)=x1,x2,x3,x4,x5,x7,x6.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2023/10/27,高级人工智能 史忠植,22,概念的边界,知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓的关于不精确的“边界”思想。著名哲学家Frege认为“概念必须有明确的边界。没有明确边界的概念,将对应于一个在周围没
18、有明确界线的区域”。粗糙集理论中的模糊性就是一种基于边界的概念,即一个不精确的概念具有模糊的不可被明确划分的边界。为刻画模糊性,每个不精确概念由一对称为上近似与下近似的精确概念来表示,它们可用隶属函数定义,2023/10/27,高级人工智能 史忠植,23,粗糙集的基本定义,知识的分类观点 粗糙集理论假定知识是一种对对象进行分类的能力。而知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起,这种特定部分称之为所讨论的全域或论域(universe)。为数学处理方便起见,在下面的定义中用等价关系来代替分类。,2023/10/27,高级人工智能 史忠植,24,粗糙集的基本定义,定义1 一个近
19、似空间(approximate space)(或知识库)定义为一个关系系统(或二元组)K=(U,R),其中U(为空集)是一个被称为全域或论域(universe)的所有要讨论的个体的集合,R是U上等价关系的一个族集。定义2 设PR,且P,P中所有等价关系的交集称为P上的一种不分明关系(indiscernbility relation)(或称不可区分关系),记作IND(P),2023/10/27,高级人工智能 史忠植,25,粗糙集的基本定义,定义3 给定近似空间K=(U,R),子集XU称为U上的一个概念(concept),形式上,空集也视为一个概念;非空子族集PR所产生的不分明关系IND(P)的所
20、有等价类关系的集合即U/IND(P),称为基本知识(basic knowledge),相应的等价类称为基本概念(basic concept);特别地,若关系QR,则关系Q就称为初等知识(elementary knowledge),相应的等价类就称为初等概念(elementary concept)。,2023/10/27,高级人工智能 史忠植,26,上近似、下近似和边界区域,定义5:X的下近似:R*(X)=x:(xU)(xRX)X的上近似:R*(X)=x:(xU)(xRX)X的边界区域:BNR(X)=R*(X)R*(X)若BNR(X),则集合X就是一个粗糙概念。下近似包含了所有使用知识R可确切分
21、类到X的元素,上近似则包含了所有那些可能是属于X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。POSR(X)=R*(X)称为集合X的R-正区域,NEGR(X)=UR*(X)称为集合X的R-反区域。,2023/10/27,高级人工智能 史忠植,27,Lower&Upper Approximations(2),Lower Approximation:,Upper Approximation:,上近似、下近似和边界区域,2023/10/27,高级人工智能 史忠植,28,新型的隶属关系,传统集合论中,一个元素的隶属函数X(x)0,1。而粗糙集理论中,X(x)0,1 定义4 设
22、XU且xU,集合X的粗糙隶属函数(rough membership function)定义为,其中R是不分明关系,R(x)=xR=y:(yU)(yRx),=1当且仅当xRX,0当且仅当xRX,=0当且仅当xRX=,2023/10/27,高级人工智能 史忠植,29,隶属关系,显然有 0,1。我们可以看到,这里的隶属关系是根据已有的分类知识客观计算出来的,可以被解释为一种条件概率,能够从全域上的个体加以计算,而不是主观给定的。,2023/10/27,高级人工智能 史忠植,30,集近似实例 Set Approximation,Let W=x|Walk(x)=yes.The decision clas
23、s,Walk,is rough since the boundary region is not empty.,Age LEMS Walk,x 16-30 50 yes x2 16-30 0 no x3 31-45 1-25 nox4 31-45 1-25 yesx5 46-60 26-49 nox6 16-30 26-49 yesx7 46-60 26-49 no,2023/10/27,高级人工智能 史忠植,31,集近似实例 Set Approximation(2),yes,yes/no,no,x1,x6,x3,x4,x2,x5,x7,AW,2023/10/27,高级人工智能 史忠植,32,
24、U,set,U/RR:subset of attributes,粗糙集近似图示,2023/10/27,高级人工智能 史忠植,33,Lower&Upper 近似(3),X1=u|Flu(u)=yes=u2,u3,u6,u7 RX1=u2,u3=u2,u3,u6,u7,u8,u5,X2=u|Flu(u)=no=u1,u4,u5,u8 RX2=u1,u4=u1,u4,u5,u8,u7,u6,The indiscernibility classes defined by R=Headache,Temp.are u1,u2,u3,u4,u5,u7,u6,u8.,2023/10/27,高级人工智能 史忠植
25、,34,Lower&Upper 近似(4),R=Headache,Temp.U/R=u1,u2,u3,u4,u5,u7,u6,u8X1=u|Flu(u)=yes=u2,u3,u6,u7X2=u|Flu(u)=no=u1,u4,u5,u8,RX1=u2,u3=u2,u3,u6,u7,u8,u5,RX2=u1,u4=u1,u4,u5,u8,u7,u6,u1,u4,u3,X1,X2,u5,u7,u2,u6,u8,2023/10/27,高级人工智能 史忠植,35,例1:设有一知识库K=U,p,q,r其中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,x8,x3,x6
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 人工智能 第十一 部分
链接地址:https://www.31ppt.com/p-6404413.html