高级人工智能十一章.pptx

创馈谁挚需潜杖次擂强道育咽橙容费何窄贰株锥钞鸯曹血淹雷伴忌抖苍瘫高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植1高级人工智能高级人工智能第十一章第十一章 史忠植史忠植 中国科学院计算技术研究所 粗粗 糙糙 集集 Rough SetRough Set 屁运命黄隧仅虹顶渴窍袖斥炉需益褪啮晴于雕惺馅躬恼猾奄侄攫壮拙狄迄高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植2内容提要内容提要一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统七、粒度计算简介兴汰凄唐尼愁陷受澈不明摩六贰盛贯的法毋彩同届溜狄峙持忙汪者疼拟拖高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植3一、一、概述概述 现实生活中有许多含糊现象并不能简单地用真、假值来表示如何表示和处理这些现象就成为一个研究领域。早在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词，他把它归结到边界线上，也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类。僚巳霖幽岗琶沏少休补锗俯山旦笆榨抉茎朵陈你掘哪几豹旭晌崎坟袭码捐高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植4模糊集模糊集 1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。氏奏阶俩柒味剂乒罪宾扫荔甲艺争愉节筏抠犹叔基屠嘛毖敦吞簇倡篱腆帝高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植5粗糙集的提出粗糙集的提出 20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集（Rough Set）他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完全由数据决定，所以更有客观性。肖俞兑优渍滚贤迭矗湃辖煮觅趾翻烷青碘陵诵砷券复匈质梳戒研并吩期佛高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植6粗糙集的研究粗糙集的研究 粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来，许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究，使之在理论上日趋完善，特别是由于20世纪80年代末和90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。淹姜剿趴剑息遂驶下肩楼榴臆壬黔栅晴肩鱼盒钥娇侦泄诀蔚忌侩蓖轰血痛高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植7粗糙集的研究粗糙集的研究 1991年波兰Pawlak教授的第一本关于粗糙集的专著Rough Sets：Theoretical Aspects of Reasoning about Data 和1992年R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入研究。1992年在波兰Kiekrz召开了第1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。崇六闽咯畴旬酞豫新策夸彤垦糖略薯钱钩掘问泥葱嵌躇拼游报涯凹讫庚稍高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植8研究现状分析研究现状分析2001年5月在重庆召开了“第1届中国Rough集与软计算学术研讨会”，邀请了创始人Z.Pawlak教授做大会报告；2002年10月在苏州第2届中国粗糙集与软计算学术研讨会2003年5月在重庆第3届中国粗糙集与软计算学术研讨会2004年10月中下旬在浙江舟山召开第4届中国粗糙集与软计算学术研讨会2005年8月1日至5日在鞍山科技大学召开第五届中国Rough集与软计算学术研讨会（CRSSC2005）2006第六届中国粗糙集与软计算学术研讨会在浙江师范大学蔗菏退卑骨她衙橡抢投铝丝间算纷遵翱鱼密央专忌券插讹窜竣淤佐担慰州高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植9研究现状分析研究现状分析2007年粗糙集与软计算、Web智能、粒计算联合学术会议,山西大学2008年第8届中国粗糙集与软计算学术会议、第2届中国Web智能学术研讨会、第2届中国粒计算学术研讨会联合学术会议（CRSSC-CWI-CGrC2008）,河南师范大学 中科院计算所、中科院自动化所、重庆邮电学院、南昌大学、西安交通大学、山西大学、合肥工业大学、北京工业大学、上海大学促桐微滔衰析拂昔濒玉阿参榆咬克葛因嘛陈逊捏犀走拥胸蚀她雪鸥脯遁锤高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植10研究现状分析研究现状分析曾黄麟.粗集理论及其应用(修订版).重庆:重庆大学出版社,1998刘清.RoughSet及Rough推理.北京:科学出版社,2001张文修等.RoughSet理论与方法.北京:科学出版社,2001王国胤.RoughSet理论与知识获取.西安:西安交通大学出版社,2001史忠植.知识发现.北京:清华大学出版社,2002苗夺谦苗夺谦/王国胤王国胤/刘清刘清/林早阳林早阳/姚一姚一豫.粒计算-过去现在与展望.科学出版社,2007拷岛矿赐憋阁恿贯币句瓜副青渣光佑仁乳鼠贱备署挎池埂乖鸦吊锄虽汁估高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植11二、二、知识分类知识分类基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。例如，在现实世界中关于环境的知识主要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式，就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此，粗糙集理论假定知识是一种对对象进行分类的能力。这里的“对象”是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域全域或论域论域(universeuniverse)。对于全域及知识的特性并没有任何特别假设。事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集(family)，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。篱淄篓钧螟鼓焙摊竖怕侣凝两逃妙鞭脆帮墩憨炉堤闲其羹卷馅乏湖脖撅罗高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植12二、二、知识分类知识分类 为数学处理方便起见，在下面的定义中用等价关系来代替分类。一个近近似似空空间间(approximate space)（或知知识识库库）定义为一个关系系统（或二元组）K K=(U,R R)其中U（为空集）是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R R是U上等价关系的一个族集。宰郝呼砖躺咏袱根威夹麓倚铭瓢抹洼讼瞥勾吕盎疵腕讯汐聊狞糕惕医巾芹高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植13二、二、知识分类知识分类 设P PR R，且P P，P P中所有等价关系的交集称为P P上的一种不可区分关系(indiscernbility relation)（或称难区分关系），记作IND(P P)，即 xIND(p)=xR RP 注意，IND(P P)也是等价关系且是唯一的。谭射芒桃劈帽承污蠢科陕淬获挛疆安讼饰宫烷厉言茫堑锥服帘桌戴鳞诺放高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植14二、二、知识分类知识分类 给定近似空间K K=(U,R R)，子集XU称为U上的一个概念概念(concept)，形式上，空集也视为一个概念；非空子族集P PR R所产生的不分明关系IND(P P)的所有等价类关系的集合即U/IND(P P)，称为基本知识基本知识(basic knowledge)，相应的等价类称为基本概念基本概念(basic concept)；特别地，若关系QR R，则关系Q就称为初等知识初等知识(elementary knowledge)，相应的等价类就称为初等概念初等概念(elementary concept)。一般用大写字母P,Q,R等表示一个关系，用大写黑体字母P P,Q Q,R R等表示关系的族集；xR或R(x)表示关系R中包含元素xU的概念或等价类。为了简便起见，有时用P P代替IND(P P)。根据上述定义可知，概念即对象的集合，概念的族集（分类）就是U上的知识，U上分类的族集可以认为是U上的一个知识库，或说知识库即是分类方法的集合。纸泌鸦君琴奏闹构汗锚闸我慕纠双共褪潜掐俱掖匡泛言税净通龙批从预晃高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植15二、二、知识分类知识分类 粗糙集理论与传统的集合理论有着相似之处，但是它们的粗糙集理论与传统的集合理论有着相似之处，但是它们的出发点完全不同。传统集合论认为，一个集合完全是由其元出发点完全不同。传统集合论认为，一个集合完全是由其元素所决定，一个元素要么属于这个集合，要么不属于这个集素所决定，一个元素要么属于这个集合，要么不属于这个集合，即它的隶属函数合，即它的隶属函数 X X(x x)0,10,1。模糊集合对此做了拓广，。模糊集合对此做了拓广，它给成员赋予一个隶属度，即它给成员赋予一个隶属度，即 X X(x x)0,10,1，使得模糊集合，使得模糊集合能够处理一定的模糊和不确定数据，但是其模糊隶属度的确能够处理一定的模糊和不确定数据，但是其模糊隶属度的确定往往具有人为因素，这给其应用带来了一定的不便。而且，定往往具有人为因素，这给其应用带来了一定的不便。而且，传统集合论和模糊集合论都是把隶属关系作为原始概念来处传统集合论和模糊集合论都是把隶属关系作为原始概念来处理，集合的并和交就建立在其元素的隶属度理，集合的并和交就建立在其元素的隶属度maxmax和和minmin操作上，操作上，因此其隶属度必须事先给定（传统集合默认隶属度为因此其隶属度必须事先给定（传统集合默认隶属度为1 1或或0 0）。）。在粗糙集中，隶属关系不再是一个原始概念，因此无需人为在粗糙集中，隶属关系不再是一个原始概念，因此无需人为给元素指定一个隶属度，从而避免了主观因素的影响。给元素指定一个隶属度，从而避免了主观因素的影响。卷吱爪毯与告洒椒马梢晰罗踪荣语巷增履荤欺漏砾意架闰搏块腿揪陈莲骏高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植16Information Systems/TableslIS is a pair(U,A)lU is a non-empty finite set of objects.lA is a non-empty finite set of attributes such that for every l is called the value set of a.AgeLEMSx16-3050 x216-300 x331-451-25x431-451-25x546-6026-49x616-3026-49x746-6026-49锅羊惭趾录取降牟颤押晚江爽名刁沫酶罕蔷滑球绎扩佐免跃谤糖蠕辐阿底高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植17Decision Systems/TableslDS:l is the decision attribute(instead of one we can consider more decision attributes).lThe elements of A are called the condition attributes.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no衔抹至晴算黍窒特丛率植凑篷启盗簇突冰趋庄窗冉厚陋百刑漆荣均篇毋攘高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植18Issues in the Decision Tablel相同或不可区分的对象可能被表示多次相同或不可区分的对象可能被表示多次The same or indiscernible objects may be represented several times.l有些属性可能是多余的 Some of the attributes may be superfluous.权滇妈按平诫祈秽捞乙跑饱噬禽爵科呕瞬涕筛荣愿绢痹鼠探血悬暴埃仿燕高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植19不可区分性不可区分性IndiscernibilitylThe 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 xRz).lThe equivalence class of an element consists of all objects such that xRy.曾夯椽周雄狰碗孙浚滋珐剖落帝哇卜味饺畦猎鸳么扼构啦莎苛妙卷衅掷映高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植20不可区分性不可区分性Indiscernibility(2)lLet IS=(U,A)be an information system,then with any there is an associated equivalence relation:where is called the B-indiscernibility relation.lIf then objects x and x are indiscernible from each other by attributes from B.lThe equivalence classes of the B-indiscernibility relation are denoted by 漆缎鹿很壬谦让毁敏刚昨仪托茶郑亲坊饰替协浴迄文羹糯渊纯份需晰沸手高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植21不可区分性实例不可区分性实例 IndiscernibilitylThe non-empty subsets of the condition attributes are Age,LEMS,and Age,LEMS.lIND(Age)=x1,x2,x6,x3,x4,x5,x7lIND(LEMS)=x1,x2,x3,x4,x5,x6,x7lIND(Age,LEMS)=x1,x2,x3,x4,x5,x7,x6.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no选湛屉渔敞绳诀陕户规葱买尝竖竹涨近抽刘绘急祝食货辞虱圾吕纽光爹味高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植22概念的边界概念的边界 知识的粒度性是造成使用已有知识不能精确地表示知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓的关于不精确的某些概念的原因。这就产生了所谓的关于不精确的“边界边界”思想。著名哲学家思想。著名哲学家FregeFrege认为认为“概念必须概念必须有明确的边界。没有明确边界的概念，将对应于一有明确的边界。没有明确边界的概念，将对应于一个在周围没有明确界线的区域个在周围没有明确界线的区域”。粗糙集理论中的。粗糙集理论中的模糊性就是一种基于边界的概念，即一个不精确的模糊性就是一种基于边界的概念，即一个不精确的概念具有模糊的不可被明确划分的边界。概念具有模糊的不可被明确划分的边界。为刻画模为刻画模糊性，每个不精确概念由一对称为上近似与下近似糊性，每个不精确概念由一对称为上近似与下近似的精确概念来表示，它们可用隶属函数定义的精确概念来表示，它们可用隶属函数定义焰殖强棱欣橙效连凡卖舵噶操牟酬厅豁批脆翰玖伸厚捏骨歌冒药炮谍蟹娶高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植23粗糙集的基本定义粗糙集的基本定义知识的分类观点 粗糙集理论假定知识是一种对对象进行分类的能力。而知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域全域或论域论域(universeuniverse)。为数学处理方便起见，在下面的定义中用等价关系来代替分类。搐普渝他擒躲嵌漂凌曳食闲拣阀茧挂敝空视差砒悠袁详颓扑灯峪功工刨孰高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植24粗糙集的基本定义粗糙集的基本定义定定义义1 1 一个近近似似空空间间(approximate space)(或知知识库识库)定义为一个关系系统(或二元组)K K=(U,R R)，其中U(为空集)是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R R是U上等价关系的一个族集。定定义义2 2 设P PR R，且P P，P P中所有等价关系的交集称为P P上的一种不分明关系(indiscernbility relation)（或称不可区分关系），记作IND(P P)扣剩隐敏蹋体慌遣财紧闺儡怂稼唬圾邯敖妈真赃酮税沈楼桩洪瀑福狡梭揉高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植25粗糙集的基本定义粗糙集的基本定义 定定义义3 3 给定近似空间K K=(U,R R)，子集XU称为U上的一个概概念念(concept)，形式上，空集也视为一个概念；非空子族集P PR R所产生的不分明关系IND(P P)的所有等价类关系的集合即U/IND(P P)，称为基基本本知知识识(basic knowledge)，相应的等价类称为基基本本概概念念(basic concept)；特别地，若关系QR R，则 关 系 Q就 称 为 初初 等等 知知 识识(elementary knowledge)，相应的等价类就称为初初等等概概念念(elementary concept)。伍鲁炕图沦肿苯昭兴捣杯市牌橙酪饱拨进躺贸坚诉旋砌愁欠兔邵贷庶方淫高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植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可确切分类到X的元素，上近似则包含了所有那些可能是属于X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。POSR(X)=R*(X)称为集合X的R-正区域正区域，NEGR(X)=UR*(X)称为集合X的R-反区域反区域。睁其禹彻构晴畔喊其绵尽庇湍狠便愈琼右趟故膀武斯腑婆送蛆厨英孜扑挂高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植27Lower&UpperApproximations(2)Lower Approximation:Upper Approximation:上近似、下近似和边界区域上近似、下近似和边界区域褪甘葫穴蛤皋疵匆版聚圭少假种营价利亿益棠聘棠锚乡潮根沾巍腺缔只藩高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植28新型的隶属关系新型的隶属关系 传统集合论中，一个元素的隶属函数X(x)0,1。而粗糙集理论中，X(x)0,1 定定义义4 4 设XU且xU,集合X的粗粗糙糙隶隶属属函函数数(rough membership function)定义为 其中R是不分明关系，R(x)=xR=y:(yU)(yRx)=1当且仅当xRX 0当且仅当xRX=0当且仅当xRX=器凝症信柱悦漫苏驯截侦烩铃戌涡啊墟大伦炸俺混梁丢邯怠趾扮阮品乏忍高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植29隶属关系隶属关系显然有显然有 0,10,1。我们可以看到，这里的隶属关系。我们可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的，可以被解是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率，能够从全域上的个体加以计算，释为一种条件概率，能够从全域上的个体加以计算，而不是主观给定的。而不是主观给定的。芭唁聋珍海尺叛霞件注梧廉伐褒蚀防塘胀亿忿樟颐帅绎年笔得豢轴牌怔堡高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植30集近似实例集近似实例 Set ApproximationlLet W=x|Walk(x)=yes.lThe decision class,Walk,is rough since the boundary region is not empty.AgeLEMSWalkx16-3050yesx216-300nox331-451-25nox431-451-25yesx546-6026-49nox616-3026-49yesx746-6026-49no捣逝序耘舷励纳肤顽颜缝灯蔫古守桥黎由鹏撤暮倦挠蝎伊峙吹崩椿姚梢滩高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植31集近似实例集近似实例 Set Approximation(2)yesyes/nonox1,x6x3,x4x2,x5,x7AW婴溺盆攫守谗吕育宅目却徊驮几阿赛瓢油哀偏撰绦冬雨眶囱芭漆卫炳联修高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植32UsetU/RR:subset of attributes粗糙集近似图示粗糙集近似图示专炯燎煮魄叫拈摆视噎渊职谴锑敝属沪抹呜浸苑仲拨俘既仅光析闯谭思瑶高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植33Lower&Upper 近似近似 (3)X1=u|Flu(u)=yes=u2,u3,u6,u7RX1=u2,u3=u2,u3,u6,u7,u8,u5X2=u|Flu(u)=no=u1,u4,u5,u8RX2=u1,u4 =u1,u4,u5,u8,u7,u6TheindiscernibilityclassesdefinedbyR=Headache,Temp.areu1,u2,u3,u4,u5,u7,u6,u8.谱汞南驶褒昌焙创械勉用顺葛懈千兰糙婿臆关镍喳蛾忠鸣宴形赋鹰者巳塌高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植34Lower&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,u8RX1=u2,u3=u2,u3,u6,u7,u8,u5RX2=u1,u4 =u1,u4,u5,u8,u7,u6u1u4u3X1X2u5u7u2u6u8畦陨麓颈拄跟铃比蛹无罐弥扣办俗渊裹科矣不沁削汉桶紫吓胜眺涣憋吩闷高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植35例例1 1：设有一知识库K=U,p,q,r其中U=x1,x2,x3,x4,x5,x6,x7,x8且U/p=x1,x4,x5,x2,x8,x3,x6,x7U/q=x1,x3,x5,x6,x2,x4,x7,x8 U/r=x1,x5,x6,x2,x7,x8,x3,x4 则x1p=x1,x4,x5x1q=x1,x3,x5。若P=p,q,r则IND(P)=x1,x5,x2,x8,x3,x4,x6,x7 对于U上的子集X1=x1,x4,x7可得到P*X1=x4x7=x4,x7P*X1=x1,x5x4x7=x1,x4,x5,x7Lower&Upper 近似近似(5)癌昏规氢樟谩蔗秀袄讯默姿躯诚捧绰榷饱晤掏骏疟傻鳞非丁格郁搭痘嫂叮高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植36近似度近似度Accuracy of Approximation where|X|denotes the cardinality of Obviously If X is crisp with respect to B.If X is rough with respect to B.苫习录狂甲拂拢陶馈轩冕浇虏覆寅肤洗绅柳做藤玄畴碘旬题粟塞胀嘶渤琢高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植37近似性质近似性质Properties of Approximationsimpliesand脂掏睫屏肝仓抑极玉邪弦链禾囱枚长杜债坪辛稚侗之便兵掷涂鞘讼阁钮妖高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植38近似性质近似性质Properties of Approximations(2)where-XdenotesU-X.浚牢莎期碧访竟宫狼轮洪拣舷璃冰绪遣嚣驼臭柯换刀呈邯颅腔腾淘汰涛譬高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植39三、三、知识的约简知识的约简一般约简 定义定义6 6 设R R是等价关系的一个族集，且设RR R。若IND(R R)=IND(R RR)，则称关系R在族集R R之中是可省可省的(dispensable)否则就是不可省不可省的。若族集R R中的每个关系R都是不可省的则称族集R R是独立的独立的(independent)否则就是依赖的依赖的或非独立非独立的。定义定义7 7 若Q QP P是独立的并且IND(Q Q)=IND(P P)则称Q Q是关系族集P P的一个约简约简(reduct)。在族集P P中所有不可省的关系的集合称为P P的核核(core)以CORE(P P)来表示。显然，族集P P有多个约简（约简的不唯一性）。定理定理1 1 族集P P的核等于P P的所有约简的交集。即CORE(P P)=RED(P P)拒躲儒芦氓氏箍淹董齿鼻寇铁殊落釉筛涧承娘罩仔毁苏费救抠名河综茶书高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植40例例2 2：取前面的例1若P=p,q,r则IND(P)=x1,x5,x2,x8,x3,x4,x6,x7IND(P-p)=x1,x5,x2,x7,x8,x3,x4,x6IND(P)所以p是不可省的同理可得q、r是可省的。这样由p,q,r三个等价关系组成的集合和p,q、p,r定义了相同的不分明关系。又IND(p,q)IND(p)IND(pq)IND(q)则p,q和p,r就是P的约简而且p是P的核也就是说p是绝对不能省的 三、三、知识的约简知识的约简构乖泊必芳舍仲萝溜辊鲜拣拭默咳像寝双斤儒哩阻帮掌旱洽迪轨张逾琐搁高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植41相对约简相对约简定义定义8 8 设P P和Q Q是全域U上的等价关系的族集，所谓族集Q Q的P-P-正区域正区域(P-positive region of Q Q)，记作POSP P(Q Q)=P P*(X)族集Q Q的P-P-正区域正区域是全域U的所有那些使用分类U/P P所表达的知识，能够正确地分类于U/Q Q的等价类之中的对象的集合。定义定义9 9 设P P和Q Q是全域U上的等价关系的族集，RP P。若POSIND(P P)(IND(Q Q)=POSIND(P P-R)(IND(Q Q)则称关系R在族集P P中是Q-Q-可可省省的的否则称为Q-Q-不不可可省省的的如果在族集P P中的每个关系R都是Q Q-不可省的则称P P关于Q Q是独独立立的的否则就称为是依赖的依赖的。冬尹族枯确烫鲤粳邯您咎钉文姓鸟伪缘刊湾乔点挟樱徘厄傈广泪疹纲诸佃高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植42相对约简相对约简定义定义10 SP称为P的Q-约简约简(Q-reduct)当且仅当S是P的Q-独立的子族集且POSS(Q)=POSP(Q)；族集P中的所有Q-不可省的初等关系的集合称为族集P的Q-核核(Q-core)记作COREQ(P)。下面的定理是定理定理1的拓广。定理定理2 族集P的Q-核等于族集P的所有Q-约简的交集。即COREQ(P)=REDQ(P)其中REDQ(P)是族集P的所有Q-约简的族集。乱糯麓恳末羞胜垫亚哭岭盏嗅个狞陆钎拭美拯卖炉渔摈宋斡镣监抢块滋霸高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植43知识的依赖性知识的依赖性知识的依赖性可形式定义如下：定义定义11 设K=(U,R)是一个近似空间，P,QR。1)知识Q依赖于依赖于知识P或知识P可推导出可推导出知识Q，当且仅当IND(P)IND(Q)记作PQ；2)知识P和知识Q是等价的等价的当且仅当PQ且QP即IND(P)=IND(Q)记作P=Q，明显地，P=Q当且仅当IND(P)=IND(Q)；3)知识P和知识Q是独立的独立的，当且仅当PQ且QP均不成立，记作PQ。裳弛鹃合虑氛介涧始福拂耀妄席瞻铸阴穆嗜器够玻昏筋拙淬糊俱庶幽转平高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植44知识的依赖性知识的依赖性依赖性也可以是部分成立的也就是从知识P能推导出知识Q的一部分知识，或者说知识Q只有一部分依赖于知识P的。部分依赖性（部分可推导性）可以由知识的正区域来定义。现在我们形式地定义部分依赖性。定义定义12 设K=(U,R)是一个知识库P,QR我们称知识知识Q以依赖以依赖度度k(0 k1)依赖于知识依赖于知识P记作PkQ当且仅当k=P(Q)=card(POSP(Q)/card(U)(6.8)(1)若k=1则称知识Q完全依赖于完全依赖于知识P，P1Q也记成PQ；(2)若0k1则称知识Q部分依赖于部分依赖于知识P；(3)若k=0则称知识Q完全独立于完全独立于与知识P。链耸狐婪图绪杨腰生囤补腆彭酸疟宅烷千蝉疲镇贮肥绎调亭争罕庙邮轰讨高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植45四、四、决策表的约简决策表的约简 决策表 决策表是一类特殊而重要的知识表达系统，它指当满足某些条件时，决策（行为）应当怎样进行。多数决策问题都可以用决策表形式来表示，这一工具在决策应用中起着重要的作用。决策表可以定义如下：S=(U,A)为一信息系统，且C,DA是两个属性子集，分别称为条件属性和决策属性，且CD=A，CD=，则该信息系统称为决策表，记作T=(U,A,C,D)或简称CD决策表。关系IND(C)和关系IND(D)的等价类分别称为条件类和决策类。踞法硅早凯瞬诲双镇炮留逢那聘碍偷肚认宏桥包薯骇娱搓们订低钠骑忿胃高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植46身高性别视力录取e1高男差否e2高女一般是e3高男好是e4矮男差否e5矮女一般是e6矮男好是表1一决策表身高、性别、视力为条件属性，录取为决策属性四、四、决策表的约简决策表的约简钠载翱匪汝儡窃滦牛似评抑捧洋泪夷虽巷抗晶休秃了硼逞谆叔直帕勃戮兵高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植47决策规则决策规则决策表中的每一行对应诸如形式的决策规则，和分别称为决策规则的前驱和后继。当决策表S中决策规则为真时，我们说该决策规则是S中一致的，否则说该决策规则是S中不一致的。若决策规则是S中一致的，相同的前驱必导致相同的后继；但同一种后继不一定必需是同一前驱产生的。如表1第一行对应决策规则：身高(高)性别(男)视力(差)录取(否)埔铅伊崎抿输涂挑衍镇瘦酿割帽刻惹貌盒曳凛过索咀窟瘴什齿啮租遥涯浚高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植48决策表的一致性决策表的一致性命题命题1 1当且仅当 CD，决策表T=(U,A,C,D)是一致的。由命题1，很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于1时，我们说决策表是一致的，否则不一致。址鬼糟姥兜冀弗期羽肢令砚信卡哭迢口备郎副天讣菇衙傀疵诧钞吭坝祭葱高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植49决策表的分解决策表的分解 命题命题2 2每个决策表T=(U,A,C,D)都可以唯一分解为两个决策表T1=(U1,A,C,D)和T2=(U2,A,C,D)，这样使得表T1中C1D和T2中C0D。这 里U1=POSC(D)，U2=BNC(X)，XU|IND(D)。由命题2可见，假设我们已计算出条件属性的依赖度，若表的结果不一致，即依赖度小于1，则由命题2可以将表分解成两个子表：其中一个表完全不一致，依赖度为0；另一个表则完全一致，依赖度为1。当然，只有依赖度大于0且不等于1时，这一分解才能进行。刻濒闯野喊忍孤乃撵档衫拨画嘴哥嘎盖领薄肾岳怠眠巩荧寄囊去利叁涪昭高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植50表2不一致决策表 a、b、c为条件属性，d、e为决策属性 1、5产生不一致Ua b c d e123456781022001112200111102210201220112111201101决策表的分解决策表的分解眨拄诬醇授泅亲胆尽霄陶铁钨互腹窍阮狡棉菜棱嗓单曲更屯沫姑肌幢渐城高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植51表3完全一致的决策表Ua b c d e346720011110222201121112表4完全不一致的决策表Ua b c d e125810220011121020101101决策表的分解决策表的分解巩库疏直赡烟庆涯奶棘太剁疆征噬芯友障戌质隆款笔冀诅伪悉棘宗拘肖某高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植52一致决策表的约简一致决策表的约简在我们制定决策时是否需要全部的条件属性，能否进行决策表的约简。约简后的决策表具有与约简前的决策表相同的功能，但是约简后的决策表具有更少的条件属性。一致决策表的约简步骤如下：(1)对决策表进行条件属性的约简，即从决策表中消去某一列；(主要研究点)(2)消去重复的行；(3)消去每一决策规则中属性的冗余值。拈尘月悔秆裸裂杨阔冶验泰荔耳征币佣桓蛙闽拯雄币救僻贺玻斟薄婴防始高级人工智能十一章高级人工智能十一章2024/10/8 周二高级人工智能 史忠植53条件属性的约简条件属性的约简A.Skowron提出了分明矩阵，使核与约简等概念的计算较为简单，主要思想：设S=(U,A)为一个知识表示系统，其中U=x1,x2,xn，xi为所讨论的个体，i=1,2,n，A=a1,a2,am，aj为个体所具有的属性，j=1,2,m。知识表达系统S的分明矩阵M(S)=cijnn，其中矩阵项定义如下：cij=aA：a(xi)a(xj)，i,j=1,2,n因此cij是个体xi与xj有区别的所有属性的集合明汛缸酬声桂知濒溺框墒吗恢稿蜕藤夹惮税羹滋宅烯晰症攀针丧漫暂韭背高级人工智能十一章高级人工智能十一章20