施磊磊

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

關鍵詞：Hadoop集群 ；MapReduce ；PageRank

DOIDOI：10.11907/rjdk.143458

中圖分類號：TP312

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

0 引言

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

1 PageRank算法

1.1 算法簡介

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

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

其中，x為0.15；C（Tn）為網(wǎng)頁Tn的出鏈接數(shù)；（1-x）是阻尼系數(shù)。

1.2 算法改進

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

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

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

1.2.1 網(wǎng)頁時間反饋因子

由于用戶對新網(wǎng)頁點擊的次數(shù)少，對舊網(wǎng)頁點擊的次數(shù)較多，所以為了能夠讓新網(wǎng)頁的點擊次數(shù)增加，

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

網(wǎng)頁更新時間函數(shù)Qt，即

Qt=QT（2）

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

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

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

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

（1）數(shù)據(jù)定期清理。如果某些IP地址的用戶對某個固定網(wǎng)頁的點擊次數(shù)一天內(nèi)超過一定閾值，那么就進行數(shù)據(jù)清理。

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

1.2.3 網(wǎng)頁主題內(nèi)容

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

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

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

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

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

網(wǎng)頁最后得分計算公式：

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為網(wǎng)頁的時間函數(shù)；c為站內(nèi)站外系數(shù)比；SIM（P，A）是網(wǎng)頁的相似度；Wi為出鏈接的個數(shù)。對于沒有明確主題的出鏈網(wǎng)站采用權(quán)值平均分配的原則進行分配，計算每一個網(wǎng)頁最后的PRScore值，然后根據(jù)PRScore值由高到低進行排序。

2 實驗過程與結(jié)果分析

2.1 相關準備

1臺master，2臺slave。

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

軟件安裝：

Hadoop版本 1.1.2

Jdk版本 1.7.0_25

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

數(shù)據(jù)目錄：/home/administrator/sll

集群信息如表1所示。

2.2 設定免密碼登陸

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

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

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

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

2.5 結(jié)果分析

實驗結(jié)果如圖1、圖2所示。

圖1 爬取和索引時間

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

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

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

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

圖3 查詢準確率對比

3 結(jié)語

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