现代信息检索导论-王斌-计算所-课件-lecture6-tfidf

IntroductiontoInformationRetrieval现代信息检索中国科学院大学2013年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第6讲文档评分、词项权重计算及向量空间模型Scoring,TermWeighting&VectorSpaceModel12013/9/9提纲2❶上一讲回顾❷排序式检索❸词项频率词项频率❹tf-idf权重计算❺向量空间模型提纲3❶上一讲回顾❷排序式检索❸词项频率词项频率❹tf-idf权重计算❺向量空间模型现代信息检索Heaps定律词汇表大小M是文档集规模T的一个函数图中通过最小二乘法拟合出的直线方程为：log10M=0.49∗log10T+1.64于是有：M=101.64T0.49k=101.64≈44b=0.494现代信息检索5Zipf定律反映词项的分布拟合度不是太高，但是今本反映词项的分布规律：高频词少，低频词多。5现代信息检索6将整部词典看成单一字符串(Dictionaryasastring)6现代信息检索7单一字符串方式下按块存储7现代信息检索8对间隔编码8现代信息检索9可变字节(VB)码被很多商用/研究系统所采用变长编码及对齐敏感性(指匹配时按字节对齐还是按照位对齐)的简单且不错的混合产物设定一个专用位(高位)c作为延续位(continuationbit)如果间隔表示少于7比特，那么c置1，将间隔编入一个字节的后7位中否则：将低7位放入当前字节中，并将c置0，剩下的位数采用同样的方法进行处理，最后一个字节的c置1（表示结束）9现代信息检索10ϒ编码将G表示成长度(length)和偏移(offset)两部分偏移对应G的二进制编码，只不过将首部的1去掉例如13→1101→101=偏移长度部分给出的是偏移的位数比如G=13(偏移为101),长度部分为3长度部分采用一元编码:1110.于是G的ϒ编码就是将长度部分和偏移部分两者联接起来得到的结果。10现代信息检索11ReutersRCV1索引压缩总表11现代信息检索12本讲内容对搜索结果排序(Ranking):为什么排序相当重要？词项频率(TermFrequency,TF):排序中的重要因子Tf-idf权重计算方法:最出名的经典排序方法向量空间模型(Vectorspacemodel):信息检索中最重要的形式化模型之一(其他模型还包括布尔模型和概率模型)12提纲13❶上一讲回顾❷排序式检索❸词项频率❹tf-idf权重计算❺向量空间模型现代信息检索14排序式检索(Rankedretrieval)迄今为止，我们主要关注的是布尔查询文档要么匹配要么不匹配对自身需求和文档集性质非常了解的专家而言，布尔查询是不错的选择对应用开发来说也非常简单，很容易就可以返回1000多条结果然而对大多数用户来说不方便大部分用户不能撰写布尔查询或者他们认为需要大量训练才能撰写合适的布尔查询大部分用户不愿意逐条浏览1000多条结果，特别是对Web搜索更是如此14现代信息检索15布尔搜索的不足:结果过少或者过多布尔查询常常会倒是过少(=0)或者过多(1000)的结果查询1(布尔与操作):[standarduserdlink650]→200,000个结果–太多查询2(布尔与操作):[standarduserdlink650nocardfound]→0个结果–太少在布尔检索中，需要大量技巧来生成一个可以获得合适规模结果的查询15现代信息检索16排序式检索排序式检索可以避免产生过多或者过少的结果大规模的返回结果可以通过排序技术来避免只需要显示前10条结果不会让用户感觉到信息太多前提：排序算法真的有效，即相关度大的文档结果会排在相关度小的文档结果之前16现代信息检索17排序式检索中的评分技术我们希望，在同一查询下，文档集中相关度高的文档排名高于相关度低的文档如何实现？通常做法是对每个查询-文档对赋一个[0,1]之间的分值该分值度量了文档和查询的匹配程度17现代信息检索18查询-文档匹配评分计算如何计算查询-文档的匹配得分？先从单词项查询开始若该词项不出现在文档当中，该文档得分应该为0该词项在文档中出现越多，则得分越高后面我们将给出多种评分的方法18现代信息检索19第一种方法:Jaccard系数计算两个集合重合度的常用方法令A和B为两个集合Jaccard系数的计算方法:JACCARD(A,A)=1JACCARD(A,B)=0如果A∩B=0A和B不一定要同样大小Jaccard系数会给出一个0到1之间的值19现代信息检索20Jaccard系数的计算样例查询“idesofMarch”文档“CaesardiedinMarch”JACCARD(q,d)=1/620现代信息检索21Jaccard系数的不足不考虑词项频率，即词项在文档中的出现次数罕见词比高频词的信息量更大，Jaccard系数没有考虑这个信息没有仔细考虑文档的长度因素本讲义后面，我们将使用(即余弦计算)来代替|A∩B|/|A∪B|，前者进行的长度归一化21现代信息检索PaulJaccard(1868-1944)瑞士植物学家，ETH教授1894年毕业于苏黎世联邦理工学院ETH(出过包括爱因斯坦在内的21位诺贝尔奖得主)1901年提出JaccardIndex即JaccardCoefficient概念22提纲23❶上一讲回顾❷排序式检索❸词项频率❹tf-idf权重计算❺向量空间模型现代信息检索24二值关联矩阵每篇文档可以看成是一个二值的向量∈{0,1}|V|24AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...111011111110000000011011001100100111010010现代信息检索25非二值关联矩阵(词频)每篇文档可以表示成一个词频向量∈N|V|25AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...15742320572273157227100000000031022008100100511000085现代信息检索26词袋(Bagofwords)模型不考虑词在文档中出现的顺序JohnisquickerthanMary及MaryisquickerthanJohn的表示结果一样这称为一个词袋模型(bagofwordsmodel)在某种意思上说，这种表示方法是一种“倒退”，因为位置索引中能够区分上述两篇文档本课程后部将介绍如何“恢复”这些位置信息这里仅考虑词袋模型26现代信息检索27词项频率tf词项t的词项频率tft,d是指t在d中出现的次数下面将介绍利用tf来计算文档评分的方法第一种方法是采用原始的tf值(rawtf)但是原始tf不太合适：某个词项在A文档中出现十次，即tf=10，在B文档中tf=1，那么A比B更相关但是相关度不会相差10倍相关度不会正比于词项频率tf27现代信息检索28一种替代原始tf的方法:对数词频t在d中的对数词频权重定义如下：tft,d→wt,d:0→0,1→1,2→1.3,10→2,1000→4,等等文档-词项的匹配得分是所有同时出现在q和文档d中的词项的对数词频之和t∈q∩d(1+logtft,d)如果两者没有公共词项，则得分为028现代信息检索29课堂练习计算下列查询-文档之间的Jaccard系数q:[informationoncars]d:“allyou’veeverwantedtoknowaboutcars”q:[informationoncars]d:“informationontrucks,informationonplanes,informationontrains”q:[redcarsandredtrucks]d:“copsstopredcarsmoreoften”29提纲30❶上一讲回顾❷排序式检索❸词项频率❹tf-idf权重计算❺向量空间模型现代信息检索31文档中的词频vs.文档集中的词频除词项频率tf之外，我们还想利用词项在整个文档集中的频率进行权重和评分计算31现代信息检索32罕见词项所期望的权重罕见词项比常见词所蕴含的信息更多考虑查询中某个词项，它在整个文档集中非常罕见(例如ARACHNOCENTRIC).某篇包含该词项的文档很可能相关于是，我们希望像ARACHNOCENTRIC一样的罕见词项将有较高权重32现代信息检索33常见词项所期望的权重常见词项的信息量不如罕见词考虑一个查询词项，它频繁出现在文档集中(如GOOD,INCREASE,LINE等等)一篇包含该词项的文档当然比不包含该词项的文档的相关度要高但是，这些词对于相关度而言并不是非常强的指示词于是，对于诸如GOOD、INCREASE和LINE的频繁词，会给一个正的权重，但是这个权重小于罕见词权重33现代信息检索34文档频率(Documentfrequency,df)对于罕见词项我们希望赋予高权重对于常见词我们希望赋予正的低权重接下来我们使用文档频率df这个因子来计算查询-文档的匹配得分文档频率指但是出现词项的文档数目34现代信息检索35idf权重dft是出现词项t的文档数目dft是和词项t的信息量成反比的一个值于是可以定义词项t的idf权重:(其中N是文档集中文档的数目)idft是反映词项t的信息量的一个指标实际中往往计算[logN/dft]而不是[N/dft]，这可以对idf的影响有所抑制值得注意的是，对于tf和idf我们都采用了对数计算方式35现代信息检索36idf的计算样例利用右式计算idft:36词项dftidftcalpurniaanimalsundayflyunderthe1100100010,000100,0001,000,000643210现代信息检索37idf对排序的影响idf会影响至少包含2个词项的查询的文档排序结果例如，在查询“arachnocentricline”中,idf权重计算方法会增加ARACHNOCENTRIC的相对权重，同时降低LINE的相对权重对于单词项查询,idf对文档排序基本没有任何影响37现代信息检索38文档集频率vs.文档频率词项t的文档集频率(Collectionfrequency):文档集中出现的t词条的个数词项t的文档频率:包含t的文档篇数为什么会出现上述表格的情况？即文档集频率相差不大，但是文档频率相差很大哪个词是更好的搜索词项？即应该赋予更高的权重上例表明df(和idf)比cf(和“icf”)更适合权重计算38单词文档集频率文档频率INSURANCETRY104401042239978760现代信息检索39tf-idf权重计算词项的tf-idf权重是tf权重和idf权重的乘积信息检索中最出名的权重计算方法注意：上面的“-”是连接符，不是减号其他叫法：tf.idf、tfxidf39现代信息检索40tf-idf小结词项t在文档d中的权重可以采用下次计算tf-idf权重随着词项频率的增大而增大随着词项罕见度的增加而增大40现代信息检索41课堂练习:词项、文档集及文档频率df和cf有什么关系?tf和cf有什么关系?tf和df有什么关系？41统计量符号定义词项频率