（模式识别与智能系统专业论文）搜索引擎的相关性排序研究.pdf

摘要 摘要 随着计算机系统性能的提高和网络技术的不断进步，万维网成为全球最大 的信息资源库，如何为如此庞大的信息资源提供高效的导航服务，帮助用户在 海量的数据中快速找到需要的信息是搜索引擎亟待解决的问题。用户通常只关 心搜索引擎返回的排在前面的结果，因此对搜索引擎索引的文档按照与用户查 询的相关程度进行排序，将相关度高的文档排在前面，即本文研究的搜索引擎 的相关性排序，成为当前研究的重点和热点。 本文的主要研究工作可归纳为以下几点： ( 1 ) 研究了文本搜索引擎的相关性排序模型，包括布尔模型，向量空间模型， 概率模型，超链接模型，自学习排序模型。其中自学习排序模型将机器 学习方法运用于搜索引擎的相关性排序问题，解决了以往模型的许多不 足之处。 ( 2 ) 为自学习排序模型提出一种构造训练集的方法。自学习排序是一种有监 督的机器学习方法，模型的性能很大程度上依赖训练集。本文提出一种 同时考虑查询的难度、密度、多样性的贪心算法，从海量的查询中选择 有信息量的查询进行标注。实验表明本文提出的方法能构造一个规模较 小且有效的训练集。 ( 3 ) 研究了图像重排序算法。现今的图像搜索引擎主要利用图像周围的文本 信息进行排序，没有考虑图像视觉信息。图像重排序是在文本搜索结果 的基础上，通过挖掘图像视觉特征的内在关系，对原始搜索结果进行重 新排序，使新的序列更能满足用户需求。基于分类、基于聚类和基于图 理论是图像重排序的三类主要方法。 ( 4 ) 提出一种与查询相关的图像相似性的度量方法。在图像重排序中如何度 量图像相似性至关重要。现有的相似性度量没有考虑针对不同的查询， 图像的相似性应该不同。本文提出一种与查询相关的相似性度量方法， 把基于全局特征的相似性，基于局部特征的相似性，以及视觉单词同时 出现率融合到一个迭代算法中，挖掘出与查询相关的图像信息，计算相 似性。实验结果表明本文提出的相似性度量方法在图像重排序中优于基 于全局特征，局部特征，或它们线性组合的相似性。 关键词：搜索引擎的相关性排序，自学习排序模型，构造训练集，图像重排序， 图像特征提取，图像相似性度量 a b s t r a c t a b s t r a c t w i t ht h ei m p r o v e dp e r f o r m a n c eo fc o m p u t e rs y s t e m sa n dt h ec o n t i n u o u sp r o c e s s o fn e t w o r kt e c h n o l o g y , t h ew o r l dw i d ew e bh a sb e c o m et h el a r g e s ti n f o r m a t i o n r e s o u r c e sw a r e h o u s e s e a r c he n g i n e sh a v et op r o v i d ee f f i c i e n tn a v i g a t i o ns e r v i c ef o r s u c hh u g ei n f o r m a t i o nr e s o u r c e st oh e l pu s e r sq u i c k l yf i n dt h ei n f o r m a t i o n t h e yn e e d i nv a s ta m o u n to fd a t a a n du s e r su s u a l l yo n l yb r o w s et h er e s u l t sr a n k e dn e a rt h e t o p o ft h es e a r c he n g i n er e t u r n s s oi no r d e rt oh e l pu s e r sf i n dr e q u i r e di n f o r m a t i o n ， s e a r c he n g i n e ss o r tt h ei n d e x e dd o c u m e n t sb yt h er e l e v a n c et ou s e r s r e q u i r e m e n t h o wt oo r d e rt h eh i g h l yr e l e v a n td o c u m e n t so nt h et o po ft h er e s u l t si sac r u c i a lf o r s e a r c he n g i n e s i ti sa l s ok n o w na ss e a r c he n g i n e s r e l e v a n c er a n k i n g ，w h i c hi st h e f o c u so fc u r r e n tr e s e a r c h t h em a i nr e s e a r c hw o r ki nt h i sp a p e rc a nb es u m m a r i z e da sf o l l o w s 1 s t u d yo ns e a r c he n g i n e s r e l e v a n c er a n k i n gm o d e l s ，i n c l u d i n gb o o l e a nm o d e l ， v e c t o rs p a c em o d e l ，p r o b a b i l i s t i cm o d e l ，t h eh y p e r l i n km o d e la n dl e a r n i n gt o r a n k l e a r n i n gt or a n kh a sb e c o m eap o p u l a rm e t h o dt ob u i l dar a n k i n g m o d e lf o rw e bs e a r c h 2 p r o p o s e a n a l g o r i t h mt o c o n s t r u c t t r a i n i n g s e ti nl e a mt or a n k t h e p e r f o r m a n c eo fr a n k i n gm o d e ld e p e n d so nt h et r a i n i n gs e t i nt h i sp a p e rw e d e v e l o pag r e e d ya l g o r i t h mt os e l e c tq u e r i e s ，b ys i m u l t a n e o u s l yt a k i n gt h e q u e r yd i f f i c u l t y , d e n s i t ya n dd i v e r s i t yi n t oc o n s i d e r a t i o n t h ee x p e r i m e n t a l r e s u l t ss h o wt h ep r o p o s e dm e t h o dc a nl e a dt oam o r ei n f o r m a t i v et r a i n i n gs e t f o r b u i l d i n gar o b u s tm o d e l 3 s t u d yo ni m a g er e r a n k i n ga l g o r i t h m s r e c e n t l yi m a g es e a r c he n g i n e sm a i n l y b a s eo na s s o c i a t e dt e x t u a li n f o r m a t i o n i m a g e r e - r a n k i n gi s a l le f f e c t i v e a p p r o a c ht or e f i n et h ei n i t i a lt e x t b a s e ds e a r c hr e s u l tb ym i n i n gt h ev i s u a l i n f o r m a t i o no ft h er e t u r n e di m a g e s w e s t u d yt h er e r a n k i n gm e t h o d s ， i n c l u d i n gc l a s s i f i c a t i o n - b a s e d ，c l u s t e r i n g - b a s e da n dg r a p h b a s e dm e t h o d s 4 p r o p o s eam e t h o dt om e a s u r eq u e r ya w a r ev i s u a ls i m i l a r i t yf o ri m a g es e a r c h r e r a n k i n g t h ee s t i m a t i o no fv i s u a ls i m i l a r i t yi st h ef u n d a m e n t a lf a c t o ri nr e r a n k i n gm e t h o d s h o w e v e r , t h ee x i s t i n gs i m i l a r i t ym e a s u r e sc a n n o ta d a p tt o d i f f e r e n tq u e r i e s i nt h i sp a p e r , w ep r o p o s et oe s t i m a t ea q u e r ya w a r ei m a g e s i m i l a r i t yb yi n c o r p o r a t i n gt h eg l o b a lv i s u a ls i m i l a r i t y , l o c a lv i s u a ls i m i l a r i t y i i i a b s t r a c t a n dv i s u a lw o r dc o - o c c u r r e n c ei n t oa ni t e r a t i v ep r o p a g a t i o nf r a m e w o r k a f t e r t h ep r o p a g a t i o n ，aq u e r ya w a r e i m a g es i m i l a r i t yc o m b i n i n gt h ea d v a n t a g e so f b o t hg l o b a la n dl o c a ls i m i l a r i t i e si sa c h i e v e d t h e nw ea p p l ys u c hq u e r y a w a r es i m i l a r i t yt oi m a g er e r a n k i n gm e t h o d s t h ee x p e r i m e n t sd e m o n s t r a t e t h a tt h ep r o p o s e dq u e r ya w a r es i m i l a r i t y o u t p e r f o r m st h eg l o b a l ，l o c a l s i m i l a r i t ya n dt h e i rl i n e a rc o m b i n a t i o nf o ri m a g es e a r c hr e r a n k i n g k e yw o r d s ：s e a r c he n g i n e e r sr e l e v a n c er a n k i n g ，l e a r n i n gt or a n k ，c o n s t r u c tt r a i n i n g s e t ，i m a g er e r a n k i n g ，e x t r a c tf e a t u r e sf r o mi m a g e ，t h ee s t i m a t i o no f v i s u a ls i m i l a r i t y i v 致谢 致谢 本文的完成首先要感谢我的导师帅建梅老师，感谢她对我的指导、关心和 帮助。在论文的选题，写作，修改，润色过程中，她始终认真负责地给予我耐 心细致的指导。她一丝不苟的工作作风，严谨求实的治学态度，勤奋踏实的科 研精神是我学习的榜样。她随和热情，生活中给予我无微不至的关怀，鼓励我 努力面对困难。正是帅老师无私的教导和关爱，使我在人生的道路上不断进步 在此，谨向帅老师表示衷心的感谢和诚挚的敬意，祝帅老师身体健康，工作顺 利! 感谢信息安全实验室的奚宏生老师、谭小彬老师；感谢周潇、张小康师姐， 在我进入实验室时给我莫大帮助；感谢章文师兄、孔德光师兄、刘光宏师兄， 耐心地帮助我解决疑难问题；感谢刘芬、冯翔、梁萍、吴庆响：感谢实验室所 有的师弟师妹，感谢大家齐心合力营造了一个良好的研究环境。 感谢s a 0 7 1 0 的所有同学，杨奎元、赵立恒、杨波、孟彦鹏、孙晓燕、戴 君、房丽芳，和你们一起度过的日子充满了阳光和温暖，谢谢你们! 最后，谨以此文献给我亲爱的父母和弟弟，你们永远是我最大的动力。 第1 章绪论 1 1 选题研究背景 第1 章绪论 随着计算机系统性能的提高和网络技术的不断进步，万维网得到了蓬勃发 展，成为全球最大的信息资源库。据发表在科学杂志1 9 9 9 年7 月的文章 万维网信息的可访问性估计，万维网上的网页超过8 亿，有效数据约1 5 t ， 并且仍以每4 个月翻一番的速度增长。调查显示2 0 0 8 年初，全球可索引的网页 已高达1 5 6 亿。用户要在如此庞大杂乱的万维网资源中查找所需要的信息，就 像大海捞针一样，搜索引擎的诞生为用户检索如此庞大的信息资源提供了可能。 搜索引擎是基于万维网平台，提供网络信息检索服务的工具。搜索引擎首先对 万维网的数据进行搜集并建立索引数据库，当用户给出关键词进行查询时，搜 索引擎分析用户查询需求，并计算该查询与其索引文档的相关性，最终按照相 关程度返回检索结果给用户，帮助用户拒绝和忽略大量无关信息，从而起到信 息导航的作用。 一般来说，评价一个搜索引擎性能的主要指标【1 】是：查全率、查准率、检 索速度、检索系统的易用性和检索费用。目前搜索引擎的查全率、检索速度、 检索系统的易用性和检索费用基本能满足用户需求，然而用户对查准率并不满 意。如图1 1 ，用户在g o o g l e 中输入关键词“硼r ”，该搜索引擎仅用0 0 7 秒 返回1 5 6 8 0 0 0 0 0 0 0 查询结果，但前5 个结果都不是用户期望的。g o o g l e 搜索引擎 用户界面简单易用，提供免费搜索服务，返回成千上万的网页，查全率高，但 用户期望的结果往往并不排在前列，并且查询结果中有着大量的重复，无关， 无用的网页。 一赴雌蛆量璺鲢魄卿置直- g o o g l e 旷1 厅委蕊煎习“ 亩所棚o 鼻 _ o 中x h 霄一盯 口$ i 膏- _ _ _ 百虞一下t 竹m 柚j i t “ l ，一r o t 田卫掣型弛蟹e 世 _ ，m o 口z 】= 基毒s 酶薹 nw 野器 毫墨 置。矗啦 l 1 u 业! t ! = 宴乜 嫩咧直噜鞋硝蛆皇擅点矗螂盛巍电钮剧犀拍墙芏盘二蝣墨一 p 目忡q 岬哺删孙* n t 驯_ 盏 圳b 1 o 一 wg i ! 置 “c o r n新， 晌臂椿i h ”n n 一8 i 协n 譬u l i t i i - - - h v t m 丛! l 自h 三她 i 圳* 州“h 抽- s l m hl 时c 帅 州呷叫o 州h _ a j b 卫口【量垃 o p ”m 蛐班丑二二也虹上一t 亚 h 栅孙t 姐i 一t w o 十哇r 错 州圳口l - + 了- 啪 一rc l 哇f u 螂，州，竹悖二盟i 蛳_ “m 蹦i 眈勃m l t 幻l o - 抽冉吨_ t 岫v x _ - i - _ 一y 砷” m 肿m i _ k _ 机 _ ；t f 口5 f ， ，h # 鼢器黑嚣巴篇：= 嚣= ：船臻鬣：裂恕：裟高：品豁” n h - - 帅岫岫i 。一一一 一一 图1 1g o o g l e 搜索引擎中用户输入关键词“w w w ”返回的查询结果 第l 章绪论 当前搜索引擎返回的查询结果与用户需求的相关程度并不理想。根据中国 互联网络信息中心调查报告，中国搜索引擎用户不满意因素及比例如表1 1 。因 此研究搜索引擎的相关性排序算法，将与用户需求相关度高的网页排在前面是 搜索引擎系统亟待解决的问题。 表1 1 中国搜索引擎用户不满意因素及比例 不满意因素所占比例 搜索结果重复 5 0 搜索结果排序欠佳 4 3 搜索结果杂乱 3 7 搜索结果不合适 3 6 广告太多 3 5 另外，在普遍的关键词检索系统中用户一般只是键入少数几个词语。s p i n k 等对搜索引擎的近3 0 0 位用户调查，发现人均输入的检索词为3 3 4 个。国内部 分学者也发现9 0 左右的用户输入的中文检索单字为2 6 个，而且2 字词居多， 约占5 8 ，其次为4 字词( 约占1 8 ) 和3 字词( 约占1 4 ) 。然而检索词所提供的 用户需求信息是很重要的，过少的检索词事实上无法真正表达用户的检索需求， 而且很多用户从不使用高级检索功能，据不完全统计约4 0 的用户不能正确运 用字段检索或二次检索，8 0 左右的用户不能正确运用高级检索功能，但他们 都希望搜索引擎将最想要的结果尽可能地放到查询结果的前面。然而根据现有 的搜索引擎相关性排序算法返回的搜索结果，并不能让用户满意。因此研究搜 索引擎的相关性排序算法，提高用户满意度已经成为搜索引擎系统的紧要任务。 1 2 相关性排序研究意义 中国互联网络信息中心调查报告指出，有8 2 5 的网民经常使用搜索引擎， 8 3 4 的用户通过搜索引擎得知新网站。可见，搜索引擎在大家日常的网络生活 中发挥了重要作用。对搜索引擎性能的改进能在很大程度上提高用户上网体验。 一个优秀的搜索引擎能从巨量的、形如垃圾的信息中发现真正的知识，通过对 信息的甄别、加工、提纯，带来信息价值的提升。然而由于当今搜索引擎相关 性排序算法并不完善，用户通常需要从大量的返回结果中手工挑选相关网页， 搜索引擎的导航功能没有得到充分的发挥。 在搜索引擎发展的初期，搜索结果的排列只是根据搜索引擎在数据库中找 到匹配网页的先后次序，不保证排在前面的网页与用户查询的相关性更大，因 此不能帮助用户从过载的海量信息中快速地选取真正相关的信息。目前搜索引 擎索引的网页数量已达到上十亿的规模，通常搜索结果包含成千上万的网页， 即便这些网页都是用户所需要的，用户也不可能浏览所有的网页。如何将更相 2 第1 章绪论 关的网页排在前面，减少用户浏览网页的数目，帮助其快速找到需要的信息， 是一项很有意义且富有挑战性的工作。 美国最早的搜索引擎营销专业服务商i p r o s p e c t 对1 6 4 9 名搜索引擎用户使 用习惯进行调查，发现8 1 7 的用户不会浏览三页之后的搜索结果，而5 2 2 的 用户只会关注第一页搜索结果。也就是说，用户通常只关心搜索引擎返回的排在 前面的文档。因此研究搜索引擎的相关性排序算法，将用户期望的结果排列在 前面，显得越来越重要。 综上，从搜索引擎系统来讲，它需要从海量的数据中找到与用户需求相关 的信息，并且按照相关程度对这些信息进行排序。然而目前没有一个完善的衡 量信息相关程度的普适算法，因此按照文档与查询的相关程度进行排序本身是 一个很有挑战的研究工作。从用户使用习惯来讲，用户通常只输入有限的关键 词并且只关心搜索引擎返回的排在前面的文档。通常有限的关键词不能有效表 达用户需求，用户却希望搜索引擎智能地将与其需求相关程度高的信息排在返 回结果的前面，这对搜索引擎系统提出了很高的挑战。搜索引擎返回结果中排 在前面的网页对用户了解信息，学习知识有重要的帮助，排在前面的搜索结果 与查询需求的相关程度是衡量搜索引擎性能的重要指标，因此对搜索引擎相关 性排序的研究有着十分重要的意义。 1 3 国内外研究和现状分析 搜索引擎不仅需要返回索引结果，而且应该对这些结果进行再加工，判断 哪些更符合用户搜索意图，将用户最感兴趣的文档排列在前面，方便用户在最 短时间内找到需要的信息，提高搜索引擎的用户满意度。这便是搜索引擎的相 关性原则，已被作为搜索引擎最基本原则之一。 搜索引擎的相关性排序模型【1 】包含布尔模型，向量空间模型，概率模型， 超链接模型和自学习排序模型。布尔模型建立在经典集合论和布尔代数的基础 上，根据文档中是否出现关键词来判断文档是否与查询相关，所有相关文档与 查询的相关程度都是一样的，不支持按文档与查询的相关程度进行排序。向量 空间模型将文档和用户查询分别映射到向量空间中，即将文档和用户查询分别 表示成向量形式，计算两个向量的夹角余弦作为相似性的度量，并按照其递减 的顺序排列文档。该模型假设关键词彼此独立，在实际应用中一般很难满足。 另外文档的向量表示形式缺乏理论验证，大都是经验公式，并且计算量大。概 率模型以概率论为基础，对文档和查询建立概率模型，根据文档与查询相关联 的概率计算相似性，对文档进行排序。该模型同样假设关键词彼此独立。另外 它还需要事先知道文档的分布，估计参数，因此准确性难以保证。超链接模型 第l 章绪论 根据网页之间相互的超链接计算网页排名，从链接数目和链接页面的质量判断 网页的级别。为了提升网页排名，网页引入更多的导入链接，使用虚假的连接 使网页排名靠前，不符合搜索引擎相关性排序原则。并且在超链接模型中，新 网页比较难以得到认可。自学习排序模型将机器学习的方法运用到搜索引擎相 关性排序问题，解决了以往模型的许多不足之处。它根据训练样本学习排序模 型，再根据学习得到的排序模型，预测与查询相关的文档排序。 在这些模型的基础上，出现各种计算文档与查询相关性排序的算法。最初 的搜索引擎相关性排序算法基于传统信息检索技术的方式，主要利用关键词本 身在文档中的重要程度，对文档与用户查询的相关性做出评价，具有代表性的 算法主要是b m 2 5 1 6 】。它提出文档中关键词的“匹配位置频次原则，就是说 文档中的字词、词组或短语与用户输入的关键词越匹配，匹配的次数越多，则 该文档与用户查询的相关程度越高。同时，查询关键词如果出现在文档中的重 要位置上( 如标题) ，则比出现在正文的相关度要大，该文档在搜索结果中排名 也越靠前。但该方法有较多参数，对大规模的数据集合难以调整参数。 随着万维网的发展，g o o g l e 提出超链接分析技术【3 5 】，以网页被认可的重 要程度作为相关性排序依据。网页间存在的各种超链接指向，超链接技术主要 分析网页之间的引用关系。依据网页链接数目和链接网页质量计算该网页的重 要度权值。一般认为，如果b 网页有超链接指向a 网页，相当于b 网页投了a 网页一票，即b 网页认可了a 网页的重要性。整个w e b 网页文档集看成一个有 向的拓扑图，其中每个网页都构成图中的一个结点，网页之间的链接就构成了 结点间的有向边，根据每个结点的入度来评价网页的重要性。超链分析注重第 三方对该网页的认可，具有较大链入网页数的网页是得到广泛认可的重要网页， 而根据关键词位置和频率的传统方法只是一种网页自我认可的形式，缺乏客观 性。对于超链分析技术，有代表性的算法主要是p a g e r a n k 和h i t s 算法【3 6 】。 这些算法对新网页的认可度不高，而且难以辨别虚假连接。 随着机器学习理论的日益成熟，很多研究人员将机器学习的方法应用到搜 索引擎排序问题中，提出自学习排序算法 1 3 】。对每个查询给定一系列的文档， 人工标注文档和查询间的关系。一个样本，记作( q ，d ，r ) ，其中q 代表查询，d 代表文档，r 表示文档与查询的相关程度。在学习阶段，从给定的训练样本集合 中学习得到排序函数。在排序阶段，直接使用排序函数预测文档与给定查询的 相关性，对所有文档按照相关性大小进行排序。 除此之外，还存在收费排名模式，它作为搜索引擎的一种主要赢利手段， 在具有网络门户特点的大型搜索引擎中广为使用，考虑到收费排名模式影响搜 4 第1 章绪论 索结果的客观性，这种方式不是搜索引擎的主流排序方式，而仅仅作为一个补 充显示在付费搜索栏目中。 随着多媒体技术的发展，图像搜索引擎也受到广泛关注。现今通用的大型 图像搜索引擎主要是利用图像周围的文本信息，实现图像的搜索和排序，没有 考虑图像本身的特征。为了解决只依据文本搜索的缺陷，很多研究者提出基于 图像内容的图像搜索的重排序。图像重排序是指在原始搜索结果的基础上，通 过挖掘图像内在关系，对原始搜索结果进行重新排序，使新的序列能更好地满 足用户搜索需求。目前图像重排序主要有基于分类的方法( 如虚相关反馈 2 5 1 ) ， 基于聚类的方法( 如信息瓶颈理论 2 6 】) 和基于图理论的方法( 如随机游走 【2 7 】) 。在以上图像重排序算法中，图像相似性的度量至关重要。通常，通过计 算图像视觉特征的相似性来估计图像的相似性。图像视觉特征包含全局特征 ( 如颜色，纹理，形状 2 1 】) 和局部特征( 如尺度不变特征 2 3 】) 。 1 4 本文的研究内容与组织结构 本文主要研究了文本搜索引擎的相关性排序模型，为自学习排序模型提出 一种构造训练集的方法。然后研究了图像搜索引擎相关性排序问题，重点研究 了图像重排序的方法，提出一种与查询相关的图像相似性度量方法，改善了图 像重排序的性能。 本文以下章节组织如下： 第二章主要研究了搜索引擎的基本概念和工作原理。搜索引擎由搜索器， 索引器，检索器，用户接口四部分组成，其中检索器中搜索引擎的相关性排序 算法是本文的研究重点。 第三章主要研究了文本搜索引擎的相关性排序模型，包括布尔模型，向量 空间模型，概率模型，超链接模型，自学习排序模型，重点研究了自学习排序 模型。自学习排序是一种有监督的机器学习算法，模型的性能很大程度上依赖 训练集。在本章中为自学习排序模型提出一种构造训练集的方法，实验表明本 文提出的方法能构造一个规模较小且有效的训练集。 第四章主要研究了图像搜索引擎的相关性排序，重点研究了图像重排序的 相关算法。图像重排序中，图像相似性度量至关重要。本章提出一种与查询相 关的图像相似性度量方法，进而改善了图像重排序的性能。 第五章总结本文的主要研究工作，展望未来的研究方向。 第2 章w e b 信息检索工具搜索引擎 第2 章w e b 信息检索工具一搜索引擎 2 1 搜索引擎基本概念 搜索引擎 1 】是基于万维网平台提供网络信息检索服务的工具。它利用网络 自动搜索软件，对万维网资源进行收集，整理，组织并提供检索服务。搜索引 擎处理的对象是文档( d o c u m e n t ) 资源，包含文本，图像，视频，音频等多媒 体。用户提交的检索需求称为查询( q u e r y ) 。搜索引擎按照一定的策略，在互 联网中搜集、发现信息，对信息进行理解、提取、组织和处理，为用户提供检 索服务，从而起到信息导航的目的。以文本搜索引擎为例，散布在世界各地的万 维网网页集合是检索对象，用户给出的关键词是查询请求，搜索引擎需要完成 的任务是找出含有用户给出的关键词的网页。通常搜索引擎先把万维网网页收 集到一块，分析其内容，把其中的u r l ，关键词等信息转换成便于检索的内部 形式，存储到数据库中。用户给定一个查询时，搜索引擎便到数据库中查找含 有用户提出的查询请求的网页，并将结果返回给用户。如图2 1 用户的信息需 求首先通过查询的形式输入到系统中，搜索系统将用户查询转换成内部表示的 同时，与文档集合的内部表示进行比较匹配，输出一组与用户需求相关的文档。 用户 毒 查询请求 文档集合 i 上上 查询的内部表不文档的内部表示 l 砸套 l v + 检索结果 图2 1 搜索引擎系统的概念结构 本文研究的搜索引擎的相关性就是指是用户查询请求与搜索引擎返回文档 的匹配程度。这是信息检索中最难定义的一个概念，因为实际上很难将用户的 查询需求形式化，通常用户只输入少量的查询词，并不能真正表达用户的查询 需求。即使用户输入了一些可以表达其需求的相关查询词，但是文档和查询是 否相关以及多大程度上相关，都依赖于用户自身的经验；同时自然语言处理还 不能完全理解文本信息，难以判断一个文档与查询的真实相关程度。因此研究 搜索引擎中查询与文档的相关性是一项极富挑战性的工作。 6 第2 章w e b 信息检索工具一搜索引擎 2 2 搜索引擎分类 按照信息搜索方法和服务提供方式的不同，搜索引擎系统可分为三类 1 ： ( 1 ) 全文搜索引擎 国内著名的有百度，国外代表性的有g o o g l e 、f a s t 、a l t a v i s t a 、i n k t o m i 、 t e o m a 、w i s e n u t 等。全文搜索引擎从互联网提取各个网站的信息( 以网页文字 为主) 建立数据库，检索与用户查询条件匹配的相关记录，然后按一定的排列 顺序将结果返回给用户。它通常由一个称为蜘蛛( 网络爬虫) 的机器人程序以 某种策略自动地在互联网中搜集和发现信息，将搜集到的信息下载到本地数据 库，然后由索引器为搜集到的信息建立索引，再通过检索器根据用户的查询对 索引数据库进行搜索，找出匹配的文档并将查询结果返回给用户。 该类搜索引擎一般有庞大的索引数据库，能实现信息的全面获取和及时更 新，不需人工干预，但它返回的信息过多，有很多无关信息，用户必须在结果 中进行筛选。 ( 2 ) 目录式索引 国内的搜狐、新浪，国外y 撕o o ! ，o p e nd i r e c t o r yp r o j e c t 、l o o k s m a r t 、 a b o u t 等。目录式索引是按目录分类的网站链接列表，用户完全可以不用进行 关键词查询，仅靠分类目录也可找到需要的信息。在严格意义上它并不是真正 的搜索引擎。它以人工、半自动或由万维网站点作者主动提交方式来搜集信息， 由编辑人员查看信息之后，人工形成信息摘要，并将信息置于事先确定的分类 框架中。目录信息大多面向网站，提供目录浏览服务和直接检索服务。 目录式索引加入了人的智能，信息准确、导航质量高，但是人工成本高、 维护量大、索引信息量少、更新不及时。随着信息量的增加，单纯靠人工组织 网站目录已不现实。 ( 3 ) 元搜索引擎( m e t as e a r c he n g i n e ) 国内的搜星，国外的i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等。元搜索引擎没有自 己的数据，在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结 果返回给用户。元搜索引擎的工作原理如图2 2 ，用户只需要提交一次检索请求， 元搜索引擎将请求格式根据预先选定的各个独立的成员搜索引擎的格式做相应 转换，然后再分发到各引擎，各引擎返回检索结果后，元引擎将结果汇总起来 以统一的格式呈现给用户。搜索结果排列方面，有的直接按来源引擎排列搜索 结果，如d o g p i l e ，有的则按自定义的规则将结果重新排列组合，如v i v i s i m o 。 这类搜索引擎的优点是返回结果的信息量更大更全，分散处理负载，缺点 是用户需要做更多的筛选。 7 第2 章w e b 信息检索工具一搜索引擎 皂圈囟富圈 蓍h 请求提交代珲圈检索接口代珲图结果显示代理i 图2 2 元搜索引擎示意图 2 3 评价搜索引擎的性能指标 为了比较多种搜索引擎系统的优劣，改善现有系统的性能、开发新的应用 领域，需要进行客观的评价工作。最具普遍意义的系统评价指标是时间和空间。 另外用户使用搜索引擎时，对系统返回的文档与查询的相关性有很高要求。因 此在评价搜索引擎性能时，除了系统的响应时间和所需的存储空间，我们还应 该考虑查询结果的相关性。好的信息检索系统应该尽可能多的包含与用户查询 相关的结果，同时与用户查询需求最相关的那些结果，应排在最前面。换句话 说基于相关性的评价应该同时考虑完全性和准确性。其中，完全性评价是否无 遗漏地检索出与查询需求相关的文档；准确性评价是否只检索出与查询需求相 关的文档。 搜索引擎是一种万维网信息检索工具，所以评价搜索引擎的性能可以借鉴 传统的衡量信息检索系统的性能参数查全率( r e c a l lr a t e ) 和查准率( p r e c i s i o n r a t e ) 。 为了评价信息检索的性能，首先需要人工标注文档与查询的相关性。用d 表示检索系统所针对的文档集合，q 表示一个查询，而宄( q ) 表示检索系统根据 查询返回的相关文档集，咒+ ( q ) 表示文档集中与查询相关的所有文档，并定义 算符f i 为集合中元素的个数。 查全率表示被检索出来的相关文档数目占文档集合中所有的相关文档数的 比率，用来衡量检索系统的遗漏程度，评价搜索引擎的完全性。查全率【1 】定义 如下： 眦n l l = 哿= 盟型等罴裂篆舞掣 眩t ， 查准率是检索出的相关文档数占所有检索出的文档总数的比率，用来衡量 的是检索系统的噪音程度，评价搜索引擎的准确性。查准率 1 】定义如下： 8 第2 章w e b 信息检索工具搜索引擎 p r p c z s z 。n = 眢= 卫三三生2 兰竺坚兰；芝三；三凳毫翌号毫芝笔i i ；耋i 必 ( 2 2 ) 对于搜索引擎系统来讲，因为没有一个搜索引擎系统能够搜集到所有的万 维网网页，所以查全率很难计算。而且用户更关心检索返回的相关文档是否排 在前面，以及排在前面的紧密程度如何，所以目前的搜索引擎系统更关心查准 率。 为了客观地评价搜索引擎的相关性排序，我们采用普遍使用的排序指标 m a p ( m e a na v e r a g ep r e c i s i o n ) 和n d c g ( n o r m a l i z e dd i s c o u n t e dc u m u l a t i v e g a i n ) 。 给定一个查询，搜索引擎根据排序模型返回文档排序r 1 ，r 2 ，r n ，位置j 处 的查准率计算公式如下： p 刨= 竺堕型竺号竺型塑坐坐 ( 2 3 ) 平均查准率a p ( a v e r a g ep r e c i s i o n ) 结合准确性与文档在返回序列中的位置， 强调了排在前面文档的重要性，符合用户对文档检索的需求。公式如下： a p = n u m b 蔷e ro 婴r e l e u 型a n td 盟o c u m e n t s ( 2 4 ) ， 、- 。 其中n 表示返回文档数目，r e l 0 ) 表示返回文档序列r 中位于j 处的文档与查询 是否相关，相关为l ，不相关为0 。对于多等级相关性，我们通常将其简化为两 个等级，比如，将“完全相关”看作相关，其他均看作不相关。为了进一步了解 平均查准率计算方式，我们假设搜索引擎系统对给定查询，返回5 个有序文档， 如图2 3 ，其中文档1 ，3 ，5 与查询相关，2 ，4 与查询不相关，平均查准率为 a p = 事 0 _ 7 6 ( 2 5 ) 圜圈圜 图2 3 搜索引擎返回有序结果的示意图 注：绿色表示文档与查询相关，红色表示文档与查询不相关 m a p 是测试集中所有查询的平均查准率的均值，反映了排序模型在测试集 上的整体性能。 n d c g 是信息检索中普遍使用的评价标准。给定一个查询，根据排序模型 返回排序r ，位置n 处的n d c g 的计算如下： 9 第2 章w e b 信息检索工具搜索引擎 n d c g 住= zy y ：1 而2 r ( j 3 - 1 ( 2 6 ) 其中r 0 ) 表示对返回的第j 个文档，人工标注它与查询的相关程度，收益 g ( g a i n ) 用2 r u ) 一1 计算。累计收益c g ( c u m u l a t i v eg a i n ) 即收益之和，对文档排 序不敏感，如表2 1 ，文档1 与文档2 调换次序，不影响c g 的值，但是对用户 而言，文档1 比文档2 更相关，应该排在前面。由于用户更关注前面的文档， 因此前面的文档排错，受到的惩罚应该较大。d c g 考虑了文档排列次序的影响， 使用饕1 ( 2 r f 3 ) 一1 ) l o g ( 1 + ，) 计算，对信息检索系统返回的结果给出一个客观地 评价。z n 是归一化因子，保证n d c g n 4 , 于等于l 。 n d c g 可以用来评价多个等级相关性。为了进一步理解n d c g 评价方式。 给定查询“a b e ”，搜索引擎返回有序文档，如表2 1 ，人工标注返回的文档与给 定查询的相关程度。这里我们假设文档与查询相关等级有“p e r f e c t “e x c e l l e n t ”，“g o o d ，“f a i r 和“b a d 五个等级。 表2 1 给定查询“a b c ”返回结果的n d c g 计算 u r l r e l a t e g a i n c gd o gb i d 0 3 撑l 一a b e g o c o r n p e r f e c t 3 13 13 1i 撑2a b c t e a c h t o mf a i r33 43 2 9 0 8 1 舞3 a b c n e w s g o t o m e x c e l l e n t1 5 ，一4 9 4 0 4 0 8 4 ，。 二a b e n e t a u 一2 f 雌e l l e n t ， 1 5 6 4。4 6 9 0 8 6 e 托 a + b c n e w sg n ，e c r ue x c e u e n t 。1 57 9 。+ 5 2 。0 8 7 。 ! ? 6 2 4 搜索引擎结构与工作原理 常用的搜索引擎系统，通过搜索器在万维网上收集网页，将网页下载到本 地数据库，然后使用索引器建立索引数据库。用户使用搜索引擎时，首先通过 用户接口输入查询关键词，检索器根据关键词在索引数据库中查找匹配的文档， 并且依据文档与查询的相关程度，返回有序文档作为查询结果呈现给用户。如 图1 ，一个完整的搜索引擎系统由搜索器、索引器、检索器和用户接口等四个 部分组成 1 】。 w e b g 目络 国 图2 4 搜索引擎基本结构 l o 第2 章w e b 信息检索工具搜索引擎 搜索引擎并不真正搜索互联网，它搜索的实际上是预先整理好的网页索引 数据库。真正意义上的搜索引擎，通常指的是收集了万维网上几千万到几十亿 个网页，并对网页中的每一个词( 即关键词) 进行索引，建立索引数据库的全 文搜索引擎。本文研究的相关性排序算法是全文搜索引擎中的检索器的一部分。 当用户输入的查询请求中包含某个关键词的时候，从索引数据库中将页面内容 中包含了该关键词的网页都检索出来，再通过相关性排序算法对检索出来的所 有网页进行排序，最后将排好序的网页呈现给用户。下面具体研究搜索引擎各 个部分的作用和基本工作原理。 2 4 1 搜索器从万维网上收集网页 搜索器的主要任务是从万维网上收集网页，将网页上的相关数据保存起来， 为搜索引擎构建索引做准备，是搜索引擎的重要组成部分。搜索器的实现有人 工收集和自动收集两种方式。人工收集由人跟踪选择万维网站点。万维网信息 资源丰富且更新快，人工收集的速度有限，收集范围较小；自动收集则利用网 络爬虫系统从互联网上自动收集网页，它自动访问万维网，沿着网页中含有的 u r l 爬到其它网页，并把爬过的网页收集回来，重复这一过程直到达到预先设 定的停止条件。 万维网是一个以网页为节点，超链接为边的有向图，搜索器在万维网中运 行可以看作是一个有向图的遍历过程。网页搜索策略可以分为深度优先、广度 优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入( t r a p p e d ) 问题， 目前常见的是广度优先和最佳优先方法。广度优先搜索策略是指抓取过程中， 在完成当前层次的搜索后，才进行下一层次的搜索。最佳优先搜索策略按照一 定的网页分析算法，预测候选u r l 与主题的相关性，并选取评价最好的一个或 几个u r l 进行抓取。它只访问经过网页分析算法预测为“有用”的网页，因此爬 虫抓取路径上的很多相关网页可能被忽略，是一种局部最优搜索算法。 下面重点研究网络爬虫的相关概念和工作机制。网络爬虫是一个从万维网 上自动提取网页的程序，它可以自动搜集网页，将网页上的相关数据保存起来。 它在互联网中漫游，发现和搜集信息，将分布在不同万维网服务器上的文档下 载到本地数据库中。由于互联网上的信息量大且更新快，因此判断网络爬虫性 能的重要依据是看它能否尽可能多、尽可能快地搜集各种类型的信息，是否能 够定期更新已经搜集过的旧信息，以避免死连接和无效连接。 网络爬虫收集信息的具体方式有两种。第一种是设定起始u r l ，从起始 u r l 开始，顺着网页中的超链接( h y p e r l i n k ) ，以广度优先或最佳优先方式循 环地在互联网中发现并收集信