網(wǎng)絡(luò)信息獲取與情報(bào)分析技術(shù)八第一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三提綱

上一講回顧

排序式檢索

詞項(xiàng)頻率tf-idf權(quán)重計(jì)算

向量空間模型2第二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三3排序式檢索(Rankedretrieval)迄今為止，我們主要關(guān)注的是布爾查詢文檔要么匹配要么不匹配對(duì)自身需求和文檔集性質(zhì)非常了解的專家而言，布爾查詢是不錯(cuò)的選擇對(duì)應(yīng)用開(kāi)發(fā)來(lái)說(shuō)也非常簡(jiǎn)單，很容易就可以返回1000多條結(jié)果然而對(duì)大多數(shù)用戶來(lái)說(shuō)不方便大部分用戶不能撰寫(xiě)布爾查詢或者他們認(rèn)為需要大量訓(xùn)練才能撰寫(xiě)合適的布爾查詢大部分用戶不愿意逐條瀏覽1000多條結(jié)果，特別是對(duì)Web搜索更是如此3第三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三4布爾搜索的不足:結(jié)果過(guò)少或者過(guò)多布爾查詢常常會(huì)倒是過(guò)少(=0)或者過(guò)多(>1000)的結(jié)果查詢1(布爾與操作):[standarduserdlink650]→200,000個(gè)結(jié)果–太多查詢2(布爾與操作):[standarduserdlink650nocardfound]→0個(gè)結(jié)果–太少在布爾檢索中，需要大量技巧來(lái)生成一個(gè)可以獲得合適規(guī)模結(jié)果的查詢4第四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三5排序式檢索排序式檢索可以避免產(chǎn)生過(guò)多或者過(guò)少的結(jié)果大規(guī)模的返回結(jié)果可以通過(guò)排序技術(shù)來(lái)避免只需要顯示前10條結(jié)果不會(huì)讓用戶感覺(jué)到信息太多前提：排序算法真的有效，即相關(guān)度大的文檔結(jié)果會(huì)排在相關(guān)度小的文檔結(jié)果之前5第五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三6排序式檢索中的評(píng)分技術(shù)我們希望，在同一查詢下，文檔集中相關(guān)度高的文檔排名高于相關(guān)度低的文檔如何實(shí)現(xiàn)？通常做法是對(duì)每個(gè)查詢-文檔對(duì)賦一個(gè)[0,1]之間的分值該分值度量了文檔和查詢的匹配程度6第六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三7查詢-文檔匹配評(píng)分計(jì)算如何計(jì)算查詢-文檔的匹配得分？先從單詞項(xiàng)查詢開(kāi)始若該詞項(xiàng)不出現(xiàn)在文檔當(dāng)中，該文檔得分應(yīng)該為0該詞項(xiàng)在文檔中出現(xiàn)越多，則得分越高后面我們將給出多種評(píng)分的方法7第七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三8第一種方法:Jaccard系數(shù)計(jì)算兩個(gè)集合重合度的常用方法令

A

和B為兩個(gè)集合Jaccard系數(shù)的計(jì)算方法:JACCARD(A,A)=1JACCARD(A,B)=0如果

A∩B=0A和B不一定要同樣大小Jaccard系數(shù)會(huì)給出一個(gè)0到1之間的值8第八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三9Jaccard系數(shù)的計(jì)算樣例查詢

“idesofMarch”文檔“CaesardiedinMarch”JACCARD(q,d)=1/69第九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三10Jaccard系數(shù)的不足不考慮詞項(xiàng)頻率

，即詞項(xiàng)在文檔中的出現(xiàn)次數(shù)罕見(jiàn)詞比高頻詞的信息量更大，Jaccard系數(shù)沒(méi)有考慮這個(gè)信息沒(méi)有仔細(xì)考慮文檔的長(zhǎng)度因素10第十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三

現(xiàn)代信息檢索PaulJaccard(1868-1944)瑞士植物學(xué)家，ETH教授1894年畢業(yè)于蘇黎世聯(lián)邦理工學(xué)院ETH(出過(guò)包括愛(ài)因斯坦在內(nèi)的21位諾貝爾獎(jiǎng)得主)1901年提出JaccardIndex即JaccardCoefficient概念11第十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三提綱

上一講回顧

排序式檢索

詞項(xiàng)頻率tf-idf權(quán)重計(jì)算

向量空間模型12第十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三13二值關(guān)聯(lián)矩陣

每篇文檔可以看成是一個(gè)二值的向量∈{0,1}|V|AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...11101111111000000001101100110010011101001013第十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三14非二值關(guān)聯(lián)矩陣(詞頻)

每篇文檔可以表示成一個(gè)詞頻向量∈N|V|AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...1574232057227315722710000000003102200810010051100008514第十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三15詞袋(Bagofwords)模型不考慮詞在文檔中出現(xiàn)的順序JohnisquickerthanMary及MaryisquickerthanJohn的表示結(jié)果一樣這稱為一個(gè)詞袋模型(bagofwordsmodel)在某種意思上說(shuō)，這種表示方法是一種“倒退”，因?yàn)槲恢盟饕心軌騾^(qū)分上述兩篇文檔這里僅考慮詞袋模型15第十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三16詞項(xiàng)頻率tf詞項(xiàng)t的詞項(xiàng)頻率tft,d

是指t

在d中出現(xiàn)的次數(shù)下面將介紹利用tf來(lái)計(jì)算文檔評(píng)分的方法第一種方法是采用原始的tf值(rawtf)但是原始tf不太合適：某個(gè)詞項(xiàng)在A文檔中出現(xiàn)十次，即tf=10，在B文檔中tf=1，那么A比B更相關(guān)但是相關(guān)度不會(huì)相差10倍相關(guān)度不會(huì)正比于詞項(xiàng)頻率tf16第十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三17一種替代原始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∈q∩d(1+logtft,d)如果兩者沒(méi)有公共詞項(xiàng)，則得分為017第十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三提綱

上一講回顧

排序式檢索

詞項(xiàng)頻率

tf-idf權(quán)重計(jì)算

向量空間模型18第十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三19文檔中的詞頻vs.文檔集中的詞頻除詞項(xiàng)頻率tf之外，我們還想利用詞項(xiàng)在整個(gè)文檔集中的頻率進(jìn)行權(quán)重和評(píng)分計(jì)算19第十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三20罕見(jiàn)詞項(xiàng)所期望的權(quán)重罕見(jiàn)詞項(xiàng)比常見(jiàn)詞所蘊(yùn)含的信息更多考慮查詢中某個(gè)詞項(xiàng)，它在整個(gè)文檔集中非常罕見(jiàn)(例如ARACHNOCENTRIC).某篇包含該詞項(xiàng)的文檔很可能相關(guān)于是，我們希望像ARACHNOCENTRIC一樣的罕見(jiàn)詞項(xiàng)將有較高權(quán)重20第二十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三21常見(jiàn)詞項(xiàng)所期望的權(quán)重常見(jiàn)詞項(xiàng)的信息量不如罕見(jiàn)詞考慮一個(gè)查詢?cè)~項(xiàng)，它頻繁出現(xiàn)在文檔集中(如

GOOD,INCREASE,LINE等等)一篇包含該詞項(xiàng)的文檔當(dāng)然比不包含該詞項(xiàng)的文檔的相關(guān)度要高但是，這些詞對(duì)于相關(guān)度而言并不是非常強(qiáng)的指示詞于是，對(duì)于諸如GOOD、INCREASE和LINE的頻繁詞，會(huì)給一個(gè)正的權(quán)重，但是這個(gè)權(quán)重小于罕見(jiàn)詞權(quán)重21第二十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三22文檔頻率(Documentfrequency,df)對(duì)于罕見(jiàn)詞項(xiàng)我們希望賦予高權(quán)重對(duì)于常見(jiàn)詞我們希望賦予正的低權(quán)重接下來(lái)我們使用文檔頻率df這個(gè)因子來(lái)計(jì)算查詢-文檔的匹配得分文檔頻率指但是出現(xiàn)詞項(xiàng)的文檔數(shù)目22第二十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三23idf權(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)實(shí)際中往往計(jì)算[logN/dft]而不是[N/dft]，這可以對(duì)idf的影響有所抑制值得注意的是，對(duì)于tf和idf我們都采用了對(duì)數(shù)計(jì)算方式23第二十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三24idf的計(jì)算樣例利用右式計(jì)算idft:詞項(xiàng)dftidftcalpurniaanimalsundayflyunderthe1100100010,000100,0001,000,00064321024第二十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三25idf對(duì)排序的影響idf會(huì)影響至少包含2個(gè)詞項(xiàng)的查詢的文檔排序結(jié)果例如，在查詢“arachnocentricline”中,idf權(quán)重計(jì)算方法會(huì)增加ARACHNOCENTRIC的相對(duì)權(quán)重，同時(shí)降低

LINE的相對(duì)權(quán)重對(duì)于單詞項(xiàng)查詢,idf對(duì)文檔排序基本沒(méi)有任何影響25第二十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三26文檔集頻率vs.文檔頻率詞項(xiàng)t的文檔集頻率(Collectionfrequency):文檔集中出現(xiàn)的t詞條的個(gè)數(shù)詞項(xiàng)t的文檔頻率:包含t的文檔篇數(shù)為什么會(huì)出現(xiàn)上述表格的情況？即文檔集頻率相差不大，但是文檔頻率相差很大哪個(gè)詞是更好的搜索詞項(xiàng)？即應(yīng)該賦予更高的權(quán)重上例表明df(和idf)比cf(和“icf”)更適合權(quán)重計(jì)算單詞文檔集頻率文檔頻率INSURANCETRY10440104223997876026第二十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三27tf-idf權(quán)重計(jì)算詞項(xiàng)的tf-idf權(quán)重是tf權(quán)重和idf權(quán)重的乘積信息檢索中最出名的權(quán)重計(jì)算方法注意：上面的“-”是連接符，不是減號(hào)其他叫法：tf.idf、tfxidf27第二十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三28tf-idf小結(jié)詞項(xiàng)t在文檔d中的權(quán)重可以采用下次計(jì)算tf-idf權(quán)重隨著詞項(xiàng)頻率的增大而增大隨著詞項(xiàng)罕見(jiàn)度的增加而增大28第二十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三29課堂練習(xí):詞項(xiàng)、文檔集及文檔頻率df和cf有什么關(guān)系?tf和cf有什么關(guān)系?tf和df有什么關(guān)系？統(tǒng)計(jì)量符號(hào)定義詞項(xiàng)頻率

文檔頻率文檔集頻率tft,ddftcftt在文檔d中出現(xiàn)的次數(shù)出現(xiàn)t的文檔數(shù)目t在文檔集中出現(xiàn)的總次數(shù)29第二十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三提綱

上一講回顧

排序式檢索

詞項(xiàng)頻率tf-idf權(quán)重計(jì)算

向量空間模型30第三十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三31二值關(guān)聯(lián)矩陣

每篇文檔表示成一個(gè)二值向量∈{0,1}|V|AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...11101111111000000001101100110010011101001031第三十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三32詞頻矩陣

每篇文檔表示成一個(gè)詞頻向量∈N|V|AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...1574232057227315722710000000003102200810010051100008532第三十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三33二值→詞頻→權(quán)重矩陣

每篇文檔表示成一個(gè)基于tfidf權(quán)重的實(shí)值向量∈R|V|AnthonyandCleopatraJuliusCaesarTheTempestHamletOthelloMacbeth...ANTHONYBRUTUSCAESARCALPURNIACLEOPATRAMERCYWORSER...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.9533第三十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三34文檔表示成向量每篇文檔表示成一個(gè)基于tfidf權(quán)重的實(shí)值向量

∈R|V|.于是，我們有一個(gè)|V|維實(shí)值空間空間的每一維都對(duì)應(yīng)詞項(xiàng)文檔都是該空間下的一個(gè)點(diǎn)或者向量極高維向量：對(duì)于Web搜索引擎，空間會(huì)上千萬(wàn)維對(duì)每個(gè)向量來(lái)說(shuō)又非常稀疏，大部分都是034第三十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三35查詢看成向量關(guān)鍵思路1:對(duì)于查詢做同樣的處理，即將查詢表示成同一高維空間的向量關(guān)鍵思路2:按照文檔對(duì)查詢的鄰近程度排序鄰近度=相似度鄰近度≈距離的反面回想一下，我們是希望和布爾模型不同，能夠得到非二值的、既不是過(guò)多或也不是過(guò)少的檢索結(jié)果這里，我們通過(guò)計(jì)算出相關(guān)文檔的相關(guān)度高于不相關(guān)文檔相關(guān)度的方法來(lái)實(shí)現(xiàn)35第三十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三36向量空間下相似度的形式化定義先考慮一下兩個(gè)點(diǎn)之間的距離倒數(shù)一種方法是采用歐氏距離但是，歐氏距離不是一種好的選擇，這是因?yàn)闅W氏距離對(duì)向量長(zhǎng)度很敏感36第三十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三37歐氏距離不好的例子盡管查詢q和文檔d2的詞項(xiàng)分布非常相似，但是采用歐氏距離計(jì)算它們對(duì)應(yīng)向量之間的距離非常大。.Questionsaboutbasicvectorspacesetup?37第三十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三38采用夾角而不是距離來(lái)計(jì)算將文檔按照其向量和查詢向量的夾角大小來(lái)排序假想實(shí)驗(yàn)：將文檔d復(fù)制一份加在自身末尾得到文檔d′.d′是d的兩倍很顯然，從語(yǔ)義上看，

d

和

d′

具有相同的內(nèi)容兩者之間的夾角為0，代表它們之間具有最大的相似度但是，它們的歐氏距離可能會(huì)很大38第三十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三39從夾角到余弦下面兩個(gè)說(shuō)法是等價(jià)的：按照夾角從小到大排列文檔按照余弦從大到小排列文檔這是因?yàn)樵趨^(qū)間[0?,180?]上，余弦函數(shù)cosine是一個(gè)單調(diào)遞減函數(shù)39第三十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三40Cosine函數(shù)40第四十頁(yè)，共五十六頁(yè)，編輯于2023年，星期三41文檔長(zhǎng)度歸一化如何計(jì)算余弦相似度？一個(gè)向量可以通過(guò)除以它的長(zhǎng)度進(jìn)行歸一化處理，以下使用L2

（2范數(shù)）:這相當(dāng)于將向量映射到單位球面上因此，長(zhǎng)文檔和短文檔的向量中的權(quán)重都處于同一數(shù)量級(jí)前面提到的文檔

d

和

d′(兩個(gè)d

的疊加)經(jīng)過(guò)上述歸一化之后的向量相同41第四十一頁(yè)，共五十六頁(yè)，編輯于2023年，星期三42查詢和文檔之間的余弦相似度計(jì)算qi

是第i

個(gè)詞項(xiàng)在查詢q中的tf-idf權(quán)重di是第i

個(gè)詞項(xiàng)在文檔d中的tf-idf權(quán)重||和||分別是和的長(zhǎng)度上述公式就是和的余弦相似度，或者說(shuō)向量和的夾角的余弦

42第四十二頁(yè)，共五十六頁(yè)，編輯于2023年，星期三43歸一化向量的余弦相似度歸一化向量的余弦相似度等價(jià)于它們的點(diǎn)積(或內(nèi)積)如果和

都是長(zhǎng)度歸一化后的向量43第四十三頁(yè)，共五十六頁(yè)，編輯于2023年，星期三44余弦相似度的圖示44第四十四頁(yè)，共五十六頁(yè)，編輯于2023年，星期三45余弦相似度的計(jì)算樣例

詞項(xiàng)頻率tf3本小說(shuō)之間的相似度(1)SaS(理智與情感):SenseandSensibility(2)PaP(傲慢與偏見(jiàn)):PrideandPrejudice(3)WH(呼嘯山莊):WutheringHeights詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING115102058700201163845第四十五頁(yè)，共五十六頁(yè)，編輯于2023年，星期三46余弦相似度計(jì)算

詞項(xiàng)頻率tf對(duì)數(shù)詞頻（1+log10tf）詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING3.062.01.3002.761.85002.302.041.782.58詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING1151020587002011638為了簡(jiǎn)化計(jì)算，上述計(jì)算過(guò)程中沒(méi)有引入idf46第四十六頁(yè)，共五十六頁(yè)，編輯于2023年，星期三47余弦相似度計(jì)算

對(duì)數(shù)詞頻(1+log10tf)數(shù)詞頻的余弦歸一化結(jié)果

詞項(xiàng)SaSPaPWHAFFECTIONJEALOUSGOSSIPWUTHERING3.062.01.3002.761.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)47第四十七頁(yè)，共五十六頁(yè)，編輯于2023年，星期三48余弦相似度計(jì)算算法48第四十八頁(yè)，共五十六頁(yè)，編輯于2023年，星期三49tf-idf權(quán)重計(jì)算的三要素49第四十九頁(yè)，共五十六頁(yè)，編輯于2023年，星期三50tf-idf權(quán)重機(jī)制舉例對(duì)于查詢和文檔常常采用不同的權(quán)重計(jì)算機(jī)制記法:ddd.qqq例如:lnc.ltn文檔:對(duì)數(shù)tf，無(wú)idf因子，余弦長(zhǎng)度歸一化查詢:對(duì)數(shù)tf，idf，無(wú)歸一化文檔當(dāng)中不用idf結(jié)果會(huì)不會(huì)很差？查詢:“bestcarinsurance”文檔:“carinsuranceautoinsurance”50第五十頁(yè)，共五十六頁(yè)，編輯于2023年，星期