（计算机应用技术专业论文）范例推理在gis中的应用研究.pdf

摘要摘要基于知识工程的系统研究历来是计算机理论及应用研究的前沿之一，但是知识获取的瓶颈问题，一直束缚着研究人员的研究进程，而范例推理系统( c b r ) 恰能较好地解决这个问题，目前已广泛应用于各种问题求解，有着十分良好的应用前景。范例推理是一种用先前求解问题的经验和方法，通过类比和联想来解决当前相似问题的推理技术，它是动态决策环境下求解不良结构问题的常用方法。地理信息系统( g i s ) 是6 0 年代发展起来的一种集数据采集、存储、管理、分析于一体，并能够描述地球表面信息( 包括大气层在内) 以及空间、地理分布相关数据的空间信息系统。6 i s 系统作为一种新兴的地学工具，具有很强的空间分析能力，但由于地学问题的复杂性，一些地学现象很难用确切的模型进行模拟和预测。另外，随着计算机技术的迅速发展和社会需求的不断增加，6 i s 技术逐渐走向成熟，应用领域不断扩大。人们对g i s 的要求己经不再局限于简单的图层显示和自动制图，人们期望它能为决策提供依据。考虑到范例推理系统的在处理半结构化和非结构化问题方面的出色能力，本文探讨了如何将范例推理应用于g i s 中。根据国内外学者在地理范例领域的研究成果，给出了地理范例个较为科学的定义。在此基础上，重点讨论了基于范例推理的g i s 系统结构，研究了如何进行地理范例表达，如何构建地理范例，以及如何在地理范例空间中进行空间推理。本文的主要做法是将改进的t e s s e r a l 方法用于属性信息的表达，并在t e s s e r a l 空间内进行空间推理。应用研究方面，研制开发了“数字合肥”的子系统。其中的绿化管理模块就是一个基于c b r 的g i s 实例。“数字合肥”是基于m a p l n f o 平台的g i s 系统，在这个平台上，我们实现了g i s 与c b r 系统的对接。在这个模块中以改进的t e s s e r a l 方法来表达属性信息并进行空间推理，实现了在前面理论研究中的想法。关键词：范例推理系统，地理信息系统，地理范例，t e s s e r a l 推理a b s t r a ( ? ra b s t i 认c tt h er e s e a r c ho fk n o w l e d g ee n g i n e e r i n gh a sa l w a y sb e e no n eo ft h ef r o n t so ft h ec o m p u t e rt h e o r ya n da p p l i c a t i o nr e s e a r c h b u tt h eb o t t l e n e c ko fk n o w l e d g ea c q u i s i t i o nc u m b e r st h er e s e a r c hp r o g r e s so fa ir e s e a r c h e r c b r ( c a s eb a s e dr e a s o n i n g ) c a ns o l v et h i sp r o b l e mw i t hb e t t e rr e s u l t sa n di sw i d e l ya p p l i e dt ov a r i o u sf i e l d so fp r o b l e ms o l v i n g t h ep r o s p e c to ft h ea p p l i c a t i o ni sv e r yw e l l c a s sb a s e dr e a s o n i n gs y s t e mi sav e r yi m p o r t a n tm a c h i n el e a r n i n gm e t h o d t oe x p l a i nan e wo b j e c tc a s e ，c b rs y s t e ml o o k u po r i g i n a lc a s ei nt h ec a s eb a s ei no r d e rt of i n dao l dc a s ew h i c hi st h em o s ts i m i l a rt ot h en e wo b j e c tb a s e g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) w a sd e v e l o p e df r o m1 9 6 0 s i ti n t e g r a t e st h ed a t ac o l l e c t i o n 、s t o r a g e 、m a n a g e m e n ta n da n a l y s i s i tc a nd e s c r i b et h ei n f o r m a t i o no fe a r t hs u r f a c e( i n c l u d i n ga e r o s p h e r e ) a n dt h es p a t i a li n f o r m a t i o no fs p a c ea n dg e o g r a p h yd i s t r i b u t i o n g i s ，a san e wg e o g r a p h yt o o l ，i sf a m o u sf o ri t sp o w e r f u ls p a c ea n a l y s i sa b i l i t y b u t ，a sw ek n o w , b e c a u s eo ft h ec o m p l e x i t yo ft h eg e o g r a p h yp r o b l e m s ，i ti sd i f f i c u l tt oc o n s t r u c taa s s u r e dm o d e lt op r e d i c tg e o g r a p h yp h e n o m e n a a l s o ，w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n ds o c i a ld e m a n d ，g i st e c h n o l o g yi sg o i n gu pa n dt h er a n g eo fi t sa p p l i c a t i o na r ew i d e n i n gc o n t i n u o u s l y p e o p l en o to n l yw a n tg i st os h o wm a ps i m p l ya n dt om a k em a pa u t o m a t i c a l l y ，b u ta l s ow a n tg i st og i v ep e o p l es o m e t h i n gt os u p p o r td e c i s i o n c o n s i d e r i n gt h ef i n e n e s sa b i l i t yt os o l v et h eh a l f - s t r u c t u r e da n dn o n - s t r u c t u r e dp r o b l e mo ft h ec b rs y s t e m ，t h et h e s i sd i s c u s s e st h es t r u c t u r eo ft h ec b r b a s e dg i ss y s t e m i tp r e s e n t sh o wt oc o n s t r u c tg e o - c a s e ，h o wt oe x p l a i nag e o c a s ea n dh o wt or e a s o ni ti ni t so w nc a s e - s p a c e i nt h i st h e s i s ，t h ei m p r o v e d t e s s e r a lm e t h o dh a sb e e na p p l i e dt oe x p r e s sa t t r i b u t ei n f o r m a t i o na n dc a s e s p a c er e a s o n i n g i nt h er e s e a r c h o fa p p l i c a t i o n t h es u b s y s t e mo f d i g i t a lh e f e i h a sb e e nd e v e l o p e d t h em a n a g e m e n to fg r e e n b e l t t h em o d u l eo f d i g i t a lh e f e i 一i sae x a m p l ef o rc a s e - b a s e dg i s d i g i t a lh e f e i i sb a s e do nm a p l n f os y s t e m b a s e do n、坠! ! ! 里t h i sp l a t f o r m ，c b ra n dg i sh a v eb e e nc o n n e c t e dt oe a c ho t h e r i nt h em o d u l e ，i m p r o v e d - t e s s e r a lm e t h o dh a sb e e nu s e dt oe x p r e s sa t t r i b u t ei n f o r m a t i o na n dc a s e - s p a c er e a s o n i n g i th a sb e e nt a k et h et h e o r yr e s e a r c hf o r e h e a dt ot h ep r a c t i c e k e yw o r d s ：c a s e - b a s e dr e a s o n i n g ，g i s ，g e o - c a s e ，t e s s e r a lr e a s o n i n gi独创性声明y9 7 9 1 4 6本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得毒放赙或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名=俞磊+签字日期=2 叫年岁月乃日学位论文版权使用授权书本学位论文作者完全了解厦劭肽；有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权应做题可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。学位篓篡? 篙雾硼桃篆二名：1 宪匕彳音学位论文作者签名：么冷么导师签名：l 厶)签字日期：2 6 年岁月8 日签字日期：五内6 年f 月扩日工作单位：电话：第一章绪论1 1 背景第一章绪论1 1 1 范例推理简介范例推理( c a s e b a s e dr e a s o n i n g 、c b r ) 是由目标范例的提示而得到历史记忆中的原范例来指导目标范例求解的一种策略1 1 】。c b r 是人的一种认知行为，它是基于记忆的推理。它利用类似的旧事例和旧经验来解决问题、评价方案、解决新的问题。c b r 兴起的主要原因是传统的基于规则的系统存在较多的问题，例如知识获取的瓶颈问题，对处理过的问题无记忆导致效率低下，对例外情况不能很好的处理等。而c b r 却能很好的解决上述问题。在2 0 世纪7 0 年代中期，就已经出现了一些具有c b r 思想的计算机程序。c b r 起源是1 9 7 7 年r o g e rs h a n k 和a b e l s o n 关于动态概念记忆的研究。随着认知理论的不断完善，c b r 被广泛的应用于建立智能系统。由于它具有简化知识获取、提高问题的求解质量、进行知识积累等优点，i a nw a t s o n ( 1 9 9 4 ) 等认为“c b r是紧随在人工智能的冬天之后春天里的第一颗果实”【2 l 。在】9 8 2 年，r o g e rs h a n k 出版了d y n a m i cm e m o r y 一书，书中详细的介绍了c b r 的最早研究工作，给出了在计算机上建造c b r 的方法。他的早期思想被逐渐实现，并加以应用，这一时期的代表人物是佐治亚工学院的j a n e tk o l o d n e r ，c y r u s 即是其领导开发的第一个基于范例的推理系统。在此基础上，美国许多大学的研究人员开发了一些c b r 系统。到8 0 年代后期9 0 年代初，范例推理作为基于规则推理技术的一个重要补充，已经受到人工智能研究人员的高度重视。研究范例推理的直接目的只有两个：一是模仿人类推理的思维方式，推动认知学的发展，二是建立高效可行的计算机系统。在这一时期出现了许多c b r 系统，其应用已经越来越普遍。c b r 已经广泛的应用到医疗诊断、法律、电路、农业、气象等许多领域。表1 一l 列出了国内外部分典型的c b r 软件。第一章绪论表1 - 1 国内外典型的c b r 系统工具或软件商家或研究人员要点简介国家c y r u sj a n e tk o l o d n e r第一个c b r美国h y p oe d w i n ar i s s l a n d应用于法律系统美国c a b a r e tr i s s l a n d ，s k a l a k法律，集成c b r 与r b r美国j u d g eb r a i n1 9 8 9模拟司法判决美国r e f i n e rd e r e ks l e e m a n利用c b r 进行知识获取苏格兰f o r e z王军淮河王家坝洪水预报调度中国e o f o d s周涵内燃机油产品设计系统中国目前c b r 的主要理论研究方向集中在以下几个方面：a 范例索引和检索技术：b 范例修正技术以及修正规则的获取方法；c 范例库的维护技术：d 范例工程的自动化；e 范例推理和其他方法的集成：f 范例推理的应用，研制c b r 开发平台，c b r 融合进大规模并行处理等1 3 】d从上面的论述中可以看到c b r 有以下显著优点：信息的完全表达、增量式的学习、知识获取容易、动态知识库、求解率高等。但是也正是由于这些特点决定了c b r 也存在其固有缺陷：对噪声数据敏感，系统对算法的空间复杂度和时间复杂度都有较高的要求( 否则会出现范例库越大，系统性能越弱的问题) ，范例工程的自动化程度不高。这些问题都将是今后c b r 研究的重点所在。另外，c b r 的应用方面将会在以下几个方面重点研究：c b r 在电子商务，虚拟现实和计算机安全等领域中的应用基于w e b 的分布式c b r 系统c b r 中修正方法的深入研究c b r 系统工程文本c b r 及其检索技术范例库中特征项的自动提取范例库维护的定量化分析与证明范例推理系统与其他系统的集成本文着重讨论最后一点，即范例推理与g i s 的集成。第一章绪论1 1 2g i s 系统概述g i s 是地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) 的缩写，是以地理空间数据库为基础，在计算机硬件、软件环境支持下，对空间相关数据进行采集、管理、操作、分析、模拟和显示，适时提供空间和动态地理信息，为决策服务的一类信息系统。它起源于2 0 世纪6 0 年代是一门集计算机科学、地理地质学、测绘科学、环境科学、空间科学、信息科学和管理科学等为一体的边缘学科领域f 4 】。在经历了4 0 多年的发展之后，g i s 取得了很大的成就，被广泛的用于土地资源管理、环境监测、交通运输、城市规划等各个领域。目前正是g i s 的一个飞速发展时期，g i s 的广泛普及导致了一个新概念“数字地球”的提出。在这个概念下的推动下，g i s 的理论和应用方面都取得了长足进展。随着应用面的扩大，g i s 也出现了产品化的趋势，目前世界各国已经设计出大量的实用化的g i s ，目前常用的g i s 产品已经达4 0 0 种之多。比较著名的有e s r i 的a r c i n f o 和a r c v i e w ；m a p l n f o 公司的m a p i n f op r o f e s s i o n a l m a p x 系统。而中国较为著名的系统有中国地质大学的m a p g i s ；原武汉测绘科技大学开发的g e o s t a r 等。g i s 之所以能在这么短的时间内发展如此迅速，得到如此大范围的应用，其原因就在于它优秀的空间数据管理能力和空间数据的处理分析能力。原先的各种管理系统中，几乎所有的数据和信息都以枯燥的数字形式显示，这在处理与地理有关的问题时是非常不方便的。而g i s 实现了空间信息和属性信息的集成管理，并能够完善地建立二者之间的联系。它对属性信息和空间信息进行关联后，展现给我们的是一个现实世界空间关系的模拟，让我们对客观世界有最直接、最具体、最客观的认识，而不仅仅是一堆枯燥的数据。利用g i s 不仅可以展示二维无级缩放的信息查询地图，还可以展示三维的地形模拟，这种“所见即所得”的系统使得地理工作人员工作量大大减小【5 j 。通常一个g i s 系统包括有人机对话接口部件，数据管理和处理部件和空间数据库。其中空间数据处理和分析部件是其核心部分，该部件通过一些非常成熟的数学模型对各种数据进行分析处理，产生出的结果具有高度的可信性，可以作为决策支持的重要依据。目前g i s 的研究和应用正处在个突飞猛进的时期，主要的发展方向有1 6 】：第一章绪论1g i s 中的面向对象技术研究面向对象方法因为与人类的思维方式最为接近，所以在计算机技术中被广泛应用。面向对象的g i s ，己成为g i s 的主要发展方向之一，这是因为空间信息较之传统数据库信息更为繁杂、琐碎，面向对象的方法为描述复杂的空间信息提供了一条直观、结构清晰、组织有序的方法，因而倍受重视。2时空系统的研究传统的g i s 把注意力都集中在了空间信息上而忽略了时间信息。但是很多时候时间属性和空间属性是密切相关的，例如在天气预报、环境监测等工作中，就是要依靠一系列不同时间内空间属性的变化来预测今后的发展状况。因此近些年来人们对g i s 中时态性的研究越来越重视。3 三维g i s 的深入研究三维g i s 是许多应用领域对g i s 的基本要求。目前的g i s 产品虽然大多提供了一些三维显示和操作功能，但与真三维表示和分析还有很大差距。真正的三维g i s 必须支持真三维的矢量和栅格数据模型及以此为基础的三维空间数据库，有较为成熟的模型解决三维空间数据的分析和处理问题。三维g i s 的主要研究的方向包括：三维数据结构的研究，主要包括数据的有效存储、数据状态的表示和数据的可视化；三维数据的生成和管理；地理数据的三维显示，主要包括三维数据的操作、表面处理、栅格图像、全息图像显示、层次处理等。4g i s 与其他人工智能方法的集成研究g i s 的数据分析和处理能力无疑是非常出色的，但是对于处理边缘数据和模糊数据却不是非常有效合理。这里就需要人工智能的其他手段的介入( 例如范例推理) 。1 1 3 范例推理与g i s 的结合g i s 是以数字化的形式反映人类社会赖以生存的现实世界的现势和变迁的各种数据，以及描述这些空间数据特征的属性；以模型化的方法来模拟地理系统空间研究对象的行为；在计算机软件、硬件支持下，以特定的格式支持输入输出、存储、显示，以及进行地理信息查询、综合地学分析、辅助决策的有效的工具。但是在解决较为复杂的空间问题，尤其是半结构化和非结构化的空间问题的第一章绪论时候，g i s 遇到了困难。些模糊的、不确定的因素很难在系统中表述，也很难用一个非常准确的数学模型去描述它。c b r 系统为提供了解决空间问题的一种新思路。在地理学系统中，环境非常复杂，影响结果的条件繁多，甚至有些现象到现在还无法知道其本质和原理。在这种情况下，想利用一个原理模型来做出非常准确的预测和推理几乎是不可能的。而c b r 系统作为一种经验式的问题处理系统不需要知道原理，只要有足够多的历史数据并从中抽取出源范例就可以得到较为准确的结果。而这一问题就求解的过程也是人类认识事物晟初方式的，是符合人类认知学和心理学的。因此提出了将t e s s e r a l 推理方法应用于地理范例中。1 2 本文的内容及安排本文共分为六章。第一章对分别对c b r 和g i s 这两种技术进行概述，并介绍了将c b r 应用于g i s 系统中的想法来源，简单分析了此类系统所具备的优点。第二章主要对范例推理的基本概念，基本原理及系统结构进行阐述。详细介绍了c b r 技术的关键技术，并将c b r 与专家系统作了一个简单的比较。第三章对g i s 的现状和发展作了一个简单的阐述和展望。随后给出了g i s的基本功能和特征，并较为详细的介绍了空间数据结构及其表达第四章首先论述了范例推理在解决地学问题上的优势，随后给出了一个基于c b r 的地理信息系统的框架，并在此基础上探讨了地理范例的构建流程。根据地理范例的特殊性提出了套地理范例表达和推理的方案，并重点介绍了基于改进的t e s s e r a l 方法的范例推理，最后将改进的t e s s e r a l 方法应用于地理范例推理。第五章研究如何将1 c b r 应用于g i s ，如何实现一个以m a p l n f o 为平台的基，于范例推理的g i s 系统。文中以“数字合肥”的子系统为例，给出了系统结构设计、功能设计、绿化管理中地理范例的构建以及算法的流程和框架。第六章是全文的总结和研究展望。第二章范例推理的基本原理第二章范例推理的基本原理我们处理的实际问题中大多是不良结构，有时甚至很难用公理化的方法进行表达，这给我们的研究带来了困难。人类在解决问题时，常常回忆过去积累下来的类似情况的处理，通过对过去类似情况处理的适当修改来解决新的问题。受人类认知过程的启示，专家们提出了基于范例推理( c b r ) 的方法。c b r 技术反映了人类认知科学研究的新成果，强调了人类对过去经验和前人智慧的重现，并依据它们指导解决实际工作中遇到的新问题。c b r 特别适用于领域定理难以表示成规则形式，而易于表示成范例形式并且积累了丰富范例的领域【7 1 。2 1 范例推理的提出与发展现状2 1 1 机器学习的发展及存在问题人类自古以来就有着用机器代替人类劳动的幻想，随着科技的进步，机器代替人类进行体力劳动的水平已经相当高，但在代替人类进行脑力劳动即人工智能方面的研究水平却有待提高。随着信息社会和知识经济时代的到来，学习已经成为大家谈论最多的话题之一。学习是人类智能的主要标志和获得知识的基本手段，同时也是机器具有智能的重要标志。作为人工智能的一个重要方面，机器学习受到越来越广泛的关注，成为人工智能的重要课题之一。机器学习的发展大致分为如下几个阶段【3 l ：1热烈时期这一阶段是在2 0 世纪5 0 年代中叶到6 0 年代中叶。在这个时期研究的是所谓的“没有知识”的学习，即“无知”学习，它的主要研究目标是研制各类自组织和自适应系统。这类问题主要采用的研究方法是不断修改系统的控制参数以改进系统的执行能力，不涉及具体问题的知识。这种方法的理论基础是早在2 0 世纪4 0 年代开始的神经网络模型。1 9 4 3 年，m c c u l l o c h 和p i t t s 首次发现了人类神经元的工作方式，并给出了这种方式的数学描述。这项研究在科学史上的意义是非同寻常的，它第一次揭示了人类神经系统的工作方式，并且由于p i t t s 的努力，使得这项研究成果没有仅第二章范例推理的基本原理仅停留在生物学的结果上，他为神经元的工作方式建立了数学模型，正是这个模型深刻的影响了机器学习的研究。在这一阶段出现各种神经计算机的模拟，其中r o s e n b l a t t 的感知机最为著名，它由阈值神经元组成，试图模拟人脑的感知和学习能力。在这一阶段的研究中形成了机器学习的两种重要方法，即判别函数法和进化学习。著名的s a m u e l 下棋程序就是判别函数法的典型代表。该程序具有一定的自学习，自组织，自适应能力，能够根据下棋时的实际情况决定走步策略，并从经验中学习，不断调整棋盘局势评估函数，在不断的对弈中提高自己的水平。但是这种脱离知识的感知型学习系统还是有很大的局限性的，还远远不能满足人类对机器学习系统的要求。2冷静时期这一阶段是在2 0 世纪6 0 年代中叶到2 0 世纪7 0 年代中叶。这一阶段的研究主要目标是模拟人类的概念学习过程。机器内部表示采用逻辑结构或图结构，机器采用符号来表示概念，并提出关于所学概念的各种假设。在此阶段研究者意识到学习是一个复杂而困难的过程，因此人们不能期望学习系统可以从一个空白的状态开始学习到高深而又有价值的概念。在这种观点的支持下，研究人员把注意力方面转移到深入探讨简单的学习问题，另一方面则转移到把大量的领域专家知识加入到学习系统中。比较有代表性的是p hw i n s t o n 的结构系统和h a y e s r o t h 等人的基于逻辑的归纳系统。3复兴时期这一阶段是在2 0 世纪7 0 年代中叶到2 0 世纪8 0 年代中叶。这一阶段的主要研究目标仍然是模拟人类的概念学习过程，但是研究者已经从学习单个概念扩展到学习多个概念，探索不同的学习策略和各种学习方法。机器学习过程一般都是以大规模的知识库作为背景，实现知识强化学习，这一阶段研究者开始将学习系统月各种应用系统结合起来，并获得了极大的成功。在出现了第一个专家学习系统之后，示例归纳学习成为研究的主流，自动知识获取成为学习应用的研究目标。比较有代表性的研究成果有：dj m o s t o w 的指导式学习，l e n a t 的数学概念发现程序a m ，l a n g l e y 的b a c o n 程序及其改进程序。本阶段的研究特点有三点：第二章范例推理的基本原理基于知识的方法，即首先具备大量初始知识；开发出各种各样的学习方法，如观察和发现学习，类比学习和解释学习：结合生成和选择学习任务的能力，应用了启发式信息4蓬勃发展时期这一阶段起始于2 0 世纪8 0 年代至今。在此阶段，一方面神经网络的研究重新兴起，提出了多层网络的学习算法，再加上v l s l 技术，超导技术，生物技术，光学技术等的发展和支持，神经网络又迎来了第二个春天。另一方面实验研究和应用研究受到前所未有的重视。这一阶段的符号学习由“无知”学习转向有专门领域知识的增长型学习，因而出现了具有一定领域知识的分析学习。这一阶段的机器学习研究有以下显著特点：机器学习已经成为新的边缘学科；开发出各种各样的学习方法，相当一部分已经成为商品；结合各种学习方法，将多种学习方法综合集成的系统研究正在兴起；机器学习和人工智能各种基础问题的统一性观点正在形成。总之，机器学习发展至今，已经取得许多实用性的成就。但是从研究人类学习方法出发的机器学习在定程度上是有缺陷的。因为关于人类学习机理的很多问题到现在还没有科学的解释，因此也就无法在计算机上进行准确的模拟。还有随着社会发展，信息量越来越大，知识获取效率低的问题也就日渐凸现。于是c b r 方法出现了。它具有简化知识获取、提供问题的求解效率、改善求解质量、进行知识积累等6 大优点。由于不受知识获取的局限，又可以通过学习不断增强系统功能，使得c b r 这种方法越来越流行，应用越来越广泛。2 1 2 范例推理方法简述范例推理来源于人类的认知心理活动，它属于类比推理方法。其基本思想是：当遇到一个新问题的时候，首先联想以往处理类似问题的经验，在范例库中查找出与之最接近的旧范例，再根据新情况的差异相对应的做出调整，从而得到解决新问题的办法并形成新的范例【3 】。一个完整的范例推理包括几个循环过程，a m o d t和p l a z a 将范例推理归结为4 r ：r e t r i e v e 、r e u s e 、r e v i s e 和r e t a i n n 其一般过程如下图2 1 所示：第二章范例推理的基本原理新问题图2 1 范例推理的工作过程l检索：根据待解决问题的有关信息，从范例库中找到与之最接近的范例集；2重用：从检索到的一组范例中获得求解方法，如果完全符合条件则直接应用，否则修正后再使用；3修正：从相似范例中修正求解方案以适合新问题；4保存：将新的范例以及解释根据一定的原则存入到范例库中。基于范例的推理效果在一定程度上依赖于范例库的结构以及范例的知识表示方式。c b r 系统所依赖的最重要的知识都储存在范例库中，范例库中包括了应用领域中的历史经验，是整个c b r 系统知识库中最重要的一个库。范例不仅包括对问题整体情况的描述，还包括对问题的解或解的方法的描述，有时候还包括解的效果的描述，所以范例可以表示成： 或范例的表示有多种方法，目前常用的有：s c r i p t 方法、面向对象方法、语义神经网络、框架结构等等。范例表示的设计可以分为两个阶段：1 概念设计阶段，即方案的生成：2 方案的落实阶段，即根据设计方案进行结果的生成操作，形成最后的设计结果。除了范例的表示，如何得到充足、有效的范例也是一个c b r 系统成败的关键。c b r 系统是通过检查范例库中以往的类似范例从而获得当前问题的解决方案，它克服了传统知识处理系统对边界外知识处理低效、匹配冲突的问题。但是随着c b r 系统的自学习，知识库越来越大，如何从库中尽快找到一组最接近的解就成了问题。这里要求相似性函数不能太复杂，否则检索速度太慢，但也不能第二章范例推理的基本原理太简单，否则得到的相似范例集会非常大。因此选取一个合适的相似性度量函数就显得非常重要。目前较常用的有：t v e r s k y 对比匹配函数、距离度量法、多参数相似性计算法等，这些函数将在23 节详细介绍，在此不再赘述。还有一个关键技术就是c b r 的修正技术，它同时也是c b r 技术的难点问题。因为对于新问题，系统中没有完全相同的范例，只能找到一些相似的旧范例，然后利用修正技术对其进行重用。这里的修正我们可以简单的理解为把解决方案的部分用其他的内容替换或者整个的修改方案。对于同一个旧范例，我们或者插入一些新内容，或者删除一些内容，或者替换一部分内容，到底用哪一种方法或是哪些方法的组合是非常重要的，它直接关系到解的质量的好坏。关于修正技术也将在2 3 种详细论述。最后一点是范例库的维护。c b r 的系统是一个不断增大的系统，随着它处理的问题越来越多，新的范例也就越来越多的被储存在范例库中。范例库增大带来的好处是很容易找到相同范例或相似范例，减少修正的次数和时间，同时带来的弊端是范例库的冗余度增加，有的是重复范例，有的是噪声范例，这样在检索的时候代价就越来越大，所以合理适时的清理范例库是非常有必要的。目前常用的方法有：随机删除法、使用值度量法、i b 3 算法等。2 1 3 范例推理的历史与现状r o g e rs c h a n k 在】9 8 2 年出版的( d y n a m i cm e m o r y ：at h e o r yo f r e m i n d i n ga n dl e a r n i n gi nc o m p u t e ra n dp e o p l e ) 著作中，最早描述了c b r 的研究工作，给出了计算机上建造这种推理系统的方法。他的早期思想被耶鲁大学的学生推广，1 9 8 3 年著名的左治亚工学院的j a n e tk o l o d n e r 的c t r u s 系统在计算机上首次实现了r o g e rs c h a n k 著作中的许多原理【川i i 。尔后，耶鲁大学、左治亚工学院和马萨诸塞大学的研究生又建立了一些系统，这些系统在法律、烹饪、医药、故障诊断等领域中证明了c b r 。目前美国是开展c b r 研究与开发最普遍的国家，欧洲、日本等工业化国家对c b r 的有关问题及相应的系统正在进行大量的研究与开发，建立上百个用c b r 推理的知识系统。我国的c b r 的研究与系统开发起步较晚，但在上个世纪9 0 年代初也见到了这方面的研究与应用。例如北方交大的田盛丰、张清等人将c b r 用于岩石工程中的支护辅助设计中，效果显著，复旦大学的蒋栎等人将c b r 用于西文图书分第二章范例推理的基本原理类中，以相当高的正确率获得了用户欢迎。这些都充分说明了c b r 作为人工智能的一个分支有较大的应用价值i “】。2 2 范例推理系统结构及优缺点比较2 2 1 范例推理的系统结构c b r 是一种类比推理方法，它提供了一种近似人类思维模型的建造专家系统的新的方法学，这与人对自然问题的求解相一致。它克服了传统的基于规则推理( r u l e b a s e dr e a s o n i n g r b r ) 系统的知识难于获取和推理的脆弱性。整个范例推理系统有两个大部分组成，一是范例库，二是推理机。范例就是c b r 中的知识表达的基本单元，是问题状态到相应解空间的一个映射，这样的一组范例集合就是c b r 系统的。像上节中提到的，c b r 系统解决问题的过程包括了范例的检索( r e t r i e v e ) 、范例的复用( r e u s e ) 、范例的修正( r e v i s e ) 、范例的保存( r e t a i n ) 。多数情况下我们很难得到一个完全相同情况的范例，当一对一的匹配失败之后，通过对新范例进行多方位适当的分解，对纵向和横向类似范例的修正和集成，产生一个全新的解，并将其纳入到范例库中，这就使得c b r 有很强的自适应能力。一般情况下c b r 系统结构与求解的方法及过程如图2 2 所示。第二章范例推理的基本原理图2 - 2c b r 系统的结构及工作流程不惹图由上图我们可以看到范例库是整个系统的核心部分，从初期的检索，中期的范例修正，到最后一个新范例入库都离不开它。因此围绕着范例库出现了许多研究热点，例如范例库的维护、范例库的检索等等。本文将重点放在了一种新的范例地理范例的范例表示和范例推理过程上。2 2 2 范例推理的优缺点简述c b r 具有如下优点：信息的完全表达、增量式学习、形象思维的准确模拟，知识获取较为容易、求解率高等。与传统的专家系统相比，它的最大优点在于动态知识库，即通过增量式学习不断增加知识的范例库。在c b r 系统中，许多解第二章范例推理的基本原理态知识库，即通过增量式学习不断增加知识的范例库。在c b r 系统中，许多解决问题的方案和经验被收集起来，这些方案和经验就是c b r 系统的知识库，一些新问题就依赖于这个知识库中的旧方案和旧经验调整而获得。但是c b r 也有其缺点，如求解过程中相似范例的修正非常困难，整个系统对噪声非常敏感，而且随着系统的增大，维护代价增高，会影响范例检索的速度。为了克服其中的一些问题，我们想到了将范例推理和其他人工智能方法进行集成。例如，利用神经网络擅长处理噪声数据来降低c b r 对噪声的敏感度。2 2 3 范例推理方法与其它方法的集成范例推理有上面所说的一些缺点，这些缺点是c b r 系统的结构和工作原理所导致的固然缺陷，我们如果想克服这些问题就必须从系统结构入手，将c b r和其他方法进行集成。范例推理系统和其他方法的集成的研究已经成为范例推理研究的一个庞大分支。常见的集成有：归纳技术与范例推理的集成一般的领域知识可以从规则归纳( r u l ei n d u c t i o n ，r i ) 的一组训练数据中学习到。大部分的r i 系统通过规则的前提空间和决策树来进行试探搜索，采用典型的统计学估计能力去选择只是结构中的属性和属性值。在知识体系机构中，先后剪枝被用来处理不完善的数据或噪声数据。c b r 和r i 的互补性能充分的结合起来之后可以解决一些单个技术不能很好解决的东西。专家系统与范例推理的集成专家系统虽然在研制和应用上已经取得了重大的进展，但由于其立足于符号信息处理机制的固有缺陷而使得传统的e s 存在许多问题，如推理技术单调、学习能力差、知识贫乏等等。而将范例推理结合进来之后情况就完全不同了，由于一，范例推理是模拟人的心理感知行为，其获取的知识是丰富的，学习能力也比专家系统要强，它利用旧经验解决新问题，使得专家系统更接近人类专家思维模式，除了判断推理之外还兼顾了专家凭直觉、想象和经验求解的一面。范例推理系统和g i s 的结合这是本文将要重点讨论的问题，g 1 s 近些年来得到突飞猛进的发展，但是它【 l 存在一些问题，例如在决策支持上效果不是很理想，对于模糊数据以及界外数据，常常不能很好的处理。但是c b r 可以解决这个问题，它可以通过对旧经验第二章范例推理的基本原理本身具有自学习能力，通过经验可以解决相当一部分的界外数据的问题。2 3 范例推理与专家系统的比较范例推理与其它人工智能方法相比有许多独到之处，下面就重点介绍范例推理与专家系统的区别。范例推理和专家系统最主要的区别就是知识存储和使用方法。专家系统依靠规则来解决问题，从经验中抽取规则，并应用于下一次的问题求解，而范例推理却是依靠范例，以抽取和修正技术取代专家系统中知识产生和检验机制。范例推理可以隐含的表达一些信息，这是专家系统所不具备的。范例推理具有学习能力，它的学习由两种情况：成功学习和失败学习。这些成功的经验和失败的教训都被存贮到范例中。从根本上说，c b r 系统可以自动的简练它的知识【”i 。概括地说：c b r 提供了一组范例从而允许用户挑选相同的范例或最适合的范例修改；而专家系统则是通过规则直接给出问题的答案。另外，随着使用次数的增多，范例系统会自我扩充和自我精炼，解决问题的精度会越来越高( 当然效率会有所下降，维护代价会有所上升) ，而专家系统的性能则不会随着次数的增多而改变。2 4 范例推理系统的关键技术研究2 4 1 相似性计算函数前面我们提到在一个c b r 系统中检索是整个范例推理的第一步也是极其重要的一步，因为检索的成功与否直接关系到能否得到一组最接近问题描述的范例，如果能得到最接近的这样一组范例将会为接下来的修复创造很大的便利。c b r 检索要达到如下两个目标：1 检索出来的范例尽可能的少：2 检索出来的范例尽可能得与当前范例相似【”i 。如何从范例库中检索和选择最为相似的范例决定了范例推理系统的学习与推理性能。范例间的相似性度量是检索的关键。在范例间相似度的评估中，通常是建立个相似性度量计算函数对当前范例与旧范例进行比较，常用的相似性度量函数有以下几类【3 】。1 1t v e r s k y 对比匹配函数第二章范例推理的基本原理，( a ”ia 。)。时2 讨百万f 牙丁石( 2 1 )这是基于几率模型的度量算法。公式( 2 - 1 ) 是其相似性度量的定义。其中a ”a 是表示范例r l ，k 的属性全集，l 表示范例1 1 和k 之间相似度。这种相似性度量法适用的属性值是二进制的应用领域“】。2 1 改进的t v e r s k y 对比匹配函数w ( n ，i ) w ( k ，f ) ( 2 2 )上面的公式( 2 2 ) 是改进的t v e r s k y 匹配法的相似度定义。其中w ( n ，i ) ，w ( k ，i )分别表示第i 属性在范例n k 中的权值；表示范例n 和k 的第i 个属性的相似度；m 表示范例n 和k 的所有属性的个数：& 为其相似度。改进的t v e r s k y 匹配算法考虑了属性集中的各个属性对于两个范例具有不同的权值，这样对于属性集相同的范例可以用这种方法求相似度。对于属性集不同的两个饭里可以设置属性集为两范例的并集，范例k 有而范例n 没有的w ( n ，i ) 设置为0 ，反之亦然。这样就可以得到范例n 和范例k 的相似度。3 ) 距离度量法或最近相邻算法( kn e a r e s tn e i g h b o r k - n n )距离度量或k - n n 方法是通过计算两个对象在特征空间中的距离来获得两范例间的相似性。在c b r 系统中，大多数的范例间所都是用最邻近算法。假设范例x = x 。，x ：，x 。) ，置( 1 蔓i n ) 是它的特征值，w i 是其权重。x是n 维特征空间d = ( d 。h + 见) 上的一点，置d i 。对于d 上的x ，y , n x ，y 在d 上的距离为d i s t ( x ，y ) = ( ，w i * d ( x i ，f ) ) “7( 2 3 )其中第二章范例推理的基本原理如果d 是连续的如果d 是离散的且置= y( 2 - 4 )如果口是离散的t 且x ，】j ：在式( 2 3 ) 中r = 2 时，则d i s t ( x ，y ) 为欧拉距离。除了常用的欧拉距离，曼哈顿距离，无限距离外，还有其他的距离度量函数，如h a u s d o r f f , m i n k o w s k y 以及h a m m i n g 等等。s i m ( x ，y ) = 卜d i s t ( x ，y ) = 1 一，彬d 2 ( 一，z )( 2 5 )公式( 2 5 ) 使用的是欧拉距离的相似度定义。其中d ( 置，i ) 计算公式就是上面的公式( 2 4 ) 。下面的公式( 2 6 ) 使用的是h a m m i n g 距离度量法。s i m ( x ，y ) = 1 一d i s t ( x ，j ，) = 1 一，彬d ( 置，)( 2 6 )4 ) 多参数的相似性在两个范例p , p 之间的相似性计算，考虑了很多个因素，公式如下：s i m ( p ，p ) =d * a t t r s i m ( p ，p 1 ) + + a d d r s i m ( p , p ) + y * c o n t s i m ( p , p )旺七8 七7( 2 7 )其中，c o n t s i m , a d d r s i m , a t t r s i m 分别计算两个范例之问的上下文，地址，属性相似性的计算函数：而d ，y