為系統(tǒng)索引項(xiàng)集合則Di={di1di2…din}dij≥0課件

1、信息檢索與搜索引擎排序算法 - 徐艷霞主要內(nèi)容1 信息檢索模型介紹2 搜索引擎典型排序算法介紹3 適用于數(shù)學(xué)公式搜索引擎排序算法探討搜索引擎排序標(biāo)準(zhǔn)如果我牙疼，應(yīng)該去看怎樣的醫(yī)生呢？假設(shè)我只有三種選擇： A醫(yī)生，既治眼病，又治胃??； B醫(yī)生，既治牙病，又治胃病，還治眼??； C醫(yī)生，專治牙病。 假如再加一個(gè)條件：B醫(yī)生經(jīng)驗(yàn)豐富，有二十年從醫(yī)經(jīng)歷，醫(yī)術(shù)高明，而C醫(yī)生只有五年從醫(yī)經(jīng)驗(yàn)。 結(jié)論：擇醫(yī)需要考慮兩個(gè)條件，1：醫(yī)生的專長(zhǎng)與病情的適配程度 2：醫(yī)生的醫(yī)術(shù) 網(wǎng)頁(yè)內(nèi)容與用戶查詢的匹配程度 搜索引擎排序 網(wǎng)頁(yè)本身的質(zhì)量 目錄1.1 信息檢索模型的定義及檢索系統(tǒng)的形式化表示1.2 布爾模型1.3 向量

2、空間模型1.4 概率模型1.5 典型的搜索引擎排序算法 信息檢索模型1 信息檢索模型的定義 什么是數(shù)學(xué)模型？ 為了某種特定目的，通過對(duì)現(xiàn)實(shí)世界的某一特定對(duì)象做出一些必要的簡(jiǎn)化與假設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具得到的一種數(shù)學(xué)結(jié)構(gòu)。 面對(duì)相同的輸入，模型的輸出應(yīng)能夠無限地逼近現(xiàn)實(shí)世界的輸出。 信息檢索模型 是用來描述文檔和用戶查詢的表示形式以及它們之間相關(guān)性的框架信息檢索模型信息檢索的實(shí)質(zhì)問題 對(duì)于所有文檔，根據(jù)其與用戶查詢的相關(guān)程度由大到小進(jìn)行排序。信息檢索模型與搜索引擎排序算法關(guān)系 好的信息檢索模型在相關(guān)性上產(chǎn)生和人類決策非常相關(guān)的結(jié)果，基于好的檢索模型的排序算法能夠在排序結(jié)果頂部返回相關(guān)的文檔。 在

3、TREC數(shù)據(jù)集上的試驗(yàn)中，最有效的排序算法來自于被明確定義的檢索模型。（在商用的搜索引擎中，所使用的檢索模型沒用明確的定義，但其排序算法都依賴于堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)）信息檢索模型 相關(guān)性概念 信息檢索系統(tǒng)的形式化表示相關(guān)性 主題相關(guān)（一篇文檔被判定和一個(gè)查詢是同一主題）1.相關(guān)性 用戶相關(guān) （考慮用戶在判定相關(guān)性時(shí)涉及的所有因素） 二元相關(guān)（簡(jiǎn)單判定一篇文檔是相關(guān)還是非相關(guān)）2.相關(guān)性 多元相關(guān) （從多個(gè)層次判斷相關(guān)性）信息檢索模型形式化表示信息檢索系統(tǒng)的形式化表示 D,Q,F,R(Di,q)1.文檔表示 D 文檔集合的機(jī)內(nèi)表示 D=D1, D2 , , Dm 為了滿足檢索匹配所要求的快速與便利，文

4、檔Di通常由從文檔中抽取的能夠表達(dá)文檔內(nèi)容的特征項(xiàng)（如索引項(xiàng)/檢索詞/關(guān)鍵詞）來表示 設(shè)T=t1, t2 , , tn 為系統(tǒng)索引項(xiàng)集合。 則Di =di1,di2 , ,din (dij0) dij索引詞tj在文檔Di中的重要性（權(quán)值weight）信息檢索模型 D,Q,F,R(Di,q)2 查詢項(xiàng)Q表示 查詢項(xiàng)Q表示為有n個(gè)權(quán)值的向量： Q=(q1,q2,q3,qn) 其中qj是第j個(gè)詞項(xiàng)的權(quán)值。3 F 文檔與查詢查詢之間的匹配框架 4 R(Di, q)文檔與用戶查詢之間相關(guān)度計(jì)算函數(shù)例： D1：Tropical Freshwater Aquarium Fish. D2：Tropical F

5、ish,Aquarium Care,Tank Setup. D3：Keeping Tropical Fish and Goldfish in Aquariums,and Fish Bowls. D4：The Tropical Tank HomeTropical Fish and Aquariums. 文檔向量表示：Terms Documents D1 D2 D3 D4aquarium 1 1 1 1bowl 0 0 1 0care 0 1 0 0Fish 1 1 2 1Freshwater 1 0 0 0Goldfish 0 0 1 0Homepage 0 0 0 1Keep 0 0 1 0S

6、etup 0 1 0 0Tank 0 1 0 1Tropical 1 1 1 2查詢表示：如：查詢項(xiàng)為“tropical fish”,則基于以上查詢項(xiàng)的向量表示形式為： q=(0,0,0,1,0,0,0,0,0,0,1).信息檢索模型信息檢索模型 1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討布爾模型最早的IR模型 1957年，YBar-Hille就對(duì)布爾邏輯應(yīng)用于計(jì)算機(jī)信息檢索的可能性進(jìn)行了探討目前仍然應(yīng)用于商業(yè)系統(tǒng)中布爾模型的前提假設(shè)： 1.在檢索到的集合中所有文檔關(guān)于相關(guān)

7、性是等價(jià)的。 2.相關(guān)性是二元的。特點(diǎn) 1.檢索的結(jié)果只輸出結(jié)果（TURE | FALSE)。 2.查詢項(xiàng)被描述為布爾邏輯操作符(AND,OR,NOT)。布爾模型 Q 查詢q被表式成索引項(xiàng)的布爾組合形式 為方便計(jì)算文檔D和查詢q之間的相關(guān)度，一般將查詢q的布爾表達(dá)式轉(zhuǎn)換成析取范式（Disjunctive Normal Form，DNF）的形式Example q=( a b ) z ( az )( b z ) (1,0,1)(1,1,1) (0,1,1)析取范式（1）由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式。 （2）僅由有限個(gè)文字構(gòu)成的合取式稱為簡(jiǎn)單合取式。 布爾模型Example： q= 病

8、毒and（計(jì)算機(jī)or 電腦）and not 醫(yī) D: D1 ： 據(jù)報(bào)道計(jì)算機(jī)病毒最近猖獗 D2 ：小王雖然是學(xué)醫(yī)的，但對(duì)研究電腦病毒也感興趣 D3：計(jì)算機(jī)程序發(fā)現(xiàn)了艾滋病病毒傳播途徑上述文檔哪一個(gè)會(huì)被檢索到？ q=病毒(計(jì)算機(jī)電腦) 醫(yī) q-dnf=(病毒計(jì)算機(jī)醫(yī)) (病毒電腦醫(yī)) 采用完全匹配的方式 -If sim(Di,q)=1,返回 -If sim(Di,q)=0，不返回布爾模型ExampleD- D1：a,b,c,f,g,h D1=(1,1,0)- D2：a,f,b,x,y,z D2=(1,1,1)q- (ab) z (1,0,1) (0,1,1) (1,1,1)F-sim(D1,q)

9、=0-sim(D2,q)=1R-將文檔2返回布爾模型缺點(diǎn)：效率完全依賴于用戶，包含特定檢索詞的所有文檔將按照某種和相關(guān)性無關(guān)的順序（如：日期）呈現(xiàn)給用戶。優(yōu)點(diǎn)：查詢項(xiàng)無局限性，可以是任何文檔的特征而只非詞語(yǔ)，可以直接在檢索規(guī)范中融入元數(shù)據(jù)，如文檔日期，文檔類型。比排序檢索更有效，文檔可以在搜索過程中快速被剔除。信息檢索模型 1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 向量空間模型向量空間模型（Vector Space Model，VSM）是由GSalton等人在1958年提出的代表系統(tǒng) SMART（System for

10、the Manipulation and Retrieval of Text）這一系統(tǒng)理論框架到現(xiàn)在仍然是信息檢索技術(shù)研究的基礎(chǔ)向量空間模型1 .仍然采用如前所述的信息檢索系統(tǒng)的形式化表示。2 .向量空間模型的定義： D=D1, D2, Di=(Di1 , Di2 , ,Din ) Dij0 Q q= (q1 , q2 , ,qn ) qj0 F 非完全匹配方式 R 在VSM中，由于文檔和查詢都是向量，因此用文檔和查詢兩個(gè)向量相似度來估計(jì)文檔和查詢的相關(guān)性 文檔和查詢之間的相關(guān)度具有較強(qiáng)的可計(jì)算性和可操作性，不再只有0和1兩個(gè)值 sim(Di ,q)3 前提假設(shè) 1.在檢索到的集合中所有文檔關(guān)

11、于相關(guān)性是不等價(jià)的。 2.相關(guān)性是多元元的。 3.查詢關(guān)鍵字之間是相互獨(dú)立的。向量空間模型例圖：相似度度量的提出 基于以上表示和分析可以通過計(jì)算表示文檔和查詢點(diǎn)之間的距離來進(jìn)行排序。詞項(xiàng)1詞項(xiàng)2詞項(xiàng)3查詢文檔2文檔1向量空間模型余弦相似度度量方法內(nèi)積值沒有界限 不象概率值，要在(0,1)之間對(duì)長(zhǎng)文檔有利 內(nèi)積用于衡量有多少詞項(xiàng)匹配成功，而不計(jì)算有多少詞項(xiàng)匹配失敗 長(zhǎng)文檔包含大量獨(dú)立詞項(xiàng)，每個(gè)詞項(xiàng)均多次出現(xiàn)，因此一般而言，和查詢式中的詞項(xiàng)匹配成功的可能性就會(huì)比短文檔大。利用向量長(zhǎng)度對(duì)內(nèi)積進(jìn)行歸一化向量空間模型Example D1=(0.5,0.8,0.3) D2=(0.9,0.4,0.2) Q=

12、(1.5,1.0,0) cos(D1,Q)=0.87; cos(D2,Q)=0.97;優(yōu)點(diǎn)：- 反映出不同關(guān)鍵詞在文檔中的重要程度。- 可以根據(jù)結(jié)果文檔對(duì)于查詢串的相關(guān)度通過余弦相似度度量等公式對(duì)結(jié)果文檔進(jìn)行排序- 可以控制輸出結(jié)果的數(shù)量向量空間模型缺點(diǎn)： 認(rèn)為關(guān)鍵詞之間是相互獨(dú)立的，這一假設(shè)有時(shí)不符合自然語(yǔ)言的實(shí)際情況，未能揭示詞語(yǔ)之間的關(guān)系。如何確定詞項(xiàng)在文檔中的權(quán)值？ 使用tf.idf方法，(tf索引項(xiàng)在一個(gè)文檔中出現(xiàn)的次數(shù)；idf索引項(xiàng)在整個(gè)文檔集合中出現(xiàn)的頻率，稱為反文檔頻率，如果一個(gè)詞素出現(xiàn)在少量的文檔中，則該詞項(xiàng)被賦予較大的權(quán)值，參考香農(nóng)信息論），該方法有很多變形，但都是基于tf

13、和idf的組合形式。 是文檔Di中詞項(xiàng)k的頻率，fik是詞項(xiàng)k在文檔中出現(xiàn)的次數(shù)。 向量空間模型為了避免長(zhǎng)文檔中很多詞項(xiàng)只出現(xiàn)一次，其他詞項(xiàng)出現(xiàn)成百上千次，對(duì)以上取對(duì)數(shù)。倒置文檔頻率反映了文檔數(shù)據(jù)集中詞項(xiàng)的重要性。Idfk是詞項(xiàng)k的倒置文檔頻率，N是文檔數(shù)據(jù)集中文檔的個(gè)數(shù)，nk是詞項(xiàng)k出現(xiàn)過的文檔個(gè)數(shù)。向量空間模型最終典型的文檔詞項(xiàng)權(quán)值形式為：詞項(xiàng)頻率加1是為了保證頻率為1的詞項(xiàng)具有非零權(quán)值。著名的Rocchio算法基于向量空間模型，并加入了用戶判定文檔的相關(guān)性來修改查詢項(xiàng)。香農(nóng)信息論信息量是指從N個(gè)相等可能事件中選出一個(gè)事件所需要的信息度量或含量,也就是在辯識(shí)N個(gè)事件中特定的一個(gè)事件的過程中

14、所需要提問“是或否”的最少次數(shù). 香農(nóng)（C. E. Shannon）信息論應(yīng)用概率來描述不確定性。信息是用不確定性的量度定義的.一個(gè)消息的可能性愈小,其信息量愈多;而消息的可能性愈大,則其信息愈少.事件出現(xiàn)的概率小，不確定性越多，信息量就大，反之則少如何計(jì)算信息量的多少？在日常生活中，極少發(fā)生的事件一旦發(fā)生是容易引起人們關(guān)注的，而司空見慣的事不會(huì)引起注意，也就是說，極少見的事件所帶來的信息量多。如果用統(tǒng)計(jì)學(xué)的術(shù)語(yǔ)來描述，就是出現(xiàn)概率小的事件信息量多。因此，事件出現(xiàn)得概率越小，信息量愈大。即信息量的多少是與事件發(fā)生頻繁(即概率大小)成反比。信息檢索模型 1.1 信息檢索模型的定義 1.2 布爾模

15、型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討概率模型概率論模型，亦稱為二值獨(dú)立檢索模型。1976年由Roberston和Sparck Jones提出的經(jīng)典概率模型。在概率的框架下解決IR的問題。、對(duì)于特定的查詢，計(jì)算相關(guān)文檔的概率和不相關(guān)文檔的概率。換句話說，當(dāng)P(R|D)P(NR|D)時(shí)，判定文檔是相關(guān)的。采用貝葉斯決策法則。概率模型貝葉斯定理：獨(dú)立假設(shè)定理：P(AB)= P(A) P(B) 當(dāng)且僅當(dāng) A與B相互獨(dú)立。由此對(duì)一篇文檔而言，假設(shè)文檔中的各個(gè)索引詞相互獨(dú)立，則有： P(dj)=P(k1)P(kt)如：假

16、設(shè)詞項(xiàng)“總統(tǒng)”在相關(guān)文檔中的概率為0.02，“林肯”的概率為0.03，如果新的文檔中包括這兩個(gè)詞項(xiàng)，那么假設(shè)詞項(xiàng)的出現(xiàn)是獨(dú)立的，則在相關(guān)文檔中詞語(yǔ)整體出現(xiàn)的概率為0.02X0.03=0.0006。概率模型1.設(shè)索引詞的權(quán)重為二值的，即： 2.R表示已知的相關(guān)文檔集（或最初的猜測(cè)集），用 表示R的補(bǔ)集。 表示文檔dj與查詢q相關(guān)的概率， 表示文檔dj與查詢q不相關(guān)的概率。文檔dj與查詢q的相似度sim(dj, q)可以定義為：概率模型 根據(jù)貝葉斯定理有概率模型 假設(shè)索引詞項(xiàng)獨(dú)立，則這是概率模型中排序計(jì)算的主要表達(dá)式。概率模型 取對(duì)數(shù)，在相同背景下，忽略對(duì)所有因子保持恒定不變的因子，則有概率模型

17、如何計(jì)算上式中的 和 呢 ？ 簡(jiǎn)單假設(shè)作為最初的猜測(cè)1). 對(duì)所有的索引詞ki是恒定不變的，通常取為0.5，即 2).不相關(guān)文檔中的索引詞ki的分布可以通過文檔集中索引詞的分 布來估計(jì)，即其中，ni表示包含索引詞ki 的文檔數(shù)， N表示集合中的文檔總數(shù)。初始值確定后，根據(jù)與查詢q相關(guān)的大小進(jìn)行初步排序，取前若干個(gè)文檔作為相關(guān)查詢集合。之后通過如下方法進(jìn)行改進(jìn)(即開始遞歸計(jì)算)。概率模型總結(jié)：在此模型中，假設(shè)詞項(xiàng)的權(quán)重是二值的，則文檔可表示為一組二元向量，即Di=（d1,d2,dn),其中di=1表示詞項(xiàng)i出現(xiàn)在文檔中，反之為0。假設(shè)二：詞項(xiàng)的出現(xiàn)的獨(dú)立的。（二元獨(dú)立模型，基于此模型的算法有BM

18、25算法）該方法的缺點(diǎn):不考慮索引詞在文檔中出現(xiàn)的頻率,所有權(quán)值都是二元的.索引詞之間相互獨(dú)立的假設(shè)。優(yōu)點(diǎn) 文檔可以按照相關(guān)概率遞減的順序來排序。信息檢索模型 1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 典型的搜索引擎排序算法1.Yahoo!搜索引擎列出影響相關(guān)程度的因素有：和查詢字符創(chuàng)相同的字串多寡。2.詞頻和位置加權(quán)算法。 核心思想：以空間向量模型為基礎(chǔ) ，以關(guān)鍵字與網(wǎng)頁(yè)的關(guān)系作為網(wǎng)頁(yè)排序的依據(jù)，關(guān)鍵詞與網(wǎng)頁(yè)的關(guān)系是根據(jù)關(guān)鍵詞在網(wǎng)頁(yè)中出現(xiàn)的次數(shù)和位置兩個(gè)方面進(jìn)行權(quán)值的計(jì)算。 關(guān)鍵詞的頻次采用上文中的頻次計(jì)算方法 ；

19、位置加權(quán)則是根據(jù)關(guān)鍵詞在網(wǎng)頁(yè)中出現(xiàn)的不同位置及版式來賦予不同的權(quán)值，位置的重要性不同，則權(quán)值不同，版式不同，權(quán)值也有區(qū)別。其中關(guān)鍵詞的位置有:網(wǎng)頁(yè)標(biāo)題、META標(biāo)簽、正文標(biāo)題、正文內(nèi)容、超鏈接錨文本等;版式有:字號(hào)大小、是否加粗等強(qiáng)調(diào)特征。對(duì)于重要的位置如標(biāo)題、正文的結(jié)尾等出現(xiàn)的關(guān)鍵詞則賦予較大的權(quán)值。 該排序算法根據(jù)關(guān)鍵詞的位置和頻次加權(quán)得出關(guān)鍵詞與網(wǎng)頁(yè)的相似度，按照關(guān)鍵詞在網(wǎng)頁(yè)中的權(quán)值大小對(duì)該搜索結(jié)果進(jìn)行排序。 其核心公式為上文中的余弦相似度量公式。缺點(diǎn)：比較適用于結(jié)構(gòu)化文檔數(shù)據(jù)，無法應(yīng)對(duì)關(guān)鍵詞堆砌現(xiàn)象。3 .Google核心排序算法：PageRank算法。典型的搜索引擎排序算法PageRan