黃賢英，陳紅陽(yáng)

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

基于用戶興趣度的PageRank改進(jìn)算法

黃賢英，陳紅陽(yáng)

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

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

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

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

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

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

1 傳統(tǒng)PageRank算法

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

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

2 改進(jìn)的PRUI算法

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

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

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

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

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

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

2.2 基于用戶興趣度的主觀特性改進(jìn)PageRank算法

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

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

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

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

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

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

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

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

2.3 利用改進(jìn)的PRUI算法計(jì)算網(wǎng)頁(yè)的PR值

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

表1 測(cè)試人員查詢請(qǐng)求表

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

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

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

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

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

圖22 種不同算法下的首頁(yè)命中率

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

［8］謝月.網(wǎng)頁(yè)排序中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)頁(yè)興趣度的用戶興趣模型體系研究［D］.上海:復(fù)旦大學(xué)，2012.

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

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

(責(zé)任編輯 楊黎麗)

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

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

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

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