`
十三月的
  • 浏览: 168414 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

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);

		}

	}
 

 

 

 

  • 大小: 15.4 KB
  • 大小: 38.4 KB
4
1
分享到:
评论
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值

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

相关推荐

    python实现PageRank算法

    PageRank是Google创始人Larry Page提出的一种网页排名算法,它通过计算网页之间的链接关系来评估网页的重要性,从而为搜索引擎提供一种衡量网页质量的方式。在Python中实现PageRank算法可以帮助我们理解其工作原理,...

    Hadoop-MapReduce下的PageRank矩阵分块算法

    PageRank算法通过模拟随机用户在Web上的浏览行为,计算出每个网页的重要性得分。其核心思想是将Web看作一个有向图,其中节点表示网页,边表示从一个网页到另一个网页的链接。PageRank分数通过以下公式计算: \[ PR...

    山东大学大数据实验三:Hadoop实现PageRank

    在本实验中,我们将探索如何使用Hadoop框架来实现PageRank算法,这是Google早期用于网页排名的核心算法。这个实验由山东大学设计,旨在让学生深入理解大数据处理和分布式计算的概念。 首先,我们来看PageRank的基本...

    pagerank_大数据pagerank算法代码_pageRank_

    在这个南开大学的大数据课程大作业中,学生们被要求实现PageRank算法,通过Python代码来处理大规模数据。下面我们将深入探讨PageRank算法的核心原理、实现过程以及在大数据环境下的应用。 **PageRank原理** ...

    java实现和Matlab语言实现的pagerank算法

    Hadoop允许在廉价硬件上进行并行处理,非常适合处理PageRank算法所需的大量网页链接数据。在Hadoop环境中,PageRank的实现通常涉及MapReduce编程模型,其中Map阶段将数据切片并分配给各个节点,Reduce阶段负责聚合和...

    pagerank_BSU_大数据课程大作业一_南开大学_pagerank算法_pageRank_

    PageRank算法基于这样的假设:如果一个高质量的网页链接到另一个网页,那么后者也很可能有较高的质量。 在分块处理PageRank时,因为原始数据集可能非常庞大,无法一次性加载到内存中,所以需要将数据分割成多个小块...

    Hadoop (十五)Hadoop-MR编程 -- 【使用hadoop计算网页之间的PageRank值----编程】

    在reduce阶段,reducer会接收到所有指向同一个网页的链接,汇总这些链接的PageRank值,并按照PageRank算法进行计算。PageRank的更新公式如下: ``` PR(A) = (1-d) + d * (PR(T1)/L(T1) + ... + PR(Tn)/L(Tn)) ``...

    基于hadoop对网页进行排名.zip

    而“基于Hadoop对网页进行排名”这一主题,正是解决这个问题的一种方法,它涉及到的核心技术是分布式计算框架Hadoop以及其在搜索引擎中的应用——PageRank算法。 Hadoop,作为大数据处理的基石,是由Apache基金会...

    Pagerank-using-hadoop:本项目使用hadoop实现页面排名算法

    下面我们将详细探讨PageRank算法及其在Hadoop上的实现。 **PageRank算法** PageRank的核心思想是,一个被许多高质量网页链接的网页,其自身也更可能具有高质量。PageRank的计算基于以下假设: 1. **随机浏览模型*...

    Algorithm-hadoop-pagerank.zip

    本篇文章将深入探讨如何在Hadoop上实现PageRank算法。 PageRank的核心思想是:一个网页的重要性取决于其他网页对它的链接数量和质量。在Hadoop框架下,PageRank的实现主要分为两个阶段:迭代计算和结果聚合。 1. *...

    数据算法++Hadoop+Spark大数据处理技巧

    通过深入研究这个源码包,开发者可以了解如何在Hadoop和Spark平台上有效地实现和优化大数据处理算法,这对于提升大数据处理能力和解决实际问题具有极高的价值。同时,它也提供了实践和学习大数据技术的良好机会。

    基于Hadoop的PageRank算法并行实现+源代码+文档说明

    基于Hadoop的PageRank算法并行实现+源代码+文档说明 -------- 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载...

    pagerank.zip

    pagerank算法是Google创始人拉里·佩奇和谢尔盖·布林提出的一种评估网页重要性的数学模型,它通过分析互联网上的超链接结构来衡量网页的重要性。在本项目中,我们利用Java编程语言实现了基于MapReduce的PageRank...

    Pagerank实验.zip

    PageRank算法是Google创始人拉里·佩奇和谢尔盖·布林在1998年提出的一种衡量网页重要性的算法,它是Google搜索引擎早期的核心技术之一。该算法通过分析网页之间的链接关系来评估网页的重要性,将互联网视为一个巨大...

    pagerank-java实现查询

    此外,PageRank算法还需要考虑一些特殊情况,例如悬挂链接(一个网页没有出链)和循环链接(网页A链接到B,B又链接回A)。对于悬挂链接,通常会引入“damping factor”(阻尼因子),使得每个网页的一部分PageRank会...

    pagerank:谷歌页面排名算法

    PageRank算法的实现网页排名这是使用 Java 实现的 PageRank 算法驱动程序程序的 Main() 函数位于此文件中。 执行从这里开始。 它收集命令行参数并从主函数调用后续作业。 最初,首先调用图形属性作业。 图.java 该类...

    基于Spark+PageRank算法构建仿微博用户好友的分布式推荐系统.zip

    PageRank算法是Google早期用于网页排名的一种方法,它通过计算网页之间的链接关系来评估其重要性。在社交网络中,PageRank可以被用来衡量用户之间的影响力或相似性。在这个推荐系统中,PageRank被用于计算用户之间的...

Global site tag (gtag.js) - Google Analytics