用戶差別化和主題敏感的PageRank算法

馬海波，楊楠，于新興

(大連交通大學 軟件學院，遼寧 大連 116028)*

0 引言

據中國互聯網絡信息中心發布的第28次“中國互聯網絡發展狀況統計報告”，截止2011年6月，中國共有網民4.85億，搜索引擎用戶3.86億，中國現有網站183萬個.2008年谷歌官方博客稱其擁有1萬億幅網頁頁面的索引量.由這些數據不難看出，互聯網成為現代共享信息的主要載體，無論網站、網頁數量還是用戶數量都特別巨大，搜索引擎在搜索信息方面占據主要地位.從用戶行為上看，多數用戶在使用搜索引擎的搜索結果時只會點擊搜索出來的前2頁中10到20個高相關度的搜索結果.因此如何將最能滿足用戶需求的頁面排列在搜索結果的前面變得至關重要.

在網頁排序算法中，最著名的是1998年由Sergey Brin和Lawrence Page提出的基于鏈接分析的 PageRank網頁排序算法［1］.然而 PageRank算法本身存在一些不足之處，如常見的主題漂移、對新生成的網頁所給予的PR值較低等問題.

幾乎所有的現行網頁排序方法都沒有對用戶進行差別化看待，關注的重點只是網頁重要程度本身，依據該重要程度進行排序，而沒考慮到不同用戶興趣、關注點、需求上的差異.對所有用戶，由相同的查詢詞得到同樣的搜索結果，顯然很難滿足有不同個性、不同興趣的用戶需求.

本文針對PageRank算法的未將用戶差別化看待和主題漂移的問題，提出來一種基于用戶差別化和主題敏感的PageRank算法的網頁排序方法.

1 PageRank算法

PageRank算法是基于網頁間鏈接和基于用戶的隨機沖浪模型的，主要思想是為每個網頁設定一個PR值，用來標識該網頁的重要程度.鏈接到其他網頁則相當于為該網頁投了一票，該票的權值為源網頁將自身的PR值依所有出度鏈接數量平均分配而得到，這樣將網頁間的關系看做是圖的結構，經過矩陣間迭代計算得到每個網頁的PR值.公式如下:

式中，PR(A)表示欲計算網頁A的PR值;Ti為有鏈接到網頁A的頁面;PR(Ti)為Ti頁面的PR值;d為阻尼因子，通常取0.85.

由于PageRank算法將一個網頁的PR值，以平均分配的方式分發給每個出度的鏈接頁面，而沒有考慮到鏈接出去的頁面主題與本頁面的相關程度，從而在多次迭代后造成主題漂移問題［2］.

2 對PageRank算法主題漂移問題的改進

針對主題漂移問題，很多人在PageRank算法上來進行改進，如Taher H.Haveliwala等提出的Topic-Sensitive PageRank(TH-PageRank)算法［3］和Matthew Richardson 等提出的 MP-PageRank［4］，黃德才等提出的TS-PageRank［5］都是通過改變平均傳遞PR值的方式，一定程度上修正主題漂移問題.

本文主要對TH-PageRank算法進行改進.TH-PageRank算法公式如下:

其主要思想為將每個網頁按照Open Directory Project(ODP)分類，將每個網頁分成16個主題，Aj為該網頁在每個主題下的相關度，計算出的PRj(p)為該主題下的PR值，其他參數含義同式(1).從而使得每個網頁都有16個對應主題的PR值.

在用戶查詢時，算法根據用戶輸入詞和查詢的上下文條件，用式(3)計算出每個網頁最終的PR值.

式中，qj為查詢詞對應的每個主題下的相關度;PR(p)為最終該網頁在此查詢詞下的PR值.

雖然TH-PageRank算法在一定程度上解決了主題漂移的問題，但是其同樣存在一些不合理的地方:

(1)對用戶查詢詞進行分主題計算相關度時，需要依據查詢的上下文條件，但在應用中很難有足夠多的上下文條件供計算.查詢詞過少，形成了查詢詞的主題模糊，無法準確的判斷查詢詞的主題相關度，從而影響最終網頁的PR值和排序結果;

(2)搜索引擎極高的響應速度源自對數據的離線計算，搜索時只進行查詢和簡單的排序.計算出查詢詞的主題相關度后，需要對所有查詢到的網頁重新在線計算PR值.對于可以達到上億級別的搜索結果全部重新在線計算PR值，這將是不可行的;

生物浮床是利用浮床作為載體在池塘水面種植具有特定功能且易于在水中生長的植物，其原理是利用浮床植物根部吸收、轉化、吸附、濾過養殖系統中殘留的氮、磷及有機物質轉化成植物生長所需要的營養物質，從而達到凈化水質和優化池塘生態系統的一種水體修復技術。同時，浮床植物根部形成的“泌氧與耗氧”環境是微生物生長繁殖的良好場所，且使得整個池塘養殖系統中微生物菌群的結構與功能多樣性得到有效調節。其中，浮床植物的選擇是浮床池塘養殖建立的關鍵性因素。

(3)僅有16個主題，粒度過小，過于粗糙，較難反映網頁真實的信息.

3 基于用戶差別化對主題敏感的PageRank算法的改進

用戶之間具有興趣愛好、性別、年齡、工作、背景閱歷、生活地點、對事物關注點等等差別.現如今的搜索引擎只關注網頁的重要程度，沒有對用戶不同的需求加以區分，導致對于不同的用戶，只要查詢詞相同就會返回相同的搜索結果，忽略了用戶個性需求的.

比如體育愛好者搜索Jordan時，應該將籃球明星Jordan相關網頁排序結果提前，愛好購物的用戶搜索Jordan時，其意愿更傾向于Jordan品牌的服飾，地理和旅游愛好者在搜索Jordan時，如果將約旦這個國家的風土人情介紹排列在搜索結果的前面，將更會滿足用戶的需求.再比如汽車愛好者在搜索QQ時希望得到QQ汽車的相關信息，愛好網絡聊天的用戶搜索QQ會返回一款IM.當用戶搜索附近的麥當勞時，返回的應該是本地的麥當勞信息，如果返回的是其他地點的麥當勞信息，即便PR值再高，也難以滿足用戶的需求.

這樣就需要對用戶的興趣、愛好等信息進行搜集，可通過主動和被動兩種方式.

主動方式:谷歌、百度等主要搜索引擎都有用戶登錄功能，可以在保護用戶隱私的前提下，主動要求用戶提交興趣愛好、年齡、性別、工作、生活地點等個性信息，并可以隨時進行提交、修改，當然提交的信息越多越具體，將更能反映用戶真實的需求.

被動方式:在經過用戶允許下，記錄登錄用戶的搜索時查詢詞的記錄，統計用戶的網絡收藏夾等信息.

式中，D表示每個用戶獨有的一個主題相關度向量;Wtn為該用戶在第n個主題中的興趣程度.

TF(D，T)為詞項T在同主題關鍵詞庫中出現的次數，即詞頻.IDF為倒排文檔頻率，即含有T的用戶信息文檔數的倒數.式(6)、(7)都是為防止某些奇異詞對W計算結果的干擾而進行的變型.

每個用戶興趣主題相關度的向量隨著主動和被動方式對用戶信息的搜集而進行改變.有此公式，得到了用戶針對不同主題的喜好程度的排序.并不僅限于記錄16個主題的愛好程度，將16個主題改變為可擴展的主題集，可以添加用戶上網時所處網絡，生活地點，關注網頁類型等擴展信息.用戶所在網絡可以解決聯通、電信訪問對應網絡服務器響應速度差異問題，生活地點則更好的滿足用戶實際需求，網頁類型分為具有時效性和非時效性［9］，可以對用戶信息的記錄區分用戶更傾向于關注的網頁類型.

針對TH-PageRank算法的粒度較小的問題，采用擴展的主題集，記錄和用戶興趣信息對應的信息，如服務器網絡類型，網頁信息是否具有地域性，傳統PageRank算法下的PR值等.對提取的網頁關鍵詞，運用式(8)、(9)、(10)計算出該網頁的主題相關度向量.初步計算網頁PR值的公式為:

與原公式相比，這里提供的是可擴展的主題集，不再局限于16個主題，主題相關度為該維向量值在n維向量值中的百分比.func()函數［10］依據關鍵詞在網頁不同的位置，分配不同的權重值.式(11)中j為預先設定的閾值.如果網頁在某些主題下的PR值特別小，則將其置0.

輸入查詢詞后的計算方式也不同于TH-PageRank算法.首先在對每個關鍵詞生成索引的時候記錄每個主題下前500頁面的平均PR值.具體執行方式如圖1所示.

圖1 搜索查詢詞時網頁排序流程圖

4 實驗驗證分析

算法可行性:對于網頁的PR值采用離線計算的方式，針對特定用戶的查詢詞，只進行比較、有限數量值間的排序，保障了搜索引擎的響應速度.在對網頁PR值存儲上，空間擴大了主題集中主題個數的倍數，為有限數量，對空間復雜度影響不大.

由于多數網頁的主題集中在1～3個之間，通過對主題特別小的PR值置0操作，減少噪音，形成網頁主題PR值間的稀疏矩陣.無論在運算還是存儲上都具有很高的效率.

依據用戶提供的信息和式(4)、(5)、(6)、(7)計算出該用戶在不同主題下的興趣程度.由圖2可以看出，用戶對計算機和網絡、新聞、地域性的事物比較關注.在此情況下可以判定，用戶興趣主題為計算機網絡、新聞、地域性的事物.

圖2 用戶在不同主題下的興趣程度

當用戶查詢詞為社交網絡時，返回的10個頁 面在不同主題下的PR值如附表所示.

附表 依據本文算法計算出的網頁在不同主題下的PR值

如果按照傳統的PageRank算法對網頁進行排序的結果為:5，2，7，9，1，6，10，3，4，8

用本文的算法對網頁進行排序的結果為:10，3，6，2，4，5，7，9，1，8

可以看出對于查詢詞“社交網絡”，頁面5具有較高的傳統PageRank算法下的PR值，但其所屬的主題著重于從科學研究的角度描述社交網絡，這對于一個在科學方面沒用興趣的用戶來說，雖然其有較高的重要程度，但并不是用戶的真正需求.相反頁面10雖然在傳統方法上沒有較高的重要程度，但其是從計算機網絡方面對社交網絡進行描述的，將會更加符合用戶的需求.同時本算法還具有可擴展性的優勢，與不同用戶的需求結合緊密.

5 結論

本文的算法考慮了對于同一查詢詞，不同個性用戶之間的不同的實際需求，對用戶進行差別化看待，結合改進后的主題敏感的PageRank算法，一定程度上解決了PageRank算法的主題漂移問題，提高了網頁排序的準確程度和用戶的滿意程度.

根據本文的算法，在進一步的工作中，為了能準確的獲得用戶的個性需求，應該通過對算法的大范圍應用，進一步研究用戶主動提交的個人興趣的關鍵詞達到何種程度的數量和廣度，才可以對本算法進行應用.本文對擴展的主題已經提出了一些可行的設想，需要在應用中進一步對主題進行擴展.式(11)中閾值j的在不同主題和不同的查詢結果的取值，需要在大量的運用中結合實際經驗，給出較準確的取值.本算法基于PageR-ank算法，應用中便于移植和切換算法，在具有大量用戶的全文檢索領域具有較好發展前景.

［1］Sergey Brin and Lawrence Page.The PageRank Citation Ranking:Bring Order to the Web［C］.Stanford University:Computer Science Department，1998.

［2］高琪，張永平.PageRank算法中主題漂移的研究［J］.微計算機信息，2010，89(9):117-119.

［3］HAVELIWALA.Topic-Sensitive PageRank:A Context-Sensitive Ranking Algorithm for Web Search［J］.IEEE，2007，18:365-368.

［4］RICHARDSON，DOMINGOS P.The intelligent surfer:probabilistic combination of link and content informaion in PageRank［J］.Advances in Neural Information Processing Systems，2002，14:1441-1448.

［5］黃德才，戚華春，錢能.基于主題相似度模型的TSPageRank算法［J］.小型微型計算機系統，2007，28(3):510-514.

［6］JENEI S.Structure of left-continuous triangular norms with strong induced negations:(II)Rotation-annihilation construction［J］.J.Appl.Non-Classical Logics，2001，11(3-4):351-366.

［7］JENEI S.Structure of left-continuous triangular norms with strong induced negations:(III)Construction and decomposition［J］.Fuzzy Sets and Systems，2002，128(2):197-208.

［8］JENEI S.A note on the ordinal sum theorem and its consequence for the construction of triangular norms［J］.Fuzzy Sets and Systems，2002，126(2):199-205.

［9］王勇，劉奕群，張敏，等.基于用戶興趣分析的網頁生命周期建模［C］.第三屆全國信息檢索與內容安全學術會議，2008.

［10］宋聚平，王永成，尹中航，等.對網頁PageRank算法改進［J］上海交通大學學報，2003，37(3):21-25.