（计算机系统结构专业论文）基于移动agent的信息检索系统中调度策略的研究.pdf

摘要 摘要 i n t e r n e t 自诞生以来飞速发展，信息容量呈爆炸性趋势增长。如何从海量的 信息中准确且快速地获取对人们有价值的信息，已成为一个非常重要的研究课题。 信息检索作为获取信息的一种重要手段日趋智能化，以此达到提高检索效率和质 量的目标。在实现智能化的过程中，移动a g e n t 技术和成员搜索引擎智能调度策 略起到了至关重要的作用。 本文首先分析了国内外智能信息检索的研究现状，在此基础上提出了论文的 主要研究内容。针对现有信息检索系统存在的局限性，设计出一个将成员搜索引 擎数据库选择算法、引擎负载均衡策略和引擎平均响应时间结合起来的智能的动 态调度策略，弥补了现有调度策略的不足，实验结果表明，采用该动态调度策略 的检索系统在查全率和查准率上有显著地提高。为提高检索的效率，系统在通信 上还引入移动a g e n t 技术，提出了基于移动a g e n t 的信息检索模型并进行了通信 实验，验证系统达到了预期目标，有效缩短了检索时间。 关键词：信息检索搜索引擎调度策略移动a g e n t a b s t r a c t a b s t r a c t i n t e r n e th a sb e e nd e v e l o p i n gf a s ts i n c ei t sa p p e a r a n c ea n dt h ei n f o r m a t i o nc a p a c i t y i n c r e a s e sr a p i d l y h o wt of i n dv a l u a b l ed a t ae x a c t l ya n dr a p i d l yf r o ma l a r g en u m b e ro f i n f o r m a t i o nh a sb e c o m eav e r yi m p o r t a n tr e s e a r c ht o p i c i n f o r m a t i o nr e t r i e v a l ，a sa n l m p o r t a n tm e a n so fo b t a i n i n gi n f o r m a t i o n ，i sg r a d u a l l yi n t e l l i g e n t ，a n dt h i sp r o c e s sc a n i m p r o v et h ee f f i c i e n c ya n dq u a l i t yo fa t t a i n i n gi n f o r m a t i o n i nt h ep r o c e s so fr e a l i z i n g i n t e l l i g e n c e ，m o b i l ea g e n ta n dt h ei n t e l l i g e n t s c h e d u l i n gp o l i c yh a v ep l a y e da n l m p o r t a n tr o l e t h i sp a p e r , f i r s t l y , a n a l y z e sc u r r e n tr e s e a r c ha c t u a l i t y , t h e np u t sf o r w a r dt h em a i n r e s e a r c hc o n t e n tb a s e do ns u c h f o u n d a t i o n a i m i n g a tt h el i m i t a t i o n so fe x i s t i n g i n f o r m a t i o nr e t r i e v a ls y s t e m ，t h ep a p e rh a sd e s i g n e dad y n a m i cs c h e d u l i n gs t r a t e g y w h i c hc o m b i n e sw i t ht h ed a t a b a s es e l e c t i o nm e t h o da n dt h ee n g i n e s l o a da n da v e r a g e t i m e t h ep o l i c y , w h i c hi sm e n t i o n e da b o v e ，o v e r c o m e st h e s h o r t a g eo fc u r r e n t s c h e d u l i n gp o l i c y , a n dt h ee x p e r i m e n tr e s u l t ss h o wt h a tt h er e c a l la n dt h ep r e c i s i o no f t h es y s t e mw h i c ha d o p t sd y n a m i cs c h e d u l i n gp o l i c ya r ep r o m o t e d o b v i o u s l y i no r d e rt o i m p r o v et h ee f f i c i e n c yo fi n f o r m a t i o nr e t r i e v a l ，t h es y s t e ma d o p t sm o b i l ea g e n t t e c h n o l o g y a ni n f o r m a t i o nr e t r i e v a lm o d e lb a s e do nm o b i l ea g e n th a sb e e np u t f o r w a r di nt h ep a p e r , a n da ne x p e r i m e n tf o rt h ec o m m u n i c a t i o no ft h es y s t e mh a sb e e n c o m p l e t e d t h er e s u l t ss h o wt h a tt h es y s t e mh a sa c h i e v e di t se x p e c t e dg o a l ，a n dt h e s e a r c ht i m eh a sb e e ns h o r t e n e de f f e c t i v e l y k e y w o r d ：i n f o r m a t i o nr e t r i e v a l s e a r c he n g i n e s c h e d u l i n gp o f i c y m o b i l e a g e n t 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论 文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科 技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 至丝辜 日期：兰! 全墨生! 旦! 目 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名： 毯：辜 导师签名：烟 日期： 日期：皇竺童! ：f 第一章绪论 第一章绪论 1 1 研究背景 i n t e r n e t 的迅速发展带来了丰富和动态变化的网络化信息资源。据统计，w e b 已经拥有1 0 0 亿左右的静态网页和5 5 0 0 亿左右的动态网页【l j 。网络向社会的方方 面面渗透，使得科学研究、教育、金融、贸易等领域的概念、内容、形式、方法 和渠道正在发生巨大的变化。现在i n t e r n e t 已逐步融入人们的工作、学习和生活中， 而用户要在信息海洋里查找信息，就像大海捞针一样，搜索引擎则是为了解决w e b “信息迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现 信息，对信息进行理解、提取、组织和处理来提供全局性网络资源控制与检索机 制，从而帮助用户方便地在网络中找到所需信息，因此在i n t e m e t 上出现了许多知 名的搜索引擎，例如国外的a l t a v i s t a 、g o o g l e 、y a h o o ! 、e x c i t e 、l y c o s 等，国内 起步较晚，现在也推出了一些搜索站点，如百度、搜狐、北大天网和教育科研网 的指南针等等，它们大大提高了人们检索信息的能力和查找信息的效率。 然而，当搜索引擎数量迅速增加，各自使用的检索方式日益复杂且结果中包含 的垃圾信息成指数级增长时，如何准确选择搜索引擎、如何减轻学习与操作负担、 如何有效利用多个搜索引擎的集成资源与检索能力等就成为制约网络信息检索技 术进一步优化和发展的重要问题。元搜索引擎的出现，在一定程度上解决了这些 问题。元搜索引擎也称集成搜索引擎，它将现有多个独立搜索引擎看成一个整体， 为用户提供一个统一的查询页面，用户的查询请求根据某种方式转换为成员搜索 引擎可以识别的方式，然后将查询请求分送到各个成员引擎完成实际的信息检索， 最后将返回的结果进行处理，以一定的格式返回给用户1 2 。国内外都有一些成功的 元搜索引擎产品，像国外的v i v i s i m o 、m e t a s e a r c h 、d o g p i l e 以及国内的万纬搜索 等，但它们在使用的智能化方面都有所欠缺，具体表现为：检索精度不高、响应 时间过长、查询请求上的局限性、调用搜索引擎上的局限性、查询结果数量上的 局限性和查询结果排序上的局限性【3 j 。 针对以上不足，论文设计并实现了一个智能信息检索系统。该系统在元搜索引 擎的基础上加入了智能化技术，提高了系统的检索精度，缩短了检索响应时间， 减少了网络带宽的占用率，增加了检索结果的个性化因素，更贴近用户的需求。 本文重点研究的就是信息检索系统中成员引擎的智能调度策略和采用移动a g e n t 技术的通信机制。 基于移动a g e n t 的信息检索系统中调度策略的研究 1 2 课题研究意义 搜索引擎作为连接互联网的一座桥梁，越来越受到人们的重视，但是搜索引擎 现在的性能还不能令人满意，性能亟待优化。信息量成倍增长但质量与利用效率 却不高，是摆在人们面前需要迫切解决的问题。元搜索引擎可以对独立搜索引擎 在检索范围上的局限性做出一定程度的弥补和改善【4 1 。对用户而言，元搜索引擎可 以使用户提交的检索请求一次性递交给多个独立的搜索引擎进行查找，获得多个 独立搜索引擎的检索结果，节省时间，提高效率。目前，国内外非常重视元搜索 引擎的研究和开发。 我国对于元搜索引擎已有了初步的研究，并且出现了一些元搜索引擎，但是， 随着信息资源的日益膨胀，这些元搜索引擎在用户性能、信息覆盖率、查全率、 查准率、系统效率和响应时间等方面还都有待改进。因此，结合传统的信息检索 技术，综合利用计算机网络技术、数据库新技术、a g e n t 技术、智能算法、计算机 语言学等多个领域的研究成果来研究开发新一代的信息检索系统，使之更智能化、 更个性化、更能满足用户的需求，是具有重要理论意义和广阔应用前景的。 本文就是在研究现有元搜索引擎存在的局限性的基础上，设计出一个结构更合 理、功能更优越，同时能够融合很多相关领域技术，体现个性化查询的智能信息 检索模型。该模型充分考虑到独立搜索引擎对检索信息的偏重以及响应时间的不 同，结合成员引擎负载量和性能评价表采用动态实时调度策略，解决了查准率偏 低等问题；在通信上引入移动a g e n t 技术，利用a g e n t 的智能性和主动性实现信息 检索中的个性化主动服务，采用移动a g e n t 技术能够很好地适应网络信息的发展， 是元搜索引擎发展的必然趋势，是计算机科学与技术和信息科学相结合的前沿课 题，既具有重要的学术价值，又有很强的实际应用背景。 1 3 国内外研究现状 国外的元搜索引擎的发展速度很快，目前已经有上百个产品，其中不乏有很多 优秀的元搜索引擎，如d o g p i l e 、m e t a c r a w l e r 、p r o f u s i o n 、m a m m a 等。 d o g p i l e 是一个并、串相结合的元搜索引擎，共收集了8 个最流行的搜索引擎， 提供w e b 检索、新闻组检索、多媒体检索、地图检索等等【5 j 。它的定制检索可以 让使用者设置过滤、多语言、拼写纠正等功能，有自己的网站目录和其他资源， 返回结果可以按所调用搜索引擎归类排序或按相关度排序。 m e t a c r a w l e r 是一个并行式元搜索引擎，提供涵盖近2 0 个主题的目录检索服 务，其中高级检索模式可实现：搜索引擎的选择调用，基于域名、地区或国家的 第一章绪论 检索结果过滤，最长检索时间设置，每页可显示的和允许的每个搜索引擎返回的 检索结果数量的设定。 p r o f u s i o n 拥有智能化的检索技术、对查询的实用提示和个性化的定制服务， 也是目前最优秀的并行元搜索引擎之一。它可以选择调用3 个检索结果最好或最 快的成员引擎，或手动自选成员引擎进行查询，并且能自动对查询结果进行整理 和删除冗余项。 国内自主开发的万纬搜索引擎是一个并行元搜索引擎，支持简单查询和高级查 询。在简单模式下，提供结果数量选择菜单，在最短的时间内为用户提供最符合 的查询结果；在高级搜索模式下提供独立搜索引擎列表，用户可以根据自己的需 要来选择合适的引擎。同时，用户可以根据需要设置搜索返回结果的排列方式， 可根据相关度、时间、域名分类、引擎等项。此外，还可以设置最大等待检索时 间、最大检索结果限制、显示结果统计、网页标题、源搜索引擎标志、内容摘要 等。 国内的元搜索引擎与国外有明显的差距，主要表现在【6 j ： 1 查询请求提交机制比较落后，缺乏逻辑查询支持和高级查询选项。 2 查询结果处理及显示机制存在不足，如对查询结果的去重、合并和输出处 理等技术差距较大，显示细节考虑不够。 3 在界面友好性、个性化服务方面有待完善。 尽管智能化搜索已经成为元搜索领域内研究的焦点，但是目前大部分元搜索引 擎还不能很好的提供这类搜索服务，国内外的搜索巨头也纷纷推出自己的测试版 产品【7 1 。n e c 研究院提出了个性化元搜索引擎系统i n q u i r u s 2 ，它可以根据用户输 入的偏好优化查询关键词，并对返回的结果进行排序。 雅虎推出的个性化搜索服务“m yy a h o o ! s e a r c h “，目的是使注册用户可以用 自己喜欢的方式搜索想要的信息，并对搜索结果提供更好的管理和共享。它可以 在搜索结果页上加上注释，可在w e b 的保管场所整理归档，也可根据需要对保存 后的w e b 网页进行分类或排序，还可通过电子邮件和r s sf e e d 与其他人共享搜索 结果。 g o o g l e 推出自己的个性化搜索服务“p e r s o n a l i z e dw e bs e a r c h 和“w e b a l e , s 。 g o o g l e 的个性化网络搜索通过使用一系列的检查框来帮助用户精简他们的搜索结 果，并把搜索结果通过电子邮件发送给注册用户。 a o l ( 美国在线) 的个性化服务将赋予用户定制搜索操作、保留查询、管理处理 和存储搜索结果的能力。 中国搜索( 中搜) 推出的个性化搜索是通过建立简单的用户兴趣模型，对搜索结 果进行个性化处理的一种搜索方式，它能根据用户定制的喜好，返回与用户最相 关的搜索结果，目前只提供两级兴趣类。 4 基于移动a g e n t 的信息检索系统中调度策略的研究 搜狐于2 0 0 4 年推出全球首家中文互动式搜索引擎一搜狗( w w w s o g o u c o r n ) ，它 是以一种人工智能的新算法，分析和理解用户可能的查询意图，给予多个相关主 题的搜索提示。在用户查询和搜索引擎返回结果的人机交互过程中，引导用户更 快速、更准确地定位自己所关注的内容，帮助用户找到所需的检索结剁引。 南京大学推出自行研制的个性化信息检索智能体d o l t r i a g e n t ，该智能体可 以学习用户的兴趣，并根据学习到的用户模型提供个性化的信息【9 】。中国科技大学 基于分布式智能体技术和相关反馈学习提出了一个个性化信息检索系统。浙江大 学提出了个性化信息检索系统n e t l o o k e r ，该系统综合采用两层分布式智能体技 术、相关反馈学习算法和信息过滤方法实现个性化检索。 智能a g e n t 的兴起始于8 0 年代，它是人工智能技术的一个充满挑战的研究领 域，进入9 0 年代后，随着i n t e m e t 的广泛使用及其相关技术的飞速发展，围绕着 i n t e m e t 展开的智能a g e n t 技术研究取得了很大的进展。国内外的研究经验表明， 发展智能a g e n t 技术是一个趋势，它将是克服i n t e m e t 现有问题的有效手段i lo j 。对 基于a g e n t 的元搜索引擎的研究开始时间不长，但是已经提出了一些具有可行性 的方案。例如上海大学刘宗田等提出的基于w 曲多a g e n t 协同搜索框架( c s a ) u 、 中南大学徐德智等提出的基于a g e n t 的搜索引擎模型( a b s e e ) 2 j 、哈尔滨工业大学 的李滨丽等提出的基于m o b i l ea g e n t 的信息搜索系统( i s s m a ) 【1 3 】、武汉大学张功耀 等提出的基于多a g e n t 的搜索引擎模型【l4 1 、东南大学冯永杰等提出的基于a g e n t 的信息检索方法【1 5 j 等。 1 4 论文主要内容 本文研究的重点是提出一种基于移动a g e n t 的信息检索系统中的智能调度策 略，以弥补现有信息检索技术的不足，为快速高效地获取面向用户的网络信息提 供一种有效方法，以满足用户智能化查询的需求。论文所做工作如下： 1 对智能信息检索系统的功能需求进行了分析，设计了调度模块和通信模块 的主体框架和工作流程。 2 对用户提交的检索请求进行关键词的提取、查询扩展，以及查询所属主题 类别的定位分析。通过这些分析和处理，可以更好地理解用户的查询请求，从而 为成员引擎的调度提供有力的基础保障。 3 研究并实现了一种智能调度算法，很好地考虑到了各个独立搜索引擎对不 同信息的检索性能有所区别以及成员引擎当前负载量和平均响应时间，采用动态 选择算法在每一次查询中调用最优的几个引擎来进行检索操作，并能根据检索结 果不断地更新调度性能评价模型。 第一章绪论 4 在服务器与成员引擎的通信方式上，论文采用移动a g e n t 技术取代传统c s 模式，将所有数据在本地打包传输到接收端。实验表明，使用移动a g e n t 技术大 大减少了网络传输负担，缩短了传输耗时。 1 5 论文结构 论文共五章，具体章节如下： 第一章绪论。介绍了课题的研究背景和意义，讨论了国内外相关技术的研究 现状，给出了论文要研究的内容及其所作的工作。 第二章智能信息检索相关技术研究。概要介绍了元搜索引擎的原理及分类， 在总结其不足的基础上提出了智能信息检索系统，分析了系统的体系结构，之后 讨论了搜索引擎调度常用的三种策略，最后描述了移动a g e n t 的概念、体系结构 及应用。 第三章基于移动a g e n t 的信息检索系统的设计与实现。在分析传统信息检索 的局限性的基础上，提出论文设计的检索系统的设计思路与解决方案，之后介绍 了系统的功能模块和工作流程，详细分析了信息前处理模块的三个子模块即查询 请求分析、成员引擎调度和查询参数转换的设计与实现，最后着重给出了基于移 动a g e n t 的通信模块的实现过程，并进行了实验分析。 第四章智能调度策略的实现与算法仿真。本章是论文提出的调度策略的实现 和仿真环节。在探讨了经典的调度算法后，对论文提出的智能调度算法的设计原 则与思路作了分析，详细讨论了该调度算法中用到的关键技术和策略，即成员引 擎的特征表示( 也可称为数据库选择技术) 、成员引擎的负载平衡策略和平均响应 时间计算，最后对算法进行了仿真，通过性能分析，验证了其可行性和先进性。 第五章总结与展望。总结了全文所做工作，提出了研究的不足之处，并指出 了进一步的研究方向。 第二章智能信息检索相关技术研究 7 第二章智能信息检索相关技术研究 2 1 1 元搜索引擎 2 1 信息检索技术 所谓元搜索引擎，是对分布于网络的多种检索工具的全局控制机制，它通过一 个统一的用户界面帮助用户在多个搜索引擎中选择和利用合适的引擎来实现检索 操作。元搜索引擎按功能划分包括集成搜索引擎和多线索式搜索引擎；按运行方 式的差异又可分为桌面型元搜索引擎和基于w e b 的元搜索引擎：按工作方式，元 搜索引擎分为并行处理式和串行处理式两大类，并行处理式元搜索引擎将用户的 查询请求同时转送给它调用链接的多个独立型搜索引擎进行查询处理；串行处理 式元搜索引擎将用户的查询请求依次转送给它调用的独立搜索引擎i l 6 j 。 一个真正的元搜索引擎由三部分组成【1 7 1 ：检索请求提交机制、检索接口代理机 制和检索结果显示机制。如图2 1 所示，其中检索请求提交功能与其他搜索引擎提 交功能相似，是系统的用户接口。对于元搜索引擎来说，搜索请求提交的方式一 方面受到引用的独立搜索引擎调用方法的限制，另一方面又要提供用户选择搜索 结果显示方式的功能，是系统的统一用户接口；检索接口代理功能是将所有信息 请求转化为独立搜索引擎本地化格式，同时也转化返回的搜索结果；检索结果处 理功能是对各成员引擎返回的结果信息进行相关处理( 如删除重复结果、校验链接、 按相关值排序等) ，然后以统一的格式返回给用户。因此可将元搜索引擎看成具有 双层c s 结构的系统，用户向元搜索引擎发出检索请求，引擎再根据该请求向多 个搜索引擎发出实际的检索任务，搜索引擎执行完检索请求后以应答形式返回检 索结果，上层处理机构将所有结果整理后最终显示给用户。 元搜索引擎的特点主要有【1 8 】：1 增加了查询的w e b 覆盖范围：2 解决互联网搜 索引擎的可扩展性问题；3 便于对多个独立搜索引擎的查询；4 提高检索的有效性。 它与一般搜索引擎的区别在于它没有自己独立的数据库，更多地是提供统一的界 面供用户查询，形成一个由多个分布的、具有独立功能的搜索引擎构成的虚拟逻 辑整体。这些独立的引擎称为“成员搜索引擎”，它们各自保持其原来的局部数据 模式和检索指令。 元搜索引擎的主要功能有【1 9 j ： 1 搜索引擎的选择：元搜索引擎一般自动选择若干个合适的搜索引擎集合具 体进行检索。 基于移动a g e n t 的信息检索系统中调度策略的研究 图2 1 元搜索引擎结构图 2 检索指令的转换：由于每个搜索引擎都有自己的查询语言，因此上层转换 机制要将统一的全局检索指令转换为各个成员引擎的局部指令。 3 检索结果合并：从各个成员引擎返回的结果具有不同的数据格式，因此要 转换格式并构成逻辑上统一的整体结果集合呈交给用户。 目前已有的元搜索引擎各具特色，功能各有侧重，如大多数元搜索引擎不支持 多语种，尤其是中文检索；一些元搜索引擎实现检索语法转换的能力有限，不支 持指定字段检索，不能充分发挥各个独立引擎的高级检索功能；在检索结果上， 元搜索引擎只能返回数十条信息，大量可能有价值的结果被忽视，影响检索结果 的全面性。 2 1 2 智能信息检索 元搜索引擎是基于独立搜索引擎在互联网上进行信息检索，通常情况下不同 搜索引擎之间没有协作，各自独立地搜集和处理信息，造成了大量重复劳动又浪 费了网络带宽，故这种静态元搜索引擎体系结构难以适应日益扩大的网络规模。 为了改进静态元搜索引擎的不足，目前出现了一种将智能化技术运用于信息检索 的智能信息检索系统，其基本框架结构如图2 2 所示。其基本思想是：根据检索主 题、各搜索引擎的实际工作状况以及它们对各类信息的检索相关度情况，动态地 调用合适的成员引擎。 第二章智能信息检索相关技术研究 9 一 一 一 图2 2 智能信息检索系统框架图一 该系统与传统的元搜索引擎相比有4 个突出的特点： 1 搜索速度快。由于采用了多线程技术并且通过建立历史文档库将用户经常 访问的数据存储起来，克服了机械式检索信息的不足，加快了搜索服务的速度。 2 检索结果精度高。研究结果表明，信息搜索服务提供的结果信息量过大也 会影响信息服务的质量。本文实现的系统通过去除重复信息和过滤掉相关度较低 的信息，有效地减少了结果信息量。 3 成员引擎查准率稳定。通过对现有元搜索引擎的比较和分析，可以发现由 于机械式的调用独立搜索引擎而导致检索结果查准率波动较大，返回大量的无用 信息。而智能信息检索系统充分考虑了每个搜索引擎在不同搜索主题下表现出不 同的搜索性能，采用智能调度策略，动态的决定当前最佳的搜索引擎，真正做到 取各搜索引擎之长，补其之短。 4 基于a g e n t 技术。利用a g e n t 的自主性、相互之间的协调性来完成搜索任 务，满足用户需要的个性化检索，提高检索的查全率和查准率。 1 0 基于移动a g e n t 的信息检索系统中调度策略的研究 2 2 搜索引擎调度策略 查询分发机制是信息检索系统框架中重要的组成部分，它负责将用户的查询请 求分发给成员引擎。如果成员引擎数量不多，那么可以直接将用户查询请求分发 给所有的成员引擎。研究信息检索系统的调度策略就是为了在检索中提供数量合 适并贴近用户查询请求的成员引擎，其目标是以较小的资源耗费，帮助用户获得 较高的查询质量。调度策略通常包括成员引擎的特征表示和调度算法 两部分。成员引擎的特征表示代表成员引擎的数据库所具有的特性以及它的查询 能力和特点。调度算法则根据成员引擎的特征表示计算用户查询与成员引擎的数 据库之间的相关度，由相关度的高低来进行成员引擎的选择。孟卫一【2 0 】f 2 1 1 将数据 库选择算法分为三类：定性算法、定量算法和基于学习的算法，以下各小节将详 细讨论这三种方法。 2 2 1 定性法 这类方法根据一定的评分函数针对给定查询预测每个数据库的质量，其评分或 质量衡量往往不易理解1 2 2 1 。 1 粗略特征信息表示法 在这种方法中，成员数据库的内容往往会被一些经过精心挑选的关键词或语句 表示。使用粗略信息的好处在于这些信息相对比较容易获得而且只需要很少的存 储空间。但是这种方法通常只能提供关于成员数据库内容的一些粗略的信息，很 难充分全面地代表成员数据库的内容，因此这种策略在给定某个特定的查询任务 时，不能非常有效和精确的估计成员数据库的有效性，很可能遗漏和忽略一些潜 在有用的成员数据库。 例：a l i w e b ，w a i s ，s e a r c hb r o k e r 方法【2 3 】 ( 1 ) 在a l i w e b 方法中，会使用人工生成的固定格式来表示成员数据库或网 站搜索引擎的内容。例如，一个包含有p e r l 语言编程资料的网站会被表示成以下 这种格式： t e m p l a t e - t y p e ：d o c u m e n t title：ped u r i p u b l i c p e r l p e r l h t m l d e s c r i p t i o n ： i n f o r m a t i o no nt h ep e r lp r o g r a m m i n gl a n g u a g e i n c l u d e sal o c a lh y p e r t e x tp e f lm a n u a l ，a n dt h e l a t e s tf a qi nh y p e r t e x t k e y w o r d s ：p e r l ，p e r l f a q ，l a n g u a g e 第二章智能信息检索相关技术研究 a u t h o r - h a n d l e ： m k o s t e r n e x o r e o u k 当用户提交查询请求时，系统会根据查询关键词与各个成员数据库的特征信息 匹配的结果，对成员数据库进行排序并按匹配程度的高低将结果显示在一个列表 中，然后再让查询用户选择一个成员数据库执行查询任务的操作。需要强调的是， a l i w e b 并不是一个严格意义上的并发元搜索引擎，它一次只允许用户选择一个 成员数据库来完成查询任务，并且并不包含结果合并的策略模块。 ( 2 ) w a i s ( w e bi n d e xa n ds e a r c he n g i n e ) 也是使用数据库的描述信息。对于给 定的查询，根据查询与数据库特征描述信息之间的相似度来划分成员数据库，然 后用户选择合适的数据库来获取想要的文档，但是在w a i s 中可以同时选择一个 以上的成员数据库。 ( 3 ) s e a r c hb r o k e r 方法与前述的两种方法类似，但是它采用的是通过给成员数 据库附加关键词将它们分成不同的类别，当用户提交查询请求的时候，用户还必 须首先确定查询的类别，然后再选择一些属于该类别的成员数据库进行搜索直到 找到满意的结果文档。 ( 4 ) n e t s e r f 方法也是一种粗略特征信息表示法。但是它与a l i w e b 等方法使 用的数据库简单文本方法描述不同，它采用了结构化的信息表示方法而且采用特 定的词典来消除同义词的影响，例如，如果有一个名叫w o r l df a c t b o o k 的成员数 据库，它包含的主要内容是“w o r l df a c t sl i s t e db yc o u n t r y 同类型的文件，该数据 库的结构化特征信息描述就可能会采用如下的方式： t o p i c ： c o u n t r y s y n s e t ： 【n a t i o n , n a t i o n a l i t y , l a n d ，c o m m y ，a _ _ p e o p l e 】 s y n s e t ：【s l a t e ，n a t i o n , c o u i l 仃ml a n d ，c o m m o n w e a l t h ，b o d y _ p o l i t i c 】 s y n s e t ：【c o u n t r y , s l a t e ，l a n d ，n a t i o n 】 i n f o - t y p e ：f a c t s 从以上信息可以看出根据该词典“c o u n t r y 这个单词被划分成了三个同义词 集合，简单文本描述也被细化成若干条结构化描述信息，而且用户的查询语句也 会被系统相应进行拆分，这样在选择成员数据库时就增加了成员数据库与查询关 键词之间的匹配能力。 2 详细特征信息表示法 较新的定性方法多采用非常详细的数据库特征信息。一个数据库的详细特征信 息涉及到在此数据库里每一个文件中出现的词汇的统计信息。因此，如果处理 得当，使用详细特征信息的数据库选择策略可以探测到每一个潜在有用的成员数 据库，也可以为每一个词汇保存一个或多个统计信息。 d w i s e 方法是应用在d w i s e 2 4 】分布式元搜索引擎中的一种w e b 数据库的特 征信息表示方法。d w i s e 元搜索引擎是由香港科技大学实施进行的一项信息检索 1 2 基于移动a g e n t 的信息检索系统中调度策略的研究 实验项目，其中它设计实现的d w i s e 资源数据库元信息表示方法对于成员数据 库的选择问题具有一定的典型意义。 在d w i s e 方法中，每一个成员数据库都会向外提供其文件数据库中每个词汇 的文档频度d f ( d o c u m e n tf r e q u e n c y ) ，即数据库中包含该词汇的文档个数。除了提 供每个文件的d f 信息，成员数据库还会公布一个自身的维数，即它包含的文档总 个数。 当查询用户提交一个查询请求q 时，假设成员数据库，的维数是豫，数据库f 中 的词汇f 的文档频度为a f , j ，首先计算成员数据库i 相对于q 中每个查询关键词t j 的 有效性c ，： c z , j = 矾 刀f 其中n 是整个成员数据库的个数，直观上看c 形，计算的第i 个数据库中包含关 键词，占所有包含t ，的数据库中的比例。下面计算每个关键词t ，的c 的方差 c 嘎： ， ( c 巧- a c z j ) 2 c 嘎= 旦_ f 一 式( 2 - 2 ) 其中彳c 巧是元搜索引擎中所有成员数据库c 的算术平均值。c ，衡量的是 查询关键词t ，在所有成员数据库中的分布，如果c 暇大于c 暇说明关键词乙要 比关键词，。在成员数据库中分布地更均匀些，这可以明显的从系统为各个成员数 据库的评分分值r 的计算公式中看出： m = c 矾 式( 2 3 ) j = l 其中m 是g 中查询关键词的个数。元搜索引擎根据成员数据库评分值，：的高低 选择一个分值最高的成员数据库进行查询以保证查询是在查询关键词集中程度最 高的数据库中进行。这种方法简单易扩展，但也有可能忽略一些得分低的成员数 据库中有用的文献。 2 2 2 定量法 这类方法根据一些比定性方法使用的衡量标准更易理解的标准来衡量数据库 的有用性。换言之，定量的方法使用根据给定查询计算出数据库的有用性相对于 式 每一 k 彬一一缸i 蛎一体 第二章智能信息检索相关技术研究 定性方法而言更加直接和明确。定量方法与定性方法的主要区别是前者使用的衡 量数据库有用性的标准更加明确和实用瞵】。举例来说，定量方法使用的衡量成员 搜索引擎数据库有用性的一种标准是“成员搜索引擎数据库中对于每一个查询潜 在的有用文件的数量 。很明显，这个数量清楚的反映了该成员搜索引擎数据库对 于给定查询的有用性。 另外一种有用的定量衡量标准是：一个成员搜索引擎数据库中与给定查询最为 相似的文件的全局相似度。一方面，该标准表明了能够指望从一个成员搜索引擎 数据库中可得到最好的结果是什么。另一方面，对于给定的查询，该标准可以用 来最优化的对成员搜索引擎数据库进行排序，进而从所有成员搜索引擎数据库中 检索得到最相似的m 个文件。接下来分析一些基于典型衡量标准设计的定量方法。 1 估算成员数据库中潜在有用文件的数量 以这种标准设计的选择策略清楚反映了搜索引擎对给定查询的有用性。缺点是 需要在元搜索引擎中保存大量资料才可以得到较高的估计准确性，更适用于处理 属于较少的短查询，计算复杂度是指数级的，而且统一术语权值假设，减少了成 员搜索引擎有用性估计的准确性。 例如：假设d 是元搜索引擎的成员搜索数据库，s i m ( q ，d ) 表示d 中的一个文档 d 与查询请求g 之间的全局相关度。r 是一个指定相关度阈值，具有大于这个阈值 的文件就被认为是对查询请求有用的，则潜在有用文档的数量可被精确定义如下： n o d o c ( d ，q ，丁) = c a r d i n a l i t y ( dl d da n ds i m ( q ，d ) ， ) 式( 2 - 4 ) 如果n o d o c ( d ，q ，t ) 可以被精确地估计出来，那么元搜索引擎只需选择那些潜 在有用文档数量较多的成员数据库搜索即可。w e i y im e n g 于1 9 9 8 年提出了当文档 与查询请求之间的全局相似度是用内积公式计算时的具体过程如下：首先将包含 有刀个不同词汇的成员数据库表示成一个包含力个序对 ( n ，w ，) ) ，j = 1 , 2 ，7 的向 量，其中p 表示词汇f 在成员数据库d 中出现的概率，实际计算中可以用f ，的文档 频度来代替，w 表示d 中所有包含词汇，的文档赋予t 的权值的平均量。包含k 个 关键词的查询请求q 可以表示为 g i ，9 2 ，g t ) 的向量。多项式的生成函数为： ( p l x 9 1 + ( 1 一p 1 ) ) 幸( p 2 xw 2 胃2 + ( 1 一p 2 ) ) 木牛( p j x 呵+ ( 1 一p 七) ) 式( 2 5 ) 该多项式展开以后就变成如下形式： a 。y6 j + a ，x 如+ 4 - 口，x ，b 1 b ， b ，式( 2 6 ) 可以看出，如果词汇，相互独立而且词汇f 在d 中任何包含它的文档中，其权 值均为w f ，则q 可以看成是成员数据库d 中与q 相似度为6 ，的一个文档概率。因 此，如果数据库d 中有个文件，那么n 幸口就可以用来估算d 中与g 相似度为匆 的潜在文档数量，加入t 是一个指定相关度闽值，且b c t ，则： 1 4 基于移动a g e n t 的信息检索系统中调度策略的研究 n o d o c ( d ，q ，r ) = n a z = 人r 口 式( 2 - 7 ) i i li - i 以上的解决方案有两个限制性假设：第一个是词汇独立假设，第二个是统一词 汇权值假设，这些假设减少了成员数据库中有用文件数量估计的准确性。上述的 方法需要在集成引擎处保存大量资料才能得到较高的估计准确性，而且展开生成 函数的复杂度是指数级的，因此它们更适用于处理关键词较少的短查询。 2 估算最相似文件的相关度 假设用户要求从拥有m 个成员搜索引擎数据库d 】，岛，d 。中查找册个相对 于查询q 相关度最高的文档，对于查询g 而言，成员数据库一个优化的顺序应该是 d 。，皿，d 脚) ，其中存在一个整数k ，使得d l ，d ：，皿中含有这m 个相关度最 高的文档，并且其中每个成员数据库d ，1 f k ，至少含有聊个相关度最高的文档 中一个。 2 2 3 基于学习的方法 这类方法根据以往检索成员搜索引擎的经验来预测各引擎对新查询的有用性。 这些经验可以通过如下几种方法获得【2 6 j ： 第一，使用训练查询( t r a i n i n gq u e r y ) 帮助系统预先获取成员数据库的信息，即 使数据库选择器还没有激活。这种方法被称为静态学习型方法，因为数据库信息 一旦通过训练查询获得就不会再发生变化。该方法的弱点是无法适应数据库内容 的更新和查询模式的变化。 第二，可使用真正的用户查询( 而不是训练查询) 在对实际查询的处理中逐步积 累和更新处理经验。这种方法被称为动态学习型方法，其缺点是选择器需要一 段时间才能获取足够有用的处理经验。 第三，综合学习型方法，这种方法中，数据库选择器通过训练查询获取初始化 处理经验，然后通过实际查询持续动态更新处理经验，综合学习可以克服另外两 种方法的弱点。 下面简单介绍两种主要的基于学习型数据库选择方法。 1 s a v v y s e a r c h 方法。s a v v y s e a r c h 是一个采用动态学习方法的集成搜索引擎， 它对于成员搜索引擎关于一个查询的评分是根据查询中术语在以往查询中所获得 的知识来得到的。 2 p r o f u s i o n 方法。p r o f u s i o n 是一个使用混合学习方法的元搜索引擎。在 p r o f u s i o n 中，1 3 个预先设置的类别被用于学习过程。这1 3 个类别是：“科学和工 程”，“计算机科学”，“旅行旅游”，“医学和生物学”，“商业和金融”，“社会和宗教”， “社会、法律和政府”，“动物和环境”，“历史”，“休闲和娱乐”，“音乐”，“艺术”和“食 第二章智能信息检索相关技术研究 品”。每一个类别有一组反映该类别主题的术语，对每一个类别，一组训练查询将 用来做静态学习。使用这些类别以及专门的训练查询的原因是为了了解不同的成 员搜索引擎对于不同类别的查询的响应情况。 2 3 移动a g e n t 技术 a g e n t 是分布式人工智能的一个基本术语，同时也是人工智能的一个原语。 w o o l d r i d g e 和j e r m i n g s 在1 9 9 8 年给出的定义是口7 】：a g e n t 是处在某个环境中的计 算机系统，该系统有能力在这个环境中自主行动以实现其设计目标。f r a n k l i n 和 g r a e s s e r 对a g e n t 给出这样的定义【2 8 l ：a g e n t 是一个处于一个环境之中并且作为这 个环境一部分的一个系统，它随时可以感受到这个环境并且执行相应的动作，同 时逐渐建立自己的活动规划以应付未来可能感受到的环境变化。而s h o h a m 认为 1 2 9 1 ：a g e m 就是一种实体，它由许多心智状态，如信念、能力、选择和承诺等组成 的。 2 3 1 移动a g e n t 的概念特性 2 0 世纪9 0 年代初由g e n e r a lm a g i c 公司在推出商业系统t e l e s c r i p t 时提出了移 动a g e n t 的概念。简单的说，移动a g e n t 是一个能在异构网络中自主地从一台主机 迁移到另一台主机，并可与其他a g e n t 或资源交互的程序【3 训。在移动时，该程序 可以根据要求挂起其运行，然后转移到网络的其他地方重新开始或继续其执行， 最后返回结果和消息。在转移过程中它的执行状态被保持，转移到目标后的执行 是持续的。移动a g e n t 的执行平台是一个虚拟机，通常被称为移动a g e n t 服务器， 为移动a g e n t 的移动和执行提供执行环境，为移动a g e m 的发射、接收、恢复、安 全管理和服务调用等提供基础服务设施。移动a g e n t 携带完成