信息檢索模型與搜索引擎排序算法.ppt

信息檢索與搜索引擎排序算法,- 徐艷霞,主要內(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 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討,信息檢索模型,1 信息檢索模型的定義 什么是數(shù)學(xué)模型？ 為了某種特定目的，通過(guò)對(duì)現(xiàn)實(shí)世界的某一特定對(duì)象做出一些必要的簡(jiǎn)化與設(shè)，運(yùn)用適當(dāng)?shù)臄?shù)學(xué)工具得到的一種數(shù)學(xué)結(jié)構(gòu)。 面對(duì)相同的輸入，模型的輸出應(yīng)能夠無(wú)限地逼近現(xiàn)實(shí)世界的輸出。 信息檢索模型 是用來(lái)描述文檔和用戶查詢的表示形式以及它們之間相關(guān)性的框架,信息檢索模型,信息檢索的實(shí)質(zhì)問(wèn)題 對(duì)于所有文檔，根據(jù)其與用戶查詢的相關(guān)程度由大到小進(jìn)行排序。 信息檢索模型與搜索引擎排序算法關(guān)系 好的檢索模型在相關(guān)性上產(chǎn)生和人類決策非常相關(guān)的結(jié)果，基于好的檢索模型的排序算法能夠在排序結(jié)果頂部返回相關(guān)的文檔。 在TREC數(shù)據(jù)集上的試驗(yàn)中，最有效的排序算法來(lái)自于被明確定義的檢索模型。（在商用的搜索引擎中，所使用的檢索模型沒(méi)用明確的定義，但其排序算法都依賴于堅(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 為了滿足檢索匹配所要求的快速與便利，文檔Di通常由從文檔中抽取的能夠表達(dá)文檔內(nèi)容的特征項(xiàng)（如索引項(xiàng)/檢索詞/關(guān)鍵詞）來(lái)表示 設(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)表示 查詢項(xiàng)Q表示為有m個(gè)權(quán)值的向量： Q=(q1,q2,q3,qm) 其中qj是第j個(gè)詞項(xiàng)的權(quán)值。 3 F 文檔與查詢查詢之間的匹配框架 4 R(Di, q)文檔與用戶查詢之間相關(guān)度計(jì)算函數(shù) 例： D1：Tropical Freshwater Aquarium Fish. D2：Tropical Fish,Aquarium Care,Tank Setup. D3：Keeping Tropical Fish and Goldfish in Aquariums,and Fish Bowls. D4：The Tropical Tank Homepage-Tropical Fish and Aquariums.,文檔向量表示：,Terms Documents D1 D2 D3 D4 aquarium 1 1 1 1 bowl 0 0 1 0 care 0 1 0 0 Fish 1 1 2 1 Freshwater 1 0 0 0 Goldfish 0 0 1 0 Homepage 0 0 0 1 Keep 0 0 1 0 Setup 0 1 0 0 Tank 0 1 0 1 Tropical 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)中 典型系統(tǒng)：Lucene 布爾模型的前提假設(shè)： 1.在檢索到的集合中所有文檔關(guān)于相關(guān)性是等價(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= 病毒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，不返回,布爾模型,Example D - 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)=0 -sim(D2,q)=1 R -將文檔2返回,布爾模型,缺點(diǎn)：效率完全依賴于用戶，包含特定檢索詞的所有文檔將按照某種和相關(guān)性無(wú)關(guān)的順序（如：日期）呈現(xiàn)給用戶。 優(yōu)點(diǎn)：查詢項(xiàng)無(wú)局限性，可以是任何文檔的特征而只非詞語(yǔ)，可以直接在檢索規(guī)范中融入元數(shù)據(jù)，如文檔日期，文檔類型。比排序檢索更有效，文檔可以在搜索過(guò)程中快速被剔除。,信息檢索模型,1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討,向量空間模型,向量空間模型（Vector Space Model，VSM）是由GSalton等人在1958年提出的 代表系統(tǒng) SMART（System for 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è)向量相似度來(lái)估計(jì)文檔和查詢的相關(guān)性 文檔和查詢之間的相關(guān)度具有較強(qiáng)的可計(jì)算性和可操作性，不再只有0和1兩個(gè)值 sim(Di ,q) 3 前提假設(shè) 1.在檢索到的集合中所有文檔關(guān)于相關(guān)性是不等價(jià)的。 2.相關(guān)性是多元元的。 3.查詢關(guān)鍵字之間是相互獨(dú)立的。,向量空間模型,例圖： 相似度度量的提出 基于以上表示和分析可以通過(guò)計(jì)算表示文檔和查詢點(diǎn)之間的距離來(lái)進(jìn)行排序。,詞項(xiàng)1,詞項(xiàng)2,詞項(xiàng)3,查詢,文檔2,文檔1,向量空間模型,余弦相似度度量方法 內(nèi)積值沒(mé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=(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)度通過(guò)余弦相似度度量等公式對(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)信息論） 是文檔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)過(guò)的文檔個(gè)數(shù)。,向量空間模型,最終典型的文檔詞項(xiàng)權(quán)值形式為： 詞項(xiàng)頻率加1是為了保證頻率為1的詞項(xiàng)具有非零權(quán)值。 著名的Rocchio算法基于向量空間模型，并加入了用戶判定文檔的相關(guān)性來(lái)修改查詢項(xiàng)。,信息檢索模型,1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討,概率模型,概率論模型，亦稱為二值獨(dú)立檢索模型。 1976年由Roberston和Sparck Jones提出的經(jīng)典概率模型。在概率的框架下解決IR的問(wèn)題。,概率模型,給定一個(gè)用戶查詢，存在一個(gè)文檔集合，該集合只包括與查詢完全相關(guān)的文檔而不包括其他不相關(guān)的文檔，稱該集合為理想結(jié)果集合。 如何描述這個(gè)理想結(jié)果集合？即：該理想結(jié)果集合具有什么樣的屬性？ 基于相關(guān)反饋的原理，需要進(jìn)行一個(gè)逐步求精的過(guò)程,PRP (probability ranking principle),將信息獲取看成是一個(gè)過(guò)程：用戶提交一個(gè)查詢，系統(tǒng)提供給用戶它所認(rèn)為的相關(guān)結(jié)果列表；用戶考察這個(gè)集合后給出一些輔助信息，系統(tǒng)再進(jìn)一步根據(jù)這輔助信息（加上以前的信息）得到一個(gè)新的相關(guān)結(jié)果列表；如此繼續(xù)。 如果每次結(jié)果列表中的元素總是按照和查詢相關(guān)的概率遞減排序的話，則系統(tǒng)的整體效果會(huì)最好。 其中概率的計(jì)算應(yīng)該是基于當(dāng)時(shí)所能得到的所有信息。,概率模型-相關(guān)概念,貝葉斯定理： 詞條的獨(dú)立假設(shè)：P(AB)= P(A) P(B) 當(dāng)且僅當(dāng) A與B相互獨(dú)立 由此對(duì)一篇文檔而言，若文檔中的各個(gè)索引詞相互獨(dú)立，則有 P(dj)=P(k1)P(kt),概率模型,定義：設(shè)索引詞的權(quán)重為二值的，即： R表示已知的相關(guān)文檔集（或最初的猜測(cè)集），用 表示R的補(bǔ)集。 表示文檔dj與查詢q相關(guān)的概率， 表示文檔dj與查詢q不相關(guān)的概率。文檔dj與查詢q的相似度sim(dj, q)可以定義為：,概率模型,根據(jù)貝葉斯定理有,概率模型,假設(shè)標(biāo)引詞獨(dú)立，則 這是概率模型中排序計(jì)算的主要表達(dá)式。,概率模型,取對(duì)數(shù)，在相同背景下，忽略對(duì)所有因子保持恒定不變的因子，則有,概率模型,如何計(jì)算上式中的 和 呢 ？ 簡(jiǎn)單假設(shè)作為最初的猜測(cè) 1). 對(duì)所有的索引詞ki是恒定不變的，通常取為0.5，即 2).不相關(guān)文檔中的索引詞ki的分布可以通過(guò)文檔集中索引詞的分 布來(lái)估計(jì)，即 其中，ni表示包含索引詞ki 的文檔數(shù)， N表示集合中的文檔總數(shù)。 初始值確定后，根據(jù)與查詢q相關(guān)的大小進(jìn)行初步排序，取前若干個(gè)文檔作為相關(guān)查詢集合。之后通過(guò)如下方法進(jìn)行改進(jìn)(即開(kāi)始遞歸計(jì)算)。,概率模型,用V表示概率模型初步檢出并經(jīng)過(guò)排序的文檔子集 Vi表示V中包含索引詞ki的文檔數(shù)。 改進(jìn) 和 的過(guò)程如下： 1）用已經(jīng)檢出的文檔中索引詞ki的分布來(lái)估計(jì) 2). 假定所有未檢出的文檔都是不相關(guān)的來(lái)估計(jì) 如此遞歸重復(fù)這一過(guò)程，得到理想結(jié)果集合,概率模型,對(duì)較小的V和Vi上述計(jì)算會(huì)出現(xiàn)問(wèn)題，如V=1和Vi=0，可做一些改進(jìn)： 調(diào)整因子也可以為ni/N， 即,概率模型,該方法的缺點(diǎn): 不考慮索引詞在文檔中出現(xiàn)的頻率,所有權(quán)值都是二元的. 索引詞之間相互獨(dú)立的假設(shè)。,信息檢索模型,1.1 信息檢索模型的定義 1.2 布爾模型 1.3 向量空間模型 1.4 概率模型 1.5 典型的搜索引擎排序算法 1.6 適用于數(shù)學(xué)公式搜索引擎排序算法的探 討,典型的搜索引擎排序算法,Yahoo!搜索隱身列出影響相關(guān)程度的因素有：和差選字符創(chuàng)相同的字串多寡。 詞頻和位置加權(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)