信息檢索6-tfidf

1、Introduction to Information Retrieval 現(xiàn)代信息檢索現(xiàn)代信息檢索中國(guó)科學(xué)院大學(xué)2017年秋季課程現(xiàn)代信息檢索 更新時(shí)間： Modern Information Retrieval*改編自”An introduction to Information retrieval”網(wǎng)上公開(kāi)的課件，地址 /IR-book/第6講 文檔評(píng)分、詞項(xiàng)權(quán)重計(jì)算及向量空間模型Scoring, Term Weighting & Vector Space Model12017/9/19提綱2 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-i

2、df權(quán)重計(jì)算 向量空間模型提綱3 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-idf權(quán)重計(jì)算 向量空間模型 現(xiàn)代信息檢索Heaps定律詞典大小的估計(jì) 詞匯表大小M 是文檔集規(guī)模T的一個(gè)函數(shù) M = kTb 圖中通過(guò)最小二乘法擬合出的直線(xiàn)方程為： log10M = 0.49 log10T + 1.64 于是有：M = 101.64T0.49k = 101.64 44 b = 0.494現(xiàn)代信息檢索 5Zipf定律-倒排記錄表大小的估計(jì)反映詞項(xiàng)的分布情況cfi*ic擬合度不是太高，但是今本反映詞項(xiàng)的分布規(guī)律：高頻詞少，低頻詞多。5現(xiàn)代信息檢索 6詞典壓縮-將整部詞典看成單一字符串6現(xiàn)代信息檢索 7詞典

3、壓縮-單一字符串方式下按塊存儲(chǔ)7 現(xiàn)代信息檢索詞典壓縮-前端編碼(Front coding) 每個(gè)塊當(dāng)中 (下例k = 4)，會(huì)有公共前綴 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 可以采用前端編碼方式繼續(xù)壓縮 8 a u t o m a t a 1 e 2 i c 3 i o n8現(xiàn)代信息檢索 9倒排記錄表壓縮-對(duì)間隔編碼9現(xiàn)代信息檢索 10倒排記錄表壓縮-可變字節(jié)(VB)碼 設(shè)定一個(gè)專(zhuān)用位 (高位) c作為延續(xù)位(continuation bit) 如果間隔表示少于7比特，那

4、么c 置 1，將間隔編入一個(gè)字節(jié)的后7位中 否則：將低7位放入當(dāng)前字節(jié)中，并將c 置 0，剩下的位數(shù)采用同樣的方法進(jìn)行處理，最后一個(gè)字節(jié)的c置1（表示結(jié)束） 比如，257=1 00000001 = 0000010 0000001 0000010 1000001 被很多商用/研究系統(tǒng)所采用 變長(zhǎng)編碼及對(duì)齊敏感性(指匹配時(shí)按字節(jié)對(duì)齊還是按照位對(duì)齊)的簡(jiǎn)單且不錯(cuò)的混合產(chǎn)物10現(xiàn)代信息檢索 11倒排記錄表壓縮-?編碼 將整數(shù)G 表示成長(zhǎng)度(length)和偏移(offset)兩部分 偏移對(duì)應(yīng)G的二進(jìn)制編碼，只不過(guò)將首部的1去掉 例如 13 1101 101 = 偏移 長(zhǎng)度部分給出的是偏移的位數(shù) 比如G

5、=13 (偏移為 101), 長(zhǎng)度部分為 3 長(zhǎng)度部分采用一元編碼: 1110. G的?編碼就是將長(zhǎng)度部分和偏移部分兩者聯(lián)接起來(lái)得到的結(jié)果。11現(xiàn)代信息檢索 12Reuters RCV1索引壓縮總表12現(xiàn)代信息檢索 13本講內(nèi)容 對(duì)搜索結(jié)果排序(Ranking) : 為什么排序相當(dāng)重要？ 詞項(xiàng)頻率(Term Frequency, TF): 排序中的重要因子 逆文檔頻率(Inverse Document Frequency, IDF): 另一個(gè)重要因子 Tf-idf 權(quán)重計(jì)算方法: 最出名的經(jīng)典排序方法 向量空間模型(Vector space model): 信息檢索中最重要的形式化模型之一 (

6、其他模型還包括布爾模型、概率模型、統(tǒng)計(jì)語(yǔ)言建模模型等)13提綱14 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-idf權(quán)重計(jì)算 向量空間模型現(xiàn)代信息檢索 15布爾檢索 迄今為止，我們主要關(guān)注的是布爾檢索，即文檔(與查詢(xún))要么匹配要么不匹配 布爾檢索的優(yōu)點(diǎn)： 對(duì)自身需求和文檔集性質(zhì)非常了解的專(zhuān)家而言，布爾查詢(xún)是不錯(cuò)的選擇 對(duì)應(yīng)用開(kāi)發(fā)來(lái)說(shuō)也非常簡(jiǎn)單，很容易就可以返回1000多條結(jié)果 布爾檢索的不足： 對(duì)大多數(shù)用戶(hù)來(lái)說(shuō)不方便 大部分用戶(hù)不能撰寫(xiě)布爾查詢(xún)或者他們認(rèn)為需要大量訓(xùn)練才能撰寫(xiě)出合適的布爾查詢(xún) 大部分用戶(hù)不愿意逐條瀏覽1000多條結(jié)果，特別是對(duì)Web搜索更是如此15現(xiàn)代信息檢索 16布爾檢索的其他

7、不足: 結(jié)果過(guò)少或者過(guò)多 布爾查詢(xún)常常會(huì)導(dǎo)致過(guò)少(=0)或者過(guò)多(1000)的結(jié)果 例子： 查詢(xún) 1 (布爾與操作): standard user dlink 650 200,000 個(gè)結(jié)果 太多 查詢(xún)2 (布爾與操作): standard user dlink 650 no card found 0 個(gè)結(jié)果 太少 結(jié)論： 在布爾檢索中，需要大量技巧來(lái)生成一個(gè)可以獲得合適規(guī)模結(jié)果的查詢(xún)16現(xiàn)代信息檢索 17排序式檢索(Ranked retrieval) 排序式檢索會(huì)對(duì)查詢(xún)和文檔的匹配程度進(jìn)行排序，即給出一個(gè)查詢(xún)和文檔匹配評(píng)分 排序式檢索可以避免產(chǎn)生過(guò)多或者過(guò)少的結(jié)果 可以通過(guò)排序技術(shù)來(lái)避免大規(guī)

8、模返回結(jié)果，比如只需要顯示前10條結(jié)果，這樣不會(huì)讓用戶(hù)感覺(jué)到信息太多 用戶(hù)滿(mǎn)意的前提：排序算法真的有效，即相關(guān)度大的文檔結(jié)果會(huì)排在相關(guān)度小的文檔結(jié)果之前17現(xiàn)代信息檢索 18排序式檢索中的評(píng)分技術(shù) 我們希望，在同一查詢(xún)下，文檔集中相關(guān)度高的文檔排名高于相關(guān)度低的文檔 如何實(shí)現(xiàn)？ 通常做法是對(duì)每個(gè)查詢(xún)-文檔對(duì)賦一個(gè)0, 1之間的分值 該分值度量了文檔和查詢(xún)的匹配程度18現(xiàn)代信息檢索 19第一種方法: Jaccard系數(shù) 計(jì)算兩個(gè)集合重合度的常用方法 令 A 和 B 為兩個(gè)集合 Jaccard系數(shù)的計(jì)算方法: JACCARD (A, A) = 1 JACCARD (A, B) = 0 如果 A B

9、 = 0 A 和 B 不一定要同樣大小 Jaccard 系數(shù)會(huì)給出一個(gè)0到1之間的值19AB現(xiàn)代信息檢索 20Jaccard系數(shù)的計(jì)算樣例 查詢(xún) “ides of March” 3月15日(朱利烏斯愷撒的殉難日) 文檔 “Caesar died in March”JACCARD(q, d) = 1/620現(xiàn)代信息檢索 21課堂練習(xí) 計(jì)算下列查詢(xún)-文檔之間的Jaccard系數(shù) q: information on cars d1: “all youve ever wanted to know about cars” q: information on cars d2: “information o

10、n trucks, information on planes, information on trains” q: red cars and red trucks d3: “cops stop red cars more often”21現(xiàn)代信息檢索 22Jaccard系數(shù)的不足 不考慮詞項(xiàng)頻率 ，即詞項(xiàng)在文檔中的出現(xiàn)次數(shù)(后面會(huì)定義) 一般而言，罕見(jiàn)詞比高頻詞的信息量更大，Jaccard系數(shù)沒(méi)有考慮這個(gè)信息 沒(méi)有仔細(xì)考慮文檔的長(zhǎng)度因素 本講義后面，我們將不考慮使用Jaccard系數(shù)來(lái)進(jìn)行查詢(xún)和文檔的評(píng)分計(jì)算 提醒：在第19講Web網(wǎng)頁(yè)查重，我們還會(huì)介紹大規(guī)模網(wǎng)頁(yè)下的Jaccard系數(shù)計(jì)算問(wèn)

11、題（網(wǎng)頁(yè)和網(wǎng)頁(yè)之間的相似度）22 現(xiàn)代信息檢索Paul Jaccard(1868-1944) 瑞士植物學(xué)家，ETH教授 1894年畢業(yè)于蘇黎世聯(lián)邦理工學(xué)院ETH(出過(guò)包括愛(ài)因斯坦在內(nèi)的21位諾貝爾獎(jiǎng)得主) 1901年提出Jaccard Index即Jaccard Coefficient(Jaccard系數(shù))概念23提綱24 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-idf權(quán)重計(jì)算 向量空間模型現(xiàn)代信息檢索 25查詢(xún)-文檔匹配評(píng)分計(jì)算 如何計(jì)算查詢(xún)-文檔的匹配得分？ 先從單詞項(xiàng)查詢(xún)(查詢(xún)只包含一個(gè)詞項(xiàng))開(kāi)始 若該詞項(xiàng)不出現(xiàn)在文檔當(dāng)中，該文檔得分應(yīng)該為0 該詞項(xiàng)在文檔中出現(xiàn)越多，則得分越高 這就是所

12、謂詞項(xiàng)頻率詞項(xiàng)頻率 (term frequency，簡(jiǎn)稱(chēng)tf)評(píng)分 后面我們將給出多種評(píng)分的方法25現(xiàn)代信息檢索 26二值關(guān)聯(lián)矩陣每篇文檔可以看成是一個(gè)二值的向量 0, 1|V|26Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .111011111110000000011011001100100111010010現(xiàn)代信息檢索 27非二值關(guān)聯(lián)矩陣(詞項(xiàng)頻率) 每篇文檔可以表示成一個(gè)詞頻向量

13、N|V|27Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .15742320572273157227100000000031022008100100511000085現(xiàn)代信息檢索 28詞袋(Bag of words)模型 不考慮詞在文檔中出現(xiàn)的順序 John is quicker than Mary 及 Mary is quicker than John 的表示結(jié)果一樣 這稱(chēng)為一個(gè)詞袋模型

14、(bag of words model, BOW模型) 在某種意思上說(shuō)，這種表示方法是一種“倒退”，因?yàn)槲恢盟饕心軌騾^(qū)分上述兩篇文檔 本課程后部將介紹如何“恢復(fù)”這些位置信息 這里僅考慮詞袋模型28現(xiàn)代信息檢索 29詞項(xiàng)頻率 tf 詞項(xiàng)t的詞項(xiàng)頻率(以下簡(jiǎn)稱(chēng)詞頻) tft,d 是指t 在d中出現(xiàn)的次數(shù)，是與文檔相關(guān)的一個(gè)量，可以認(rèn)為是文檔內(nèi)代文檔內(nèi)代表度表度的一個(gè)量，也可以認(rèn)為是一種局部信息局部信息。 下面將介紹利用tf來(lái)計(jì)算文檔評(píng)分的方法 第一種方法是采用原始的tf值(raw tf) 但是原始tf不太合適： 某個(gè)詞項(xiàng)在A文檔中出現(xiàn)十次，即tf = 10，在B文檔中 tf = 1，那么A比B

15、更相關(guān) 但是相關(guān)度不會(huì)相差10倍，即相關(guān)度不會(huì)正比于詞項(xiàng)頻率tf29現(xiàn)代信息檢索 30一種替代原始tf的方法: 對(duì)數(shù)詞頻 t 在 d 中的對(duì)數(shù)詞頻權(quán)重定義如下： tft,d wt,d : 0 0, 1 1, 2 1.3, 10 2, 1000 4, 等等 文檔-詞項(xiàng)的匹配得分是所有同時(shí)出現(xiàn)在q和文檔d中的詞項(xiàng)的對(duì)數(shù)詞頻之和 t qd (1 + log tft,d ) 如果兩者沒(méi)有公共詞項(xiàng)，則得分為030提綱31 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-idf權(quán)重計(jì)算 向量空間模型現(xiàn)代信息檢索 32文檔中的詞頻 vs. 文檔集中的詞頻 除詞項(xiàng)頻率tf之外，我們還想利用詞項(xiàng)在整個(gè)文檔集中的頻率進(jìn)行

16、權(quán)重和評(píng)分計(jì)算32現(xiàn)代信息檢索 33罕見(jiàn)詞項(xiàng)所期望的權(quán)重 罕見(jiàn)詞項(xiàng)比常見(jiàn)詞所蘊(yùn)含的信息更多 考慮查詢(xún)中某個(gè)詞項(xiàng)，它在整個(gè)文檔集中非常罕見(jiàn) (例如 ARACHNOCENTRIC). 某篇包含該詞項(xiàng)的文檔很可能相關(guān) 于是，我們希望像ARACHNOCENTRIC一樣的罕見(jiàn)詞項(xiàng)將有較高權(quán)重 物以稀為貴！33現(xiàn)代信息檢索 34常見(jiàn)詞項(xiàng)所期望的權(quán)重 常見(jiàn)詞項(xiàng)的信息量不如罕見(jiàn)詞 考慮一個(gè)查詢(xún)?cè)~項(xiàng)，它頻繁出現(xiàn)在文檔集中 (如 GOOD, INCREASE, LINE等等) 一篇包含該詞項(xiàng)的文檔當(dāng)然比不包含該詞項(xiàng)的文檔的相關(guān)度要高 但是，這些詞對(duì)于相關(guān)度而言并不是非常強(qiáng)的指示詞 于是，對(duì)于諸如GOOD、INCR

17、EASE和LINE的頻繁詞，會(huì)給一個(gè)正的權(quán)重，但是這個(gè)權(quán)重小于罕見(jiàn)詞權(quán)重34現(xiàn)代信息檢索 35文檔頻率(Document frequency, df) 對(duì)于罕見(jiàn)詞項(xiàng)我們希望賦予高權(quán)重 對(duì)于常見(jiàn)詞我們希望賦予正的低權(quán)重 接下來(lái)我們使用文檔頻率df這個(gè)因子來(lái)計(jì)算查詢(xún)-文檔的匹配得分 文檔頻率(document frequency, df)指的是出現(xiàn)詞項(xiàng)的文檔數(shù)目35現(xiàn)代信息檢索 36idf 權(quán)重 dft 是出現(xiàn)詞項(xiàng)t的文檔數(shù)目 dft 是和詞項(xiàng)t的信息量成反比的一個(gè)值 于是可以定義詞項(xiàng)t的idf權(quán)重(逆文檔頻率): (其中N 是文檔集中文檔的數(shù)目) idft 是反映詞項(xiàng)t的信息量的一個(gè)指標(biāo)，是一種

18、全局性指標(biāo)，反應(yīng)的是詞項(xiàng)在全局的區(qū)別性。 實(shí)際中往往計(jì)算log N/dft 而不是 N/dft ，這可以對(duì)idf的影響有所抑制 值得注意的是，對(duì)于tf 和idf我們都采用了對(duì)數(shù)計(jì)算方式36現(xiàn)代信息檢索 37idf的計(jì)算樣例 利用右式計(jì)算idft:37詞項(xiàng)dftidftcalpurniaanimalsundayflyunderthe1100100010,000100,0001,000,000643210假設(shè)語(yǔ)料中文檔數(shù)目N=1，000，000現(xiàn)代信息檢索 38idf對(duì)排序的影響 對(duì)于單詞項(xiàng)查詢(xún),idf對(duì)文檔排序沒(méi)有任何影響 idf 會(huì)影響至少包含2個(gè)詞項(xiàng)的查詢(xún)的文檔排序結(jié)果 例如，在查詢(xún) “ar

19、achnocentric line”中, idf權(quán)重計(jì)算方法會(huì)增加arachnocentric的相對(duì)權(quán)重，同時(shí)降低 line的相對(duì)權(quán)重38現(xiàn)代信息檢索 39文檔集頻率 vs. 文檔頻率 詞項(xiàng)t的文檔集頻率(Collection frequency，cf) : 文檔集中出現(xiàn)的t詞條的個(gè)數(shù) 詞項(xiàng)t的文檔頻率df: 包含t的文檔篇數(shù) 為什么會(huì)出現(xiàn)上述表格的情況？即文檔集頻率相差不大，但是文檔頻率相差很大 哪個(gè)詞是更好的搜索詞項(xiàng)？即應(yīng)該賦予更高的權(quán)重 上例表明 df (和idf) 比cf (和“icf”)更適合權(quán)重計(jì)算39單詞文檔集頻率文檔頻率INSURANCETRY10440104223997876

20、0現(xiàn)代信息檢索 40tf-idf權(quán)重計(jì)算 詞項(xiàng)的tf-idf權(quán)重是tf權(quán)重和idf權(quán)重的乘積 信息檢索中最出名的權(quán)重計(jì)算方法 注意：上面的 “-”是連接符，不是減號(hào) 其他叫法：tf.idf、tf x idf40現(xiàn)代信息檢索 41tf-idf小結(jié) 詞項(xiàng)t在文檔d中的權(quán)重可以采用下式計(jì)算 tf-idf權(quán)重 隨著詞項(xiàng)頻率的增大而增大 (局部信息) 隨著詞項(xiàng)罕見(jiàn)度的增加而增大 (全局信息)41現(xiàn)代信息檢索 42課堂練習(xí): 詞項(xiàng)、文檔集及文檔頻率 df和cf有什么關(guān)系? tf和cf有什么關(guān)系? tf和df有什么關(guān)系？42統(tǒng)計(jì)量符號(hào)定義詞項(xiàng)頻率 文檔頻率文檔集頻率tft,ddftcft t在文檔d中出現(xiàn)的

21、次數(shù)出現(xiàn) t的文檔數(shù)目t在文檔集中出現(xiàn)的總次數(shù)提綱43 上一講回顧 排序式檢索 詞項(xiàng)頻率 tf-idf權(quán)重計(jì)算 向量空間模型現(xiàn)代信息檢索 44二值關(guān)聯(lián)矩陣每篇文檔表示成一個(gè)二值向量 0, 1|V|44Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .111011111110000000011011001100100111010010現(xiàn)代信息檢索 45tf矩陣 每篇文檔表示成一個(gè)詞頻向量 N|

22、V|45Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .15742320572273157227100000000031022008100100511000085現(xiàn)代信息檢索 46二值 tfidf矩陣每篇文檔表示成一個(gè)基于tfidf權(quán)重的實(shí)值向量 R|V|46Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbe

23、th . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .90.02.851.511.341.540.00.00.00.00.00.00.00.01.900.110.01.01.510.00.00.00.250.00.050.00.00.00.00.881.95現(xiàn)代信息檢索 47文檔表示成向量 每篇文檔表示成一個(gè)基于tfidf權(quán)重的實(shí)值向量 R|V|. 于是，我們有一個(gè) |V|維實(shí)值空間 空間的每一維都對(duì)應(yīng)詞項(xiàng) 文檔都是該空間下的一個(gè)點(diǎn)或者

24、向量 極高維向量：對(duì)于Web搜索引擎，空間會(huì)上千萬(wàn)維 對(duì)每個(gè)向量來(lái)說(shuō)又非常稀疏，大部分都是047現(xiàn)代信息檢索 48查詢(xún)看成向量 關(guān)鍵思路1: 對(duì)于查詢(xún)做同樣的處理，即將查詢(xún)表示成同一高維空間的向量 關(guān)鍵思路2: 按照文檔對(duì)查詢(xún)的鄰近程度排序 鄰近度 = 相似度 鄰近度 距離的反面 回想一下，我們是希望和布爾模型不同，能夠得到非二值的、既不是過(guò)多或也不是過(guò)少的檢索結(jié)果 這里，我們通過(guò)計(jì)算出相關(guān)文檔的相關(guān)度高于不相關(guān)文檔相關(guān)度的方法來(lái)實(shí)現(xiàn)48現(xiàn)代信息檢索 49向量空間下相似度的形式化定義 先考慮一下兩個(gè)點(diǎn)之間的距離倒數(shù) 一種方法是采用歐氏距離 但是，歐氏距離不是一種好的選擇，這是因?yàn)闅W氏距離對(duì)向量

25、長(zhǎng)度很敏感49現(xiàn)代信息檢索 50歐氏距離不好的例子盡管查詢(xún)q和文檔d2的詞項(xiàng)分布非常相似，但是采用歐氏距離計(jì)算它們對(duì)應(yīng)向量之間的距離非常大。50現(xiàn)代信息檢索 51采用夾角而不是距離來(lái)計(jì)算 將文檔按照其向量和查詢(xún)向量的夾角大小來(lái)排序 假想實(shí)驗(yàn)：將文檔 d 復(fù)制一份加在自身末尾得到文檔d. d 是d的兩倍 很顯然，從語(yǔ)義上看， d 和 d 具有相同的內(nèi)容 兩者之間的夾角為0，代表它們之間具有最大的相似度 但是，它們的歐氏距離可能會(huì)很大51現(xiàn)代信息檢索 52從夾角到余弦 下面兩個(gè)說(shuō)法是等價(jià)的： 按照夾角從小到大排列文檔 按照余弦從大到小排列文檔 這是因?yàn)樵趨^(qū)間0, 180上，余弦函數(shù)cosine是一

26、個(gè)單調(diào)遞減函數(shù)52現(xiàn)代信息檢索 53Cosine函數(shù)53現(xiàn)代信息檢索 54查詢(xún)和文檔之間的余弦相似度計(jì)算 qi 是第i 個(gè)詞項(xiàng)在查詢(xún)q中的tf-idf權(quán)重 di是第i 個(gè)詞項(xiàng)在文檔d中的tf-idf權(quán)重 | | 和 | | 分別是 和 的長(zhǎng)度 上述公式就是 和 的余弦相似度，或者說(shuō)向量 和 的夾角的余弦 54現(xiàn)代信息檢索 55文檔長(zhǎng)度歸一化 如何計(jì)算余弦相似度？ 一個(gè)向量可以通過(guò)除以它的長(zhǎng)度進(jìn)行歸一化處理，以下使用L2 （2范數(shù)）: 這相當(dāng)于將向量映射到單位球面上 這是因?yàn)闅w一化之后: 因此，長(zhǎng)文檔和短文檔的向量中的權(quán)重都處于同一數(shù)量級(jí) 前面提到的文檔 d 和 d (兩個(gè)d 的疊加) 經(jīng)過(guò)上述

27、歸一化之后的向量相同55現(xiàn)代信息檢索 56歸一化向量的余弦相似度 歸一化向量的余弦相似度等價(jià)于它們的點(diǎn)積(或內(nèi)積)如果 和 都是長(zhǎng)度歸一化后的向量56現(xiàn)代信息檢索 57余弦相似度的圖示57現(xiàn)代信息檢索 58余弦相似度的計(jì)算樣例 詞項(xiàng)頻率tf3本小說(shuō)之間的相似度(1) SaS(理智與情感):Sense andSensibility (2) PaP(傲慢與偏見(jiàn)):Pride andPrejudice (3) WH(呼嘯山莊):WutheringHeights58詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING1151020587002011638現(xiàn)代信息檢索 59

28、余弦相似度計(jì)算 詞項(xiàng)頻率 tf 對(duì)數(shù)詞頻（1+log10tf）59詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING3.062.01.3002.761.85002.302.041.782.58詞項(xiàng)SaS PaPWHAFFECTIONJEALOUSGOSSIPWUTHERING1151020587002011638為了簡(jiǎn)化計(jì)算，上述計(jì)算過(guò)程中沒(méi)有引入idf現(xiàn)代信息檢索 60余弦相似度計(jì)算 對(duì)數(shù)詞頻(1+log10tf) 對(duì)數(shù)詞頻的余弦歸一化結(jié)果 60詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING3.062.01.3002.761

29、.85002.302.041.782.58詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING0.7890.5150.3350.00.8320.5550.00.00.5240.4650.4050.588cos(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) 現(xiàn)代信息檢索 61余弦相似度計(jì)算算法61假設(shè)數(shù)組Length預(yù)先存放了文檔歸一化因子，即二范式 現(xiàn)

30、代信息檢索夾角余弦相似度之外的其他相似度計(jì)算 考慮三個(gè)因素tf、idf、文檔長(zhǎng)度 為什么長(zhǎng)度因素很重要？ 長(zhǎng)度長(zhǎng)的文檔詞項(xiàng)也多 長(zhǎng)度長(zhǎng)的文檔TF高 需要對(duì)長(zhǎng)度進(jìn)行規(guī)整/歸一(normalization)處理！62 現(xiàn)代信息檢索課堂練習(xí)：余弦相似度的一個(gè)問(wèn)題 查詢(xún) q: “anti-doping rules Beijing 2008 olympics” 反興奮劑 計(jì)算并比較如下的三篇文檔 d1: 一篇有關(guān)“anti-doping rules at 2008 Olympics”的短文檔 d2: 一篇包含d1 以及其他5篇新聞報(bào)道的長(zhǎng)文檔，其中這5篇新聞報(bào)道的主題都與Olympics/anti-do

31、ping無(wú)關(guān) d3: 一篇有關(guān)“anti-doping rules at the 2004 Athens Olympics”的短文檔 我們期望的結(jié)果是什么？ 如何實(shí)現(xiàn)上述結(jié)果？63 現(xiàn)代信息檢索回轉(zhuǎn)歸一化 余弦歸一化對(duì)傾向于短文檔，即對(duì)短文檔產(chǎn)生的歸一化因子太大，而平均而言對(duì)長(zhǎng)文檔產(chǎn)生的歸一化因子太小 于是可以先找到一個(gè)支點(diǎn)(pivot，平衡點(diǎn))，然后通過(guò)這個(gè)支點(diǎn)對(duì)余弦歸一化操作進(jìn)行線(xiàn)性調(diào)整。 效果：短文檔的相似度降低，而長(zhǎng)文檔的相似度增大 這可以去除原來(lái)余弦歸一化偏向短文檔的問(wèn)題64現(xiàn)代信息檢索 65預(yù)測(cè)相關(guān)性概率 vs. 真實(shí)相關(guān)性概率65現(xiàn)代信息檢索 66回轉(zhuǎn)歸一化(Pivot norm

32、alization)66 現(xiàn)代信息檢索回轉(zhuǎn)歸一化: Amit Singhal的實(shí)驗(yàn)結(jié)果 結(jié)果第一行：返回的相關(guān)文檔數(shù)目 結(jié)果第二行： 平均正確率 結(jié)果第三行： 平均正確率的提高百分比67 現(xiàn)代信息檢索Amit Singhal 1989年本科畢業(yè)于印度IIT (Indian Institute of Technology) Roorkee分校 1996年博士畢業(yè)于Cornell University，導(dǎo)師是Gerard Salton 其論文獲得1996年SIGIR Best Student Paper Award 2000年加入Google，2001年被授予Google Fellow稱(chēng)號(hào) Google 排序團(tuán)隊(duì)負(fù)責(zé)人,被財(cái)富雜志(Fortune, 2010)譽(yù)為世界科技界最聰明的50個(gè)人之一68現(xiàn)代信息檢索 69tf-idf權(quán)重計(jì)算的三要素69現(xiàn)代信息檢索 70tf-idf權(quán)重機(jī)制舉例 對(duì)于查詢(xún)和文檔常常采用不同的權(quán)重計(jì)算機(jī)制 記法: ddd.qqq 例如