（计算机应用技术专业论文）元搜索引擎的调度策略研究.pdf

元搜索引擎的调度策略研究 孟丈杰( 计算机应用技术) 指导教师：李村合( 教授) 摘要 随着网络信息的爆炸性增长，用户在网上查询所需信息的难度越 来越大。要想得到更为全面、准确的搜索结果，必须同时调用多个搜 索引擎，元搜索引擎就是在这样的背景下产生的。元搜索引擎的调度 策略是影响元搜索引擎查询性能的关键因素，也是元搜索引擎研究的 重要领域。它研究如何选择合适的成员搜索引擎进行组合，以较小的 资源耗费，帮助用户获得较高的查询质量。介绍了元搜索引擎的基本 概念与关键技术，分析了影响元搜索引擎查询性能的几方面的因素， 并对元搜索引擎的调度策略进行了深入的研究。研究了国内外现有的 元搜索引擎调度策略，分析其优缺点，发现一些调度策略在查询新术 语或者不常见术语时尚有所欠缺；另外元搜索引擎对于成员搜索引擎 的评价也不明确。针对以上不足，提出了一种基于检索术语分类的搜 索引擎评价方法。该方法根据成员搜索引擎的查全率、查准率和平均 响应时间，对其查询性能进行评价。将这种评价方法与基于以往查询 经验的评价方法结合起来，提出了一种新的基于学习的元搜索引擎的 调度策略。设计并实现了基于该调度策略的系统模型，测试了调度策 略的生成、查准率以及对查询不常用术语的查询质量，并将实验结果 与万纬元搜索引擎得到的结果进行比较。实验结果表明，系统有效地 提高了查准率，改善了查询不常用术语的查询质量。 关键词：元搜索引擎，调度策略，搜索引擎，查询性能 s t u d y o fs c h e d u h n g s t r a t e g y f o rm e t as e a r c he n g i n e l v i e n gw e n - j i e ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rl ic u r t - h e a b s t r a c t w i t ht h ee x p l o s i v ei n c r e a s eo f n e t w o r ki n f o r m a t i o n , i tb e c o m e sm o r e a n dm o d i 伍c u hf o rp e o p l et ol o o kf o rw h a tt h e yw a n t t og e tm o r ef u l l s c a l e ，a c c u r a t es e a r c hr e s u l t s ，m u l t i s e a r c he n g i n e ss h o u l db eu s e da n d m e t as e a r c he n t r i e so c c r r s c h e d u l i n gs t r a t e g yi sak e yf a c t o rt h a tc a n a f f e c tt h eq u e r yc a p a b i l i t yo fm e t as e a r c h e n g i n e sa n di t i sa l s oa n i m p o r t a n tr e s e a r c hf i e l d i ti s t oh e l pc h o o s ep r o p e rg r o u po fs e a r c h e n g i n e sf o raq u e r yt og e tm o r ea c c u r a t er e s u l tf o rt h eu s a 8w i t hl e s s r e s o u _ r c e t h eb a s i cc o n c 印t i o n so fm e t as e a r c he n g i n e sa r ei n u o d u c e d w h i c hd i s c u s st h ef a c t o r st h a ta f f e c tt h ee f f i c i e n c yo fm e t as e a r c he n g i n e s a n dt h es c h e d u l i n gs t r a t e g yo f m e t as e a r c he n g i n e si se s p e c i a l l ys t u d i e di n t h i sp a p e r s c h e d u l i n gs t r a t e g i e so fm e t as e a r c he n g i n e st h a th a v e a p p e a r e di na n do u to fc h i n aw 讹s t u d i e d , a l s ot h e i ra d v a n t a g e sa n d s h o r t c o m i n g sw e r ea n a l y z e d t h e ni t i sd e t e c t e dt h a ts o m es c h e d u l i n g s t r a t e g i e sd o n tp e r f o r mw e l lw h e ns e a r c h i n gi t e m sw h i c ha r en e w o rl e s s u s e d , a n ds o m ed o n t e v a l u a t em e m b e rs e a r c h e n g i n e sd e f i n i t e l y t h e r e f o r e , an e wm e t h o di sp r o p o s e dt oe v a l u a t et h eq u e r yc a p a b i l i t yo f s e a r c he n g i n e sb a s e do nc a t e g o r yw h i c hu s e sr e c a l l ，p r e c i s i o na n da v e r a g e r e s p o n s et i m e c o m b i n i n gt h i se v a l u a t i n gm e t h o da n dt h em e t h o db a s e d 0 1 1f o r m e re x p e r i e n c e s ，an e ws c h e d u l i n gs l r a t e g yf o rm c t as e a r c he n g i n e s b a s e do ns t u d yi sb r o u g h tu p at e s ts y s t e mw a sd e s i g n e da n de x p e r i m e n t s w e r et a k e nt ot e s tt h ee s t a b l i s h m e n to fs c h e d u l i n gs t r a t e g y , t h ep r e c i s i o n a n dt h eq u e r yc a p a b i l i t yf o ri t e m sw h i c ha r eu s e dl e s s t h er e s u l t ss h o w t h a tt h et e s ts y s t e mp r o m o t e st h ep r e c i s i o ne f f e c t i v e l ya n di m p r o v e st h e q u e r yq i 】a l 毋o f i t e m sw h i c ha r eu s e d l e s s k e yw o r d s ：m e t as e a r c he n g i n e ，s c h e d u l i n gs t r a t e g y , s e a r c he n g i n e ，q u e r y c a p a b i l i t y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中 国石油大学或其它教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 。 签名： a 口洚争月f 日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名：垂童查，z 净争月f 日 导师签名：名 岭劭d 7 年 牟 月 f 日 中国石油大学( 华东) 硕士论文第1 章前言 第1 章前言 1 1 课题的背景 随着i n t o n e r 以及相关技术的发展与成熟，玷t e m 髓已经成为人们 获取所需资源和信息交流的主要场所。据权威机构统计，1 9 9 9 年全球 网页总数量不到3 0 亿，2 0 0 0 年达到了近5 0 亿i l 】，截止到2 0 0 5 年1 月，可以检索到的网页至少有1 1 5 亿1 2 。传统搜索引擎由于其自身固 有的局限性，使得人们不能充分利用网络资源，而陷入了一种信息丰 富却知识贫乏的矛盾状态1 3 】。这些局限性主要表现在： ( 1 ) 传统的搜索引擎的信息覆盖率不高。根据专家的评测，目前 主要搜索引擎返回的相关结果的比率不足4 5 ，同一个检索请求在不 同搜索引擎中的查询结果的重复率不足3 4 1 4 。 ( 2 ) 数据冗余度丈【5 】。 ( 3 ) 现有的搜索引擎各自使用不同的索引技术、信息收集技术和 关键词查询语法技术，给用户查询带来很大的不便旧。 因此，要想获得一个比较全面、准确的搜索结果，就必须反复调 用多个搜索引擎。元搜索引擎的出现，以及其各项相关技术的研究， 在一定程度上解决了这些问题 7 - 1 0 1 。 元搜索引擎是一种基于独立搜索引擎的搜索引擎，又称为多元搜 索引擎或集合式搜索引擎【u l 。元搜索引擎为用户提供统一的检索界 面，接收并处理用户的查询提问；然后根据一定的调度策略，选择调 用一个或多个独立搜索引擎进行查询；最后将来自独立搜索引擎的检 索结果收集起来，进行优化处理后，以一定的格式返回给用户。 元搜索引擎没有自己独立的数据采集机制和相应的数据库，它的 数据分析是建立在若干个成员搜索引擎返回的结果上的【1 2 1 。这样，通 中国石油大学( 华东) 硕士论文第l 章前言 过元搜索引擎，用户不必关心自己想检索的信息在哪个搜索引擎的文 档数据库中，元搜索引擎会自动遍历其整合的独立搜索引擎来查询信 息。同样，由于元搜索引擎的出现，也不需要把搜索引擎的负载设计 得很大，这样不仅积累了资金，而且提高了搜索引擎的性能【u 】。 在众多的搜索引擎中，如何选择贴近用户查询需求的成员搜索引 擎进行组合，以较小的资源耗费，帮助用户获得较高的查询质量，这 就是元搜索引擎的调度策略所研究的内容。元搜索引擎的调度策略是 元搜索引擎的关键技术，也是元搜索引擎研究的重要领域。实现智能 调度，可以根据成员搜索引擎的工作情况，动态地调度成员搜索引擎， 对于提高元搜索引擎的性能有很大的影响【1 4 】。 1 2 国内外研究现状 目前，元搜索引擎的研究、开发十分活跃。它主要用到了信息检 索、人工智能、数据库、数据挖掘、自然语言理解等领域的理论和技 术，具有综合性和挑战性。i n t e r a c t 上有很多元搜索引擎，它们在功能 实现上，各有侧重点。一些元搜索引擎在某些方面做得很好，但是在 其他功能上却存在着缺陷或尚需改进。元搜索引擎的功能受其自身技 术和成员搜索引擎搜索技术的双重制约f l5 】：一方面，独立搜索引擎各 具特色的强大功能在元搜索引擎中受到限制而不能充分体现；另一方 面，任何一种元搜索技术都不能发掘和利用独立搜索引擎的全部功 能。 元搜索引擎的调度策略一直是元搜索引擎研究的热点。元搜索引 擎下的每个成员搜索引擎都有自己的文本数据库，这些文本数据库由 一系列文档组成。元搜索引擎的调度策略就是为每个查询选择最可能 包含有用文档的成员搜索引擎，这对元搜索引擎的执行效率是至关重 2 中国石油大学( 华东) 硕士论文第1 章前言 要的。现有的搜索引擎调度技术有【1 6 】： ( 1 ) 朴素算法：这个方法没有衡量成员搜索引擎的有用性，用户 的查询请求被简单地送到每个成员搜索引擎上。当成员搜索引擎的数 量较大时，将查询送到每个成员搜索引擎的策略就不再合理了，因为 在这种情况下，大多数的成员搜索引擎对查询毫无用处，势必给元搜 索引擎带来大量不必要的通信资源的浪费。 ( 2 ) 定性的方法：根据一定的评分函数，针对给定的查询，预测 每个成员搜索引擎的质量，其评分或质量衡量往往不易理解。 ( 3 ) 定量的方法：根据一定的标准来衡量成员搜索引擎的有用 性，这些标准比定性方法使用的衡量标准更容易理解，也更加直接和 明晰。 ( 4 ) 基于学习的方法：根据各成员搜索引擎以往的经验来预测它 们对新查询的有用性。检索经验可能来自多方面：第一，可使用训练 查询。对于每个成员搜索引擎数据库关于训练查询的检索经验，可以 在搜索引擎数据库投入使用前得到，这类方法称为静态学习方法。在 此类学习方法中，检索经验一经学习得到就不再改变了。静态学习方 法的缺陷在于不能适应成员搜索引擎数据库内容和查询模式的改变。 第二，可使用真正的用户查询，检索经验可以逐步积累并持续更新， 这类方法称为动态学习方法。这种方法的问题在于需要一定时间才能 对搜索引擎数据库积累足够多的有用信息。第三，可使用静态学习和 动态学习相结合的方法。这类方法可以通过训练查询得到初始经验， 然后通过真正的查询不断更新知识。 目前用到的基于学习的调度策略主要有；s a 啊y s e a r c h 方法【1 7 1 ， p r o f u s i o n 方法【l8 】【1 9 1 ，还有张卫丰、徐宝文等提出的基于遗传算法的调 度策略脚l ，刘丽等提出的基于决策树归纳分类算法的调度策略1 2 “，李 中国石油大学( 华东) 硕士论文第1 章前言 鹏采用遗传算法改进决策树算法的调度策略【1 4 】，王津涛、兰皓等提出 的对遗传算法进行改进的调度策略【2 2 1 ，徐科、黄国景等提出的基于用 户兴趣的个性化调度模型【纠等。这些算法各有优缺点，但是对成员搜 索引擎查询性能的评价都不明确。鉴于此，本文查阅了大量文献，提 出了一种新的基于学习的调度策略。 1 3 论文研究内容 论文介绍了元搜索引擎的发展及现状，分析了影响元搜索引擎查 询性能的主要因素，并对其调度策略进行了深入研究。首先研究现有 的调度策略，分析其优缺点，找出其存在的不足；然后查阅文献资料， 找出解决这些不足的方法；最后提出了一种新的基于学习的元搜索引 擎调度策略，并设计了实验系统测试其性能，实验数据证明新的调度 策略有效地提高了元搜索引擎的查准率。 1 4 论文组织结构 论文分六章，其具体结构如下： 第l 章：阐述了课题的研究背景和国内外研究现状，介绍了论文 的主要研究内容，并给出了本文的组织结构。 第2 章：从元搜索引擎的定义及基本构成、分类、关键技术、主 要指标和发展趋势等五个方面详细地阐述了元搜索引擎的相关知识。 第3 章：介绍了元搜索引擎调度策略的相关研究，给出了几个比 较有代表性的各具特色的调度算法。 第4 章：提出了一种新的基于学习的元搜索引擎调度策略。 第5 章：设计实验系统对第四章提出的算法进行验证，并对实验 结果进行了分析。 第6 章：全文总结并展望未来的发展方向。 4 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 第2 章元搜索引擎概述 2 1 元搜索引擎的定义及基本构成 ( 1 ) 元搜索引擎定义 元搜索引擎是指在统一的用户查询界面和信息反馈形式下，共享 多个独立搜索引擎的资源库为用户提供信息资源检索的系统。被利用 的独立搜索引擎可称之为“源搜索引擎”，也称之为独立搜索引擎或 成员搜索引擎，本文称之为成员搜索引擎。严格地讲，元搜索引擎是 一个搜索代理程序，检索时，元搜索引擎根据用户提交的检索请求， 调用成员搜索引擎进行搜索，然后对检索结果进行汇集、去重、排列 等优化处理后，以统一格式在同一界面集中显示 2 4 1 。从检索机制的角 度看，元搜索引擎可以看作是一种分布式信息检索系统，由于具有检 索覆盖面广、系统复杂度不高等优点，元搜索引擎的研究发展非常迅 速。 ( 2 ) 元搜索引擎基本构成 与独立搜索引擎相比。元搜索引擎不需要维护庞大的索引数据 库，也不需要网络蜘蛛去采集网页。一个元搜索引擎主要由以下几部 分组成【2 5 】( 如图2 1 所示) ： 用户接口部件 用户接口部件是系统的用户界面，负责接收用户请求，并将用户 对系统界面的操作转换为系统标准请求。当搜索引擎管理器向它提供 整合好的搜索结果后，该模块负责输出系统的搜索结果。 搜索引擎管理器 搜索引擎管理器根据包含用户请求主题、地域情况的系统标准搜 索请求，向调度策略生成器请求本次搜索的调度策略。然后根据策略 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 生成连接请求，并对搜索引擎代理管理器的搜索结果提供缓冲管理和 信息整合功能。整合好的搜索信息一方面发送到用户接口部件；另一 方面作为搜索引擎工作记录交由调度策略生成器处理。 用 户 图2 - - 1 智能型元搜索引擎模型 搜索引擎代理管理器 搜索引擎代理管理器是若干个搜索引擎代理的综合。它把接收到 的连接请求转化为相应搜索引擎调用的本地化连接请求，激活相关引 擎工作。当接收到独立搜索引擎返回的搜索结果时，搜索引擎代理负 责页面分析和信息的初次过滤工作，并将处理后的结果送回搜索引擎 管理器。 调度策略生成器 调度策略生成器是体现系统智能化的主要模块。它负责实现搜索 引擎知识库的预处理功能，建立搜索引擎调度策略，对搜索引擎管理 器发送的本次搜索记录进行统计整理，以及根据数据挖掘的具体算法 修改下一次的搜索引擎调用策略。 6 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 2 2 元搜索引擎的分类 元搜索引擎有多种分类方式，如可以根据用户应用模式、调用独 立搜索引擎的方式等进行分类。我们根据图2 1 中各个部分的复杂 程度，将元搜索引擎分为简单元搜索引擎和复杂元搜索引擎，其中复 杂元搜索引擎又分为桌面型元搜索引擎和基于w e b 的元搜索引擎 2 0 3 。 ( 1 ) 简单元搜索引擎 简单元搜索引擎只是给用户提供一个搜索引擎列表，用户可以选 择所用的搜索引擎。用户输入查询请求，然后直接以c o l 方式调用对 应的搜索引擎。由于是由用户选择搜索引擎，而且查询请求只能发送 到一个搜索引擎，所以请求提交代理和检索接口代理的设计就非常简 单，可以直接设计在静态网页中。简单元搜索引擎不进行搜索结果的 处理，其在设计上的简单性，使之成为众多网站采用的提供搜索服务 的方法，如：f r e e a l i t y ( h t t p ：w w v f r e e a l i t y c o r n ) 提供的搜索服务。 ( 2 ) 桌面型元搜索引擎 桌面型元搜索引擎以程序的方式提供给用户。它运行在用户的机 器上，用户的查询请求直接由用户端分发给它所调用的搜索引擎，然 后对返回的搜索结果进行集成后再以一定的方式显示给用户。 ( 3 ) 基于w c b 的元搜索引擎 基于w e b 的元搜索引擎以w e b 方式为用户提供元搜索服务，搜 索引擎管理器、搜索引擎代理管理器和调度策略生成器都存放在元搜 索引擎所在的服务器端。这种方式中，用户的查询请求经过服务器端 将查询请求分发到它所调用的独立搜索引擎，这些独立搜索引擎返回 的结果经过处理后再呈现给用户。由于w e b 具有易用性的特点，基于 w e b 的元搜索引擎得到了更为广泛的应用。国外具有代表性的基于 w e b 的元搜索引擎有m e t a c r a w l e r ( h t t p ：w w w 9 0 2 n c t e o n g s e a r c h h t m l ) 、 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 s e a r c h e o m ( h t t p ：l l w w w s e a r c h e o m ) 、m a m m a ( h t t p ：w w w m a m m 丑c o m ) 、 c 4 0 a t t p ：w w w e 4 e o m ) 等。国内的中文元搜索引擎，代表性的有万纬 0 a t t p ：w w w w i d e w a y s e a r e h e o m ) ，b b m a o ( h t t p ：l l w w w b b m a o c o r n ) 等， 另外还有专业商业元搜索引擎h e n s o u ( h t t p ：w w w h e n s o u e o m ) 等。 2 3 元搜索引擎关键技术 元搜索引擎的关键技术主要有成员搜索引擎的调度技术，检索条 件转化技术和检索结果融合技术1 2 7 1 。 ( 1 ) 成员搜索引擎的调度 选择成员搜索引擎是元搜索引擎实现过程中需要解决的一个关 键问题。无论元搜索引擎如何优秀，它的性能都离不开它所调度的成 员搜索引擎的影响，对成员搜索引擎的调度策略已成为元搜索引擎的 主要研究领域之一。有关成员搜索引擎调度算法的分类方法也不统 一，通常可分为三大类：定性法，定量法和基于学习的方法。 具体介绍见第三章。 ( 2 ) 检索条件的转化技术 成员搜索引擎直接对用户的检索条件进行处理，不同的搜索引擎 有不同的语法和语义响应。元搜索引擎在进行检索请求分发前，需要 对用户的检索条件进行解析或翻译，分别转化为各成员搜索引擎能处 理的格式。检索条件转化的关键是要保证用户检索信息的不缺损，因 此，在可能丢失用户检索信息的成员搜索引擎上，常用的方法是对检 索请求进行扩充。 ( 3 ) 搜索结果的融合 结果信息的融合是元搜索引擎的核心问题之一，一个元搜索引擎 的性能很大程度上是由这一部分决定的。每个搜索引擎都会向元搜索 8 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 引擎返回一个检索结果列表，它们检索的标准和排序算法各不相同， 如何将所有搜索引擎的反馈结果整合成一个单一的结果列表，客观地 综合各搜索引擎的相关性评价，在最后结果中精确地体现相关性和重 要性，是非常复杂和值得研究的问题。 结果排序的典型算法有三种田】。 间隔排列合成法 首先把每个独立搜索引擎检索结果中的第一项交叉列出，后面的 结果依此类推。 分值合成法 如果可以得到文档的原始相关性分值，那么当这些分值可以直接 比较时，则可以采用原始分值合成法，即直接依据每个文档的原始相 关性分值决定其合成排列次序；如果文档的原始分值不能直接比较， 则可以采用规范分值合成法，即通过对其进行标准化来得到规范的相 关性分值，并以此作为依据确定文档的合成排列次序。 加权分值法 首先计算出各个检索结果相对于检索条件的重要性，再以此为权 值，乘上文档的相关性分值作为决定其合成排列次序的根据。 2 4 元搜索引擎的主要指标 作为一种搜索引擎。元搜索引擎也有搜索引擎的一些基本指标， 如响应速度、准确率等。但是元搜索引擎个体差异很大，很难进行精 确的比较。下面给出元搜索引擎的几个主要指标并对其中的一些指标 进行比较【2 9 】。 ( 1 ) 对独立搜索引擎的调度策略 有些元搜索引擎固定地调用几个独立搜索引擎，用户不能修改； 9 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 有些元搜索引擎的高级特性中让用户选择调用哪些独立搜索引擎。这 种方式对于那些对独立搜索引擎比较了解的用户来说，是可取的，而 对于不了解的用户来说，可能选择不到适合自己查询的搜索引擎。独 立搜索引擎的各种技术飞速发展，性能也随之不断地提高，元搜索引 擎只能选择几个( 一般不超过1 6 个) 搜索引擎同时进行检索，因为选 择的搜索引擎越多，固然得到的搜索结果更全面，但是结果的集成花 费的时问也越多。元搜索引擎如果一直固定地调用几个搜索引擎，将 可能跟不上搜索引擎的发展潮流。 ( 2 ) 覆盖网络资源的广度 元搜索引擎由于不需要建立自己的索引，避免了大量信息的存储 和处理。一般的元搜索引擎都尽量地覆盖多种网络资源。有些元搜索 引擎还支持更加专业的搜索引擎，比如m p 3 、各种专业的论文查找、 健康医药查找等搜索引擎。 ( 3 ) 是否提供足够的检索选项 包括是否提供高级检索服务，是否可以限定最长检索时间，是否 可以设置每个搜索引擎返回的结果数量，是否可以设置每页显示的结 果数目，是否可以设置标题大小( 搜索引擎可以从t i t l e 标记中显示的 最大字符数) 和摘要大小( 搜索引擎所显示的结果中摘要的最大字符 数) ，是否提供显示选项( 用户可以通过它来设置结果的其它显示方 式，如只显示标题、按照时间排序等) 等。检索选项越多，用户使用 的时候就越灵活。但是由于元搜索引擎的检索特性向它所调用的独立 搜索引擎检索特性转换所具有的复杂性，许多元搜索引擎不提供复杂 的检索选项。大多数元搜索引擎提供通用的布尔检索，而对于如高级 布尔检索、短语检索、自然语言检索等高级特性则只有少数几个元搜 索引擎能够提供，如d a t a w a r e 和i x q u i c k 等。 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 ( 4 ) 对搜索结果的处理能力 对独立搜索引擎返回的搜索结果进行处理是元搜索引擎的又一 重要技术，它包括结果的处理和结果的显示。有些元搜索引擎提供多 种显示结果的方式，如国内第一个元搜索引擎一万纬搜索，用户可 以选择按照时间、按照搜索引擎或者按照相关度等来排序。有些元搜 索引擎提供了让用户定制搜索结果的聚类方式，如按照域名聚类、按 照主题分类等。 ( 5 ) 相关度指标 每个搜索引擎开发商为了将最满意的结果放到前面，不遗余力地 创建出各种相关度指标体系，从检索词的位置频率到链接和流行度 等等。虽然没有一种方法是完美的，但都有创叛和独到之处。面对这 些众多的相关度评价指标，按照怎样的方式对独立搜索返回的结果进 行一致性的排序，是元搜索引擎结果处理部分面临的主要问题。元搜 索引擎的结果排序有多种方法，有根据搜索结果在成员搜索引擎中的 位置进行排序的方法，有根据搜索结果的摘要信息进行排序的方法， 还有的干脆获取这些网页，然后按照位置频率法对搜索结果进行一 致性排序。i x q u i c k 在肯定各个独立搜索引擎所用的相关度指标的基础 上，通过统计搜索结果记录被多少个独立搜索引擎所青睬，作为元搜 索结果相关度评价指标，简称“星星体系”( 如果在一个搜索引擎的 前几条记录中出现，就得一个星，得到的星越多，则该记录越重要) 。 2 5 元搜索引擎的发展趋势 未来的元搜索引擎应该在以下方面有所突破【3 0 】： ( 1 ) 自然语言，精度更高 自然语言的输入将更加方便用户的使用，更易于用户与搜索引擎 中国石油大学( 华东) 硕士论文第2 章元搜索引擎概述 之间的交互。自然语言更能贴切地表达用户的查询需求，从而有利于 提高查询的精度。 ( 2 ) 多种语言搜索 元搜索引擎可以充分利用在搜索预处理方面的优势，按照语言的 不同将用户的查询请求发送到对应语言的独立搜索引擎，以提供多语 言的搜索功能。 ( 3 ) 善解人意，学习个人喜好 元搜索引擎通过不断地学习，来掌握用户的喜好。通过对用户搜 索习惯、用户兴趣的掌握，达到自动选择合适的独立搜索引擎的效果， 从而改进搜索结果。 ( 4 ) 多通道输入 元搜索引擎应该利用其在搜索预处理上的能力，对于用户输入的 查询，如声音、图象、视频等，实现查询的转换功能，从而得到预想 的结果。 ( 5 ) 个性化和本地化 未来的元搜索引擎应该充分发挥搜索预处理和搜索结果集成方面 的能力，考虑人的性别、年龄、地域等方面的差别，给出个性化的搜 索结果。 2 6 本章小结 本章概述了元搜索引擎的相关知识，主要介绍了元搜索引擎的定 义和基本构成、元搜索引擎的分类，分析了元搜索引擎的关键技术， 探讨了元搜索引擎的主要指标，并给出了未来的元搜索引擎的发展趋 势。 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 第3 章元搜索引擎调度策略的相关研究 选择成员搜索引擎是元搜索引擎实现过程中需要解决的一个关 键问题，而成员搜索引擎调度算法的分类方法也不统一。通常可分为 三大类：定性法，定量法，基于学习法。 3 1 定性法 定性法根据一定的评分标准，针对给定查询预测每个成员搜索引 擎数据库的性能。其评分或性能衡量往往不易理解。有些定性法只能 用很粗略的信息来代表每个成员搜索引擘的内容。通常，这些信息只 有几个关键字和几个句子。使用粗略信息的好处在于这些信息比较容 易获得而且只需要很少的存储空闻，但是它的缺点是不容易把单个成 员搜索引擎的性能描述清楚。较新的定性方法采用非常详细的信息， 描述了每一个成员搜索引擎数据库的性能。下面介绍一种该类方法。 在c o r in e t ( c o l l e c t i o nr e t r i e v a li n f e r e n c en 前哟r b 方法【3 i l 中，每个 成员搜索引擎数据库的描述信息包括了其所有术语的两个信息：文件 频率和数据库频率。前者是指在某个成员搜索引擎数据库中含有该术 语的文件个数，后者是指含有该术语的成员搜索引擎数据库的个数。 对于给定查询q ，c o r in e t 将一种在i n q u e r y 系统中被称为 i n f e r e n c en e t w o r k 的文件评估法经拓展后用于计算成员搜索引擎数据 库关于q 的评分。这种延展主要是概念上的，其思想是将一个成员搜 索引擎数据库代表想象为一个含有该数据库的所有术语的超级文件。 数据库中术语的文件频率成为超级文件中术语的术语频率。假设d 表 示这个所有超级文件的数据库，术语的数据库频率在d 中成为该术语 的文件频率。因此，从成员搜索引擎数据库代表信息中，便可以得到 每个术语文件的术语频率和文件频率。公式 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 铲idf(3-1) 可以用来计算每个超级文件中术语的权值，以便将每个超级文件用权 值向量来表示，其中西是根据术语频率计算出来的权值因子，而i d f 是根据文件频率计算出来的权值因子。通常廿是术语频率的增函数， i d f 是文件频率的减函数。c o r in e t 使用的是一种基于i n f e r e n c e n e t w o r k 的概率论方法。由于在c o r jn e t 中，每个术语的数据库代表 信息稍稍多于一个数据量( 即文件频率加上所有数据库共享的数据库 频率) ，因此，c o r in e t 方法具有较好的扩展性，获得或维护代表每 个成员数据库内的信息也很容易。c o r i n e t 的一个优点是其计算文件 对于查询系统的一套评分方法可以同样( 通过数据库代表信息或超级 文件) 用于计算数据库对于查询的评分。 3 2 定量法 定量法根据给的定查询计算出成员搜索引擎数据库的有用性，其 计算方法相对于定性方法而言更加直接和明晰。举例来说，定量方法 使用的衡量成员搜索引擎数据库有用性的一种标准是“成员搜索引擎 数据库中对于每一个查询潜在的有用文件的数量”，很明显，这个数 量清楚的反映了该成员搜索引擎数据库对于给定查询的有用性。 另外一种有用的定量衡量标准是：一个成员搜索引擎数据库中与 给定查询最为相似的文件的全局相似度。一方面，该标准表明了能够 从一个成员搜索引擎数据库中可得到最好的结果是什么；另一方面， 对于给定的查询，该标准可以用来最优化地对成员搜索引擎数据库进 行排序，进而从所有成员搜索引擎数据库中检索得到最相似的m 个文 件。 1 4 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 3 3 基于学习法 基于学习法根据以往提交的查询中得到的检索经验来预测成员 搜索引擎数据库对于新查询的有用程度。检索经验可能来自多方面。 第一，可使用训练查询。对于每个成员搜索引擎数据库关于训练查询 的检索经验可以在搜索引擎数据库选择投入使用前得到。因为在此类 学习方法中，检索经验一经学习得到就不再改变了，所以这类方法称 为静态学习方法。静态学习方法的缺陷在于不能适应成员搜索引擎数 据库内容和查询模式的改变。第二，可使用真正的用户查询，检索经 验可以逐步积累并持续更新，这类方法称为动态学习方法。这种方法 的问题在于需要一定时间才能积累对搜索引擎数据库足够有用的信 息。第三，可使用静态学习和动态学习结合的方法，又叫混合学习法。 这类方法可以通过训练查询得到初始经验，然后通过真实查询不断更 新知识。混合学习可以克服另外两种方法的弱点。下面介绍几种比较 著名且各有特色的基于学习的调度算法。 3 3 1s a v v y s e a r c h 方法 s a v v y s e a r c h 方法【1 刀中成员搜索引擎关于一个查询的评分是根据 查询中的术语在以前查询中获得的知识来得到的。更具体的说，元搜 索引擎数据库选择程序对于每一个成员搜索引擎都维护一个权值向 量( w l , w 2 ，w m ) ，其中w t 对应于该搜索引擎数据库第i 个术语。所有权 值初始值都为0 。当一个含有术语 的查询用来从一个成员搜索引擎数 据库检索文件时，该成员搜索引擎权值向量中对应于 的值将根据检索 结果来调整。如果搜索引擎没有返回文件，权值下降1 k ，k 是查询中 术语的数量；如果用户阅读点击了至少一个返回文件，权值则增加1 k 。 直观的看，一个较大的正数晰，表示术语，f 在以往的检索中从该成员搜 索引擎中得到很好的响应，而一个较大的负数w f ，则表示术语 从该成 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 员搜索引擎中得到的响应不好。 s a v v y s e a r c h 也跟踪了每个成员搜索引擎的最近表现情况，它跟踪 最近五个查询返回文件的平均个数h 和最近5 个查询提交到成员搜索 引擎所需要的平均时间r ，如果h 在临界值t h ( 默认值为1 ) 以下，则 对于该成员引擎的一个惩罚为 p h 娟i d z t h 2 ( 3 2 ) 相似的，如果平均响应时间大于临界值t ，( 默认时间为1 5 秒) ， 则惩罚为 p r = ( r - t r ) 2 ( r o t ( 3 3 ) r o ( 默认为4 5 s ) 是可以被接受的最大响应时间，t r r o 被视为超 时对于一个新的查询q ，含有术语t l , t 2 ，t k ，成员搜索引擎数据库d 的评价分值为 i s ( q ，d ) = ( w j xl o g n f , ) i f f i l 一( a + n ) ( 3 - 4 ) 其中，z o g ( n f 0 是术语卉的反成员搜索引擎数据库频率权值，n 是 成员搜索引擎总数，石是对于t t 有正数权值的成员搜索引擎总数。 s a v v y s e a r c h 的一个弱点是对于新出现的查询术语或不常用的查 询术语的检索效果不好。此外，搜索引擎用户有点击排名靠在前面的 文件的倾向，这意味着搜索引擎数据库信息中代表术语的权值可能会 被一种与该权值所表示含义不一致的方式轻易改变，其结果很有可能 出现搜索引擎数据库的术语权值不能充分反映数据库对于该查询术 语的真实响应。 3 3 2p r o f u s j o n 方法 在p r o f u s i o n 方法f 1 9 1 中，1 3 个预先设置的类别被用于学习过程。 每一个类别有一组反映该类别主题的术语。对于每一个类别，一组训 1 6 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 练查询将用来做静态学习。使用这些类别以及专门的训练查询的原因 是为了了解不同成员搜索引擎对于不同类别的响应情况。对于给定类 别c 和给定的成员搜索引擎数据库d ，每个相关的训练查询都提交给 d 。从排名最前的1 0 个检索文件中识别出相关文件，然后，一个反映 d 对于该查询和该类别表现的评分值可以由如下公式得到； 1 0 c m 1 0 r i o 括】 ( 3 5 ) 其中c 是一个常数。如果排名第i 的文件是相关文件，m 被设为 1 i 如果无关，m 被设为o 。r 是1 0 个返回文件中相关文件的总数。 最后，类别c 的所有训练查询在数据库d 得到评分的平均值被作为该 数据对于类别c 的信任因数。训练完成以后，每个数据库对于每个类 别都有一个信任因数。 当元搜索引擎收到用户查询q 时，q 被首先对应到一个或多个类 别。如果与类别c 相关的一组术语中至少有一个术语出现在q 中，q 便被对应到该类别。然后，各搜索引擎数据库按照对应的类别中的信 任因数之和来排序。一个搜索引擎数据库对于q 的信任因数值之和为 搜索引擎数据库对于q 的评分。得到最大评分值的三个搜索引擎数据 库将用来对查询q 进行检索。 p r o f u s i o n 中，从被选择的成员搜索引擎中检索回来的文件使用 成员搜索引擎数据库评分和文件的局部相似度的乘积来进行排序。假 设成员搜索引擎数据库d 中的文件d 是第一个被用户阅读的文件，如 果d 不是排名最靠前的文件，那么d 的评分就应该增加，而同时应该 降低那些排名在d 前的文件的数据库的评分。这可以通过按比例调整 有关成员搜索引擎数据库的相关类别的信任因数来进行。信任因数调 整原则是：有助于将来再遇到同样查询时，将d 的排名提高。使用该 1 7 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 原则的原因是：如果评分是正确的话，那么排名最高的文件应该被用 户首先阅读。 p r o f u s i o n 将静态学习和动态学习结合了起来，这样做的结果解决 了一些与单一使用静态学习方法或单一使用动态引擎方法相关的问 题。 3 3 3 基于遗传算法的搜索引擎调度策略 基于遗传算法的搜索引擎调度策叫驯的基本思想是通过模拟生 物的进化过程来实现对成员搜索引擎的选择。 ( 1 ) 编码方法 将整个搜索空间t 分为不同的领域，表示为t _ i t l , t 2 ，口每个领域 由一个或者多个智能代理a g e n c 【3 2 】为其服务，每个a g 即t 运行时使用若干 个搜索引擎。 ( 2 ) 适应函数和选择 将搜索引擎e 的性能表示为五元组( 厦d ，p ，c ，“，f ) ， 各函数分别表示e 的领域分布集、搜索精度、搜索完全度、平均响应 时间和更新时间。 定义相关搜索引擎集r s e ( sf i e l d ) 为所有与s e l d 的相关度大于m 的搜索引擎的集合。即： r s e ( s _ f i e l d ) = e i 垆佴s _ f i l e d ) m , s _ f l l e d t )( 3 6 ) 其中，妒( es f i e l d ) 为聚集函数；m 为阀值，它的值越大，得到的 相关搜索引擎集合与领域s _ f i e l d 的相关性越大，但是如果m 取得太大， 则将使得该领域可选搜索引擎大大减少。管理员可以根据需要动态调 整m 的值。 设智能代理删由一个搜索引擎序列( 蜀。点k ，剐组成。智能代 理：a g e n t l 的领域分布集何以表示为构成该智能代理的搜索引擎的领 l s 中国石油大学( 华东) 硕士论文第3 章元搜索引擎调度策略的相关研究 域分布集的并，即 p ( a g e n ) u = m a x ( u ( e l o ，氓蚴卜t ( e a ，最b ，) ) ( 3 7 ) 其中t ( 晶，e i t , ，) 为智能代理处理搜索引擎勘，e b ，疡 返回结果所用的平均时间，它是所用搜索引擎及搜索引擎个数( 在这 里为z ) 的函数，z 的取值对亍影响较大。智能代理昭p 埔的整体更新时 间可以用其下搜索引擎的最近更新时间来表示，即 p ( a g e n “) t = m a x ( t ( e a ) ，t ( e f ) ) ( 3 8 ) 定义智能代瑶a a g e n t i 与领域集s 多e l d 的相关度为 r e a ( a g e n t ，, sf i e l d ) = 烈e ，j f i l e d ) ( 3 9 ) 占e 昭p 哪 由以上这些定义，适应函数可以设置为 o ( a g e n t j ) = f ( ，p ，c ，t ) ( 3 1 0 ) r 为比例变换函数，p ，c ，越，t 为智能代理a g e n t j 的性能指标。 当前的所有智能代理可以构成规模为阅仑1 ) 的父辈种群。为简便 起见，在不引起混淆的情况下，我们用a g e n 矗( t ) 表示在进化代t ( t - 2 0 ) 所生成的第i 5 智能代理。从而，在进化代t 眨o ) ，种群p ( 1 ) 可以表示为 a g e n t t ( t ) ，a g e n g ( o 。父辈种群通过遗传操作产生规模为m 砭1 ) 的 子代种群，即每一代通过重组和变异产生的智能代理数。从这个子代 种群中选择u 个智能代理作为下一代的父辈种群。选择是按照如下概 率分布选取u 个智能代理： 船嘶( 妒