基于Hadoop的PageRank算法的研究與改進(jìn)

閔 攀，徐 虹

(成都信息工程大學(xué)計(jì)算機(jī)學(xué)院，四川成都610225)

0 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，網(wǎng)絡(luò)數(shù)據(jù)呈指數(shù)增長(zhǎng)，如何通過(guò)搜索引擎從海量數(shù)據(jù)中快速、方便、高效地檢索到符合需求的信息已經(jīng)迫在眉睫。搜索引擎技術(shù)中網(wǎng)頁(yè)排序算法成為了關(guān)鍵部分。PageRank算法是由Google創(chuàng)始人Brin和Page等于1998提出的，算法根據(jù)網(wǎng)頁(yè)鏈接結(jié)構(gòu)分析和計(jì)算網(wǎng)頁(yè)的重要程度，應(yīng)用于Google搜索領(lǐng)域，并受到廣大用戶的青睞。然而，傳統(tǒng)PageRank算法在應(yīng)用過(guò)程中主題漂移，偏向舊網(wǎng)頁(yè)和忽略用戶興趣的缺陷逐漸暴露，文中引入主題相關(guān)因子，有效點(diǎn)擊頻率和時(shí)間反饋因子對(duì)算法進(jìn)行改進(jìn)。然后，將改進(jìn)算法用 MapReduce[1]實(shí)現(xiàn)，并部署在由Apache開(kāi)源 Hadoop[2]搭建的集群上，使用 HBase 列式數(shù)據(jù)庫(kù)實(shí)現(xiàn)實(shí)時(shí)數(shù)據(jù)存儲(chǔ)和檢索，用戶在檢索效率和查準(zhǔn)率上相對(duì)傳統(tǒng)算法有明顯的提高。

1 PageRank算法分析與改進(jìn)

1.1 算法簡(jiǎn)介

PageRank算法[3－4]是根據(jù)網(wǎng)頁(yè)鏈接結(jié)構(gòu)分配網(wǎng)頁(yè)分值，經(jīng)過(guò)多次迭代收斂后，通過(guò)網(wǎng)頁(yè)分值進(jìn)行檢索排序。一個(gè)網(wǎng)頁(yè)獲得的分值越大，排序就越靠前。網(wǎng)頁(yè)獲得的分值的和鏈入網(wǎng)頁(yè)的數(shù)量、鏈入網(wǎng)頁(yè)本身?yè)碛械姆种岛统鲦湐?shù)有關(guān)，因?yàn)镻ageRank算法每個(gè)鏈接分配的分值是平均分配的，所以鏈入網(wǎng)頁(yè)數(shù)目越多、分值越大、出鏈數(shù)越少，網(wǎng)頁(yè)獲得的分值就越多。傳統(tǒng)的PageRank算法公式為

其中:阻尼因子μ設(shè)為0.85;B(y)是所有鏈入網(wǎng)頁(yè)x的網(wǎng)頁(yè)集合，Out(y)是網(wǎng)頁(yè)y的所有鏈出網(wǎng)頁(yè)總數(shù)，由此可知，PageRank算法中，網(wǎng)頁(yè)y的PR值是平均分配給y的鏈出網(wǎng)頁(yè)，而網(wǎng)頁(yè)x的PR值是所有鏈入鏈接的PR值之和。

1.2 算法相關(guān)分析

PageRank算法在Google搜索引擎中是一個(gè)成功應(yīng)用的范例，運(yùn)行高效穩(wěn)定。該算法是基于網(wǎng)頁(yè)鏈接結(jié)構(gòu)而沒(méi)有考慮權(quán)重問(wèn)題。網(wǎng)頁(yè)P(yáng)R值是平均分配給鏈出網(wǎng)頁(yè)，且忽略了新舊網(wǎng)頁(yè)的偏向性，網(wǎng)頁(yè)鏈接與主題內(nèi)容關(guān)聯(lián)性和用戶對(duì)網(wǎng)頁(yè)的興趣程度。因此算法的缺陷具體可以歸納為:

(1)主題漂移。PageRank算法并沒(méi)有考慮到查詢到的網(wǎng)頁(yè)內(nèi)容和用戶搜索主題關(guān)聯(lián)程度，這樣導(dǎo)致搜索到的網(wǎng)頁(yè)雖然具有很高的權(quán)重值，但是網(wǎng)頁(yè)內(nèi)容并不符合用戶的檢索需要，這種檢索主題和檢索到網(wǎng)頁(yè)內(nèi)容關(guān)聯(lián)度小的現(xiàn)象(主題漂移)經(jīng)常發(fā)生。

(2)偏向舊網(wǎng)頁(yè)。PageRank在設(shè)計(jì)的時(shí)候沒(méi)有考慮網(wǎng)頁(yè)鏈接和網(wǎng)頁(yè)存在的時(shí)間的關(guān)系，因?yàn)榕f網(wǎng)頁(yè)在互聯(lián)網(wǎng)上存在的時(shí)間長(zhǎng)，獲得其他網(wǎng)頁(yè)正向鏈接的機(jī)會(huì)和數(shù)量遠(yuǎn)大于新發(fā)布的網(wǎng)頁(yè)，新網(wǎng)頁(yè)往往沒(méi)有被引用導(dǎo)致在檢索中并沒(méi)有被檢索到或者排名比較靠后，通常這些新發(fā)布的網(wǎng)頁(yè)才是用戶所需要的。

(3)忽略用戶興趣。在網(wǎng)頁(yè)檢索的過(guò)程中，如果只是考慮網(wǎng)頁(yè)的鏈接結(jié)構(gòu)而忽略用戶對(duì)網(wǎng)頁(yè)的興趣，那么在檢索的過(guò)程中，用戶感興趣的網(wǎng)頁(yè)無(wú)法檢索出來(lái)，從而無(wú)法滿足用戶需求。這也是傳統(tǒng)PageRank算法的一個(gè)設(shè)計(jì)不合理之處。

Xing等的研究表明，在PageRank算法中加入網(wǎng)頁(yè)鏈入鏈出權(quán)重因子對(duì)檢索排序結(jié)果起到優(yōu)化作用[5－7]，由于 PageRank算法存在的主題漂移問(wèn)題，文獻(xiàn)[8]在算法的基礎(chǔ)上提出基于主題敏感的PageRank算法，該算法對(duì)用戶查詢的關(guān)鍵字與已知主題相似度分析計(jì)算。文獻(xiàn)[9]在Weighted PageRank算法中添加主題特征相關(guān)因子和時(shí)間反饋因子，這2個(gè)算法在主題漂移的問(wèn)題上有一定的改善，但是忽略了用戶興趣。文獻(xiàn)[10]添加網(wǎng)頁(yè)內(nèi)容和時(shí)間反饋因子，對(duì)新舊網(wǎng)頁(yè)排序位置做出調(diào)整，使舊網(wǎng)頁(yè)下沉和新網(wǎng)頁(yè)上浮，側(cè)面解決了算法偏向舊網(wǎng)頁(yè)的問(wèn)題。文獻(xiàn)[11－13]通過(guò)用戶興趣和用戶點(diǎn)擊行為正向相關(guān)，從而反映用戶興趣度，但仍然有不合理之處。因?yàn)楹芏嗑W(wǎng)頁(yè)是屬于垃圾，虛假網(wǎng)頁(yè)，通過(guò)添加了很多與自身網(wǎng)站內(nèi)容不相符的搜索關(guān)鍵字來(lái)增加用戶點(diǎn)擊量，這樣無(wú)疑增加了網(wǎng)頁(yè)在搜索中的PR值，欺騙搜索引擎，提升自身在搜索結(jié)果中的排名。在計(jì)算用戶有效點(diǎn)擊數(shù)上沒(méi)有進(jìn)行有效，合理地過(guò)濾，而且只通過(guò)網(wǎng)頁(yè)點(diǎn)擊量來(lái)判斷用戶興趣度也是有一定片面性。

1.3 算法改進(jìn)

傳統(tǒng)PageRank算法是基于網(wǎng)頁(yè)鏈接結(jié)構(gòu)提出的，所以存在一些缺陷，通過(guò)網(wǎng)頁(yè)鏈接結(jié)構(gòu)，主題相關(guān)度，時(shí)間相關(guān)因子，用戶有效點(diǎn)擊頻率，對(duì)算法進(jìn)行改進(jìn)。網(wǎng)頁(yè)鏈接結(jié)構(gòu)可以分為站內(nèi)鏈接和站外鏈接兩種，為了防止欺騙和作弊行為的發(fā)生，對(duì)沒(méi)有明確主題和站內(nèi)鏈接網(wǎng)頁(yè)權(quán)值分配相對(duì)站外較低。對(duì)網(wǎng)頁(yè)主題內(nèi)容和鏈接網(wǎng)頁(yè)主題相關(guān)性，用向量模型分析計(jì)算，在分配權(quán)值時(shí)，分配較大權(quán)值。在對(duì)用戶反饋和時(shí)間反饋因子上，通過(guò)點(diǎn)擊權(quán)重和點(diǎn)擊時(shí)間權(quán)重結(jié)合來(lái)判定一次點(diǎn)擊的有效性。改進(jìn)PageRank算法公式為

其中:α是鏈入因子所占比重，β鏈出因子所占比重，1－α－β鏈接點(diǎn)擊權(quán)重因和時(shí)間反饋因子之商所占比重，η是主題相關(guān)度所占比重。和是根據(jù)網(wǎng)頁(yè)鏈接結(jié)構(gòu)的權(quán)重因子。

F(y)是y正向鏈接網(wǎng)頁(yè)集合集合;是網(wǎng)頁(yè)x的入度和y鏈向其他集合網(wǎng)頁(yè)的入度累加和之商所得入度因子，同理，是網(wǎng)頁(yè)x的出度和y鏈向其他集合網(wǎng)頁(yè)的出度累加和之商所得的出度因子。

1.3.1 主題內(nèi)容相關(guān)

網(wǎng)頁(yè)的主題內(nèi)容Content(x)是網(wǎng)頁(yè)x的內(nèi)容和用戶檢索的主題相關(guān)因子，即score(q，x)。通過(guò)網(wǎng)頁(yè)內(nèi)容和查詢關(guān)鍵字相關(guān)度的打分策略獲得，有效解決主題漂移問(wèn)題。其中打分公式[14－15]為

其中:w，q分別是詞語(yǔ)和當(dāng)前查詢語(yǔ)句;coord(q，x)是網(wǎng)頁(yè)x中包含的查詢?cè)~語(yǔ)的個(gè)數(shù);queryNorm(q)是各詞語(yǔ)權(quán)重平方和;idf(w)是詞語(yǔ)在倒排文檔中出現(xiàn)頻次;w.getBoost()是詞語(yǔ)w所占查詢語(yǔ)句權(quán)重，tf(w in x)是w在x中出現(xiàn)頻次，norm(w，x)是長(zhǎng)度因子，其值為詞語(yǔ)總數(shù)平方根的倒數(shù)。通過(guò)分析查詢語(yǔ)句與查詢到的網(wǎng)頁(yè)中各詞相關(guān)度分值進(jìn)行統(tǒng)計(jì)打分，分值越高說(shuō)明相關(guān)度越大。η是主題相關(guān)因子，為了避免網(wǎng)頁(yè)作弊，通過(guò)增加熱門關(guān)鍵字來(lái)欺騙搜索引擎，η值不宜太大。

1.3.2 有效用戶點(diǎn)擊率

網(wǎng)頁(yè)點(diǎn)擊量能客觀反映網(wǎng)頁(yè)內(nèi)容和用戶搜索需求的匹配度，一般情況下，索引結(jié)果頁(yè)面點(diǎn)擊次數(shù)越多，越符合用戶的索引需求，網(wǎng)頁(yè)重要程度越高。一項(xiàng)研究表明，一個(gè)好的搜索引擎，30%的高點(diǎn)擊率頁(yè)面能符合70%～80%用戶需求。然而一個(gè)新的頁(yè)面加入時(shí)，是沒(méi)有用戶點(diǎn)擊數(shù)，需要給予新頁(yè)面一些補(bǔ)償避免PageRank算法偏向于老的頁(yè)面，點(diǎn)擊權(quán)重S(y)設(shè)置如下點(diǎn)擊權(quán)重因子公式如下

N表示頁(yè)y在某段時(shí)間的點(diǎn)擊數(shù)，λ是衰減系數(shù)，控制點(diǎn)擊數(shù)權(quán)重，通常設(shè)置為0.3，λ0是補(bǔ)償系數(shù)，反映了一個(gè)新頁(yè)面的重要性，通常設(shè)置為1，PR(y)與S(y)成正比。

在計(jì)算用戶對(duì)各鏈接點(diǎn)擊量N時(shí)，通過(guò)用戶瀏覽網(wǎng)頁(yè)時(shí)間判定用戶點(diǎn)擊的有效性，從而對(duì)點(diǎn)擊行為進(jìn)行過(guò)濾，如果用戶通過(guò)點(diǎn)擊鏈接進(jìn)入鏈接頁(yè)面后在鏈接頁(yè)面停留的時(shí)間τ，如果超過(guò)正常人停留頁(yè)面時(shí)間，那么本次點(diǎn)擊鏈接可計(jì)入點(diǎn)擊量中，否則，認(rèn)為用戶對(duì)該鏈接頁(yè)面是不感興趣的，不計(jì)入點(diǎn)擊量中，正常人瀏覽頁(yè)面時(shí)間t為

Tw、Tp、Tv分別是網(wǎng)頁(yè)文字個(gè)數(shù)，一個(gè)圖片相對(duì)漢字?jǐn)?shù)，一個(gè)視頻相對(duì)文字?jǐn)?shù);正常人閱讀速度為280字/分。

1.3.3 時(shí)間反饋因子

僅僅考慮點(diǎn)擊次數(shù)是不能避免偏向舊頁(yè)面的問(wèn)題，因?yàn)榕f的頁(yè)面存在的時(shí)間比較長(zhǎng)，積累的點(diǎn)擊數(shù)比較多，而新頁(yè)面存在時(shí)間比較短，點(diǎn)擊數(shù)比較少，因此有必要引入點(diǎn)擊時(shí)間權(quán)重因子，可以通過(guò)最近一段時(shí)間的點(diǎn)擊判斷網(wǎng)頁(yè)的活躍程度，單位時(shí)間內(nèi)點(diǎn)擊一個(gè)頁(yè)面說(shuō)明是正常的，如果在單位時(shí)間內(nèi)沒(méi)有點(diǎn)擊該頁(yè)面，該頁(yè)面的重要性降低。那么可以根據(jù)最近一段時(shí)間頁(yè)面如果沒(méi)有被點(diǎn)擊，就降低PageRank值，可以認(rèn)為一個(gè)新的網(wǎng)頁(yè)的內(nèi)容與重要性相關(guān)，如果頁(yè)面持續(xù)更新則可以提高重要性，設(shè)定一個(gè)月內(nèi)點(diǎn)擊屬于正常，計(jì)算用戶實(shí)時(shí)搜索時(shí)間和最后點(diǎn)擊結(jié)果頁(yè)的差異。如果結(jié)果頁(yè)的點(diǎn)擊率為0，替換最后單擊時(shí)間為生成或更新結(jié)果的時(shí)間頁(yè)面。時(shí)間間隔是一個(gè)月。點(diǎn)擊時(shí)間權(quán)重公式為

T為頁(yè)面y不同時(shí)間搜索頁(yè)面的間隔時(shí)間，Tnow是頁(yè)面y最近一次點(diǎn)擊頁(yè)面，Tlast和Tupdate表示頁(yè)面y的修改時(shí)間，ω是時(shí)間間隔衰減系數(shù)，通常設(shè)置為1/12，PR(y)與T(y)成反比。

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境

2.1.1 硬件環(huán)境

3臺(tái)PC機(jī)，PC機(jī)硬件配置:Master節(jié)點(diǎn)，主頻3.0 GHZ，內(nèi)存2 G，硬盤250 G，IP:192.168.80.100;slave1節(jié)點(diǎn)，主頻3.0 GHZ，內(nèi)存2 G，硬盤 160G，IP:192.168.80.110;slave2 節(jié)點(diǎn)，主頻3.0 GHZ，內(nèi)存2 G，硬盤160 G，IP:192.168.80.120。

2.1.2 軟件環(huán)境

Java version:1.7.0_09－icedtea

Hadoop version:Hadoop 2.2.0

集群節(jié)點(diǎn)信息如表1所示。

表1 集群節(jié)點(diǎn)信息

2.2 集群配置

Hadoop集群配置信息和啟動(dòng)步驟如下:

(1)通過(guò)/etc/sysconfig/network文件修改主機(jī)名;

(2)修改IP地址;

(3)通過(guò)/etc/hosts修改所有主機(jī)名和IP的映射關(guān)系;

(4)關(guān)閉防火墻;

(5)安裝JDK并將環(huán)境變量添加在/etc/profile文件中;

(6)安裝Hadoop并將環(huán)境變量配置在/etc/profile文件中，使用source/etc/profile使配置生效;

(7)配置3個(gè)節(jié)點(diǎn)間免密碼登錄;

(8)修改Hadoop配置文件。添加Java環(huán)境變量，配置由Yarn管理資源管理器和節(jié)點(diǎn)管理器，修改集群節(jié)點(diǎn)副本數(shù)和其他參數(shù)，然后將配置好的JDK、Hadoop文件復(fù)制到其他節(jié)點(diǎn)。最后，格式化文件系統(tǒng)。

(9)啟動(dòng)HDFS文件系統(tǒng)和Yarn資源管理器。

2.3 實(shí)驗(yàn)配置

實(shí)驗(yàn)將Nutch-1.7版本部署在集群環(huán)境中，收集“體育網(wǎng)站”相關(guān)網(wǎng)頁(yè)18個(gè)，與體育無(wú)關(guān)網(wǎng)頁(yè)15個(gè)，作為實(shí)驗(yàn)測(cè)試網(wǎng)頁(yè)。通過(guò)體育運(yùn)動(dòng)項(xiàng)目“籃球”、“足球”、“羽毛球”、“乒乓球”和“游泳”作為關(guān)鍵字進(jìn)行查詢，分別在單節(jié)點(diǎn)，雙節(jié)點(diǎn)，3節(jié)點(diǎn)上，對(duì)爬取速率、檢索速率，查準(zhǔn)率的變化進(jìn)行對(duì)比分析。其中，查準(zhǔn)率為用戶檢索到符合主題的頁(yè)面數(shù)與返回頁(yè)面總數(shù)之比。

通過(guò)java語(yǔ)言實(shí)現(xiàn)傳統(tǒng)的PageRank算法和改進(jìn)后的PageRank算法對(duì)應(yīng)的MapReduce程序，實(shí)驗(yàn)參數(shù)設(shè)置分為4組，并對(duì)查準(zhǔn)率進(jìn)行對(duì)比分析，如表2所示。分別將4組參數(shù)設(shè)置的算法打成jar包作為集群環(huán)境UDF功能函數(shù)，在用戶檢索的結(jié)果集中調(diào)用PageRank函數(shù)計(jì)算各頁(yè)面的PR值，對(duì)結(jié)果集進(jìn)行按PR值進(jìn)行排序顯示。

表2 影響因子對(duì)應(yīng)查準(zhǔn)率表

2.4 結(jié)果分析

實(shí)驗(yàn)結(jié)果如圖1、圖2和圖3所示。

圖1 不同節(jié)點(diǎn)爬取索引時(shí)間

圖1、圖2分別是不同節(jié)點(diǎn)上網(wǎng)頁(yè)爬取時(shí)間和不同關(guān)鍵字檢索時(shí)間對(duì)比，在單節(jié)點(diǎn)，和雙節(jié)點(diǎn)進(jìn)行頁(yè)面爬取索引時(shí)，時(shí)間相差不大，因?yàn)閱喂?jié)點(diǎn)上節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)和管理都是在本機(jī)上完成，而雙節(jié)點(diǎn)是一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)，而另一節(jié)點(diǎn)作為從節(jié)點(diǎn)，集群的優(yōu)勢(shì)都還沒(méi)發(fā)揮出來(lái)，但是3節(jié)點(diǎn)的爬取和索引效率提高7.209%，檢索速率提高10.12%，說(shuō)明集群中隨著節(jié)點(diǎn)數(shù)的增加，爬取索引和索檢索時(shí)間明顯減少，效率有明顯提高。

圖2 不同關(guān)鍵字檢索時(shí)間

在圖3中，在算法中添加了主題相關(guān)度，有效用戶點(diǎn)擊頻率和時(shí)間反饋因子改進(jìn)PageRank算法。經(jīng)不同關(guān)鍵字進(jìn)行檢索測(cè)試，改進(jìn)后的PageRank算法相對(duì)于沒(méi)有改進(jìn)的算法在查準(zhǔn)率提高21.4%，更能滿足用戶的檢索需求。

圖3 不同關(guān)鍵字查準(zhǔn)率

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

文中算法是在傳統(tǒng)PageRank算法的基礎(chǔ)上同時(shí)加入鏈接結(jié)構(gòu)權(quán)重，主題相關(guān)度，有效用戶點(diǎn)擊率，時(shí)間反饋因子對(duì)算法進(jìn)行改進(jìn)，利用Hadoop的HDFS、MapReduce和Hbase列式數(shù)據(jù)庫(kù)實(shí)現(xiàn)實(shí)時(shí)存儲(chǔ)和檢索網(wǎng)頁(yè)數(shù)據(jù)，提高搜索引擎排序效率，通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析表明，改進(jìn)后的PageRank算法在Nutch上的爬取索引效率提高7.209%，用戶在網(wǎng)頁(yè)檢索效率上提高10.12%，查準(zhǔn)率提高21.4%，并且隨著集群節(jié)點(diǎn)數(shù)和數(shù)據(jù)量的增加，搜索引擎的檢索效率逐漸增強(qiáng)。

[1] Jeff dean.Sanjay ghemawat.MapReduce:Simplified data processing on large clusters[J].Communications of the ACM，2008，51(1):107－113.

[2] White Tom.Hadoop:The Definitive Guide[M].O’Reilly Media，Inc，2009.

[3] Sergey brin.Theanatomy of a large scale hyper textual Web search engine[J].Computer Networks and ISDN Systems，1998，33:107－117.

[4] Broder A Z，Najork M，Wiener J L，Efficient URL caching for world wide web crawling[C]//Proceedings of the 12th International Conference on World Wide Web.Budapest，Hungary:[s.n]，2003:679－689.

[5] Xing w，Ghorbani a.Weighted PageRank algorithm[C]//Proceedings of 2nd Annual Conferrence.Piscataway:IEEE，2004:305－314.

[6] Manning C D，Raghavan P.Schutze H.信息檢索導(dǎo)論[M].王斌，譯.北京:人民郵電出版社，2010:218－225.

[7] Tyagi N，Sharma S.Comparative study of various page ranking algorithms in Web Structure Ming(WSM)[J].International Journal of Innovative Technology and Exploring Engineering，2012，1(1):14－19.

[8] Haveliwala T H.Topic－sensitive PageRank[R/OL].[2014－06－14].http://www2002.org/CDROM/refered/127/.

[9] Duan H，HU P.Improved PageRank algorithm based on topic character and time factor[J].Computer Engineering and Design，2010，31(4):866－868.

[10] LI Z.Research on the PageRank algorithm of PageRank based on Web content and time feedback[D].Chongqing:Chongqing University of Technology，2012.

[11] Tyagi N，Sharma S.Weighted PageRank algorithm based on number of visits of links of Web page[J].International Journal of Soft Computing and Engineering，2012，2(3):441－446.

[12] Kumar G，Duhan N，Sharma A K.Page ranking based on number of visits of links of Web page[C]//Proceedings of the 2nd International Conference on Computer and Communication Technology.Piscataway:IEEE，2011 11－14.

[13] Zhou C L，Chen K，Li S S.Improved PageRank Algorithm Based on Feedback of User Clicks[J].IEEE，2011，918－1－4244－9763－8.

[14] Mccandless M，Hatcher E，Gospodnetic O，Lucene實(shí)戰(zhàn)[M].牛長(zhǎng)流，肖宇，譯.北京:北京郵電出版社，2011:81－93.

[15] 邱哲，符滔滔.開(kāi)發(fā)自己的搜索引擎:Lucene 2.0+Heritrix[M].北京:人民郵電出版社，2007.