基于Hadoop的PageRank算法的研究與改進

閔 攀，徐 虹

(成都信息工程大學計算機學院，四川成都610225)

0 引言

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

1 PageRank算法分析與改進

1.1 算法簡介

PageRank算法[3－4]是根據網頁鏈接結構分配網頁分值，經過多次迭代收斂后，通過網頁分值進行檢索排序。一個網頁獲得的分值越大，排序就越靠前。網頁獲得的分值的和鏈入網頁的數量、鏈入網頁本身擁有的分值和出鏈數有關，因為PageRank算法每個鏈接分配的分值是平均分配的，所以鏈入網頁數目越多、分值越大、出鏈數越少，網頁獲得的分值就越多。傳統的PageRank算法公式為

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

1.2 算法相關分析

PageRank算法在Google搜索引擎中是一個成功應用的范例，運行高效穩定。該算法是基于網頁鏈接結構而沒有考慮權重問題。網頁PR值是平均分配給鏈出網頁，且忽略了新舊網頁的偏向性，網頁鏈接與主題內容關聯性和用戶對網頁的興趣程度。因此算法的缺陷具體可以歸納為:

(1)主題漂移。PageRank算法并沒有考慮到查詢到的網頁內容和用戶搜索主題關聯程度，這樣導致搜索到的網頁雖然具有很高的權重值，但是網頁內容并不符合用戶的檢索需要，這種檢索主題和檢索到網頁內容關聯度小的現象(主題漂移)經常發生。

(2)偏向舊網頁。PageRank在設計的時候沒有考慮網頁鏈接和網頁存在的時間的關系，因為舊網頁在互聯網上存在的時間長，獲得其他網頁正向鏈接的機會和數量遠大于新發布的網頁，新網頁往往沒有被引用導致在檢索中并沒有被檢索到或者排名比較靠后，通常這些新發布的網頁才是用戶所需要的。

(3)忽略用戶興趣。在網頁檢索的過程中，如果只是考慮網頁的鏈接結構而忽略用戶對網頁的興趣，那么在檢索的過程中，用戶感興趣的網頁無法檢索出來，從而無法滿足用戶需求。這也是傳統PageRank算法的一個設計不合理之處。

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

1.3 算法改進

傳統PageRank算法是基于網頁鏈接結構提出的，所以存在一些缺陷，通過網頁鏈接結構，主題相關度，時間相關因子，用戶有效點擊頻率，對算法進行改進。網頁鏈接結構可以分為站內鏈接和站外鏈接兩種，為了防止欺騙和作弊行為的發生，對沒有明確主題和站內鏈接網頁權值分配相對站外較低。對網頁主題內容和鏈接網頁主題相關性，用向量模型分析計算，在分配權值時，分配較大權值。在對用戶反饋和時間反饋因子上，通過點擊權重和點擊時間權重結合來判定一次點擊的有效性。改進PageRank算法公式為

其中:α是鏈入因子所占比重，β鏈出因子所占比重，1－α－β鏈接點擊權重因和時間反饋因子之商所占比重，η是主題相關度所占比重。和是根據網頁鏈接結構的權重因子。

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

1.3.1 主題內容相關

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

其中:w，q分別是詞語和當前查詢語句;coord(q，x)是網頁x中包含的查詢詞語的個數;queryNorm(q)是各詞語權重平方和;idf(w)是詞語在倒排文檔中出現頻次;w.getBoost()是詞語w所占查詢語句權重，tf(w in x)是w在x中出現頻次，norm(w，x)是長度因子，其值為詞語總數平方根的倒數。通過分析查詢語句與查詢到的網頁中各詞相關度分值進行統計打分，分值越高說明相關度越大。η是主題相關因子，為了避免網頁作弊，通過增加熱門關鍵字來欺騙搜索引擎，η值不宜太大。

1.3.2 有效用戶點擊率

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

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

在計算用戶對各鏈接點擊量N時，通過用戶瀏覽網頁時間判定用戶點擊的有效性，從而對點擊行為進行過濾，如果用戶通過點擊鏈接進入鏈接頁面后在鏈接頁面停留的時間τ，如果超過正常人停留頁面時間，那么本次點擊鏈接可計入點擊量中，否則，認為用戶對該鏈接頁面是不感興趣的，不計入點擊量中，正常人瀏覽頁面時間t為

Tw、Tp、Tv分別是網頁文字個數，一個圖片相對漢字數，一個視頻相對文字數;正常人閱讀速度為280字/分。

1.3.3 時間反饋因子

僅僅考慮點擊次數是不能避免偏向舊頁面的問題，因為舊的頁面存在的時間比較長，積累的點擊數比較多，而新頁面存在時間比較短，點擊數比較少，因此有必要引入點擊時間權重因子，可以通過最近一段時間的點擊判斷網頁的活躍程度，單位時間內點擊一個頁面說明是正常的，如果在單位時間內沒有點擊該頁面，該頁面的重要性降低。那么可以根據最近一段時間頁面如果沒有被點擊，就降低PageRank值，可以認為一個新的網頁的內容與重要性相關，如果頁面持續更新則可以提高重要性，設定一個月內點擊屬于正常，計算用戶實時搜索時間和最后點擊結果頁的差異。如果結果頁的點擊率為0，替換最后單擊時間為生成或更新結果的時間頁面。時間間隔是一個月。點擊時間權重公式為

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

2 實驗與結果分析

2.1 實驗環境

2.1.1 硬件環境

3臺PC機，PC機硬件配置:Master節點，主頻3.0 GHZ，內存2 G，硬盤250 G，IP:192.168.80.100;slave1節點，主頻3.0 GHZ，內存2 G，硬盤 160G，IP:192.168.80.110;slave2 節點，主頻3.0 GHZ，內存2 G，硬盤160 G，IP:192.168.80.120。

2.1.2 軟件環境

Java version:1.7.0_09－icedtea

Hadoop version:Hadoop 2.2.0

集群節點信息如表1所示。

表1 集群節點信息

2.2 集群配置

Hadoop集群配置信息和啟動步驟如下:

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

(2)修改IP地址;

(3)通過/etc/hosts修改所有主機名和IP的映射關系;

(4)關閉防火墻;

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

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

(7)配置3個節點間免密碼登錄;

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

(9)啟動HDFS文件系統和Yarn資源管理器。

2.3 實驗配置

實驗將Nutch-1.7版本部署在集群環境中，收集“體育網站”相關網頁18個，與體育無關網頁15個，作為實驗測試網頁。通過體育運動項目“籃球”、“足球”、“羽毛球”、“乒乓球”和“游泳”作為關鍵字進行查詢，分別在單節點，雙節點，3節點上，對爬取速率、檢索速率，查準率的變化進行對比分析。其中，查準率為用戶檢索到符合主題的頁面數與返回頁面總數之比。

通過java語言實現傳統的PageRank算法和改進后的PageRank算法對應的MapReduce程序，實驗參數設置分為4組，并對查準率進行對比分析，如表2所示。分別將4組參數設置的算法打成jar包作為集群環境UDF功能函數，在用戶檢索的結果集中調用PageRank函數計算各頁面的PR值，對結果集進行按PR值進行排序顯示。

表2 影響因子對應查準率表

2.4 結果分析

實驗結果如圖1、圖2和圖3所示。

圖1 不同節點爬取索引時間

圖1、圖2分別是不同節點上網頁爬取時間和不同關鍵字檢索時間對比，在單節點，和雙節點進行頁面爬取索引時，時間相差不大，因為單節點上節點數據存儲和管理都是在本機上完成，而雙節點是一個節點作為主節點，而另一節點作為從節點，集群的優勢都還沒發揮出來，但是3節點的爬取和索引效率提高7.209%，檢索速率提高10.12%，說明集群中隨著節點數的增加，爬取索引和索檢索時間明顯減少，效率有明顯提高。

圖2 不同關鍵字檢索時間

在圖3中，在算法中添加了主題相關度，有效用戶點擊頻率和時間反饋因子改進PageRank算法。經不同關鍵字進行檢索測試，改進后的PageRank算法相對于沒有改進的算法在查準率提高21.4%，更能滿足用戶的檢索需求。

圖3 不同關鍵字查準率

3 結束語

文中算法是在傳統PageRank算法的基礎上同時加入鏈接結構權重，主題相關度，有效用戶點擊率，時間反饋因子對算法進行改進，利用Hadoop的HDFS、MapReduce和Hbase列式數據庫實現實時存儲和檢索網頁數據，提高搜索引擎排序效率，通過實驗數據分析表明，改進后的PageRank算法在Nutch上的爬取索引效率提高7.209%，用戶在網頁檢索效率上提高10.12%，查準率提高21.4%，并且隨著集群節點數和數據量的增加，搜索引擎的檢索效率逐漸增強。

[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.信息檢索導論[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實戰[M].牛長流，肖宇，譯.北京:北京郵電出版社，2011:81－93.

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