搜索引擎的檢索模型-查詢與文檔的相關度計算

1. 檢索模型概述

      搜索結果排序時搜索引擎最核心的部分，很大程度度上決定了搜索引擎的質量好壞及用戶滿意度。實際搜索結果排序的因子有很多，但最主要的兩個因素是用戶查詢和網頁內容的相關度，以及網頁鏈接情況。這里我們主要總結網頁內容和用戶查詢相關的內容。

       判斷網頁內容是否與用戶査詢相關，這依賴于搜索引擎所來用的檢索模型。檢索模型是搜索引擎的理論基礎，為量化相關性提供了一種數學模型，是對查詢詞和文檔之間進行相似度計算的框架和方法。其本質就是相關度建模。如圖所示，檢索模型所在搜索引擎系統架構位置：

    當然檢索模型理論研究存在理想化的隱含假設，及即假設用戶需求已經通過查詢非常清晰明確地表達出來了，所以檢索模型的任務不涉及到對用戶需求建模。但實際上這個和實際相差較遠，即使相同的查詢詞，不同用戶的需求目的可能差異很大，而檢索模型對此無能為力。 

2. 檢索模型分類

   大學學習的《數學模型》（姜啟源第三版），現在還有點印象。數學模型將現實問題歸結為相應的數學問題，并在此基礎上利用數學的概念、方法和理論進行深入的分析和研究，從而從定性或定量的角度來刻畫實際問題，并為解決現實問題提供精確的數據或可靠的指導。
    所以我們從所使用的數學方法上分：

1）基于集合論的IR模型(Set Theoretic models)

     布爾模型

     基于模糊集的模型

     擴展布爾模型

2）基于代數論的IR模型(Algebraic models)

     向量空間模型

     潛性語義索引模型

     神經網絡模型

3）基于概率統計的IR模型(Probabilistic models)

     回歸模型

     概率模型

     語言模型建模IR模型

     推理網絡模型

     信任度網絡模型

此外還有基于統計的機器學習排序算法。
這里主要介紹 布爾模型，向量空間模型，概率模型，語言模型，機器學習排序算法
3. 布爾模型

布爾模型：

        是最簡單的信息檢索模型，是基于集合理論和布爾代數的一種簡單的檢索模型。

基本思想：

    文檔和用戶查詢由其包含的單詞集合來表示，兩者的相似性則通過布爾代數運算來進行判定；

相似度計算：

         查詢布爾表達式和所有文檔的布爾表達式進行匹配，匹配成功的文檔的得分為1，否則為0。 

         如查詢詞：

                 蘋果 and （iphone OR Ipad2）

         文檔集合：

         D1：IPhone 5于9月13號問世。

         D2: 蘋果公司于9月13號發布新一代IPhone。

         D3：Ipad2將于3月11日在美上市。

         D4：Iphone和ipad2的外觀設計精美時尚

         D5：80后90后都喜歡iphone，但不喜歡吃蘋果。

         那么單詞與文檔關系如下圖:

         檢索結果就是D2和D5符合搜索條件。
       這類似于傳統數據庫檢索，是精確匹。一些搜索引擎的高級檢索往往是使用布爾模型的思想。如Google的高級檢索。

優點：
      在于形式簡潔、結構簡單。

缺點：

     1）準確的匹配可能導致檢出的文檔過多或過少。因為布爾模型只是判斷文檔要么相關、要么不相關，它的檢索策略基于二值判定標準，無法描述與查詢條件部分匹配的情況。因此，布爾模型實際上是一個數值檢索模型而不是信息檢索模型。

     2）盡管布爾表達式有確切的語義，但通常很難將用戶的信息需求轉換成布爾表達式。如今，人們普遍認為，給索引詞加權能極大地改善檢索效果。從對索引詞加權的方法中引出了向量模型。

4. 向量空間模型(Vector Space Model，VSM)

向量空間模型：
    康奈爾大學Salton等人上世紀70年代提出并倡導，原型系統SMART   

基本思想：

    把文檔看成是由t維特征組成的一個向量，特征一般采用單詞，每個特征會根據一定依據計算其權重，這t維帶有權重的特征共同構成了一個文檔，以此來表示文檔的主題內容。

相似性計算：

    計算文檔的相似性可以采用Cosine計算定義，實際上是求文檔在t維空間中查詢詞向量和文檔向量的夾角，越小越相似；對于特征權重，可以采用Tf*IDF框架，Tf是詞頻，IDF是逆文檔頻率因子指的是同一個單詞在文檔集合范圍的出現次數，這個是一種全局因子，其考慮的不是文檔本身的特征，而是特征單詞之間的相對重要性，特征詞出現在其中的文檔數目越多，IDF值越低，這個詞區分不同文檔的能力就越差，這個框架一般把Weight=Tf*IDF作為權重計算公式。

思路：

1）向量表示：

    文檔Dj的向量可以表示為Dj(w1j， w2j ，?，wnj ) ，其中n是系統中的單詞數目，wij 代表了標引詞i在文檔Dj中的權重。

    查詢Q的向量可以表示為Q(w1q， w2q ，?，wnq ) ，wiq代表了單詞i在查詢Q中的權重

 2）文檔–單詞矩陣(Doc-Term Matrix)：
   n篇文檔，m個標引詞構成的矩陣Am*n，每列可以看成每篇文檔的向量表示，同時，每行也可以可以看成單詞的向量表示：

3）權重計算：

       布爾權重：標引詞i在文檔j中的權重wij =0或1（出現則取1，否則取0）

       TF權重：TF（Term Frequency）是單詞在文檔中出現的次數。權重wij = TFij或者歸一化后的TF值

       TF的歸一化（Normalization）：將一篇文檔中所有的標引詞的TF值歸一化到[0,1]之間。通?？梢圆捎靡韵路绞街唬?br />           1： Wtf = 1 + log(TF)

           2：Wtf = a + （1- a）*  TF /Max(TF) 其中a為調節因子，經驗取值a=0.5 最新研究表明是0.4效果更好。
   

       單詞的文檔頻率DF（Document Frequency）：單詞在整個文檔集合中出現的文檔篇數，DF反映了單詞的區分度， DF越高表示單詞越普遍，因此其區分度越低，其權重也越低。

        逆文檔頻率（Inverse DF ，IDF）：DF的倒數，通常采用如下公式計算：（N是文檔集合中所有文檔的數目）

3) 計算權重：向量空間模型中通常采用TF* IDF的方式計算權重，即標引詞i在文檔dj的權重Wij = TFij * IDFij .
4)  相似度計算：文檔和查詢詞的相關程度(即相似度)可由它們各自向量在向量空問中的相對位置來決定。相似度計算函數有很多種，較常用的是兩個向量夾角的余弦函數。
   

     由向量的數量積定義：兩個向量的數量積（又稱“內積”、“點積”，物理學上稱為“標量積”。）是一個數量，記作a·b。若a、b不共線，則a·b=|a|·|b|·cos〈a，b〉。
     其意義：兩向量的數量積等于其中一個向量的模與另一個向量在這個向量的方向上的投影的乘積。我們把|b|cosθ叫做向量b在向量a的方向上的投影。
     兩向量a與b的數量積：a·b=|a|*|b|cosθ；其中|a|、|β|是兩向量的模，θ是兩向量之間的夾角(0≤θ≤π)。
     若有坐標a(x1,y1,z1) ；b(x2,y2,z2)，那么a·b=x1x2+y1y2+z1z2；　|a|=sqrt(x1^2+y1^2+z1^2)；|b|=sqrt(x2^2+y2^2+z2^2)。

     依定義有：cos〈a，b〉=a·b / |a|·|b|）；若a、b共線，則a·b=+-∣a∣∣b∣。
     其性質：
     1）a·a=|a|的平方。 　　
     2）a⊥b 〈=〉a·b=0。 　　

     于是文檔和提問的相似度值由以下公式獲得：
               

理解Cosine相似性，可以講每個文檔以及查詢看做t維特征空間的一個數值點。每個特征形成t維空間中的一個維度，鏈接特征空間原點和這個數值點形成一個向量，而Cosine相似性就是計算特征空間中兩個向量之間的夾角。這個夾角越小，說明兩個特征向量內容越相似。極端的情況就是兩個完全相同的文檔，其在向量空間中的兩個向量是重疊的，Cosine相似性值為1.

舉例：  

          查詢q：(<2006：1>,<世界杯：2>)

       文檔d1：(<2006：1>,<世界杯：3>,<德國：1>,<舉行：1>)

       文檔d2：(<2002：1>,<世界杯：2>,<韓國：1>,<日本：1> <舉行：1>)
       倒排索引列表：
       

       查詢和文檔進行向量的相似度計算：

       采用內積

       文檔d1和q的內積：1*1+3*2=7

       文檔d2和q的內積：2*2=4

       夾角余弦：

       文檔d1和q的夾角余弦：

       文檔d2和q的夾角余弦：

優點：1) 簡潔直觀，可以應用到很多其他領域(文本分類、生物信息學)，郵件過濾系統spamAssass。

           3) 支持部分匹配和近似匹配，結果可以排序

           4) 檢索效果不錯

缺點：1) 計算量大

           2) 單詞的不同位置會代表不同的權重，而不同的關鍵詞長度也會影響權重的大小
           3) 單詞之間的獨立性假設與實際不符：實際上，單詞的出現之間是有關系的，不是完全獨立的。如：“王勵勤”“乒乓球”的出現不是獨立的。

5. 概率模型

概率模型：

    是目前效果最好的模型之一，okapi BM25這一經典概率模型計算公式已經在搜索引擎的網頁排序中廣泛使用。概率檢索模型是從概率排序原理推導出來的。  

基本假設前提和理論：
    1).相關性獨立原則：文獻對一個檢索式的相關性與文獻集合中的其他文獻是獨立的。
    2).單詞的獨立性:單詞和檢索式中詞與詞之間是相互獨立。即文檔里出現的單詞之間沒有任何關聯，任一單詞在文檔的分布概率不依賴其他單詞是否出現。
    3).文獻相關性是二值的:即只有相關和不相關兩種。
    4).概率排序原則:該原則認為，檢索系統應將文檔按照與查 詢的概率相關性的大小排序，那么排在最前面的是最有可能被獲取的文檔
    5).貝葉斯(Bayes)定理:用公式表示為：
      P(R|d)=(d|R)·P(R)/P(d)

基本思想是：

    是通過概率的方法將查詢和文檔聯系起來,給定一個用戶查詢，如果搜索系統能夠在搜索結果排序時按照文檔和用戶需求的相關性由高到底排序，那么這個搜索系統的準確性是最優的。在文檔集合的基礎上盡可能準確地對這種相關性進行估計就是其核心。

相似度計算：
    將查詢Q和文檔D根據有沒有單詞表示為二值向量，Q={q1,q2,…}，D={d1,d2,…}，di=0或1表示文獻中沒有或有第i個單詞. 用R表示文獻相關，表示文獻不相關.
    條件概率P(R|dj )表示文檔 dj與查詢qi相關的概率

    條件概率P(|dj)表示文檔dj與查詢qi不相關的概率

    利用它們的比值計算文檔與查詢的相似度。
    若P(R|d)> P( |d)，即比值大于1，則文獻相關程度大于不相關程度，認為文獻d是相關的，否則認為文獻d不相關。在兩者相等時，人為地認為它是不相關的。

優點:
   1.采用嚴格的數學理論為依據，為人們提供了一種數學理論基礎來進行檢索決策；PubMed的related articles 。
   2.采用相關反饋原理
   3.在其中沒有使用用戶難以運用的布爾邏輯方法；
   4.在操作過程中使用了詞的依賴性和相互關系。
缺點：
   1.計算復雜度大,不適合大型網絡
   2.參數估計難度較大
   3.條件概率值難估計
   4.系統的檢索性能提高不明顯，需與其他檢索模型結合

6. 語言模型

語言模型：
    是借鑒了語音識別領域采用的語言模型技術，將語言模型和信息檢索模型相互融合的結果
基本思想：
    其他的檢索模型的思考路徑是從查詢到文檔，即給定用戶查詢，如何找出相關的文檔，該模型的思路正好想法，是由文檔到查詢這個方向，即為每個文檔建立不同的語言模型，判斷由文檔生成用戶查詢的可能性有多大，然后按照這種生成概率由高到低排序，作為搜索結果。語言模型代表了單詞或者單詞序列在文檔中的分布情況；

7. 機器學習排序算法

機器學習排序算法：
    隨著搜索引擎的發展，對于某個網頁進行排序需要考慮的因素越來越多，這是無法根據人工經驗完成的，這時候用機器學習就是非常合適的，例如Google目前的網頁排序公式考慮了200多種因子。機器學習需要的數據源在搜索引擎中較好滿足，例如用戶的搜索點擊記錄。其分成人工標注訓練、文檔特征抽取、學習分類函數以及在實際搜索系統中采用機器學習模型等4個步驟組成。人工標注訓練可由用戶點擊記錄來模擬人為對文檔相關打分的機制。

轉自：http://blog.csdn.net/hguisu/article/details/7981145