hadoop上跑一下网页排名算法之PageRank算法

          也许google当初的PageRank网页排名有着很严密的数学逻辑推导，但在编程的时候实现这种数学推导困难很大，用的更多的是另外一个超级简单的数学公式，同样可以实现将网页排名的目的。

 

PageRank原理分析

            举例来讲 ：

       假设每个网页都有一个自己的默认PR值，相当于人为添加给它是一种属性，用来标识网页的等级或者重要性，从而依据此标识达到排名目的。假设有ID号是1的一个网页，PR值是10，假如它产生了到ID=3，ID=6，ID=8 ，ID=9这4个网页的链接。那么可以理解为ID=1的网页向ID=3，6，8，9的4个网页各贡献了2.5的PR值。如果想求任意一个网页假设其ID=3的 PR值 ， 需要得到所有的其他网页对ID=3这个网页的贡献的总和，再按照函数“所求PR”=“总和”*0.85+0.15得到。经过循环多次上述过程求得的网页PR值，可以作为网页排名的标识。  

 

MapReduce过程 分析

    1：准备数据  

           理论数据是通过网页爬虫得到了某个特定封闭系统的所有网页的信息，为了测试程序，可以自己模拟生成自己定义特定格式的数据。下面是我用来测试的数据，存储方式如图

 

 

         （注：对于自定义模拟数据，在PR初始值的选取时，所有的网页是“平等”的，不会说自己写的网页和Google的热门网页有多少差别，但是按照某种法则经过一定运算后PR是不一样的，比如很多其他的网页可能会链接到google，它的PR自然会比你的高。所以初始值的选取按照这种逻辑来讲符合现实些，即所有网页默认PR值相等。但是即使初始值定的不一样 ，整个系统的PR总和可能会变化，最后的每个网页PR也会发生变化，但是这种量之间的变化，不会影响到网页自身的通过比较大小方式上的逻辑排名。

 

2：Map过程

        map接受的数据格式默认是<偏移量，文本行>这样的<key,value>对，形如<0,1    5  2 3 4 5><20,2    10 3 5 8 9>.

      目标 ：将默认数据格式，转换成自定义格式<key,value>对。

        已知 ：hadoop框架在Map阶段的时候会自动实现sort过程，就是将相同的key的所有value保存到list，形如<key,list(1,1,1,2)>这种形式，例如上述对ID=2的网页有ID=1，6，7，8.这4个网页贡献（1.25，1，5/3，5），那么如果你采用的key是网页ID，那么hadoop框架会以此种形式<2,list(1.25，1，5/3，5)>输出。

       分析 ： 因为这个过程要进行多次，reduce的最终输出结果需要保存成原文件那样的格式，所以每个网页ID和自己链接情况也要在map阶段输出给reduce。

       操作 ： 所以对于上述第一行操作map函数后结果是<id=1,2><id=1,3><id=1,4>,<id=1,5>保存了id=1网页的链接情况，同时还要输出<id=2,1.25><id=3,1.25><id=4,1.25><id=5,1.25>,每个网页得到的贡献值。

        代码：

public static class MyMapper extends
			Mapper<Object, Text, IntWritable, Text> {

		//存储网页ID
		private IntWritable id;
		//存储网页PR值
		private String pr;
		//存储网页向外链接总数目
		private int count;
		//网页向每个外部链接的平均贡献值
		private float average_pr;

		public void map(Object key, Text value, Context context) {
			StringTokenizer str = new StringTokenizer(value.toString());
			if (str.hasMoreTokens()) {
				// 得到网页ID
				id = new IntWritable(Integer.parseInt(str.nextToken()));
			} else {
				return;
			}
			// 得到网页pr
			pr = str.nextToken();
			// 得到向外链接数目
			count = str.countTokens();
			// 对每个外部链接平均贡献值
			average_pr = Float.parseFloat(pr) / count;
			// 得到网页的向外链接ID并输出
			while (str.hasMoreTokens()) {
				try {
					String nextId = str.nextToken();
					//将网页向外链接的ID以“@+得到贡献值”格式输出
					Text t = new Text("@" + average_pr);
					context.write(id, t);
					// 将网页ID和PR值输出
					Text tt = new Text("&" + nextId);
					context.write(id, tt);
				} catch (IOException e) {
					e.printStackTrace();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}

	}

 Reduce阶段 ：

          分析 ：这个阶段操作就相对简单很多，读取map的输出<key,value>，并解析出来。

          具体操作 ：如果value中首字母是“@”表示是贡献值，如果是“&”表示是链接情况。

public void reduce(IntWritable key, Iterable<Text> values,
				Context context) {

			// 定义一个存储网页链接ID的队列
			ArrayList<String> ids = new ArrayList<String>();
			// 将所有的链接ID以String格式保存
			String lianjie = "  ";
			// 定义一个保存网页PR值的变量
			float pr = 0;
            //遍历
			for(Text id : values) {
				  String idd = id.toString();
				//判断value是贡献值还是向外部的链接
				  if (idd.substring(0, 1).equals("@")) {
					// 贡献值
					pr += Float.parseFloat(idd.substring(1));
				} else if (idd.substring(0, 1).equals("&")) {
					// 链接id
					String iddd = idd.substring(1);
					System.out.println("idddd= " + iddd);
					ids.add(iddd);
				}
			}
			// 计算最终pr
			pr = pr * 0.85f + 0.15f;
			// 得到所有链接ID的String形式
			for (int i = 0; i < ids.size(); i++) {
				lianjie += ids.get(i) + "  ";
			}
			// 组合pr+lianjie成原文件的格式类型
			String result = pr + lianjie;
			System.out.println("Reduce    result=" + result);
			try {
				context.write(key, new Text(result));
				System.out.println("reduce 执行完毕。。。。。");
			} catch (IOException e) {
				e.printStackTrace();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}

 

    main函数:

 

public static void main(String[] args) throws IOException,
			InterruptedException, ClassNotFoundException {

		Configuration conf = new Configuration();
		String pathIn1 = "/usr/local/hadoop/tt/ww";//输入路径
		String pathOut=“”;//输出路径
                //迭代10次
		for (int i = 0; i < 10; i++) {
			System.out.println("xunhuan cishu=" + i);
			Job job = new Job(conf, "MapReduce pagerank");
			pathOut = pathIn1 + i;
			job.setJarByClass(Main2.class);
			job.setMapperClass(MyMapper.class);
			job.setReducerClass(MyReducer.class);
			job.setOutputKeyClass(IntWritable.class);
			job.setOutputValueClass(Text.class);
			FileInputFormat.addInputPath(job, new Path(pathIn1));
			FileOutputFormat.setOutputPath(job, new Path(pathOut));
			pathIn1 = pathOut;
			job.waitForCompletion(true);

		}

	}

 

 

 

 

评论

2 楼 xuezaigds 2012-06-10  

silk0peas10 写道

每太看明白你的程序啊，我觉得map那里应该要改成
String nextId = str.nextToken();
next_id = new IntWritable(Integer.parseInt(nextId));
Text t = new Text("@" + average_pr);
context.write(next_id, t);
Text tt = new Text("&" + nextId);
context.write(id, tt);

k2: 被某一指向的页面（暂且说是p）  v2: p从这个指出的页面得到的部分PR值

不知道这样对不对 ，帮解释下呗

我觉得有道理，map确实有问题。

1 楼 silk0peas10 2012-05-27  

每太看明白你的程序啊，我觉得map那里应该要改成
String nextId = str.nextToken();
next_id = new IntWritable(Integer.parseInt(nextId));
Text t = new Text("@" + average_pr);
context.write(next_id, t);
Text tt = new Text("&" + nextId);
context.write(id, tt);

k2: 被某一指向的页面（暂且说是p）  v2: p从这个指出的页面得到的部分PR值

不知道这样对不对 ，帮解释下呗