（计算机应用技术专业论文）网络故障诊断专家系统知识库的研究与设计.pdf

摘要 摘要 计算机网络的可靠性一直以来都是人们比较关心的问题，而提高网络可靠 性的一个主要方法就是及时诊断出网络故障的具体原因。网络故障诊断专家系 统在实际中应用较为广泛，但是存在知识获取“瓶颈”和知识难以维护等不足。 本文将决策树分类算法应用于网络故障诊断专家系统中，实现了故障诊断知识 的自动获取与表示，提高了故障诊断专家系统的灵活性。 首先本文对专家系统的一般结构进行阐述，并对知识库与推理机进行深入 研究；同时详细的阐述了决策树分类算法，对比较流行的决策树算法i d 3 ，c 4 5 等算法进行详细分析与比较。 其次建立了网络故障诊断专家系统的基本结构，划分了各个功能模块，并 提出了整个系统的控制策略。 然后提出了基于决策树知识表示，给出了知识的存储方法，并构建了整个 系统的知识库；针对知识存储的特点采用基于决策树推理机制来实现推理机。 最后以决策树理论为基础，提出了基于决策树知识获取的方法。该方法充 分利用决策树把知识表示与获取融于一身的优点，使知识表示与知识获取同时 进行，克服了传统人工智能系统中知识表示与知识获取分离的缺点。 关键词：网络故障诊断；决策树理论；知识表示；知识获取 东北电力大学硕十学位论文 a b s t r a c t n l er e l i a b i l i t yo fc o m p u t e rn e t w o r ki sc o n c e m e da l lt h et i m e o n eo ft h ef e a s i b l e a p p r o a c h e st oe n h a n c i n gt h en e t w o r kr e l i a b i l i t yi s t od e t e c ta n dl o c a t et h ef a u l ti n t i m e t h ea p p l i c a t i o no fn e t w o r kf a u l td i a g n o s i se x p e r ts y s t e mi sw i d e ，b u ti t s k n o w l e d g ei sd i f f i c u l tt oo b t a i na n dt h em a n a g e m e n ti sc o m p l e x t h es y s t e mr e a l i z e s t h ea u t o a c q u i r e m e n tf o rf a u l td i a g n o s i sk n o w l e d g eb yu s i n gd e c i s i o nt r e ea l g o r i t h m i ni t ，w h i c hi m p r o v e st h ef l e x i b i l i t yo ft h i ss y s t e m f i r s t l y , t h i sp a p e ri n t r o d u c e st h eg e n e r a ls t r u c t u r eo fe x p e r ts y s t e m t h e ni t m a k e sat h o r o u g hs t u d yo nt h ek n o w l e d g ed a t a b a s ea n dr e a s o n i n gm a c h i n e m e a n w h i l ei td e s c r i b e st h ed e c i s i o nt r e ec l a s s i f i c a t i o na l g o r i t h mi nd e t a i l ，a n a l y z e s a n dc o m p a r e st h ei d 3 ，c 4 5a n do t h e rp r e v a l e n td e c i s i o nt r e ea l g o r i t h m s e c o n d l y , t h i sp a p e rd e s i g n st h eb a s i cs t r u c t u r eo fn e t w o r kf a u l td i a g n o s i se x p e r t s y s t e m ，w h i c hi sd i v i d e di n t os e v e r a lf u n c t i o nm o d u l e s ，a n dp u t sf o r w a r d t h ec o n t r o l s t r a t e g yo f t h es y s t e m t h i r d l y , i tp u t sf o r w a r dt h ek n o w l e d g er e p r e s e n t a t i o nb a s e do nd e c i s i o nt r e e ， g i v e st h es t o r a g em e t h o do ft h ek n o w l e d g e t h e na c c o r d i n gt ot h ec h a r a c t e r i s t i c s ，i t r e a l i z e st h er e a s o n i n gm a c h i n eb yu s i n gr e a s o n i n gm e c h a n i s mb a s e do nd e c i s i o nt r e e a n dc o n s t r u c t st h ek n o w l e d g ed a t a b a s eo ft h ew h o l es y s t e m f i n a l l y , t h i sp a p e rp r o m o t e st h em e t h o do fk n o w l e d g ea c q u i s i t i o nb a s e do nt h e d e c i s i o nt r e et h e o r y t h i sp r o p o s e dm e t h o du s e st h ea d v a n t a g et h a tt h ed e c i s i o nt r e e p o s s e s s e s t h ek n o w l e d g er e p r e s e n t a t i o na n da c q u i s i t i o n ，a n dc a r r i e so u t t h e k n o w l e d g er e p r e s e n t a t i o na n dk n o w l e d g ea c q u i s i t i o ns i m u l t a n e o u s l y , o v e r c o m e st h e s h o r t a g eo ft h ek n o w l e d g er e p r e s e n t a t i o na n dk n o w l e d g ea c q u i s i t i o ns e p a r a t e di n t r a d i t i o n a la r t i f i c i a li n t e l l i g e n c es y s t e m k e yw o r d s ： n e t w o r kf a u l td i a g n o s i s ；d e c i s i o nt r e et h e o r y ； k n o w l e d g e r e p r e s e n t a t i o n ；k n o w l e d g ea c q u i s i t i o n i i 论文原创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上已属于他人的任何形式的研究成果，也不包含本人己用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害， 进行公开道歉； 4 本人负责因论文成果不实产生的法律纠纷。 论文作者签名：二蔓毯卜 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属东北电 力大学。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时， 署名单位仍然为东北电力大学。 论文作者签名： 导师签名： 日期： 盖! 墅星年土月兰红日 日期：丑年王月互日二 第1 章绪论 第1 章绪论 1 1 研究背景及意义 近几年来，计算机网络的发展异常迅猛。计算机网络的使用越来越广泛， 用户对网络的依赖也越来越大。网络不仅渗透到工业、银行、大专院校等各个 领域，而且还进入了千家万户。未来社会是信息的社会，而信息社会是离不开 网络的。因此，计算机网络在人们生活中的地位将越来越重要。研究表明，一 个普通的局域网络在一年中平均出现重大故障二十次，由此产生的服务失效时 间长达十六小时，这对于各大型企业、公司等机构来说，造成的损失是巨大而 且难以弥补的【l j 。网络管理系统可以给网络管理员提供良好的信息来源，减少网 络故障，缩短网络失效时间，最大程度地提高网络服务质量。所以，成功企业 在选择良好的网络设备和网络操作系统、应用软件的同时，也会选择优秀的网 络管理系统，为它们的网络提供最好的服务。 当前计算机网络发展的特点是：网络规模不断提高，复杂性不断增加，网 络的异构性越来越高。一个网络往往由若干大大小小的子网组成，集成了多种 n o s 平台，包括不同厂家、公司的网络设备和通信设备等。同时，网络中还有 许多网络软件提供各种服务。随着用户对网络的性能要求越来越高，如果没有 一个高效的网络管理系统对网络系统进行管理，那么很难保证为广大用户提供 令人满意的服务。网络管理是网络发展中一个很重要的关键技术，对网络的发 展有很大的影响，并成为现代信息网络中最重要的问题之一。 作为网络管理五大功能之一的故障管理【2 】，其负责检测和确认网络中的故 障。由于网络越来越复杂化，所使用的设备也越来越精密，所提供的网络服务 也日趋多样化，网络问题也通常以不明确的形式出现，甚至同样的网络故障会 因网络拓扑结构的不同、网络延迟时间不同及网络数据资料缺失而有不同故障 现象发生，而不同的故障能导致如传输速度过慢、服务主机效率不佳、网络数 据包无故遗失等不同的状况。当出现网络故障，网管人员首先要做的就是了解 更多的故障信息，然后他们凭借工作经验以及专业知识，辅以各种软、硬件工 东北电力大学硕士学位论文 具，在复杂的警告信息中找出真正的关键警告信息，由此确认网络出现何种故障 进而解决网络故障。网管人员都希望能在最短时间内了解所有问题与设备的关 联性，网络问题发生时希望能在最短时间确认时间与地点，但有经验的管理人 员在实际的执行面上也是有其困难的，常常是在花了数倍的时间与精力之下却 也不一定能完全解决问题。 为了迅速进行网络故障诊断，重要的是要拥有合适的网络测试和分析工具。 网络故障诊断系统就是为了解决这个问题而被开发出来的。为了使现代网络故 障诊断系统能够更高效的对如此复杂多变的网络进行故障诊断，网络故障诊断 的综合化、自动化和智能化提到了议事日程，成为了网络故障诊断未来的发展 方向。许多研究者很早就尝试将人工智能的技术应用到网络管理领域，如人工 神经元网络、专家系统、数据挖掘、确定性理论、证据理论、主观b a y e s i a n 方 法等等。在这些技术中，专家系统技术在网络故障诊断领域的应用是比较成功 的，专家系统对解决网络故障诊断中的一些问题有很好的效果，如实时性、协 作管理等，因此专家系统特别适合用在网络的故障管理中。 应该说专家系统的结构是完整的，其工作是富有成效的。然而由专家手动 建立知识库的过程，为专家系统的应用带来了很大的不便： 1 为保证专家知识的准确性，知识只能由领域专家提供，这便限制了大部 分没有足够经验的研究人员独立应用专家系统进行故障诊断。 2 知识库建立的过程是通过知识工程师同领域专家进行不断交流，再手动 输入专家知识并完成相关的人机交互工作。这一步骤通常会消耗领域专家和知 识工程师大量的时间和精力，并严重降低了专家系统的应用效率。 本文拟将决策树算法和网络故障诊断专家系统结合起来，从网管数据库中 挖掘出有价值的信息和模式来更新网络故障诊断专家系统的知识库，以提高故 障诊断速度及正确性，减少对特定人员的依赖。 1 2 国内外研究现状及进展 1 2 1 课题的国外研究现状 国外在网络故障诊断方面的研究起步比较早，他们有网络故障管理专家系 第1 章绪论 统的商业化产品。目前，国外的网络管理软件如i b m 的n e t v i e w ，h p 公司的 o p e n v i e w ，s u n 公司的s u nn e t m a n a g e r 等，都没有提供良好的网络故障诊断功 能，故障诊断的功能实现需要管理人员通过人工经验分析去完成，没有完成网 络故障管理的自动化p 】。在数据挖掘应用于网络故障诊断方面，芬兰h e l s i n k i 大 学与一家远程通讯设备制造厂合作的t a s a 系统，它主要用于通信网络的故障 定位检测和严重故障的预测等任务。但将数据挖掘技术应用于计算机网络故障 诊断的研究相对较少，也没有形成实用的系统。 1 2 2 课题的国内研究现状 网络管理在国内现在也是网络研究的热点，取得了一些阶段性的成果。如 清华大学的c i m s 网络监控管理系统，北京航空航天大学开发的网络管理系统， 东南大学的网络管理系统w a t c h e r ，以及上海交通大学与日本合作开发的w a l k e r 中文版网络管理系统h 1 等。这些系统没能把算法理论高效的应用到实际的网络故 障诊断中，虽然其中一些用到了基于专家系统的故障诊断方法1 5 j ，基于神经网络 的故障诊断方法【6 】和基于模糊神经网络的故障诊断方法1 7 】等人工智能技术，但这 些理论固有的缺陷使得实际结果与应用需求还有较大的差距。 1 基于专家系统的故障诊断方法 专家系统是人工智能领域中最活跃的一个分支，它已广泛的应用于过程监 测系统。该方法不依赖于系统的数学模型，而是根据人们长期的实践经验和大 量的故障信息知识，设计出一套智能计算机程序，以此来解决复杂系统的故障 诊断问题。在故障检测诊断专家系统的知识库中，存储了某个对象的故障征兆、 故障模式、故障成因、处理意见等内容，这是检测诊断的基础【8 j 。故障检测专家 系统的推理机构是一个特定的计算机程序，它在一定的推理机制指导下，根据 用户的信息，运用知识进行推理判断。 2 基于神经网络的故障诊断方法 基于神经网络具有处理复杂多模式及进行联想、推理和记忆的功能，它非 常适合应用于故障诊断系统。它具有白组织自学习能力，能克服传统专家系统 当启发式规则未考虑到时就无法工作的缺陷。因此，将神经网络应用于过程监 测系统已成为一个非常活跃的研究领域f 9 】。 东北电力大学硕士学位论文 用神经网络进行故障诊断有以下两种方式： ( 1 ) 离线诊断。它将学习和使用过程分开。当系统出现故障时，把故障信息或 现象输入神经网络，经过自组织、自学习，输出合理的解决办法。 ( 2 ) 在线诊断。将神经网络与系统直接相连，让其自动获得故障信息及现象， 然后由神经网络内部自组织、自学习，使学习过程和使用过程合二为一。这种 学习过程是“无导师学习 。 3 基于模糊神经网络的故障诊断方法 在诊断领域中，模糊逻辑理论和神经网络技术在知识表示、知识存储、推 理速度等方面起到了很大作用。模糊控制和神经网络各自优势在于：模糊控制 易于获得由语言表达的专家知识，能有效的控制难以建立精确模型而凭经验可 控制的系统，而神经网络则由于其仿生特性更能有效利用系统本身的信息，并 能映射任意函数关系，具有并行处理和自学习能力，容错能力也很强。 1 2 3 存在的问题 尽管上述各种智能故障诊断技术各具特色，但仍存在以下不足： 基于专家系统的故障诊断方法中，专家系统不能处理那些因网络环境变化 而产生的新数据，已建立的规则不够健全，无法跟随网络的动态变化；不能从 经验中学习，在开发阶段已经建立的规则无法适应不断变化的网络；对于未经 专i - n 练的网络用户，向专家系统添加规则很困难；随着领域知识的变化，需 要动态添加或删除相应的规则，维护的工作量较大。 基于神经网络的故障诊断方法也存在着一定的局限性：由于神经网络所学 到的知识是以权重形式分布在网络之中，对诊断结果缺乏解释能力，对用户来 说整个诊断系统相当于一个“黑箱 、不具备透明性。 基于模糊神经网络的故障诊断方法，将模糊逻辑理论和神经网络技术相结 合，在实现上具有一定的复杂性【i o 】。 1 2 4 数据挖掘理论的引入 由于传统的网络管理技术无论从功能上还是从效率上以及网络管理成本上 均无法满足对大型复杂网络系统的管理，这些因素使得在现代网络管理中必须 第1 章绪论 引入有效的信息处理技术一基于知识发现的网管信息处理技术。作为一门新兴 的自动信息提取技术，数据库中的知识发现( 1 d ) 和数据挖掘( d a t am i n i n g ) 技 术f 6 】的出现为自动和智能地把海量原始数据转化为有用的信息和知识提供了手 段，从而可望克服传统专家系统“知识获取 瓶颈的不足。将知识发现和数据 挖掘技术引入到现代网络管理，目的是提取出隐含的海量网管数据库中先前未 知的却有潜在价值的信息和模式，做出预测性分析，从而实现网络故障自动诊 断、预测和维护，并保证网络具有高服务质量和高可靠性。 1 3 本文的研究工作及组织结构 1 3 1 本文的研究工作 论文所做的工作是： 1 设计整个网络故障诊断系统结构，划分各个功能模块； 2 构建系统知识库，包括知识表示和知识的存储，实现对知识库的修改，研 究如何表示知识和存储知识可以更加便于知识获取，更加便于运用知识进行推 理： 3 针对知识存储的特点采用基于决策树推理机制来设计并实现推理机； 4 知识获取，用以部分地代替专家进行专门知识的自动获取，实现系统的自 学习，通过更新知识，来不断完善知识库。诊断知识获取主要利用决策树理论 再结合有关专家经验得出诊断规则，当网络出现故障时进行诊断，再根据出现 的网络故障的诊断情况对知识库中原有知识进行更新。 1 3 2 本文的组织结构 全文共分5 章，具体的章节内容安排如下： 第1 章介绍了论文的研究背景及意义以及国内外研究现状及进展，概要介 绍本文所作的工作和本文的组织情况。 第2 章介绍了专家系统和决策树分类算法的基本概念和主要知识，为后文 知识库的构建与推理机的设计奠定基础。 第3 章建立了网络故障诊断专家系统的基本结构，划分了各个功能模块， 东北电力大学硕士学位论文 并提出了整个系统的控制策略。 第4 章提出了基于决策树知识表示，给出了规则的存储方法，构建并实现 了知识库；设计并实现了基于决策树的推理机制，在此基础上，给出了冲突消 解策略。 第5 章提出并实现了决策树知识获取方法，并对几种知识获取方法的性能 进行了分析，最后给出了应用举例。 最后为结论与展望。 第2 章相关知识及技术 第2 章相关知识及技术 2 1 专家系统概述 专家系统( e x p e r ts y s t e m ，e s ) 是人工智能的一个重要的应用领域，产生于 6 0 年代中期，经过多年的研究和发展，其理论和技术日趋成熟，应用也愈加广 泛。目前专家系统已在医疗、化工、图像处理、金融决策、军事等领域开发出 了大量的专家系统，产生了巨大的经济效益和社会效益。 2 1 1 专家系统的定义 专家是指在某一专业领域的知识与解决问题的能力达到较高水平的人，他 们经过了长期的专业训练与经验积累，拥有大量的知识，而且具有将知识运用 到具体问题和任务中的能力，擅长从众多看似不相关的信息中发现问题的本质， 解决其他人不能解决的问题。 专家首先熟练掌握了某个领域的专业知识，包括该领域内相关的定义、事 实和理论，这些往往可以在教科书和文献当中找到；除此之外，他们还经常使 用他们的个人知识，这些个人知识大部分来源于专家本人的经验积累，一般也 称为启发性知识。启发性知识能让专家在某些特殊情况下做出合理的猜测，寻 找最有希望的解决途径，有效地处理错误和不完全的数据。 在实际的问题处理过程中，有许多问题无法被精确地描述和严格的分析， 必须利用专家的对问题的描述能力和有选择性地应用有关知识的能力。但是， 作为一种稀缺资源，高水平的专家是有限的，专家的数量不可能大到在任何需 要他们的地方都可以进行配备的程度，并且这样做也造成了人力资源的浪费。 因此，一种可行的解决方案是：设计一种计算机程序，利用其存储的某一领域 内专家的专业知识和经验，来解决过去需要人类专家才能解决的问题。这种具 有人类专家水平的计算机程序就被称为专家系统。利用类似专家的思维方式和 路径，对问题的原始数据进行合理的推理、演绎，并做出判断和决策，这就是 专家系统的任务。 东北电力火学硕士学位论文 从结构上看，专家系统【l l 】主要是由一个存放专家领域知识的知识库和一个 应用知识进行推理的推理机所组成的，它与传统程序的区别在于专家系统中知 识库和推理机是相互独立的，而传统程序则是数据与算法的有机结合。传统的 程序通过算法对大量的数据进行积累和处理，使繁琐的事务处理自动化；而专 家系统通常是要完成那些需要拥有专门知识的专家在短时间内完成的任务，需 要动态地建立解决问题的方法。 2 1 2 专家系统的结构 专家系统的结构根据应用的环境和所处理的任务类型而各不相同，但不论 采用哪种系统结构，存放知识和运用知识进行问题求解是专家系统两个最基本 的功能模块。知识库用于存储从专家那里获得的某个专业领域的知识；推理机 依据一定的策略进行推理，根据知识和当时所处的环境推导出正确的结论。图 2 - 1 表示了专家系统的基本结构。 图2 1 专冢系统的基本结构 在构造知识库时，需要研究如何把专家的知识转化为计算机可识别的形式， 即如何对专家知识进行表示，让专家系统能够对他们进行识别、查询、使用等 操作；另外，还需要研究如何从专家那里获得知识，即知识获取问题，这往往 是专家系统的瓶颈所在。 2 1 3 专家系统的核心一知识库 知识是人类对客观世界的认识。数据、信息和知识形成一个层次，数据在 底层，知识在最上层。数据是信息的载体，信息是数据所表达的客观事实。数 据经过一系列的加工，如归纳、综合、比较、分类、联想或计算等数据处理过 第2 章相关知识及技术 程成为信息，以使人们容易理解数据的意义。在数据和信息之上的是知识。知 识是人们通过实践认识到的客观世界规律性的东西。知识是信息经过加工整理、 解释、挑选和改造而形成的，是人们进行决策的基础。数据是资源，数据处理 的计算化将有助于提高数据资源的利用率和获得高质量的信息。知识是一种更 宝贵的资源，知识的推广和使用可以产生巨大的经济效益。 2 1 3 1 知识库及其管理知识库( k n o w l e d g eb a s e ，k b ) 至今还没有一个统一 的定义。从存储知识的角度来看，以描述型方法来存储和管理知识的机构叫做 知识库。知识库是事实、规则和概念的集合。事实在库中是短期信息，这种信 息在与用户交互作用中会迅速改变。规则是从专家们的经验中提取出来的知识， 是长期信息，它能指导专家系统如何由已知的或新产生的事实推导出假设来。规 则的质量直接影响到专家系统的性能的优劣。概念包含信念和常识。信念会随 着时间的改变而变化，所以是一种非长期的信息；常识是一种不随时间变化的 固定概念，所以是一种长期信息。从使用知识的角度来看，知识库是由知识和 知识处理机构组成。知识库形成一个知识域，该知识域中除了事实、规则和概 念之外还包含推理、归纳、演绎等知识处理方法，逻辑查询语言、语义查询优 化和人机交互界面等。一般来讲，从存储知识的角度出发做出的知识库的定义 比较常用，而且也比较符合知识库使用的实际情况。 知识库管理是指对知识库进行管理、控制，完成对知识库的各类操作，并 向用户提供检索、查询手段，它包括系统的维护与诊断、日常的系统事务管理、 各种实用程序的管理、出错处理、知识库系统的安全控制和用户的使用权限管 理等。在早期的知识库中，知识数量比较少，知识的层次也是单一化的，知识 的管理并不十分突出，因此在设计知识库时，比较重视知识的使用而不重视知 识的管理。随着知识库的大型化，知识数量达到成千上万条，知识的层次也丰 富起来，包括尝试性知识、原理性知识、经验知识和元知识等，知识的管理成 为突出的问题l l 引。 2 1 3 2 知识库系统如果一个系统具有能用计算机所存贮的知识对输入的数 据进行解释，生成作业假说并有对其进行验证的功能，则该系统称为知识库系 东北电力大学硕：l 学位论文 统。按照这个定义，知识库系统中的知识，是该系统在自身进行推理过程中所 利用的信息，而不是提供给系统使用者的信息。因此，知识库系统与数据库系 统不同之处就在于，它并非向用户提供检索的信息，而是提供根据输入的数据 信息使用知识进行判断分析的结果l l 引。 知识库系统的核心组成部分是知识库和推理机。知识库是以一致的形式存 贮知识的机构，推理机则是为了使用知识库藏内的知识执行推理的控制机构利 用知识，解释输入的数据或事实，推导出用户所需的结论；并根据要求，说明 得出结论的依据。知识库系统的基本组成如图2 - 2 所示。 图2 2 知识库系统的基本组成 其中知识库是用来存放知识的实体。在知识库中的知识具有无矛盾性和无 冗余性。知识库的存贮容量巨大，一般容量远远超过数据库的存贮容量。快速 的知识存取功能是知识库实现实用化的一个关键。推理机是利用知识的执行体， 是决定知识库系统性能好坏和工作效率高低的关键部件。知识库管理系统是知 识库建立、更新、维护、管理、使用的功能体。知识获取接口是完成从知识源 抽取的知识，通过向某一种知识表示语言的转换，并完成知识同化的功能部件。 用户接口是一种向用户提供使用知识库的手段，并向用户提供问题求解答案的 功能部件。 知识表示，知识利用和知识获取是知识库系统实现的三个关键技术问题。 第2 章相关知识及技术 知识采用什么形式表示，使计算机能对之进行处理，并以一种人类能理解 的方式将处理结果告知人们，这是知识库系统首先要解决的关键。知识表示要 具有层次化、模块化、网络化，统称为知识的结构化。 知识利用是指利用知识库中的知识进行推理，从而得出结论的过程。推理 所涉及的问题有：知识库的搜索、目标的控制、模式匹配的方法、推理的策略， 以及对不确定性知识的评价等。 知识获取是指从知识源获得知识来建造知识库的工作。知识库中的知识有 两个来源，一个是原始知识，由外界直接进入知识库；另一个是中间知识，是 由推理机生成后追加入知识库。 知识获取是知识库系统实用化中最难解决的一个关键，成为建立知识库系 统的一个瓶颈部分。目前在研究的解决该难题的各种对策方法中，利用计算机 学习来实行自动或半自动的知识获取是最理想的目标。 2 1 4 专家系统的智能一推理机制 专家系统根据一定的原则，利用存储在知识库中的领域知识，从已知的事 实推断出新的事实，即是专家系统的推理过程。 一个高性能的专家系统不但要拥有大量的专门知识，而且还要具有选择和 运用知识的能力。推理机作为专家系统的重要部分，其主要任务就是在问题求 解过程中适时地决定知识的选择和运用。推理的控制策略确定知识的选择，推 理的方式确定具体知识的运用。 专家系统中一般采用基于专门知识的推理，它以拥有知识为前提，而知识 在系统中有一定的表示模式，推理方式和控制策略在很大程度上依赖于知识的 表示模式，知识表示模式的不同决定了知识的选择和运用方式的不同，即推理 策略和推理方式的不同。其中，由于产生式专家系统应用最为广泛，基于产生 式规则的推理也得到了广泛的应用。 基于规则的专家系统在推理时主要涉及三个方面，即事实库、规则以及推 理控制策略 1 4 1 。 2 1 4 1 推理控制策略控制策略的作用是对下一步应选用什么规则进行决策， 东北电力大学硕十学位论文 也就是如何应用规则。通常从选择规则到执行操作有三个步骤：匹配、冲突解 决和操作。匹配就是把当前的事实库和规则的前提部分进行比较，如果两者完 全匹配，这条规则可以进行执行操作。当匹配成功的规则超过一条，系统就需 要决定优先使用哪一条规则，这即是冲突消解。选择出需要执行的规则之后， 系统就根据规则的结论部分对事实库进行操作，事实库随即出现变化，造成又 有其他规则可以匹配成功而得到执行。这样就形成了一个“选择规则一执行规 则的循环，自到满足结束条件或没有可用规则为止。 1 冲突消解【1 5 l 冲突消解策略解决如何在多条匹配成功的可用规则中合理 地选择一条进行执行，是一种基本的推理控制策略。 在专家系统的推理过程中，一种经常出现的情况是，在某个推理的中间状 态，规则的条件部分与事实库匹配成功的可执行规则不止一条，即发生“冲 突 ，就需要由推理机以某种机制来决定启用哪一条规则，称为“冲突消解 。 在通常的数学问题求解过程中，冲突消解策略采用深度优先或广度优先策略， 其主要思想是：先试用一条规则，如果在运用过程中出现失效，再回溯选择其 他规则。但在专家系统的应用环境中，这种策略往往表现出较低的效率。这是 由于专家系统求解问题的复杂性，企图试探每一种可能的求解途径，知识的检 索和选择的次数成几何级数的爆炸式增长，造成系统达不到某些应用的实时性 要求。因此，实际的专家系统往往采用一些比较简单直观的冲突消解策略，将 规则按优先级进行排序，常用的有： ( 1 ) 专一性排序如果一条规则的条件部分比另一条规则的条件部分更有针 对性，即一条规则条件是另一条规则条件的弱化，则弱化规则比强化知识具有 更高的优先级。 ( 2 ) 规则库组织次序排列规则在知识库中编排的顺序就表示了它的优先级， 则在问题求解过程中，一旦一条规则匹配成功即选择执行。 ( 3 ) 数据排序把规则的条件项按优先级进行组织，当冲突产生时首先使用条 件部分包含较高优先级数据的规则。 ( 4 ) 就近排序把最近使用的规则放在最优先的位置。这和人类的行为有相似 之处，即如果某一规则经常被使用，则会更加倾向使用这一规则。 ( 5 ) 分块组织规则库的组织按它们所对应的问题求解状态进行分块，在求解 第2 章相关知识及技术 过程中，只能从相应的规则中去选择可用知识。 ( 6 ) 数据冗余限制当一条知识的操作产生冗余事实时，则这条知识的优先级 降低，冗余事实越多，优先级越低。如果产生的事实全部为冗余事实时，则这 条知识为不可用知识。 冲突消解策略是一个基本的控制策略，在其他的控制策略中，往往都会涉 及到冲突消解策略。 2 正向推理控制策略正向推理又称自底向上控制、数据驱动控制、前向 链路推理等。它的基本思想是从现有事实出发，在规则库中寻找适合的规则并 进行执行。规则的执行造成环境发生改变，事实库中的信息发生了增减或修改， 进而导致先前部分不适用的规则变得可以被执行。系统不断重复这个过程，直 到得出结论或没有可用规则为止。 正向推理的主要优点是用户可以主动提供问题的有关信息，而不必等到系 统需要时才提供，这样可以对用户输入事实做出快速反应，而且可以求出全部 解。主要适用于“解空间”很大的一类问题，例如设计、规划、预测、监控、 管理等，其不足之处在于规则的启用与执行似乎漫无目的，求解过程中可能要 过多地执行许多与问题求解无关的操作，导致推理过程的低效。 3 反向推理控制策略反向推理又称自顶向下控制、目标驱动控制、后向链 推理和目标制导推理等。它的基本思想是先选择一个目标，然后在规则库中寻 找相关规则，依次检查这些规则的条件是否已经具备，即是否已经在事实库中 存在。如果某条规则的条件部分可以得到满足，则把该条知识的结论放入事实 库，即该目标被成功证明；否则把所缺的条件项作为新的子目标，递归上述过 程，直至子目标全部被证明，或者子目标不能进一步被分解且与事实库中的项 无法成功匹配为止i l 6 。 反向推理控制策略的优点是推理的方向性强，不用寻找和不必使用那些与 目标无关的信息和知识。这种策略对它的推理过程提供明确的解释，告诉用户 它要达到的目标以及为此而使用的规则；另外，这种策略在解空间较小的问题 求解环境下尤为合适。它的不足之处是初始目标的选择较为盲目，不能通过用 户自愿提供的有用信息来操作。对于解空间较大，用户要求做出快速输入响应 的问题领域，反向推理策略难以胜任。 东北电力大学硕七学位论文 2 2 决策树算法介绍 决策树方法是目前应用最广泛的归纳推理算法之一，是一种逼近离散值函 数的方法。它是以实例为基础的归纳学习算法，从一组无次序、无规则的事例 中推理出决策树表示形成的分类规则【1 7 】。到目前为止决策树有很多实现算法。 例如：由h u n t 等人提出的c l s ，由q u i n l a n1 9 8 6 年提出的i d 3 算法【1 8 1 和1 9 9 3 年提出的c 4 5 算法，以及c a r t 等等。 2 2 1 决策树的基本思想 决策树分类方法采用自顶向下的递归方式，在决策树的内部节点进行属性 值的比较并根据不同的属性值判断从该节点向下的分支，在树的叶节点得到结 论。因此从根到叶节点的一条路径就对应着一条合取规则，整棵决策树对应着 一组表达式规则。基于决策树的分类算法的一个最大优点就是它在学习过程中 不需要使用者了解很多背景知识，只要训练例子能够使用属性一结论式表示出 来，就能使用该算法来学习。 许多经典决策树是以信息论为理论基础。信息论是s h a n n o n 在1 9 4 8 年提出 的，为解决信息传递( 通信) 过程问题而建立的一系列理论【1 8 l ，也称为统计通 信理论，它以数学的方法度量并研究信息，通过对信源中各种符号出现的不确 定程度的消除来度量信息量的大小【1 9 1 。一个传递信息的系统由发送端( 信源) 、 接收端( 信宿) 和连接两者的通道( 信道) 三者组成。信息论把通信过程看作在 随机干扰的环境中传递信息的过程。在这个通信模型中，信息源和干扰( 噪声) 都被理解为某种随机过程或随机序列。 1 信息量也称为期望信息设局，局，为信源发出的信号，定义信 源发出信号的不确定性为信息符号的自信息量，其计算如公式( 2 - 1 ) 所示。 i ( x 。) = - l o g ( p _ f ) ( 2 一1 ) 其中尸f 信源x 发出的概率。 2 信息熵的概念信息量只反映符号的不确定性，而信息熵可以用来度量 整个信源整体的不确定性，定义如公式( 2 2 ) 所示。 第2 章相关知识及技术 日( x ) = 一p ，l o g ( p i ) ( 2 2 ) ，= l 3 条件熵在信源x 与随机变量】，不是相互独立的情况下，可以用条件熵 ( 册) 来度量收信者在收到随机变量】，之后，对随机变量x 存在的不确定性。 设对应信源符号巧，当p ) 表示y j 为时的概率，其条件熵计算如公式 ( 2 - 3 ) 所示。 日( 州】，) = 一y p ( x ，y j ) l l o g ( x ，艺) ( 2 3 ) i f f i l t l 4 平均互信息量用来表示信号】，所能提供的关于x 的信息量的大小，其 计算如公式( 2 - 4 ) 所示。 i ( x ，】，) = 日( x ) 一日( 驯y ) ( 2 4 ) 信息论中是用熵来度量信息的不确定性，在决策树中是作为训练集纯度的 标准。在计算信息熵底时候，由于信息编码是用二进位编码，所以对数函数以2 为底。决策树建立过程中，最主要的部分是对分裂属性的选择。比较常用的一 种方法是计算信息增益即使某个属性用来分割训练集而导致的信息熵降低。因 此，信息增益大的属性，被选择作为分裂属性底可能性大。决策树的形成就是 递归的对数据集中的每个节点进行分裂，直到没有可分裂的属性或所有叶子节 点的数据集都属于同一类。 2 2 2 决策树生成算法 决策树是采用自顶向下的递归方式，在它的内部节点进行属性值的比较并 根据不同的属性值判断从该节点向下的分支，最后在决策树的叶节点得到结论， 整个过程都是以新节点为根的子树上重复。 其生成算法g e n e r a t ed e c i s i o nt r e e 2 川描述如下： 输入：训练样s a m p l e s ，由离散值属性表示：候选属性的集合a t t r i b u t el i s t 输出：一棵决策树 1 创建节点n ； 2 i fs a m p l e s 都在一个类c 东北电力大学硕士学位论文 返回n 作为叶节点，以类c 标记； 3 i f a u d b m el i s t 为空 返回n 作为叶节点，标记为s a m p l e s 中最普通的类； 4 选择a t t r i b u t el i s t 中具有最高信息增益的属性t e s ta t t r i b u t e ； 5 标记节点n 为t e s ta t t r i b u t e ； 6 f o re a c ht e s ta t t r i b u t e 中己知的值a i 由节点n 长出一个条件为t e s ta t t r i b u t e = a i 的分支； 7 设s i 是s a m p l e s 中的t e s ta t t r i b u t e = a i 的样本集合； 8 i fs i 为空 加上一个树叶，标记为s a m p l e s 中普通的类； 9 e l s e 加上一个由g e n e r a t e _ d e c i s i o n _ t r e e ( s i ，a t t r i b u t e _ l i s t ，t e s u a t t r i b m e ) 返回节 点： 决策树是一个类似流程图的树型结构，其中每个内部节点表示在一个属性 上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树 的最顶层节点是根节点。 从整棵树的角度来看，通常决策树代表实例属性值约束的合取的析取式。 从根到树叶的每一条路径对应一条合取规则，树本身是这些合取规则的析取。 因此决策树很容易转换成分类规则。 2 2 3 决策树的修剪算法 在建树过程中，由于数据集中的噪声、孤立点以及某个节点的数据量太小， 决策树的许多分枝反映出训练集中的异常，也就是决策树的过度拟合问题。它 表现为用某些分类规则对训练集预测十分准确，而对测试集进行预测时，误差 极大。剪去决策树的冗余分枝是解决过度拟合问题的重要方法。剪枝的过程是 从根节点以下开始，测试所有的内节点，一旦某个内节点下的子树被剪除，该 内节点以下的其它内节点不用再测试。剪枝利用统计学方法，去掉最不可靠或 可能是噪音的一些分枝。剪枝方法分为两大类口1 】： 1 预先剪枝也称前修剪前修剪策略是边建树，边修剪。前修剪需要在建 第2 章相关知识及技术 树的过程中决定何时停止建立子树，信息增益或者某些有效统计量达到某个预 先设定的标准时，节点不再继续分裂，成为一个叶子节点。该策略能避免建立 某些子树( 将来要被舍弃的子树) 所需的全部工作。 2 后剪枝也称后修剪后修剪策略是先建树，后修剪。后修剪是一种拟合 一化简( f i t t i n ga n ds i m p l i f y i n g ) 的两个阶段方法。首先生成与训练数据完全拟合 的一棵决策树，然后从树的叶子开始剪枝，逐步向根的方向剪。剪枝时要用到 一个测试数据集合( t u n i n gs e to ra d j u s t i n gs e t ) ，如果存在某个叶子剪去后能使得 在测试集上的准确度或其他测度不降低，则剪去该叶子，否则停止。 理论上讲，后剪枝好于预先剪枝，但计算复杂度大。选择合适的剪枝评估 标准是确定正确决策树的关键。 通过设备管理系统，有效地对资产投资、使用维护、维修、更新改造和折 旧报废的每一个阶段进行经济分析、经济评价，采用量化的观点，用数字说话， 建立模糊比较，促进管理透明化、清晰化，提供管理效率。 2 2 4 经典决策树算法的简介 1 id 3 算法的简介 自从q u i n l a n 在1 9 8 6 年描述和分析i d 3 算法以来，有 大量的学者围绕该算法作了非常广泛的研究。目前为止有很多种算法都是围绕 决策树的核心算法i d 3 演变而来的。i d 3 是基于信息熵的决策树分类算法，该算 法是根据属性集的取值选择实例的类别，它的核心是在决策树中各级节点上选 择属性1 2 2 。i d 3 算法的基本原理如下： 设s 是包含s 个样本数据的集合。假定类标号属性有m 个不同值，定义m 个 不同的类g ( 卢1 ，2 ，m ) 。设研是类g 中样本的个数。给定样本的期望信息的 计算如公式( 2 - 5 ) 所示。 j 已 ，( _ ，8 2 ，s 所) = 一p fl o g ( p i ) ( 2 5 ) l = i 其中，p ，是任意样本属于c f 的概率，一般用s s 来估算。 设属性a 具有，个不同值 口，a 2 ，a v 。利用属性a 将s 划分为v 个子集 s f ，& ，母) ，s 是在属性么上具有值a ，的样本。如果把彳作为分裂属性，则 东北电力大学硕士学位论文 由彳划分成子集熵的计算如公式( 2 - 6 ) 所示。 e ( 么) = 一当旦二! 学，( s 。j ，j ：j ，s 彬) ( 2 - 6 ) 其中，勋是子集母中类c f 的样本数，( s l j + 蚴+ + s i i l j ) s 充当母的权。对于给定 的子集s 的期望信息的计算如公式( 2 7 ) 所示。 棚 i ( s l j s 2 ，) = 一p ，l o g ( p ，) ( 2 7 ) i = 1 其中p 芦朽，是母中的样本属于类g 的概率。 由期望信息和熵值可以得到对应的信息增益