第3章 搜索引擎能评价.doc

第3章 搜索引擎性能评价搜索引擎的性能评价是性能改进的重要环节。“实验”、“评价”、“改进”三者间的关系如下图所示。搜索引擎系统评价 客观、公平、全面。 借鉴信息检索的Cranfield评价体系，结合互联网应用特点，总结出了一些评价方案。3.1 搜索引擎评价与 Cranfield 评价体系搜索引擎评价的角度 商业市场角度：通过用户使用调查，获取评价数据，形成市场调查、行业发展、市场监测报告； 学术研究角度，基于信息检索评价技术框架的搜索引擎性能评价。信息检索评价 检索效果(Effectiveness)、效率 (Efficiency); 信息检索系统评价主要针对检索效果(Effectiveness)而非效率 (Efficiency);对搜索引擎系统的评价，也主要针对检索效果(Effectiveness)。相关研究 1955年，Kent提出了“准确率/召回率”的信息检索评价框架； 20世纪50年代末到60年代，英国Cranfield工程建立了基于查询样例集、正确答案集、语料库的评测方案。其评价方法一般称为Cranfield方法框架。Cranfield体系的三个环节： 查询样例集合确定：抽取最能表示用户信息需求的一部分查询样例，构建一个规模恰当的集合； 正确答案集合标注：针对查询样例集合，在语料库中寻找对应的答案； 将查询样例集合、语料库输入检索系统，系统反馈检索结果，利用评价指标对检索系统结果和正确答案的接近程度进行评价，给出用数值表示的评价结果。Cranfield体系的四个因素： 语料库集合； 查询样例集合； 正确答案集合； 评价指标。使用Cranfield评价体系评价搜索引擎 不需准备专门的语料库集合； 对搜索引擎系统，语料库集合就是万维网数据的全体； 搜索引擎可利用网页抓取子系统自行获取万维网数据。 需要构建查询样例集合、正确答案集合、评价指标。3.2 查询样例集合构建定义：查询样例集合是评价搜索引擎性能时，模拟用户实际需求提出的查询(query)集合。查询样例集合构建的三原则：真实性、代表性、信息需求表述的完整性。1 查询样例集合构建的真实性构建查询样例集合时采用真实的搜索引擎用户查询 反映用户的真实信息需求； 保证评价的结果与用户的真实感受相吻合。国内外的信息检索系统评测，重视查询样例集合真实性 文本信息检索会议(TREC)采用微软 Live 或 Yahoo ！等搜索引擎提供的真实查询样例； 北京大学网络中心组织的搜索引擎与网络信息挖掘(SEWM )评测也采用了来自天网搜索引擎的真实查询样例。获取真实的搜索引擎用户日志有困难，解决办法 通过搜索引擎公开发布的用户行为日志样例来获取真实查询； 借助搜索引擎提供的热门查询展示服务来获取真实的用户查询。/具有足够的代表性吗？2 查询样例集合构建的代表性代表性是指构建的查询样例集合要能够反映用户群体的查询偏好 人力、物力资源的限制，构建的查询样例集合规模不能太大 如何用少量的查询样例集合代表大多数用户的查询偏好？ 需分析搜索引擎用户查询频率的分布情况。搜索引擎处理的用户查询数目十分庞大 2003年，谷歌每日处理的查询请求数达到2.5 亿个。 本书作者对某中文搜索引擎网站一个月内的部分查询日志进行了分析，结果表明，这部分查询日志的查询请求数达到了10多亿个。这些数量庞大的查询请求并非两两不同，而是集中在若干个查询上。 作者分析的搜索引擎查询日志中，“百度”这一查询的查询请求次数就达18 万次以上。 观察查询频率的分布时发现，查询频率最高的一部分查询集中了大多数的用户查询请求。 查询日志涉及的独立查询数共1500万个，查询频度最高的10000个查询就集中了超过56的用户查询请求。 说明搜索引擎查询频度的分布符合“二八定律”。用户查询频率的分布规律的存在： 使用高频查询样例集合代表大多数用户的查询请求； “搜索风云榜”的存在，使得既具有合理性，也具有可行性。缺点：查询样例集合构建没顾及查询频度低的用户查询。最好，既控制好样例集合的规模，又保证各种查询频度的用户查询数据能够被采样到。3 查询样例集合构建中信息需求表述的完整性搜索引擎交互方式“关键词查询选择性浏览”特点、原因 用户用简单的关键词作为查询提交给搜索引擎； 用户希望少用键盘输人、多用鼠标点击进行交互； 80的英文用户，95以上的中文用户不用“高级查询”功能； 查询所包含的平均词数为 3.11个 搜索引擎不是反馈检索目标页面，而是可能的检索目标页面列表；难以通过简单的关键词准确的理解用户的查询意图，只能将有可能满足用户需求的结果集合以列表的形式返回，无法提供准确的检索目标。 用户浏览列表，选择满足信息需求的内容、浏览。搜索引擎用户信息需求的类别：导航类：用户检索时具有确定的检索目标页面，目的是查找某个已知存在的页面资源。 “清华大学本科招生网”： “导航类”信息需求信息类：用户检索时没有确定的检索目标页面，目的是查找与某个主题相关的信息。 “手足口病症状”： “信息类”信息需求。事务类：用户检索时没有确定的检索目标页面，目的是查找与某个特定需求相关的资源。 “潜伏在线观看”： “事务类”信息需求例：同一个“魔兽争霸”查询请求，三种可能性都存在。问题： 同一个查询请求，有可能信息需求却截然不同。 这对搜索引擎处理用户查询造成了很大的困难； 对构建查询样例集合的过程设置了障碍。如果没有确定用户的信息需求，则无法准确地确定用户的查询目标页面。解决的办法：( l)尽量选取信息需求描述得比较明确的用户查询。 “清华大学本科招生网”：是明确的“导航类”信息需求; “潜伏在线观看”：是明确的“事务类”信息需求; “手足口病症状”：是“信息类”信息需求。但应在满足“真实性”和“代表性”的前提下进行。(2)对查询样例集合的信息需求类别加以规定。TREC :Home Page Finding(主页查找)、 Named Page Finding(命名网页查找)子任务是针对“导航类”信息需求设定的评测任务；Topic Distillation(主题提取)子任务则是针对“信息类”需求而设定的评测任务。国内的 SEWM 评测也沿袭了这一评测体系，将评测任务分为主题提取和导航搜索两个子任务。( 3) 可以对每个查询的信息需求给予详细的描述。构建查询样例集合时，不仅可以列出查询文本，而且还可以撰写对应查询的信息需求描述，以便在进行后续的目标页面集合构建时有章可循。根据研究，导航类、信息类、事务类信息需求在用户使用搜索引擎行为中的比例约为 20%、50%、30%，查询样例集合中相应信息需求样例的比例要符合这个比例关系。3.3 正确答案集合构建定义：正确答案集合就是对应查询样例集合的目标页面集合。Cranfield 评测方法中，正确答案是依照查询样例从语料库集合中标注出满足查询样例信息需求的文档（或网页）。查询样例 网页对搜索引擎的性评价任务，语料库集合为全体万维网数据。2002年，Web有100亿静态页面、1500亿动态页面。TREC统计，在800万文档集合上，针对1个查询样例的正确答案评判，需9个人月。那么对100亿静态页面进行针对一个查询样例的标注，需要一千个人年。TREC的“结果池过滤技术”( pooling technology)(l)根据数据规模的大小，选择适当的查询结果集合规模N。(2)对于某个查询样例Q，使用不同的待评测系统(T1，T2，Tn)对大规模文档集合进行检索，并分别得出各自的查询结果集合(RC1，RC2，RCn) ，其中| RCi |= N , ( i = 1，2，n)。(3)构建结果池， pool = RC1 RC2 RCn。(4)对上述结果池中的结果进行标注，其中符合查询样例Q的信息需求的集合即为Q的正确答案集合。3.4 搜索引擎评价指标传统信息检索系统的评价指标为“准确率/召回率”（“查准率/查全率”）。定义如下两个文档集合：Retrieved集合，待评测检索系统处理查询样例后返回的结果集合。 Relevant集合，正确答案集合。准确率( Precision ，查准率)定义为：准确率衡量的是检索系统所返回的结果列表中正确答案的比例召回率(Recall ，查全率)定义为：召回率衡量的是正确答案集合中有多大比例的答案在检索系统返回的结果列表中。检索系统的准确率、召回率同时都高： 大部分正确答案被检索系统找到； 返回的结果列表中非正确答案较少。提高准确率与提高召回率，存在一定矛盾：搜索引擎性能评价中常用的评价指标。1. 前n选精度( Precision at n , Pn )搜索引擎返回的结果序列前n位结果中正确答案的比例。例: P10=0.4 表示在搜索引擎系统返回的前10篇结果文档中有4篇是正确答案。由于导航类信息需求对应的正确答案唯一，因此 P n 指标通常用来评测信息类或者事务类查询的性能。2. 前n选成功率( Success at n , Sn)搜索引擎结果序列的前n篇结果文档中是否有正确答案。例如 S 10=1 :前10个结果中有某个结果是正确答案，可以满足用户需求。S 10 =0：前10个结果中没有正确答案。不存在 S10的数值既不为1，也不为0的情况。3 首现正确答案排序倒数(Reciprocal Rank of First Correct Answer , RR)定义：首现正确答案排序倒数（RR）是指检索系统返回的结果序列中第一个满足用户需求文档出现序号的倒数。RR=1表示检索系统返回的结果中，第一个结果就满足用户需求。RR通常用来评价导航类信息需求的性能，因为这类信息需求对应的查询样例只要有一个正确答案就可以满足用户需求。例：下图的三个结果序列，正确答案出现的数目，以及除排名最靠前的正确答案之外的正确答案在结果序列中的排序都是一致的，其差别只在于首次出现的正确答案的结果排序。“首现正确答案排序”分别为 1、2、3 ，其对应的“首现正确答案排序倒数”分别为1、0.5、0.33。4. 平均准确率(Average Precision , AP)定义：平均准确率(AP)是指检索系统返回每一个正确答案文档时准确度的平均值例：下图两个结果序列，正确答案文档数目为 6 ，通过评价”前N位”结果构成的结果集合对应的”准确率/召回率”可以得到图中所示的准确率和召回率数值。结果序列1中第 1、3、4、5、6、10位为正确答案文档。准确率的平均值：