評分與向量空間模型課件

1、文檔評分與向量空間模型主講人：陳文亮李正華稍微刪減蘇州大學計算機學院第1頁，共51頁。提綱2 排序式檢索 詞項頻率詞項頻率 tf-idf權重計算 向量空間模型第2頁，共51頁。提綱3 排序式檢索 詞項頻率 tf-idf權重計算 向量空間模型第3頁，共51頁。為什么要排序第4頁，共51頁。5排序式檢索(Ranked retrieval)迄今為止，我們主要關注的是布爾查詢文檔要么匹配要么不匹配對自身需求和文檔集性質(zhì)非常了解的專家而言，布爾查詢是不錯的選擇對應用開發(fā)來說也非常簡單，很容易就可以返回1000多條結果然而對大多數(shù)用戶來說不方便大部分用戶不能撰寫布爾查詢或者他們認為需要大量訓練才能撰寫合適

2、的布爾查詢大部分用戶不愿意逐條瀏覽1000多條結果，特別是對Web搜索更是如此對于剛才的例子，40M的文檔，相信大家都不會想去看。5第5頁，共51頁。6布爾搜索的不足: 結果過少或者過多布爾查詢常常會倒是過少(=0)或者過多(1000)的結果查詢 1 (布爾或操作): standard user dlink 650 200,000 個結果 太多查詢2 (布爾與操作): standard user dlink 650 no card found 0 個結果 太少在布爾檢索中，需要大量技巧來生成一個可以獲得合適規(guī)模結果的查詢6第6頁，共51頁。7排序式檢索排序式檢索可以避免產(chǎn)生過多或者過少的結果大

3、規(guī)模的返回結果可以通過排序技術來避免只需要顯示前10條結果不會讓用戶感覺到信息太多前提：排序算法真的有效，即相關度大的文檔結果會排在相關度小的文檔結果之前7第7頁，共51頁。8排序式檢索中的評分技術我們希望，在同一查詢下，文檔集中相關度高的文檔排名高于相關度低的文檔如何實現(xiàn)？通常做法是對每個查詢-文檔對賦一個0, 1之間的分值該分值度量了文檔和查詢的匹配程度怎么做？8第8頁，共51頁。9查詢-文檔匹配評分計算如何計算查詢-文檔的匹配得分？原則先從單詞項查詢開始若該詞項不出現(xiàn)在文檔當中，該文檔得分應該為0該詞項在文檔中出現(xiàn)越多，則得分越高9第9頁，共51頁。提綱10 排序式檢索 詞項頻率 tf-

4、idf權重計算 向量空間模型第10頁，共51頁。11二值關聯(lián)矩陣每篇文檔可以看成是一個二值的向量 0, 1|V|11Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .111011111110000000011011001100100111010010第11頁，共51頁。12非二值關聯(lián)矩陣(詞頻) 每篇文檔可以表示成一個詞頻向量 N|V|12Anthony and CleopatraJuliu

5、s Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .15742320572273157227100000000031022008100100511000085第12頁，共51頁。13詞袋(Bag of words)模型不考慮詞在文檔中出現(xiàn)的順序John is quicker than Mary 及 Mary is quicker than John are 的表示結果一樣這稱為一個詞袋模型(bag of words model)在某種意思上說，

6、這種表示方法是一種“倒退”，因為位置索引中能夠區(qū)分上述兩篇文檔13第13頁，共51頁。14詞項頻率 tf詞項t的詞項頻率 tft,d 是指t 在d中出現(xiàn)的次數(shù)下面將介紹利用tf來計算文檔評分的方法第一種方法是采用原始的tf值(raw tf)但是原始tf不太合適：某個詞項在A文檔中出現(xiàn)十次，即tf = 10，在B文檔中 tf = 1，那么A比B更相關但是相關度不會相差10倍相關度不會正比于詞項頻率tf14第14頁，共51頁。15一種替代原始tf的方法: 對數(shù)詞頻t 在 d 中的對數(shù)詞頻權重定義如下：tft,d wt,d : 0 0, 1 1, 2 1.3, 10 2, 1000 4, 等等文檔-

7、詞項的匹配得分是所有同時出現(xiàn)在q和文檔d中的詞項的對數(shù)詞頻之和(1 + log tft,d )如果兩者沒有公共詞項，則得分為015第15頁，共51頁。提綱16排序式檢索 詞項頻率 tf-idf權重計算 向量空間模型第16頁，共51頁。17文檔中的詞頻 vs. 文檔集中的詞頻哪種詞重要？的 了 水果 火龍果 劉翔 體育 蘇州大學 計算機學院除詞項頻率tf之外，我們還想利用詞項在整個文檔集中的頻率進行權重和評分計算17第17頁，共51頁。18罕見詞項所期望的權重罕見詞項比常見詞所蘊含的信息更多考慮查詢中某個詞項，它在整個文檔集中非常罕見 (例如 赫爾辛根默斯).某篇包含該詞項的文檔很可能相關于是，

8、我們希望像“赫爾辛根默斯”一樣的罕見詞項將有較高權重18阿爾代夫海灘馬路第18頁，共51頁。19常見詞項所期望的權重常見詞項的信息量不如罕見詞考慮一個查詢詞項，它頻繁出現(xiàn)在文檔集中 (如 GOOD, INCREASE, LINE等等)一篇包含該詞項的文檔當然比不包含該詞項的文檔的相關度要高但是，這些詞對于相關度而言并不是非常強的指示詞于是，對于諸如GOOD、INCREASE和LINE的頻繁詞，會給一個正的權重，但是這個權重小于罕見詞權重19第19頁，共51頁。20文檔頻率(Document frequency, df)對于罕見詞項我們希望賦予高權重對于常見詞我們希望賦予正的低權重接下來我們使用

9、文檔頻率df這個因子來計算查詢-文檔的匹配得分文檔頻率指但是出現(xiàn)詞項的文檔數(shù)目20第20頁，共51頁。21idf 權重dft 是出現(xiàn)詞項t的文檔數(shù)目dft 是和詞項t的信息量成反比的一個值于是可以定義詞項t的idf權重: (其中N 是文檔集中文檔的數(shù)目)idft 是反映詞項t的信息量的一個指標值得注意的是，對于tf 和idf我們都采用了對數(shù)計算方式21第21頁，共51頁。22idf的計算樣例（inverted document freq）利用右式計算idft:22詞項dftidftcalpurniaanimalsundayflyunderthe1100100010,000100,0001,00

10、0,000643210第22頁，共51頁。23idf對排序的影響idf 會影響至少包含2個詞項的查詢的文檔排序結果例如，在查詢 “馬爾代夫 海灘”中, idf權重計算方法會增加 馬爾代夫 的相對權重，同時降低 海灘 的相對權重對于單詞項查詢,idf對文檔排序基本沒有任何影響23第23頁，共51頁。24文檔集頻率 vs. 文檔頻率詞項t的文檔集頻率(Collection frequency) : 文檔集中出現(xiàn)的t詞條的個數(shù)詞項t的文檔頻率: 包含t的文檔篇數(shù)為什么會出現(xiàn)上述表格的情況？即文檔集頻率相差不大，但是文檔頻率相差很大哪個詞是更好的搜索詞項？即應該賦予更高的權重上例表明 df (和idf

11、) 比cf (和“icf”)更適合權重計算24單詞文檔集頻率文檔頻率INSURANCETRY104401042239978760第24頁，共51頁。25tf-idf權重計算詞項的tf-idf權重是tf權重和idf權重的乘積信息檢索中最出名的權重計算方法注意：上面的 “-”是連接符，不是減號其他叫法：tf.idf、tf x idf25第25頁，共51頁。26tf-idf小結詞項t在文檔d中的權重可以采用下次計算tf-idf權重隨著詞項頻率的增大而增大隨著詞項罕見度的增加而增大26第26頁，共51頁。提綱27 排序式檢索 詞項頻率 tf-idf權重計算 向量空間模型第27頁，共51頁。28二值關聯(lián)

12、矩陣每篇文檔表示成一個二值向量 0, 1|V|28Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .111011111110000000011011001100100111010010第28頁，共51頁。29詞頻矩陣 每篇文檔表示成一個詞頻向量 N|V|29Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth

13、 . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .15742320572273157227100000000031022008100100511000085第29頁，共51頁。30二值 詞頻 權重矩陣每篇文檔表示成一個基于tfidf權重的實值向量 R|V|30Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macbeth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .5.251.2

14、18.590.02.851.511.373.186.102.541.540.00.00.00.00.00.00.00.01.900.110.01.01.510.00.00.124.150.00.00.250.00.05.250.250.350.00.00.00.00.881.95第30頁，共51頁。31二值 詞頻 權重矩陣每篇文檔表示成一個基于tfidf權重的實值向量 R|V|下一步：需要按列進行歸一化（保證每一個列向量的平方和為1）思考一下如何做？原因后面講。31Anthony and CleopatraJulius Caesar The TempestHamlet Othello Macb

15、eth . . .ANTHONYBRUTUS CAESARCALPURNIACLEOPATRAMERCYWORSER. . .5.251.218.590.02.851.511.373.186.102.541.540.00.00.00.00.00.00.00.01.900.110.01.01.510.00.00.124.150.00.00.250.00.05.250.250.350.00.00.00.00.881.95第31頁，共51頁。32文檔表示成向量每篇文檔表示成一個基于tfidf權重的實值向量 R|V|.于是，我們有一個 |V|維實值空間空間的每一維都對應詞項文檔都是該空間下的一個點或者

16、向量極高維向量：對于Web搜索引擎，空間會上千萬維對每個向量來說又非常稀疏，大部分都是032第32頁，共51頁。33查詢看成向量每一個查詢也可以表示為一個高維稀疏向量。注意，為了簡化問題，只考慮tf值，而不考慮idf如：good - 1 movie-2查詢對應的向量不需要歸一化（為什么自己思考）33第33頁，共51頁。34向量空間下相似度的形式化定義先考慮一下兩個點之間的距離倒數(shù)一種方法是采用歐氏距離但是，歐氏距離不是一種好的選擇，這是因為歐氏距離對向量長度很敏感34第34頁，共51頁。35歐氏距離不好的例子盡管查詢q和文檔d2的詞項分布非常相似，但是采用歐氏距離計算它們對應向量之間的距離非常

17、大。.Questions about basic vector space setup?35第35頁，共51頁。36采用夾角而不是距離來計算將文檔按照其向量和查詢向量的夾角大小來排序假想實驗：將文檔 d 復制一份加在自身末尾得到文檔d. d 是d的兩倍很顯然，從語義上看， d 和 d 具有相同的內(nèi)容兩者之間的夾角為0，代表它們之間具有最大的相似度但是，它們的歐氏距離可能會很大36第36頁，共51頁。37從夾角到余弦下面兩個說法是等價的：按照夾角從小到大排列文檔按照余弦從大到小排列文檔這是因為在區(qū)間0, 180上，余弦函數(shù)cosine是一個單調(diào)遞減函數(shù)37第37頁，共51頁。38Cosine函數(shù)

18、38第38頁，共51頁。39文檔長度歸一化如何計算余弦相似度？一個向量可以通過除以它的長度進行歸一化處理，以下使用L2 （2范數(shù)）:這相當于將向量映射到單位球面上這是因為歸一化之后: 因此，長文檔和短文檔的向量中的權重都處于同一數(shù)量級前面提到的文檔 d 和 d (兩個d 的疊加) 經(jīng)過上述歸一化之后的向量相同39第39頁，共51頁。40查詢和文檔之間的余弦相似度計算qi 是第i 個詞項在查詢q中的tf-idf權重di是第i 個詞項在文檔d中的tf-idf權重| | 和 | | 分別是 和 的長度上述公式就是 和 的余弦相似度，或者說向量 和 的夾角的余弦 40第40頁，共51頁。41歸一化向量

19、的余弦相似度歸一化向量的余弦相似度等價于它們的點積(或內(nèi)積)如果 和 都是長度歸一化后的向量41第41頁，共51頁。42余弦相似度的圖示42第42頁，共51頁。下面的內(nèi)容不講，有興趣的同學可以了解第43頁，共51頁。44第一種方法: Jaccard系數(shù)計算兩個集合重合度的常用方法令 A 和 B 為兩個集合Jaccard系數(shù)的計算方法:JACCARD (A, A) = 1JACCARD (A, B) = 0 如果 A B = 0A 和 B 不一定要同樣大小Jaccard 系數(shù)會給出一個0到1之間的值44第44頁，共51頁。45Jaccard系數(shù)的計算樣例查詢 “ides of March”文檔

20、“Caesar died in March”JACCARD(q, d) = 1/645第45頁，共51頁。46Jaccard系數(shù)的不足不考慮詞項頻率 ，即詞項在文檔中的出現(xiàn)次數(shù)罕見詞比高頻詞的信息量更大，Jaccard系數(shù)沒有考慮這個信息沒有仔細考慮文檔的長度因素46第46頁，共51頁。47課堂練習: 詞項、文檔集及文檔頻率df和cf有什么關系?tf和cf有什么關系?tf和df有什么關系？47統(tǒng)計量符號定義詞項頻率 文檔頻率文檔集頻率tft,ddftcft t在文檔d中出現(xiàn)的次數(shù)出現(xiàn) t的文檔數(shù)目t在文檔集中出現(xiàn)的總次數(shù)第47頁，共51頁。48余弦相似度的計算樣例 詞項頻率tf3本小說之間的相似度(1) SaS(理智與情感):Sense andSensibility (2) PaP(傲慢與偏見):Pride andPrejudice (3) WH(呼嘯山莊):WutheringHeights48詞項SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING1151020587002011638第48頁，共51頁。49余弦相似度計算 詞項頻率 tf 對數(shù)詞頻（1+log10tf）49詞