（计算机软件与理论专业论文）基于序相关性的搜索结果质量评价.pdf

西华大学硕士学位论文 基于序相关性的搜索结果质量评价 计算机软件与理论 研究生王富贵指导教师杜亚军 为了从因特网海量的信息资源中方便、准确地找到所需要的信息，9 0 年 代中期人们发明了检索w w v 矿信息资源的搜索引擎技术。此后，出现了大量的 搜索引擎如谷歌、百度、m s n 、雅虎、搜搜、搜狗、中搜等。面对众多的搜 索引擎，我们应该用哪一个搜索引擎才会返回比较好质量的结果昵? 这就需要 对搜索引擎进行评价。1 9 9 5 ，人们开始了对搜索引擎的比较和评价。 本文把序的相关理论应用到对搜索结果质量评价中，进行了有益的探索和 研究，主要内容如下三方面： 1 ) 为了对搜索结果质量做一个客观的评价，本文提出了基于序相关性的客 观搜索结果质量评价。主要思想是是通过针对同样的查询词，把搜索引擎返回 的结果集间序的相关性作为搜索结果质量评价的一个指标。 2 ) 搜索引擎的最终目的是为了方便用户使用。如果用户能够快速地在搜索 结果页面找到适合自己的网页，就认为搜索引擎提供了比较好质量的结果。基 于这一思想，本文提出基于序相关性的主观搜索结果质量评价。 3 ) 基于形式概念分析的搜索结果质量评价。当用户输入查询词后，搜索结 果通常包含一些u r l 集合，以及对应的摘要信息。在搜索结果上提取形式背景。 在此基础上构成形式概念格。通过计算概念格之间的支持度来评价搜索结果质 量。在此基础上，本文提出基于形式概念格的搜索结果质量评价方法。 经过实验证实，以上三种基于序相关性的搜索结果质量评价方法，能够对 搜索结果质量进行公正的评价。可以把评价结果用于提高搜索引擎质量，以及 方便用户搜索引擎的选择。 关键词：搜索结果评价形式概念分析搜索a p i 概念格构建 第l 页 as e a r c hr e s u i te v a l u a t i o nb a s e d o nt h ec o r r e l a t i o no fo r d e r c o m p u t e rs o f t w a r ea n dt h e o r y m a s t e rd e g r e ec a n d i d a t e ：f u g u iw a n gs u p e r v i s o r ：y a j u n d u i no r d e rt of i n dt h ei n f o r m a t i o np e o p l e n e e d e df r o mt h ei n t e r n e te a s i l y a n d a c c u r a t e l y t h em i d 9 0 t sp e o p l ei n v e n t e ds e a r c he n g i n et e c h n o l o g y s i n c et h e n ，t h e e m e r g e n c co fal a r g en u m b e ro fs e a r c he n g i n e ss u c h a sg o o g l e ，b a i d u ，m s n ， y a h o o ，s o s o ，s o g o u ，a n ds oo n w i t hal a r g en u m b e r o fs e a r c he n g i n e s w es n o u l d u s eas e a r c he n g i n ew h i c hw i l l r e t u r nb e t t e rq u a l i t yr e s u l t ? t h i sr e q u i r e s a n e v a l u a t i o n0 fs e a r c he n g i n e s s i n c e1 9 9 5 ，p e o p l eb e g a nt oc o m p a r ea n de v a l u a t s e a r c he n 西n e h o w e v e r , d u et os e a r c he n g i n ef u n c t i o n a l i t ya n ds c a l e ，a sw e l l a st h e l a c ko ft e c h n i c a ls u p p o r t ，t oe v a l u a t et h ev a s tm a j o r i t yo fs e a r c he n g l n e s i ss t i l l d e s c r i p t i o nm ainly i l lt h i sp a p e f ，t h er e l e v a n to fs e q u e n c et h e o r yi sa p p l i e dt ot h ee v a l u a t l o no ft h e q u a l i t yo fs e a r c hr e s u l t s ，t h ec o n t e n t so f t h ef o l l o w i n gt h r e ea s p e c t s ： 1 1i no r d e rt om a k ea no b j e c t i v ee v a l u a t i o no ft h eq u a l i t yo f s e a r c hr e s u l t s ，a n o b i e c t i v es e a r c he v a l u a t i o nb a s e do nt h er e l e v a n c e o fo r d e rw a sp r o p o s d t h em a m i d e ai st h r o u g l lt h es a m eq u e r y , t h er e l e v a n c eo fs e q u e n c ea sa ni n d i c a t o r o fq u a l i t y a s s e s s m e n t 2 t h eu l t i m a t eg o a lo fs e a r c he n g i n ei sf o rt h ec o n v e n i e n c eo f u s e r s l lau s e f c a i lq u i c k l yf i n di nt h es e a r c hr e s u l t sp a g et o s u i tt h e i ro w n w e bp a g e st h a tt h e 3 ) a s e a r c hq u a l i t yb a s e do nf o r m a lc o n c e p ta n a l y s i sw a sp r o p o s e d w h e n t h eu s e ri n p u tq u e r y , t h es e a r c hr e s u l t st y p i c a l l yi n c l u d eac o l l e c t i o no fs o m eu r l , 一一 第1 i 页 两华大学硕+ 学位论文 a n dt h ec o r r e s p o n d i n gs u m m a r yi n f o r m a t i o n g e tt h ef o r mc o n t e x tf r o ms e a r c h r e s u l t s o nt h i sb a s i sc o n s t i t u t e saf o r mo fc o n c e p tl a t t i c e c a l c u l a t et h ed e g r e eo f s u p p o r tf o re a c hc o n c e p tl a t t i c e o nt h i sb a s i s ，t h i sp a p e r , t h ef o r mo fc o n c e p t l a t t i c eb a s e do nf c aw a sp r o p o s e d e x p e r i m e n tc o n f i r m e dt h a tt h et h r e eo r d e r sb a s e do nt h er e l e v a n c eo fs e a r c h r e s u l t sq u a l i t ye v a l u a t i o nm e t h o d s ，t h eq u a l i t yo fs e a r c hr e s u l t st oaf a i re v a l u a t i o n e v a l u a t i o nr e s u l t sc a nb eu s e dt oi m p r o v et h eq u a l i t yo fs e a r c he n g i n e s ，a sw e l la s u s e r - f r i e n d l ys e a r c he n g i n ec h o i c e k e y w o r d s ：e v a l u a t i o no fs e a r c hr e s u l t s ，s e a r c ha p i ，f o r m a lc o n c e p ta n a l y s i s ， c o n s t r u c tc o n c e p tl a t t i c e 第l l i 页 两华人学硕士学位论文 7 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位 或证书而使用过的材料。与本文一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名：电易在 导师签名： 扣广年 | 妒吩妒卞 【日i1 7 t c ， 月厂日 第6 9 页 两华大学硕+ 学位论文 8 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 印手段保存和汇编本学位论文。 本学位论文属于 1 、保密r - i ，在年解密后适用本授权书； 2 、不保密口，适用本授权书。 ( 请在以上口内划v ) 学位论文作者签名：妙秀丧 日期： 。，7 ， 第7 0 页 锄 也 参。 名、 签 ： 币 “ j 7 、-譬如 导期指日 西华大学硕十学位论文 1 引言 1 1 研究背景以及当前现状 为了从因特网海量的信息资源中方便、准确地找到所需要的信息，9 0 年 代中期人们发明了检索m 删信息资源的搜索引擎技术。此后，出现了大量的 搜索引擎如谷歌、百度、m s n 、雅虎、搜搜、搜狗、中搜等，面对众多的搜 索引擎，我们应该用哪一个搜索引擎才会返回比较好质量的结果呢? 这就需要 对搜索引擎进行评价。从1 9 9 5 年开始，人们开始了对搜索引擎的比较和评价 1 1 圳，但由于搜索引擎自身的功能和规模问题，以及缺少评价技术的支持，对 搜索引擎的评价绝大多数仍以描述为主。 搜索引擎作为在互联网上查询资源的重要工具，自它出现之同起就备受人 们的关注。人们认识到用搜索引擎组织查询网上信息资源是解决网络资源利用 的有效方式，因此许许多多的i s p ( i n t e m e ts e r v e rp r o v i d e r ) 投人大量的人力、物 力、财力去开发研究它。但由于每个搜索引擎的收录范围、查询理论、查询方 法等不尽相同，因而使得每个搜索引擎在查全率、查准率和易用性上差别很大。 搜索引擎检索结果的质量直接影响着检索效果，通过对搜索引擎查询结果的评 价，一方面能更好地了解搜索引擎的优劣，为用户选择合适的搜索引擎提供依 据，决定着用户从网上获取信息的成功与否；另一方面可以促进搜索引擎的提 供者改进服务标准。因此有必要对它们进行系统详细的分析对比和评价，以达 到帮助用户方便使用的目的，并为今后搜索引擎进行发展提供借鉴。搜索引擎 的质量评价一直是国内外搜索引擎研究的一个热点问题。 1 1 1搜索结果质量评价的研究背景 搜索引擎是用来帮助用户在互联网上快速地找到有用的信息。互联网上众 多搜索引擎它们采用不同的索引方法，具有不同的网页覆盖范围。通过一个搜 索引擎查找出最合适的搜索结果是往往很困难的。为此元搜索引擎( m s e ) 应 运而生。一个元搜索引擎一般包含若干独立搜索引擎作为搜索结果的提供源。 在用户提交查询给元搜索引擎后，根据各独立搜索引擎( s e ) 的查询关键字策 略，查询词被转换成若干子查询词，接着这些子查询词分别提交给各个独立搜 索引擎。元搜索引擎采用的某种聚合策略，聚合各个独立搜索引擎的搜索结果 第1 页 西华大学硕十学位论文 作为搜索的最终结果。因此，在元搜索引擎响应用户请求时，是否应该向所有 待选择的独立搜索引擎都发出请求；是否所有待选择的独立搜索引擎都应该设 置相同的响应参数，如最大响应时间、返回结果集中记录的条数以及最小相关 度等。不同搜索引擎在响应相同的用户请求时，所返回的网页集的质量是不同 的，因为每个搜索引擎它的索引库大小，采用的排序算法，在不同领域的查询 优势不同所造成的。 元搜索引擎，也叫集搜索引擎，是指在统一的用户查询界面与信息反馈的 形式下，共享多个搜索引擎的资源库为用户提供信息服务的系统。元搜索与一 般搜索引擎的最大不同在于它可以没有自己的资源库和机器人，它充当一个中 间代理的角色，接受用户的查询请求，将请求翻译成相应搜索引擎的查询语法。 在向各个搜索引擎发送查询请求并获得反馈之后，首先进行综合相关度排序， 然后将整理抽取之后的查询结果返回给用户。元搜索引擎查全率高、搜索范围 更多更大，查准率也并不低。 元搜索引擎包括w e b 服务器、结果数据库、检索式处理、w e b 处理接口、 结果生成等几个部分，其中用户通过w 曲服务器访问元搜索引擎，而元搜索引 擎则通过w e b 处理接口访问其它外部的搜索引擎。 用户通过w w w 服务访问元搜索引擎，向w 曲服务器提交查询词。当w e b 服务器收到查询请求时，先访问结果数据库，查看近期是否有相同的查询词， 如果有则直接返回保存的结果，完成查询；如果没有相同的查询词，就分析查 询词并转化成与所要查找各搜索引擎相应的查询词格式，然后送至w e b 处理接 口模块。 第2 页 舀华大学硕十学位论文 一棺索引墼1 查询 查询处l 理氐一桔索引擎2 服务 ： 上心 ， i i 接口 结罢形成i 扮索弓i 擎3 7 口1 、7 呐 i 、v ，人、 、r 拇索引擎n 、 数据 库 f i g u r e1 1t h es t r u c to fm e t as e a r c he n g i n 图1 1 元搜索引擎结构图 w e b 处理接口通过并行的方式同时查询多个搜索引擎，把所有的结果集中 到一起。根据各搜索引擎的重要性，以及所得结果的相关度，对结果进行抽取 并排序，生成最终结果返回给用户。同时，把结果存到自己的数据库里，以备 下次查询参考使用。 针对用户的某次查询，根据历史知识，如何预知哪些能返回较好结果的搜 索引擎，这被认为搜索引擎的选择问题。近来搜索引擎的选择问题成为一个研 究的热点。搜索引擎的选择问题的核心技术就是搜索引擎结果的质量评价问 题。搜索结果评价的意义就在于帮助用户利用合适的搜索引擎来检索信息。 1 1 2搜索结果质量评价的发展及研究现状 ( 1 ) 1 9 9 8 年，k r i s h n ab h a r a t 在文献h 1 中，作者描述了一个通过随机查询库 来评价搜索引擎的覆盖率与重叠率的统计方法。通过实验，测出h o t b o t 。 a l t a v i s t a ，e x c i t e ，a n di n f o s e e k ，在1 9 9 7 年1 0 月的索引库大小以及交替性。该方 法没有提供精确的值。但是使用某一个测试据源，作者测试1 9 9 7 年1 0 月h o t b o t ， a l t a v i s t a ，e x c i t e ，a n di n f o s e e k 索引的网页数量分别大约是7 7 m ，1 0 0 m ，3 2 m 和 第3 页 西华人学硕士学位论文 1 7 m ，总共有1 6 0 0 m 张网页。作者进一步推测1 0 月份的所有静态的与公共网络 的网页总数是2 0 0 m 张。最令人吃惊的发现是它们的重叠部分很小。不足总共 的1 4 ，大约2 2 m 张网页被这四个搜索引擎所索引。 ( 2 ) 1 9 9 9 年，m r h e n z i n g e r 在文献瞄1 中，作者利用随机在网络上爬行去获 取一个统一的网页样本。这个统一的样本是用来评价众多搜索引擎的索引库的 大小。索引库的大小是一个评估搜索引擎质量的一个直接方式。大的索引库， 意味着可以提供好的搜索结果。 ( 3 ) 2 0 0 0 年，l o n g z h o n gl i 在文献1 中，作者提出一个基于简单查询的搜索 结果精度的统计方法，这个方法包括相关评价与统计比较。在相关评价中，作 者提出两个排序算法，一个是建立向量空间模型的基于词的算法，另一个是新 的三级( t h r e e 1 e v e l ) 算法。在统计比较中，采用了一个统计尺度( p r o b a b i l i t yo f w i n ) ，用来对搜索引擎排序。 空间向量模型被广泛应用在传统信息检索领域。这个模型用向量表示网页 与查询词。每个网页，每个查询都通过一个m 维的向量来表示。m 是网页集合 中不重复词的个数。向量相似度函数，比如向量内积，可以用来计算网页与查 询词之间的相似度。利用新的三级排序算法去计算网页与查询短语的相关性。 这个方法包含两步：第一，在网页中出现精确查询词的个数，以及出现查询子 短语的个数。通过他们的加权求和得到一个粗约的得分，同时给长短语更高的 权重：第二，这个粗约的得分被转换成三级相关性得分，比如2 ( 相关) ，1 ( 不 太相关) ，0 ( 不相关) ，它们都是基于先前定义的阈值。 ( 4 ) 2 0 0 2 年，w e n s h e n gw u 在文献盯1 中，作者描述的统计模型表示为：为每 一个s e 返回结果集建立两个指标n o d o c ，a v g s i m ( n o d o c 表示相对一个用户请 求而言，一个搜索引擎数据库中所包含高相关度的网页的数目，a v g s i m 表示 高相关度网页的平均相似度) ，并通过它来表示每个结果集中高相关度的文章 数目以及高相关度文章的平均相似度( 相对于用户请求而言) 。该模型通过精确 的相关度数据分析来对s e 进行评价，这对于需要进行精确评价是很有帮助的： 但其缺点也很明显，因为需要通过精确计算来进行分析，故效率比较低，特别 是对各个s e 返回结果集的记录数变化比较大且需要进行快速处理的m s e 而言， 该模型是不理想的。 第4 页 西华大学硕十学位论文 ( 5 ) 2 0 0 5 年，m m s u f y a nb e g 在文献峭1 中，描述了基于用户行为的评价模 型。该模型与统计模型不同，用户模型将更多的因素转移到用户上来。该方法 通过对用户动作进行监听来实现对各个搜索引擎的评价，如：对各s e 搜索结果 网页的访问时间以及是否对该文章进行拷贝、打印、e m a i l 以及添加到收藏夹 等。这种模型充分考虑了以用户为中心的观点，且改变用户直接为s e 评价的 被动模型( 如提交表单) ，而是采用了监听用户动作来间接实现对搜索引擎的评 价，故它能更客观全面地反应用户对搜索引擎的评价。但该模型比较适合对高 级用户的动作进行评价，且不能提供像统计模型那样精确的评价。基本思想如 下：对于搜索结果中网页j 的重要性度量按网页的重要性从高到低排序，这个 形成的用户序p 与搜索引擎提供的原始序e ，通过s p e a r m a nf o o t r u l ed i s t a n c e 计 算它们之间的相关性，根据相关性的大小得到对搜索引擎的一个主观评价。 ( 6 ) 2 0 0 5 年，j u d i tb a r - h a n 在文献旧1 中，描述了对于同一查询词而言，比较 各个搜索引擎结果的序。这个方法只对出现在的搜索引擎结果集中的u r l 的比 较。例如用s p e a r m a nc o r r e l a t i o nc o e f f i c i e n t 方法比较两个搜索引擎之间的相关 性。作者通过1 5 个查询词的集合提交给4 个大的搜索引擎。通过实验发现不同 的搜索引擎通常采用不同的排序方法。 ( 7 ) 2 0 0 7 年，雷万保在文献n 们中，描述了基于结果集相关度的搜索引擎评 价主要是通过分析各个结果集之间的相关度来实现对各个结果集的评价。该模 型的立足点是：a 所有的结果集都应该是相对可靠的，每个结果集都可以作 为其它结果集分析的可信任参考点；b 每个结果集对其它结果集的影响与其 自身的重要度，对应结果集共同包含的文章个数及相应的文章出现的顺序等因 素有关；c 对于每次评价，每个结果集得到的信任度是由其它所有结果集信 任度共同作用的结果。 具体模型分析：对于某一用户请求而言，令s e l ，s e 2 分别为搜索引擎返回 的结果，而建立在排序关系r 1 ，r 2 上相应的有序列是l s e l ，l s e 2 , l s e l 2 是 s e ln s e 2 是建立在l s e 2 上的规则序列。例如l s e l = 【1 ，2 ，3 ，4 ，5 ，6 ，7 】 l s e 2 = 3 ，2 ，4 ，l ，7 ，8 ，9 】，贝i j l s e l 2 = 3 ，2 ，4 ，1 ，7 1 ，l s e 2 1 = 1 ，2 ，3 ，4 ，7 1 ；s p e a r m a n 相关分析 n o 】 第5 页 西华人学硕十学位论文 r s p e a r m a n ( l s e l 2 , l s e 2 1 ) 。1 - 6 _ l s 面e 丙l r s e ，z ( i ) ：t ( i ) 1 2 例如上式得r s p e a r m a n ( l s e l 2 ，l s e 2 1 ) = 0 3 ，即l s e l 2 和l s e 2 1 之间的相似度是o 3 。 依次计算搜索结果s e 。与其他搜索结果的相关性，最后求加权之和再取平均值 即得到对搜索引擎s e 。的一个基于搜索结果相关度的评价。 ( 8 ) 2 0 0 8 年4 月，基于用户群体行为分析的搜索引擎自动性能评价1 。清 华大学智能技术与系统国家重点实验室马少平提出基于用户群体行为分析的 搜索引擎自动性能评价系统( h t t p ：s e a r c h e t h u i r c n ) 。总体思路，因为个体 用户可能在点击过程中出现谬误，而用户群体的点击信息则是很大程度上可靠 的，通过统计用户群体的点击行为，进而对查询对应的结果进行标注。 现有的搜索结果评价主要分为两类n 刳，第一类可以称为基于统计模型的搜 索结果评价，这类模型主要根据搜索结果网页路径的序进行评价或者依据人工 访问这些链接判断搜索结果与查询词的相关性来评价；第二类被称为基于用户 的搜索结果评价，它根据用户在搜索结果上的一系列行为，比如说查看某个网 页、保存某个网页、打印某个网页等，从用户的满意度来对搜索引擎作相应的 评价；两者各有优缺点，都有待提高。 目前，搜索引擎评价主要有以下几种方式。 ( 1 ) 以描述为主的搜索引擎评价方式 以描述为主的搜索引擎评价方式大多从搜索引擎自身网上提供的说明或者 帮助手册上查看得到的信息，以及从用户个人的角度，个人对搜索使用感觉。 集中对某一个搜索引擎的特点及功能描述n 2 删，而对搜索引擎中比较重要的索 引算法，搜索算法并不特别涉及。由于测试的时候往往因为个体差异，因此对 于测试的结果也往往是评价者个人得出的结论，通常带有很主观的思想在里 面。另外还有对索引网页的数目、索引更新间隔、用户交互的友好程度等搜索 引擎实现的外围接口进行综合，作为评价标准。 ( 2 ) t r e c 进行的实际测试 由n i s t ( 美国国家标准技术局) 举办的文本信息检索会议( t e x tr e t r i e v a l c o n f e r e n c e ，t r e c ) 。由于t r e c 提供的测试数据在信息检索领域具有较高的 第6 页 西华人学硕十学位论文 可信度，利用这些测试数据进行搜索引擎的性能评价工作也开展得较多。澳大 利亚联邦科学与工业研究组织( c s i r o ) 研究员、t r e cw e bt r a c k 的组织者d a v i d h a w k i n g 与n i c kc r a s w e l l 在2 0 0 1 年召丌的w 1 0 会议上就报告了一个利用 t r f 8 和t r f 9 的测试数据进行搜索引擎( 包括c o o g l e 、l y c c e 等1 1 个搜索引 擎) 在线服务搜索性能比较的实验n 刳。当然，由于数据集内容差异很大。这些 测试数据并不能使用t r e c 给出的测试标准答案来进行评测。这就使这些测 试的可信度打了一些折扣。 ( 3 ) 搜索引擎的搜索结果相关性排序 当用户提交查询词给搜索引擎时，搜索引擎通过查找自己的索引库，再按 照自己特定的排序算法，把查询结果返回给用户。查询结果通常包含很多，而 真j 下与用户相关的结果只是查询结果中的很小一部分，用户通常只会查看搜索 引擎的前几页结果n 6 。2 0 1 。并且用户通常会按照结果的排序，会优先考虑排在搜 索结果前面的网页。用户希望首先能够阅读最相关、最有用的网页信息。从搜 索引擎是否能为用户提供好的搜索结果，作为对搜索引擎的评价。目前几乎所 有的研究都认为搜索引擎搜索结果的相关性排序是衡量搜索结果质量好坏的 一个重要指标乜1 。2 4 1 。所以每个搜索引擎都试图按相关度排序搜索结果。尽管如 此，搜索引擎输出的搜索结果离人们的期望仍有较大的出入，通常的情况很多 重要的信息排在搜索结果的后面。这是因为每个搜索引擎在专业度以及相关性 排序技术上采用的判断标准都不尽相同，而且每个搜索引擎在索引、排序算法 这些都是商业机密。随着网络信息量的不断增加，搜索引擎对信息有效性的判 断能力( 即搜索结果的相关性排序) 将取代其他指标成为搜索引擎质量的一个 极为重要的指标。 1 2 本文的内容安排 本文剩下的章节将组织如下 第2 章：基于序相关性的客观搜索结果质量评价主要是通过针对同样的查 询词，把搜索引擎返回的结果之问序的关系作为搜索结果质量评价的一个指 标。针对某查询词，如果某搜索引擎返回的结果中的前几个网页，也被大部分 第7 页 西华人学硕士学位论文 其他搜索引擎排在搜索结果的前面，那么我们就认为此搜索引擎的返回结果是 比较理想的。基于这一思想，提出基于序相关性的客观搜索结果质量评价方法。 搜索引擎的最终目的就是让用能方便查找网络信息。如果用户能够快速地 在搜索结果页面找到适合自己的网页，就认为搜索结果提供了比较好质量的结 果。搜索引擎返回了一个原始的序，用户的关注的网页也形成了一个序。通过 计算两个序之间的相似性，得到基于序相关性的主观搜索结果质量评价。 第3 章：当用户输入查询词后，搜索结果通常包含一些u r l 集合，以及对 应的摘要信息。在搜索结果上提取形式背景。令搜索结果u r l 为对象集合， u r l 对应的网页关键词为属性集合k e y w o r d ，u r l 与k e y w o r d 具有关系r 。在 此基础上形成形式概念格。通过计算概念格之间的支持度来评价搜索结果质 量。在此基础上，提出基于形式概念格的搜索结果质量评价方法。 第4 章：对本文的工作进行了总结和展望。 第8 页 西华人学硕士学位论文 2 基于序相关性的搜索结果质量评价 2 1 序的相关理论 首先，给出以下定义 定义1 1 给定论域u ，以及t u u 一个序列1 ，l = 【d 1 ，d 2 d 。】， d l d 2 - - d 州，这罩“ _ ”是丁上某种序关系。同样，对于ie u af ，令1 ( i ) 表示i 的位置。高的排序具有低的位置标识。我们可以给u 中的每一个元素一 个唯一标识。不了不失一般性，可得u = l ，2 ，3 ，i u | 定义2n 们( 信任和信任集) 设u ，v 为任意集合，l u ，l v 表示建立在某 种排序关系r l ，r 2 上的相应序列，l u = 【a 1 1 a 1 2 ，a 1 n 】， l v = a 2 1 ，a 2 2 ，a 2 m 】( 其中a l l a 1 2 a h ，a 2 1 a 2 2 a 2 m ) 。如果对任意 鸣e uf l y ( 1 sfs 2 ，1s _ sl e n g t h ( a i j 所属表的长度) ) ，则称，对于a 面而言， u 和v 是信任的。un y 就是相应的信任集。它表征的是两个集合中元素的重 叠率。 定义3 n 们( 规则序列) 设u l u 2 为任意集u ，u ，合，且，l u i ，l u 2 表示 建立在某种关系r 上的有序表。如果l u 2 中所有元素出现的顺序都与l u l 相 应的元素出现的顺序是严格一致的，则称l u 2 是l u l 的规则序列。如l u l = 【1 ，2 ，3 ，4 ，5 1 ，l u 2 = 1 ，3 ，5 】则l u 2 是l u i 的规则序列，又如l u i = 【1 , 2 ，3 ，4 ，5 】，l u 2 = 【1 ，4 ，3 】，此时l u 2 则不是。 定义4 陋1如果一个序列l 包含论域d 中的所有元素。那l 就是一个全序列。 定义5 阳1 部分序列某序列l 包含的元素为论域d 的严格子集，l 称作d 的一 个部分序列。此时有一个严格的不等式成立ill l u i 。 定义6 碡1 ( s p e a r m a nr a n ko r d e rc o r r e l a t i o nc o e f f i c i e n t ) 令全序列 第9 页 西华人学硕士学位论文 【a l ，a 2 ，a n 】与【b l ，b 2 ，b n 】为某查询词的两个序列。这全序列的s p e a r m a n r a n k o r d e rc o r r e l a t i o nc o e f f i c i e n t ( r s ) 为如下定义碑1 6 罗【z ( 口，) 一，( 6 ，) 】2 ， 。1 一 互! 一 5 n ( ，l2 1 ) t h es p e a r m a nr a n k o r d e r c o r r e l a t i o nc o e f f i c i e n t ( r s ) 方法是用来计算两个序列相 关性的方法。其中1 函数代表某元素在序列中的位置。r s 取值在一1 与1 之间。 当两个序列相同时，r s = 1 9 当两个序列相反时，r s = 1 2 2 基于序相关性客观搜索结果质量评价 2 2 1 基本思想 基于序相关性的客观搜索结果质量评价主要是通过分析各个结果集合之 间的相关度来实现对各个结果集评价。搜索结果集合之间的相关度是指当用户 提交一个查询词给若干搜索引擎之后，每个搜索引擎根据当前系统索引库的大 小，排序策略等把与用户查询词最接近的网页作为搜索结果返回给用户。每个 搜索引擎返回一个结果序，在这里只是计算搜索结果网页的顺序。此方法基于 以下三点是a ) 所有的结果集都应该是相对可靠的，每个结果集都可以作为对其 它结果分析的可信任参考点；b ) 每个结果集对其它结果集的影响与其自身的重 要度等因素有关；c ) 对于每次评价，每个结果集的信任度是由其它所有结果集 信任度的共同作用的结果。此理论的在现实中可以理解为，一个班有若干个同 学，现在要同学们自己在其中产生班长、副班长等职，每个同学得到一个表， 其中需要写上的是自己所认为的正班长的名字，以及副班长的名字。等大家填 好之后，就可以统计得到，正班长谁的票数最多，副班长谁的票数最多。最后 就产生了这个班的正副班长。 在这一部分主要讨论搜索引擎间的客观评价方法以及它的实现。当用户把 一个查询词提交给n + 1 个搜索引擎，s e o ，s e l s e n 为搜索引擎0 到n 的搜索 结果， l s e o ，l s e i l s e n 分别了为搜索引擎排序策略舶，r 1 ，心的序列。 用户在输入一个查询词递交给搜索引擎，一般只浏览前几页的结果，第一 页的搜索结果尤为重要哺，1 刀，因此只分析搜索引擎返回结果的第一页，一般包 第1 0 页 两华大学硕士学位论文 含1 0 条网页信息( 文后面提到的某搜索引擎的搜索结果都是指搜索结果的前 1 0 条结果) 。搜索引擎会根据自己的排序策略，按照和用户查询词的相关性把 网页进行排序。把和用户最相关的网页信息放在第一位。 因此在搜索结果的前1 0 条网页信息中。分别给每个网页信息一个权重。 例如，前1 0 条网页集合d = d o ，d 1 ，d 2 ，d 9 ) ，对应的网页权重为w = w o ，w 1 ，w 2 ，w 9 。比如令w o = l ，w l = o 9 ，w 2 - - 0 8 ，w 9 = 0 1 ，因w 5 s 此。例如 提交查询词q 给谷歌、百度、雅虎、m s n 、中搜、搜搜、 搜狗。得到 结果为如表2 1 所示，其中d i j 代表搜索引擎s e i 的搜索结果中的第i 条网页记录。 表2 1 对丁查询词q u r y ，每个搜索引擎的结果 谷t百鹰雅虎恻中撞蔑擅搜狗 付置0 收重坼 a - “o h b“ d - a - 位1 1 ，权t md n如d 蚰“ 健置9 权重呐 d _如d -“d -h 表2 2 针对查询词q u e r y 搜索结果评价表 谷t百度曩虎 m 刚 巾&蔑撞擅旁 证量。的直恃度 - - a _ - p q d ，d _ 州 _ 州d 由q 州m m a 州, t - ) 位置9 的支持度 _ p p 。i i d 曲鞠 l d 曲_ 啊m 蛐_ 啊啊暇d 时- p 啊d 神m l n a 啪, )o 叩d 曲 整体评情 a m m n t 谷呷州再_ 一叫雅 _ 弹州m s n q 州中_ 州擅“p 州擅 t l 度l虎搜擅l翔l 当提交查询词给测试的七个搜索引擎时，每个搜索引擎返回包含1 0 个网 页的集合，这1 0 个元素就是搜索结果第一页的1 0 个网页路径u r l 集合。提交 查询词给搜索引擎，搜索引擎通过自己特定的搜索算法，把索引库中网页按照 第1 1 页 西华大学硕士学位论文 与用户查询词相关度降序排列形成搜索结果。因此，在返回搜索结果页面的第 一条u r l ，是搜索引擎认为与此查询词最相关的网页；在搜索结果页面的最后 一条是搜索引擎认为在索引库中与查询词最不相关的网页。在搜索结果页面， 排在前面的网页，也往往是被用户最先查看的网页。 下面，某待测搜索引擎针对此次用户查询，返回的结果网页中，第一条 u r l 也被其他搜索引擎认为此u r l 与用户查询词比较相关而放在搜索结果的前 几位，这个待测的搜索引擎的返回结果第一条u r l 质量是比较好的。如果某待 测搜索引擎返回结果的第一条u r l ，在其他在待测搜索引擎返回结果排得比较 靠后，甚至不在其他搜索引擎返回结果里，就认为此搜索引擎的第一条u r l 质量是不太好的。 基于上面的思想，逐一分析某一搜索引擎返回结果的质量。分析第一个搜 索引擎的结果集合l s e o 。提取位置o 的网页信息d o o 根据前面的假设，其权 重为w o o 。下二步，在第二个搜索引擎结果l s e l 中是否存在d o o 一样的记录， 假设，l s e l 中第三条记录d 1 2 ，其对应权重为w 1 2 ，与o ss u p p o r t ( d ) 56d 0 0 是相同的网页；下一步，在第三个搜索0 ss u p p o r t ( d ) s 1 引擎结果l s e 2 中是否存在d 0 0 ，假设，l s e 3 中第四条记录d 2 3 ，其对应权重为w 2 3 ，与0 0 0 是相同 的网页。接下来，分别和搜索引擎结果l s e 3 、l s e 4 、l s e 5 、l s e 6 进行同样的 计算。可以得到第一个搜索引擎结果的第一条网页记录的一个支持度 s u p p o r t ( d o o ) = w 2 2 + w 3 3 + w n n 。如果在某个搜索引擎中没有出现d o o ，则计算支 持度的时候不考虑它。因为计算搜索引擎中某条u r l 的支持度时，只会考虑此 u r l 在其他6 个搜索引擎中的支持度，因此，得出。作规范化处理，令s u p p o r t ( d o o ) 除以6 ，使得。 上面的步骤得到了搜索引擎l s e 0 中位置o 的网页的支持度，接下来考虑 位置1 支持度，最后得到s u p p o r t ( d o o ，s u p p o r t ( d 0 2 ) ，s u p p o r t ( d o g ) 女l l 表2 2 。在 2 2 中s u p p o r t ( d 0 ) ，表示第i 个搜索引擎的第j 条网页记录的支持度值。 得到搜索引擎1 的一个支持度计算公式 塑 s u p p o r t ( l s e l ) a ( 木s u p p o r t ( d ) 4 - ) + 4 - w 0 9 * s u p p o r t ( d 0 9 ) ) ( 罗哪) 衙 第1 2 页 西华人学硕十学位论文 容易得0s s u pp d 厂f 化瓯) s1 证。如果网页在搜索结果中的位置比较靠 前，那么他对应的权重值也比较高，并且其他搜索引擎的越靠前的某网页与此 网页相同，那么s u p p o r t ( d o o ) 越大。所果所有的s u p p o r t ( d 0 0 ) 值都比较高，表示 搜索结果中的网页被大量搜索引擎所公认，其搜索结果支持度越高；反之，代 表其搜索结果支持度越低，意味着所提供的结果不被大多数搜索引擎所共识， 搜索质量不太理想。以下是程序逻辑实现。 2 2 2 程序逻辑 输入：查询词集合 输出：搜索结果质量客观评价值 过程： l查询词队列初始化 2 搜索引擎对象初始化： 3 三维数组s e a r c h r e s u l t 【i 】d 儿k 】用于存储第i 个查询词，第j 个搜索引擎，第 k 条记录 4 三维数组s e a r c h e v a l u a t i o n i y z 用于存储第i 个查询词，搜索引擎z 对搜 索引擎y 的支持度 5 一维数组s e e v a l u a t i o n r e u s l t 【i 】【j 】用于存储第i 个查询词时，搜索引擎j 的 客观评价值 6 提交查询词集合中的每一个查询词给待评价的搜索引擎 7因此步骤3 的中所有元素都被赋了值。 8 通过前面的方法我们可以对步骤4 中的所有元素赋值。 9最后，根据步骤8 的结果就可以对步骤5 中的所有元素赋值 2 3 基于序相关性主观搜索结果质量评价 2 3 1 基本思想 测量用户对搜索结果的满意度，通过观察用户搜索结果页面的行为，以此 理解用户的反馈。搜索结果的质量是一个很主观的，用户如何对搜索结果进行 第1 3 页 西华大学硕士学位论文 排序，很有必要获得用户的反馈信息，用户的反馈信息可以是显示的，也可以 是隐式的。显式反馈就是让用户在完成搜索后，填写表单的形式完成。直接通 过表单形式询问用户对网页的排序，很容易分析。通过分析用户的排列可以和 搜索结果的原始排序，得到一个相关因子，通过一个查询词集合，分别递交给 搜索引擎，然后用户在上面进行一些操作，记录下用户的行为，得到一组相关 因子，然后再求平均值，即可以通过这种方式得到搜索引擎的主观评价。通过 表单的显示用户行为获取的问题就是导致不关心的用户要么不仔细填写，要么 只填写一部分。 因此，本文认为隐式获取用户行为的必要性。获取用户在搜索结果页面上 的行为呻1 ，理解用户的反馈。基于序相关性的主观搜索结果质量评价主要是通 过测量用户对搜索结果的满意度，为此，需要监视用户在搜索结果页面的行为。 通过一组向量( v t e s ，b ，e ，c ) 来刻划用户的反馈行为，它包含如下： ( a ) 用户查看网页的顺序v ，v = ( v l ，v 2 ，v 3 ，v 。) 如果网页i 是第k 个被浏 览的网页，那么令v i - k 。用户进行下一次查询前没有点击过v i ，那么，令v i _ 1 。 ( b ) 用户查看网页i 所用的时间，定义t = ( t l ，t 2 , t 3 ，t n ) ，如果网页i 没有被用 户查看过，那么令t i = 0 。 ( c ) 用户是否打印网页i ，定义成一个布尔值，定义p = ( p l ，p 2 ，p 3 ，p n ) 。 ( d ) 用户是不保存网页i ，定义成一个布尔值，定义s = ( s l ，s 2 ，s 3 ，s n ) 。 ( e ) 用户