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

黃賢英，陳紅陽

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

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

黃賢英，陳紅陽

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

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

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

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

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

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

1 傳統(tǒng)PageRank算法

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

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

2 改進的PRUI算法

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

2.1 基于網(wǎng)頁內(nèi)容和鏈接結(jié)構(gòu)的客觀特性改進PageRank算法

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

源網(wǎng)頁Ti和目標頁面A之間的相似度為

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

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

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

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

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

其中:ai為網(wǎng)頁A的第i個特征詞的權(quán)重;HIwi為用戶搜索第i個關(guān)鍵詞的次數(shù)。

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

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

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

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

其中:ai為網(wǎng)頁A的第i個特征詞的權(quán)重;CIwi為用戶搜索第i個關(guān)鍵詞的次數(shù)。

2.3 利用改進的PRUI算法計算網(wǎng)頁的PR值

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

其中:α與β為控制影響網(wǎng)頁重要性的客觀因素與主觀因素的權(quán)重參數(shù)。

3 實驗結(jié)果及分析

其中:F1為查準率;Ra為系統(tǒng)根據(jù)用戶查詢詞檢索出的相關(guān)文檔總數(shù);R為系統(tǒng)檢索出的文檔總數(shù);F2為首頁命中率;Sa為在首頁檢索結(jié)果中滿足用戶需求的相關(guān)文檔總數(shù);S為首頁檢索結(jié)果中文檔的總數(shù)。

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

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

表1 測試人員查詢請求表

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

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

圖1 傳統(tǒng)的PageRank算法與改進的PRUI算法準確率比較

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

系統(tǒng)采用2種算法針對20種不同的查詢請求返回對應(yīng)的相關(guān)結(jié)果集，從中選取首頁10條記錄，統(tǒng)計首頁命中率，對比結(jié)果如圖2所示。

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

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

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

4 結(jié)束語

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

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

［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］王春花，朱俊平.改進的非平均傳遞權(quán)值PageRank算法［J］.計算機工程與設(shè)計，2010，31(10):216－217.

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

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

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

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

［8］謝月.網(wǎng)頁排序中PageRank算法和HITS算法的研究［D］.成都:電子科技大學(xué)，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］.上海:復(fù)旦大學(xué)，2011.

［11］南智敏.基于網(wǎng)頁興趣度的用戶興趣模型體系研究［D］.上海:復(fù)旦大學(xué)，2012.

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

［13］朱征宇，孫俊華.改進的基于《知網(wǎng)》的詞匯語義相似度計算［J］.計算機應(yīng)用，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

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

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

黃賢英，陳紅陽.基于用戶興趣度的PageRank改進算法［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，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.