（计算机应用技术专业论文）基于机器学习的用户个性化元搜索引擎的研究.pdf

摘要 于两斐 随着网络资源的进一步丰富，原本就为网络查询而生的搜索引擎表现出了它 不足的一面。搜索引擎覆盖范围相对减少；访问不均衡；内容陈旧；元数据使用 较少；信息分布不平衡等等。 所以元搜索引擎应运而生，至今已获得了极大的发展，但仍有其自身的不足。 比如：用户友好性差，适应性不高和缺乏针对性等等。本文就是为解决这些问题 而进行的研究。 对用户的输入确定分类内容，从而选择搜索引擎。由于各个成员搜索引擎有 各自专长的领域，针对某一方面的查询，应选择调用该领域查询性能较好的成员 搜索引擎，动态调用成员搜索引擎。同时，选择的依据包含用户的个人信息以及 搜索历史。在执行搜索后，保留搜索引擎的执行效率，作为下次搜索引擎选择的 参考依据之一。 选择搜索引擎使用改进的遗传算法，以搜索引擎的集合智能代理为染色体， 让它在重组，变异之后通过对搜索引擎的评价得出最优基因，并赋值给每个智能 代理的第一个搜索引擎，这样就保证了系统向着正确的方向进化。另一方面，把 搜索引擎以x m l 文件描述的形式保存，以便于搜索引擎成员的添加等行为。 在用户个性化方面，采用了r d f 表示用户偏好，然后通过用户偏好的压缩和 优化，合并成用户聚类，形成用户向量中心，以推测用户的爱好。需要说明的是 用户偏好文件所表达的用户偏好需要有一点的概括力，过分具体的用户偏好，不 利于推测；另一方面，用户偏好文件所表达的用户偏好需要有一定的具体性，不 能过分概括而失去了实际意义。而搜索结果的按名聚类，使得构建有效地偏好库 成为可能。 最后，本文提出了一个完整的元搜索引擎模型。以后的工作将围绕着算法的 验证和模型的丰富而进行。 关键词元搜索引擎：遗传算法；用户个性化；用户偏好 a b s t r a c t a b s t r a c t t h es e a r c he n g i n e sw h i c hb o r nf o rq u e r ys h o wt h el a c ko fa b i l i t yw h e nt h e r ea r e v e r yl a r g ew e br e s o u r c e t h el o wc o v e r ；v i s i tu n e v e n ；t h ec o n t e n t sa r en o tf r e s h ；l e s s m e t a d a t a ；u n e v e nd i s t r i b u t i o na n ds oo n a n ds om e t a - s e a r c he n g i n ea p p e a r sa n dg e tav e r yb i gi m p r o v e ，b u ti ts t i l lh a s o w nd i s a d v a n t a g e s ，l i k ep o o ru s e r - f r i e n d l y , a d a p t i v ei sn o tg o o d ，a n dt h el a c ko f s p e c i f i c i t ya n ds oo n i nt h i sp a p e r , t h e r ei sas u m m a r ya n dc o m p a r eo ft h ee x i s t t h e o r i e s ，w h i c hd oaf a v o rf o rt h ew o r ki nt h ef u t u r e t h i sp a p e rw o r k e dt os o l v et h e s e p r o b l e m s s e l e c tt h es e a r c h i n ge n g i n ea c c o r d i n gt ot h eu s e r s i n p u t a g a i n s tt h es e a r c h i n gi n o n es p e c i f i cf i e l d ，w es h o u l ds e l e c tt h eb e s tm e m b e rs e a r c h i n ge n g i n ei nt h a tf i e l d ， b e c a u s ee a c hm e m b e rs e a r c h i n ge n g i n eh a si t so w ns p e c i a l t y t h a ti sd y n a m i c m e m b e rs e a r c h i n ge n g i n es e l e c t i n g m e a n w h i l e ，i tw i l lc o n s i d e rp e r s o n a l i n f o r m a t i o na n ds e a r c h i n gh i s t o r y a f t e rs e a r c h i n ge x e c u t i n g ，i tw i l lp r e s e r v e e x e c u t i n ge f f i c i e n c yo ft h es e a r c h i n ge n g i n ea so n eo ft h ei m p o r t a n tr e f e r e n c ef o r t h e n e x tt i m e it a k et h ei n t e l l i g e n ta g e n ta sc h r o m o s o m e ，a n da f t e rt h er e f o r ma n dt h ev a r i a t i o n ， t h e ng i v eae v a l u a t i o nt h a tw h i c hi st h eb e s tg e n e ，a n da s s i g nt h eb e s tg e n et ot h e f i r s ts e a r c he n g i n ei ne v e r yi n t e l l i g e n ta g e n t ，w h i c hi n s u r et h es y s t e me v o l v e st ot h e c o r r e c td i r e c t i o n i na n o t h e rs i d e ，is a v et h es e a r c he n g i n e si n f o r m a t i o ni nt h et y p e o fx m lf i l e ，w h i c ha r ee a s yt oa d da n dr e m o v et h em e m b e r s i nt h ea s p e c to fi m p l e m e n t a t i o n , i tu s e sr d ft or e p r e s e n tt h eu s e r s p r e f e r e n c e a n dc o m b i n et h eu s e r s p r e f e r e n c et ou s e rc l u s t e rt of o r mu s e rv e c t o rc e n t e rb y c o m p r e s s i o na n do p t i m i z a t i o n o no n eh a n d ，t h ee x p r e s s i o no fu s e r s p r e f e r e n c ef i l e s h o u l db eal i t t l eg e n e r a l ，i ft o od e f i n i t e ，i ti sn o te a s yf o rs p e c u l a t i n g ；o nt h eo t h e r h a n d ，i ts h o u l db eal i t t l ed e f i n i t e ，i ft o og e n e r a l ，i tm a yl o s et h er e a lm e a n i n g t h e n a m ec l u s t e ro fs e a r c h i n gr e s u l t sm a k e st h ec r e a t i o no fe f f e c t i v ep r e f e r e n c el i b r a r y p o s s i b l e a tl a s t ，ip r o v i d e dam e t a - s e a r c he n g i n em o d e lw i t hc o m p l e t ef u n c t i o n s ，a n dt o a u t h e n t i c a t et h ec o r r e c t n e s so ft h ea l g o r i t h ma n de n r i c ht h em e t a s e a r c hm o d e l b e c o m et h em a i n w o r ki nt h ef u t u r e k e yw o r d sm e t a - s e a r c he n g i n e ；u s e rp e r s o n a l i z e d ；m a c h i n el e a r n i n g 1 1 1 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：j 亟盘螫日期：鲨盟车三日 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：塑：查兰垦鲁师签名： i u 第1 章绪论 1 1 研究背景 第1 章绪论 人们在应用网络资源时，希望尽可能在短时间内获得有用的信息。如何从海 量w e b 信息中快速获取有用的信息，是目前w e b 信息获取研究的重点。基于 w e b 的信息获取包括两个方面内容：信息搜索和信息抽取。w e b 文本信息搜索 是指查找与查询条件相关的w e b 文本。搜索引擎无疑是信息搜索的有利工具， 搜索引擎通过收集众多的网络站点来提供全局性网络资源控制与检索机制，从而 帮助用户方便地在网络中找到所需信息。目前在i n t e r n e t 上己经出现了很多著名 的拥有很高访问量的搜索引擎站点，例如g o o g l e ， y a h o o ，a l t a v i s t a ，e x c i t e 熊 寸o 搜索引擎一般由一个称为“机器人或“蜘蛛”或“爬虫 的软件a g e n t 以 某种方式自动地在互联网中搜集和发现信息，由索引器为搜集到的信息建立索 引，由用户界面根据用户的查询输入检索索引库并将结果返回给用户。搜索引擎 总是使用“蜘蛛 严密搜索互联网以寻找文件和它们的网址，被搜集到文件及其 网址则被送给搜索引擎的索引器。索引器从文件中摘录一些信息并将它存入数据 库。选取索引信息取决于特定的搜索引擎，一些搜索引擎索引文件中的每个词： 另一些则仅仅索引文件标题。当用户输入关键词执行搜索时，搜索引擎就会在数 据库中搜索与用户查询相匹配的文件，并编辑出可作为超文本链接的结果。 l a w r e n c e 和g i l e s 在1 9 9 9 年对当前w e b 上的搜索引擎做了研究，提出当前 搜索引擎存在的五个普遍问题： ( 1 ) 搜索引擎覆盖范围相对减少：搜索引擎的索引能力正在越来越落后于网 络的快速增长速度。自1 9 9 7 年1 2 月以来，搜索引擎的覆盖面相对于网络上公开 的可检索的内容实际上是减少了。据估计网络中有超过8 亿个可索引的网页，大 约1 5 t b 的信息量。然而，没有一个单个的搜索引擎能涵盖多于网上全部可检索 页的1 6 。 ( 2 ) 访问不均衡：w e b 搜索引擎检索到w e b 中的某个偏爱的网站页后，搜索 引擎或跟随其链接( 9 0u r l ) ，或通过分析用户注册发现新页。他们通常更喜欢检 索与其有更多链接的站点( 更“流行 的站点) 。如，美国站点与非美国站点相比， 他们更可能检索美国站点( a l t a v i s t a 例外) ，教育站点与商业站点相比，他们更可 能检索商业站点。 ( 3 ) 内容陈旧：各搜索引擎检索到的文件有时是不再有效的，因为网页已被 移至别处或不再存在。调查发现，几个不同搜索引擎检索到的第一个文件在网上 北京工业大学工学硕士学位论文 存在的平均时间是1 8 6 天。 ( 4 ) 元数据使用较少：许多搜索引擎是基于网页中定义了的元数据来索引网 络信息。然而，简单的h t m l “关键词 和元标签“描述”仅仅在3 4 的网站 主页上被使用。使用d u b l i nc o r e 元数据标准的站点更是微乎其微，仅仅只有0 3 。 ( 5 ) 信息分布不平衡：网上信息分布是不平衡的。有8 3 网站包含商业的内 容，只有6 的网站包含科学或教育的内容。 元搜索引擎是建立在己有的搜索引擎服务之上的一种搜索引擎，它利用下层 多个搜索引擎提供的服务向上提供统一的检索服务，自身不采集文件，也没有索 引，只是维护它所管理的搜索引擎的参数信息，如每个引擎的查询参数、引擎的 内容表示。当一个查询到来时，元搜索引擎自身并不处理( 这只是一种简单的情 况) ，而是按照各个成员引擎的查询格式作相应的转换之后再分发到各个成员引 擎，有关成员引擎的参数信息可以帮助元搜索引擎进行引擎的选择和协调，各个 成员引擎返回结果之后，元引擎进行结果合并形成按全局权重排序的序列输出给 用户。之所以要开发元搜索引擎，主要的理由是：( 1 ) 增加w e b 网页检索的覆盖 范围。如果将多个搜索引擎组合在一起，可查询的互联网覆盖范围面将比任何单 个搜索引擎都大很多。( 2 ) 元搜索具有较好的扩展性；它使得各个成员引擎规模 变小，性能更好，这样成员引擎的检索响应时间短，还可以使得检索的内容保持 最新。( 3 ) 提高检索的有效性。因为参考了多了独立搜索引擎的结果，使得元搜 索引擎的结果更具中立性，更有权威。同时，经过对用户个性特征的考虑，使得 结果更具参考性。所以，使用元搜索引擎可获得比综合性引擎更好的结果。 1 2 本文的主要工作 现在元搜索引擎并没有彻底的解决问题，它只是通过信息的整合增加了信息 容量，并没有解决准确度差的问题，对于性能也没有太好的提升。针对这种情况， 从搜索引擎的选取，到结果选取，乃至内容整合方面，本文都提出了一整套独特 的方法来解决这些问题。 1 对用户的出入确定分类内容，从而选择搜索引擎。由于各个成员搜索引 擎有各自专长的领域，针对某一方面的查询，应选择调用该领域查询性 能较好的成员搜索引擎，动态调用成员搜索引擎。同时，选择的依据包 含用户的个人信息以及搜索历史。在执行搜索后，保留搜索引擎的执行 效率，作为下次搜索引擎选择的参考依据之一。 2 对用户的输入进行辨别分析，给出相似的关键词，确定最接近用户本意 的最精确关键字，发往不同的已选定搜索引擎，以期获得最优结果。 2 第1 章绪论 3 对各个独立搜索引擎返回的结果进行分析处理，剔除重复的链接，无效 的链接，广告页和陈旧网页，留下有效地信息留待处理。 4 针对不同用户，给不同的搜索引擎以不同的权值，通过排序算法确定最 终结果，将不同引擎的结果进行同一格式处理后返回给用户。 5 对用户的满意度进行采集，保留和学习用户的个性，更新搜索引擎库和 兴趣库。 1 3 论文内容的组织 本论文是对作者所做工作的总结。概要论述了元搜索引擎的发展现状和元搜 索技术中的关键问题和相关算法，提出了一种基于机器学习的元搜索引擎的模 型。全文共分为六章，组织结构如下： 第一章介绍了论文的背景和所作工作及论文内容的组织。 第二章概述了元搜索引擎的基本原理，分类，它与独立搜索引擎及分布式搜 索的区别，评价指标和发展情况。 第三章介绍了成员搜索引擎的选择策略和文档选择技术。 第四章对检索结果的融合和排序进行了研究，给出了一个有效的排序算法。 第五章介绍了一个元搜索引擎的设计模型，给出了主要的算法。 最后，对本文工作的阶段总结并对今后工作进行展望。 3 第2 章元搜索引擎概述 第2 章元搜索引擎概述 据信，一个单一搜索引擎的网络覆盖率最多只能覆盖到整个i n t e m e t 资源的 3 0 5 0 【2 1 ，因而查全率便无法保障；再加上任何搜索引擎的设计，均有其特定的 数据库索引范围、独特的功能和使用方法，以及预期的用户群指向，导致同一个 搜索请求，在不同搜索引擎中查询结果的重复率不足3 4 嘲，因而查准率亦无法 保证；因此，要想获得一个比较全面、准确的结果，就必须反复调用多个搜索引 擎，并对返回结果进行比较、筛选和相互印证。元搜索引擎便应运而生。 2 1 搜索引擎定义及基本原理 特殊的存储方式使w e b 成为人们实现对跨越时间和空间界限的信息访问的 有力载体，而其信息的海量、异构、动态且无限增长而引起“信息丰富，知识馈 乏的尴尬局面，也使人们认识到必须选择一种合适的方式来实现对w e b 信息 的有效获取和访问。作为一种信息检索技术，搜索引擎成为人们关注并寄以厚望 的对象。搜索引擎是指一种在w e b 上的应用的软件系统，它以一定的策略在w e b 上搜集和发现信息在对信息进行处理和组织后，为用户提供w e b 信息的查询 服务。按其工作方式，一般可分为：目录搜索引擎，全文检索搜索引擎以及元搜 索引擎“1 。通常目录搜索引擎和全文检索搜索引擎也统称为独立搜索引擎。所谓 目录搜索引擎是指依赖人工整理的网站分类目录。对于该类搜索引擎而言，用户 不仅可以通过目录导航来直接定位网页，而且可以利用检索系统中的自动导航功 能，实现对潜在有用网页的定位。如y a h o o 、搜狐和在线m s d n 等。所谓全文 检索搜索引擎，也称机器人搜索引擎，是指利用一定的机制收集、索引以及搜索 w e b 网页，并以一定的方式保存在后台数据库中，供用户访问。如g o o g l e 和百 度等。 元搜索引擎( m e t as e a r c he n g i n e 简称m s e ) ，是一种建立在独立搜索引擎 基础上，调用其它独立搜索引擎的引擎，亦称”搜索引擎之母( t h em o t h e ro f s e a r c h e n g i n e s ) ”。在这里，”元( m e t a ) 为”总的”、”超越”之意，元搜索引擎就是对多 个独立搜索引擎的整合、调用、控制和优化利用。相对于元搜索引擎，可被利用 的独立搜索引擎称为”源搜索引擎”( s o u r c es e a r c he n g i n e ) ，或”成员搜索引擎” ( c o m p o n e n ts e a r c he n g i n e ) 。从功能上来讲，元搜索引擎像是一个过滤通道： 以多个独立搜索引擎的输出结果作为输入，经过一番提取、剔除、萃取等优化处 理，并以统一的格式呈现给用户。其工作原理可归纳为嘲： ( 1 ) 接受用户提交检索请求。用户通过统一的访问界面提交检索请求； 5 北京工业大学工学硕士学位论文 ( 2 ) 检索请求转换。把用户输入的原始检索请求分别转换为各个搜索引擎能 够接受的形式： ( 3 ) 分发检索请求。将转换后的检索请求分发给各个独立搜索引擎； ( 4 ) 收集检索结果。将各个独立搜索引擎返回的检索结果收集起来； ( 5 ) 检索结果整合。对各个独立搜索引擎返回的结果进行整合，形成最终结 果； ( 6 ) 把检索结果返回给用户。将整合后得检索结果以统一的形式返回给用户。 2 2 元搜索引擎分类 元搜索引擎按照其调用成员搜索引擎的方式分类1 ，可分为串行元搜索引擎 和并行元搜索引擎。所谓串行元搜索引擎就是将用户的查询提交给某个成员搜索 引擎，待该成员搜索引擎返回结果后再对另外一个成员搜索引擎进行查询，这样 查询时间为所有成员搜索引擎查询时间的总和。而并行元搜索引擎是指各个成员 搜索引擎并发进行查询。 元搜索引擎按运行方式的差异可分为在线搜索引擎和桌面搜索引擎。【8 】通 过网上调用方式在线使用的元搜索引擎称之为在线元搜索引擎，与它相对应的另 一类元搜索引擎可直接在用户计算机上运行，相当于用户自己拥有一个元搜索引 擎，称之为桌面元搜索引擎。桌面元搜索引擎是一个包括多个成员搜索引擎的完 整系统，它们往往允许用户自定义检索运行的搜索引擎集合，甚至可由用户添加 新的搜索引擎。 元搜索引擎按功能划分，可分为多线索式搜索引擎和a 1 1 i n o n e 式搜索引 擎口1 。下面详细介绍一下： 2 2 1 多线索式元搜索引擎 多线索式元搜索引擎，指利用统一的检索界面，实现对多个独立搜索引擎的 索引数据库进行检索，并将检索结果以统一格式显示的网络检索工具。 多线索式元搜索引擎一般具有以下特征： ( 1 ) 统一检索界面提供统一界面，提供对各搜索引擎的特点介绍和选择机制， 但所有目标源搜索引擎构成一个逻辑整体，元搜索引擎检索界面构成唯一的全局 外部检索模式，用户通过这个全局界面实现对多个或任意一个搜索引擎的检索。 ( 2 ) 检索指令转换在具有唯一全局外部检索模式情况下，系统可提供统一的 全局指令语言，并自动地实现元搜索引擎指令与其目标沥搜索引擎指令的转换， 用户使用同一指令语言检索不同搜索引擎的索引数据库。 ( 3 ) 统一结果集的组织与显示元搜索引擎提供全局组织器，对各目标源搜索 引擎返回的结果进行处理，形成全局结果集并以统一格式显示，主要涉及数据格 6 第2 章元搜索引擎概述 式转换、去重、统一排序等。像m e t ac r a w l e r ，s a v v ys e a r c h ，p r o f u s i o n 等都属 于这类元搜索引擎。 2 2 2 a l l - i n - o n e 式搜索引擎 a l l i n o n e 方式，是指元搜索引擎界面以任意顺序或分类罗列多个搜索引 擎，元搜索引擎本身主要提供各类搜索引擎的介绍信息和物理连接机制。用户可 通过这些信息了解有关的搜索引擎，连入要选择的搜索引擎。但元搜索引擎没有 统一的全局外部模式，而是以各搜索引擎的检索模式和数据格式直接面对用户。 确切的说，这种a l l i n o n e 方式的元搜索引擎，只是搜索引擎的罗列。它们具 有以下特点： ( 1 ) 仅仅提供一个简单的界面帮助用户选择和使用各搜索引擎。 ( 2 ) 只能选择一个搜索引擎进行检索。 ( 3 ) 对各目标源搜索引擎检索界面的复制可能是部分的或全部的。 ( 4 ) 直接利用所选搜索引擎的显示格式将结果呈送给用户。 以上就是a l l i n o n e 主要特点，可以帮助我们使用这种元搜索引擎，但是 从它的特点可以看出存在一些局限性。 2 3 元搜索引擎与独立搜索引擎和分布式搜索的比较 2 3 1 与独立搜索引擎的比较 元搜索引擎区别于独立搜索引擎，最主要的是一般没有自己独立的索引数据 库，可以投入更多力量提供统一检索界面，形成一个由多个分布的、具有独立功 能的搜索引擎构成的虚拟整体，用户通过元搜索引擎的功能实现对这个虚拟整体 中各独立搜索引擎数据库的查询、显示等操作。元搜索引擎中各独立搜索引擎各 自保持其原来的局部数据模式和检索指令，由元搜索引擎提供一个全局外部模 式，用以接受用户检索输入和结果输出。这种特色的布局方式，造就了元搜索引 擎的以下优势例： ( 1 ) 信息的覆盖面元搜索引擎一般调用它自己认为比较好的几个搜索引擎， 而且大多数的元搜索引擎都提供给用户在一定范围内搜索引擎的功能。有些元搜 索引擎还以频道的方式为用户提供专业的搜索引擎分类。这样用户可以根据自己 的喜好和要查询的内容选择相应的搜索引擎。 ( 2 ) 搜索结果的权威性和可靠性独立搜索引擎索引数据库的更新需要一定的 周期，而且搜集的信息也各有一定的侧重，元搜索引擎调用多个独立搜索引擎获 取搜索结果，这种方式保证了信息的互补性。其次，与独立搜索引擎相比，提高 了信息的新鲜度。如果同样搜索结果在多个搜索引擎中同时出现，那么说明这个 7 北京工业大学工学硕士学位论文 搜索结果比较重要。这样，避免了有些独立搜索引擎人工干预有些搜索排名的缺 点，使得搜索结果的排序更加公正。 ( 3 ) 易维护性是针对元搜索引擎的管理者而言的。元搜索引擎省去了独立搜 索引擎中搜集和存储网页、建立和存储索引的工作。它将它所调用的搜索引擎看 成一个独立完成一定功能的实体，本身不需要去维护，只需要知道他们的调用接 口。元搜索引擎的查询精度在很大程度上在于它所调用的搜索引擎的精度。所以， 元搜索引擎可以把主要精力放在搜索引擎的选择、查询请求的优化和搜索结果的 优化上。一般的元搜索引擎都提供了对应的优化机制。 2 3 2 与分布式搜索引擎的比较 分布式搜索引擎是由很多“独立搜索引擎”构成的，但是它采用的是和元搜 索引擎完全不同的分布式检索方式3 。这种方式根据地域、主题或其他划分标准， 将全网划分成若干自治域，在每个自治域内分设检索服务器，每个检索服务器由 信息搜集软件、索引数据库和代理三部分组成。信息搜集软件负责本自治域信息 的搜集，并建立索引信息存入索引数据库，代理则负责向用户提供查询接口，并 与其他代理进行交互，实现检索服务器之间的信息交换。可见，分布式检索中， 各个检索服务器要管理的w e b 信息量相对小，对于各检索服务器的添加、删除 也便于维护。因为它们可以联合起来针对同一查询协同工作，因此，可在降低索 引数据库大小的同时，克服独立搜索引擎覆盖面低、维护困难，重复建设，浪费 网络资源等问题。但是，分布式检索在实际提供w e b 检索服务时，客户端要使 用支持同一协议的检索工具或者添加一个协议转换的网关。而这都是非常难解决 的问题，因此，到目前为止，基于这种分布式思想的搜索引擎还不存在。 元搜索引擎也是为克服独立搜索引擎覆盖面低等问题而提出来的。虽然目前 存在的版本效率不高，但是它的存在为其改造和发展奠定了基础，不需要从根本 上改造现有独立搜索引擎，也不用维护大的索引数据库。如果采用好的数据模型， 对各异构搜索引擎集成，对整个查询过程在上层加入合适的控制机制，将会使元 搜索引擎的特长得以充分发挥，从而获得较高的查全率和查准率。 2 4 元搜索引擎的评价指标 作为一种搜索引擎，元搜索引擎也有搜索引擎的一些基本指标，如响应速度、 准确率等。但成员搜索引擎间的个体差异性很大，如果结合它们的性能来对元搜 索引擎进行评价，将很难得出精确的结果。因此元搜索引擎的评价主要依靠下面 几个主要指标u 们： 1 成员搜索引擎的调度策略也就是足否允许用户浏览并选择要调用的独立 搜索引擎。有些元搜索引擎固定地调用几个独立的搜索引擎，用户不能修改。有 8 第2 章元搜索引擎概述 些元搜索引擎的高级特性中让用户选择调用哪些搜索引擎。这种方式对于那些对 独立搜索引擎比较了解的用户来说，是可取的，而对于不了解的用户来说，可能 选择不到适合自己查询的搜索引擎。独立搜索引擎的各种技术飞速发展，性能也 随之不断提高。元搜索引擎只能选择几个搜索引擎同时进行搜索，因为选择的搜 索引擎的个数越多，固然得到的搜索结果更加全面，但是结果的集成将花费更多 的时间。元搜索引其一直固定的调用几个搜索引擎，可能跟不上搜索引擎发展的 潮流。 2 覆盖网络资源的广度即是否覆盖多种网络资源类型，是否可提供主题范 畴的目录服务。 3 检索选项和功能设置是否支持逻辑匹配检索、短语检索、自然语言检索 等高级检索特性：是否能够实现检索请求的“本地化”转换；是否可以限定最长 检索时间；是否可以设置每个搜索引擎的返回的结果数：是否可以设置标题的大 小( 搜索引擎可以从t i t l e 标记中显示的最大字符数) 和摘要的大小( 搜索引擎所显 示结果中摘要的最大字符数) ；是否提供显示选项( 用户可以通过它来设置结果的 其他显示方式) ；是否能够自动检查链接的有效性等等。检索选项越多，用户使 用的时候就越灵活n u 。 4 对搜索结果的处理能力对独立搜索引擎返回的结果处理是元搜索引擎的 又一重要技术，它包括结果的处理和结果的显示。有些元搜索引擎提供多种显示 结果的方式j 如有些元搜索引擎提供方式让用户按照时间、按照搜索引擎、按相 关度等来排序。有些元搜索引擎提供了让用户定制搜索结果的聚类方式，如按域 名聚类、按主题分类等。 2 5 搜索引擎发展历史和趋势 追溯历史，1 9 9 0 年由加拿大麦吉尔大学开发的软件a r c h i e 可算得上是最早 意义上的搜索引擎。a r c h i e 通过相应的索引技术从分散的f t p 系统中获取文件 名信息，并存放在一个大型数据库中，供用户查询和访问。尽管其所提供服务的 信息资源对象与当前搜索引擎不同( 前者是f t p 文件，后者是h t m l 网页) ，但 自动搜集和索引分布在广域网上的资源信息并提供检索服务的工作方式却构建 了现代搜索引擎技术的基本框架n 利。 真正意义上的搜索引擎是始于1 9 9 4 年7 月。当时，利用j o h nl e a v i t t 的蜘蛛 程序能够实现网页索引程序的自动发现和索引功能，m i c h a e lm a u l d i n 创建了世 界上第一个真正意义的搜索引擎l y c o s n 朝。随后，伴随着w e b 上信息量的急剧增 长，人们不断推出各种功能更强大、检索效率更高的搜索引擎，其中比较著名的 有：g o o g l e ， y a h o o ，m s n 以及m e t ac r a w l e r 等。 9 北京工业大学工学硕士学位论文 w e b 信息的海量、异构及动态特性给搜索引擎的发展提出严峻的挑战。面对 “因特网信息检索定律”，搜索引擎技术如何发展已经成为人们日益关心的难题。 针对当前w e b 和搜索引擎发展状况，徐宝文等指出新一代搜索引擎应该在自然 语言处理、数据挖掘和机器学习技术、基于内容的多媒体查询技术、多通道用户 界面( 自然语言、多媒体等) 等方面有所突破n 引。具体概括如下： 1 智能搜索引擎将继续作为关注的重点。这里所指的智能搜索引擎研究内 容主要包括对自然语言语义或概念的更充分的理解( 分词技术、语义理解等) 、不 同语种的智能支持( 英文、中文等) 、异构信息检索请求( 文本、图片、多媒体等) 世 奇o 2 查准率将逐渐成为各搜索引擎之间竞争的焦点。考虑到索引技术、w e b 信息增长的速度、w e b 隐藏网页的存在、信息存储和c p u 处理能力等主客因素 的限制，各主要搜索引擎( 主要指独立搜索引擎) 除保证一定的查全率外，将更多 的注意力都放在查准率上，通过提高查准率来间接地提高用户满意度。 3 检索的个性化、本地化依然是研究的热点。未来的搜索引擎应该更集中 地强化以用户为中心的思想，致力于为不同用户( 年龄、学历、种族等) 提供不同 的检索服务( 文本、多媒体、语言等) 。同时，随着各大搜索引擎公司不断强化本 地化搜索引擎建设，搜索引擎的本地化已经成为搜索引擎发展的必然趋势。 4 元搜索引擎技术依然是关注的亮点。考虑到当前独立搜索引擎发展过程 中碰到且自身无法解决的查全率问题以及个性化方面的需求，元搜索引擎依然是 人们研究的重点。近几年，虽然从理论上来讲，元搜索引擎应该优于独立搜索引 擎，但由于种种因素的限制，当前元搜索引擎的优势还远没有得到发挥与体现， 还有待相关领域的研究人员进行更深入的探索与研究，这也是本文研究的目的和 重点。 2 6 本章小结 本章开始概述了元搜索引擎的定义和基本原理，重点说明元搜索引擎的技术 和一般搜索引擎的不同之处，它们的根本分歧在哪里，以及在实现上的不同。 第二节介绍了元搜索引擎的分类，以及不同的种类之间的优劣。 最后，从评价指标上给出了元搜索引擎的发展的必然趋势，并简要介绍其发 展历史。 l o 第3 章成员搜索引擎的选择策略 第3 章成员搜索引擎的选择策略 i n t e m e t 技术的不断普及与发展，为搜索引擎的研究工作提供了良好的环境。 但近几年来，随着各式各样搜索引擎的出现，为了提高信息检索的质量与效率， 如何进行搜索引擎之间的比较与选择逐渐成为人们关心的主要问题。元搜索引擎 系统应该选择哪些搜索引擎作为待选择搜索引擎? 针对某一查询请求，应该选择 哪些搜索引擎作为搜索入口? 如何设定被选定的各个待选择搜索引擎返回结果集 的数目以及响应时间等参数? 这就是元搜索引擎研究中的搜索引擎选择问题。 3 1 搜索引擎选择策略的重要性与必要性 搜索引擎选择问题主要包括两个方面：元搜索引擎数据源选择问题和搜索引 擎在响应用户查询请求时对各待选择搜索引擎的动态调用问题。在众多的搜索引 擎中如何选择搜索引擎以及将什么样的搜索请求分发给哪些搜索引擎是一件非 常棘手的事情。具体注意事项如下： 一、搜索引擎的种类、数量以及质量等因素将直接影响到元搜索引擎最终的 搜索质量。 二、基于系统运行效率的考虑，针对任何查询请求，都采用同一种响应策略 和响应参数是不合理的。 三、考虑到各独立搜索引擎索引数据库在网页信息量、适用范围以及索引技 术等方面的差异，如果只是简单地选择几种性能比较优越且用户评价比较好的搜 索引擎可能会造成不必要的系统资源浪费。 3 2 成员搜索引擎的影响 成员搜索引擎的影响是多方面的，成员搜索引擎的查询时间、查准率和查全 率、输入输出接口从不同方面影响着元搜索引擎的性能n 引。 查询时间 元搜索引擎的响应时间是由成员搜索引擎决定的，而且是由时间性能最差的 那个成员搜索引擎的检索时间所决定的。时间问题是元搜索引擎所遇到的一大问 题，目前流行有两个解决方案。其一，通过用户的输入，控制时间。即在用户接 口，有一个时间选择选项，由用户选择等待返回结果的最长时间。另一种方式是 分批显示。即增量式显示，返回结果一点点的增加。最早返回的结果先显示给用 北京工业大学工学硕士学位论文 户，然后随着结果的返回，再动态的改变显示页面。目前大部分的元搜索引擎采 用的是第一种方式。 查准率和查全率 查准率是指获取的相关信息与获取总信息的比率。即用户通过元搜索引擎所 获取的信息中对于用户来讲有用的信息占总共获取信息的比率，而查全率是用户 获取的信息与整个i n t e m e t 中相关信息的比率。元搜索引擎，由于它调用了多个 成员搜索引擎，并且采用相关的元搜索技术，消除了重复及冗余信息，并进行结 果的重新排序。所以它的查全率相比单个成员搜索引擎高，也就是信息覆盖率高。 元搜索引擎的查全率和查准率受它所调度成员搜索引擎的查全率和查准率影响， 而一个好的元搜索引擎可以通过一系列的优化来提高元搜索引擎的查全率和查 准率。 输入输出接口 元搜索引擎通过调度成员搜索引擎进行查询，从各个成员搜索引擎返回的 h t m l 文件中抽取结果，然后进行结果合并。而每个成员搜索引擎都有自己独特 的用户输入和输出接口。由于成员搜索引擎的用户输入和输出接口没有统一的标 准，这样就增加了元搜索引擎实现难度，为了实现对成员搜索引擎的调度，必须 对每个成员搜索引擎的用户输入输出接口进行分析。随着成员搜索引擎用户输入 和输出接口的改变，系统维护开销也将变大。 3 3 成员搜索引擎的选择方法 怎样选择独立搜索引擎是在元搜索引擎是在元搜索引擎实现的过程中所要 解决的一个关键的问题。如果元搜索引擎的独立搜索引擎数量不多，可以将用户 的查询送到各个独立搜索引擎。然而，如果独立搜索引擎数量巨大，将查询送到 每个独立搜索引擎的策略则不再合理。因为在这种情况下，大多数成员数据库对 此查询毫无用处。假设用户只对1 0 个与其提交查询最匹配的文件感兴趣。这1 0 个文件显然最多只能来自于l o 个不同的数据库。因此，如果数据库的数量远远 超过l o 个，大量的数据库对于此查询是没有用的。将查询送到大量无用数据库 有很多缺点。首先，传输查询到无用数据库并从这些数据库传输无用文件到元搜 索引擎形成了不必要的网络通信。其次，当无用独立搜索引擎处理查询时，其资 源也被浪费了。第三，当无用搜索引擎返回大量结果时，元搜索引擎需要花更大 的代价来识别处理有用的结果。为了解决以上的问题，我们尽量将查询只送到潜 在有用的数据库。这个如何识别潜在数据库的问题被称为成员搜索引擎的选择问 题。 1 2 第3 章成员搜索引擎的选择策略 当元搜索引擎收到用户查询时，它启动数据库选择程序来选择合适的成员搜 索引擎。一个好的数据库选择方法应该准确地识别出有用的数据库，为了进行数 据库的选择，必须要知道能够反映每个成员引擎的数据库特点的信息，我们称这 种信息为数据库特征信息。现有多种解决数据库选择问题的方法，可以分为三类 【 ( 1 ) 定性的方法这类方法根据一定的评分函数针对给定查询预测每个数据库 的质量。其评分或质量衡量往往不易理解。 ( 2 ) 定量的方法这类方法根据一些比定性方法使用的衡量标准更易理解的标 准来衡量数据库的有用性。换言之，定量的方法使用根据给定查询计算出数据库 的有用性。相对于定性方法而言更加直接和明确。 ( 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 e t w o r k ) 方法刀中，每个成员搜索 引擎数据库的描述信息包括了其所有术语的两个信息：文件频率和数据库频率。 前者是指在某个成员搜索引擎数据库中含有该术语的文件个数，后者是指含有该 术语的成员搜索引擎数据库的个数。对于给定查询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 中成为该术语的文件频率。因此，从成员 搜索引擎数据库代表信息中，便可以得到每个术语文件的术语频率和文件频率。 公式t f * i d f 可以用来计算每个超级文件中术语的权值，以便将每个超级文件用权 值向量来表示，t f 是根据术语频率计算出来的权值因子，而i d f 是根据文件频率 计算出来的权值因子。通常t f 是术语频率的增函数，i d f 是文件频率的减函数。 c o r in e t 使用的是一种某于i n f e r e n c en e t w o r k 的概率论方法。 在c o r in e t 中，每个术语的数据库代表信息稍稍多于一个数据量( 即文件频 率加上所有数据库共享的数据库频率) 。因此，c o r in e t 方法具有较好的扩展性， 获得或维护代表每个成员数据库内的信息也很容易。c o r in e t 的一个优点是其 北京工业大学工学硕士学位论文 计算文件对于查询系统的一套评分方法可以同样( 通过数据库代表信息或超级文 件) 用于计算数据库对于查询的评分。 3 3 2 定量法 定量方法和定性方法主要区别在于前者使用的衡量成员搜索引擎数据库有 用性的标准更加明确和实用。举例来说，定量方法n 鲫使用的衡量成员搜索引擎数 据库有用性的一种标准是“成员搜索引擎数据库中对于每一个查询潜在的有用文 件的数量”。很明显，这个数量清楚的反映了该成员搜索引擎数据库对于给定查 询的有用性。另外一种有用的定量衡量标准是：一个成员搜索引擎数据库中与给 定查询最为相似的文件的全局相似度。一方面，该标准表明了能够指望从一个成 员搜索引擎数据库中可得到最好的结果是什么。另一方面，对于给定的查询，该 标准可以用来最优化地对成员搜索引擎数据库进行排序，进而从所有成员搜索引 擎数据库中检索得到最相似的几个文件。 3 3 3 基于学习法 这类方法n 们基于以前提交的查询中得到的检索经验来预测成员搜索引擎数 据库对于新查询的有用程度。检索经验可能来自多方面。第一，可使用训练查询。 对于每个成员搜索引擎数据库关于训练查询的检索经验可以在搜索引擎数据选 择投入使用前得到。这类方法称为静态学习方法，因为在此类学习方法中，检索 经验一经学习得到就不再改变了。静态学习方法的缺陷在于不能适应成员搜索引 擎数据库内容和查询模式的改变。第二，可使用真正的用户查询( 而不是训练查 询) ，检索经验可以逐步积累并持续更新。这类方法称为动态学习方法。这种方 法的问题在于需要一定时间才能对搜索引擎数据库有足够用的信息。第三，可使 用静态学习和动态学习结合的方法。这类方法可以通过训练查询得到初始经验， 而通过真实查询不断更新知识。混合学习可以克服另外两种方法的弱点。 ( 1 ) 静态学习方法啪1 ：使用训练查询，对于每个成员搜索引擎关予训练查询 的检索经验可以在成员搜索引擎选择程序投入使用前得到。 优点：计算简单 缺点：不能适应成员搜索引擎内容和查询的更新。 例：m r d d 方法 m r d d ( m o d e l i n gr e l e v a n td o c u m e n td i s t r i b u t i o n ) 方法是一种静态学习方法。 在学习过程中，使用一组训练查询集，把每个训练查询发送给每个搜索引擎。对 于给定查询从某个搜索引擎返回的结果中，可以得