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

馬海波，楊楠，于新興

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

0 引言

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

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

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

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

1 PageRank算法

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

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

由于PageRank算法將一個網(wǎng)頁的PR值，以平均分配的方式分發(fā)給每個出度的鏈接頁面，而沒有考慮到鏈接出去的頁面主題與本頁面的相關(guān)程度，從而在多次迭代后造成主題漂移問題［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算法公式如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

被動方式:在經(jīng)過用戶允許下，記錄登錄用戶的搜索時查詢詞的記錄，統(tǒng)計用戶的網(wǎng)絡(luò)收藏夾等信息.

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

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

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

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

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

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

圖1 搜索查詢詞時網(wǎng)頁排序流程圖

4 實驗驗證分析

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

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

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

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

當(dāng)用戶查詢詞為社交網(wǎng)絡(luò)時，返回的10個頁 面在不同主題下的PR值如附表所示.

附表 依據(jù)本文算法計算出的網(wǎng)頁在不同主題下的PR值

如果按照傳統(tǒng)的PageRank算法對網(wǎng)頁進行排序的結(jié)果為:5，2，7，9，1，6，10，3，4，8

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

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

5 結(jié)論

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

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

［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］.小型微型計算機系統(tǒng)，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］王勇，劉奕群，張敏，等.基于用戶興趣分析的網(wǎng)頁生命周期建模［C］.第三屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議，2008.

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