《第八章相关排序与质量评估精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章相关排序与质量评估精选文档.ppt（119页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章相关排序与质量评估本讲稿第一页，共一百一十九页相关排序的概念n信息检索中的相关排序n信息检索系统返回结果的排序n各个条目的顺序反映了结果和查询的相关程度本讲稿第二页，共一百一十九页相关排序的概念n搜索引擎中的相关排序n反映多种因素的综合统计优先序n搜索引擎维护的内容十分繁杂且不规范，不像传统的图书、文献等有很好的分类体系管理n搜索引擎面对的用户背景广阔、层次多样，不像传统的图书馆所面对的用户通常有相对比较整齐的用户本讲稿第三页，共一百一十九页主要内容n传统IR的相关排序技术n链接分析与相关排序n相关排序的一种实现方案n搜索引擎系统质量评估本讲稿第四页，共一百一十九页主要内容n传统IR的相
2、关排序技术n链接分析与相关排序n相关排序的一种实现方案n搜索引擎系统质量评估本讲稿第五页，共一百一十九页布尔模型n文档表示n一个文档被表示为关键词的集合n查询式表示n查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序n匹配n一个文档当且仅当它能够满足布尔查询式时，才将其检索出来n检索策略基于二值判定标准本讲稿第六页，共一百一十九页布尔模型举例nQ=病毒AND（计算机OR电脑）ANDNOT医n文档：nD1:据报道计算机病毒最近猖獗nD2：小王虽然是学医的，但对研究电脑病毒也感兴趣nD3：计算机程序发现了艾滋病病毒传播途径n上述文档哪一个会被检索到？本
3、讲稿第七页，共一百一十九页布尔模型优点n到目前为止，布尔模型是最常用的检索模型，因为：n由于查询简单，因此容易理解n通过使用复杂的布尔表达式，可以很方便地控制查询结果n相当有效的实现方法n相当于识别包含了一个某个特定term的文档n经过某种训练的用户可以容易地写出布尔查询式n布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”本讲稿第八页，共一百一十九页布尔模型问题n布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回n非常刚性:“与”意味着全部;“或”意味着任何一个n很难控制被检索的文档数量n原则上讲，所有被匹配的文档都将被返回n很
4、难对输出进行排序n不考虑索引词的权重，所有文档都以相同的方式和查询相匹配n很难进行自动的相关反馈n如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？本讲稿第九页，共一百一十九页向量空间模型nGerard Salton在上世纪60年代提出的向量空间模型进行特征表达n成功应用于SMART（System for the Manipulation and Retrieval of Text）文本检索系统n这一系统理论框架到现在仍然是信息检索技术研究的基础本讲稿第十页，共一百一十九页n给定某个文档集合D，大小为M；设两篇文档 d1,d2 D，一个查询q，用什么来衡量“d1 与 d2 相比，
5、哪个和 q 更相关”n向量空间模型n该模型作出如下假设：n文档 d 和查询 q 的相关性可以由它们包含的共有词汇情况来刻画向量空间模型本讲稿第十一页，共一百一十九页n文档 d 和查询 q 被简化成词汇的集合（多重集）n为一个词典，ti 为词项，N为词典的规模nmi，ni（i=1，2，N）表示相应词项出现的次数，即词频。向量空间模型本讲稿第十二页，共一百一十九页n词项在文档和查询中出现的次数是一个基本量，称为“词频”模型n为简便起见，mi，ni值在集合0，1中取值，表示词项出现与否，不关心出现的次数，此时的模型称为“二元模型”n若一个词项 ti 在许多文档中出现，它对于不同文档的区分能力就不会很
6、强，因此它的权重应该相对较小向量空间模型本讲稿第十三页，共一百一十九页n文档频率DFnki 表示词项 ti 在文档集合 D 中涉及的文档个数，M 表示集合 D 的大小，则n倒置文档频率IDF向量空间模型本讲稿第十四页，共一百一十九页nTF*IDF词项权重n文档和查询的相关性变成了求 d 和 q 向量的距离向量空间模型本讲稿第十五页，共一百一十九页n文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”TF IDFTFIDFTFIDFTFIDF俄罗斯2较高高安全1中等高恐怖2较高高部门1较低低的2非常低很低加大1较低低频繁1较低低打击1中等高发生1较低低主义1较低低事件1较低
7、低力度1中等高文档的词项权重TF*IDF举例本讲稿第十六页，共一百一十九页IDF计算示例本讲稿第十七页，共一百一十九页模型中的问题n怎样确定文档中哪些词是重要的词？（索引项）n怎样确定一个词在某个文档中或在整个文档集中的重要程度？（权重）n怎样确定一个文档和一个查询式之间的相似度？本讲稿第十八页，共一百一十九页n若干独立的词项被选作索引项(index terms)or 词表vocabularyn索引项代表了一个应用中的重要词项n计算机科学图书馆中的索引项应该是哪些呢?体系结构总线计算机数据库.XML计算机科学文档集文档集中的索引项索引项的选择本讲稿第十九页，共一百一十九页n这些索引项是不相关的
8、(或者说是正交的)，形成一个向量空间vector spacen实际上，这些词项是相互关联的n当你在一个文档中看到“计算机”,非常有可能同时看到“科学”n当你在一个文档中看到“计算机”,有中等的可能性同时看到“商务”n当你在一个文档中看到“商务”，只有很少的机会同时看到“科学”“计算机”“科学”“商务”计算机科学文档集该文档集中的全部重要词项索引项的选择本讲稿第二十页，共一百一十九页由索引项构成向量空间n个索引项构成一个二维空间，一个文档可能包2个索引项2或0,1 含ndi)一个索引项也不包含(=ndj)包含其中一个索引项(=ndk)包含两个索引项(=n个索引项构n个索引项构成一个三维空间，3类
9、似的，维空间n成n个元素的线性组n一个文档或查询式可以表示为合本讲稿第二十一页，共一百一十九页n向量空间中的N个文档可以用一个矩阵表示n矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现 T1 T2 .TtD1 d11 d12 d1tD2 d21 d22 d2t:Dn dn1 dn2 dnt文档集一般表示本讲稿第二十二页，共一百一十九页举例:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T37325D1比D2更接近Q吗？怎
10、样衡量相似程度？夹角还是投影图示本讲稿第二十三页，共一百一十九页n相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：n两个文档之间（文本分类，聚类）n两个查询式之间（常问问题集）n一个查询式和一个文档之间（检索）n人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在相似度计算本讲稿第二十四页，共一百一十九页n术语权重的算法提高了检索的性能 n部分匹配的策略使得检索的结果文档集更接近用户的检索需求n可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序向量空间模型的优点本讲稿第二十五页，共一百一十九页n标引词之
11、间被认为是相互独立n随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大n隐含语义索引模型是向量空间模型的延伸向量空间模型的不足本讲稿第二十六页，共一百一十九页n传统IR方法的成功有两个重要的内在假设n被索引的信息本身有很高的质量，至少在信息的组织和内容上有着比较高的质量n很多IR产品都是针对特殊的领域n可以对这个领域进行算法的优化，避免了对一词多义的处理n检索信息的用户有一定的相关技能和知识n用户知道通过什么样的手段去提高检索的准确率n传统的IR系统总是提供一套相当复杂的检索语法来满足用户的不同要求传统IR的相关排序技
12、术本讲稿第二十七页，共一百一十九页n这些假设在web上已经不再成立nWeb上网页的质量参差不齐，大量的网页组织性、结构性比较差。同时，Web又是一个无所不包的载体，它涉及政治、经济、教育等各个层面nIR中的很多技术都没有了用武之地n网络上充斥着很多没有任何意义的网页、很多镜像的网页，如果不采取相应的技术处理，会影响检索的质量n大部分检索用户是没有任何经验的n通常只输入一个或者两个检索词来检索他们需要的网页，但会得到大量的返回结果，很难达到满意的程度n很少有用户愿意使用逻辑运算来提高检索的质量传统IR的相关排序技术本讲稿第二十八页，共一百一十九页n传统IR的相关排序技术n链接分析与相关排序n相关
13、排序的一种实现方案n搜索引擎系统质量评估主要内容本讲稿第二十九页，共一百一十九页nWeb的复杂性带来的机会n利用网页间的链接关系进行链接分析，量化网页信息n在web查询模式下产生了许多新的信息可以利用，如web用户行为信息链接分析与相关排序本讲稿第三十页，共一百一十九页n链接分析nHTML标签n标签能给我们提示其中文字的重要程度n比较大的字体往往是作者比较强调的内容n放在前面和中间的应该是作者比较强调的nAlta，infoseek等搜索引擎在网页的预处理阶段记录了这些信息用于结果的排序链接分析与相关排序本讲稿第三十一页，共一百一十九页n链接分析（续）n网页之间的超链接n链接反映的是网页之间形成
14、的“参考”、“引用”和“推荐”关系n如果一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应该是较重要的n网页的“出度”对分析网上信息的情况也很有意义的，因此可以同时考虑用两个指标来衡量网页n这些想法即是google和IBM（clever）小组提出PageRank 技术和 HITS 技术的基础链接分析与相关排序本讲稿第三十二页，共一百一十九页n“随机冲浪”模型（PageRank的理论基础）n用户随机的选择一个网页作为上网的起始网页n看完这个网页后，从该网页内所含的超链接内随机的选择一个页面继续进行浏览n沿着链接前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，
15、如此往复链接分析与相关排序本讲稿第三十三页，共一百一十九页n网页的权值（PageRank）n每个网页可能被访问到的次数越多就越重要n“可能被访问的次数”也就定义为网页的权值nwj 表示第 j 个网页的权值；nli,j 只取0、1，代表从网页 i 到网页 j 是否存在链接nni 代表网页 i 有多少个指向其他网页的链接nd 代表“随机冲浪”中沿着链接访问网页的平均次数链接分析与相关排序本讲稿第三十四页，共一百一十九页nHITS（Hyperlink-Induced Topic Search）n权威型网页（authority）n对于一个特定的检索，该网页提供最好的相关信息n目录型网页（hub）n该网
16、页提供很多指向其他高质量权威型网页的超链链接分析与相关排序本讲稿第三十五页，共一百一十九页n算法过程n利用检索的关键词得到一个网页的根集合n根据这个集合在整个网页有向图中的位置来扩展这个根集合n将被链接（包括链出和链入）的网页加入到这个根集合中，形成一个新的集合n依据指定的网页规模作扩展n得到这个集合后，计算集合中每个网页的目录型权值和权威型权值n按照这两个不同的权值，分别取出前 k 个结果返回给用户链接分析与相关排序本讲稿第三十六页，共一百一十九页nPageRank算法&HITS算法n利用了网页和超链组成的有向图，根据相互链接的关系进行递归的运算n运算的时机nPageRank在网页搜集告一段
17、落时，离线的使用一定的算法计算每个网页权值n速度快，但丧失了检索的灵活性nHITS采用即时分析运算策略，每得到一个检索，它都要从数据库中找到相应的网页和超链构成的有向子图，再运算获得各个网页的相应链接权值n灵活性强，更加精确；但效率较低链接分析与相关排序本讲稿第三十七页，共一百一十九页nWeb查询模式下的新信息n新出现的网页n尽管重要，但由于时间短，被链接的次数不可能很高nPageRank值就不会高n除网页本身的特性外n用户行为n新词的产生链接分析与相关排序本讲稿第三十八页，共一百一十九页n用户行为n用户经验少，但数量巨大nGoogle、AltaVista、百度、雅虎每天都有超过1000万次的
18、用户检索n可以从中获取许多有用的信息，这些信息可以大大提高搜索引擎检索结果的准确率，提高检索质量nDirect Hit技术就是基于该思想创立的链接分析与相关排序本讲稿第三十九页，共一百一十九页nDirect Hitn跟踪用户对检索结果的后继型为：n哪些站点被用户选择浏览了？n用户在这个站点上花费了多少时间？n根据统计结果，改变网页的权值n提高哪些经常被用户选择、花大量时间浏览站点的权值，降低哪些不太被用户关心的站点的权值n对于新加入系统的网页，系统则先给它们一个缺省的权值n对一个固定的用户的行为进行跟踪和统计，发现这个用户的喜好，从而产生专门针对该用户的检索结果（个性化检索）链接分析与相关排序
19、本讲稿第四十页，共一百一十九页n四种技术的比较n网页本身信息（Author）n超链接关系（Other Author）n人工编辑产生的目录系统（Editor）n用户行为（User）链接分析与相关排序本讲稿第四十一页，共一百一十九页n新词的产生n词典n传统的信息检索n信息资源相对稳定，信息内容相对成熟，词典也就相对稳定n网络环境下n时代感很强n如果词典中没有相应的词，就不可能（不能有效地）查到含有它们的网页。因此，获得新词，将它们及时加入到词典中，是维护搜索引擎的一个重要工作链接分析与相关排序本讲稿第四十二页，共一百一十九页词典在系统中的地位链接分析与相关排序本讲稿第四十三页，共一百一十九页n词典
20、的设计n采用Hash表来实现系统的词典nh_size 为Hash表的大小nFkey 为散列函数nDinput 为输入数据链接分析与相关排序本讲稿第四十四页，共一百一十九页n如何扩大词典的容量？n系统和外界数据的接口nWebn用户检索（天网选择用户的检索进行学习，扩大词典容量）n学习词汇是为了满足用户的检索需求，提高检索的质量n统计上看，web上的数据和用户检索的字符串有着很大的差别n用户输入的大部分是词汇和词汇组成的断语，经过简单的处理，可以方便的学习到新的词汇nWeb网页中的中文大部分是连写在一起的句子，很难从中提取新词链接分析与相关排序本讲稿第四十五页，共一百一十九页新词学习链接分析与相关
21、排序本讲稿第四十六页，共一百一十九页n词汇统计n复杂的逻辑检索n用户输入的检索有一部分是复杂的逻辑检索（大约20%），我们应该首先将这些带有逻辑运算符号的检索字符串转化为简单检索形式n中英文混合检索n检索中有大量的英文检索和中英文混合检索，我们这里处理的是中文新词的学习，因此我们要将所有的英文词汇过滤掉n新词的最大长度n对于过长的中文字符串，它是一个词汇的可能性极小。定义一个学习词汇的最大长度n，把所有检索字符串串长大于n的过滤掉n检索频率n我们对这些合法的“可能新词”进行学习，统计出每个词汇的检索频率链接分析与相关排序本讲稿第四十七页，共一百一十九页n词汇筛选n词频筛选n低频的检索排除在新词
22、之外n生僻词汇不必加入到新词词典中n检索时不小心的输入错误n搜狐搜虎n两个或多个合法词汇组成的短语，需要过滤掉，如“计算机网络”链接分析与相关排序本讲稿第四十八页，共一百一十九页新词学习对检索效率的影响链接分析与相关排序本讲稿第四十九页，共一百一十九页n传统IR的相关排序技术n链接分析与相关排序n相关排序的一种实现方案n搜索引擎系统质量评估主要内容本讲稿第五十页，共一百一十九页nURL权值的评价n对一个URL地址进行被链接次数的统计，确定该URL获得的其他网页的评价，Wln当一个网页属于重要网站时，赋予另外一个权值Wsn根据不同的编码类型，给相应的网页赋予编码权值Wc相关排序的一种实现方案本讲
23、稿第五十一页，共一百一十九页n形成网页中词项的基本权重n向量空间模型不能应用于搜索引擎系统n网页文本和正文信息最重要的区别在于HTML标签n有些标签影响文本的权值n、等n不影响文本权值的标签n、等相关排序的一种实现方案本讲稿第五十二页，共一百一十九页影响权值的HTML标签本讲稿第五十三页，共一百一十九页n一个特征项的权值nHTML标签影响的绝对权值n首先给每一个特征项赋予一个初始权值W0n如果一个特征项被其他有权标签包围，这些标签的权值会影响特征项的权值n例如：hello WBT=W0+Wt(H3)+Wt(b)相关排序的一种实现方案本讲稿第五十四页，共一百一十九页n网页大小对权值的影响n网页的
24、长度越长，特征项可能获得的权值n特征项出现频率对权值的影响n区分高频词和低频词对网页的影响程度nSmax表示最大的网页可索引文本大小nS(p)代表网页p的可索引文本大小nN代表被索引网页的总量nT(t)包含特征项t的网页数量相关排序的一种实现方案本讲稿第五十五页，共一百一十九页n归一化处理nWBmax代表对于所有k,p而言，WB(k,p)的最大值相关排序的一种实现方案本讲稿第五十六页，共一百一十九页n利用链接结构n网页之间的超链接是Web的基本特点n海量网页之间构成了一个巨大的有向图n我们更关心网页的入度（链接命中数，link hit number，LHN）相关排序的一种实现方案本讲稿第五十七
25、页，共一百一十九页n天网将网页的超链分为两类n链向本网站内部的网页超链（忽略）n链向其它网站上的网页的超链n通过统计发现，很多网站的页面都是运用一定的页面模版实现的n模版中会包含大量的该网站的索引超链，这些超链会跟随模版被继承到该网站的每一个网页中n有些大型网站的主页会被本站点的其他网页大量链接，而获得很高的LHN，尽管它有可能被极少的其他网站所链接n考虑网页编辑的欺骗行为n他们在一些网页中包含大量的不可见链接指向自己的页面相关排序的一种实现方案本讲稿第五十八页，共一百一十九页nLHN新网页的n新网页即使质量很高，知道它的网页编辑很少，只能得到很小值LHN的n补偿算法LHNnT(p)可以获得网
26、页的发布时间nT令当前的时间为nownT补偿的阈值时间为stn值LHN得到新的相关排序的一种实现方案本讲稿第五十九页，共一百一十九页n归一化nWLmax表示系统对所有的p的WL(p)的最大值相关排序的一种实现方案本讲稿第六十页，共一百一十九页n收集用户反馈信息n用户点击数（user hit number，UHN）n对于一个查询qn会得到很多检索结果网页p0,p1,p2,pnn假定检索 q 在一天内被提交了 m 次n定义检索 q 对应的一个网页 p 的UHN相关排序的一种实现方案本讲稿第六十一页，共一百一十九页n上述的方法忽略了返回结果中URL的位置信息n统计结果：47.3%的用户只访问搜索引擎
27、返回的第一页，12.2%的用户会继续访问第二页n一个结果在返回网页中的位置将会很大程度的影响用户点击的可能性n采用补偿算法来弥补这个缺陷n按照用户对每个返回页面访问的概率进行补偿相关排序的一种实现方案本讲稿第六十二页，共一百一十九页补偿因子定义表本讲稿第六十三页，共一百一十九页n考虑长时期的用户评价n考虑 n+1 天的数据nWUD0，WUD1，WUDnn存在的问题n用户在不同的时间感兴趣的网页是不同的n奥运前，用户关心的是奥运会的准备情况和参赛运动员情况n奥运后，用户关心的事世界纪录打破的情况、各个国家获得的奖牌数和排名情况相关排序的一种实现方案本讲稿第六十四页，共一百一十九页n衰减算法n衰减
28、系数 knk 值越大，先前的数据对结果的影响就越大nk=0，表示历史数据不被考虑nk=1，表示所有的历史数据都和现在的数据有相同的重要性n对于新的网页，需要考虑补偿相关排序的一种实现方案本讲稿第六十五页，共一百一十九页n计算最终的权重n计算每个网页和查询 q 的相关度n基本权值n链接权值n用户评价权值相关排序的一种实现方案本讲稿第六十六页，共一百一十九页n该方法的优点n几乎所有的网页拥有者，尤其是商业网站，期望他们的网页被排在搜索结果的前列n如果忽略一个站点内部的链接，这就使得网站的作者很难通过超链接权值对搜索引擎进行欺骗n用户评价也是一个容易被用来欺骗搜索引擎的特性相关排序的一种实现方案本讲
29、稿第六十七页，共一百一十九页n传统IR的相关排序技术n链接分析与相关排序n相关排序的一种实现方案n搜索引擎系统质量评估主要内容本讲稿第六十八页，共一百一十九页n评价一般是指评估某个系统的性能、某种产品的质量、某项技术的价值，或者是某项政策的效果等等n信息检索评价则是指对信息检索系统的性能（主要是其满足用户信息需求的能力）进行评估的活动n从信息检索系统诞生以来，对检索系统的评价就一直是推动其研究、开发与应用的一种主要力量评价本讲稿第六十九页，共一百一十九页n针对一个检索系统，可以从功能和性能两个方面对其进行分析评价n功能评价n可通过测试系统来判定是否支持某项功能，因此相对来说较容易n性能评价n对
30、于检索系统的性能来说，除了系统的时间和空间因素之外，要求检索结果能够按照相关度进行排序信息检索的评价本讲稿第七十页，共一百一十九页n相关度理论假定：对于一个给定的文档集合和一个用户查询，存在并且只存在一个与该查询相关的文档集合n检索系统的目标就在于检出相关文档而排除不相关文档相关度本讲稿第七十一页，共一百一十九页相关性是一种主观评价是不是正确的主题输入：“和服”；输出：“咨询和服务”由于分词错误，导致检索结果偏离主题是否满足用户特定的信息需求(information need)时效性，是不是新的信息输入：“美国总统是谁”；输出：“克林顿”信息已经过时权威性，是否来自可靠的信息源相关性本讲稿第七
31、十二页，共一百一十九页n相关性不是二值评价，而是一个连续的量n即使进行二值评价，很多时候也很难n从人的立场上看，相关性是：n主观的，依赖于特定用户的判断n和情景相关的，依赖于用户的需求n认知的，依赖于人的认知和行为能力n时变的，随着时间而变化评价IR系统的困难本讲稿第七十三页，共一百一十九页n检索性能的评价n检索结果的准确度n检索任务n批处理查询n交互式查询n实验室环境下主要是批处理查询，具有良好的可重复性和可扩展性检索的评价本讲稿第七十四页，共一百一十九页GRE词汇精选词汇精选考研考研毛主席语录毛主席语录PAIR：客户端个性化检索工具点击点击本讲稿第七十五页，共一百一十九页本讲稿第七十六页，
32、共一百一十九页n一个文档集合C。系统将从该集合中按照查询要求检出相关文档n一组用户查询要求q1,q2,qn。每个查询要求qi描述了用户的信息需求n对应每个用户查询要求的标准相关文档集R1,R2,Rn。该集合可由人工方式构造n一组评价指标。这些指标反映系统的检索性能。通过比较系统实际检出的结果文档集和标准的相关文档集，对它们的相似性进行量化，得到这些指标值评价和比较检索系统的检索性能需要以下条件：本讲稿第七十七页，共一百一十九页n在早期的检索实验集合中，相关性判断是全方位的，就是说，由专家事先对集合中每一篇文献与每一个主题的相关性做出判断n由于TREC 的文献集合如此庞大，全方位的判断是不可行的
33、。因此TREC相关性判断基于检索问题所来自的测试文档集合，并采用一种“pooling”的技术来完成相关性判断本讲稿第七十八页，共一百一十九页n假设绝大多数的相关文档都收录在这个文档池中n没有进行判断的文档即未被认为是不相关的n“pooling”技术的具体操作方法是：针对某一检索问题，所有参与其检索试验的系统分别给出各自检索结果中的前K个文档（例如K=100），将这些结果文档汇集起来，得到一个可能相关的文档池“pool”n由检索评价专家进行人工判断，最终评判出每一文档的相关性“Pooling”方法有以下两个假设本讲稿第七十九页，共一百一十九页相关文本相关文本检索出的检索出的文本文本全部文本集合全
34、部文本集合检出且相关未检出且相关检出且不相关未检出且不相关检出未检出相关不相关召回率(Recall)=检出的相关文档数/相关文档数准确率(Precision)=检出的相关文档数/检出文档数假设：文本集中所有文献已进行了检查准确率和召回率本讲稿第八十页，共一百一十九页101准确率召回率返回最相关的文本但是漏掉了很多相关文本理想情况返回了大多数相关文档但是包含很多垃圾准确率和召回率之间的关系本讲稿第八十一页，共一百一十九页nExampleRq=d3,d5,d9,d25,d39,d44,d56,d71,d89,d123n通过某一个检索算法得到的排序结果：1.d123 6.d9 11.d382.d84
35、7.d51112.d483.d56 8.d12913.d2504.d69.d18714.d1135.d8 10.d25 15.d3 (precision,recall)(100%,10%)(66%,20%)(50%,30%)(40%,40%)(33%,50%)举例本讲稿第八十二页，共一百一十九页n11个标准查全率水平所对应的查准率:0%,10%,20%,100%02040608010012020406080100120interpolationprecision一个查询的11个标准查准率本讲稿第八十三页，共一百一十九页n上述准确率召回率的值对应一个查询n每个查询对应不同的准确/召回率曲线n为了
36、评价某一算法对于所有测试查询的检索性能，对每个召回率水平下的准确率进行平均化处理，公式如下：Nq:the number of queries usedPi(r):the precision at recall level r for the i-th query平均准确率本讲稿第八十四页，共一百一十九页n对多个查询，进行平均，有时该曲线也称为：查准率/查全率的值n如下为两个检索算法在多个查询下的查准率/查全率的值n第一个检索算法在低查全率下，其查准率较高。n另一个检索算法在高查全率下，其查准率较高多个查询下进行检索算法的比较本讲稿第八十五页，共一百一十九页n合理估计需要了解集合的所有文献n这两
37、个指标相互关联，评价不同方面，结合在一起形成单个测度更合适n测的是批处理模式下查询集合性能，对现代信息检索系统，交互式是重要特征，对量化检索过程的性指标可能会更合适适应性本讲稿第八十六页，共一百一十九页n随着测试集规模的扩大以及人们对评测结果理解的深入，更准确反映系统性能的新评价指标逐渐出现n单值概括 新的评价指标本讲稿第八十七页，共一百一十九页n已检出的相关文献的平均准确率n逐个考察检出新的相关文献，将准确率平均nExample1.d123(1)6.d9 (0.5)11.d382.d84 7.d51112.d483.d56 (0.66)8.d12913.d2504.d6 9.d18714.d
38、1135.d8 10.d25 (0.4)15.d3 (0.3)(1+0.66+0.5+0.4+0.3)/5=0.57单值概括（1）本讲稿第八十八页，共一百一十九页nR-Precisionn计算序列中前R个位置文献的准确率nR指与当前查询相关的文献总数1.d123 6.d9 2.d847.d5113.d56 8.d1294.d69.d1875.d8 10.d25 R=10 and#relevant=4R-precision=4/10=0.41.d1232.d843.56 R=3 and#relevant=1R-precision=1/3=0.33单值概括（2）本讲稿第八十九页，共一百一十九页n准
39、确率直方图n多个查询的R-Precision测度n用来比较两个算法的检索纪录nRPA/B=0:对于第i个查询，两个算法有相同的性能nRPA/B0:对于第i个查询，算法A有较好的性能nRPA/B0:对于第i个查询，算法B有较好的性能单值概括（3）本讲稿第九十页，共一百一十九页0.00.51.01.5-0.5-1.0-1.512345678910Query Number28单值概括（3-1）本讲稿第九十一页，共一百一十九页n概括统计表n查询数n检出的所有文献数量n相关文献数n应检出的相关文献数n单值概括（4）本讲稿第九十二页，共一百一十九页前面提到的一些评价指标，如R-准确率，MAP，P10等，都
40、只考虑经过pooling技术之后判断的相关文档的排序对判断不相关文档与未经判断的文档的差别并没有考虑而目前随着互联网的发展，测试集越来越大，由于相关性判断还基本上是人工判断，因此建立完整的相关性判断变得越来越难评价指标的不足本讲稿第九十三页，共一百一十九页n只考虑对返回结果列表中的经过判断后的文档进行评价n在相关性判断完整的情况下，bpref具有与MAP相一致的评价结果n在测试集相关性判断不完全的情况下，bpref依然具有很好的应用n这个评价指标主要关心不相关文档在相关文档之前出现的次数。具体公式为：Bpref指标本讲稿第九十四页，共一百一十九页n下面举个例子来说明bpref的性能，假设检索结
41、果集S为：nS=D1,D2,D3*,D4*,D5,D6,D7,D8,D9,D10 n其中D2、D5 和D7是相关文档，D3 和D4为未经判断的文档。n对这个例子来说，nR=3;bpref=1/3(1-1/3)+(1-1/3)+(1-2/3)Bpref举例本讲稿第九十五页，共一百一十九页n对于搜索引擎系统来讲，由于没有一个搜索引擎系统能够保证搜集到所有的网页，所以召回率很难计算，因而准确率成为目前的搜索引擎系统主要关心的指标。n而当用户在使用Web搜索引擎的时候，用户常常在找到一个好的页面后就不再继续察看排序列表其他结果。n只找出一个相关的文档的高准确率就是信息检索系统的一个重要任务单一相关文档
42、检索的评价本讲稿第九十六页，共一百一十九页nRR（Reciprocal Ranking）是第一个相关文档出现位置的倒数n经常用于评价只找到一个相关文档的情况nRR值具体为1/r，其中r为第一个相关文档在结果中排序数n如果检索结果中没有相关文档，那么RR值为0RR排序倒数和MRR平均排序倒数本讲稿第九十七页，共一百一十九页nMRR是在RR的基础上对多个查询的RR结果取平均值。即对一个检索系统输入多个查询，分别得到每个查询的排序倒数，取平均即为MRR。计算公式如下：n例如MRR=0.25就意味着检索系统平均在返回结果的第四个位置找到相关文档n然而RR评价是基于2元相关判断基础上的，因此RR与MRR
43、都不能区分一个高相关性的文档与低相关性文档之间的区别MRR（Mean Reciprocal Ranking）平均排序倒数本讲稿第九十八页，共一百一十九页n调和平均值nR(j):the recall for the j-th document in the rankingnP(j):the precision for the j-th document in the ranking其它测度方法本讲稿第九十九页，共一百一十九页1.d1236.d9 11.d382.d847.d51112.d483.d56 8.d129 13.d2504.d69.d18714.d1135.d8 10.d25 15.d
44、3 (33.3%,33.3%)(25%,66.6%)(20%,100%)Example本讲稿第一百页，共一百一十九页nE指标n允许用户根据需要调整精确率和召回率的比例其它测度方法（cont.）本讲稿第一百零一页，共一百一十九页n面向用户的测度方法n覆盖率：实际检出的相关文献中用户一致的相关文献所占比例n新颖率：检出的相关文献中用户未知的相关文献所占的比例其它测度方法（cont.）本讲稿第一百零二页，共一百一十九页相关文献|R|结果集|A|用户已知的相关文献|U|检出的用户以前未知的相关文献|Ru|检出的用户已知的相关文献|Rk|覆盖率和新颖率（图示）本讲稿第一百零三页，共一百一十九页n组成要素
45、n文件集(Document Set;Document Collection)n查询问题(Query;Topic)n相关判断(Relevant Judgment)n用途n设计与发展:系统测试n评估:系统效能(Effectiveness)之测量n比较:不同系统与不同技术间之比较n评比n根据不同的目的而有不同的评比项目n量化的测量准则，如Precision与Recall测试集（Test Collection）本讲稿第一百零四页，共一百一十九页nTREC评测 n文本检索会议（Text Retrieval Conference，TREC）是信息检索(IR)界为进行检索系统和用户评价而举行的活动,它由美国
46、国家标准技术协会(NIST)和美国高级研究计划局(DARPA)（美国国防部）共同资助，开始于1992年。n NTCIR评测nNTCIR(NACSIS Test Collection for IR Systems)始于1998年，是由日本国立信息学研究所（National Institute of Informatics，简称NII）主办的搜索引擎评价型国际会议 nCLEF评测nCLEF于2000年开始筹办，是欧洲各国共同合作进行的一项长期研究计划，主要想通过评测信息科技技术，促进欧洲语言中的各种单一语言以及多语言信息技术的发展，nCLEF的目标只在于跨语言信息检索以及多语言信息检索方面 国外的
47、评测本讲稿第一百零五页，共一百一十九页nTREC:Text REtrieval Conference(http:/trec.nist.gov/)n1992年开始，每年一次n由美国国防部Defense Advanced Research Projects Agency(DARPA)和美国国家标准技术研究所National Institute of Standards and Technology(NIST)联合发起n参加者免费获得标准训练和开发数据n参加者在参加比赛时收到最新的测试数据，并在限定时间内作出答案，返给组织者n组织者对各参赛者的结果进行评价n包括检索、过滤、问答等多个主题TREC评测
48、（Benchmark）本讲稿第一百零六页，共一百一十九页Standard Generalized Mark-up Language,SGMLWSJ880406-0090AT&T Unveils Services to Upgrade Phone Networks Under Global Plan Janet Guyon(WSJ staff)American Telephone&Telegraph Co.introduced the first of a new generation of phone services with broad implications for computer
49、and communications.Document Format本讲稿第一百零七页，共一百一十九页n概括表统计n准确率-召回率平均值n文献级别平均值n平均准确率TREC会议评价测度本讲稿第一百零八页，共一百一十九页n全名：n863计划中文信息处理与智能人机接口技术评测n组织者：国家高技术研究发展计划（863计划）n方式n通过网络进行n各单位在自己的环境中运行参评系统n2005年11月召开研讨会n2005年度评测内容n机器翻译n信息检索n语音识别国内863评测介绍本讲稿第一百零九页，共一百一十九页国内863评测介绍 信息检索评测n项目：相关网页检索n任务定义：给定主题，返回数据中与该主题相关
50、的网页 n数据：CWT100g(中文Web测试集100g)n根据天网搜索引擎截止2004年2月1日发现的中国范围内提供Web服务的1,000,614个主机，从中采样17,683个站点，在2004年6月搜集获得5,712,710个网页（有效网页：5,594,521）n包括网页内容和Web服务器返回的信息n真实容量为90GB。本讲稿第一百一十页，共一百一十九页n主题主题（Topic）模拟了用户需求，由若干字段组成，描述了用户所希望检索的信息。主题和查询的区别在于：主题是对信息需求的陈述，查询则是信息检索系统的实际输入n主题由4个字段组成：n编号编号（num）n标题标题（title）n描述描述（de