信息检索6-tfidf.ppt

1,第6讲 文档评分、词项权重计算及向量空间模型Scoring,Term Weighting&Vector Space Model,2017/9/19,2,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,3,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,4,Heaps定律词典大小的估计,词汇表大小M 是文档集规模T的一个函数 M=kTb图中通过最小二乘法拟合出的直线方程为：log10M=0.49 log10T+1.64于是有：M=101.64T0.49k=101.64 44 b=0.49,5,5,Zipf定律-倒排记录表大小的估计,反映词项的分布情况cfi*ic拟合度不是太高，但是今本反映词项的分布规律：高频词少，低频词多。,6,6,词典压缩-将整部词典看成单一字符串,7,7,词典压缩-单一字符串方式下按块存储,8,词典压缩-前端编码(Front coding),每个块当中(下例k=4)，会有公共前缀 8 a u t o m a t a 8 a u t o m a t e 9 a u t o m a t i c 10 a u t o m a t i o n可以采用前端编码方式继续压缩 8 a u t o m a t a 1 e 2 i c 3 i o n,9,9,倒排记录表压缩-对间隔编码,10,10,倒排记录表压缩-可变字节(VB)码,设定一个专用位(高位)c作为延续位(continuation bit)如果间隔表示少于7比特，那么c 置 1，将间隔编入一个字节的后7位中否则：将低7位放入当前字节中，并将c 置 0，剩下的位数采用同样的方法进行处理，最后一个字节的c置1（表示结束）比如，257=1 00000001=0000010 0000001 0000010 1000001被很多商用/研究系统所采用变长编码及对齐敏感性(指匹配时按字节对齐还是按照位对齐)的简单且不错的混合产物,11,11,倒排记录表压缩-编码,将整数G 表示成长度(length)和偏移(offset)两部分偏移对应G的二进制编码，只不过将首部的1去掉例如 13 1101 101=偏移长度部分给出的是偏移的位数比如G=13(偏移为 101),长度部分为 3长度部分采用一元编码:1110.G的编码就是将长度部分和偏移部分两者联接起来得到的结果。,12,12,Reuters RCV1索引压缩总表,13,13,本讲内容,对搜索结果排序(Ranking):为什么排序相当重要？词项频率(Term Frequency,TF):排序中的重要因子逆文档频率(Inverse Document Frequency,IDF):另一个重要因子Tf-idf 权重计算方法:最出名的经典排序方法向量空间模型(Vector space model):信息检索中最重要的形式化模型之一(其他模型还包括布尔模型、概率模型、统计语言建模模型等),14,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,15,15,布尔检索,迄今为止，我们主要关注的是布尔检索，即文档(与查询)要么匹配要么不匹配布尔检索的优点：对自身需求和文档集性质非常了解的专家而言，布尔查询是不错的选择对应用开发来说也非常简单，很容易就可以返回1000多条结果布尔检索的不足：对大多数用户来说不方便大部分用户不能撰写布尔查询或者他们认为需要大量训练才能撰写出合适的布尔查询大部分用户不愿意逐条浏览1000多条结果，特别是对Web搜索更是如此,16,16,布尔检索的其他不足:结果过少或者过多,布尔查询常常会导致过少(=0)或者过多(1000)的结果例子：查询 1(布尔与操作):standard user dlink 650 200,000 个结果 太多查询2(布尔与操作):standard user dlink 650 no card found 0 个结果 太少结论：在布尔检索中，需要大量技巧来生成一个可以获得合适规模结果的查询,17,17,排序式检索(Ranked retrieval),排序式检索会对查询和文档的匹配程度进行排序，即给出一个查询和文档匹配评分排序式检索可以避免产生过多或者过少的结果可以通过排序技术来避免大规模返回结果，比如只需要显示前10条结果，这样不会让用户感觉到信息太多用户满意的前提：排序算法真的有效，即相关度大的文档结果会排在相关度小的文档结果之前,18,18,排序式检索中的评分技术,我们希望，在同一查询下，文档集中相关度高的文档排名高于相关度低的文档如何实现？通常做法是对每个查询-文档对赋一个0,1之间的分值该分值度量了文档和查询的匹配程度,19,19,第一种方法:Jaccard系数,计算两个集合重合度的常用方法令 A 和 B 为两个集合Jaccard系数的计算方法:JACCARD(A,A)=1JACCARD(A,B)=0 如果 A B=0A 和 B 不一定要同样大小Jaccard 系数会给出一个0到1之间的值,A,B,20,20,Jaccard系数的计算样例,查询“ides of March”3月15日(朱利乌斯恺撒的殉难日)文档“Caesar died in March”JACCARD(q,d)=1/6,21,21,课堂练习,计算下列查询-文档之间的Jaccard系数q:information on cars d1:“all youve ever wanted to know about cars”q:information on cars d2:“information on trucks,information on planes,information on trains”q:red cars and red trucks d3:“cops stop red cars more often”,22,22,Jaccard系数的不足,不考虑词项频率，即词项在文档中的出现次数(后面会定义)一般而言，罕见词比高频词的信息量更大，Jaccard系数没有考虑这个信息没有仔细考虑文档的长度因素本讲义后面，我们将不考虑使用Jaccard系数来进行查询和文档的评分计算提醒：在第19讲Web网页查重，我们还会介绍大规模网页下的Jaccard系数计算问题（网页和网页之间的相似度）,23,Paul Jaccard(1868-1944),瑞士植物学家，ETH教授1894年毕业于苏黎世联邦理工学院ETH(出过包括爱因斯坦在内的21位诺贝尔奖得主)1901年提出Jaccard Index即Jaccard Coefficient(Jaccard系数)概念,24,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,25,25,查询-文档匹配评分计算,如何计算查询-文档的匹配得分？先从单词项查询(查询只包含一个词项)开始若该词项不出现在文档当中，该文档得分应该为0该词项在文档中出现越多，则得分越高这就是所谓词项频率(term frequency，简称tf)评分后面我们将给出多种评分的方法,26,26,二值关联矩阵,每篇文档可以看成是一个二值的向量 0,1|V|,27,27,非二值关联矩阵(词项频率),每篇文档可以表示成一个词频向量 N|V|,28,28,词袋(Bag of words)模型,不考虑词在文档中出现的顺序John is quicker than Mary 及 Mary is quicker than John 的表示结果一样这称为一个词袋模型(bag of words model,BOW模型)在某种意思上说，这种表示方法是一种“倒退”，因为位置索引中能够区分上述两篇文档本课程后部将介绍如何“恢复”这些位置信息这里仅考虑词袋模型,29,29,词项频率 tf,词项t的词项频率(以下简称词频)tft,d 是指t 在d中出现的次数，是与文档相关的一个量，可以认为是文档内代表度的一个量，也可以认为是一种局部信息。下面将介绍利用tf来计算文档评分的方法第一种方法是采用原始的tf值(raw tf)但是原始tf不太合适：某个词项在A文档中出现十次，即tf=10，在B文档中 tf=1，那么A比B更相关但是相关度不会相差10倍，即相关度不会正比于词项频率tf,30,30,一种替代原始tf的方法:对数词频,t 在 d 中的对数词频权重定义如下：tft,d wt,d:0 0,1 1,2 1.3,10 2,1000 4,等等文档-词项的匹配得分是所有同时出现在q和文档d中的词项的对数词频之和 t qd(1+log tft,d)如果两者没有公共词项，则得分为0,31,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,32,32,文档中的词频 vs.文档集中的词频,除词项频率tf之外，我们还想利用词项在整个文档集中的频率进行权重和评分计算,33,33,罕见词项所期望的权重,罕见词项比常见词所蕴含的信息更多考虑查询中某个词项，它在整个文档集中非常罕见(例如 ARACHNOCENTRIC).某篇包含该词项的文档很可能相关于是，我们希望像ARACHNOCENTRIC一样的罕见词项将有较高权重物以稀为贵！,34,34,常见词项所期望的权重,常见词项的信息量不如罕见词考虑一个查询词项，它频繁出现在文档集中(如 GOOD,INCREASE,LINE等等)一篇包含该词项的文档当然比不包含该词项的文档的相关度要高但是，这些词对于相关度而言并不是非常强的指示词于是，对于诸如GOOD、INCREASE和LINE的频繁词，会给一个正的权重，但是这个权重小于罕见词权重,35,35,文档频率(Document frequency,df),对于罕见词项我们希望赋予高权重对于常见词我们希望赋予正的低权重接下来我们使用文档频率df这个因子来计算查询-文档的匹配得分文档频率(document frequency,df)指的是出现词项的文档数目,36,36,idf 权重,dft 是出现词项t的文档数目dft 是和词项t的信息量成反比的一个值于是可以定义词项t的idf权重(逆文档频率):(其中N 是文档集中文档的数目)idft 是反映词项t的信息量的一个指标，是一种全局性指标，反应的是词项在全局的区别性。实际中往往计算log N/dft 而不是 N/dft，这可以对idf的影响有所抑制值得注意的是，对于tf 和idf我们都采用了对数计算方式,37,37,idf的计算样例,利用右式计算idft:,假设语料中文档数目N=1，000，000,38,38,idf对排序的影响,对于单词项查询,idf对文档排序没有任何影响idf 会影响至少包含2个词项的查询的文档排序结果例如，在查询“arachnocentric line”中,idf权重计算方法会增加arachnocentric的相对权重，同时降低 line的相对权重,39,39,文档集频率 vs.文档频率,词项t的文档集频率(Collection frequency，cf):文档集中出现的t词条的个数词项t的文档频率df:包含t的文档篇数为什么会出现上述表格的情况？即文档集频率相差不大，但是文档频率相差很大哪个词是更好的搜索词项？即应该赋予更高的权重上例表明 df(和idf)比cf(和“icf”)更适合权重计算,40,40,tf-idf权重计算,词项的tf-idf权重是tf权重和idf权重的乘积信息检索中最出名的权重计算方法注意：上面的“-”是连接符，不是减号其他叫法：tf.idf、tf x idf,41,41,tf-idf小结,词项t在文档d中的权重可以采用下式计算tf-idf权重随着词项频率的增大而增大(局部信息)随着词项罕见度的增加而增大(全局信息),42,42,课堂练习:词项、文档集及文档频率,df和cf有什么关系?tf和cf有什么关系?tf和df有什么关系？,43,提纲,上一讲回顾 排序式检索 词项频率 tf-idf权重计算 向量空间模型,44,44,二值关联矩阵,每篇文档表示成一个二值向量 0,1|V|,45,45,tf矩阵,每篇文档表示成一个词频向量 N|V|,46,46,二值 tfidf矩阵,每篇文档表示成一个基于tfidf权重的实值向量 R|V|,47,47,文档表示成向量,每篇文档表示成一个基于tfidf权重的实值向量 R|V|.于是，我们有一个|V|维实值空间空间的每一维都对应词项文档都是该空间下的一个点或者向量极高维向量：对于Web搜索引擎，空间会上千万维对每个向量来说又非常稀疏，大部分都是0,48,48,查询看成向量,关键思路1:对于查询做同样的处理，即将查询表示成同一高维空间的向量关键思路2:按照文档对查询的邻近程度排序邻近度=相似度邻近度 距离的反面回想一下，我们是希望和布尔模型不同，能够得到非二值的、既不是过多或也不是过少的检索结果这里，我们通过计算出相关文档的相关度高于不相关文档相关度的方法来实现,49,49,向量空间下相似度的形式化定义,先考虑一下两个点之间的距离倒数一种方法是采用欧氏距离但是，欧氏距离不是一种好的选择，这是因为欧氏距离对向量长度很敏感,50,50,欧氏距离不好的例子,尽管查询q和文档d2的词项分布非常相似，但是采用欧氏距离计算它们对应向量之间的距离非常大。,51,51,采用夹角而不是距离来计算,将文档按照其向量和查询向量的夹角大小来排序假想实验：将文档 d 复制一份加在自身末尾得到文档d.d 是d的两倍很显然，从语义上看，d 和 d 具有相同的内容两者之间的夹角为0，代表它们之间具有最大的相似度但是，它们的欧氏距离可能会很大,52,52,从夹角到余弦,下面两个说法是等价的：按照夹角从小到大排列文档按照余弦从大到小排列文档这是因为在区间0,180上，余弦函数cosine是一个单调递减函数,53,53,Cosine函数,54,54,查询和文档之间的余弦相似度计算,qi 是第i 个词项在查询q中的tf-idf权重di是第i 个词项在文档d中的tf-idf权重|和|分别是 和 的长度上述公式就是 和 的余弦相似度，或者说向量 和 的夹角的余弦,55,55,文档长度归一化,如何计算余弦相似度？一个向量可以通过除以它的长度进行归一化处理，以下使用L2（2范数）:这相当于将向量映射到单位球面上这是因为归一化之后:因此，长文档和短文档的向量中的权重都处于同一数量级前面提到的文档 d 和 d(两个d 的叠加)经过上述归一化之后的向量相同,56,56,归一化向量的余弦相似度,归一化向量的余弦相似度等价于它们的点积(或内积)如果 和 都是长度归一化后的向量,57,57,余弦相似度的图示,58,58,余弦相似度的计算样例,词项频率tf3本小说之间的相似度(1)SaS(理智与情感):Sense andSensibility(2)PaP(傲慢与偏见):Pride andPrejudice(3)WH(呼啸山庄):WutheringHeights,59,59,余弦相似度计算,词项频率 tf 对数词频（1+log10tf）,为了简化计算，上述计算过程中没有引入idf,60,60,余弦相似度计算,对数词频(1+log10tf)对数词频的余弦归一化结果,cos(SaS,PaP)0.789 0.832+0.515 0.555+0.335 0.0+0.0 0.0 0.94.cos(SaS,WH)0.79cos(PaP,WH)0.69cos(SaS,PaP)cos(SAS,WH)cos(PaP,WH),61,61,余弦相似度计算算法,假设数组Length预先存放了文档归一化因子，即二范式,62,夹角余弦相似度之外的其他相似度计算,考虑三个因素tf、idf、文档长度为什么长度因素很重要？长度长的文档词项也多长度长的文档TF高需要对长度进行规整/归一(normalization)处理！,63,课堂练习：余弦相似度的一个问题,查询 q:“anti-doping rules Beijing 2008 olympics”反兴奋剂计算并比较如下的三篇文档d1:一篇有关“anti-doping rules at 2008 Olympics”的短文档d2:一篇包含d1 以及其他5篇新闻报道的长文档，其中这5篇新闻报道的主题都与Olympics/anti-doping无关d3:一篇有关“anti-doping rules at the 2004 Athens Olympics”的短文档我们期望的结果是什么？如何实现上述结果？,64,回转归一化,余弦归一化对倾向于短文档，即对短文档产生的归一化因子太大，而平均而言对长文档产生的归一化因子太小于是可以先找到一个支点(pivot，平衡点)，然后通过这个支点对余弦归一化操作进行线性调整。效果：短文档的相似度降低，而长文档的相似度增大这可以去除原来余弦归一化偏向短文档的问题,65,65,预测相关性概率 vs.真实相关性概率,66,66,回转归一化(Pivot normalization),67,回转归一化:Amit Singhal的实验结果,结果第一行：返回的相关文档数目 结果第二行：平均正确率 结果第三行：平均正确率的提高百分比,68,Amit Singhal,1989年本科毕业于印度IIT(Indian Institute of Technology)Roorkee分校1996年博士毕业于Cornell University，导师是Gerard Salton其论文获得1996年SIGIR Best Student Paper Award2000年加入Google，2001年被授予Google Fellow称号Google 排序团队负责人,被财富杂志(Fortune,2010)誉为世界科技界最聪明的50个人之一,69,69,tf-idf权重计算的三要素,70,70,tf-idf权重机制举例,对于查询和文档常常采用不同的权重计算机制记法:ddd.qqq例如:lnc.ltn文档:对数tf，无idf因子，余弦长度归一化查询:对数tf，idf，无归一化文档当中不用idf结果会不会很差？查询:“best car insurance”文档:“car insurance auto insurance”,71,71,tf-idf 计算样例:Inc.Itn,查询:“best car insurance”.文档:“car insurance auto insurance”.,1/1.92 0.521.3/1.92 0.68 最终结果 wqi wdi=0+0+1.04+2.04=3.08,72,72,向量空间模型小结,将查询表示成tf-idf权重向量将每篇文档表示成同一空间下的 tf-idf权重向量计算两个向量之间的某种相似度(如余弦相似度)按照相似度大小将文档排序将前K（如K=10）篇文档返回给用户向量空间(检索)模型中包含一个向量表示模型，可以广泛用于其他领域，比如：判断论文抄袭、代码抄袭、图像相似度计算等等,73,Gerard Salton(1927-1995),信息检索领域的奠基人之一，向量空间模型的完善者和倡导者，SMART系统的主要研制者，ACM Fellow1958年毕业于哈佛大学应用数学专业，是Howard Aiken的关门博士生。Howard Aiken是IBM第一台大型机ASCC的研制负责人。Salton是康奈尔大学计算机系的创建者之一。,74,74,本讲内容,对搜索结果排序(Ranking):为什么排序相当重要？词项频率(Term Frequency,TF):排序中的重要因子Tf-idf 权重计算方法:最出名的经典排序方法向量空间模型(Vector space model):信息检索中最重要的形式化模型之一(其他模型还包括布尔模型和概率模型),75,75,本讲小结,tf，反映词项在文档内部的权重，局部权重idf，反映词项在文档集(文档间)的权重，全局权重tf-idf，综合以后反映词在文档中的权重长度因素，归一化,76,76,参考资料,信息检索导论第6、7章http:/ifnlp.org/ir向量空间入门Exploring the similarity space(Moffat and Zobel,2005)Okapi BM25(另外一种著名的权重计算方法,信息检索导论节),77,课后练习,有待补充,