信息檢索6-tfidf

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

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

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

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

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

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

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

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

9、 = 0 A 和 B 不一定要同樣大小 Jaccard 系數(shù)會給出一個0到1之間的值19AB現(xiàn)代信息檢索 20Jaccard系數(shù)的計算樣例 查詢 “ides of March” 3月15日(朱利烏斯愷撒的殉難日) 文檔 “Caesar died in March”JACCARD(q, d) = 1/620現(xiàn)代信息檢索 21課堂練習 計算下列查詢-文檔之間的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àn)次數(shù)(后面會定義) 一般而言，罕見詞比高頻詞的信息量更大，Jaccard系數(shù)沒有考慮這個信息 沒有仔細考慮文檔的長度因素 本講義后面，我們將不考慮使用Jaccard系數(shù)來進行查詢和文檔的評分計算 提醒：在第19講Web網(wǎng)頁查重，我們還會介紹大規(guī)模網(wǎng)頁下的Jaccard系數(shù)計算問

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

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

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é)果一樣 這稱為一個詞袋模型

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

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

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

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

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

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

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

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

22、V|45Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .15742320572273157227100000000031022008100100511000085現(xiàn)代信息檢索 46二值 tfidf矩陣每篇文檔表示成一個基于tfidf權(quán)重的實值向量 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文檔表示成向量 每篇文檔表示成一個基于tfidf權(quán)重的實值向量 R|V|. 于是，我們有一個 |V|維實值空間 空間的每一維都對應(yīng)詞項 文檔都是該空間下的一個點或者

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

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

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

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

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

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

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

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

32、alization)66 現(xiàn)代信息檢索回轉(zhuǎn)歸一化: Amit Singhal的實驗結(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稱號 Google 排序團隊負責人,被財富雜志(Fortune, 2010)譽為世界科技界最聰明的50個人之一68現(xiàn)代信息檢索 69tf-idf權(quán)重計算的三要素69現(xiàn)代信息檢索 70tf-idf權(quán)重機制舉例 對于查詢和文檔常常采用不同的權(quán)重計算機制 記法: ddd.qqq 例如