（管理科学与工程专业论文）基于动态数据流挖掘的案例推理的研究与应用.pdf

合肥工业大学 i l li ti jltii i i ii ii iiil y 18 8 7 0 9 7 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士 学位论文质量要求。 主席： 委员： 答辩委员会签名 勿罔玖知孑似阪 弓娜厶匀扭矽城苏短 佣姚 刷吼 气包 钒陀7 彬 吉 宏双 引讯 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金胆王些太堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 签字日期：少，j 年v 月l ，- 日 学位论文版权使用授权书 本学位论文作者完全了解金起王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金起王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：1 1 年u 月p 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 心柳 签字日期：7 归t 1 年y 月p 日 电话： 邮编： 基于动态数据流挖掘的案例推理的研究与应用 摘要 随着社会经济的发展和计算机技术的不断进步，人们越来越多地依靠计算 机帮助解决实际生产、生活中遇到的问题。案例推理技术作为一种重要的机器 学习方法，具有求解问题高效准确，解决方案直观易用，且能够自我增量学习 等优点，因此，其思想与方法被广泛地应用于实际中帮助人们进行推理、解释， 解决问题。数据流作为近年来被广泛关注并深入研究的新型数据类型，具有实 时产生、源源不断等特点，现实生活中很多数据都具有类似特征，例如网络流 量数据、股票交易数据等，因此对数据流的挖掘与研究具有十分重要的现实意 义。 本文首先阐述了基于案例的推理和数据流挖掘方面的主要理论与方法。重 点介绍了基于案例推理的概念、分类和基本模型，研究了当前基于案例推理方 面的研究热点。深入分析了数据流的特点与研究思路，对数据流的聚类、分类、 频繁模式挖掘等算法进行了详细的论述。然后，分析了最小距离原则聚类算法 和s t r e a m 算法的优缺点，提出了一种改进的数据流聚类算法。在传统案例推理 模型的基础上，引入数据流挖掘技术，提出了基于动态数据流挖掘的案例推理 模型，并将其应用于实际生产中，开发出了汽车行业故障诊断系统。 文章最后对课题的研究情况进行了总结，并且对基于案例的推理和数据流 挖掘的研究前景进行了展望。 关键词：基于案例的推理；数据流；聚类；故障诊断 c a s eb a s e dr e a s o n i n gr e s e a r c ha n da p p l i c a t i o nb a s e do n d y n a m i cd a t as t r e a mm i n i n g a b s t r a c t a sl o n ga st h ed e v e l o p i n go fe c o n o m y a n dc o m p u t e rt e c h n o l o g y , p e o p i e d e p e n do nc o m p u t e rt o s o l v ep r o b l e mi np r a c t i c em o r ea n dm o r e c a s e b a s e d r e a s o n i n g ( c b r ) i sa ni m p o r t a n tt e c h n i q u e o fm a c h i n el e a r n i n g ，i ts o l v e sp r o b l e m e x a c t l va n de f f i c i e n t l y ，i t sa n s w e r sa r ev i s u a la n dc o m p r e h e n s i b l e ，a n d i tc a nl e a r n i n c r e m e n t a l l yb yi t s e l f , i t s t h e o r i e sa n dm e t h o d sa r eu s e df o rh e l p i n gp e o p i e r e a s o n i n g ，e x p l a i n i n ga n ds o l v i n gp r o b l e mw i d e l y a s an e wd a t at y p e ，d a t a s t r e a m g e tw i d e l ya t t e n t i o na n dr e s e a r c h i n g d a t a s t r e a mi s r e a l - t i m ea n di n f i n i t u d e t h e r e a r em a n vd a t ah a v i n gt h es a m ec h a r a c t e r i s t i ca sd a t a s t r e a mi nt r u e - l i f e ，s u c h a sn e t f l o wd a t a 。s t o c kd a t a ，e t c s ot h em i n i n ga n dr e s e a r c h i n gi nd a t a s t r e a m 1 sv e r y i m p o r t a n t t h i sa r t i c l ef i r s t l yi n t r o d u c e st h eb a s i ct h e o r i e s a n dm e t h o d so fc a s e b a s e r e a s o n i n ga n dd a t a s t r e a m ， i n v e s t ig a t e st h ec o n c e p t i o n ， s o r ta n dt h em o d e lo f c a s e b a s er e a s o n i n g ，d i s c u s s e st h eh o t s p o to fc a s e - b a s er e a s o n i n g ，a n a l y s e st h e c h a r a c t e r i s t i ca n da p p r o a c ho fd a t a s t r e a m ，d i s c u s s e st l f e a r i t h m e t i co fd a t a s t r e a m i n c l u d i n gc l u s t e r i n g ，s o r t i n g ，f r e q u e n tp a t t e r n sm i n i n g ，e t c t h e n t h i sa r t i c l e s u m m a r i z e st h es t r o n gp o i n t sa n dd i s a d v a n t a g e so ft h em i n i m a ld i s t a n c e - b a s e d c l u s t e r i n ga n ds t r e a mc l u s t e r i n g ，r a i s e sa ni m p r o v e dd a t a s t r e a mc l u s t e r i n g t h i s a r t i c l ei sb a s e du p o nt r a d i t i o n a lm o d e lo fc a s e - b a s e r e a s o n i n g ，j o i n sd a t a s t r e a m m i n i n gm e t h o d s ，r a i s e st h em o d e lo fc a s e - b a s e dr e a s o n i n gb a s e d o nd y n a m l cd a t a s t r e a mm i n i n g ，a n da p p l i e s t h i sm o d e lt op r a c t i c e ，d e s i g n sa n dm a k e sc a rf a u l t d i a g n o s i ss y s t e m t h i sa r t i c l ef i n a l l y s u m m a r i z e s c a s e b a s er e a s o n i n ga n dd a t a s t r e a m t h er e s e a r c h ，p r o p o s e s t h eo u t l o o ko f k e y w o r d s ：c a s e b a s e dr e a s o n i n g ；d a t a s t r e a m ；c l u s t e r i n g ；f a u l td i a g n o s i s 致谢 时光飞逝，岁月如梭。两年半的研究生生活已接近尾声。在论文即将完成 之际，我首先要感谢我的研究生导师倪志伟教授。在两年半的研究生学习期间， 倪老师崇高的师德、渊博的知识、严谨的治学态度深深地影响了我，让我受益 匪浅，并将使我终身受用。在我研究生的学习、论文的写作、项目的参与以及 平时的生活中，倪老师都给了我巨大的关心与帮助，在此，我谨向导师致以最 崇高的敬意与最真诚的感谢。 在两年半的学习与生活中，我得到了许多老师、同学的关心与帮助，在此 表示感谢。感谢查春生、周之强、姜苗、孟金华、公维峰等同学以及所里的师 弟师妹一直以来给予我的帮助与支持，特别要感谢倪丽萍师姐、伍章俊师兄、 王超师兄在学术和工作上的帮助与指导。正因为有了你们的支持与鼓励，才使 我顺利完成了这篇论文。 我还要感谢我的父母，是他们一直以来默默的支持与鼓励，才使我每一步 走得更加坚实，他们无私的、伟大的爱，是我永远的动力。 同时，感谢所有参与我答辩的专家老师，感谢他们在百忙之中抽出时间对 论文进行了认真的评阅。 i i i 作者：戴奇波 2 0 11 年4 月 目录 第一章绪论1 1 1 论文的选题背景和意义1 1 2 国内外研究现状2 1 3 本文主要研究内容“2 1 4 本文组织及章节安排3 第二章案例推理理论4 2 1 案例推理概述4 2 1 1 案例推理的概念4 2 1 2 案例推理的起源与发展4 2 1 3 案例推理的分类5 2 2 案例推理基本模型5 2 3 案例推理的研究现状7 2 3 1 案例的表示。7 2 3 2 案例的检索7 2 3 3 案例的解释9 2 3 4 案例二次提取9 2 3 5 案例的修改与应用1 0 2 3 6 案例改编及案例库维护：。1 0 2 3 7c b r 与其它数据挖掘技术的结合“ 2 4 本章小结。1 2 第三章数据流挖掘的研究13 3 1数据流概述1 3 3 1 1 数据流的概念1 3 3 1 2 数据流的研究与应用1 3 3 2数据流挖掘的分类及各算法介绍1 5 3 2 1 聚类1 5 3 2 2 分类1 6 3 2 3 频繁项集挖掘1 7 3 2 4 多数据流挖掘18 3 3 数据流聚类算法“18 3 3 1 最小距离原则聚类算法1 8 3 3 2b i r c h 算法1 9 3 2 3s t r e a m 算法2 0 3 2 4c l u s t r e a m 算法2 0 3 4目前数据流挖掘技术的应用2 l i v 3 5 本章小结2 2 第四章改进的数据流聚类算法2 3 4 1 传统的聚类算法分析2 3 4 2 改进的数据流聚类算法2 4 4 2 1 算法思想2 5 4 2 2 算法详细步骤2 6 4 2 3 算法伪代码2 6 4 3 算法优缺点对比2 7 4 4 本章小结2 8 第五章基于数据流挖掘的案例推理模型及应用2 9 5 1 研究背景和问题提出2 9 5 1 1 问题的提出2 9 5 1 2 研究内容2 9 5 2 基于数据流挖掘的案例推理模型3 0 5 2 1 模型介绍3 0 5 2 2 案例的动态获取3 1 5 2 3 知识库的及时更新“3 2 5 2 4 两级检索策略3 2 5 2 5 模型的使用与问题的解决3 3 5 3 基于数据流挖掘的案例推理模型在汽车故障诊断中的应用3 3 5 3 1 汽车行业故障诊断的现状3 3 5 3 2 汽车故障数据流的动态接收3 4 5 3 3 动态数据流挖掘3 5 5 3 4 车辆故障知识库的动态更新3 6 5 3 5 新的车辆故障问题的诊断3 7 5 3 6 新案例保存3 7 5 4 本章小结3 8 第六章总结与展望3 9 6 1 总结3 9 6 2 展望3 9 参考文献4 l 研究生期间发表的论文和参与的项目情况4 5 v 图2 1 图3 1 图3 2 图4 1 图4 2 图4 3 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 插图清单 案例推理基本模型6 最小距离原则聚类算法l9 s t r e a m 算法2 0 最小距离原则聚类算法2 3 s t r e a m 算法2 4 改进的数据流聚类算法2 5 基于动态数据流的案例推理模型_ 3 0 获取动态数据流界面35 数据流挖掘界面36 知识库更新界面36 故障分析界面37 故障案例详细信息38 v i 表格清单 表5 1 汽车故障数据的动态数据流数据一3 4 表5 2数据流挖掘后获得某车型的故障知识3 5 v n 第一章绪论 1 1 论文的选题背景和意义 近年来，随着计算机使用的普及、网络设施的发展和信息技术的不断进步， 整个社会已经进入了信息化时代，信息对于整个人类与社会的发展，已经起到 了至关重要的作用。信息的数量、信息的传播速度、对信息的处理能力以及应 用信息的速度都在以指数级的方式不断增长。 随着各种信息技术不断应用，信息的产生与存在方式也不断发生着变化， 在很多领域产生了一种具有不断出现、连续到达、实时产生等特点的数据，譬 如：瞬息万变的气象变化数据、变化莫测的股票交易数据、起伏不定的电力使 用数据等等，这类数据与我们的生产、生活息息相关，通过分析发现它们普遍 存在着一类共同的特点：持续无限到达、到达速度快、取值范围不定，我们 称这类数据为“数据流 或者“流数据 。随着我们对这类数据的不断分析与 深入研究，其中存在的大量有用信息与数据被人类不断获得，对我们的生产、 生活起到了非常重要的指导与预测作用。 人们通过不断分析，从各种纷繁芜杂的数据中挖掘出新的知识、规律或者 规则，为我们下一步的活动起到了更好的指导作用。这也是人类从记忆出发去 探知新事物的一种认知行为心1 ，这符合人类的推理习惯，于是基于此，基于案 例的推理( c b r ) 的研究应运而生。它是一种符合人类思维逻辑与模型的推理 方法，利用过去的、已知的案例或者经验来进行推理，从而找出求解新问题的 方法与途径他1 。 然而传统的基于案例的推理系统，由于其范例库往往是由专家给出或者通 过修改已有历史库来进行更新，这样就存在着知识陈旧、知识更新太慢，不能 解决最新问题，对最新的条件或者情况不能及时响应的问题。对于具有不断出 现、连续到达、变化不定的数据流性质问题更是无法处理。 本文将对数据流的研究与对案例推理的应用相结合，提出了一种基于数据 流挖掘的案例推理模型，此模型通过对动态数据流的实时分析与挖掘，找出不 断更新的、具有保留价值的新的案例，更新案例库推理中陈旧的、过时的、长 期不用没有价值的案例，以此来满足不断变化的新问题，及时、准确地响应新 的需求，并将该模型应用于实际的汽车故障诊断项目中。与此同时，本文还基 于数据流聚类中的最小距离原则聚类算法n 1 和s t r e a m 聚类h 喝1 算法，在此基础 上提出了改进的数据流聚类算法，通过对比，理论上证明此改进算法具有明显 优于前两种算法的优点。目前，对于数据流与案例推理相结合的理论与应用研 究都还很少，因此，该研究具有重要学术意义和实用价值。 1 2 国内外研究现状 自上世纪八十年代，案例推理的概念诞生以来，各国学者对案例推理的研 究不断深入，应用领域也在不断扩大。尤其是每年一次的c b r ( c a s e b a s e d r e a s o n i n g ，案例推理) 研讨会的召开，更是极大推动了案例推理研究的进展， 并出现了一大批优秀的理论研究和实际应用成果。 目前，对案例推理的理论研究方面主要围绕案例的表示、案例的检索、系 统的推理、案例的修改和维护等展开。德国学者d o y l e 等提出使用x m l 语言 来表示具体的案例，同时根据案例的不同的特征选择不同的相似度计算方法对 案例进行检索，提高检索的准确性；加拿大学者c h u n s h e n gy a n g 和b e n o i tf a r l e y 等提出了案例的自动生成与管理；还有英国学者s t e w a r tm a s s i e 等提出了一种 通过消除案例库中的噪音案例，来提高推理系统的准确率；在案例推理与其他 数据挖掘技术的结合方面也出现了很多新的研究成果。同时，基于案例的推理 在实际中也得到了越来越广泛的应用，在医疗诊断、网络入侵检测、垃圾邮件 判定等领域案例推理已经产生了实际效用。 数据流是一种新型的数据类型，它有别于传统的存储于数据库中的静态数 据。由于其具有数据持续产生、实时到达、数量无限等新的特点1 ，而且在实 际的生产、生活中出现了越来越多具有数据流性质的数据，例如：工业部门监 控的电力能源使用情况数据，证券交易行业里股票价格及交易数据，气象部门 中瞬息万变的气象分析数据，还有网络监控实时数据等等，因此，数据流受到 了很多数据挖掘领域专家学者的关注，并成为近年来研究的热点。 目前，对数据流的研究，按照研究侧重点不同基本可以分为三大类，一类 是对数据流处理的算法研究，这是数据流研究的一个重要部分，按照方法和作 用不同，主要算法有数据流聚类、数据流分类、数据流异常点检测等n 1 ，除此 之外，还出现了数据流频繁模式挖掘和概念漂移阳1 等新的研究内容；第二类是 对数据流模型的研究，包括数据流数据的表示结构、数据流处理的模型更新等， 目前，针对数据流处理问题提出的滑动窗口模型是比较流行的数据流处理模型。 还有一类是针对数据流的管理系统的研究，已经有一些学者提出并设计了数据 流管理系统结构。 虽然已经出现了一些将基于案例的推理技术与其他数据挖掘技术相结合阳1 的研究成果，但目前该类研究主要是针对静态数据的挖掘n 们，并将其与案例推 相结合，还很少有将数据流挖掘与案例推理相结合的理论与研究出现。 1 3 本文主要研究内容 本文对案例推理和数据流挖掘的相关理论、算法和应用进行了全面、深入 的讨论，在此基础上针对案例推理中存在的不足，将数据流的相关理论与方法 引入案例推理，并提出了基于数据流挖掘的案例推理模型，最终将其应用于实 2 本文的主要研究内容如下： ( 1 ) 分析传统的数据流聚类算法，提出了改进的数据流聚类算法，通过比 较，发现该改进算法具有明显优于传统算法的特点。 ( 2 ) 针对传统案例推理中案例库无法及时更新的问题，将数据流挖掘技术 应用到案例推理中，并提出了基于数据流挖掘的案例推理模型。 ( 3 ) 将本文提出的基于数据流挖掘的案例推理模型应用到车辆故障检测的 实际项目中，将理论转化为实际应用。 1 4 本文组织及章节安排 本文共分为六章，具体每章的内容如下： 第一章：绪论。介绍了本文的选题背景、研究意义，以及数据流、案例推 理的国内外研究现状，最后指出本文的主要内容和文章组织结构。 第二章：案例推理理论。介绍案例推理的起源、概念，详细介绍传统的案 例推理基本模型和各部分作业，并对目前案例推理的研究热点及发展情况进行 了详细介绍。 第三章：数据流挖掘的研究。介绍了数据流的概念、数据流挖掘的分类和 算法，着重介绍了数据流聚类的各种基本算法，并对目前数据流的研究热点进 行的阐述。 第四章：改进的数据流聚类算法。分析了传统的最小距离原则聚类算法和 s t r e a m 算法，分析各自的优缺点，在此基础上，提出了改进的数据流聚类算 法，比较算法的优缺点。 第五章：基于数据流挖掘的案例推理模型及应用。本文重点，针对传统案 例推理中案例库无法及时更新的问题，在传统案例推理模型的基础上将数据流 挖掘算法引入案例推理，提出基于数据流挖掘的案例推理模型，使得案例库能 够及时更新，满足实际需要，解决最新问题，并最终将该理论应用到汽车行业 中。 。第六章：结束语。对本文所有的研究工作进行总结，并对进一步开展深入 研究提出了设想与展望。 3 第二章案例推理理论 2 1 案例推理概述 2 1 1 案例推理的概念 案例推理( c a s e b a s e dr e a s o n i n g ，c b r ) 是由目标范例的提示而得到历史 记忆中的源范例，并由源范例来指导目标范例求解的一种策略，它是一种重要 的机器学习方法乜1 。 简单的说案例推理就是通过旧有的知识去解决新问题的方法。对于它的研 究最早起源于人类认识和改造外部世界的行为，人们在认识外界新事物，解决 新问题时，往往由于主观认知的欠缺和客观条件的限制，不可能掌握新事物或 者新问题的所有信息，于是人们利用那些曾经遇见过、经历过，并经过整理改 编已经留存在记忆中的信息，将新事物或者新问题的特征与这些已有信息进行 对比，对某些特征进行修改和处理，最终获得认识新事物、解决新问题的信息 与方法，并且再次将这些新的认识与方法保存在大脑的记忆中，这就是基于记 忆的推理，也是c b r 的起源。 相对于其他许多从“零”开始探索、解决问题的方法，案例推理最显而易 见的优点是它在遇到新问题时，可以从已有的知识中获取信息，并根据问题的 具体情况，通过修改、整理这些已有信息获得新的信息，以此提供解决新问题 的知识与方法。 2 1 2 案例推理的起源与发展 案例推理的概念最早是由美国耶鲁大学的r o g e rs c h a n k 教授于1 9 8 2 年在 其著作 d y n a m i cm e m o r y ) ) 中提出的，s c h a n k 提出的表示经历的知识结构以 及这些结构上的操作1 ，被认为是c b r 思想及过程的原型，为在计算机上实现 c b r 奠定了基础。 1 9 8 3 年佐治亚工学院的j a n e tk o l o d n e r 教授，基于动态存储模型和m o p 理论，领导开发了第一个基于案例的推理系统的c y r u s n 引。随后，在c y r u s 的案例记忆模型基础上，美国许多大学的研究人员开发了c b r 系统。 到8 0 年代后期9 0 年代初，出现了许多c b r 系统，其应用也越来越普遍， 目前c b r 已经广泛应用于医疗诊断、气象灾害分析、农业信息研究、机械故障 诊断、垃圾邮件判定与处理等各个领域。 c b r 的研究方法源自于人类的认知行为，即一种基于记忆的推理，它缓解 了常规的知识系统中知识获取从零开始的瓶颈问题，它将定量分析与定性分析 相结合，具有信息完全表达、动态更新知识库、增量式学习、知识获取容易、 求解效率高等特点。另外，早期对类比推理的研究，哲学和心理学中对概念形 式理论及问题求解和经验学习理论的研究，也对c b r 思想产生一定的影响。 目前，案例推理已经发展成为人工智能领域中的一个重要分支，它是一种 4 题是通过重用或修改 以前解决相似问题的方案来实现的。典型的c b r 系统及开发工具有j u d g e 、 k r i t i k 、c a b a r e t 、c a b o t 、c b r 2 、e c l i p s e 、e s t e e m 、k a t e 等乜1 。 2 1 3 案例推理的分类 案例推理一般被分为两类，一类是被称为解释型的案例推理，另一类是问 题解决型的案例推理n 引。解释型的案例推理是将已知的案例作为标准来对当前 的问题进行分类、归纳和解释；问题解决型的案例推理是利用以往的案例来为 当前新的问题提供参考，并给出具有建设意义的解决办法或方案。 ( 1 ) 解释性的案例推理 解释型的案例推理是通过将新的问题的描述、参数等特征信息与案例库中 已经存在的案例进行对比，借此对该新问题产生一个的分类或判断。例如，在 医疗诊断领域，当一个新的病情到来，通过将该新病情的特征与诊断案例库中 保存的以往病例相比较，得到治疗该新病情的最相似、最可靠的方法与措施， 给医疗人员提供参考与帮助，这就是解释型案例推理的典型应用。 ( 2 ) 问题解决型的案例推理 问题解决型的案例推理的任务是将以往的解决方案或者方法，根据具体的 情况，进行一定的修改和改进，形成适合解决该新问题的方法和方案，最终解 决新的问题。例如，在工业设计或者诊断领域n ，对于新的设计计划与任务， 首先检索以往设计案例库中具有相似条件与要求的设计方案，然后在此基础上 进行修改与调整，得到能够满足新的计划需求的设计方案，这就是问题解决型 案例推理的应用过程。 2 2 案例推理基本模型 案例推理起源于人类的认知心理活动，是一种属于类比推理的方法，其基 本思想是人们在新问题求解时，习惯于检索过去处理类似问题的经验和知识， 再针对新旧情况的现实差异做出必要的调整与修改，从而得到新问题的解并形 成新的范例，并将其保存，用于其他新问题的求解。 案例推理是使用过去已知的信息去解决新问题的方法，这种方法包含一个 库，其中保存了所有的案例。这些案例包括两个部分：一部分事件或者条件， 另一部分是相对应的结果。其中，事件或者条件往往使用可度量的参数或者一 段文字描述来表示，其相对应的结果可以是任何文本或者数字的内容。当一个 新问题到达时，系统首先将其转化为系统能够识别的格式，然后系统根据一定 的算法或者理论从案例库中找出最相似的案例，将他们提取、整合，提交给用 户，帮助用户去解决该新问题。然后，通过检测，如果该案例被确认为新的案 例，则将其添加到案例库中，否则不添加，以此扩充案例库的信息量，扩大案 5 例的覆盖面，提高案例推理系统解决问题的能力n 引。 一般来说人们将案例推理的过程分解为四个步骤伸1 ，分别是：案例检索 ( r e t r i e v a l ) 、案例复用( r e u s e ) 、案例修正( r e v i s e ) 、案例保存( r e t a i n ) ， 因此，案例推理也常常被人们为4 r 方法。案例推理的基本模型如图2 1 所示。 新问题 图2 - 1 案例推理基本模型 ( 1 ) 案例检索：当有新的问题到来时，往往由于新问题的表述或者表示不 符合规范，我们首先需要按照一定的格式将其进行转换处理，变为系统能够识 别和处理的格式，成一个目标案例。然后根据该目标案例的参数、关键字等特 征信息到案例库中找出与其具有最相似特征的案例。 ( 2 ) 案例复用：将从案例库中检索出来的、与目标案例具有最相似特征的 案例提取出来，通过一定的分析、整合提取出解决该目标案例的方法或者解。 如果该方法可以解决目标案例的问题，则直接将其作为问题解决方案提交给用 户，帮助用户解决新问题，如果该方法还不能解决目标案例，则表示该方案需 要进一步的修改与处理。 ( 3 ) 案例修正：用户得到了一个尚不能直接解决目标案例的方案，需要根 据一定的规则或者算法对其进行修改与调整，使其能够解决目标案例，并最终 解决新的问题。 ( 4 ) 案例保存：用户需要按照一定的规则或者算法，对已经经过修正、并 帮助用户解决新问题的案例进行确认，如果该案例被确认为是新的案例，则需 要按照一定的案例表示规范和保存方法将其保存到案例库中，使其能够满足解 决类似问题的需要，如果该案例不是新的案例，则不需要保存。案例保存的过 6 程也是实现系统增量学习的过程。 2 3 案例推理的研究现状 由于案例推理的结构复杂，过程繁多，各个步骤中都包含很多值得深入分 析与研究的问题。在案例检索阶段研究内容有案例如何表示、查找案例库的标 准即如何检索案例、如何确认最相似案例等，在案例复用阶段研究内容有如何 复用获取的最相似案例、提交给用户解决方案的表现形式即如何解释案例等， 案例修正阶段有案例如何修正、如何确定修改后的案例已经满足问题需要等， 案例保存阶段有案例如何保存、案例如何更新等。 目前，学术界对案例推理的研究热点主要集中在以下几个方面： 2 3 1 案例的表示 在案例推理中，案例是存有知识的信息载体，案例表示是知识表示的基础， 可以说案例的表示是案例推理的核心n 盯，因为它涉及到信息如何保存、案例结 构如何组织、案例库如何组建、案例检索方式等等问题，对案例推理起着至关 重要的作用。 一般来说，一个案例至少包含两部分内容，一部分是对问题的描述，即案 例的发生条件、外部环境、当前状态等信息，另一个不可缺少的部分是对问题 解的描述，即解决问题的方法、途径、措施等等信息。除了这两个基本的部分 之外，很多学者也将问题解决的结果作为案例的组成部分。 案例表示可以是一段文本文字，也可以是一串参数数据或者一段脚本信息 等，还可以是面向对象的数据库，框架结构，语义网络等等，形式多种多样。 在这些已有的表示方法基础上，也出现了许多新颖的表示方法，例如使用嵌套 的图结构表示，还有基于概率模型的表示等。 都柏林大学的d o y l e 等人在其文章中提出使用x m l 语言n 来表示案例的方 法，该研究小组构建了一种基于x m l 的c b r 语言( c b m l ) ，即基于案例推理的 标记语言( c a s e b a s e dm a r k u pl a n g u a g e ) ，用于表示案例本身。文中指出，使 用c b m l 表示的案例由两部分组成，分别是案例的内容和案例的结构。 ( 1 ) 案例内容包含了以x m l 格式表示的案例信息，这些内容必须与指定 的案例结构保持一致，且内容与结构都必须有效； ( 2 ) 案例结构则定义了出现在案例中的层次和基数特征。存在许多可以表 示案例的特征结构，这些特征结构定义了案例的种类、值的限制以及一些其他 的属性。 2 3 2 案例的检索 案例推理解决问题的基本思想是提供与新问题最相似的以往解决方法或者 7 方案给用户，帮助用户解决新问题。然而，简单地给用户提供案例显然不能使 用户充分信任案例推理的准确性与有效性。案例检索就是检查案例库，从中找 出与新问题最相似案例的方法与过程，从而给用户提供解决当前问题的方案n 引。 因此，对于一个案例推理系统来说，如何从案例库中检索并选择与新问题最相 似的案例直接决定了案例推理系统的推理性能，也关系到案例推理的准确性。 案例检索使得案例推理的过程更加透明，使得用户更易于信任案例推理的能力 与有效性n 钔。 。 在案例检索中，案例间的相似性度量是检索的关键。一般的，两个案例间 的相似度可以表示为案例的主要特征值乘以该特征权重的加权和，计算公式如 下： 、一 s i m ( q ，c ) = 。w ，x o y ( 缈，c 1 ) j - 毛f 其中q 表示某新问题；c 为案例库中的某个案例，f 表示所有的特征，f 表示相似特征，w f 是某相似特征的权重值，o 是相似特征的差值。为了提供相 似度表示，必须为每个特征都准备相关性权重和相似度量刻度。 案例推理经过这么多年的发展，出现了许多计算案例问相似性的度量方法。 主要的相似算法有以下几种： ( 1 ) 最近邻相似度算法。它的基本思想是计算案例之间的相似度，找出相 似度最大的案例作为结果。适用于简单的基于属性特征的案例表示方法。 ( 2 ) 基于归纳技术的相似度算法乜们。它思想来源于利用决策树算法，它按 照某些特定的规则或者标准，将案例库中的案例分为不同的类别，并根据不同 的类别构建出一个具有判别能力的层次型的决策树。其本质上是对案例进行分 类。 ( 3 ) 模糊相似度算法。案例推理和模糊技术都具有确定相似度的能力，而 案例推理常常处理的是属性、结构、集合等属性，模糊技术处理的是具有相似 的不确定性，针对需要定性分析与定量分析结合的案例属性，案例的匹配过程 使用模糊技术，很好的解决了这个问题。 ( 4 ) 多维空间检索技术堙。对于结构化的案例，其案例间的相似度计算往 往相对比较简单。而现在很多案例往往由存在于多维空间的矢量组成，结构复 杂，此时相似度的计算问题就转化为了计算多维空间中最近邻点的问题，这样 距离就是相似度的计算目标。对于这类问题主要解决办法有降维技术和多维空 间索引技术。 除了以上几种典型的相似度算法之外，还有基于神经网络的相似度检索技 术、基于启发式的相似度算法、适用于语义网络的连锁激活相似算法等他引。 8 d o y l e 在其文章( r e p r e s e n t i n gs i m i l a r i t yf o rc b ri nx m l 中，不是按照 传统的方法，只按照一种计算方法案例间的相似度，而是根据特征的不同，将 相似度量度量方法分为3 类，分别是精确匹配、基于差异度的匹配以及复杂的 相似度匹配心引， e x a c ts i m i l a r i t ym e a s u r e s ( 精确匹配) ：值相等为1 ，不等为o d i f f e r e n c eb a s e ds i m i l a r i t ym e a s u r e s ( 差异相似匹配) ：相似度与两个特征 值的差异有关，这种测量适合于差异能用值定义的情况，例如包括数值型、符 号型( 枚举类型) 以及层次分类型等特征值的度量，可以通过计算获得。 c o m p l e xs i m i l a r i t ym e a s u r e s ( 复杂相似匹配) ：它不同于以上的两种情况， 他不可能为所有的种类提供表示方案。但是如果可能的值是有限的，那样就可 以计算和定义未来每种特征组合的相似值。它会通过引入外部预定义的度量对 象来解决( 可以看做一个针对具体情况的类) 。 在计算两案例中的相似度时，根据不同的特征选择不同的属性，然后做总 的汇总处理。 2 3 3 案例的解释 案例推理的解释是案例推理系统的一个重要环节，它主要解决案例推理系 统如何为用户解释推理过程、如何使用户相信案例推理的结果，以及如何让案 例推理的解决方案帮助人们解决问题，它是基于案例的解释，是案例推理得到 应用的关键环节，主要在案例的复用阶段。案例的解释直接影响用户对案例推 理系统的信赖程度。 国内已经有一些学者对案例解释做了一些研究与整理，认为基于案例的解 释是推理技术与解释技术相结合的过程心引，并将基于案例的解释的研究内容归 类为三个层次，分别是：利用解释来支持案例推理的内部过程、利用案例推理 来生成解释信息、使用案例为外部用户解释案例推理系统给出的推理结果。 目前有两类比较典型的解释方法，一类是基于相似度的解释心引，另一类是 类似于产品推荐系统的解释，它通过用户与系统之间的交互，查询符合用户要 求的产品信息，并将其推荐给用户心引。而有时，经常会出现用户对自己的需求 并不十分明确的情况，这时利用产品推荐系统，就能通过一定的推理过程，帮 助用户明确其自身的需求，并最终得到最符合其要求的解。 2 3 4 案例二次提取 很多案例推理系统常常要求用户必须给出全部的查询条件，且只有当每个 查询条件完全符合时，才会给出查询结果。这样就经常导致案例推理系统无法 提供解决方案的情况出现，案例提取以失败告终，导致系统可用性低下，因此 也降低了用户对系统信赖程度。而实际上，很多时候用户在进行查询时，他们 9 并不清楚查询的所有条件，这时如果根据用户已知的条件进行判断，并对案例 进行二次检索，将最接近用户要求的案例或者方案提取出来，供给用户选择， 这将大大提高系统的可用性，这就是案例的二次提取。 m c s h e r r y 等人在其文章中心 提出一种二次提取案例、重新获取解决方案的 机制。当第一次案例提取失败时，系统将触发二次提取操作，通过减少用户的 查询条件来扩大查询结果的范围，将最接近求解问题的解提供给用户。 2 3 5 案例的修改与应用 当案例推理系统根据新问题得到一个解决方案后，往往由于新问题的条件 和环境的特殊性，不能将其直接使用到问题上，而需要进行必要的修改乜引，才 能适合新问题、解决新问题。这是利用案例的关键一步，通常也是比较难的一 步。 目前，案例推理系统中对案例进行修改所使用最多的方法是在原有案例基 础上，根据当前条件，对案例的某些相关参数进行修改，使其满足解决新问题 的需求。 c h u n s h e n gy a n g 等人在其文章a u t o m a t e dc a s ec r e a t i o na n dm a n a g e m e n tf o r d i a g n o s t i cc b rs y s t e m s ) ) 中提出了一个在案例推理系统开发的初级阶段自动生 成案例的方法，并通过实验说明该方法能够减少人们创建案例的工作量，能够 在系统开发的初始阶段从维护和操作的历史数据中为诊断案例推理系统创造高 质量的案例库，并且提出了a u t o m a t e dc a s ec r e a t i o ns y s t e m ( a c c s ) 自动案例生成 系统托9 1 。这中间的新案例是通过四个步骤生成的： 第一步根据问题确认症状。从问题的状态参数、时间戳、症状描述等信息 中找出当前问题的特征。 第二步根据问题确认解决方案。从事件发生的时间地点、修理时间地点、 操作过程、问题描述等信息中提取出修改、操作和组成信息。 第三步创建一个潜在案例。 第四步保存该案例。通过添加新案例、删除多余案例、合并相似案例来高 效的管理案例库 2 3 6 案例改编及案例库维护 案例的改编与案例库的维护是为了提高案例推理的准确性，提升案例推理 系统的效率，使其更好的解决新的问题。 案例的改编与维护策略很多，典型的有以下几种： ( 1 ) 按照差异度进行的案例改编与维护。通过比较不同案例间的差异程度， 确定差异度阈值，对达到和超过阈值的案例进行改编； ( 2 ) 通过聚类算法的改编与维护