（计算机系统结构专业论文）cbr系统中事例检索算法研究及应用.pdf

东 北大学 硕士学位论文 摘要 c b r系统中事例检索算法研究及应用 摘要 随 着网 络资 源 共享 程 度的 提高 ， 基于 事 例 推 理( c a s e - b a s e d r e a s o n i n g , c b r ) 作为 基于 知 识 的 专家 系 统( e x p e r t s y s t e m ) 的 一 个分 支， 受 到 越来 越多 的 关 注， 它 是人工智能 ( a r ti f i c i a l i n t e l l i g e n c e ) 研究中一种迅速发展的有效的推理方 法。 本文简单阐述c b r的 基本概念和原理， 结合医院医生诊断的背景， 具体的阐 述了c b r系统的几个核心环节和一些相关的设想:事例表示和存储、事例检索和 匹配、事例的修改，学习和索引。 事例表示和存储采用了可拓物元与标准表相结合的表示方法。有效的解决了 知识表达的可拓性问题，为属性的拓展提供了一般性解决方案;在事例检索中， 采用了 分级过滤与最近相邻方法相结合的策略，利用基于属性空间的概念，精简 了 检索过程， 提高了系统的检索效率;在事例的修改，学习和索引环节，采用两 级事例库的方式对系统模拟学习能力进行实现， 采用类似于b 十 树的结构来组织代 表事例库， 以达到系统自 动学习的目 标。 此外， 文章对c b r与r b r的结合， c b r 系统与分布式数据库的结合也作了相应的探讨和可行性的展望。 关键词: c b r 分级过滤算法事例学习 属性空间 .i l。 东 北 大 学 硕 士 学 位 论 文_ r e s e a r c h a n d a p p l i c a t i o n o f s e a r c h a l g o r i t h m r e a s o n i n g ab s t r a c t i n ca s e - b a s e d abs tract w it h t h e im p r o v e m e n t s o f t h e s h a r e d e g r e e o f th e n e t a n d c o l la b o r a t io n , c a s e - b a s e d r e a s o n i n g ( c b r ) , a s a b r a n c h o f k n o w l e d g e - b as e d e x p e r t s y s t e m , a tt r a c t e d m o r e a tt e n t i o n s . c b r i s a r a p i d l y g ro w i n g a n d e f f i c i e n c y r e a s o n i n g m e t h o d i n t h e r e s e a r c h o f a r t i f i c i a l i n t e l l i g e n c e ( a i ) . t h i s p a p e r b e g i n s w i t h a b r e v i t y in t r o d u c t i o n o f t h e c o n c e p t i o n s a n d t h e o r i e s o f c as e - b a s e d r e as o n i n g . t h e n a c c o r d i n g t o t h e a p p l ic a t i o n fi e l d s o f d i a g n o s e , e x p a t i a t e t h e k e y p a rt s o f c b r s y s t e m : c a s e r e p r e s e n t a t i o n a n d s t o r a g e , c as e r e t r i e v a l a n d m a t c h i n g , c a s e a m e n d i n g , s t u d y a n d i n d e x . t h e c o mb i n a t i o n o f e x t e n s i o n a l ma tt e r a n d s t a n d a r d t a b l e i s u s e d i n c ase re p r e s e n t a t i o n a n d s t o r a g e ， i t s o l v e s t h e d e v e l o p m e n t o f re p r e s e n t a t io n s o f k n o w l e d g e i n a n e f f i c i e n c y w a y ; a n d t h e c o m b i n a t i o n o f n e a r e s t n e i g h b o r m e t h o d a n d t h e r e d u c e i n d i ff e r e n t l e v e ls a c c o r d i n g t o s o m e t a c t i c i s e m p l o y e d in c as e r e t r i e v a l , t o d e v e l o p t h e r e t r i e v a l e ff i c i e n c y a n d r e d u c e t h e p r o c e s s o f r e t r i e v a l w e u s e t h e c o n c e p t i o n o f a t t r i b u t e s s p a c e i n t h e r e t r ie v a l p r o c e s s ; i n c as e m e n d i n g , w e u s e t w o le v e l s d a t a b a s e s o f c as e s t o s i m u l a t e t h e a b i l i t y o f s t u d y o f m e n , t o m a k e t h e s y s t e m h a s t h e a b i l i t y o f s e l f - d r i v e n s t u d y， a s t r u c t u r e l i k e b + t r e e b e u s e t o s t o r e t h e c a s e o f i n d e x .mo r e o v e r , t h i s p a p e r a l s o d i s c u s s e s t h e i n t e g r a t i o n o f c b r a n d r b r， d i s t r i b u t e d d a t a b as e a n d cbr . k e y wo r d s : c b r , t a c t i c , t h e a r i t h m e t i c o f t h e r e d u c e i n d i ff e r e n t l e v e l a c c o r d i n g t o s o m e c as e s t u d y , a t t r i b u t e s s p a c e i i i 东 北大学硕士学位论文 声明 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名: 4林 日 期 : ?. o q . r . r 学位论文版权使用授权书 本学位论文作者和指导教师完全了 解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流， 请在下方签名; 否则视为不同意。 ) 学位论文作者签名: 签 字日 期: -2 ,ftf .酝年 冬 、 1 . 1 6 导师签名 签字日期 : 贵 添毛 z 5 、 l . 1 子 东北大学硕士学位论文 第一章 引言 竺 - 音日! 育 二 月 ，勺井j .厂刁 1 . 1 人工智能简介 人t - 智能 ( a r t i fi c i a l i n t e l l i g e n c e ， 简称a i )， 顾名思义， 就是人造智能， 指 的是用电 子计算机模拟或实现的智能，人工智能同时也是一个学科名称， 她是研 究如何使机器 ( 计算机)具有智能的科学和技术，特别是人类智能如何在计算机 上实 现或再现的 科学和技术。因此，当前的人工智能是计算机科学的一个分 支 l 1 人工智能虽然是计算机科学的一个分支，但它的研究却不仅涉及到计算机科 学，而且还涉及到脑科学，神经生理学，心理学，语言 学，逻辑学，认知 ( 思维) 科学， 行为科学和数学，以 及信息论，控制论和系统论等许多学科领域。因此， 人工智能实际上是一门 综合性的交叉学科和边缘学科川 。 人工智能从诞生发展到今天经历了一条漫长的路， 许多科研人员为此而不懈努 力。 人工智能的开始可以 追溯到电 子学出 现以 前。 像布尔和其他一些哲学家和数 学家建立的理论原则后来成为人工智能逻辑学的基础。而人工智能真正引 起研究 者的兴趣则是1 9 4 3 年计算机发明以 后的事。 技术的发展最终使得人们可以仿真人 类的智能行为，至少看起来不太遥远。接下来的四十年里，尽管碰到许多阻碍， 但是人工智能仍然从最初只有十几个研究者成长到现在数以千计的工程师和专家 在研究;从一开始只有一些下棋的小程序到现在的用于疾病诊断的专家系统，人 工智能的发展有目 共睹。人工智能在某些侧面，己 经表现出相当高的水平。在机 器博弈， 机器证明，识别和控制等方面，当前的机器智能的确己达到或接近了能 同人类抗衡和媲美的水平。 人 工 智 能的目 标可 分为 远期目 标 和近 期目 标 川 。 远期目 标是 要 制 造 智能 机 器， 也就是使计算机像人一样具有自 动发现规律和利用规律的能力，或者说具有自 动 获取知识和利用知识的能力， 从而扩展和延伸人的智能。近期的目 标是实现机器 智能，即先部分的或某种程度的实现机器的智能，从而实现有的计算机更灵活， 更好用和更有用，成为人类的智能化处理的工具。主要是研究如何使现有的计算 机更聪明，即使它能够运用知识去处理问题。为了实现这一目 标，人们需要根据 现有计算机的特点， 研究实现智能的有关理论、 方法和技术， 建立相应的 智能系 统。 ，1 东北大学硕士学位论文 第一章 引言 竺 - 音日! 育 二 月 ，勺井j .厂刁 1 . 1 人工智能简介 人t - 智能 ( a r t i fi c i a l i n t e l l i g e n c e ， 简称a i )， 顾名思义， 就是人造智能， 指 的是用电 子计算机模拟或实现的智能，人工智能同时也是一个学科名称， 她是研 究如何使机器 ( 计算机)具有智能的科学和技术，特别是人类智能如何在计算机 上实 现或再现的 科学和技术。因此，当前的人工智能是计算机科学的一个分 支 l 1 人工智能虽然是计算机科学的一个分支，但它的研究却不仅涉及到计算机科 学，而且还涉及到脑科学，神经生理学，心理学，语言 学，逻辑学，认知 ( 思维) 科学， 行为科学和数学，以 及信息论，控制论和系统论等许多学科领域。因此， 人工智能实际上是一门 综合性的交叉学科和边缘学科川 。 人工智能从诞生发展到今天经历了一条漫长的路， 许多科研人员为此而不懈努 力。 人工智能的开始可以 追溯到电 子学出 现以 前。 像布尔和其他一些哲学家和数 学家建立的理论原则后来成为人工智能逻辑学的基础。而人工智能真正引 起研究 者的兴趣则是1 9 4 3 年计算机发明以 后的事。 技术的发展最终使得人们可以仿真人 类的智能行为，至少看起来不太遥远。接下来的四十年里，尽管碰到许多阻碍， 但是人工智能仍然从最初只有十几个研究者成长到现在数以千计的工程师和专家 在研究;从一开始只有一些下棋的小程序到现在的用于疾病诊断的专家系统，人 工智能的发展有目 共睹。人工智能在某些侧面，己 经表现出相当高的水平。在机 器博弈， 机器证明，识别和控制等方面，当前的机器智能的确己达到或接近了能 同人类抗衡和媲美的水平。 人 工 智 能的目 标可 分为 远期目 标 和近 期目 标 川 。 远期目 标是 要 制 造 智能 机 器， 也就是使计算机像人一样具有自 动发现规律和利用规律的能力，或者说具有自 动 获取知识和利用知识的能力， 从而扩展和延伸人的智能。近期的目 标是实现机器 智能，即先部分的或某种程度的实现机器的智能，从而实现有的计算机更灵活， 更好用和更有用，成为人类的智能化处理的工具。主要是研究如何使现有的计算 机更聪明，即使它能够运用知识去处理问题。为了实现这一目 标，人们需要根据 现有计算机的特点， 研究实现智能的有关理论、 方法和技术， 建立相应的 智能系 统。 ，1 东 北大学硕士学 位论文第一章 引言 目 前 人 工智 能 正 处于 蓬 勃发 展当 中 fz l ， 并 且己 经 取 得许多 研究 成果。 同 时 人工 智能的研究更多的是结合具体应用领域来进行的，几个主要的应用领域如下: ( 1 )专家系统 ( e x p e rt s y s t e m ) ; ( 2 ) 自 然语言 理解 ( n a t u r e l a n g u a g e u n d e r s t a n d in g ): ( 3 )机器学习 ( ma c h i n e l e a r n i n g ); ( 4 ) 定理证明 ( t h e o re m p r o v i n g ); ( 5 )分 布式人 s智能 ( d i s t r i b u t e d a rt i f i c i a l i n t e l l i g e n c e ); ( 6 ) 机器人 ( r o b o t s ): ( 7 )模式识别 ( p a t t e rn r e c o g n i t i o n ); ( 8 ) 博弈 ( g a m e p l a y i n g ); ( 9 ) 计算机视觉 ( c o m p u t e r v i s i o n ); ( 1 0 )人z神经网络 ( a rt i f i c i a l n e u r a l n e t w o r k )。 在以 上几个应用领域中， 专家系统和自 然语言理解是目 前计算机领域较为热 门的话题，他们在众多领域得到了 广泛的 应用，下面简单介绍一下专家系统。 1 . 2 专家系统简介 专家系统 ( e x p e rt s y s t e m ) 亦称为 专家咨 询系统， 它是一 种智能计 算 机 ( 软 件) 系 统f3 1顾名思 义， 专 家系 统就是能 像人 类专 家一 样解决困 难， 复 杂的 实际问 题的计算机 ( 软件)系统。专家系统实现了 人工智能从理论研究走向实际应用， 从一般思维规律探讨走向专门知识运用的重大突破，是人工智能发展历史上的一 次重要转折。 自1 9 6 5 年第一个专家系 统d e n d r a l 问 世以来， 专家系统技术和应 用获得了长足的发展和进步。随着知识工程技术的日 渐丰富和成熟，各种实用的 应用于医疗诊断、图像处理、地质勘探、实时监控、金融决策、计算机科学等众 多 领域专家系统不断涌现f4 1 专家系统可以根据某个应用领域的一个或多个人类专家提供的知识和经验进 行推理和判断， 模拟人类专家的决策过程，以 解决那些需要人类专家决定的复杂 问 题 1 1 。 专家 系统应当 具 备两个基 本因 素: ( 1 ) 丰富的专业知识和实践经验。 ( 2 ) 独特的分析问题和解决问题的方法和策略。 此外，它还有如下一些基本特点: ( 1 )从问题的处理性质上看，专家系统要善于解决那些不确定性的 .2。 东 北大学硕士学 位论文第一章 引言 目 前 人 工智 能 正 处于 蓬 勃发 展当 中 fz l ， 并 且己 经 取 得许多 研究 成果。 同 时 人工 智能的研究更多的是结合具体应用领域来进行的，几个主要的应用领域如下: ( 1 )专家系统 ( e x p e rt s y s t e m ) ; ( 2 ) 自 然语言 理解 ( n a t u r e l a n g u a g e u n d e r s t a n d in g ): ( 3 )机器学习 ( ma c h i n e l e a r n i n g ); ( 4 ) 定理证明 ( t h e o re m p r o v i n g ); ( 5 )分 布式人 s智能 ( d i s t r i b u t e d a rt i f i c i a l i n t e l l i g e n c e ); ( 6 ) 机器人 ( r o b o t s ): ( 7 )模式识别 ( p a t t e rn r e c o g n i t i o n ); ( 8 ) 博弈 ( g a m e p l a y i n g ); ( 9 ) 计算机视觉 ( c o m p u t e r v i s i o n ); ( 1 0 )人z神经网络 ( a rt i f i c i a l n e u r a l n e t w o r k )。 在以 上几个应用领域中， 专家系统和自 然语言理解是目 前计算机领域较为热 门的话题，他们在众多领域得到了 广泛的 应用，下面简单介绍一下专家系统。 1 . 2 专家系统简介 专家系统 ( e x p e rt s y s t e m ) 亦称为 专家咨 询系统， 它是一 种智能计 算 机 ( 软 件) 系 统f3 1顾名思 义， 专 家系 统就是能 像人 类专 家一 样解决困 难， 复 杂的 实际问 题的计算机 ( 软件)系统。专家系统实现了 人工智能从理论研究走向实际应用， 从一般思维规律探讨走向专门知识运用的重大突破，是人工智能发展历史上的一 次重要转折。 自1 9 6 5 年第一个专家系 统d e n d r a l 问 世以来， 专家系统技术和应 用获得了长足的发展和进步。随着知识工程技术的日 渐丰富和成熟，各种实用的 应用于医疗诊断、图像处理、地质勘探、实时监控、金融决策、计算机科学等众 多 领域专家系统不断涌现f4 1 专家系统可以根据某个应用领域的一个或多个人类专家提供的知识和经验进 行推理和判断， 模拟人类专家的决策过程，以 解决那些需要人类专家决定的复杂 问 题 1 1 。 专家 系统应当 具 备两个基 本因 素: ( 1 ) 丰富的专业知识和实践经验。 ( 2 ) 独特的分析问题和解决问题的方法和策略。 此外，它还有如下一些基本特点: ( 1 )从问题的处理性质上看，专家系统要善于解决那些不确定性的 .2。 东 北大学 硕士学位论文第一章 引 言 非结构化的，没有算法解或虽有算法解但在现有的机器上无法实施的困难问 题。 例如:医疗诊断，地质勘探，天气预报， 市场预测， 管理决策，军事领域等领域 的问题。 ( 2 )从处理问题的方法看， 专家系统则是靠知识和推理来解决问题 ( 不像传 统软件系统使用固定的算法来解决问题) ，所以，专家系统是基于知识的智能问题 求解系统。 ( 3 )从系统的结构来看， 专家系统则强调知识与 推理的分离， 因而系统具有 很好的灵活性和可扩充性。 ( 4 )专家系统一般还具有解释功能， 即 在运行过程中一方面能回答用户提出 的问题，另一方面还能对随后的输出 ( 结论)或处理问题的过程作出 解释。 ( 5 ) 有些专家系统还具有 “ 自 学习”能力，即不断对自己的知识进行扩充， 完善和提炼。这一点是传统系统所无法比拟的。 ( 6 ) 专家系统不像人那样容易疲劳， 遗忘，易受环境，情绪等的影 响，它可始终如一的以专家级的高水平求解问题。因此，从这种意义上讲，专家 系统可以超过专家本人。 领域专家 知识 _ 程师 人机接口 解释机构 推理机 知识获取机构 数据库及其专家系 统 知识库及其专家系统 图1 . 1 专家系统的一般结构 f ig . . i b a s i c s t r u c t u r e o f e x p e rt s y s t e m 针对专家系统的功能与特点，可以用图1 . 1 来表示专家系统的一般结构。 专家系统区别于常规程序的一个重要标志是它能运用专家系统的知识 进行推 理，能从一种判断推出另一种判断，不断向目 标逼近。目前，专家系统的推理方 法主 要有两 种， 基于 规则的 推理 ( r u le - b as e d r e as o n in g ， 简称r b r ) 和基于事 例的 推 理( c as e d - b as e d r e a s o n i n g , 简称c b r ) o .3 东 北大学硕士学位论文 1 . 2 . 1 基于规则推理简介 第一章 引 言 基于规则推理( r u l e - b a s e d r e a s o n i n g ,简称r b r ) 是目 前多数专家系统所采用的 推理机制。基于规则推理的专家系统主要由两部分组成:知识库和推理机，知识 库用来存储从专家那里得到的关于某一领域的专门知识，推理机具有推理的能力， 即能够根据知识推导出结论，而 不是简单的去搜索现成的答案。 在基于规则的专家系统中， 其推理原理如图1 .2 所示。一个问题的求解过程是 这样的:当给定一个条件时，推理机在知识库中，从头一条将它与各知识基进行 比较，如果匹配，则完成该步推理，且继续进行下一步的推理，若在整个知识库 无匹配的知识基，则结束推理，这样使问题得到求解。 图1 .2基于 规则专家系统推理模式 f i g . 1 .2 r e a s o n i n g m o d e l o f t u l e - b a s e d re a s o n i n g e x p e rt s y s t e m 1 . 2 . 2 基于事例推理简介 基于 事 例的 推理 ( c a s e - b as e d r e as o n i n g ,c b r ) 是目 前人工智能 研究中一 种正 在 迅速发展的推理方法，自 从 7 0 年代末8 0 年代初兴起之后一直受到人工智能 研究 者的 高 度重视 图 。 它是一 种相似 推理方 法， 核 心思 想是用过去的 事 例和经 验来解决 当前的问题。 一个典 型的 事例推理过程可以 归 纳 如下 6 . ( 1 ) 按照一定的形式向系统描述当前事例。 ( 2 ) 从事例库中检索出与当前问 题相似的事例。 ( 3 ) 若该事例与当前事例完全匹配，输出该事例的求解方案，否则修正该 事例，形成当前问题的求解。 ( 4 ) 对当前问题的求解进行评价。 4 东 北大学硕士学位论文 1 . 2 . 1 基于规则推理简介 第一章 引 言 基于规则推理( r u l e - b a s e d r e a s o n i n g ,简称r b r ) 是目 前多数专家系统所采用的 推理机制。基于规则推理的专家系统主要由两部分组成:知识库和推理机，知识 库用来存储从专家那里得到的关于某一领域的专门知识，推理机具有推理的能力， 即能够根据知识推导出结论，而 不是简单的去搜索现成的答案。 在基于规则的专家系统中， 其推理原理如图1 .2 所示。一个问题的求解过程是 这样的:当给定一个条件时，推理机在知识库中，从头一条将它与各知识基进行 比较，如果匹配，则完成该步推理，且继续进行下一步的推理，若在整个知识库 无匹配的知识基，则结束推理，这样使问题得到求解。 图1 .2基于 规则专家系统推理模式 f i g . 1 .2 r e a s o n i n g m o d e l o f t u l e - b a s e d re a s o n i n g e x p e rt s y s t e m 1 . 2 . 2 基于事例推理简介 基于 事 例的 推理 ( c a s e - b as e d r e as o n i n g ,c b r ) 是目 前人工智能 研究中一 种正 在 迅速发展的推理方法，自 从 7 0 年代末8 0 年代初兴起之后一直受到人工智能 研究 者的 高 度重视 图 。 它是一 种相似 推理方 法， 核 心思 想是用过去的 事 例和经 验来解决 当前的问题。 一个典 型的 事例推理过程可以 归 纳 如下 6 . ( 1 ) 按照一定的形式向系统描述当前事例。 ( 2 ) 从事例库中检索出与当前问 题相似的事例。 ( 3 ) 若该事例与当前事例完全匹配，输出该事例的求解方案，否则修正该 事例，形成当前问题的求解。 ( 4 ) 对当前问题的求解进行评价。 4 东北大学硕士学位论文 第一章 引言 ( 5 ) 将新的事例加入到事例库中，备以 后求解问题使用。 具体过程如图 1 .3 所示。 结果调 格( r e v i s e ) 1.we， 修止后的解匹配事例的 解决方案 图1 .3基于 事例推理的一般过程 f i g . 1 .3 b as i c p ro c e s s o f c a s e - b a s e d r e as o n i n g 众所周知，知识获取的 “ 瓶颈”问题妨碍了专家系统的快速开发。而基于事 例的 推理( c b r ) 充分利用另一种知识资源: 以 往设计成功的 例子或专家经验。 它以 事例的形式来体现知识，从而克服了知识获取困难的问题。 1 . 3 本文主要内 容及组织结构 本文探讨了基于事例推理循环的基本过程，并且结合一个医院医疗诊断系统 对循环中的各个核心环节进行了研究。在事例表示中采用了 可拓物元和标准表结 构相结合的方法，有效的 解决了知识表达的可拓性问题; 在事例检索中， 采用了 最近相邻算法和分级过滤算法相结合的策略， 确保了系统的检索效率， 提高了系 统的准确率:在系统事例的学习环节中，采用两级事例库的方式模拟了一定的人 脑学习的方式，改善了系统的整体运行效率及性能。 本文的组织结构如下: .5 东北大学硕士学位论文 第一章 引言 ( 5 ) 将新的事例加入到事例库中，备以 后求解问题使用。 具体过程如图 1 .3 所示。 结果调 格( r e v i s e ) 1.we， 修止后的解匹配事例的 解决方案 图1 .3基于 事例推理的一般过程 f i g . 1 .3 b as i c p ro c e s s o f c a s e - b a s e d r e as o n i n g 众所周知，知识获取的 “ 瓶颈”问题妨碍了专家系统的快速开发。而基于事 例的 推理( c b r ) 充分利用另一种知识资源: 以 往设计成功的 例子或专家经验。 它以 事例的形式来体现知识，从而克服了知识获取困难的问题。 1 . 3 本文主要内 容及组织结构 本文探讨了基于事例推理循环的基本过程，并且结合一个医院医疗诊断系统 对循环中的各个核心环节进行了研究。在事例表示中采用了 可拓物元和标准表结 构相结合的方法，有效的 解决了知识表达的可拓性问题; 在事例检索中， 采用了 最近相邻算法和分级过滤算法相结合的策略， 确保了系统的检索效率， 提高了系 统的准确率:在系统事例的学习环节中，采用两级事例库的方式模拟了一定的人 脑学习的方式，改善了系统的整体运行效率及性能。 本文的组织结构如下: .5 东 北大学 硕士学 位论文第 一章 引 言 第一章:引言，概要介绍人工智能与专家系统的相关理论。 第二章:介绍了 基于事例推理循环的基本过程、基于事例推理与基于规则推 理的区别及优点和基于事例推理的发展前景等。 第三章:介绍了本文中相关的一些概念， 知识和算法。 第四章:介绍了基于事例推理系统的整体结构的设计和设想，主要环节实 现 的介绍:事例的组织和表示方法.事例的检索匹配，事例的修改，学习和索引。 第五章:分析 c b r和分布式数据库结合的可行性以及在 c b r系统的事例学 习环节中c b r和 r b r的结合。 . 6 东 北大学 硕士学 位论文 第 二章 基于 事例 推理概 述 第二章基于事例推理概述 2 . 1 基于事例推理 基 于 事 例的 推理 ( c a s e - b a s e d r e a s o n in g , 简 称c b r ) 是基于知 识的 专家 系 统 ( k n o w le d g e - b a s e d s y s t e m s ， 简 称k b s ) 领 域中 的 一 个分 支。 基于 事 例 推 理 起 源 于认知科学中记忆在人类推理活动中所扮演的角色， 1 9 7 7 年s c h a n k 和 a b e l s o n 在 这 方 面 的 工 作 被 认 为 是c b r 的 起 源 7 随 后 美 国 耶 鲁 大 学r o g e r s c h a n k 又 探 索了 记 忆 中 的 事 例 在 问 题 解 决 和 学 习 中 的 作 用， 于1 9 8 2 年 在 d y n a m ic m e m o r y ) la ) 一书中提出了c b r认知模型以及在此基础上k o lo d n e r 开发的第一个实际c b r应 用 系 统c y r u s 9 。 在8 0 年代后期， 美国 的d a r p a项目 导 致了r e m i n d 系 统的 产 生， 这被认为是c b r从认知科学向人工智能方向的转变的标志。 如今， c b r己作 为人i : 智能的一种主要推理技术。 由于 c b r自 身的特点使其在众多的领域都得到 了较为广 一泛的应用。1 9 8 7 年以来国际研究界每年举行c b r研讨会， 先后在通用间 题求解、 法律事例、 医疗诊断、 医药等领域证明了c b r方法的有效性和实用性 ta l 一个c b r系统由事例索引 机制， 检索匹配机制， 事例改写和事例库等核心模 块组成，如图 2 . 1 所示。 图2 . 1 c b r系统的基本结构 f i g . 2 . l b a s i c s t r u c t u r e o f c a s e - b a s e d r e a s o n i n g 基于事例推理在许多方面都有别于其他的人工智能方法。与单独依赖于问 题 7 东 北大学 硕士学 位论文 第 二章 基于 事例 推理概 述 第二章基于事例推理概述 2 . 1 基于事例推理 基 于 事 例的 推理 ( c a s e - b a s e d r e a s o n in g , 简 称c b r ) 是基于知 识的 专家 系 统 ( k n o w le d g e - b a s e d s y s t e m s ， 简 称k b s ) 领 域中 的 一 个分 支。 基于 事 例 推 理 起 源 于认知科学中记忆在人类推理活动中所扮演的角色， 1 9 7 7 年s c h a n k 和 a b e l s o n 在 这 方 面 的 工 作 被 认 为 是c b r 的 起 源 7 随 后 美 国 耶 鲁 大 学r o g e r s c h a n k 又 探 索了 记 忆 中 的 事 例 在 问 题 解 决 和 学 习 中 的 作 用， 于1 9 8 2 年 在 d y n a m ic m e m o r y ) la ) 一书中提出了c b r认知模型以及在此基础上k o lo d n e r 开发的第一个实际c b r应 用 系 统c y r u s 9 。 在8 0 年代后期， 美国 的d a r p a项目 导 致了r e m i n d 系 统的 产 生， 这被认为是c b r从认知科学向人工智能方向的转变的标志。 如今， c b r己作 为人i : 智能的一种主要推理技术。 由于 c b r自 身的特点使其在众多的领域都得到 了较为广 一泛的应用。1 9 8 7 年以来国际研究界每年举行c b r研讨会， 先后在通用间 题求解、 法律事例、 医疗诊断、 医药等领域证明了c b r方法的有效性和实用性 ta l 一个c b r系统由事例索引 机制， 检索匹配机制， 事例改写和事例库等核心模 块组成，如图 2 . 1 所示。 图2 . 1 c b r系统的基本结构 f i g . 2 . l b a s i c s t r u c t u r e o f c a s e - b a s e d r e a s o n i n g 基于事例推理在许多方面都有别于其他的人工智能方法。与单独依赖于问 题 7 东 北大 学硕士学 位论文第二章 基于事例推理 概述 领域中的一般性知识， 或在问题描述与结论之间建立一般性联系的传统a i 方 法所 不同的是，c b r能利用过去有经验的和具体事例相关的特定知识，一个新问题的 解决是通过寻找一个与之相似的以往事例，把它重新应用到新问题的环境中来; 另一 个明显的不同在于，c b r还是一个持续的、渐进增长的学习过程，一旦解决 了一个新问题，就获得了新的经验，可以用以解决将来的问题。 其中事例库提供支持问题求解的一组事例，它是系统过去进行问题求解经验 的聚集。根据问 题描述，事例检索匹配机制从事例库中查找一个与当前问 题相匹 配的事例，如果该事例满足问 题描述的要求，则将相应的结果输出，否则根据问 题描述，对检索出的事例进行修改，事例修改的结果形成一个完全满足问题描述 的答案，该结果同时作为一个新的事例经索引机制组织到事例库中以备将来使用。 2 . 】 . 1 基于事例推理概述 首 先介绍有关事例推理的一些概念n i 定义2 . 1 事例( c a s e ) 是过去一定条件下，满足特定要求的设计结果。 c” ( q1 , c o , r ) 其中c 表 示 事 例 ( c as e ) , g 表 示设 计目 标( g o a l s ) , i 表 示设 计 初 始条 件 ( i n i ti a l s ta t e ) , c o 表示设计约束( c o n s t r a i n t s ) , r表示设计结果 ( r e s u lt s ) . 从上述定义可以看出，一个设计事例至少包含如下几个方面: ( 1 ) 设计目 标:决定了事例的根本性质，决定了设计采用的技术路线和最 终结果。 ( 2 ) 初始条件:指定了 该事例产生的 环境特征。 ( 3 ) 设计约束:指明了 该事例在达到设计目 标的同时应满足的条件。 ( 4 ) 设计结果:是设计活动的最终反映，表现为一系列属性与属性值的 配对，或表现为一系列行为的规范，或是设计失败的教训。 定 义 2 .2事例空间 ( c as e s p a c e ) 是 所有事 例的 集合， 每个事例是事 例空 间的一个元素，事例空间代表了过去针对各种设计要求的设计结果。 c s = c ; i = 1 ,2 , . . . ,n ) 其中c s 表示事例空间，c ; 表示c s 中的任一事例元素，n 表示c s 中的事例个数。 定义2 .3 事例库 ( c as e b as e ) 是事例空间的物理体现， 表现为事例的有 序 组织和管理。事例库应该包含有事例信息，事例的索引和事例间的关联。 c b= ( c r , c r i, c l ) 其中c b表示事例库，c r 表示事例信息，c r 【 表示索引，c l 表示事例间关联。 .8 东 北大 学硕士学 位论文第二章 基于事例推理 概述 领域中的一般性知识， 或在问题描述与结论之间建立一般性联系的传统a i 方 法所 不同的是，c b r能利用过去有经验的和具体事例相关的特定知识，一个新问题的 解决是通过寻找一个与之相似的以往事例，把它重新应用到新问题的环境中来; 另一 个明显的不同在于，c b r还是一个持续的、渐进增长的学习过程，一旦解决 了一个新问题，就获得了新的经验，可以用以解决将来的问题。 其中事例库提供支持问题求解的一组事例，它是系统过去进行问题求解经验 的聚集。根据问 题描述，事例检索匹配机制从事例库中查找一个与当前问 题相匹 配的事例，如果该事例满足问 题描述的要求，则将相应的结果输出，否则根据问 题描述，对检索出的事例进行修改，事例修改的结果形成一个完全满足问题描述 的答案，该结果同时作为一个新的事例经索引机制组织到事例库中以备将来使用。 2 . 】 . 1 基于事例推理概述 首 先介绍有关事例推理的一些概念n i 定义2 . 1 事例( c a s e ) 是过去一定条件下，满足特定要求的设计结果。 c” ( q1 , c o , r ) 其中c 表 示 事 例 ( c as e ) , g 表 示设 计目 标( g o a l s ) , i 表 示设 计 初 始条 件 ( i n i ti a l s ta t e ) , c o 表示设计约束( c o n s t r a i n t s ) , r表示设计结果 ( r e s u lt s ) . 从上述定义可以看出，一个设计事例至少包含如下几个方面: ( 1 ) 设计目 标:决定了事例的根本性质，决定了设计采用的技术路线和最 终结果。 ( 2 ) 初始条件:指定了 该事例产生的 环境特征。 ( 3 ) 设计约束:指明了 该事例在达到设计目 标的同时应满足的条件。 ( 4 ) 设计结果:是设计活动的最终反映，表现为一系列属性与属性值的 配对，或表现为一系列行为的规范，或是设计失败的教训。 定 义 2 .2事例空间 ( c as e s p a c e ) 是 所有事 例的 集合， 每个事例是事 例空 间的一个元素，事例空间代表了过去针对各种设计要求的设计结果。 c s = c ; i = 1 ,2 , . . . ,n ) 其中c s 表示事例空间，c ; 表示c s 中的任一事例元素，n 表示c s 中的事例个数。 定义2 .3 事例库 ( c as e b as e ) 是事例空间的物理体现， 表现为事例的有 序 组织和管理。事例库应该包含有事例信息，事例的索引和事例间的关联。 c b= ( c r , c r i, c l ) 其中c b表示事例库，c r 表示事例信息，c r 【 表示索引，c l 表示事例间关联。 .8 东 北大学硕士学位论文 第二章 基于事例推理概述 定义2 .4 事例索引 ( c a s e i n d e x ) 是事例的浓缩和代表，是一个事例区 别于 其他事例的重要标志。 c , = f ( x , , x 2 , ， x) n 0 其中c , 表示事例索引:x 1 . x 2 、二， . . x 。 表示影响c , 所代表事例的n 个属性: f 表示g关于x ,( ) i 0 其中c , 表示事例索引:x 1 . x 2 、二， . . x 。 表示影响c , 所代表事例的n 个属性: f 表示g关于x ,( ) i n ) 的函数。 2 . 1 . 2 基于事例推理基本过程 基于事例的推理过程主要由问题描述、事例检索、事例匹配、事例修正、 事 例学习 及事例保存等组成1 1 2 ) ( 1 3 ，如图2 .2 所示。 问题描述又称为事例表示，它是将待求解问题用合理的知识表示形式在计算 机中表达出来，以便于进一步处理。 图2 .2塞于事例推理的过程 f i g .2 .2 p r o c e s s o f c a s e - b a s e d r e a s o n i n g 事例检索是根据当前的问题从事例库中检索出相似的事例或事例集。 事例匹配是从检索出的事例中获得若干个求解方案， 判断是否符合当前的 求 解需要，若符合，则直接利用这些方案解决问题;否则，对所检索出的事例进行 9 东 北 大 学 硕 士 学 位 论 文_签 三 主鱼型4 1 # 51 4m 兰 修正。 事例修正是指如果事例库中现存的事例与所要求解决的问题存在差异，那么 就需要对这些事例组合进行修改，使之适合于求解当前的问题，得到解决当前问 题的新方案。 事例学习是指对求解结果进行分析评价，若求解结果可以接受，则保存事例， 得到问题的解;否则，重新对事例进行匹配和修正。 事例保存是将当前问题及其求解方案形成新的事例，根据一定的策略加入到 事例库中。 2 . 1 . 3 事例表示和存储 在c b r系统中，问题求解的状态及其求解策略用一个事例来表示。最初的事 例表示借鉴经验在大脑中的记忆形式，采用剧本的方式，以期可以立体地表示记 hz 。但在实践中人们发现这种方法容易引起相近事例间的混淆。不足以刻画人类 的 记忆。 在实践和理论的研究中，逐渐采用其他一些表示方法，如框架表示法、 文本方式、因果关系图、语义网等。 事例的存储形式是影响c b r系统效率的关键。事例组织的合理，事例检索系 统就能够迅速的从事例库中检索