基于Hadoop的PageRank算法改进

施磊磊

摘要：针对PageRank算法查准率和检索效率低的问题，通过增加用户点击率、网页发布时间以及主题内容相关度3个影响因子改进PageRank算法，提高用户查准率；利用MapReduce技术实现改进的PageRank算法，提高网页排序和检索效率；最后通过实验结果数据对比，发现用户检索效率和用户查询准确率有较大提高。

关键词：Hadoop集群 ；MapReduce ；PageRank

DOIDOI：10.11907/rjdk.143458

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2015）001006403

0 引言

作为Google公司核心技术的PageRank算法[12]存在主题漂移、对新网页有歧视等问题，随着搜索引擎技术的不断发展，面对数以 TB 甚至 PB 级的海量数据，传统单机模式下的PageRank算法往往由于 CPU、Memory 以及 I/O开销过大效率较低。本文首先利用用户点击率、网页发布时间以及主题内容相关度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]在该算法的基础上提出了一种改进的非平均发送权值PageRank算法；由于 PageRank算法对新发布的网页存在一定程度的偏见，文献[6] 同时考虑网页的主题内容相关和网页时间因子，优化了该算法。

上述算法取得了良好的效果，但由于缺乏用户反馈，忽视了主观的网络用户行为选择。为了解决这个问题，文献[7]提出通过分析主题内容和网页链接来提高算法识别能力，可以有效地避免或减少主题漂移现象。但由于缺乏用户反馈系数，不能很好的体现用户的需求。针对这一问题，文献[8]通过用户点击和内容的相关性，提出了一种改进的PageRank算法。

以上研究都只考虑到部分影响因子，或多或少存在一些不足。本文结合用户的主观行为、网页更新时间以及网页内容的主题相关性，将用户点击、时间反馈与主题内容相关性3个影响因子融入到最后的网页排序计算中，较好地解决了 PageRank算法的不足，使用户查询体验更好，满意度更高。

1.2.1 网页时间反馈因子

由于用户对新网页点击的次数少，对旧网页点击的次数较多，所以为了能够让新网页的点击次数增加，

需考虑网页的发布日期。但网页的格式往往不规范，从网页中找到发布日期很难，本文通过搜索引擎搜索周期来表示每个网页的生存期。一般情况下，搜索引擎周期从半个月到一个月不等，如果网页发布比较早，那么很有可能在每一个搜索引擎搜索周期内都能够被检索到。本文采取以下方法：如网页在同一搜索周期内搜索到多次，只算作一次，也就是说网页的存在时间与搜索引擎搜索到该页面的次数 T成正比。

网页更新时间函数Qt，即

Qt=QT（2）

式（2）中Qt为网页的时间反馈因子；T为该网页被搜索到的周期次数；k是一个固定值，可以通过实验测出；最终收敛时k/T趋于1，Qt趋于1。

1.2.2 用户点击信息统计

用户浏览信息时只会点击自己感兴趣的网页，本文据此对 PageRank算法进行优化在计算网页 PR值时，如单从被点击的次数入手考虑出链网页的重要性程度，即网页的存活时间越长，它在存活周期内被点击的次数也就越多，这样对新分布的网页不公平。为了解决此问题，本文通过统计本次网页爬取之后的点击次数与上一次网页爬取时统计的点击次数之差来分配网页的 PR值，如果该网页在一段时间内被点击次数增加的速度越快，那么该网页得到的 PR值就越大。

由于网页的点击次数可以人为控制，所以存在人为提高某类网页的PR值，骗取网页的流量的情况。针对此问题在统计时需考虑如何减少作弊行为对网页重要性的影响。点击量统计步骤如下：

（1）数据定期清理。如果某些IP地址的用户对某个固定网页的点击次数一天内超过一定阈值，那么就进行数据清理。

（2）用户使用率。不完全靠用户的点击次数来计算得分，而是相应地定义用户在一定时间内的点击次数。网页在一定时间内的点击次数可以通过在http：//www.alexa.com/输入网址来获取。通过boost值的高低来设置网页的重要性程度，通过权值的高低表现出来。用户点击率高，设置的权值大；点击率低，设置的权值小，这样用户在使用搜索引擎进行搜索的时候可充分考虑用户的反馈信息。

1.2.3 网页主题内容

为了能有更好的用户体验，只考虑网页的发布时间和用户的点击喜好是不够全面的。本文考虑

网页的主题内容是否相关，其基本思想是：一个网页的主题内容与它出链网页的主题内容越相关，因而在进行全值分配时，该出链接网页得到的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 设定免密码登陆

先确认网络连接，然后输入命令，在当前目录下创建.ssh文件夹，如果没有手动创建，则产生密钥。

2.3 配置和启动Hadoop

修改Hadoop集群的配置文件，首先将coresite. Xml中fs.Default.name对应属性值修改为hdfs：//（主机+端目号）；mapredsite.Xml中mapred.Job.tracker对应的属性值修改为10.3.11.27：9999；修改master文件中localhost为Hadoop集群中主节点Namenode的IP地址。最后，在master主机中的/etc/hosts文件中添加Hadoop集群中所有从节点Datanode的IP地址。完成上述操作后，拷贝master节点上的所有配置过的文件至slave节点，至此，Hadoop完成集群配置。

2.4 实验设置

实验采用Nutch1.2版本，采用“中药类的网站”作为抓取对象，共收集中药类相关网站11个，其它无关网站9个，构成本次实验的测试数据；以“当归”、“枸杞”、“人参”、“ 甘草”、“陈皮”5个不同的查询词作为实验测试参数。然后分别比较单节点、双节点和三节点的爬取和索引、检索耗时以及查准率的变化。

本文采用搜索结果的查准度来评价算法性能，定义如下：

查准率=用户检索到的目标页面数/返回的页面总数

2.5 结果分析

实验结果如图1、图2所示。

图1 爬取和索引时间

从图1、图2可以看出，在网页爬取和索引检索时，双节点的运行效率比单节点效率高。但两者之间的差距并不是很大，尤其是检索时，随着节点数的增加，三节点系统处理效能才体现出来，同时三节点集群运行时用户检索的效率有较大提高。

图2 5个查询关键词：检索完成时间对比

图3结果表明，在Nutch中改进PageRank算法后，与Nutch没有改进PageRank算法对比，用户平均查准率

有较大提高。用未改进的PageRank算法的查准率明显低于考虑3个影响因子的查准率。改进的PageRank算法能够更加准确地理解用户的需求，用户的查询满意度得以提高。

图3 查询准确率对比

3 结语

同时考虑用户点击率、网页时间与主题内容相关度这3个影响因子，弥补了PageRank算法的不足。利用基于 HDFS文件系统的 HBase数据库达到实时高效地检索海量网页数据，改善分布式搜索引擎排序效果的目的。实验结果表明，处理的数据量越大，集群的节点越多，搜索引擎检索的效率越高。