（系统工程专业论文）基于CBR的技术推广研究与应用.pdf

华中科技大学硕士学位论文 摘要 我国小城镇建设工作一直进行着有益的尝试和探索，在全国不同地区相继抓了 很多试点小城镇，但试点在技术推广中没有发挥预期的作用。其主要原因是试点成 功的技术应用项目没有真正发挥指导、示范作用。如果以小城镇试点、示范工程项 目为背景，从试点的成功技术应用案例中找到与自己所要解决的问题具有相似性的 历史经验，则对技术推广具有极大的现实意义。 本文着眼于小城镇建设中的技术推广问题，利用基于案例推理的方法，通过对 新问题与历史技术应用案例在不同方面的相似性度量，研究技术选择与推广的量化 标准。决策者可以通过类比以往应用案例，找出与自己实际应用需求最相似的部分 解或相对合适的整体解，为技术推广提供决策支持。 本文首先介绍了我国小城镇中的主要问题和技术推广的相关概念与理论，并对 基于案例推理的一般方法、主要任务及相似度量算法的主要研究成果做了介绍和简 要分析。 案例表示是基于案例推理的基础。围绕规范化技术应用案例表示的问题，本文 结合小城镇可持续发展理论、技术的综合评价等分析了技术应用案例的特点，建立 了技术应用案例框架表示的层次模型，并对案例描述信息不完备的情况进行处理。 针对不同框架信息特点的不同，采用粗糙集和专家咨询法确定特征属性的权重。相 似度量是基于案例推理的关键环节。本文分析案例的属性并归纳为四神类型，针对 不同类型的属性，分别采用海明距离、基于模糊集合隶属函数的相似度算法来计算 案例的局部相似度。并利用最邻近算法得到案例的框架相似度排序和案例的全局相 似度排序。通过相似度的大小来反映历史案例的参考价值大小。 此外，结合小城镇污水处理厂建设问题的实际背景，设计了基于c b r 的相似案 例查询系统，说明在技术推广中应用基于案例推理中的相似度量，为决策者提供了 大量的支持信息，可使决策者在技术选择上更具灵活性，提高技术推广的效率。 关键词：小城镇建设，技术推广，c b r ，相似性度量，粗糙集 华中科技大学硕士学位论文 a b s t r a c t c h i n ah a sd o n em u c hw o r ki ns m a l l - t o w nc o n s t r u c t i o n g r e a ta m o u n to fv a r i o u s e x p e r i m e n t a l s m a l l - t o w n sh a v eb e e ne s t a b l i s h e di nd i f f e r e n ta r e 丛b u tt h e yd i dn o t a c c e l e r a t et e c h n o l o g ye x t e n s i o n o n em a i nl a s o ni st h es u c c e s s f u lt e c h n o l o g ya p p l i c a t i o n p r o j e c t si ne x p e r i m e n t a ls m a l l - t o w n sd on o tp l a yt h er o l e o fd i r e c t o ra n df a g l e m a n i f h i s t o r i c a lt e c h n o l o g y a p p l i c a r o n s t h a th a v es i m i l a r i t ya n dc o r r e l a t i o nw i t ht h en e w a p p l i c a t i o np r o b l e m c o u l db ef o u n d , t h e p a c eo f t e c h n o l o g ye x t e n s i o n w i l lb e s p e e du p a i m i n ga t t h et e c h n o l o g ye x t e n s i o ni n s m a l l t o w n s ，i ti sn e c e s s a r yt o s e t u pa m e c h a n i s mo rs t a n d a r do f d e c i s i o n s u p p o r t i nt e c h n o l o g ys e l e c t i o n t h i st h e s i sp r o p o s e st o u s ec a s e - b a s e dr e a s o n i n gt h e o r yt oh e i pd e c i s i o nm a k e rc h o o s et h ep r o p e rt e c h n o l o g y t h r o u g hm e a s u r i n gt h es i m i l a r i t yb e t w e e nn e o np r o b l e ma n dh i s t o r i c a lc a s e s ，d e c i s i o n m a k e rc a na c q u i r et h e p a r to rw h o l e s o l u t i o no f a c t u a lp r o b l e m t h i st h e s i si n t r o d u c e st h ed i f f i c u l t yo fs m a l l - t o w nc o n s t r u c t i o na n db a s i ct h e o r yo f t e c h n o l o g ye x t e n s i o n ，t h e n i t r e p r e s e n t s t h e s t u d y i n g s t a t u sa n dm a i np r o d u c t i o no f c a s e - b a s e dr e a s o n i n g t h e o r y a n dt h ea l g o r i t h mo f s i m i l a r i t ym e a s u r e c a s ee x p r e s s i o ni st h eb a s i so fc a s e b a s e d r e a s o n i n g t h i st h e s i sa n a l y z e s t h e c h a r a c t e ro ft e c h n o l o g ya p p l i c a t i o nc a s e sr e f e r e n c i n gt h es u s t a i n a b l ed e v e l o p m e n tt h e o r y o fs m a l l t o w nc o n s t r u c t i o na n dt h e t e c h n o l o g ya s s e s s m e n t ，e s t a b l i s h e s t h e h i e r a r c h y e x p r e s s i o nm o d e lo ft e c h n o l o g yc a s eb a s e do nf r a m e w o r ke x p r e s s i o nm e t h o da n dd e a l s w i t ht h ei n c o m p l e t ei n f o r i n a r o ni fi to c c u r s t h e n ，t h i st h e s i ss u g g e s t su s i n gr o u g hs e t t h e o r ya n dd e l p h im e t h o dt oc a l c u l a t et h ew e i g h to fa t t r i b u t e s s i m i l a r i t ym e a s u r ei st h e k e yp r o c e s so fc a s e - b a s e dr e a s o n i n g a c c o r d i n gt ot h ef o u rd i f f e r e n tt y p e sa t t r i b u t e si n c a s e s ，t h i st h e s i su s e sh a m m i n gd i s t a n c ea n dt r a p e z o i d a lf u n c t i o no ff u z z ya t t r i b u t e st o r e a l i z el o c a ls i m i l a r i t ym e a s u r e ，a n du s e st h en e a r e s tn e i g h b o rt oc a l c u l a t et h eo v e r a l l s i m i l a r i t y t h es e q u e n c ea c c o r d i n gt h es i m i l a r i t i e so fe v e r yc a s ef r a m e w o r ka n dt h ew h o l e c a s ec a l c u l a t e dt h r o n g hn e a r e s t n e i g h b o ra l g o r i t h mr e p r e s e n tt h er e f e r e n c ev a l u eo ft h e s e h i s t o r i c a lc a s e s 华中科技大学硕士学位论文 f i n a l l y , b a s i n go ns i m i l a r i t ym e a s u r ei nc a s e b a s e dr e a s o n i n g ，as i m i l a rc a s e sq u e r y s y s t e mi sd e s i g n e d a n di ti l l u s t r a t e si t sf e a s i b i l i t yi nt e c h n o l o g ye x t e n s i o nt h r o u g ha d e t a i l e d e x a m p l e - s e w a g e f a r mc o n s t r u c t i o n p r o b l e m ，a n dp r o v i d e sm u c hh e l pa n d f l e x i b i l i t y i nt e c h n o l o g ys e l e c t i o na n de x t e n s i o n k e y w o r d s ：s m a l l - t o w n c o n s t r u c t i o n , s i m i l a r i t ym e a s u r e ， t e c h n o l o g ye x t e n s i o n , c a s e b a s e d r e a s o n i n g ， r o u g h s e t 【1 l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出 贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明 的法律结果由本人承担。 学位论文作者签名： 殇明 日期：妒4 年f 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密囱。 ( 请在以上方框内打“4 ”) 学位论文作者签名：隽p a 日期：w 串年r 月? 日 指导教师签名：貌群云 日期：m 4 年s 月( 日 华中科技大学硕士学位论文 1 1 课题来源 1 绪言 近年来，各种先进适用技为贯彻落实“小城镇，大战略”的战略精神，探索适 用于我国小城镇的发展模式；小城镇试点、示范工程作为科技攻关项目“居住区与 小城镇建设关键技术研究”中各课题研究成果的实施载体，以科技创新、科技经济 一体化和为支柱产业服务为宗旨，将实现“以人为本”、可持续发展原则，以功能、 质量、环境、健康和资源等指标的综合提高为方向，立足当前，适当超前，建立一 批不同类型的小城镇样板工程，辐射带动周边及区域小城镇建设。 本课题为国家科技攻关项目“小城镇试点、示范”项目之子课题先进适用 技术评估与推广。小城镇建设的相关研究成果是否适合我国小城镇建设的实际情况， 只有对这些研究成果加以评估选择后，在试点、示范工程建设实践活动中加以验证， 并逐步推广应用，这些研究成果和技术才能真正转化为现实生产力，促进我国小城 镇建设技术水平的提高。在先进适用技术的选择上，需要考虑小城镇现有的经济实 力和本身的特点优势。全国范围内，很多先进适用技术都在陆续投入实践，其转化 为生产力并服务广大群众的程度不同。如果在做出技术选择前，能够参照相似的应 用案例，对小城镇的建设具有极大的指导作用，可以大大减少投资规划的盲目性， 提高技术转移的效率。 1 2 选题背景与意义 我国小城镇建设工作。直进行着有益的尝试和探索。近年来，各种先进适用技 术与产品应运而生，取得了很大的成绩，为小城镇建设奠定了较好的基础。全国不 同地区相继抓了不同类型、不同功能和不同规划建筑风格的示范小城镇，为我国小 城镇建设提供了科学的示范，带动了全国小城镇建设快速健康发展。截至1 9 9 7 年底， 全国共计建设试点的建制镇5 8 3 0 个，集镇1 9 4 7 个，村庄建设试点9 2 4 5 个。仅从试 点的数字上看，可以说体系庞大、层次分明，但是真正具有推广意义的试点小城镇 还很少。其主要原因是以往试点成功的技术应用项目没有真正成为普遍意义上的具 l 华中科技大学硕士学位论文 有指导性的经验。 大量的先进技术成果在试点城镇的试用固然有其成功的可能性，但是如何将这 些先进技术推广、应用并转化为现实生产力，特别是因地制宜的推动小城镇建设是 一个重要的问题。小城镇的特点各不相同，需求技术根据应用地点的实际情况也有 所限制，如果以小城镇试点、示范工程为背景，从试点的成功技术应用案例中找到 与自己所要解决问题具有相似性的应用经验，则对技术推广具有极大的现实意义。 本文利用基于案例的推理的方法，通过对新问题与历史技术应用案例在不同方面的 相似性度量，根据案例间相似匹配，研究先进适用技术选择推广的量化参考标准。 决策者可以通过类比以往应用案例，找出满足自己应用需求的部分解或相对合适的 整体解。 本课题的研究正好为解决因地制宜的推动小城镇建设这一问题提供了有力的支 持。小城镇建设是国家“十五”计划的重点内容之一，因此受到各级政府的高度重 视。本课题的研究成果可以满足有关部门对小城镇建设管理的需要，在技术推广和 指导小城镇建设方面做出了有益的探索。 1 3 国内外研究现状 1 3 1 小城镇建设 小城镇建设问题是经济体制改革和发展农村商品经济的客观需要，是从我国农 村经济改革实践中提出来的一个具有重要现实意义的问题。这个问题关系到：一是 小城镇的兴衰存亡直接影响到农村商品经济能否发展；二是小城镇的兴衰存亡，直 接影响到我国农村存在的几亿剩余劳动力的出路问题【”。其意义和作用远不止这两 点，更重要的是关系到中国农村现代化的大问题，也是关系到建设有中国特色的社 会主义事业成败的大问题。 全球的城镇化发展势头猛烈并且持续，城镇人口比例占总人口的比例不断上升， 而且城镇化的水平与各国经济发展的水平具有同步性 2 1 。1 9 7 8 年1 9 9 9 年，我国城镇 化水平由1 7 9 2 提高至l j 3 0 9 ，提高了1 2 0 8 个百分点，年均增长0 6 2 个百分点， 是前2 9 年我国城镇化速度的2 5 倍，世界同期城镇化平均速度的两倍，我国已步入城 镇化的加速时期。当前小城镇发展的主要问题是4 】： 2 华中科技大学硕士学位论文 1 小城镇规模小，建设资金短缺，区位优势和产业优势不突出； 2 小城镇规划布局水平低，宏观规划布局尤其薄弱； 3 资源利用效率低，闲置浪费现象严重； 4 对小城镇发展的分类指导亟待加强。 二十一世纪的竞争是科学技术的竞争，小城镇的发展也离不开这个大环境，或 早或晚，或多或少，高科技进入小城镇是大势所趋【5 1 。在社会的经济发展当中，技术 选择要以本国的民族特点、文化历史条件、教育程度、技术水平为依据，从本国、 本地的资源和劳动力状况出发，按生态环境和社会所提出的要求，考虑经济的合理 性、技术的可行性以及现阶段发展的特点，因地制宜地选择在某特定的时期内适用 于某种技术一经济一社会结构的技术，使之既满足本国经济发展对新技术的需要，又 符合本国生产要素的现状、市场规模、文化社会环境、技术能力、经济条件等，使选 择的技术效果最佳。正如美国学者沙赫特指出：“技术选择的基础不仅仅是技术的考 虑和论证：而且应包括经济、文化、环境、能源和社会的标准【6 l 。” 本文对技术推广的研究必然离不开小城镇这一应用环境，小城镇的建设发展有 其本身的要求。因此根据小城镇可持续发展理论和区域发展理论，依照小城镇本身 因地制宜加大技术投入的要求，结合技术评价的和城市化评价指标，分析技术应用 案例中应用地区的特点，研究先进适用技术的适用条件的统一规范表示。 1 3 ，2 技术推广 技术运动是技术在时间序列中发育成长并在空间范围内扩散传播的过程，即技 术的纵向运动和技术的横向运动 9 1 。技术推广是一个广义概念，可以理解为技术的横 向运动，侧重反映技术发展在空间上的并存性和广延性，强调技术成果向现实生产 力的转化和应用地域范围上的扩大。与技术推广相关的概念还有技术转移、技术扩 散。 技术转移概念于本世纪六十年代提出，最初是作为解决南北问题的一个重要战 略。从技术转移微观主体来看，转移的动力来源于： 1 市场需求、商品竞争和技术竞争： 2 科技发展产生的“内推力”； 3 国家经济与科技计划、税收、法规政策等对主体产生的“外推力”： 3 华中科技大学硕士学位论文 4 技术价值升高，对经济发展的重要性形成“活力”【7 】o 技术扩散首先是指技术的国内传播过程，主要是考虑科学技术成果转化为商品 以实现其向经济价值的转化，以及随后向产业化、国际化的发展过程【l l l 。 目前，关于技术转移的政策、战略及适于发展中国家的技术转移模式等研究正 在成为新的研究热点。关于技术转移政策研究，较成熟的理论有拉格曼、巴克利、 卡森为代表的技术内部化理论和比昂契克、贝托索斯的技术从属论。技术转移理论 研究可分为三种战略：延长技术生命周期战略：扩大技术效用战略：找出路战略。 在发展中国家技术转移的适宜模式研究上，较具代表性的是围绕英籍德国人舒马赫 的“适宜技术”而展开的梯度发展模式与跳跃发展模式【1 1 】。 1 3 。3c b r 研究所史与现状 基于案例推理是人工智能领域中的一种解决问题的方法，它强调把当前面临的 问题或情况作为目标案例或新案例，而把过去记忆中的问题或情况作为案例或称为 历史案例，通过目标案例的提示获取记忆中的历史案例，并由历史案例指导目标案 例进行求解的一种决策。旱在1 9 8 2 年r o g e rs c h a n k 在动态存储器技术方面的研究 中就发现，过去的一些状态对问题的解决和学习有重要的作用。最早的一个c b r 系 统叫做c y r u s p “，是在1 9 8 3 年由j a n e tk o l o d n e r 在耶鲁大学开发的，它是基于s c h a n k 的动态存储器模型而开发出来的，它是一个问答式的专家系统，主要处理对前美国 国务卿c y r u sv a n c e 的各种旅行和会议的查询。它成为以后的许多c b r 系统的基础， 许多科学家从不同角度对基于案例推理进行了大量的理论研究f 1 3 】，如：m e d i a t o r “1 ， p e r s u a d e r 5 3 1 ，c h e f 6 5 1 ，j u l i a 6 6 1 ，c a s e y 6 ”。c b r 的另外一个重要基础是1 9 8 9 年b r u c e p o r t e r 在德克萨斯州立大学所提出并发展的机器分类学习的概念，他提出把领域知 识和特殊的实例综合成为一个统一的表达方式，并开发了p r o t o s 鸪1 系统。另外一个 对c b r 做出显著贡献的系统是h y p o 系统汹1 ，它是由麻萨诸塞州立大学的e d w i n a r i s s l a n d 小组开发的一个法律案例系统，在这个系统中实例不单用来得出一个简单 的结论而用来解释和评估结论。以及后来结合基于范例和基于规则方法的c a b a r e t 系统【7 0 ) 。 在欧洲c b r 的研究要比美国晚一些，它的c b r 的研究主要跟专家系统和知识获 取有关。最早的系统是由k a i s e t s l a u t e m 大学的m i c h a e lr i c h t e r ，k l a u sd i e t e r 4 华中科技大学硕士学位论文 a l t h o f f 等人开发的m o l t k e 系统川和p a t d e x l 7 2 】，用于复杂的技术诊断。 可以看出，8 0 年代中后期，c b r 的研究开始迅速发展。我国的在这一领域的研 究相对落后，离质量的论文较少。应用处于初级阶段。近年来，我国对c b r 的研究 也逐渐重视加强。中科院计算机数研究所智能计算机开放实验室在基于案例推理方 面进行了一系列的研究 1 4 1 。1 9 9 1 年李宝东、史忠植提出了记忆网模型和范例检索算 法。1 9 9 3 年周涵研制了基于范例学习的内燃机油产品设计系统e o f d s 。1 9 9 4 年徐众 会开发了基于范例推理的天气预报系统。1 9 9 5 年赵铜开发了基于范例推理技术的降 水过程预测系统。1 9 9 6 年王军开发了基于范例推理的淮河王家坝洪水预报调度系统 f o r e z 。 随着c b r 研究的深入，c b r 系统有着广泛的应用领域，如： 1 诊断，即在历史档案中找出与新问题具有相似特征的档案，根据最符合的档 案对新问题提出诊断建议。以医疗诊断和法律案件判决为代表。 2 评估，即通过与已有相似事物的比较，对当前事物进行评价，多用于财务方 面。 3 设计，即参照过去的设计方法和方案完成新的设计任务，多用于建筑、机械、 软件等设计。 基于案例的推理过程通常包括：检索、重用、修正、校阅和系统更新，开发c b r 系统应紧紧围绕这五步展开，其问主要存在以下主要问题：案例的获取；案例的表 示；案例的检索；案例的调整：案例学习与归纳。而两个案例间的相似性度量在案 例搜索中扮演了重要的脚色，所以c b r 系统有时也称为相似性搜索系统。本文针对 相似度标准的设定和案例特征属性的相似性度量问题进行探讨，希望采用一种启发 式的策略解决信息不完备的问题，通过计算案例的相似度来帮助小城镇建设有关部 门在信息不确定、不完全的情况选择较为合适有效的技术，加速小城镇的发展。 1 4 本文的主要内容与结构 本文以小城镇试点示范工程先进适用技术评估与推广项目为应用背景和对 象，遵循系统工程的观点，抽取该项目中的主要问题先进适用技术的选择和推 广问题进行分析。针对小城镇建暧急待分类指导的需求，立足小城镇可持续发展的 5 华中科技大学硕士学位论文 观点，结合技术的评价技术，选择基于案例推理( c b r ) 的方法，探索先进适用技术 的选择和推广方法。文章的主要任务是将c b r 方法应用到新的需求问题和技术应用 历史案例的相似性多目标决策上，对此应用的理论和具体实践进行了探讨。本文的 结构如下安排： 第一章主要介绍本课题的背景，论述研究的目的和意义，综述国内外研究现状， 并明确提出本文的研究目标、研究思路和研究框架，介绍本文的主要工作和结构。 第二章对本文主要采用的c b r 理论方法和任务进行介绍，并分析了现有的相似 性度量方法，为以下的应用和实践做理论铺垫。 第三章结合小城镇建设和技术的综合评价，分析技术应用案例的特点和各种知 识表示方法的特点，建立分层的技术应用历史案例的框架表示。根据不同框架知识 的特点，采用不同的方法确定特征属性的权重。 第四章针对先进适用技术案例中出现的四种不同类型的属性分别给出合适的相 似度算法。利用最邻近算法由局部相似度得到全局相似度来实现与实际应用问题的 相似匹配。 第五章设计了基于c b r 的相似案例查询系统，并结合污水处理厂建设的实际背 景，对相似计算的结果进行了比较、分析，评价了c b r 在本项目中对技术推广应用 的指导作用。 第六章对本文进行小结，总结了论文的主要工作及有待改进之处并对进步 研究的方向进行了展望。 其中第3 、4 、5 章是本文的核心内容，体现了本文的工作量。 华中科技大学硕士学位论文 2 c b r 理论及相似性度量 c b r ( c a s c - b a s c dr e a s o n i n g ) 是一种类比推理方法，它提供了一种近似人类思维模 型的建造专家系统的新的方法学，这与人对自然问题的求解相一致。人们为了解决 一个新问题，先是进行回忆，从记忆中找出一个新问题相似的案例，然后把该案例 中的有关信息复用到新问题的求解中。在处理复杂问题和多属性决策时，c b r 往往 是首选方法。通过c b r 方法可优选小城镇需求技术的相似应用，来指导小城镇建设。 2 1c b r 方法与任务 2 1 1 c b r 的一般方法 整个c b r 过程可以由图2 1 表示。 输入 分析模型 i 二习案例检索卜 一砭素方法 妇隶。；i 案例保存li 类比转换卜 转换规则 新案恻广i _ j = 1 新解 一类比验证k 二二一 土失效描述或椰分解i 一解释过程卜一案例修补 o o 因果分忻o 一 r 磋矗赢 圈2 1c b r 的一般过程 在基于案例的推理中，最初是由于目标案例的某些( 或某个) 特殊性质使我们 能够回忆起曾经实践过的相似的历史案例。但它是粗糙的，不一定正确。在完成最 初的检索后，我们必须证实它们之间的可类比性和差异。在最初阶段，实际完成的 7 华中科技大学硕士学位论文 只是最初步局部的、不完整的类比映射，并对按照与目标案例的可类比程度进行优 先级排序。接下来我们需要建立最优历史案例与目标案例之间的一致一一对应关系， 利用这种一一对应关系将历史案例转换成完整的或部分的解决方案，从而完成目标 案例的完整或部分求解。 2 1 20 1 3 1 1 的主要任务 c b r 的主要研究任务集中体现在以下问题上： 1 案例表示：c b r 中问题的描述和状态以及求解策略用一个事例来表示。最简 单的就可以由案例的一组特征集合来表示。c b r 方法的效率和案例的表示紧密相关。 案例的表示涉及到选择什么信息存放在案例库中、如何选择合适的案例内容的描述 结构和如何组织并索引案例库的问题。 案例特征属性的选择方法主要有1 1 4 11 2 2 】1 2 3 】：( 1 ) 由人结合领域知识进行属性的选 择。( 2 ) 由系统自动进行属性的选择，主要技术有：归纳决策树、粗糙集、平行搜索、 随机变化爬山法、基于熵的属性选择和逐步选择的定向搜索。 案例的表示方法主要有两种：结构表示和属性一值对表示。结构表示是将属性 通过一定的结构组织成一个案例，而属性一值对表示则将案例看作是属性一值对构 成的集合。c b r 系统中的案例表示大多使用人工智能中知识表示的方法，以下为几 种主要的知识表示方法【2 5 】：逻辑表示法、语义网络、产生式规则、框架法、状态空 间、概念从属、剧本、p e 伍网、直接表示法、过程表示法、面向对象表示法以及非 规范逻辑等。 2 分析模型：分析模型用于分析目标案例，从中识别和抽取检索历史案例库的 信息。 3 案例检索：利用检索信息从历史案例库中检索并选择潜在的可用的历史案 例。基于案例的推理方法和人类解决问题的方式很相近。碰到一个新问题时，首先 是从记忆或案例库中回忆出与当前问题相关的最佳案例。后面所有工作能否发挥出 相应的作用，很大程度上依赖于这一阶段得到的案例质量的高低，因此这步非常关 键。它可分为三个子过程：特征辨识，初步匹配，以及最佳选定。 特征辨识是指对新问题进行特征属性的获取。案例特征属性可以从对问题的描 述中直接获得：也可以对问题经过分析理解后导出：还可以根据上下文或知识模型 8 华中科技大学硕士学位论文 的需要从用户那里通过交互方式获得。 初步匹配是指从案例库中找到一组与当前问题相关的候选案例。这是通过使用 上述特征作为案例库的索引来完成检索的。由于能够完全精确匹配的案例一般不存 在，因此要对案例之间的特征关系进行相似度的估计。它可以是基于上述特征的与 领域知识关系不大的表面估计，也可以通过对问题进行深入分析后的深层估计。具 体做法是通过对特征属性赋权来体现不同特征具有不同的重要性。 最佳案例是指从初步匹配过程中获得的一组候选案例中选取一个或几个与当前 问题最相关的案例。这一步和领域知识密切。具体做法是由领域知识模型对候选案 例进行解释或生成某些期望的结果，然后对这些解释或结果的有效性进行测试或评 估，最后依照某种度量标准对候选案例进行排序，得分最高的就是最佳案例。 一般来说，案例的匹配不是精确的，只能是部分匹配或是近似匹配。因此需要 有一个相似度作为评价的标准。该标准定义的越好，检索出来的案例就会越有用， 否则会给后面的过程造成严重的影响。 4 类比映射：寻找目标案例与历史案例之间的对应关系。 5 类比转换：转换历史案例中与目标案例相关的信息，如历史案例同目标案例 间的不同之处，历史案例的哪些部分可以用于目标案例。对于简单分类问题，仅需 把历史案例的分类结果直接用于目标案例，无需考虑它们之间的差别。而对于求解 类问题，则要根据它们之间的不同对复用的解进行调整。 根据复用的信息内容可以分为两种类型：结果复用和方法复用。前者依据一些 转换操作对历史案例的结果进行调整，转换为目标案例的相应的解。后者注重历史 案例的求解方法，如操作算子的使用，子目标的考虑，搜索路径的选取等。 6 解释过程：对把转换过的历史案例的求解方案应用到目标案例时出现的失败 或是成功给予合理解释，分析失败或是成功的因果。 7 案例修补：类似于类比转换，区别在于修补过程的输入方案是解方案和一个 失败的结果分析报告，根据该报告对解方案的错误进行修补。修补的第一步是对复 用的结果进行评估，可以根据它在实际环境中运行情况的反馈，也可以向专家询问 完成。修正错误则要对错误进行勘测并寻找原因，然后修改完善。 8 类比验证：验证目标案例和历史案例类比的有效性。 9 案例保存：新问题求解后，就形成了一个可能用于将来问题求解的历史案例， 9 华中科技大学硕士学位论文 有必要把它存放到案例库中。这是学习也是知识的获取。在决定选取案例的哪些信 息进行保存时一般考虑和问题有关的特征描述、求解结果以及案例求解的成败原因 解释。 新案例加入到案例库中，要对它建立有效的索引，必要可调整案例库的索引强 度或特征权值，以便将来遇到相似的问题可以有效回忆。 2 _ 2 相似度 近年来，各种c b r 系统是否成功的衡量标准取决于该系统检索出最相似案例。提 供新案例解决方案的能力。目标案例的本质特征和历史案例的本质特征必须具有相 似性关系是c b r 系统求解的基础。 相似度问题影响了c b r 系统推理的各个方面，所以相似度的定义尤为重要。目 标案例与历史案例之间的相似性有语义相似、结构相似、目标相似和个体相似1 2 0 。 还有一些学者把相似性关系分为表面相似性和结构相似性。表面相似性定义为对确 定问题的解不扮演因果角色的那些共性，它有助于发现最初的类比和辨识个体。结 构相似性指那些影响目标的共性，它不仅有助于类比检索，而且对类比映射具有非 常大的作用。目标相似性强调了目标的特征，在相似的一组历史案例中，那些对实 现目标案例的目标具有重要作用的历史案例比那些不具有目标相关性的历史案例， 对问题求解更有帮助。个体相似性是划分个体类别的重要依据，案例中的某些个体 可能对于问题的解决具有主导作用，很多情况下个体用来作为问题的显著的检索信 息来初步的检索历史案例，最初的检索结束后可获得与目标案例的个体具有同类关 系或部分与整体关系的历史案例。 由于相似度的应用领域非常广泛，没有通用的定义方法，相似度必须依据具体 应用情况而定。但是，实践中已经形成了常用的划分方法。 根据相似度在相似算法中的级别不同，相似度可以分为1 2 6 l ： ( 1 ) 局部相似度( l o c a ls i m i l a r i t y ) ：即属性级的相似度。两个案例的相似度是 以局部相似度为基础的。局部相似度的计算依赖属性的类型和属性的取值范围。根 据属性类型和取值的特点，c b r 系统应该支持多种类型属性的局部相似算法。 ( 2 ) 全局相似度( g l o b a ls i m i l a r i t y ) ：即案例级的相似度。一旦每个已知属性 0 华中科技大学硕士学位论文 的局部相似度确定后，就可计算出两个案例间的全局相似度。根据属性间的关联和 属性对案例总体特征的贡献不同，c b r 系统可以采用多种全局相似度计算方法。 2 3 相似度算法 相似度算法在c b r 系统中十分重要，合适的度量方法可以快速、准确的从案例库 中找到所需要的案例。提到相似度算法必然要联系到检索技术，在人们的认识中常 常这样区分：相似度算法常常表现为相似度的计算公式或模型，而检索技术通常指 如索引、决策树等检索结构。在实际应用中，案例的检索技术与相似度算法是很难 明确区分的。基本的相似度计算主要使用基于距离的计算方法。目前传统的案例检 索方法有：最邻近算法( n n ) ，归纳推理( i n d u c t i o n ) ，知识引导推理( k n o w l e d g e g u i d e di n d u c t i o n ) 和模板检索法( t e m p l a t er e t r i e v a l ) 等p 2 。 2 3 1 基于距离测度的相似度算法 目前，案例间相似性度量的基本方法大都是基于距离测度的相似评判方法【3 0 l 3 1 1 。 1 欧式距离： s i m ( x ，y ) = 1 一d i s t ( x ，y ) = l - 出f ( y ，) y i 2 海明距离： s i m ( x ，】，) = 1 - d i s t ( x ，y ) = 1 - w 。d i s t ( x 。y ，) j 式中，s i m ( x ，y ) 表示案例x 和y 的相似度，x ，和y ，分别为x 和y 的属性。案例 w l 代表第f 个属性的重要度，f = 1 , 2 ，疗n 是案例属性的个数，标准的d i s t ( x 。，y 。) 通 常表示为：d i s t ( x ，y 。) = x ，一y 1 i m a x 广r a i n ，i 对于数字属性值，m a x i 和m i n i 分别代表案例的第f 个属性的最大和最小值。对于 符号属性值，如果x 。= y ，d i s t ( x 。，y 。) = 0 ：否则，d i s t ( x ，y ，) = 1 。当d i s t ( x ，】，) = 0 ， s i m = l ，这意味着两个案例是同一的。当d i s t ( x ， ，) = l ，s i m = 0 ，则表明两个案 例完全不同。 除了以上最常用的算法外，还有曼哈顿距离、无限模距离等算法。 华中科技大学硕士学位论文 2 3 2 最邻近算法和t c 相似算法嘲 1 最邻近算法( n e a r e s tn e i g h b o r ，n n ) n n 算法结合了领域知识，大多数的c b r 系统都采用该算法。n n 算法成立的假 设1 2 8 1 是两个案例之间的属性集是一样的，且属性间是相互独立的，存在合适的匹配规 则和程序。最简单的最邻近算法是采用加权平均的方法，将所有的属性的相似度经 过加权加总后就可以得到两个案例的相似度。 设每个案例z 由n 个属性定义：x = 讧i ，z ；，x ：，x ：) ，其中x 。是案例的类别， 即决策维。给定一个查询输入口和一个案例库l ，n n 算法在l 中检索最为相似( 即最 “近”) 的案例工，并预言q ，= x ，。则新案例q 和历史案例x 的全局相似度定义为： ( w f x s i r e ( x ：，q ，) ) o s “( x ，g ) = 盟- 一 w ， ，= l 其中w ，是历史案例q 在属性f 上的权值，s i m ( x f , q ，) 是新案例q 和历史案例x 在属 性f 上的局部相似度。 简单最邻近算法的普遍延伸是k 阶最邻近算法( k 一卜n ) 。k n n 算法中，新案 例的类别取决于和它最相似的k 个训练案例所属的类别，k 个案例中哪个类别的案 例多，新案例就属于哪个类型。如果存在两个或者两个以上的类别，那么平均距离 最小的就是新案例所属的类别。但是k n n 算法假设互相邻近的案例有相同的类别， 在利用案例的属性计算案例的距离时，如果关键的分类属性只是整个属性集中的一 小部分，就会出现问题。如两个无关属性差别很大，即使关键的分类属性完全相同， 两个案例未必就是相似案例。这样，k n n 的精确性就取决于无关属性的数量，因 此就有了一些改进的k n n 算法【2 6 l 。如： ( 1 ) 加权k n n 法：使用特定的方法设计案例属性的权值，尽量放大关键属性的 作用。 ( 2 ) 属，陛选择法：在对新案例分类之前先对案例属性集进行选择，排除每一类中 的无关属性后对剩下的重要属性进行计算。 ( 3 ) 属性投影式k n n 法：通过一种近似于k n n 算法的方法剔除无关属性的 1 2 华中科技大学硕士学位论文 影响。 2 t c 相似算法( t v e r s k y sc o n t r a s tm a t c h i n g ，t c ) t c 相似法适用于案例的属性可以用二进制表示的应用领域。t c 法的相似度定 妨：= 丽并 其中，4 “表示案例n 的属性全集，4 。表示案例k 的属性全集，z c 。表示案例n 和k 之间的相似度。考虑到属性集中的各属性对于两个案例具有不同的权值，这样 对于属性集相同而权值不同的案例可以用改进的t c 算法求相似度，公式如下： w ：以吃 m c “= i 型_ 一 ( 一) 2 ( 以) 2 其中，w ：表示第i 属性在案例n 中的权值，同理w ：表示第i 属性在案例k 中的 权重，表示案例n 和案例k 的第i 各属性的相似度，m 表示案例n 和案例k 的所 有属性个数，m c 。表示案例n 和案例k 的相似度。对于属性集不同的两个案例可以 设置属性集为两案例属性集的并集，案例k 有而案例n 没有的属性权值w ：为o ，同 样对案例n 有而案例k 没有的属性权值w ：为0 ，这样就可求得案例间的相似度。 2 3 3 基于归纳技术的相似算法圳 归纳算法根据案例的历史自动建立决策树。归纳算法能够自动分析案例，确定 出案例的最佳特征，利用案例的属性值对案例子集逐级划分，直到每个分支结点仅 存放同一类的案例为止。归纳法的结果是一棵决策树。最早的这类技术是h u n t 等的 c l s ( c o n c e p tl e a r n i n gs y s t e m1 9 6 6 ) ，目前最有名的是q u i n l a n 的i d 3 ( i n t e r a c t i v e d i c h o t o m i ev e r s i o n 31 9 8 6 ) ，还有基于概念聚类的f i s h e r 的c o b w e b 等。本文主要 对i d 3 进行简介。 i d 3 的核心算法仍然是c l s ，是基于信息熵的决策树分类算法。该算法是根据属 性集的取值选择实例的类别。它的核心是在决策树中各级结点上选择属性，用信息增 益率作为属性选择标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最 大的类别信息。使用该属性将案例集分成子集后，系统的熵值最小，期望该非叶结点 到达各后代叶节点的平均路径最短，使生成的决策树平均深度较小，提高分类速度和 1 3 华中科技大学硕士学位论文 准确率。其基本原理如下： 设e = f l xf 2x x e 是n 维有穷向量空间，其中f ，是有穷离散符号集，e 中的元 素e = 为案例集，其中，j = l ，2 ，九。设p e 和n e 是e 的两个子集， 分别为正例集和反例集。设向量空间e 中p e 集和n e 集的大小分别为p 和n ，i d 3 基于下 列两个假设：在向量空间e 上的一棵正确决策树，对任意例子的分类概率与e 中正、 反例的概率一致；一棵决策树能对一个例子做出正确类别判断所需的信息量为： 坳朋一熹l o g ：熹一焘l 0 9 2 ppp熹p + 九+ 玎+ 玎+ 玎 如果以属性a 作为决策树的根，a 具有v 个值( v l ，砭，) ，它将e 分为v 个子集 ( e ，e ：，e ，) ，假设e ，中含有只个正例和t 7 ，个反例，子集e ，的信息熵为l ( p ，r l 。) ，以 属性a 为根分