mapreduce——wiki网页pagerank算法

《mapreduce——wiki网页pagerank算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、WiKi网页PageRank算法目录一、实验设计11.实验说明12.算法说明13.类说明3(1).GraphBuilder3(2).PageRankIter3(3).RankViewer4(4).PageRankDriver4二、实验结果说明41.程序开始运行42.MapReduce的工作情况43.程序结束运行54.生成的中间文件65.程序运行结果7三、性能和不足8四、源程序81.GraphBuilder类82.PageRankIter类93.PageRankViewer类104.PageRankDriver类12五、心得体会12一、实验设计1.实验说明在Ecl

2、ipse环境下编写实现WiKi网页数据集的PageRank算法。2.算法说明PageRank是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术，是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）。从许多优质的网页链接过来的网页，必定还是优质网页。一个网页要想拥有较高的PR值的条件：1）多网页链接到它；2）质量的网页链接到它。PageRank的简化模型可以把互联网上的各个网页之间的链接关系看成一个有向图。对于任意网页Pi，它的PageRank值可表示为：其中Bi为所有链接到网页i的网页集合，Lj为

3、网页j的对外链接数（出度）。PageRank的随机浏览模型假定一个上网者从一个随机的网页开始浏览，网者不断点击当前网页的链接开始下一次浏览。但是，上网者最终厌倦了，开始了一个随机的网页。随机上网者访问一个新网页的概率就等于这个网页的PageRank值。这种PageRank的随机浏览模型比较接近于用户的行为。随机浏览模型的图表示：设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。随机浏览模型的矩阵表示：令：H’=d*H+(1-d)*[1/N]N×N则：R=H’R其中R为列向量，代表PageRank值；H’代表转移

4、矩阵；d代表阻尼因子，通常设为0.85。由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很大的稀疏矩，采用邻接表来表示网页之间的连接关系。随机浏览模型的PageRank公式：通过迭代计算得到所有节点的PageRank值。随机浏览模型更加符合用户的行为，在一定程度上解决了ranksink问题，保证了PageRank存在唯一值。1.类说明(1).GraphBuilder这个类的目标是分析原始数据，建立各个网页之间的链接关系。它的Map用于逐行分析原始数据,输出。其中网页的URL作为key,PageRank初始值（

5、PR_init）和网页的出度列表一起作为value,以字符串表示value，用特定的符号将二者分开。该阶段Reduce不作任何处理。(1).PageRankIter这个类用于迭代计算PR值，直到PR值收敛或迭代预定次数。它的Map对上阶段的产生两种对：1)Foreachuinlink_list,输出

6、link_list

7、>其中u代表当前URL所链接到网页ID，并作为key；Cur_rank为当前URL的PageRank值，

8、link_list

9、为当前URL的出度数量

10、，,cur_rank/

11、link_list

12、作为value。2)同时在迭代过程中，传递每个网页的链接信息在迭代过程中，必须保留网页的局部链出信息，以维护图的结构。它的Reduce对Map输出的和多个做如下处理：其中为当前URL的链出信息；为当前URL的链入网页对其贡献的PageRank值。计算所有val的和，并乘上d，在加上常数(1-d)/N得到new_rank，最后输出(URL,(new_rank,url_list))。迭代计算公式为：PR

13、(A)=(1-d)/N+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))(2).RankViewer这个类用于从最后一次迭代的结果读出文件，并将文件名和其PR值读出，并以PR值为key网页名为value，并且以PR值从大到小的顺序输出。排序过程中采用框架自身的排序处理，重载key的比较函数。(3).PageRankDriver进行多趟MapReduce的处理。一、实验结果说明1.程序开始运行将程序打包成wikiPageRank.jar，将jar包和wiki网页数据集通过Xmanager的Xftp上传到集群，然后在集群的hadoop将数据集上传到h

14、dfs：hadoopfs