文章 56
评论 99
浏览 272355
hadoop下基于mapreduce实现pagerank算法

hadoop下基于mapreduce实现pagerank算法

摘要: PageRank,网页排名,又称网页级别、Google 左侧排名或佩奇排名,是一种由[1] 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以 Google 公司创办人拉里·佩奇(Larry Page)之姓来命名。Google 用它来体现网页的相关性和重要性,在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google 的创始人拉里·佩奇和谢尔盖·布林于 1998 年在斯坦福大学发明了这项技术。

PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级。Google 把从 A 页面到 B 页面的链接解释为 A 页面给 B 页面投票,Google 根据投票来源(甚至来源的来源,即链接到 A 页面的页面)和投票目标的等级来决定新的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

PageRank 的核心公式是:
PR(A)=(1-d)+d(PR(B)/C+PR(C)/C......PR(Z)/C)

  • PR(A)是指网页 A 的 PR 数值
  • PR(i)是链接向 A 页面的 i 页面的 PR 值
  • C 是网页 i 往其他页面输出的链接的数量
  • d 是一个常数,谷歌设置为 0.85。d 的出现很简单,因为会有特殊的情况出现,比如:如果一个网页来访者没有点击任何一个链接,那么这个页面的 PR 最小就应该是 0.15;如果这个页面一个外链都没有得到那么这个页面的 PR 最小也应该是 0.15

如果看不懂上面的公式,那么就为大家用一句话来总结这个公式:网页 A 的 PR 值就等于导入链接 PR 值的总和,只不过每一个导入链接的 PR 值不一样罢了,每一个导入链接的 PR 值就是这个页面 PR 值比上到处链接的数量。

根据这个公式我们得出了这样一个结论:换友情链接一定要找 PR 值高的网站,导出链接少的网站。

PR 值是一个不固定的数字,许多检测 PR 的工具都只是估算,最简单的办法判断友情链接的 PR 值的高低,可以用要交换站的 PR 除以它自己到处的外链,就可以大概判断出对方权重的高低,希望能给新手朋友有所帮助。如果还是不太理解的,可以百度网上别人详解讲解 PageRank 算法的博客。

所以,根据上面的总结可以得出一般的 PR 公式:pr=0.15+0.85*sum

接下来,就在 hadoop 下基于 mapreduce 编程模型实现 PageRank 算法:

package org.apache.hadoop.pr;

import java.io.IOException;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.StringTokenizer;
import java.util.Iterator;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.GenericOptionsParser;

public class PageRank {

  public static class MyMapper 
       extends Mapper<Object, Text, Text, Text>{
    private Text id = new Text();
    public void map(Object key, Text value, Context context
                    ) throws IOException, InterruptedException {
		  String line = value.toString();
//因为hadoop在reduce写入hdfs的时候会生成三个文件_SUCCESS,_logs,part-r-00000,而迭代时能用到的只有第三个,所以需要判断读出来的是不是有效,这里通过判断第一个字符是不是数字简单地判断了一下,用startsWith是不行的,它不接受正则表达式。
		  if(line.substring(0,1).matches("[0-9]{1}"))
		  {
			  boolean flag = false;
			  if(line.contains("_"))
			  {
				line = line.replace("_","");
				flag = true;
			  }
//这个地方很重要,也许你会问为什么根据\t来split而不是空格,原因是context.write在写入的时候是在key/value对中加入了一个\t,为方便迭代处理,因此先这样split。
                          String[] values = line.split("\t");
			  Text t = new Text(values[0]);
			  String[] vals = values[1].split(" ");
//因为下次迭代的时候还会用到url,所以需要将这些url也保留下来,但是为了方便reduce计算的时候区别,加一个特殊符号_做标记。
                          String url="_";
			  double pr = 0;
			  int i = 0;
			  int num = 0;
//这个地方的为什么要加个flag变量下面的reduce里头再解释。
			  if(flag)
			  {
				i=2;
				pr=Double.valueOf(vals[1]);
				num=vals.length-2;
			  }
			  else
			  {
				i=1;
				pr=Double.valueOf(vals[0]);
				num=vals.length-1;
			  }
			  for(;i<vals.length;i++)
			  {
				url=url+vals[i]+" ";
				id.set(vals[i]);
				Text prt = new Text(String.valueOf(pr/num));
				context.write(id,prt);
			  }
			  context.write(t,new Text(url));
		}
    }
  }
  
  public static class MyReducer 
       extends Reducer<Text,Text,Text,Text> {
    private Text result = new Text();
    private Double pr = new Double(0);
    public void reduce(Text key, Iterable<Text> values, 
                       Context context
                       ) throws IOException, InterruptedException {
      double sum=0;
      String url="";
      for(Text val:values)
      {
//发现_标记则表明是url,否则是外链pr,要参与计算
		if(!val.toString().contains("_"))
		{
		  sum=sum+Double.valueOf(val.toString());
		}
		else
		{
		  url=val.toString();
		}
      }
      pr=0.15+0.85*sum;
      String str=String.format("%.3f",pr);
//这个地方纠结了我最久,原本pr是个double型数,但是我转成str之后,发现输出时前面多了一列比如原本应该是输出0.575,结果却是0.1500.575,而且我加空格后是0.150 0.575,这个我到现在都没明白这到底是因为什么,所以我只能让它写入结果文件,然后再下次迭代的时候再进行预处理,也就是上面map阶段的那个flag的作用。
      result.set(new Text(str+" "+url));
      context.write(key,result);
    }
  }

  public static void main(String[] args) throws Exception {
    String paths="/user/root/out/00";
    String path1=paths;
    String path2="";
//实验证明,基本上10次左右迭代就已经收敛了
    for(int i=1;i<=20;i++)
    {
	System.out.println("This is the "+i+"th job!");
	System.out.println("path1:"+path1);
	System.out.println("path2:"+path2);
        Configuration conf = new Configuration();
    	Job job = new Job(conf, "PageRank");
        path2=paths+i;
    	job.setJarByClass(PageRank.class);
    	job.setMapperClass(MyMapper.class);
    	job.setCombinerClass(MyReducer.class);
    	job.setReducerClass(MyReducer.class);
    	job.setOutputKeyClass(Text.class);
    	job.setOutputValueClass(Text.class);
    	FileInputFormat.addInputPath(job, new Path(path1));
    	FileOutputFormat.setOutputPath(job, new Path(path2));
        path1=path2;
    	job.waitForCompletion(true);
	System.out.println(i+"th end!");
  }
 }	
}

初始输入文件格式,表示了网页的链接情况(前两列间用\t 隔开):

1 1.0 2 3 4
2 1.0 3 4
3 1.0 4
4 1.0 2

结果文件形式(第二列是多出来的):

1 0.150 0.150 _2 3 4
2 0.150 1.283 _3 4
3 0.150 0.858 _4
4 0.150 1.708 _2


微信公众号

潘建锋

关于版权和转载

本文由 潘建锋 创作,采用 署名 4.0 国际 (CC BY 4.0) 国际许可协议进行授权。
本站文章除注明转载/出处外,均为本站原创或翻译,转载时请务必署名,否则,本人将保留一切追究责任的权利。
署名 4.0 国际 (CC BY 4.0)

转载规范

标题:hadoop下基于mapreduce实现pagerank算法
作者:潘建锋
原文:https://taohuawu.club/pagerank-algorithm-via-hadoop-mapreduce

关于留言和评论

如果您对本文《hadoop下基于mapreduce实现pagerank算法》的内容有任何疑问、补充或纠错,欢迎在下面的评论系统中留言,与作者一起交流进步,谢谢!(~ ̄▽ ̄)~

鲜衣怒马提银枪,一日看尽长安花,此间少年。