基于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.