CBR研究综述

基于案例推理的研究综述张怀鹏[e-mail]航天学院控制科学与工程系近几年来，面对传统人工智能知识获取的局限，基于数据挖掘和分析的计算智能成为一个新的发展方向。同时，基于相似性的推理越来越受到人们的重视，从而出现了基于案例推理（case-basedreasoningCBR）的方法。基于案例的推理方法具有简化知识获取、提高问题求解效率，改善求解质量、进行知识积累等优点，提供了与人类解决问题相当近似的一种方法。引言基于案例推理的研究历史只有二十余年，和基于规则的推理、神经网络等相比要短很多，但是发展却异常迅猛。在欧美地区，自从基于案例推理方法出现以来，无论在学术领域还是实际的应用领域都开展了积极的研究工作，出现了一些学术上的研究模型和众多的商业化系统。这些领域涉及故障诊断、决策支持、客户服务、计划、法律、推理、统计、类比推理、仲裁、教学指导等领域。这些领域有一个共同的特点：没有很强的理论模型、领域知识不完全、但经验知识丰富。在CBR的研究方面,1991年德国率先召开了第一届CBR专题研讨会,以后每年一次。从1995年开始,英国每年也举行一次。欧洲对CBR的研究主要侧重于专家系统的开发和知识获取方面,开发了许多应用系统,如基于案例的规划系统CAPLAN、基于案例的医疗诊断学习系统TCST和基于案例的专家系统开发工具RBCShell等，其中医学领域的CBR系统研究较多且较为完善。人工智能刊物(如AIMagazine、IEEEExpert)发表了许多有关CBR的论文。国内在CBR的研究和应用开发方面起步较晚,主要在基础理论方面做了一些研究工作,同时在方案设计、故障诊断和决策支持等应用领域也开展了一些探索性研究。图1基于案例推理应用领域—基于案例推理的简介—简单的例子用于说明—案例推理的研究状况及当前研究热点—总结与展望报告结构CBR简介CBR是一个问题求解范例（problem-solvingparadigm），其历史可以追溯到20世纪70年代后期，它起源于认知科学（cognitivescience)。CBR可以用一句话来解释（著名的CBR假设）：Similarproblemshavesimilarsolutions.相似问题具有相似解。这个假设的基本思想是，通过重复使用过去的类似问题的解决方案来解决当前问题。因此，当前问题必须和案例库中描述的问题进行比较，案例库中与当前问题相类似的问题的解决方案是我们解决当前问题的候选方案。我们在日常生活中的很多情形下都会使用这个问题求解技术。任何时候，只要是重复使用经验比较容易或者更方便，人们就会这样做，而不是白手起家推导出新方案。如：医生诊断我们当前症状时，回想起曾经的一个病人也有类似的症状。治愈这个病人需要青霉素，于是医生给我们确定的治疗方案也是注射青霉素。律师接手我们的案件后，会在查阅大量曾有相似案例的起因、发展和结果来确定当前案例的辩护方案并预测审判结果。CBR模仿人类的这种问题求解行为。当难以把领域规则形式化且案例可用时，就应该考虑这种方法。当规则可以形式化，但是问题描述不完整，或者在问题求解时所需知识超出现有知识储备的范围，也应该考虑这种方法。可见，在问题内部机理和主要影响因素认识尚不清楚、信息不完备的领域，CBR能够较好地弥补基于专家系统和模型的方法存在的不足，从而与基于专家系统和模型的推理方法形成良好的互补。CBR的前提是要建立一个基于已有经验的案例库。根据具体领域或者具体提问的特点，每一条经验被表示成一个案例。一个案例包括对几个提取特征的描述,以及相应案例的解决方案，类似于人解决新问题的思考过程。CBR的原理是基于已有的经验，从中搜索和新问题相似的案例，然后根据相似案例的解决方案作适当的调整来得出新问题的处理方案。可见,在CBR的整个过程中,主要包括以下几个重要的组成部分：案例的表示案例的搜索案例解决方案经调整和适应以便重用新案例的增量式学习及案例库维护CBR优势1）以案例作为基本知识元，直接援引过去相似案例的经验进行推理，与基于专家系统和基于模型的方法相比，知识获取的难度大大降低；2）能够较好地处理信息不完备情况下决策的不一致。基于案例的推理方法利用相似案例进行推理，在信息不完备情况下，相似案例的决策同样是最具参考价值的决策。而基于专家系统和基于模型的方法若要描述信息不完备情况下决策的不一致，需要规则或模型的结构形式较为复杂（如需要较多的规则、或需要较复杂的模型），按照人工智能领域统计学习理论的研究成果，过于复杂的模型将会导致方法泛化性能的急剧下降；3）增量学习表现为新案例的增补，容易实现。新产生的案例通过简单的加工和整理就可以增补到案例系统中，供以后推理使用，随着历史案例的不断增加，系统的智能程度将会不断提高。相比而言，基于专家系统和基于模型的推理方法的增量学习算法较为复杂。归纳总结：什么是CBR？——存储过去的案例以建立案例库——解决新问题1.从案例库中检索（retrieve）相似案例2.在当前问题情境下，重复使用（reuse）过去相似案例的解决方案。全部利用，部分利用，或者根据当前问题和过去问的差异对解决方案进行调整（revision）3.将新案例存储（retention）在案例库中图2CBR过程图CBR推理过程主要分为四个阶段：案例检索(retrieval)、案例重用(reuse)、解决方案修正(revise)和案例保存(retain),又称4-R生命周期模型4-R生命周期模型换言之就是：依靠CBR解决问题包括问题描述，现有问题和过去案例的相似性度量，检索一或多个相似案例，尝试重用案例，如有必要对重用案例解决方案进行调整以减少新旧案例差异性造成的影响，经调整后的方案经系统评估（例如专家评估或依据解决新问题有效性的评估），解决方案经修正并决定应用后，依据其重要程度和原有案例的重复程度将新案例准备描述后存储在案例库中。1.案例的表示已有的知识或者经验需要被表示成一个案例库，CBR才能在此基础上发挥作用。一个案例一般可以表示成一个特征值向量的形式。例如：一部数码相机的价格是由它的品牌、像素多少、光学变焦倍数等等因素决定，那么品牌、像素以及光学变焦就可以作为特征从问题的特征空间里提取出来，用以描述具体每个相机的特征，从而决定它的价格。以索尼相机为例,如果已知它的像素是400万,光学变焦是3倍,价格是3000元,那末这样一条经验就可以表示成一个案例,即一个特征值向量,可以表示成二维图表。图3用特征值向量表示案例一个简单甚至粗糙的例子2.特征的提取通常案例中的描述性特征被称为特征属性，例如上例中的品牌、像素和光学变焦。案例的结果或者决策方案被称为决策特征。然而，要确定问题的特征属性，必须对问题有很清楚地了解。对一些比较复杂的问题例如某些控制过程，人们又往往缺乏足够的认识，从而造成不能正确的抽取特征属性以至不能用案例准确地描述以往的经验。由于CBR是完全基于经验基础之上的，如何正确的提取特征和准确的案例表示就显得尤为重要。2.特征的提取图4􀀁经过特征抽取后案例的表示特征提取既减少了存储的空间要求，又更精确的描述了属性特征和决策特征之间的关系。那些与决策不相关的属性被去掉了，从而提高了CBR的抗噪能力。在机器学习中，特征提取（FeatureSelection）一直被视为一个重要的课题作了广泛的研究。根据不同的问题的特性，很多不同的方法已经应用到了特征提取中，例如神经网络，大多数研究都是通过确定在特征空间的特征权重来衡量每个特征的重要性。在图2的例子中，假定相应的特征空间是由品牌、像素以及光学变焦组成的三维空间。如果通过一定的学习算法，这三个特征对应的权重分别为0.65,0.3,0.05，那说明前两个属性特征是比较重要的，相比之下第三个属性特征对决策特征价钱的影响是可以被忽略的。因此，在经过特征抽取以后,图3中用三个属性特征表示的案例就可以只用两个特征属性来刻画了，即3.案例库确定了属性特征以后，每一条以往的经验都可以比较精确的表示成一个案例，从而形成一个案例库。下面的表格就表示了一个案例库的例子。图5案例库4.案例的搜索给定一个未知的问题，我们现在描述如何利用CBR的方法来找出解决方案或者做出相应的决策。4.1问题的表示首先，要把这个给定的问题也表示成案例的形式，称为问题案例，如图4。根据CBR的原理，要解决新的问题，就是从案例库中找到与问题的特征值向量最相似的案例，然后用相似案例的结果来作出决策，拿上面的例子来说，现在要估计相机的价钱，那么就要从案例库中找到与问题案例最为相似的案例，可以看出，这里就需要给出一定的相似度的衡量方法。图6问题案例4.2相似度度量在搜索与问题最为相似的案例时，很多基于距离的相似性的计算方法已被广泛地采用。距离越大说明相似度越小。距离度量如加权欧式距离，马氏距离等。4.3相似度计算假设我们运用距离度量计算出的问题案例和案例库中各案例的相似度分别为3，2，1，4，5。5.决策的调整和确定根据计算出的相似度，可以在已知案例库中找到与所给问题最为相近的案例，从而为解决新问题提供了参考和依据。在最后决策的确定中，往往采用最近邻原则(nearestneighborrule)。即把最相似的案例的解决方案作为新问题的决策。例如在4.3中，与所给问题最相似的案例是[CANON3202500]，那么根据最近原则，对SONY牌子,400万像素的数码相机的估价就是2500元。但是这里存在的问题就是，给出这个估价的相机的品牌是CANON而不是SONY，因为品牌是非常重要的一个因素，所以这里我们可以对这个决策做出适当的修改：在品牌是SONY的案例里面再取一个与问题最为相似的案例，即[SONY3342350]，然后这两个相似案例的平均价格(2500+2350)/2=2425做为最后的估计价格。5.决策的调整和确定这里需要说明的是，对决策的修改或者调整是针对不同问题的特点而进行的，没有一个统一的方法或者规则。除了最近原则,被广泛应用的还有KNN原则。它与最近邻原则相似，只不过问题的决策不是由最相近的那一个案例的结果给出，而是由k个最相似的案例的解决方案共同给出。例如在上面的例子里,采用3-近邻原则,即取三个与问题最相近的案例。最后的估计由三个价格的平均给出：(2500+2350+2950)/3=2600。6.新案例保存最后做出对问题案例的决策后，将其作为以个案例加入到案例库中，实现增量式学习。图7上述过程总结Allen设计了一种针对专用计算机的故障诊断系统,存储几十万个与Compaq公司计算机产品相关的故障案例,用于为客户提供技术支持服务。当客户的计算机系统出现故障时,通过输入故障现象的简单描述,诊断系统能够从案例库中查找出相似的故障案例,帮助售后服务人员快速、有效地为客户提供故障解决方案。系统的应用评估表明,使用该系统后产品故障的一次解决率从原来的50%提高到87%。CBR成功案例Geng等人针对大型通信网中骨干网结点的故障诊断问题,设计了一种CBR网络故障智能诊断系统。将以往网络出现故障时的路由器工作状态、工作站网络配置数据及修复措施等资料整理加工成故障案例,采用遗传算法确定案例特征项的权重系数。在此基础上,采用密度聚类方法提高了案例检索的效率,运用知识约简实现了案例的重用,在应用中达到了对网络故障智能诊断的目的。裴艳香（哈工大）以基于CBR的诊断方法为基础,研发了一个已经投入运行的卫星测控系统在线监测与故障诊断系统。该系统提出了一种面向对象的故障案例表示方法,引入抽象案例的概念,建立了故障案例对象的层次结构模型;在故障案例的检索机制中,提出了基于模糊划分的定量特征相似度评估模型及组合赋权的权重确定方法,结合基于最近邻的案例检索方法,缩小了检索空间,提高了检索效率。王波提出了利用机载监测系统BIT(builtintest)信息库完成飞机故障诊断的CBR方法,采用框架作为飞机故障案例的表示方法,利用粗糙集对案例的故障征兆进行约简,并计算征兆值对于它所表示的BIT信息的重要度,进而根据征兆的重要度设计检索匹配策略。在此基础