（计算机应用技术专业论文）基于可拓规则和案例推理的混合专家系统.pdf

摘要 摘要 可拓学是一门新兴的用于解决不相容问题的学科，它在人工智能领域的成功 应用给该领域的发展带来了希望。可拓逻辑给专家系统提供了一种新的数学工具， 使知识表示和推理方法更接近人类的思维方式。基于案例的推理也是最新引人关 注的推理方法之一。本论文将可拓逻辑运用到专家系统的知识表示和推理机设计 上，提出了一种新的专家系统的推理机模型可拓推理机。针对单一推理方式 的不足，本文提出将可拓规则推理与基于案例的推理结合起来，借助强大的数据 库支持，设计出了一种新的混合专家系统基于可拓规则和案例推理的混合专 家系统，并将这种混合专家系统应用到c & c 0 8 数字程控交换机的故障处理中。初 步试用表明，这种新的混合专家系统不仅合理可行，而且实用高效。 关键词：可拓逻辑可拓规则案例推理混合专家系统程控交换 a b s t f a c t a b s t i 丑c t e x t c n i 潞i san o v e ls u b j e c ti n l v i n gn 叩伽p a t i b l ep r o b l e m s ，姐di 协a p p l i t i j na r t i 丘d a lj n t e u i g e n c cg i v 鼯ag r e 砒w i s ht od c v e l o p m 姐to fa r t i 6 c i a li n t c u i g e n c e e x t c 璐i l o g i cp r o v i d 龉an c wm a u 蛐a t i c a l 啪lf 町b u i l d i 】唱懿p c ns y s t e ma n d m a k c s r e i m s e n t a t i o fh o w l e d g ca n dm c n l o do f 佗a s 衄i n gs i m i l 盯t 0h 岫翘st h 鼬g m 蛐e f c 蠲c - b a s e d 亿a n i n gi s eo ft h eh o n e s t 陀勰o n i n ga p p r o a c h e sf b c i l s e di nl a s t 出煳d e ht h i st h e s i s ，e x t e n s i o nl o g i ci su s c di n p r e s e n t a t i o no fe x p c r tb o w l e d g c 锄d d 鼯i g n o f”弱伽_ i n gm a c h 沁， 柚da 艇i v dm o d c lo fa s o n i n gm 飙：h i n ei s p m p 0 d ，n a m c d 笛强t e 璐i o nr c 勰d n i n gm a c h j n c 1 bm a k c 印f o rd i s a d v 椭g 龉o f s i n g l cr c 踟n i n gm e t h o d ，a p p r c h0 fe x t e 衄如咀m l c a n i n gi s 姗b i n c dw i u l c a - b 鹞c d 弱伽_ i n gm e t h o d ，弱t od c s i g na 们v c lh y 晡de x p t i ns y s t c m w i t h d a t a b a t h eh 州dc x p c ns y s t c mi s 惦c df o f 臼u l tp m c c s s i n go fc & c d 8d i g i t a l p r o g 蛐c h d u c ds w i t c h ，柚dt h et c s tr 鹤u l ts h o 、si ti s 陀a 蚰b l e 觚dp r t i c 曲l c k e y w o r d ：e x t e n s i 蛐b g i ce x k 雎i 帆确山c a s e b a s e d i n g 丑 y b r me x 雕r ts y s t 哪p i 嘲期mc 佃咖h e ds w i t c h 声明 创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：垂么缘熔日期型兰：2 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 “果密的论文在解密后遵守此规定) 第一章绪论 第一章绪论 1 1 专家系统及其发展 专家系统( e x p e r ts y s t e m ，e s ) 是人工智能中最活跃、成效最多的领域，广泛 应用于医疗诊断、地质勘探、石油化工、军事、文化教育等领域“1 。它是一个含有 领域专家水平的知识与经验的智能计算机程序系统，具备人类专家的知识和解决 问题的能力“1 。它应用人工智能技术、模拟人类专家解决问题时的思维过程，来求 解领域内的各种问题，达到或接近专家的水平。与通用问题求解程序系统不同， 专家系统并不试图发现强有力的和通用的问题求解方法，它把研究范围缩小在一 个特定的专业领域中。人类专家拥有解决自己专业领域问题的大量专门知识，包 括各种有用的诀窍和经验，专家系统实际上就是在计算机上实现的这种领域专家 的模仿物。 1 9 6 5 年，斯坦福大学教授费根鲍姆开创了基于知识的专家系统这一人工智能 研究的新领域“1 。在费根鲍姆的主持下，第一个专家系统d e n d r a l 系统于1 9 6 5 年 在斯坦福大学开始研究，并于1 9 6 8 年研制成功。该系统能根据质谱仪数据推断未 知有机化合物的分子结构。它是一个启发式系统，具有从化学专家那儿获得的关 于质谱测定法的知识，把它结合到控制搜索的规则中，能迅速消去不可能为真的 结构，它甚至可以找出那些人类专家往往会漏掉的候选结构。这项工作使人们看 到，在某些专门的科学领域里，以知识为基础的一个计算机程序完全可能起到这 个领域里的人类专家的作用。 1 9 7 2 年，s t a n f o r d 大学开发出了传染病诊断系统m 1 c i n ，s t a n f o r d 研究院开 发出了矿床探测专家系统p r o s p e c t o r ，法国c o l m e r a u e r 与r o u s s e l 开发了逻辑 程序语言p r o l o g 。1 9 7 4 年，卡内基美隆大学开发了人工智能与专家系统专用语 言0 p s 。1 9 7 5 年，m i n s k y 提出框架知识表示法。 1 9 7 8 年，卡内基一美隆大学和d e c 公司合作开发r l ( 又称x c o n ) ，用来依据 客户需求，架构适当的计算机系统。1 9 7 9 年，f o r g y 提出r e t e 算法，提高 p r o d u c t i o ns y s t e m 的法则匹配速度。1 9 8 0 年，l i s p 机器开始生产问世。1 9 8 2 年，日本政府宣布开发第五代计算机，以p r o l o g 作为核心语言。1 9 8 3 年， i n t e l l i c o r p 公司推出k e e ( 结合多样知识表现与推论方法的专家系统建构工 具) ，随后大量的专家系统构建工具相继问世。1 9 8 4 年，欧洲共同市场订定欧洲信 息技术研究发展策略计划。1 9 8 5 年，n a s a 开发出c l i p s 专家系统工具。1 9 8 8 年， g a l l a n t 提出以类神经网络为基础的专家系统架构。1 9 8 9 年，日本宣布人类领域 科学计划( 第六代计算机计划) ，希望藉由类神经网络突破人工智能的许多瓶颈。 2 基于可拓规则和案例推理的混合专家系统 1 2 产生式规则专家系统的不足 传统的专家系统是基于产生式规则的专家系统，它是基于经典二值逻辑的。 由于二值逻辑本身在知识表示方面的局限性，尤其是在不确定性方面的缺陷，使 得产生式专家系统在实际应用中存在很多不足： ( 1 ) 获取专家知识困难。这一点成为开发实用专家系统的瓶颈。知识和推理 是专家系统的核心，在构建专家系统的工程中，知识工程师要从繁杂的专门领域 经验和知识中提取出大量能够用于推理的规则来，这项工作非常繁重，并且很难 完善。 ( 2 ) 推理结果的解释困难。由于推理过程对客户来说是封闭的，专家系统展示 给客户的仅是结果，而并不能提供合情合理的对问题的解释。 ( 3 ) 处理大型复杂问题的能力差。在解决复杂问题时，求解问题状态空间较 大，操作数目多，操作序列会出现空前膨胀，导致组合爆炸的危险。 ( 4 ) 处理不确定性问题能力差。在生产实践中人类专家的知识往往是不确定 的，即模糊的，这使得基于二值逻辑的产生式专家系统在处理这些问题时效果不 理想。 ( 5 ) 缺乏自学习能力。所有的知识都是由知识工程师提取然后放到系统当中， 对于新的知识，系统并不能自动学习。因此，传统产生式规则专家系统不能自我 完善、发展和创新。 ( 6 ) 推理方法单一。和人类专家不同，产生式规则专家系统的推理方式是固 定的，它不会根据问题的不同而变换推理方式，致使思维僵化，智能化程度不高。 1 3 现代专家系统 随着模糊数学、人工神经网络、机器学习等学科的发展及其在人工智能领域 的应用，出现了多种多样的新的专家系统。为了区别于传统的产生式规则专家系 统，本文称之为现代专家系统。根据知识表示和推理方式的不同，现代专家系统 可分为模糊专家系统、基于神经网络的专家系统、模糊神经专家系统、基于机器 学习的专家系统等。 模糊专家系统用模糊数学的方法解决知识的不确定性表示问题。这种专家系 统具有较强的模糊问题处理能力，能够适应知识的复杂性和模糊性，适用于解决 特定领域的问题。 基于神经网络的专家系统有两种形式：一种是使用神经网络来构造专家系统， 变基于符号的推理为基于数字运算的推理，提高系统效率，解决自学习问题；另 一种是把神经网络作为知识源的表示和处理模式，并与其它推理机制相融合，实 第一章绪论3 现多模式推理。基于神经网络的专家系统实现知识表示、存储和推理三者融为一 体，在知识获取、并行推理和自适应学习等方面显示出明显的优越性，在一定程 度上克服了产生式专家系统存在的知识获取困难、推理速度慢等问题。 将模糊数学和人工神经网络的方法相融合，出现了模糊神经专家系统。这种 专家系统兼具二者之长，既能表示不确定性知识，又有自学习能力。 基于机器学习的专家系统是机器学习方法在专家系统中的应用，很好的解决 了知识获取和规则提取困难的问题。机器学习方法使专家系统具有了一定的学习 能力，其智能化程度大大提高。现在对该领域的研究，已经成为一个热点。 1 4 基于可拓规则和案例推理的混合专家系统 可拓学是由中国学者蔡文教授创立的一门新学科。经过二十多年的发展，已 经在理论上日渐成熟，现在被广泛应用到产品设计、市场拓展、智能控制等各个 领域。可拓学的基元概念、可拓集合以及可拓推理的思想，为专家系统中的知识 表示、推理机设计提供了一种新的思路。 基于案例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 技术最先是由美国耶鲁大学 r o g e rs c h 卸k 教授在他的论著d y n 锄i cm e 啪r y ) 中提出的叫，之后逐步推广到 机械c a d 、医疗卫生、企业管理、军事等领域，并得到了成功的应用。c b r 是一种 基于经验知识进行推理的人工智能技术，它是用案例来表达知识并把问题求解和 学习相融合的一种推理方法，它强调人在解决新问题时，常常回忆起过去积累下 来的类似情况的处理，并通过适当修改过去类似情况处理的方法来解决新问题。 从认识思维的角度来看，它表现了人类进行记忆、规划、学习和问题求解的心理 模型，体现了更高级的知识环境，是多种人工智能技术的综合。基于案例推理的 专家系统不仅构建方便，而且很容易扩展，也有一定的自学习能力，已经越来越 受到人们的关注。 本文将可拓学和案例推理相结合，构建一种新型的混合专家系统。这种混合 专家系统克服了产生式规则专家系统的缺点，具有如下优点： ( 1 ) 知识表示更自然。用可拓基元来表示专家知识，不仅可以表示确定性知 识，而且可以表示不确定性知识，解决了产生式规则专家系统中不确定性知识表 示困难的问题。可拓表示方法贴近现实事物，使知识表示自然、形象。 ( 2 ) 推理方式灵活。可拓逻辑中的可拓推理方法具有可拓性，符合人类专家 的思维方式。可拓推理与案例推理的结合，使混合专家系统的推理方式更为完善， 得出的结论也更为准确。 4 基于可拓规则和案例推理的混合专家系统 ( 3 ) 可扩展性强。通过案例库的修正和案例知识的增加，可以去除过时的案 例，添加新的案例，这样，不需专门的知识工程师就可以完成知识库的更新，这 使专家系统的扩展性大大增强。 ( 4 ) 智能化程度更高。可拓规则和案例推理相结合的混合专家系统，既能依赖 专家知识来判断问题，又能依赖案例库来进行推理，二者互为补充，弥补了单一 推理方式的不足，使整个系统的智能化程度大大提高。构建多种推理方式并存的 混合专家系统，是专家系统真正实现智能化的方向之一。 1 5 混合专家系统在c c 0 8 程控交换机故障处理中的应用 在2 0 世纪的最后十年，电信业作为国民经济的基础产业得到了空前发展。截 至2 0 0 6 年8 月底，我国电话用户总数突破8 亿户大关，达到8 0 5 4 0 6 万户。电信 业的飞速发展适应了在当今信息社会企业和人民生活对信息和沟通的需要，在超 常规的发展中电信业获得千载难逢的机遇，也遇到了很多挑战。 程控交换机是电信核心网的重要设备，在整个通信网中担当着重要任务。程 控交换机运行的可靠与否，直接关系到全程全网的通信畅通。也直接关系到用户 服务和电信收入。随着程控交换技术的不断发展，程控交换机的功能越来越强大， 系统也越来越复杂，再加上复杂的组网技术，系统的故障类型也越来越多。以华 为c c 0 8 数字程控交换机为例，维护手册上所列告警超过5 0 0 多种，再加上现场 各种复杂情况，实际会产生的故障情况将会耗费大量的人力去排除。有些故障在 有经验的专家在现场时，可能很快就解决了，但是，对于一个普通的维护人员， 就有可能花上一天，甚至于一个星期的时间。这在时间就是金钱的通信领域是不 能容忍的。 通过生产现场的调研，我们发现程控交换机的故障处理尚停留在手工阶段， 都是通过程控交换机专家和用户之间的沟通来完成，普通工程师无法胜任疑难故 障的诊断和处理工作，所以，目前，程控交换机的故障处理专家系统的研究，基 本上还是一个空白点。所以，建立一个程控交换机故障处理专家系统，从小的方 面来说，将是一个有利于企业的行为，从大的方面来说，将减轻整个交换机用户 群在故障处理上的投入，带来很大的社会经济效益。 本文将可拓规则和案例推理技术应用到c c 0 8 程控交换机的故障处理当中， 构建了一种程控交换机故障处理混合专家系统，不论是从运营商的角度，还是从 设备生产商的角度，这都具有十分积极的意义。从运营商的角度来讲，程控交换 机故障处理人员需要具有较高的素质，要有很好的逻辑思维能力，要有条理性， 还要有敏感性。培养一个c c 0 8 程控交换机系统方面的专家，将会花上至少两年 时间，而且需要大量的培训费用，所以，对于通信运营商来说，有一个专家系统， 第一章绪论 5 将会大大降低所需服务人员的整体人力成本，为公司带来更多的利润。从通信设 各生产商的角度来讲，有一个强大的专家系统作为支撑，将大大减少在客户服务 方面的投入，提高技术支持水平，有利于提高公司的服务能力和品牌形象。 1 6 本文的主要研究内容 本文介绍了可拓学的基础知识，并将可拓学应用到专家系统中，建立了可拓 推理机模型。本文对基于案例的推理作了详细的介绍，并对案例的检索算法作了 深入的研究，用可拓关联度和信息增益对k n n 算法进行了改进。为了解决单一推 理方式的不足，本文将可拓规则和案例推理相混合，建立了一种新的混合专家系 统模型，并研究了这种混合专家系统在数字程控交换机的故障处理中的应用。具 体说来，本文的研究工作有以下几点： l 、将可拓学应用到专家系统中，建立了可拓推理机模型。本文提出用可拓基 元来表示专家知识，用可拓规则代替传统的产生式规则，并在此基础上，实现了 可拓推理机。本文给出了可拓推理机的推理算法，并用j a v a 语言实现了推理机的 类库。 2 、介绍了基于案例的推理技术，着重研究k - n n 算法，并对其进行了改进。 论文提出用信息增益来度量属性的重要性，并根据重要属性将样本空间划分为若 干个子空间，然后用可拓关联度将测试样本映射到对应的子空间中，在子空间内 进行样本分类。改进后的算法实际上对样本做了前期的预处理，使样本的搜索空 间变小了，提高了分类速度和准确度，增强了抗干扰能力。将改进后的k n n 算法 应用到案例检索中，提高了检索效率。 3 、将可拓规则和案例推理混合列一起，构成一种新的混合专家系统基于 可拓规则和案例推理的混合专家系统。新的混合专家系统中，可拓推理机和案例 推理机组成混合推理机。可拓推理机利用可拓规则迸行推理，在知识表示上比传 统产生式规则推理有所提高；案例推理机依靠强大的案例库进行推理，符合人类 的思维方式，弥补了规则推理的不足。 4 、研究混合专家系统在数字程控交换机故障处理中的应用。数字程控交换机 是电信网络中非常重要的设备，它的故障处理是一个非常复杂且技术性很强的工 作。本文以华为公司c c 0 8 数字程控交换机为例，构建了一个故障处理混合专家 系统，实现了理论与实践相结合。 1 7 小结 6 基于可拓规则和案例推理的混合专家系统 本章回顾了专家系统的发展历史，简要介绍了现代专家系统的相关技术，提 出将可拓学应用到专家系统中，并与案例推理技术相接合，构建基于可拓规则和 案例推理的混合专家系统，并将该混合专家系统应用到c c 0 8 数字程控交换机的 故障处理中。通过生产试验表明，这种混合专家系统缩短了故障定位时间，提高 了故障处理速度，节省了运维成本，有效地保障了通信网络的安全运行。 第二章可拓学基础知识7 第二章可拓学基础知识 2 1 可拓学的发展及其现状 可拓学是一门由中国人独创的新学科。1 9 8 3 年，蔡文教授在科学探索学报 上发表了一篇开创性的论文 可拓集合和不相容问题，马上得到美国诺贝尔奖获 得者s i 雌n 教授的重视和支持。随后可拓学的系统研究渐渐形成。 可拓学的研究以物元理论和可拓集合理论为基础，它的发展主要经历了三个 阶段。第一个阶段是孕育阶段( 1 9 7 6 1 9 8 3 ) ，以可拓集合和不相容问题一文为 标志，提出了研究事物的可拓性和处理不相容问题这一方向。第二阶段是初创阶 段( 1 9 8 3 一1 9 9 2 ) ，初步确定了学科的研究范围，解决问题的技术手段和研究途径， 形成了解决问题的初步方法。这一阶段以发表可拓论及其应用、 o 称为( 力的正 稳定域。 肛( r ) = ( 。，乃，) i “毋尸膏( 西 5 0 0 ： i 。= ( 熔解，支配对象，保险丝b ) ； r 产( 电子元件c ，电流强度， 图3 1 设备d 的电路圈 o ) ； i 产( 关闭，支配对象，设备d ) ； 根据物理学的知识，显然有： i fr it h e ni l ，t h e nr 2 ，a n dt h e n1 2 。 那么可拓规则为： r l 辛1 1 r 2 1 2 用基元来表示产生式规则，就可以利用基元的可拓性开拓出新的基元，从而 利用基元变换，为处理矛盾问题提供多种选择的可能路径。利用可拓推理的拓展 性推理、传导性推理、共轭推理等多种推理规则，使可拓规贝在求解问题时功能 更为强大，求解结果更为准确，过程更为合理。 3 3 可拓推理方法在可拓规则中的应用 可拓性是事物固有的性质。客观世界中的事、物和关系可以用基元或复合元 及其组合加以形式化表达，依据事、物和关系的可拓性，可以对基元进行可拓分 析，从而产生一系列推理规则即基元拓展推理规则。基元拓展推理包括发散推理 规则、蕴含推理规则、相关推理规则和可扩推理规则。 对基元的变换会产生传导变换，传导变换的过程也可用推理规则来描述，即 传导推理规则。传导推理是指前件为可拓变换，后件为它所引起的传导交换的推 理。从内容上看，传导推理包括定性的部分和定量的逻辑值变化两个方面。从变 换的主体和对象考虑，传导推理分为自传导推理和它传导推理两类，自传导推理 又分为置换传导推理、增删传导推理、扩缩传导推理和分解传导推理。由物元内 部的传导变换所引起的传导推理过程称为自传导推理。而基元变换引起其他相关 基元的传导变换，引起相关物元的关联度的变化，这种推理过程简称为它传导推 理。 1 6 基于可拓规则和案例推理的混合专家系统 类似地，根据物的共轭性质，也可以得到一系列的推理规则，称为共轭推理。 在一定条件下，物的某一共轭部的变化，会导致其相应的共轭部发生传导变换。 在专家系统的可拓规则设计中，根据知识元的可拓性，可以灵活应用拓展推 理、传导推理和共轭推理方法，使知识规则体现可拓思维方式。 具体可拓推理规则见附录。 3 4 可拓规则的匹配 不同于传统的产生式规则，可拓规则的前件和后件都是用基元来表示的。根 据基元的特性，对可拓规则的匹配方法有欧式距离匹配方法和可拓距匹配方法。 对于基元属性取精确值的规则，要求证据与规则前件绝对相符，否则认为不匹配， 因此采用欧式距离匹配方法。而对于基元属性取特定区间值的规则，要求证据的 属性值落来特定区间内，因此采用可拓距函数来计算匹配度。 3 4 1 欧式距离匹配方法 若有可拓规则： f f a l d t l v 0 l t a g c0 1 la l 锄o i b u l tp o 啊甜叩】 【n 脚咖o j 表示当故障现象为电压o 伏，告警指示灯灭，设备停机，则诊断结果为停电 故障。这条规则的精确匹配必须使证据同时满足上述三条故障现象时，方可得出 停电故障的结论。 如有证据为： 广姒兰o 】 广兰a 第三章可拓推理机设计1 7 则认为证据与条件不匹配。 判断证据与规则前件的最简单的精确匹配办法是计算证据与条件之间的欧式 距离，如果距离为o ，则认为精确匹配，如果距离大于o ，则认为不匹配。 若有可拓规则：( r ，c 、，) 一( w ，c v ) ， 证据为： 则有匹配计算公式： i k ，c lv 1 ( r ，c ，、，) i 。：v 2 i乏z r ，c l ，v 1 c 2 ，v 2 c - ，v n p - 辱而而而丽丽- 压鬲( 3 - 1 ) 当p = 0 ，则认为匹配，当p 0 时，则认为证据与条件不匹配。 3 4 2 距匹配方法 在实际应用中，基于属性可能取某个特定区间的值。比如现实生活中，感冒 的病症现象根据每个人的身体状况会有所不同，有的人发烧很厉害，有的人咳嗽 很厉害，也有的人两者都有，并且每个人发烧时的体温会有差别，这时，我们不 可能通过简单计算欧式距离来判定证据与规则前件是否匹配，这时，我们可以利 用基元的可拓性，通过计算证据的属性值与规则前件属性取值区间的距，来判断 证据是否落在规则前件属性的区间内。 若有可拓规则： f a u l t l ，v o l t 3 9 e ，( o ，砷1 lc u r r e n t ，( 0 ，o 9 ) l 一 r e 蛐n ，p 0 w c r ，t 0 0 1 0 w ir 岫s t a m s ，( 0 ，o ) l 1 8 基于可拓规则和案例推理的混合专家系统 机，则诊断结果为电压过低。这条规则的匹配必须使证据的属性值同时落入上述 区闻内，方可得出电源电压过低的结论。 如有证据为： r 鋈剥 f a u l t l ，v 0 l t a g e ，2 5 1 iq l r 僦l ，0l l r u 硒t a n 培，0i -j 则认为证据与条件不匹配。 判断证据与条件的匹配最简单的办法是计算证据与条件属性区间的距，如果 距小于或等于0 ，则认为证据在属性值范围内，证据与条件匹配；如果距大于o ， 则认为证据不在属性值范围内，证据与条件不匹配。 设x 为实域( 一一，+ 一) 上的任一点，x 产 为实域上的任一区间，称 盹- 卜爿一字 为点x 与区间】( o 之间的距。 若有可拓规则：( r ，c v ) 一( w ，c v ) r ，c l ，( v 1 1 v 1 2 ) c 2 ，( v 2 l ，v ) c ，( v d l v n ) r ，c 1 ，v l c 2 ，v 2 c 。，v n 其中，v i ( v l i v 2 ) ，v 2 = ( v 扎v 挖) ，v 。= ( v i i v 。2 ) 。 证据为： r ，c 1 ，v 1 1 c ：，v ：。i l c 。，v 。j 第三章可拓推理机设计 1 9 则匹配度： p 三( v ，v 1 ) + _ p ( v ：，v 2 ) + + p ( v ，v n ) ) 。三皇p ( v 。- ，v i ) ( 3 - 2 ) n n 钉 如果p 小于0 ，证据与条件匹配；如果p 等于0 ，证据点落在属性区间边界上， 勉强匹配；如果p 大于o ，证据与条件不匹配。 3 5 1 可拓推理机算法步骤 3 5 可拓推理机算法 可拓推理机算法的推理思想是：首先，建立专家给定的可拓规则集和用户给 出的证据集：其次，计算证据和规则前件是否匹配成功并激活规则；然后，将得 到的推理结论加入证据集或证据集；最后，循环执行匹配，直到整个系统不再产 生新的推理结论为止，退出推理。 算法描述：输入：证据集p r o o f s e t 和规则集r u l e s e t 。输出：推理结论集。 算法步骤： 1 置初值：设有n 条可拓推理规则，m 条证据。令r = 1 。 2 】判断：如果1 r m ， 转 1 0 3 令i = 1 。 4 判断：如果1 i n ，转 9 ； 5 比对证据名和规则前件名，若相同，则转 6 ，否则，转 8 。 6 计算匹配度：根据规则前件的不同，用不同的公式计算匹配度。 若规则前件取值为精确值，用以下公式计算匹配度。 p 厅而而再丽一压鬲 当p 等于0 时匹配成功，不等于0 时匹配失败。 当规则前件取值为区间值时，用以下公式计算匹配度。 p 。三( p ( v ，v 1 ) + p ( v ：t ，v 2 ) + + p ( v 。，) ) 。三窆p ( v ；- ，v i ) n n 爿 如果p 小于0 ，证据与条件匹配；如果p 等于0 ，证据点落在属性区间边界上， 2 0 基于可拓规则和案例推理的混合专家系统 勉强匹配；如果p 大于o ，证据与条件不匹配。 若p o ，则规则匹配成功，转 7 ：否则，转 8 。 7 所有规则前件的子前提都比对后，则得到推理结论或新的证据。得出新的 证据。则将证据添加到证据集中，m + + 。得出结论，则将结论添加到结论集中。 8 i + + ，转 4 。 【9 r + + ，转 2 。 1 0 输出推理结论集。 算法描述完毕。 3 5 2 可拓推理机推理算法的复杂度分析 令n 为规则集的规则条数，m 为证据集的证据条数，每条规则的前提部分可能 含有的子前提个数不同，所以令子前提最大个数为a 。j 为产生的中间推理证据个 数。 时间复杂度分析：最坏情况下，对于一个子推理过程，每条规则有a 个子前提， 每条规则都要对其每个子前提与证据集进行比对，复杂性为a 个m 相加，即a m ， 规则集的规模数为n ，则其复杂性为o ( n m a ) ，对于一个全推理过程，其时间 复杂度为o ( j n m a ) 。最好情况下，每条证据只有一个子前提，没有任何中 间推理证据产生，只考虑证据集和规则集的规模，那么时间复杂度为o ( n h o 。 空间复杂度：算法的空间复杂度与证据集和规则集有关，中间证据可以忽略 不计，那么，算法的空间复杂度为o ( n + m ) 。 3 6 可拓推理机的设计实现 推理机的设计框图如图3 2 所示。 考虑到专家系统的跨平台应用，可拓推理机用j a v a 语言开发，在l i n u x 平台 上测试通过，打包成一个e x j j a r 文件可拓推理机主要有如下几个类： e x e n g i n e ( 可拓引擎类) ，e x r u l e s e t ( 可拓规则集类) ，e x e v i d e n c e s e t ( 可拓证据集 类) ，e x c o n c l u s i o n s e t ( 可拓结论集类) ，e x r u l e ( 可拓规则类) ，e x e v i d e n c e ( 可 拓证据类) ，e x c o n c l u s i o n ( 可拓结论类) ，e x r u l e i f ( 可拓规则前件类) ， e x r u l e t h e n ( 可拓规则后件类) ，e x v a r i a b l e ( 可拓基元类) 。 可拓基元类是推理机的最小运算单元，它可以是一个物元、关系元或事元的 表示，它是构成可拓规则前件、可拓结论的基本元素。可拓规则类由可拓规则前 件类和可拓规则后件类组成，可拓规则前件类由若干个可拓基元类组成，这些可 拓基元类之闻可以是任何逻辑关系，可拓规则后件类由可拓证据类或可拓结论类 第三章可拓推理机设计 组成。若干个可拓规则类构成可拓规则集类，若干个可拓证据类构成可拓证据集， 若干个可拓结论构成可拓结论集。整个可拓引擎类由可拓规则集、可拓证据集、 可拓结论集构成。 可拓引擎类是可拓推理机的核心类，它为专家系统的实现提供了一个运行平 台。可拓引擎类的a d d ( ) 方法是一个多态方法，可以用来向推理引擎添加用来推理 的规则集和证据集。可拓引擎类的r u n ( ) 方法用来实现可拓推理算法，即根据规则 集和证据集推出结论集，并输出最后的推理结论。 图3 2 可拓推理机设计类图 3 7 小结 用可拓基元来表示专家知识，形成可拓知识元，用可拓知识元来表示规则的 前件和后件，这是可拓规则的基本特征。在可拓推理机的设计实现中，本章给出 了两种可拓规则匹配方法，在此基础上，给出了可拓推理机算法。在本章结尾， 用j a v a 语言设计实现了可拓推理机，该推理机可以在任何平台上使用。 第四章基于案例的推理 第四章基于案例的推理 4 1 基于案例的推理介绍 基于案例的推理( c a s e b a s e dr e a s o n i n g ，c b r ) 技术最先是由美国耶鲁大学 r o g e rs c h a n k 教授在他的论著d y n 硼i cm e m o r y 中提出的。1 。c b r 是一种基于经 验知识进行推理的人工智能技术，它是用案例来表达知识并把问题求解和学习相 融合的一种推理方法，它强调入在解决新问题时，常常回忆起过去积累下来的类 似情况的处理，并通过适当修改过去类似情况处理的方法来解决新问题。也就是 说当我们遇到某种情况时，我们习惯于回忆起以前情境中的方式、方法、策略以 及解决方案等，来帮助我们找到当前问题的解决方案。从认识思维的角度来看， 它表现了人类进行记忆、规划、学习和问题求解的心理模型，体现了更高级的知 识环境，是多种人工智能技术的综合。 对于基于案例的推理而言，学习能力是它的一个很重要的特征。基于案例的 方法发展的动力很大程度上来自于机器学习，实际上基于案例的推理也被认为是 机器学习的一个分支。基于案例的推理不仅是一种特别的推理方法，同时也是一 种机器学习模型，它通过问题解决后更新案例库来获得持续不断的学习能力。对 于基于案例的推理系统而言，学习是解决问题后的一个很自然的附带过程。当一 个问题成功地解决后，经验被保留用于解决将来相似的问题：当解决问题失败后， 找出失败的原因并将它记住，将来可以避免犯同样的错误，这都是属于机器学习 的范畴。 基于案例的推理是用以往案例的知识或信息进行相似案例问题求解的方法， 它在知识获取、求解效率、求解质量以及知识积累等方面，有着突出的优势。现 在，基于案例的推理已经发展成为创设智能系统的模式，这种模式能够利用原有 的经验进行推理，使得它比传统的专家系统更像专家一样运行。 目前，在美国和欧洲基于案例推理的研究非常活跃，很多人工智能的杂志都 有这方面的文章。德国在这已研究领域处于领先的地位。从日本到亚洲国家，也 有一些关于基于案例推理的研究。 4 2 基于案例推理的工作流程 典型的c b r 操作流程一般如图4 1 所示嘲伽1 ”： 基于可拓规则和案例推理的混合专家系统 图4 1 案例推理的工作流程 ( 1 ) 问题描述。把当前问题的特征变量，以案例的形式向系统进行表述。 ( 2 ) 案例检索。通过案例的索引与检索，在案例库中寻找与当前问题最为相似 的案例。如果旧案例与当前问题完全相符，则直接输出该问题的解决方案。否则， 对检索出的案例进行完善修改，形成一个全部满足新案例的解答，生成新案例。 ( 3 ) 案例的修改或学习。对当前问题的解进行评价，并将新方案增添到案例库 中，以备日后求解问题使用。 从工作流程来看，传统的基于规则的系统遇到一个新问题时，总是试图用规 则库中的规则进行匹配，当匹配不成功时，就宣布该问题无解。而对于c b r 系统， 在给定输入说明的情况下，c b r 系统将搜索案例库，以寻找一个匹配输入特征的 现有案例。一方面，它可能找到完全匹配输入特征的案例，从而直接得到问题的 解答，使复杂问题得到快速解决；另一方面，它也可能检索到一个与输入特征相 似的案例或案例集，c b r 系统( 或用户) 可修改不相匹配的部分，得到一个新的案例 并添加到案例库中，使系统具有学习能力。 4 3 案例的表示 基于案例的推理依赖于案例集的结构和内容。由于问题的解决是通过回忆适 合解决新问题的以前的经验，需要有快速有效的搜索和匹配过程。更进一步讲， 新问题解决后得到的经验要以某种方式保留下来，因此将新的案例添加到案例库 的方法同样要求行之有效和高速。c b r 的表示问题主要是决定案例的内容、结构和 行之有效地组织和检索案例库，从而有效的检索和再使用。还有另外的一个问题 是如何将案例库的结构和常规领域知识模型结合起来，以达到包容这些知识的程 度。 第四章基于案例的推理 现有的案例表示方法有s c h a n k 和k o l o d n e r 提出的动态存储器模型和p o r t e r 和b a r e i s s 提出的种类一样本模型嘲。 ( 1 ) 动态存储模型 最早可称得上基于案例的推理系统是k o l o d n e r 的c y r u s 系统，它基于s c h a n k 提出的动态存储器模型。这个模型的案例存储器是由e m p s ( e p i s o d i c 舱哟r y o r g a n i z a t i o np a c k e t s ，小事件存储组织包) 构成的一个层次结构。这个模型是 根据s c h a n k 的更为一般的m o p 理论发展而来。这个模型的基本观点是将具有相似 特性的一些案例组织到一个一般的结构中( g e n e r a l i z e d 印i s o d e ，简称为g e ) 。 一个g e 包含三个不同类型的对象：准则、案例、索引。准则就是一个g e 所包含 的所有案例共有的特征。索引就是能够将一个g e 中的案例区别开来的那些特征。 一个索引可以直接指向一个案例，也可以指向另外一个g e 。一个索引包含有两个 部分：索引名和索引值。 ( 2 ) 种类一样本模型 r a yb a r e i s s 和b r u c ep o r t e r 建造了一个基于案例的推理系统p r o t o s ，提出 了一种在案例库中组织案例的另一种方法。这个案例存储模型是用一个由种类、 案例和索引指针构成的网络结构来实现的。每一个案例都与一个种类相关。一个 索引可能指向一个案例或一个种类。索引有三类，一类是特征连接，它由问题的 描述子也就是特征指向案例或种类；另一类是案例连接，它由种类指向与它相关 的案例( 也叫样本连接) ；第三类是差异连接。从一个案例指向与它相邻的其他相 近的案例。一个特征一般用一个名字和一个值一起来表示。一个种类包含的所有 样本依据和原型接近的程度来分类。 4 4 案例的检索 案例检索的任务是找到与求解案例最接近的过去的案例。它的子任务是：确 定特征，初始匹配，搜索，和选择，并且依先后的顺序执行。确定特征子任务提 出一些与问题相关的特征，匹配子任务的目标就是找到一些与新案例足够相似的 老案例，搜索和选择子任务就从这些案例中找到最佳的匹配案例。 在目前的c b r 系统中常用的案例检索方法有最近相邻方法( n e a r e s t n e i g h b o r m e t h o d ) 、归纳推理方法( i n d u c t i v em e t h o d ) 、基于知