鏈接分析算法之：主題敏感PageRank

  前面的討論提到。PageRank忽略了主題相關性，導致結果的相關性和主題性降低，對于不同的用戶，甚至有很大的差別。例如，當搜索“蘋果”時，一個數碼愛好者可能是想要看 iphone 的信息，一個果農可能是想看蘋果的價格走勢和種植技巧，而一個小朋友可能在找蘋果的簡筆畫。理想情況下，應該為每個用戶維護一套專用向量，但面對海量用戶這種方法顯然不可行。所以搜索引擎一般會選擇一種稱為主題敏感PageRank（Topic-Sensitive PageRank ）的折中方案。主題敏感PageRank的做法是預定義幾個話題類別，例如體育、娛樂、科技等等，為每個話題單獨維護一個向量，然后想辦法關聯用戶的話題傾向，根據用戶的話題傾向排序結果。

      主題敏感PageRank是PageRank算法的改進版本，該算法已被Google使用在個性化搜索服務中。

1. 基本思想

基本思想：

       通過離線計算出一個與某一主題相關的PageRank向量集合，即計算某個頁面關于不同主題的得分。主要分為兩個階段：主題相關的PageRank向量集合的計算和在線查詢時主題的確定（即在線相似度的計算）。 

2. 主題敏感PageRank計算流程

1、確定話題分類

           主題敏感PageRank參考ODP網站(www.dmoz.org)，定義了16個大的主題類別，包括體育、商業、科技等。ODP(Open Directory Project)是人工整理的多層級網頁分類導航站點（參見圖1），在頂級的16個大分類下還有更細致的小

                                                                   圖1  ODP首頁

粒度分類結構，在最底層目錄下，人工收集了符合該目錄主題的精選高質量網頁地址，以供互聯網用戶導航尋址。主題敏感PageRank采用了ODP最高級別的16個分類類別作為事先定義的主題類型。 

2、網頁topic 歸屬

       這一步需要將每個頁面歸入最合適的分類，具體歸類有很多算法，例如可以使用 TF-IDF 基于詞素歸類，也可以聚類后人工歸類。這一步最終的結果是每個網頁被歸到其中一個 topic。

3、分topic 向量計算

      在PageRank的向量迭代公式：

     即R = q  × P * R + ( 1 一 q) * e/N  （e單位向量）

     而在主題敏感PageRank中，向量迭代公式為：

          首先是單位向量e變為了s。

          而s是這樣一個向量：對于某 topic 的s，如果網頁k在此 topic 中，則s中第k個元素為1，否則為0。注意對于每一個 topic 都有一個不同的s。而|s |表示s中 1 的數量。

        假設有頁面A，B，C, D，假設頁面A歸為 Arts，B歸為 Computers，C歸為 Computers，D歸為 Sports。那么對于 Computers 這個 topic，s就是：

     假設我們設置阻尼系數q=0.8， 而|s|=2, 因此，迭代公式為：

       最后算出的向量就是 Computers 這個 topic 的 rank。如果實際計算一下，會發現B、C頁在這個 topic 下的權重相比上面非 Topic-Sensitive 的 rank 會升高，這說明如果用戶是一個傾向于 Computers topic 的人（例如程序員），那么在給他呈現的結果中B、C會更重要，因此可能排名更靠前。

4. 在線相似度計算

        最后一步就是在用戶提交搜索時，確定用戶的 topic 傾向，以選擇合適的 rank 向量。主要方法有兩種：

       一種是列出所有 topic 讓用戶自己選擇感興趣的項目，這種方法在一些社交問答網站注冊時經常使用；

       另外一種方法利用“用戶查詢分類器”對查詢進行分類，即搜索引擎會通過某種手段（如 cookie 跟蹤）跟蹤用戶的行為，進行數據分析判斷用戶的傾向。

       如圖2，假設用戶輸入了查詢請求“喬丹”，查詢詞“喬丹”隸屬于體育類別的概率為0.6，娛樂類別的概率為0.1,商業類別的概率為0.3。                                              

                                            圖2 在線相似度計算

       在進行上述用戶查詢分類計算的同時，搜索系統讀取索引，找出包含了用戶查詢“喬丹”的所有網頁，并獲得已計算好的各個分類主題的PageRank值，在圖6-21的例子里，假設某個網頁A的各個主題PageRank值分別為體育0.2，娛樂0.3以及商業0.1。

      得到用戶查詢的類別向量和某個網頁的主題PageRank向量后，即可計算這個網頁和查詢的相似度。通過計算兩個向量的乘積就可以得出兩者之間的相關性。在圖6-21的例子里，網頁A和用戶查詢“喬丹”的相似度為：

Sim(“喬丹”,A)= 0.6*0.2+0.1*0.3+0.3*0.1=0.18

      對包含“喬丹”這個關鍵詞的網頁，都根據以上方法計算，得出其與用戶查詢的相似度后，就可以按照相似度由高到低排序輸出，作為本次搜索的搜索結果返回給用戶。

3. 利用主題敏感PageRank構造個性化搜索    

       以上內容介紹的是主題敏感PageRank的基本思想和計算流程，從其內在機制來說，這個算法非常適合作為個性化搜索的技術方案。

    在圖2所示例子里，計算相似度使用的只有用戶當前輸入的查詢詞“喬丹”，如果能夠對此進行擴展，即不僅僅使用當前查詢詞，也考慮利用用戶過去的搜索記錄等個性化信息。比如用戶之前搜索過“耐克”，則可以推斷用戶輸入“喬丹”是想購買運動服飾，而如果之前搜索過“姚明”，則很可能用戶希望獲得體育方面的信息。通過這種方式，可以將用戶的個性化信息和當前查詢相融合來構造搜索系統，以此達到個性化搜索的目的，更精準的提供搜索服務。

4. 主題敏感PageRank與PageRank的差異 

      PageRank算法基本遵循前面章節提到的“隨機游走模型”，即用戶在瀏覽某個網頁時，如果希望跳轉到其它頁面，則隨機選擇本網頁包含的某個鏈接，進入另外一個頁面。主題敏感PageRank則對該概念模型做出改進，引入了更符合現實的假設。一般來說用戶會對某些領域感興趣，同時，當瀏覽某個頁面時，這個頁面也是與某個主題相關的（比如體育報道或者娛樂新聞），所以，當用戶看完當前頁面，希望跳轉時，更傾向于點擊和當前頁面主題類似的鏈接，即主題敏感PageRank是將用戶興趣、頁面主題以及鏈接所指向網頁與當前網頁主題的相似程度綜合考慮而建立的模型。很明顯，這更符合真實用戶的瀏覽過程。

     PageRank是全局性的網頁重要性衡量標準，每個網頁會根據鏈接情況，被賦予一個唯一的PageRank分值。主題敏感PageRank在此點有所不同，該算法引入16種主題類型，對于某個網頁來說，對應某個主題類型都有相應的PageRank分值，即每個網頁會被賦予16個主題相關PageRank分值。

     在接受到用戶查詢后，兩個算法在處理方式上也有較大差異。PageRank算法與查詢無關，只能作為相似度計算的一個計算因子體現作用，無法獨立使用。而主題敏感PageRank是查詢相關的，可單獨作為相似度計算公式使用。而且，在接收到用戶查詢后，主題敏感PageRank還需要利用分類器，計算該查詢隸屬于事先定義好的16個主題的隸屬度，并在相似度計算時的排序公式中利用此信息。

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