基于Hadoop的PageRank算法改進

施磊磊

摘要：針對PageRank算法查準率和檢索效率低的問題，通過增加用戶點擊率、網頁發(fā)布時間以及主題內容相關度3個影響因子改進PageRank算法，提高用戶查準率；利用MapReduce技術實現改進的PageRank算法，提高網頁排序和檢索效率；最后通過實驗結果數據對比，發(fā)現用戶檢索效率和用戶查詢準確率有較大提高。

關鍵詞：Hadoop集群 ；MapReduce ；PageRank

DOIDOI：10.11907/rjdk.143458

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2015）001006403

0 引言

作為Google公司核心技術的PageRank算法[12]存在主題漂移、對新網頁有歧視等問題，隨著搜索引擎技術的不斷發(fā)展，面對數以 TB 甚至 PB 級的海量數據，傳統(tǒng)單機模式下的PageRank算法往往由于 CPU、Memory 以及 I/O開銷過大效率較低。本文首先利用用戶點擊率、網頁發(fā)布時間以及主題內容相關度3個影響因子改進PageRank算法，避免主題漂移和對新網頁的歧視，并且通過用戶的點擊率賦予鏈接相應的權值，從而提高用戶的查詢準確率和體驗感。同時，使用Apache開源的 Hadoop [3]分布式平臺來實現改進的PageRank算法，利用基于 HDFS[4]的 HBase技術達到實時高效檢索海量網頁數據，從而達到提高用戶檢索效率的目的。

1 PageRank算法

1.1 算法簡介

PageRank算法是谷歌公司推出的網頁排序算法，它基于鏈接結構，核心思想為：如果一個網頁的鏈接程度越高，該網頁就越重要，權重就越大，計算出來的得分也就越高，在返給用戶的搜索結果列表中的排名就越靠前。PageRank的計算公式為[1]：

PR（A）=x+（1-x）（PR（T1）C（T1）+...+PR（Tn）C（Tn））（1）

其中，x為0.15；C（Tn）為網頁Tn的出鏈接數；（1-x）是阻尼系數。

1.2 算法改進

針對PageRank算法存在的主題漂移問題，文獻[5]在該算法的基礎上提出了一種改進的非平均發(fā)送權值PageRank算法；由于 PageRank算法對新發(fā)布的網頁存在一定程度的偏見，文獻[6] 同時考慮網頁的主題內容相關和網頁時間因子，優(yōu)化了該算法。

上述算法取得了良好的效果，但由于缺乏用戶反饋，忽視了主觀的網絡用戶行為選擇。為了解決這個問題，文獻[7]提出通過分析主題內容和網頁鏈接來提高算法識別能力，可以有效地避免或減少主題漂移現象。但由于缺乏用戶反饋系數，不能很好的體現用戶的需求。針對這一問題，文獻[8]通過用戶點擊和內容的相關性，提出了一種改進的PageRank算法。

以上研究都只考慮到部分影響因子，或多或少存在一些不足。本文結合用戶的主觀行為、網頁更新時間以及網頁內容的主題相關性，將用戶點擊、時間反饋與主題內容相關性3個影響因子融入到最后的網頁排序計算中，較好地解決了 PageRank算法的不足，使用戶查詢體驗更好，滿意度更高。

1.2.1 網頁時間反饋因子

由于用戶對新網頁點擊的次數少，對舊網頁點擊的次數較多，所以為了能夠讓新網頁的點擊次數增加，

需考慮網頁的發(fā)布日期。但網頁的格式往往不規(guī)范，從網頁中找到發(fā)布日期很難，本文通過搜索引擎搜索周期來表示每個網頁的生存期。一般情況下，搜索引擎周期從半個月到一個月不等，如果網頁發(fā)布比較早，那么很有可能在每一個搜索引擎搜索周期內都能夠被檢索到。本文采取以下方法：如網頁在同一搜索周期內搜索到多次，只算作一次，也就是說網頁的存在時間與搜索引擎搜索到該頁面的次數 T成正比。

網頁更新時間函數Qt，即

Qt=QT（2）

式（2）中Qt為網頁的時間反饋因子；T為該網頁被搜索到的周期次數；k是一個固定值，可以通過實驗測出；最終收斂時k/T趨于1，Qt趨于1。

1.2.2 用戶點擊信息統(tǒng)計

用戶瀏覽信息時只會點擊自己感興趣的網頁，本文據此對 PageRank算法進行優(yōu)化在計算網頁 PR值時，如單從被點擊的次數入手考慮出鏈網頁的重要性程度，即網頁的存活時間越長，它在存活周期內被點擊的次數也就越多，這樣對新分布的網頁不公平。為了解決此問題，本文通過統(tǒng)計本次網頁爬取之后的點擊次數與上一次網頁爬取時統(tǒng)計的點擊次數之差來分配網頁的 PR值，如果該網頁在一段時間內被點擊次數增加的速度越快，那么該網頁得到的 PR值就越大。

由于網頁的點擊次數可以人為控制，所以存在人為提高某類網頁的PR值，騙取網頁的流量的情況。針對此問題在統(tǒng)計時需考慮如何減少作弊行為對網頁重要性的影響。點擊量統(tǒng)計步驟如下：

（1）數據定期清理。如果某些IP地址的用戶對某個固定網頁的點擊次數一天內超過一定閾值，那么就進行數據清理。

（2）用戶使用率。不完全靠用戶的點擊次數來計算得分，而是相應地定義用戶在一定時間內的點擊次數。網頁在一定時間內的點擊次數可以通過在http：//www.alexa.com/輸入網址來獲取。通過boost值的高低來設置網頁的重要性程度，通過權值的高低表現出來。用戶點擊率高，設置的權值大；點擊率低，設置的權值小，這樣用戶在使用搜索引擎進行搜索的時候可充分考慮用戶的反饋信息。

1.2.3 網頁主題內容

為了能有更好的用戶體驗，只考慮網頁的發(fā)布時間和用戶的點擊喜好是不夠全面的。本文考慮

網頁的主題內容是否相關，其基本思想是：一個網頁的主題內容與它出鏈網頁的主題內容越相關，因而在進行全值分配時，該出鏈接網頁得到的PR值就越大。出鏈有兩種情況：一種是站內出鏈，另外一種是站外出鏈。對于這兩種情況要進行不同的權值分配，利用一個系數c（0

網頁鏈接之間的主題內容相關性的度量可以通過向量空間模型計算出來。計算方法是將有鏈接關系的網頁放在一起進行分析，可以將這些網頁分為有明確主題的和沒有明確主題類型。

對于有明確主題的網頁，將每個網頁中的出鏈超鏈接對應的錨文本，使用VSM來進行計算。

對于沒有明確主題的網頁，判斷出鏈鏈接是站內還是站外，按照權值進行分配。站外出鏈賦予較高的權值，避免作弊行為，相對公正。

網頁最后得分計算公式：

PRScore=x+（1-x）c*Wi（W1+…+Wj）*PR（R1）C（T1）+..+PR（Rk）C（Tk）+（1-c）*PR（Rk+1）C（Tk+1）+…+PR（Rn）C（Tn）*SIM（P，A）*Qt（3）

其中， Qt為網頁的時間函數；c為站內站外系數比；SIM（P，A）是網頁的相似度；Wi為出鏈接的個數。對于沒有明確主題的出鏈網站采用權值平均分配的原則進行分配，計算每一個網頁最后的PRScore值，然后根據PRScore值由高到低進行排序。

2 實驗過程與結果分析

2.1 相關準備

1臺master，2臺slave。

PC機的硬件配置如下：master機器，主頻為2.93Ghz，內存2G，硬盤160G，IP：10.3.11.26；slave1機器，主頻2.93Ghz，內存2G，硬盤160G，IP：10.3.11.27；slave2機器，主頻是2.93Ghz，內存2G，硬盤160G，IP：10.3.11.28。

軟件安裝：

Hadoop版本 1.1.2

Jdk版本 1.7.0_25

安裝路徑：/home/administrator/hadoop1.1.2

數據目錄：/home/administrator/sll

集群信息如表1所示。

2.2 設定免密碼登陸

先確認網絡連接，然后輸入命令，在當前目錄下創(chuàng)建.ssh文件夾，如果沒有手動創(chuàng)建，則產生密鑰。

2.3 配置和啟動Hadoop

修改Hadoop集群的配置文件，首先將coresite. Xml中fs.Default.name對應屬性值修改為hdfs：//（主機+端目號）；mapredsite.Xml中mapred.Job.tracker對應的屬性值修改為10.3.11.27：9999；修改master文件中l(wèi)ocalhost為Hadoop集群中主節(jié)點Namenode的IP地址。最后，在master主機中的/etc/hosts文件中添加Hadoop集群中所有從節(jié)點Datanode的IP地址。完成上述操作后，拷貝master節(jié)點上的所有配置過的文件至slave節(jié)點，至此，Hadoop完成集群配置。

2.4 實驗設置

實驗采用Nutch1.2版本，采用“中藥類的網站”作為抓取對象，共收集中藥類相關網站11個，其它無關網站9個，構成本次實驗的測試數據；以“當歸”、“枸杞”、“人參”、“ 甘草”、“陳皮”5個不同的查詢詞作為實驗測試參數。然后分別比較單節(jié)點、雙節(jié)點和三節(jié)點的爬取和索引、檢索耗時以及查準率的變化。

本文采用搜索結果的查準度來評價算法性能，定義如下：

查準率=用戶檢索到的目標頁面數/返回的頁面總數

2.5 結果分析

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

圖1 爬取和索引時間

從圖1、圖2可以看出，在網頁爬取和索引檢索時，雙節(jié)點的運行效率比單節(jié)點效率高。但兩者之間的差距并不是很大，尤其是檢索時，隨著節(jié)點數的增加，三節(jié)點系統(tǒng)處理效能才體現出來，同時三節(jié)點集群運行時用戶檢索的效率有較大提高。

圖2 5個查詢關鍵詞：檢索完成時間對比

圖3結果表明，在Nutch中改進PageRank算法后，與Nutch沒有改進PageRank算法對比，用戶平均查準率

有較大提高。用未改進的PageRank算法的查準率明顯低于考慮3個影響因子的查準率。改進的PageRank算法能夠更加準確地理解用戶的需求，用戶的查詢滿意度得以提高。

圖3 查詢準確率對比

3 結語

同時考慮用戶點擊率、網頁時間與主題內容相關度這3個影響因子，彌補了PageRank算法的不足。利用基于 HDFS文件系統(tǒng)的 HBase數據庫達到實時高效地檢索海量網頁數據，改善分布式搜索引擎排序效果的目的。實驗結果表明，處理的數據量越大，集群的節(jié)點越多，搜索引擎檢索的效率越高。