基于用戶興趣度的PageRank改進算法

黃賢英，陳紅陽

(重慶理工大學計算機科學與工程學院，重慶 400054)

基于用戶興趣度的PageRank改進算法

黃賢英，陳紅陽

(重慶理工大學計算機科學與工程學院，重慶 400054)

傳統的PageRank算法容易導致主題漂移、偏重舊網頁、用戶對搜索結果的主觀選擇被忽略等問題。針對PageRank算法存在的上述缺陷，提出了一種基于用戶興趣度的網頁排序算法——PRUI算法。該算法主要從網頁自身的客觀特性和用戶興趣的主觀特性兩方面對網頁的PR值進行重新估算，并依據估算后的網頁PR值對網頁做重排序。相比傳統的PageRank算法，改進的PRUI算法進一步提高了系統檢索的準確率和首頁命中率。

搜索引擎;PageRank算法;主題漂移;用戶興趣度;頁面排序

目前，搜索引擎是人們獲取網絡信息的主要工具。面對互聯網信息爆炸式的增長和日益復雜的用戶信息需求［1］，基于關鍵字查詢的傳統網頁排序算法已經愈加顯露出自身的不足。如何快速、高效、準確地從信息海洋中找到符合用戶需求的信息資源是搜索引擎網頁排序算法亟待解決的問題［2］。

針對PageRank算法中存在的主題漂移問題，王春花等［3］提出了一種改進的非平均權值傳遞PageRank算法。該算法考慮了源網頁與其出鏈網頁之間的相關度，對網頁的權值采取非平均分配方式;缺點是未能考慮目標網頁與用戶查詢詞的主題相關度。王德廣等［4］考慮網頁的時間因素，認為網頁發布時間和被檢索時間之差與其PR值呈負相關，引入了時間函數，使內容較新穎且對用戶具有吸引力的新網頁PR值得到提高。郭慶寶等［5］提出了融合反饋信息和內容相關度的PageR－ank改進算法，考慮了用戶對搜索結果頁面的反饋信息，但僅將用戶對網頁的點擊量作為衡量指標，未對用戶的反饋行為進行深入分析以及探究用戶對網頁的興趣度。黃華東［6］提出了基于用戶模型的個性化搜索研究，引入了用戶興趣模型的概念，從而為網頁排序算法的改進提供了一種新的思路——構建完善的用戶興趣模型，并將其融入到搜索引擎的網頁排序中;算法的不足之處是用戶興趣模型的構建并不完善。

本文從網頁自身的客觀特性和用戶興趣的主觀特性兩個角度出發，提出了一種改進的網頁排序算法——PRUI算法(PageRank algorithm based on user interest degree)。首先針對PageRank算法存在的主題漂移、偏重舊網頁問題，引入了源網頁與目標網頁、用戶查詢詞之間的主題相關度，并結合網頁的駐留時間對PR值重新估算;其次從用戶的角度出發，構建用戶興趣模型，重新定義了用戶對頁面的興趣度。估算后的PR值和用戶興趣度兩部分加權得到頁面最終的PR值。

1 傳統PageRank算法

PageRank算法［7－8］基于萬維網超鏈接關系對網頁的質量進行評估，進而實現網頁排序。該算法采用隨機游走模型來模擬網絡用戶的瀏覽行為，估算每個頁面的被訪問概率。隨機游走模型假設用戶主要使用兩種方式訪問網頁:其一，用戶從給定的頁面集合中隨機挑選某頁面進行訪問;其二，用戶根據初始頁面中存在的超鏈接遞歸跟蹤訪問感興趣的頁面。因此，每個頁面的被訪問概率(簡稱網頁的PR值)可通過式(1)計算獲得。

式(1)中:PR(A)表示目標網頁A的PR值，用以表征網頁的重要程度;λ是介于0和1之間的衰減系數(一般取值為0.85左右);Ti表示鏈向目標網頁A的入鏈網頁(1≤i≤n);Count(Ti)表示網頁Ti的出鏈網頁總數。

2 改進的PRUI算法

PRUI算法主要從以下兩個方面著手對網頁PR值的計算公式進行改進:一是基于網頁內容和鏈接結構的客觀特性，解決PageRank算法存在的主題漂移、偏重舊網頁問題;二是基于用戶興趣度的主觀特性，通過分析用戶與系統交互過程中的瀏覽行為，構建完善的用戶興趣度;綜合考慮網頁自身的特性和用戶的主觀選擇行為，為用戶提供更為合理的檢索結果。

2.1 基于網頁內容和鏈接結構的客觀特性改進PageRank算法

1)主題漂移。將網頁權值平均分配給出鏈網頁忽略了網頁與其出鏈網頁及查詢詞間的相關度，以致某些網頁憑借較高的PR值在搜索結果中排在靠前的位置，卻與用戶查詢主題相關度甚小。以往改進的PageRank算法在解決主題漂移問題時，未能綜合考慮網頁內容與用戶查詢詞、其出鏈網頁之間的主題相關度對網頁PR值的影響［3］。實際上，這兩種主題相關度均與該網頁所獲得的PR值呈正相關。假設目標頁面為A，鏈向它的源網頁集合T={T1，T2，…，Tn}，用戶提交給系統的查詢詞為Q，將頁面A、用戶查詢詞Q及源網頁Ti(1≤i≤n)分別向量化后可表示為:A=(a1，a2，…，an)，Q=(q1，q2，…，qn)，Ti=(Ti1，Ti2，…，Tin)。采用余弦相似度度量頁面A與用戶查詢詞Q之間的相似度，如式(2)所示。

源網頁Ti和目標頁面A之間的相似度為

綜合式(2)、(3)改進PR值計算公式，如式(4)所示。

2)偏重舊網頁。新舊網頁被其他網頁鏈向的機會、所獲的權值及在結果頁面中所排位置正比于其在網絡上存在的時間，以致出現舊網頁上浮、新網頁下沉的現象，從而使用戶可能感興趣的新網頁排在搜索結果尾部。因此，為降低網頁在網絡上的時間對其PR值的影響，引入時間衰減因子(網頁存在時間與其PR值呈反比例關系)改進PR值計算公式，具體如式(5)所示。

2.2 基于用戶興趣度的主觀特性改進PageRank算法

融入用戶對搜索結果的主觀選擇能較為全面、準確地刻畫用戶對網頁的興趣度，從而更好地衡量網頁的質量，提高網頁的排序效果［9］。本算法主要通過以下幾個方面對用戶興趣度進行描述與衡量。

1)用戶搜索歷史記錄。囊括了用戶對網頁的各種瀏覽行為，在一定程度上反映了用戶的興趣偏好。通過分析用戶以往搜索的關鍵詞、統計各個關鍵詞被搜索的次數，可將用戶的歷史興趣［10］用向量表示為HInterest=(HIw1，HIw2，…，HIwn)，當前網頁A經過向量化后表示為A=(a1，a2，…，an)。因此，基于用戶歷史興趣衡量用戶對當前網頁的興趣度，如式(6)所示。

其中:ai為網頁A的第i個特征詞的權重;HIwi為用戶搜索第i個關鍵詞的次數。

2)用戶瀏覽網頁的時間。一般情況下，如果用戶對某一網頁內容感興趣，會點擊、瀏覽并在頁面中停留一定時間。在特定的時間范圍內，用戶的興趣濃度較高;超出此范圍，用戶的興趣度則大幅衰減［11］。通過觀察用戶瀏覽網頁的時間與其對網頁興趣度的關系，構建正態分布模型，并基于頁面瀏覽時間改進用戶興趣度，如式(7)所示。

其中:t為用戶瀏覽網頁的時間，服從正態分布N (T，(Δt/6)2);T為正常情況下用戶瀏覽一個頁面所需的平均時間;Δt為特定時間范圍，Δt= tmax－tmin。

3)同類用戶的協同過濾。協同過濾推薦［12］是指通過分析用戶興趣偏好，尋找與其具有類似興趣的用戶，然后根據同類用戶對某一信息的興趣度，推測該用戶對此信息也具有同樣的興趣度，并推薦符合用戶需求的信息。

基于上述思想，提出了一種同類用戶的協同過濾方法。當前用戶對某網頁的興趣度可用群體用戶的興趣度量，即借助同類用戶的興趣偏好過濾無關信息。同類用戶興趣用其歷史興趣向量表示為CInterest=(CIw1，CIw2，…，CIwn)，當前網頁A向量化為A=(a1，a2，…，an)，那么通過協同過濾后，用戶對當前網頁的興趣度如式(8)所示。

其中:ai為網頁A的第i個特征詞的權重;CIwi為用戶搜索第i個關鍵詞的次數。

2.3 利用改進的PRUI算法計算網頁的PR值

綜上所述，一個網頁的質量融合了網頁自身的客觀特性與用戶興趣度的主觀特性，網頁最終的PR值用式(9)表示。

其中:α與β為控制影響網頁重要性的客觀因素與主觀因素的權重參數。

3 實驗結果及分析

其中:F1為查準率;Ra為系統根據用戶查詢詞檢索出的相關文檔總數;R為系統檢索出的文檔總數;F2為首頁命中率;Sa為在首頁檢索結果中滿足用戶需求的相關文檔總數;S為首頁檢索結果中文檔的總數。

本文使用Java語言在Galago開源平臺上集成PRUI算法，并采用開源的Heritrix爬蟲框架將搜狐主頁作為爬取時的起始網頁，以增量式爬取方式對網頁進行動態抓取。網頁的抓取數量設定為50萬，同時隨機選取來自不同專業的20名學生作為測試人員，每位測試人員代表一種查詢請求。各種查詢請求如表1所示。

本文采用查準率和首頁命中率作為系統檢索性能的衡量指標。具體計算如式(10)所示。

表1 測試人員查詢請求表

為了確定式(9)中α與β的取值，分別針對α+β=1，且β＞α＞0的4種可能取值情況(精度為0.1，考慮到網頁的PR值計算受用戶興趣度的主觀影響因素較大，選取β＞α)測試其在PRUI算法下的查詢準確率。當α與β分別為0.4和0.6時，查詢準確率取得最大值0.75，最終確定α與β的取值分別為0.4和0.6。

根據表1中每個用戶的查詢請求進行檢索，選取前10頁結果頁面進行統計，其中每一頁包含10條記錄。比較每個查詢請求在改進的PRUI與傳統PageRank算法下的檢索效果(如圖1所示)。

圖1 傳統的PageRank算法與改進的PRUI算法準確率比較

觀察圖1中數據的變化趨勢可以發現:在PRUI算法下，用戶查詢的準確率有了進一步提高，說明融入用戶對網頁的興趣度有效改善了網頁的排序效果，可為用戶提供更好的檢索體驗以滿足用戶個性化的檢索請求。

系統采用2種算法針對20種不同的查詢請求返回對應的相關結果集，從中選取首頁10條記錄，統計首頁命中率，對比結果如圖2所示。

圖22 種不同算法下的首頁命中率

觀察圖2中的數據可知:在2種不同算法下，針對不同的用戶查詢請求，其首頁命中率有著明顯的差異。采用PRUI算法，首頁命中率相對有所提高，穩定在0.68附近。這間接表明滿足用戶需求的網頁在搜索結果中排在了相對靠前的位置。

本文引入頁面與查詢詞及出鏈網頁的相關度、網頁存在的時間因素，解決了主題漂移和偏重舊網頁的問題。用戶對檢索結果的滿意度某種程度上還取決于其主觀選擇行為，因此本文提出的算法融入用戶興趣度，考慮了用戶的主觀感受。最后，結合兩者有效改善了網頁的排序效果，使得滿足用戶需求的網頁盡量排在靠前的位置。

4 結束語

本文主要針對傳統PageRank算法存在的主題漂移、偏重舊網頁以及用戶對搜索結果的主觀選擇被忽略問題，提出了一種改進的PRUI算法。該算法從網頁內容和鏈接結構角度出發解決主題漂移、偏重舊網頁問題;引入用戶興趣度以解決用戶對搜索結果的主觀選擇被忽略問題，最后綜合二者對網頁的PR值進行重新估算。實驗結果表明:PRUI算法提高了系統檢索的準確率、改善了用戶的檢索體驗。

算法存在的不足包括:基于向量空間模型表示網頁文本與用戶查詢詞，采用余弦相似度衡量二者之間的相似度時，未挖掘出文本內容蘊含的深層含義，相似性的準確度量需進一步改善;在本算法實施過程中，需要搜集、存儲及處理與用戶興趣度相關的數據，這在一定程度上增加了算法的時間復雜度。在今后的研究工作中，需不斷優化算法，提高搜索匹配的范圍與準確度，從而將最符合用戶需求的頁面排在搜索結果的最前端。例如，可對語義相似度模型［13］進行深入研究，以精確衡量網頁文本與查詢詞間的相似度。

［1］Luiz C M，Miranda，Carlos A S，et al.Trends and cycles of the internet evolution and worldwide impacts［J］.Technological Forecasting and Social Change，2012，79 (4):744－765.

［2］Rashid Ali，Sufyan Beg M M.An overview of Web search evaluation methods［J］.Computers and Electrical Engineering，2011:835－848.

［3］王春花，朱俊平.改進的非平均傳遞權值PageRank算法［J］.計算機工程與設計，2010，31(10):216－217.

［4］王德廣，周志剛，梁旭.PageRank算法的分析及其改進［J］.計算機工程，2010(11):291－293.

［5］郭慶寶，賈代平.融合反饋信息與內容相關度的PageRank改進算法［J］.計算機工程與設計，2011，32 (12):4072－4074.

［6］黃華東.基于用戶模型的個性化搜索研究［D］.上海:華東理工大學，2013.

［7］賀志明，王麗宏，張剛，等.一種抵抗鏈接作弊的PageRank改進算法［J］.中文信息學報，2012，26(5):102－106.

［8］謝月.網頁排序中PageRank算法和HITS算法的研究［D］.成都:電子科技大學，2012.

［9］Ling ZHENG，Shuo CUI，Dong YUE，et al.User Interest ModelingBased on Browsing Behavior［C］//2010 3rd International Conference on Ad－vanced Computer Theory and Engineering(ICACTE).Chengdu:［s.n.］，2010:455－458.

［10］王宇.基于搜索歷史的用戶興趣建模［D］.上海:復旦大學，2011.

［11］南智敏.基于網頁興趣度的用戶興趣模型體系研究［D］.上海:復旦大學，2012.

［12］吳月萍，鄭建國.協同過濾推薦算法［J］.計算機工程與設計，2011，32(9):3019－3021.

［13］朱征宇，孫俊華.改進的基于《知網》的詞匯語義相似度計算［J］.計算機應用，2013，39(8):2276－2279.

(責任編輯 楊黎麗)

Improved PageRank Algorithm Based on User Interest Degree

HUANG Xian－ying，CHEN Hong－yang
(School of Computer Science and Engineering，
Chongqing University of Technology，Chongqing 400054，China)

Traditional PageRank algorithm had such drawbacks as theme drifting，history pages being emphasized and the user＇s interests in results being ignored.Facing the above defects described，an improved ranking algorithm called PRUI was proposed，which was based on user interest degree.It mainly re－estimated PR value of web page integrating objective characteristics of web page with subjective characteristics of user＇s interests，and ranked the web page according to the calculated PR value again.The experimental results show that PRUI algorithm has acquired higher retrieval accuracy as well as first page hit ratio，compared with traditional PageRank algorithm.

search engine;PageRank algorithm;user interest degree;page ranking

TP391.03

A

1674－8425(2014)05－0074－05

10.3969/j.issn.1674－8425(z).2014.05.015

2013－12－19

國家自然科學基金項目(61173184);重慶市教委科技計劃項目(KJ100821);重慶理工大學研究生創新基金項目(YCX2012317)

黃賢英(1967—)，女，重慶人，教授，碩士生導師，主要從事嵌入式技術、移動技術研究;陳紅陽(1989—)，女，河南南陽人，碩士研究生，主要從事信息檢索研究。

黃賢英，陳紅陽.基于用戶興趣度的PageRank改進算法［J］.重慶理工大學學報:自然科學版，2014(5):74－78.

format:HUANG Xian－ying，CHEN Hong－yang.Improved PageRank Algorithm Based on User Interest Degree［J］.Journal of Chongqing University of Technology:Natural Science，2014(5):74－78.