（计算机应用技术专业论文）基于web的智能查询系统的研究.pdf

基于w e b 的智能查询系统的研兜 摘要 本文先分析了传统c b r 系统存在的某些缺陷，提出了新的c b r 系统实现方案和新 的c b r 算法。那就是把实例库分成使用者实例库和应用实例库，这 样，每次检索范例时，根据使用者的不同而检索相应的范例库，从而提高检 索速度。 c b r 系统中最基本的问题和很难的问题是关于两个实例的相似性的定义。即相似 性的度量。传统的c b r 系统的相似算法主要采用最近相邻检索法、归纳索引法和知 识导引法这3 种实例检索策略。这三种实例检索策略比较适合定性属性的实例检索。 本文引入语义距离来刻画相似实例中两个对应属性之间的相似程度，采用相似优先比 来描述新问题与各个旧实例之间的相似度的顺序。该相似算法采用数学模型来计算。 可得到精确的相似度排列顺序。可适用于_ 定量属性、定性属性和混合属性的实例的相 似度计算。 最后，为达到软件复用的目的，本人借助了本实验已开发项目的相关成果，以构 件形式实现了一个真实的应用系统。 关键字：c b r 系统。实例库，实例检索，相似算法 昆明理工大学额士学位毕业论文 基于w e b 的智能查询系统的研究 a b s t r a c t t h ea r t i c l ea n a l y s e st h ef l a w si nt h et r a n d i t i o n a lc b rs y s t e mf i r s t l y ，a n d b r i n g sf o r w a r dan e wa p p r o a c ha n da r i t h m e t i co fc b rs y s t e m t h a ti sd i v i d i n g t h ec a s e b a s ei n t ou r s e r b a s ea n da p p l i c a t i o n b a s e e v e r yt i m ew h e ns e a r c ht h e c a s e b a s e ，w ec a ns e a r c ht h ec o r r e s p o n d i n gc a s e b a s ea c c o r d i n g t h eu s e r s ，w h i c h c a nf a s t e rs p e e do fs e a r c h i n g t h eb a s i ca n dd i f f i c u l tp r o b l e mi st h ed e f i n e m e n to rm e a s u r e m e n to ft h e s i m i l i t u d eb e t w e e nt w oc a s e s t h et r a n d i t i o n a lc b rs y s t e ma l w a y sa d o p t st h e m e t h o d so fn e a r e s tl e a r n i n g 、i n d u c t i o ni n d e x i n ga n dk n o w l e d g ei n d u c t i n g t h s e s t h r e em e t h o d sa d a p tt ot h ec a s e s e a r c h i n go fq u a l i t a t i v ec a s e s t h i sa r t i c l e i n t r o d u c e ss e n l s n t i cd i s t a n c et od e p i c tt h es i m i l i t u d eo ft h ec o r r e s p o n d i n g a t t r i b u t eb e t w e e nt w os i m i l a rc a s e s a n da d o p tt h ed a r kp r i o r i t y r a t i ot og e t t h es e q u e n c eo ft h es i m i l i t u d eb e t w e e nt h en e wp r o b l e ma n dt h eo l dc a s e s t h i s a r i t h m e t i co fs i m i l i r u d ea d o p t sm a t h e m a t i cm o d e l ，w h i c hc a nw o r ko u tt h ee x t r a s e q u e n c eo fs i m i l i t u d e f i n a l l y ，i no r d e rt or e a l i z et h er e u s eo fs o f t w a r e 。im a k eu s eo fs o m e r e s u l t so fs o m ep r o j e c t sd e v e l o p e di no u r l a b o r a t o r yt od e v e l o p ar e a la p p l i c a t i o ns y s t e m k e y w o r d s ：c b rs y s t e m c a s e b a s e ，c a s e s e a r c h i n g 。a r i t h m e t i co fs i m i l i t u d e 昆明理工大学硕士学位毕业论文 2 昆明理工大学学位论文原创性声明 本人郑重声明：所星交的学位论文，是本人在导师的据导下( 或 我个人) 进行研究工作所取得的成果。除文中已经、矬明引用的内 容外，本论文不含任何其他个人或集体已经发表或撰写过的研究成 果。对本文的磷究徽爨重要羹黻麓个久鞫煞镩，均琵在论文中终了明 确的说明并表示了谢意。本声明的法律结果由本人承担。 学位论文作者签名：名菩尼、 ? 嚣期：p 哆年2 - 胄吖鑫 基于w e b 的智能壹询系统的研究 1 1 课题背景 第一章绪论 对智能查询系统的研究，国外比国内要成熟。如：b r u c em c l a r e n 开发的s i r o c c o 系统；e l a u s - d i e t e ra l t h o f f 等人开发的c b r p e b 系统：还有k a t h r y ne s a n d e r s 开 发的c h i r o n 系统。这些系统在法律、医药、农业的方面都有了很好的运用，总的趋 势是正在快速地向各个行业渗透。随着网络技术的高速发展，智能查询系统也朝随络 和电子商务方面发展着。在欧美，出现很多网上商店智能向导，支持自由文本描述的 信息查询系统。英国政府投资的i n f o s h o p 系统，它是一个当地政府法规智能查询系 统，是用来帮助处在第一线的政府职员们处理公众关于当地法规的一些询问。它能自 动处理一些反复放公众提出的问题。同时对于那些不能处理的特殊问题，它会把它们 提交给专家组，专家组进行处理后再回复公众，同时，这个案例被存在数据库中，当 下次被问到相同的问题时，就可以由系统直接得到回复，而不需要荐提交到专家组。 这个系统大大地提高了政府部门的办事效率，它是英国政府实现公众服务自动化目标 的一个组成部分。 c b r ，基于范例的推理，它相对于其它许多的推理方法( 如：基于规则的推理) 来 说，有很大的优势。基于c b r 的各种应用系统在美国和欧洲已发展到相当数量，在 网络和电子商务方面的应用也在不断展开，例如：网上商店智能向导，支持自由文本 描述的信息查询系统，网上c b r 开发工具等。 相对于国外，国内对基于c b r 的智能查询系统的研究还比较少。集中于少数大 学和研究所，高质量的论文和研究团体都很少。这和国外丈量的学术团体和论文形成 了鲜明对比，说明我们在这方面还存在很大差距。应用也处于初级阶段，只能实现基 本的c b r 架构，对于更加深入的c b r 理论的研究和应用还很少，而国外的更优化的 应用却显然要多得多。 还有，“软件危机”自上世纪六、七十年代产生以来，至今仍没有得到很好的解 决，软件企业面临越来越激烈的市场竞争。大多数情况下，成功的开发和服务不仅要 求质量“好”，而且要求响应“快”，花钱“省”。达到这个目标的途径有两条：一是 提高软件企业的生产效率例如，采用先进的开发工具，培养熟练的技术人员等；二 昆明理工大学硕士研究生毕业论文 基于w e b 的智能鸯询系统的研究 是软件复用。软件复用的具体途径就是开发出可复用的构件【”。 所以，迫切需要这样一个基于w e b 的智能查询系统：它接受到业务员输 入的客户的具体要求后，它能自动地查出一些与之最为匹配的实例给业务员，这样。 业务员可以根据实例进行比较，快速、准确地作出决策i 还有，实践证明，软件构件技术能够提高软件产品的的质量、加快软件开发的速 度，降低软件的开发和维护技术，是软件复用的关键技术。因此，在最后实现了一个 具体的系统。开发出可复用构件，从而实现软件复用。本课题正是就这种系统的研究 而提出的。 1 2c b r 的概况 1 2 1 g b r 总体概述 c b r ( c a s e - b a s e dr e a s o n i n g ) 即：基于实例的推理，它是人工智能研 究中的一个重要的推理方法，它最早源于1 9 8 2 年r o g e rs c h a n k 提出的关于动态记忆 及早期实例处理在问题求解和学习中的中心作用理论。人们的认识心理活动一般是这 样的：当遇到一个新的问题时，往往参考以前处理的类似问题的经验，将新的问题逐 步往旧问题上匹配，找到高度相似的旧问题，调整它的解，推导出新问题的解，同时 人的大脑也就学习并记住了这个新问题及其解为以后解决类似的问题作好了准备。 c b r 就是似人的这种动态记忆理论作为它的智能检索机制，用于专门问题求解嘲。 k o l o d n e r 在“c a s e - b a s e d r e a s o n i n g ”一书中给出了实例的一个定义：“实例是一段带 有上下文信息的知识。该知识表达了推理机在达到其目标的过程中能起关键作用的经 验”刚。具体说来，一个实例应有如下几个特征： 1 ) 实例表示了与某个上下文有关的具体知识，这种知识具有可操作性。 2 ) 实例可以是各式各样的，可有不同的形状和粒度可以概禽或大或小的时间片， 可以带有问题的解答或动作执行后的效应。 3 ) 实例记录了有用的经验，这种经验能帮助推理机在未来更容易地达到目标，或提 醒推理机失败发生的可能性有多大，等等。 基于实例的推理( c a s e - b a s o d r e a s o n i n g ，c b r ) 是人工智能发展较为成 熟的一个分支。它是一种基于过去的实际经验或经历的推理。传统的推理观点把推理 理解为通过前因结果链( 如规则链) 导出结论的一个过程。许多专家系统使用的就是 昆明理工大学硕士研究生毕业论文 基于w e b 的智能查询系统的谛f 究 这种规则链的推理方法。基于实例推理则是另一种截然不同的观点。它使用的主要知 识不是规则，而是实例，这些实例记录了过去发生的种种相关情节。对于基于实例的 推理来讲，求解一个问题的结论不是通过链式推理产生的，而是从记忆里或实例库中 找到与当前问题最相关的实例，然后对该实例作必要的改动以适合当前的问题。 基于实例推理作为一种方法论是合理的。因为客观世界有两个特点：规攘性和重 现性。世界从总体上看存在一定的规整性，相似条件下发生的动作会产生相似的结果。 “历史是惊人的相似”，过去的经历很有可能预示未来。 心理学研究表明，人类决策喜欢而且也善于利用实例作决定，但是人的 记忆的限制又使得人常常难以正确回忆出适当的实例，特别是当实例数目很多时。而 和人相比，计算机则正是基于实例推理的研究起源于从认知科学的角度对人类的推理 和学习机制的探索。从小孩的简单活动到专家的慎重决筇，人类借助于有意识地或无 意识地回忆完成各种事务。人类经常是按经验行事，而人又是某种意义上的一个智能 系统，因此自然可以把这种基于经验的推理方法用于人工智能的研究和应用上。总体 上说，基于实例推理在如下方面对人工智能作出了贡献t 1 ) 知识获取；这是基于知识的系统的瓶颈问题。开发基于规则的知识系统时，获 取规则或模型时最烦琐的一件事务。需要领域专家和知识工程师的密切合作， 有的领域甚至很难找到合适的规则。 2 ) 知识维护：随着系统的运行，由于初始的知识不完整，知识系统常常需要更新， 新的知识可能会与原有知识产生冲突寻致非常大的系统变动，基于实例的推 理则不存在这些问题 3 ) 改进问题求解效率：基于实例推理通过复用过去的解答，无需像常规推理那样 从头做起特别是，由于记录了过去求解时失败或成功的信息，使得求解新问 题时可以避开错误的途径。 4 ) 改进问题求解质量：过去求解失败的经历可以指导当前求解，避开失败。 5 ) 提高用户接受度：只有当用户清楚知道系统得出得结论是合理地推出来的，他 才相信该结论。而基于实例的推理的根据是历史事实，事实胜于雄辩，因此对 用户有说服力。 实例组织时由两个部分组成，一是实例的内容，实例应该包括哪些有关的信息才 能对问题的解决有用；二是实例的索引。它和实例的组织结构以及检索有关，反映了 不同实例的区另r j 4 - 6 】。 昆明理工大学硕士研究生毕业论文 基于w e b 的智船查询系统的研究 1 2 2 实例的复用 把检索到的旧实例的解答复用到新问题或新实例之中，需要通过比较所 给问题和实例库中的实例，得到新旧实例之间的不同之处，然后回答哪些解答部分可 以复用到新问题之中，对于简单的分类问题，仅需要把旧实例的分类结果直接用到新 实例，它无须考虑新旧实例之间的差别u - s l 。而对于问题求解之类的问题，则需要对 领域知识的深入理解，根据实例之间的不同对问题进行调整，可以是对整个解的某项 作一姥调整，也可以对整个解进行微调。 从复用的信息内容来看，主要有两类：结果复用和方法复用。对于结果 复用这种类型。当旧实例的解答结果需要调整时，它依据一些转换操作知识。把旧实 例中的种种可能解转换为新实例中的相应的解。方法复用则关, 0 , f f l 实例中问题的求解 方法，而不是其解答结果。用哪种方法依据具体情况而定。 当复用阶段产生的求解结果不好时，需要对其进行修正【9 】。修正的第一步是对复用结 果进行评估，如果成功则不必修正，否则需要对错误和不足进行修正。进行结果评估， 可以依据它在实际环境中运行后的反馈，也可以通过向专家询问完成。等待反馈有时 可能需要花一段时间，如等待病人治疗的效果如何。但如是工程中的在线应用，则可 以马上返回结果。 过去的情景不可能与新情景完全一样，因此对于问题求解型的c b r 系统， 必须修正过去的问题解答以适应新的情景修正过程的输入是当前的问题描述和不太 正确的建议解，输出是更适合当前情景的较好的解答。 简单的修正只是需要对过去解中的某些组成部分进行简单的替换，复杂 地修正甚至需要修改过去的整体结构。修篪可以在新解的形成过程中完成，也可能是 当新解在执行过程中出现了问题再来做0 0 - h 】。修正一般有这样几种形式；在旧解中增 加新的内容。或者从旧解中删去某些内容，或者对旧解中的某些内容进行替换，或对 旧解中的某些部分进行重新变换。 修正有四类方法：替换法、转换法、特定目标驱动法，以及派生重演法。 1 替换法 替换法就是把旧解中的相关值作相应的替换而形成的新解。此类方法包括如下6 种： ( 1 ) 重新例化：这是一种很简单的替换操作，仅仅是用新的个体替换旧的 个体。就如川菜设计系统c h e f 。在根据牛排炒甘蓝菜来设计道鸡 昆明理t 大学硕士研究生毕业论文 4 4 基于w e b 的智能壹询系统的研究 肉炒雪豆菜时，它就是把该菜谱中的所有牛排替换成鸡肉，把甘蓝替 换成雪豆。 ( 2 ) 参数调整t 这是一种处理数值参数的启发式方法。它和具体的输入输 出参数问的关系模型有关 ( 3 ) 查询：用带条件的查询在实倒库或辅助知识结构中获取要替换的内容。 ( 4 ) 局部搜索：使用辅助的知识结构来获取替换值。例如，设计点心时缺 少橘子，则可以使用此法在一个水果语义网知识结构中搜索一个与橘 子相近的水果和苹果来代替。 ( 5 ) 特定搜索t 同时在实例库和辅助知识结构中进行查询，但是在实例库 中查询时使用辅助知识来启发式指导如何搜索。 ( 6 ) 基于实例的替换；使用其它实例来建议一个替换。 2 转换法 转换法包括：常识转换法和模型制导修补法。前者使用明白易懂的常识 性启发式从旧解中替换、删除或增加某些组成部分。典型的常理转换法是：删去次簧 组成部分“。后者通过因果模型来指导如何转换。故障诊断中经常使用这种方法。 3 特定目标驱动法 这种方法主要用于完成领域相关以及要做结构修改的修正该法使用的各种启发 式需要根据它们可用的情景进行索引。特定目标驱动的修正启发式知识一般通过评价 近似解作用。并通过使用基于规则的产生式系统来控制。 4 派生重演 上述方法所做的修正是在旧解的解答上完成的。璧演方法则是使用过去的推导出 旧解的方法来推导出新解1 1 2 1 。这种方法关心的是解是如何求出来的同前面的基子 实例替换相比，派生重演使用的则是一种基于实例的修芷手段。 1 2 3 实例的保存 实例插入实例库的过程类似于检索过程。“r e m e m b e r ”有两种含义；“记住”和 “回忆”。“回忆”也就是检索，“记住”就是存储或插入。插入要调用索引选择过程， 以决定实例被索引的方式。而插入算法使用这些索引来把实例插入到实例库中适当的 地方。一般来说，插入工作所做的搜索工作与检索相同。插入算法搜索的目的是找到 一个可以插入实例的地方，而检索的目的是为了找至d 相似的实例。当检索算法找到了 昆明理工大学颓士研兜生毕业论文 基于w e b 的智能查询系统的研究 相似的实例后就进行实例排序，而插入算法则是插入源实例并根据需要重新组织实例 库的结构。 新问题得到了解决，则形成了一个可能用于将来情形与之相似的问题。这时，有 必要把它加入到实例库中去。这是学习也是知识获取。此过程涉及选取哪些信息需要 保留，以及如何把新实例有机地集成到实例库中，并且会涉及实例库的组织和管理方 面的知识。 在决定选取实例的哪些信息需要保留时，一般要考虑以下几点：和问题有关的特征描 述；问题求解结果：以及解答为什么成功的原因及解释。 把新实例加入到实例库中时，需要对它建立有效的索引，这样以后才能对它做出 有效的回忆。索引应该做到t 与该实例有关时能快速回忆到，与它无关时，不应做出 回忆。为此，可能对实例库进行有效的组织和管理。 上述的“检索”、“重用”、“修正”、和“保存”四个过程是基于实例推理的关键 步骤。由于它们对应的英文单诃都是以r 开头的，因此，c b r 的推理过程也称为4 r 过程【4 j 。 c b r 系统有两种类型：问题求解型和解释型，上述修正是针对问题求解型的c b r 系统而言，解释型c b r 系统的任务是根据以往的实例来决定这样的问题：证实某个 论断的正确性，预测结果，或者判断某个概念是否符合某种分类。人类活动常常也是 这种方式。例如。大学的新生录取蚕员会经常是通过和条件相似的已经被录取的学生 进行对照比较来估计某个学生的前途如何。医生通常也是靠对当前病人与以往的症状 类似的病人进行对照比较来断定病人的情况。完成上述这些任务。般没有什么固定 的规则可用；c b r 则能够获得较为理想的结果。除了寻找新旧实例问的相似之处外， 辩护过程还要对它们之间的不同点进行仔细考察以确定过去的解释是否适用于当前 的情况。例如，某个大学申请者可能与一个或多个并不出色的学生在某些方面相似， 但这个学生却有那些不优秀学生所没有的特别的经验、成熟度和科研能力，这就可能 意昧着我们不应对相似方面给予过多的重视。 1 2 4 实例的检索 实例的检索是从实例库中找到一个或多个与当前问题最相似的实例； c b r 系统中的知识库不是以前专家系统中的规则库，它悬由领域专家以前解决过的 一些问题组成。实例库中的每一个实例包括以前问题的一般描述【1 4 】。一个新实例并 昆明理工大学硕士研究生毕业论文6 基于w e b 的智能查询系统的研究 入实例并入实例库时，同时也建立了关于这个实例的主要特征索引。当接受了一个求 解新问题的要求后，c b r 利用相似度知识和索引从实例库中找到与当前问题相关的 最佳实例，由于它所回忆的内容，即所得到的实例质量和数量直接影响至u i - j 题的解决 效果，所以此项工作十分重要。它通过三个子过程：特征辩识、初步匹配和最佳选定 来实现。 特征辩识是指对问题进行分析、提取有关特征。特征提取的方式有： ( 1 ) 从问题的描述中直接获取问题的特征如自然语言对问题进行描述并输入系 统，系统可以对句子进行关键词提取，这些关键词就是问题的某些特征； ( 2 ) 对问题经过分析理解后导出的特征。如图象分析理解中涉及的特征提取： ( 3 ) 根据上下文或知识模型的需要从用户那里通过交互方式获取的特征。在后面 的系统实例，我们将用这种方式，让用户填写和选取所需的特征值。 初步匹配是从实例库中找到一组与当前问题相关的候选实例。这是通过 使用上序特征作为实例库的索引来完成索引的。由于一般不存在完全的精确匹配，所 以对实例之间的特征关系进行相似度估计。实例之间的特征关系相似度的估计是 c b r 最难也是最重要的部分。相似度的估算方法最常见的有最近邻近法和归纳法。 最佳选定是指从初步匹配过程中获得的一组候选实例中选取一个或几 个与当前问题最相关的实例。 检索过程由三个核心部分组成：检索算法、匹配函数和情景分析。下面 着重讨论检索算法。c b r 中已形成了一系列的实例组织和检索策略算法1 1 5 1 。有串行 的，有并行的；有平面型的，有层次型的；有在粗粒度缴上建立索引以区别不同实例 的，有在细粒度级上建立索引的用的最多的是倒排索引之类的方法，它既可以采用 串行也可以采用并行策略来检索。最常用的检索方法有如下兰种： ( 1 ) 邻近法：邻近法采用特征间的加权匹配来估计实例之间的相似度【1 6 】。 因此此法的关键问题是如何确定特征的权重。邻近法的缺点是，检 索的时间复杂度会随着实例库中实例的个数增多而线性增长。因此， 只有当实例库很小时，此算法才比较适用。 ( 2 ) 归纳法：采用归纳方法可以确定哪个特征在区分实例时最好，此方 算法能生成一棵决策树，它可以有效地组织实例。理想的决策树分 为三类：叶子结点数最少( 影响树的规模) ；叶子结点深度最小( 平 均深度影响决策速度) ；叶子结点数最少且结点深度也最小。但是， 昆明理工大学硕士研究生毕业论文7 基于w e b 的智能查询系统的研究 要得出这种决策树难度是十分大的。 ( 3 ) 模板检索：与s q l 查询很类似，模板检索能返回在一定参数值范围 内的所有实例。 昆明理工大学硕士研究生毕业论文 基予w e b 的智能螽询系统的研究 第二章传统c b r 系统的缺陷及新系统的设计 2 1 传统c b r 系统的缺陷分析 c b r 的工作流耩燕这样翡：蓄先逶对薪阚逶豹攒述，薪翡实镄霹潋定义麓震镶捺 述符集合，然后从实例库中焘询出与新实例的决策问题很捆似的实例集合，再从这魑 检索出来的实例解决方案中推导如新实例的解决方案，荐檄据新f 西实例之闽的差异调 整这一解决方法，澎成适用予叛l 霹题的织决方法。接着测试赫解对勰诀断l 畦题的裔效 性，如果新解可以接受，那么c b r 系统完成了推理。最后将新问题及其对成的新解添 翔刭实铡疼孛戈戳震熬决策皴准蠡。原理强翅强1 黢忝： c b r 其礴以下傀点； 1 ) 能以获敬新实例的方法矮现自学习。 2 ) 艇爱陕搜麓者魏经验辍裘，楚一凄c _ , b r 蓉绞在誉润豹使建嚣境下经过一段 时间，将会成为不同的艨统。 3 ) 霹提供祷定貔宴铡来秀耨 薅惩褥爨解决努案，遮魄缝糁鹣娩羹| l 滋耱更清辩、 更有说服力f i 酬s l 。 僵是，这种传统的e 嚣r 系统不燕完美的俩魏；它只能简限予菜个专门的领域， 蕊不能实现不同领域的经验重用：还有，出于这种传统的c b r 系统把所有的使用者信 息与实例信息统一于一个实例库巾，这样，使实例库过分庞大和臃肿，导致实例库滩 ；i 繁理，瞧澎璃鸯谗豹撼发每速度。 2 。2 凝c b r 系统的设计 因此，本人提出了一瓣薪的c b r 系统方案。这种方寨撼实捌麾分为使用学实例痒 和应用实例库两个部分。其中，使用者实例岸部分主要实现对应用襄例库的搜索策略、 甄错琏工大学硬士研巍擞毕监论文 基于w e b 的智能查询系统的研究 改编镱略和存储策略的重用和自学习。搜索策略是指一些指导搜索经验或规则，包括 搜索实例的特征及其权值分配，搜索的范围( 搜索域) 和搜索的收敛半径等。改编策 略是指为了让系统在已经查询到的实例的基础上进行改编以满足用户的需求时所用 到的一些策略和经验，包括实例要改动的特征和改动原则。存储策略是指对于实例存 储时所用到的一些策略和经验，包括实例有用性的评价。存储位置的选择和调整等。 用户在使用该系统进行查询时。系统首先对使用者实例库进行搜索，其搜索算法 可采用传统的c b r 算法，当为一新用户时，系统先对老用户进行搜索、类比和推理， 从而找到与新用户特征匹配最好的老用户，并依据它来确定对应用实例库的兰种操作 策略，从而实现策略的重用，同时此新用户可以对老用户的策略进行修改，如果能得 到满意的结果，则此用户被存为一个新的用户实例。从而为1 2 上后的重用打下基础这 其实是实现了策略的自学习。 而应用实例库部分，它主要实现系统所涉及领域的知识的重用和自学习。它的查 询过程是这样的：当第一次查询时，对整个实例库查询，查询的结果的数量可能很大， 把这些结果存于一个中间结果表中。一般都需要对查询的结果再进行第二次查询，修 改权值后对中间结果表进行查询，而无须再次对整个库进行查询。从而，使查询速度 得到大幅度的提高，查询精度也大大地加强。而且，这个新的实例被存于实例库中， 当下次遇到相同、或类似的实例查询时，可以一次查询成功。 2 3 基于新的o b r 的智能查询系统理论分析与评价 从系统整体来看：针对不同类型的用户，把实例库分为使用者实例库和应用实例 库，这就降低了实例库的复杂度。有利于维护和管理，同时也便于用不同的组织和搜 索方法来区别对待它们。使用者实例库的自学习模块可使用传统的c b r 算法，使得算 一法的逻辑比较清楚。这样。我们可以根掘不同使用者的存储策略对存储结构进行动态 调整，使得应用实例库的存储结构得到不断优化。同时我们可以根据不同使用者的改 编策略对查询到的应用实例进行改编，可以达到更高的满意度。以上体现了新c b r 算法的使用者实例库和应用实例库同时进行自学习，这也是它的优势所在。 从搜索速度和满意度来看：对不同的用户来说，其搜索的要求是不同的，这就导 致由此抽象出来的匹配特征是不同的。同时各个特征的权值也不问即对各个特征的重 视度不同a 只有区分不问的搜索策略才能达到更好的搜索满意度和速度。搜索满意度 的提高主要是由于把使用者分为不同的实例，其针对性和学习的目的性大大地加强 昆明理工大学礤士研究生毕业论文1 0 基于w e b 的智能查询系统的砷f 究 了。不同的使用者具有和本身特点对应的一套经验，这比不区分使用者的系统具有更 高的搜索精度。搜索速度的提高主要归结于以下两点： 1 )特征权值和收敛半径的自学习性：当使用者为一新的用户时，它可以在使 用者实例库中找到一个与之最匹配的实例，从而实现特征权值和收敛半径 的重用往往能够一次搜索成功。减少了传统c b r 系统中在调照特征权值 和收敛半径时所必须进行的重复搜索。 2 )利用使用者实例的特征对应用实例库的搜索域进行分解，减少了搜索范 围。假设实例库共有u 个实例，从中抽象出x 个使用者特征用来区分不同 的使用者。那么。传统c b r 系统需要遍历u 次，而新的c b r 系统需要遍历 的实例次数为x + u x 。所以，对实例进行抽象时新的c b r 系统要比传统 的c b r 系统要快。但是，对使用者进行抽象时，使用者的个数要恰当。 新的c b r 智能查询系统的原理图如下： 囡 ( 一、) 代表实例广 代表搜索域 、- - l - j 图2 t 新的c b r 智能查询系统的原理图 实现方案图如下： 昆明理工大学硕士研究生毕业论文 蔫于w e b 的智能杏询系统的研究 图3 ：新的c b r 智能查询系统的实现方案 由于c b r 属于类比推理，同时也是一种实用的知识表达方法 1 9 】。所以。 在本系统中，把每个实例用这样表示方式来定义：那就是每个实例都由问题的表面特 征p ( p 由n 维属性向量p = ( p p 。，p a ，p 。，g i io ，“) 组成，p 为属性) 和 解答向量r 来表达，c b r 推理在两个相似域之间进行，一个是已经认识的域，它是过 去曾经解决且与当前问题相似的实例集合，不妨称之为源域，另一个是当前尚未完全 认识的域，它是遇到的新问题，不妨称之为目标域。把源域和目标域分别记为：s 、t 。 那么如果新的问题t 的一组属性p 。= ( p 。，p 。，p a ，p 。，p n ) 与某一旧实 例s 的属性p l - ( p 。p ，p ，p 。，p n ) 相似，则称问题t 与实例s 相似， c b r 系统中最基本的问题和很难的问题是关于两个实例的相似性的定义，即相似性的 度量 昆明理工大学硕士研究生毕业论文1 2 基于w e b 的智能查询幕统的w f 究 第三章相似算法 3 1 c b r 系统中的相似度概述 基于实例的推理( c b r ) 很关键的一个环境是实例检索过程得到的相似实例，这 是应用成功与否的前提。由于实例检索是在相似比较的基础上进行的，要检索到相似 的实例出来。就要完全靠“什么程度才算相似”的定义了。如果定义的不好，检索的 结果就不理想，也谈不上应用的成功。因此，相似度的定义与估算就显得尤其重要。 实例的表示表明，实例的情景是由许多属性组成，实例间的相似度就是根据属性 之间的相似度定义的。目标实例与原实例之间的相似性有语义相似、结构相似、目标 相似和个体相似口o 】。 ， 3 1 1 语义相似性 两实例之间是可以类比的，首先必须满足语义上具有相似性关系。相似性关系是 类比问题求解的基础。两个实体之间类比可以分为币类比、反类比和不确定类比。正 类比是由相似性关系所确定的两实体之间的可类比部分。反类比则是已被确定为两实 体间不相似部分。不确定类比是两实体之间尚未确定是否可类比的部分1 2 1 。其中不 确定类比使得类比具有一定的可预见性，但是这种预见可能正确也可能是错误的。在 类比求解中目标实例的本质特征和源实例的本质特征必须具有相似性关系，才能使 类比有了基础【4 】。 3 。1 2 结构相似性 如果在两个结构之间存在某种对应关系。且这种对应关系能够保持结构致性， 则认为两结构是同构的。结构一致性要求：一对应的关系必须保证它们涉及的个体 或低阶关系也是一一对应的，且这种对应关系不应打破原来个体闯的对应关系。同构 对于类比推理的有效性有重要意义。 结构对于类比检索的意义是很重要的嘲。首先，我们发现表面上并不相似的 实例由于在结构上具有相似性，从而使类比成为可能。原予和太阳系涉及不同的领域， 表面上看，并不具有什么本质的联系。然而，深入的研究表明，两者具有十分相似的 空间结构。第二，子结构问的同构或相似性可以使我们只需要见树术，而不必顾及森 林。这是因为，目标实例和原实例的类比有时只是局部的。如果从接体上看，两者可 昆明理工大学硕士研究生毕业论文 苎士些! 塑塑堂垄塑墨竺些! 壁塞 能并不具备有任何的相似性。例如，在故事理解方面，两个故事之间总的来说可能会 大相径庭。然而，其中某个情节。或者某个人物的性格等，- j f j 有惊人的相似之处。 在规划方面，我们不仅要考虑整个源方案的可用性，而且，如果尝试使用整个源方案 不能得到成功，我们还应该把注意力放在检索子方案上面。有时，放弃整个方案是不 明智的选择。 在类比的检索模型中，同构和结构相似性占有非常重要的地位。结构相似性 有助于初步检索到可类比的源实例，而同构则提醒我们优先考虑那些与l + t 标问题具有 同构和局部同构关系的源实例或部分源实例 2 3 圳】。 3 1 3 目标特征 问题求解的最终目的是要实现问题本身所提出的目标。人们求解问题时，都是向 着这个目标而竭尽全力【3 5 1 。在相似的一组源实例中，那些对实现目标实例的目标具 有潜在的重要作用的源实例，较之那些不具有日标相关性的源实例，更应该得到优先 考虑。 如果为一种结构表示增加了目标信息，那么，这个增大了的结构，同其它包含有 相似的目标信息的结构之间，更加具有语义相似性和结构一致性。换而言之，目标特 征会增加我们对源实例选择的可靠性，同时，它还可以帮助我们限制对源实例进行搜 索的范围1 3 7 1 。 3 1 4 个体相似性 在我们的模型中强调的另一重要约束是个体的类别信息。从不严格的意义上讲。 如果两个个体之间具有一些相似的属性，则它们是属于同一类别的。在概念聚类中， 我们使用概念问的相关性或紧致性来对概念集进行分类。相关性是指概念的属性之间 相似度的平均值。 有时。一个实例中的某个个体可能对问题的解决具有主导作用。在这种情况下。 这些个体应该作为问题的显着的检索信息来初步地检索源实例。在最初的检索结束之 后，对于那些同目标实例的个体具有同类关系或部分和整体的关系的源实例。我们应 该给予优先考虑。个体之间的类比有助于我们认识如何使用一个个体。实例的部分解 决能帮助发现整个实例的解。 3 2 相似度的计算模型 昆明理工大学硕士研究生毕业论文4 基于w e b 的智能查询系统的研究 对于c b r 系统，它是基于实例的推理，那么，如何比较实例之间的相似程度，就 是关键，也是难点。 传统的基于实例的推理( c a s e - b a s e dr e a s o n i n g ，简称c b r ) 系统主要使用最近相 邻检索法、归纳索引法和知识导引法这3 种实例检索策略f 3 1 - 3 3 ) 。上述3 种实例检索 策略比较适合定性属性的实例检索。 本文引入语义距离来刻莉相似实例中两个对应属性之间的相似程度，采用模糊相 似优先比来描述新问题与各个旧实例之间的模糊相似度的顺序。该相似算法采用数学 模型来计算，可得到精确的排列顺序，适用于定量属性、定性属性和混合属性的实例 检索，有较强的适应性。 3 2 1 模糊数及语义距离 3 2 1 1 数值性属性的相似度 s i m ( v i v j ) = 卜d ( v l ，v j ) = 卜d 1 j 或 s i m ( v 。，v j ) = 1 ( 1 + d ( v i ，v j ) ) = 1 ( d 。j + 1 ) 其中d 。= lv 。一v 。i 或者 d l j = iv , - v ji ( m a x ( v 。一v j ) - r a i n ( v , - y j ) ) 其中v 。v ，是某个属性v 的两个属性值1 4 】。 3 2 1 2 枚举型属性的相似度 枚举型属性相似度一般有两种；一种是只要两个属性值不同，就认为两者之间的 相似度为0 ，否则为1 ：另一种则依据具体情况而定不是简单的非此即彼地划分， 而是针对不同属性值之间不同的关系给予具体的定义前者其实是质上的，也就是说 非此即彼的二值分割；而后者则是量上的，进一步细化值问的区别。一般来讲，前者 定义通用，实用于种种情况；而后者则是要由人来预定义，与领域知识相关，从而专 用性强。所以二者各有其适用范围。 3 2 1 3 宥序属性的相似度 昆明理工大学硕士研究生毕业论文 基于w e b 的智能查询系统的研究 有序属性介于数值和枚举型属性之间，也介于定性和定量之间。属性值有序，可 以赋予不同等级值间有不同的相似度。与枚举型属性相比，有序属性归整性强。假设 属性值分为n 个等级，则等级i 和等级j 之间的相似度可以定义为1 一ii - jl n 。 数值属性、有序属性和枚举型属性之间何以可以互相转化，有时一个属性可以由 数值属性来刻画，也可以由有序属性来刻画，比如学生成绩既可以由从0 到1 0 0 的分 数来反映。也可以用a 、b 、c 来反映，只不过刻画的方式不同而已。我们要计算实例 之间的相似度，必须考虑组成一个实例的各个属性相似度综合在一起形成的效应。实 例之间的相似度也常常是通过距离来定义的 3 6 - 4 0 1 。常用的距离定义有： ( 1 ) 绝对值距离：d u = l 仇一l 其中与分别表示实例和实例j 的第 个属性值。 b m l ik 厂矿一 欧氏距离：“2 若( 1 ，* 一v 业r 其实这就是数学上的空间两点的距离 ( 3 ) 麦克斯基距离： 啦 l 仇一v 。门“” 在语义上，一个模糊区间数 a ，b c f 表示该模糊数落在 a b 中的可能度为 c f ，当 a ，b 取最大区间时，满足c f = i 一个模糊中心数( c ，r ) c f 表示该模糊数落 在以c 为中心，r 为半径的“超球”之中的可能度为c f - 当r 为最大偏差时c f = i 。 论域为实数域时，两模糊数a 、b ： a 。b i cf l ，和 a ， b 。 c r 之间的语 义距离定义为： s d ( a b ) = ( 口i a l - 8 。i ”+ w b aj b 广也l 。+ w c s o l c f 广c r l ”) “。 其中0 ，w h 0 船o 。且w , + w b + w 萨1 ：u 1 。取整数值。 当c f 产c f 2 = 1 时，若取u = l 。有 s d ( a ，b ) = w 。口。| a 。一8 2 + w b o i b i - b 2j 实际上，u 的取值视具体问题而定。此处的模糊算子“寸”可取普通的乘。 在下面的讨论中，均假设c f = i ，u = 1 ，当c f # = 1 及u l 时，情况类似。 3 3 实例的描述 昆明理工大学确士研究生毕业论文 1 6 基于w e b 的智能轰询系统的研究 设实例库c b 中有k 个实例： c b = c ，c ck c 。) k = l ，2 ，k 。 不妨设一个实例有n 个属性，不失一般性，设前面m 个属性为定量属性，后面n - m 个属 性为定性属性，则实例c t 可表达为： c k = c k lu c = ( a k l ，a k “，a 川，a h ) u ( a k 时i ) ，a k ( 一2 ) ，a k j b ，a k 。) = ( a a a l j ，a k 。) 。 式中及以下各式中均有1 j ，m ，m + l j 。n ，1 j n 。k = l ，2 ，k ，n 个属性的权重 分配为： w = ( w l 。w ，w j i - ，w 。) ， 其中o w ，1 ，且m = 1 。 j 又设需求解的新问题为c 。，则有 c i f c a l o c 2 = ( a ，a 他a i l j ，a 嘶) 。 3 4 模糊相似优先比矩阵及其截集 设a 0 。为新问题q 的某一属性，a 。a 。，a k j 分别为实例库中与新问题相似的k 个实例c - 同钆j 所对应的属性，即有集合a j - - a l j ，a 2 j a l j ，a p j ，a “设为集台a j 中的 两个元素，并和a q i j 杰生行相似程度比较，模糊影射关系s ( j ) 为： s 0 ) ：a j 。a j 一 0 ，1 s ( i ) f f i ( s j 嗍) k x k ，s j 阳r o ，1 ，p , q = l 2 ，k ， 模糊相似优先比矩阵s ( j ) = ( s 3 。) 。的截集s ( j ) 、定义为 s ( j ) - = ( 。阳) k 。b 其中以。1 ，当s 0 a ；五2 2 0 ，当s 乙a 。 s 。可描述a - ，比a q j 同的相似优先程度，且s 。愈大，说明a 。j 比a q j 与a o j 就愈相 似。同样地，通过所有s ( j ) 的 一截集，可得a 。a 。，a u 与a i 。的相似程度序列。 3 5 混合属性实例的检索模型 3 5 1 属性之间相似程度描述 昆明理工大学硕士研究生毕业论文 基于w e b 的智能查询系统的研究 3 5 ：1 1 定量属性之间相似程度描述 为了使讨论具有普遍性，下面假设实例的r n 个定量属性的取值均为模糊区间数的 情形，并设模糊区间均为最大的情形。属性值为一个点值的情况是属性值为一个模糊 区间数的特例。 设c 。的前m 个定性属性为： c 0 。= ( e d 。b 。 ， b 。 ， 。bj 1 ， d “，b 。 ) 。 不妨设c 。c e c b ，但c 。c 。，c 。c 。的前m 个定性属性有 c 产( a ma 曲，a 川，a i 一) = ( d 。，b 。 ， d 。b 。 ， d 。，b 。 ， d ，b ， ) ， c 。= ( a q l ，轧如，a q m ，a 神) = ( e d 。b 。 ， d 。b ， d d ，b q j ， d 。，b 。 ) 。 c 。与c 。的第j 。个属性之间的语义距离为 s d ( a l ，a o j l ) - - w 。 id j , - d 0 j li 十w ibp j 广b l ( 1 ) 同样地，c 。与c o 的第j ，个属性之间的语义距离为 s d ( 钆ma o j i ) = w n id i