PAGEPAGE27第7章內(nèi)容檢索子系統(tǒng)設(shè)計及其核心算法搜索引擎對檢索結(jié)果排序的依據(jù)：檢索詞與網(wǎng)頁內(nèi)容的相似程度；網(wǎng)頁質(zhì)量評估結(jié)果；用戶偏好情況；競價情況。內(nèi)容檢索子系統(tǒng)：計算查詢詞與頁面內(nèi)容相關(guān)度。本章內(nèi)容：傳統(tǒng)檢索模型中文本與查詢相關(guān)度計算。7.1文本信息檢索模型信息檢索模型：布爾模型（BooleanModel）、向量空間模型（VectorSpaceModel）概率模型（ProbabilisticModel）。檢索模型間差異：如何定義和計算文檔和檢索詞之間的關(guān)系，即計算文檔D與查詢詞Q之間相關(guān)程度的函數(shù)f(Q,D)。7.1.1布爾模型查詢詞：一個布爾表達(dá)式，由關(guān)鍵詞、邏輯運(yùn)算符構(gòu)成，表達(dá)用戶希望文檔所具有的特征。文檔嚴(yán)格符合檢索詞的要求才被檢索出來，因此布爾檢索模型又稱為“完全匹配檢索”(Exact-MatchRetrieval）。例：查找既含有“清華”又含有“大學(xué)”的網(wǎng)頁查詢詞：“清華AND大學(xué)”布爾模型邏輯算符及含義1、邏輯與AND兩個變量的值都為“真”，結(jié)果為“真”，否則為“假”。例：檢索“清華大學(xué)招生”“清華大學(xué)AND招生”A包含“清華大學(xué)”的頁面；B包含“招生”的頁面；A、B相交的部分（陰影部分）則為同時包含“清華大學(xué)”和“招生”兩個關(guān)鍵詞的網(wǎng)頁。2、邏輯或0R如果其兩個變量中有一個值為“真”,則結(jié)果為“真”，否則結(jié)果為“假”。例：檢索“北京大學(xué)”相關(guān)信息?！氨本┐髮W(xué)OR北大”網(wǎng)頁只需要包含這兩個關(guān)鍵詞中的至少一個即可。A含有“北京大學(xué)”的頁面；B含有“北大”的頁面；A和B中的所有頁面（陰影部分）均應(yīng)返回。3、邏輯非NOT用NOT表示不含有某個關(guān)鍵詞的網(wǎng)頁”例：檢索“除招生外的清華大學(xué)信息”“清華大學(xué)NOT招生”在含有“清華大學(xué)”的網(wǎng)頁中排除含有“招生”的網(wǎng)頁。A有“清華大學(xué)”的頁面；B有“招生”的頁面；從A中剔除屬于B的頁面查詢詞為布爾表達(dá)式：分別檢索含有關(guān)鍵詞Kl、K2、K3、K4的文檔集合，記為Cl、C2、C3、C4，然后通過下式運(yùn)算，得到返回文檔集合｛Docl,Doc2,Doc3｝。缺點：返回結(jié)果是二元的，僅有相關(guān)、不相關(guān)兩種狀態(tài)，無法對文檔進(jìn)行排序。一般用戶很難將搜索需求用布爾表達(dá)式表達(dá)出來。7.1.2向量空間模型向量空間模型的基本思想：事物可以用共同的原子單元表示，將原子單元看作基向量，構(gòu)建n維空間，事物則對應(yīng)n維空間的一個向量，這樣可以用向量之間的差別來度量相似度。文檔、查詢詞都用向量表示，相似度可以通過這兩個向量的差別來度量。文本檢索中使用向量空間模型：詞項作為原子單元，用網(wǎng)頁中詞項構(gòu)成一個大小為n的詞匯表，詞匯表就構(gòu)成了一個n維空間，網(wǎng)頁可用空間上的一個向量來表示。例：網(wǎng)頁可以表示為如下n維向量：其中Wij表示文檔i在第j個詞項上的權(quán)重，這樣含d個頁面的集合就可以表示為一個矩陣：矩陣中，每一行代表一個文檔，每一列代表一維，文檔在某個詞項上的權(quán)重。例：有4個文檔建倒排索引，去除停用詞，假設(shè)某個詞項在文檔中的權(quán)重是它出現(xiàn)的次數(shù)，可以得到矩陣：根據(jù)矩陣，每個文檔都可以表示為16維的向量。文檔dl的向量：（1，1，1，1，1，1，0，0，0，0，0，0，0，0，0，0）。查詢詞“清華大學(xué)”的向量（1，1，0，0，0，0，0，0，0，0，0，0，0，0，0，0）。文本的相似度計算：例如：兩個文檔分別表示為：1、內(nèi)積相似度D1=(0.5,0.8,0.2),D2=（0.9,0.4,1.0)內(nèi)積相似度：Sim(Dl,D2)=0.5*0.9+0.8*0.4+0.2*1.0=0.97缺點：文檔越長，文檔對應(yīng)的向量權(quán)重就會越大，由于內(nèi)積相似度中向量值越大，相似度越大，因此內(nèi)積相似度會在較長文檔上得到較大相似度。假設(shè)D3=(1.0,1.6,0.4)，D4=(1.8,0.8,2.0)，D1、D2中出現(xiàn)的詞項在D3、D4中分別加倍出現(xiàn)，D3、D4的長度分別是D1、D2的兩倍。Sim(D3,D4)=1.0*1.8+1.6*0.8+0.4*2.0=3.88應(yīng)該有下式成立Sim(D3,D4)=Sim(Dl,D2)內(nèi)積相似度的問題在于它的相似度度量更偏向于較長的文檔2、余弦相似度與內(nèi)積相似度不同在于對內(nèi)積相似度進(jìn)行了歸一化。對于余弦相似度，我們可以想象它首先對文檔向量進(jìn)行歸一化，使得每個文檔對應(yīng)的向量中的權(quán)重之和為1。向量的相似度只與夾角有關(guān)，而與文檔的長度無關(guān)；例：D1、D2的余弦相似度：D3、D4的相似度為：說明余弦相似度通過歸一化避免了文檔長度對相似度度量的影響。文檔D與查詢詞Q相似度可以計算其余弦相似度：假設(shè)給定查詢詞，其向量為：Q=（1.5,1.0,0.0)Q與D1、D2的余弦相似度為：Dl與Q的相似度>D2與Q的相似度原因：第3個詞項的權(quán)重很大，而查詢詞中沒有出現(xiàn)第3個詞項，由于余弦相似度的歸一化作用，得到Dl的相似度較大。詞項在查詢詞或者文檔中的權(quán)重計算向量空間模型中，詞項在查詢詞或者文檔中的權(quán)重，代表了詞項在查詢詞或者文檔中的重要性。TF-IDF權(quán)重計算方法：TF*IDFTF：詞項在該文檔或者查詢詞中出現(xiàn)的頻度；IDF：文檔集合中出現(xiàn)該詞項的文檔數(shù)的倒數(shù)；詞項k在文檔Di中的TF值：其中cik：詞項k在Di中出現(xiàn)的次數(shù)TF：表示詞項在文檔中的重要程度。IDF：表示詞項在文檔集合中的重要程度一個詞項出現(xiàn)的文檔數(shù)越多，說明該詞項的區(qū)分度越差，其在文檔集合中的重要性就越低。詞項k的IDF值計算：其中：N表示集合中的文檔數(shù)；nk表示出現(xiàn)詞項k的文檔數(shù)。假如一個詞項在集合的幾乎所有文檔中都出現(xiàn)，例如中文的一些停用詞“的”、“了”、“著”等，那么它在文檔集合中沒有任何重要性可言。而當(dāng)一個詞項只在某個文檔中出現(xiàn)的時候，這個詞項的IDF值最大。TF-IDF權(quán)重計算方法的意義是：詞項的重要性隨著它在文檔中出現(xiàn)的次數(shù)增多而增加，但同時會隨著它在集合中出現(xiàn)的頻率的增多而下降。\給定TF和IDF后，詞項k在文檔Di中的TF-IDF權(quán)重為：詞項在查詢詞中的權(quán)重計算方法與此類似。在搜索引擎中應(yīng)用基于向量空間模型存在的問題1、查詢詞向量與文檔向量不匹配搜索引擎中，查詢詞平均僅有2-3個詞，文檔有數(shù)百個、數(shù)千個詞。存在把高維文檔向量向低維查詢空間映射問題。查詢向量、文檔向量使用的特征詞項不匹配，有研究表明查詢向量與相關(guān)文檔向量的夾角平均74度；查詢向量、相關(guān)文檔可能對同樣的概念使用了不同的詞項進(jìn)行描述；使用向量夾角的方法衡量文檔之間的相似性遠(yuǎn)非完美；問題的解決辦法：利用錨文本，提高網(wǎng)頁向量表示的精確性；對查詢詞進(jìn)行擴(kuò)展，降低查詢詞對應(yīng)向量過于稀疏的問題。例：查詢詞“清華大學(xué)”，可擴(kuò)展“清華”、“THU”、“Tsinghua”等關(guān)鍵詞。用戶先驗行為信息積累搜索引擎會記錄用戶的查詢行為，如輸人的查詢詞、點的擊網(wǎng)頁，在網(wǎng)頁上停留的時間等。大部分用戶在輸人某關(guān)鍵詞后會點擊某個網(wǎng)頁，那么對于新的該查詢詞請求，將該網(wǎng)頁的排序適當(dāng)提前。用戶行為的分析可以包括兩個方面：用戶群體整體表現(xiàn)出來的搜索偏好和熱點分析；用戶個體的檢索偏好的分析谷歌公司記錄注冊用戶查詢歷史界面，用于用戶的個性化檢索2、不同詞項間并非獨(dú)立關(guān)系向量空間模型基本假設(shè)：特征向量之間是正交關(guān)系，即各特征向量之間是獨(dú)立不相關(guān)的。詞項之間存在聯(lián)系，體現(xiàn)在詞項與詞項在網(wǎng)頁中共同出現(xiàn)的概率有很大差別。搜索“劉奕群胡錦濤”、“劉奕群馬少平”假設(shè)存在的問題“大學(xué)”、“高?！贝嬖谕x關(guān)系；如果查詢詞中有“大學(xué)”，某個文檔只出現(xiàn)了“高?！?；那么根據(jù)向量空間模型它們之間的相似度為0，問題主要解決方法：計算詞項之間的相關(guān)性。有多種算法根據(jù)詞項在文檔中的同現(xiàn)情況挖掘詞項之間的相關(guān)性；潛在語義分析；概率潛在語義分析3、詞項出現(xiàn)頻度的“邊際效應(yīng)”假設(shè)查詢詞有A、B兩個關(guān)鍵詞，Doc1和Doc2為兩個文檔。如A、B在兩文檔中出現(xiàn)頻度為：Freq(Doc1,A)=M,Freq(Doc1,B)=0,Freq(Doc2,A）=N,Freq(Doc2,B)=0，M>NScore(Doc1)>Score(Doc2)，Doc1排在Doc2前假設(shè)Freq(Doc1,A)=M+N,Freq(Doc1,B)=0Freq(Doc2,A)=N,Freq(Doc2,B)=MA、B在Doc1和Doc2中的頻度之和均為M+N，Doc1中只有A出現(xiàn)，Doc2中A、B均出現(xiàn)。主觀認(rèn)為應(yīng)將Doc2排在Doc1前在向量空間模型中不能讓某個詞項詞頻特別高的文檔得分太高，以至于忽略其他詞項的影響。7.1.3概率模型概率模型的基本思想：根據(jù)查詢詞Q，可以將文檔集合中文檔分為兩類R：與Q相關(guān)；～R：與Q不相關(guān)。同類文檔中，各個詞項有相同或相近的分布；屬于不同類的文檔中，詞項應(yīng)有不同的分布。計算某文檔與已知相關(guān)、不相關(guān)文檔詞項分布的相似性，可衡量此文檔與Q的相關(guān)度。給定查詢詞Q：：文檔D與查詢詞Q相關(guān)的概率；：文檔D與查詢詞Q不相關(guān)的概率；根據(jù)貝葉斯定理，；；相關(guān)度計算公式：P(R)：從文檔集合中隨機(jī)選取一篇文檔，該文檔與查詢Q相關(guān)的概率；P(~R)：從文檔集合中隨機(jī)選取一篇文檔，該文檔與查詢Q不相關(guān)的概率；P(D|R)：返回一篇相關(guān)文檔時，該文檔為D的概率；P(D|~R)：返回一篇不相關(guān)文檔時，該文檔為D的概率；P(R)/P(~R)：對給定查詢詞Q來說，是個常數(shù)，沒有必要估計該常數(shù)。詞項獨(dú)立性假設(shè)：文檔中，任意一個詞項出現(xiàn)與否不會影響到其他詞項的出現(xiàn)，它們之間相互條件獨(dú)立。因此查詢詞Q與文檔D的相似度為：D滿足以下條件，則判定其與查詢詞Q相關(guān)：上式等價于：D屬于R的可能性比屬于～R要大。假設(shè)：詞項k在R中出現(xiàn)的概率為pk，詞項k在~R中的概率為sk。其中：dk=1：詞項k出現(xiàn)在文檔D中；dk=0：詞項k沒有出現(xiàn)在此文檔D中。最后一項連乘不影響排序結(jié)果，可以將上式等價表示為：一般有～R遠(yuǎn)大R，沒有額外信息支持下；可以假設(shè)，可以用整個數(shù)據(jù)集合上的概率作為近似（即認(rèn)為不相關(guān)文檔的數(shù)目與整個數(shù)據(jù)集合的規(guī)模近似相等）。假設(shè)pk=0.5，sk=nk/N(nk為有k出現(xiàn)的不相關(guān)文檔的數(shù)目），N為集合中的文檔總數(shù)。如果有先驗知識，可以估計詞項在R和～R中出現(xiàn)的情況，則可以分別得到概率pk=rk/Rsk=(nk-rk)/(N-R)。其中：R為相關(guān)文檔集的基數(shù)，rk為相關(guān)文檔集中包含詞項k的文檔的數(shù)目nk為有k出現(xiàn)的不相關(guān)文檔的數(shù)目為了防止概率為0的情況，可以對上述概率做平滑，得到：這樣可以計算：公式效果不好在實際情況中，很難獲得關(guān)鍵詞在相關(guān)文檔集合、不相關(guān)文檔集合中的信息；采用類似IDF的統(tǒng)計信息作為近似。概率模型和TF-IDF相比，缺少TF信息，即詞項在文檔中的出現(xiàn)頻度。Robertson、SparkJones等人提出BM25公式，在概率模型中增加TF；其中ci：表示該詞項在文檔中出現(xiàn)次數(shù)；ki：公式參數(shù)；如果取0，表示該式忽略詞頻的影響；在實際應(yīng)用中一般取1.2，也就意味著TF的影響是非線性的；qci：詞項在查詢詞中的次數(shù)；k2：是參數(shù)，一般取值范圍從0-1000，k2對公式取值的影響小于k1K取值為：BM25考慮了TF-IDF、文檔長度影響。b：用于文檔長度的歸一化；0，不進(jìn)行歸一化；1，表示完全歸一化；實際應(yīng)用中取0.75最有效。7.2內(nèi)容檢索子系統(tǒng)運(yùn)行方式內(nèi)容檢索子系統(tǒng)通過檢索模型計算查詢詞、索引頁面相關(guān)度；計算其他排序依據(jù)、將各種依據(jù)綜合起來；將檢索結(jié)果頁面返回給用戶7.2.1內(nèi)容相似程度從用戶提交查詢到返回候選結(jié)果文檔的過程。在這過程中，用于計算查詢詞、文檔相關(guān)程度的參數(shù)也可得到。詞項xi在文檔d中的詞頻TFi;詞項xi的文檔頻度n；文檔d的長度length；數(shù)據(jù)集合中總的文檔數(shù)N；數(shù)據(jù)集合中的平均文檔長度averagelength等。例：詞項“清華”、“大學(xué)”在Doc1中的詞頻為2、1，文檔頻度都為2。有候選結(jié)果文檔列表、文檔和查詢詞之間參數(shù)：可以通過檢索模型計算文檔、查詢之間的相關(guān)性f(q,d)。相關(guān)性計算存在的局限性：精確匹配，文檔內(nèi)容完全包含整個查詢詞，并且是緊密相連的。查詢詞“信息學(xué)院”、切分“信息”、“學(xué)院”，然后檢索；d1：包含“信息學(xué)院”的句子，d2：一個句子包含“信息”，另一個句子包含“學(xué)院”；d1：精確匹配；查詢詞、文檔內(nèi)容精確匹配，文檔和查詢詞之間的相關(guān)性要比沒有精確匹配的文檔要高。信息檢索模型沒考慮精確匹配在計算相關(guān)性上的作用；改進(jìn)方法：倒排索引中有詞項的位置信息，計算各個詞項在同一文檔中的位置信息關(guān)系，可判斷精確匹配及次數(shù)。如果沒有精確匹配，計算文檔和查詢詞之間能夠發(fā)生匹配的最長公共字串的長度以及次數(shù)，以來計算匹配程度。網(wǎng)頁：不同域內(nèi)的文本，有不同的重要程度。標(biāo)題文本比正文文本更能代表網(wǎng)頁的主要內(nèi)容；字體較大的段落比較小的段落在網(wǎng)頁中有著更重要的地位；方法一：對查詢詞的詞頻TF進(jìn)行加權(quán)，再根據(jù)檢索模型計算查詢詞、文檔的相關(guān)度；分別表示查詢詞項在不同域中的詞頻，分別為加權(quán)；方法二：在各個域上單獨(dú)使用檢索模型計算相關(guān)性，在對各個域上的相關(guān)性進(jìn)行線性加權(quán)計算得到最終的相關(guān)性；結(jié)合文檔、查詢詞的匹配程度，得到最終的文檔、查詢詞的內(nèi)容相似程度；7.2.2數(shù)據(jù)質(zhì)量評估結(jié)果對結(jié)果網(wǎng)頁進(jìn)行排序：內(nèi)容相似程度；網(wǎng)頁數(shù)據(jù)質(zhì)量；．．．．．．．．．“溫哥華冬奧會”搜狐網(wǎng)站“溫哥華冬奧會”專題的頁面；小網(wǎng)站上的頁面；誰的權(quán)威性高？權(quán)威性高的更能滿足用戶需求。/features/sogourank.jsp搜狗評級對搜狐網(wǎng)站質(zhì)量的評估評估網(wǎng)頁質(zhì)量的方法：鏈接分析方法很多頁面有超鏈接鏈向它，該頁面就有較高的質(zhì)量；鏈向這個頁面的頁面質(zhì)量越高，該頁面的質(zhì)量也就越高。PageRank和HITS鏈接分析算法，計算頁面權(quán)威程度，衡量頁面質(zhì)量。頁面本身內(nèi)容評估頁面風(fēng)格是否獨(dú)特；頁面結(jié)構(gòu)是否合理；頁面交互是否友好；頁面內(nèi)容是否新穎；…….垃圾頁面過濾網(wǎng)站進(jìn)行作弊，制造垃圾頁面影響搜索引擎排名；關(guān)鍵詞堆砌、制造鏈接工廠；使用JavaScript進(jìn)行頁面跳轉(zhuǎn)等；搜索引擎需要針對作弊方式進(jìn)行垃圾頁面識別，將其排在比較靠后的位置。7.2.3用戶偏好情況大多數(shù)用戶所點擊的內(nèi)容在結(jié)果列表中排名應(yīng)靠前。查詢“百度”：大多數(shù)用戶點擊這個頁面；該頁面和查詢詞“百度”之間的相關(guān)性就非常高；查詢“清華”、“清華大學(xué)”、“清華大學(xué)首頁”用戶點擊頁面；將查詢聚合，形成clicktext，它從屬于被點擊的頁面。dickt