也许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
分享到:
相关推荐
Hadoop-MapReduce下的PageRank矩阵分块算法 高清完整中文版PDF下载
Hadoop-MapReduce下的PageRank矩阵分块算法
Pagerank-using-hadoop 该项目使用 hadoop 实现页面排名算法。
压缩包里面是源代码,导出成jar包可以在集群上直接运行,记得改程序里面的学号
基于Hadoop的PageRank算法并行实现+源代码+文档说明 -------- 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载...
Algorithm-hadoop-pagerank.zip,利用apache hadoop框架的pagerank算法实现,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
PageRank算法的实现网页排名这是使用 Java 实现的 PageRank 算法驱动程序程序的 Main() 函数位于此文件中。 执行从这里开始。 它收集命令行参数并从主函数调用后续作业。 最初,首先调用图形属性作业。 图.java 该类...
##MapReduce 编程:使用 hadoop 计算维基百科文章的内部 PageRank。 本课程将向您介绍编程和数据操作的MapReduce模型。 它将提供分析真实数据源的有限实践经验:。 ###数据: 出于本次作业的目的,您已获得一...
hadoop PageRank.jar PageRank.PageRank input_path output_path中间路径 -参数 input_path is the folder containing input file(s) output_path is the folder containing final output file(s)...
网页排名Google 的 PageRank 算法在 MapReduce 范式中的实现。 Apache Hadoop、Java
网页排名SimpleWiki数据集上PageRank算法的MapReduce实现。
互联网的高速发展使Internet上信息数量呈几何式 增长。现有的集中式搜索引擎从如此海量的信息中快速检 索出真正需要的信息正变得越来越困难,所以搜索引擎系 统应具有分布式处理能力,能根据需要处理信息的增长, ...
使用Spark GraphX基于PageRank算法构建一个仿微博用户好友的分布式推荐系统。 注意事项 代码中文件的路径用户可以修改为自己数据所处的位置。 需要启动hadoop集群,这里使用了hadoop2.5.0-cdh5.3.6。 代码执行顺序:...
摘要:随着搜索引擎对网页的排名的需要,以及社交网络的兴起,海量关系所产生的大数据需要得到处理。图计算在数据 关系的分析上发挥着其巨大的潜能。Spark 框架是Hadoop 大数据平台上整合能力强,处理速度快的内存...
实时大数据分析Pagerank 算法 源代码,报告+数据集 根据网页链接数据集“Web-google.txt”,利用“抽税”法计算网页的PageRank排名;
为了提高PageRank算法的计算效率,提出了基于块结构划分的方法,将网页之间的链接关系转换成网络块间的关系,减少了map和reduce操作的调用次数,降低了I/O传输造成的开销,提高计算的效率。实验证明,该方法具有一定...
《Hadoop硬实战》包含: ·Hadoop和MapReduce的基本概念 ·85个实战和测试技术 ·真实的场景,实用的解决方案 ·如何整合MapReduce和R前言 致谢关于本书 第1 部分 背景和基本原理1 跳跃中的Hadoop1.1 什么...
本篇英文论文通过三个具体实例(WordCount Sorted By Key, WordCount Sorted by Values 和 PageRank算法)来对比Hadoop 和 Spark 在大数据应用中运行时间,从而观察这些研究实例随着的迭代计算次数的增加,其时间...
4.2 Hadoop 第五章、你要知道的一些术语 5.1 tf/df/idf 5.2 PageRank 5.3 相似度计算 第六章、搜索引擎是什么玩意 6.1 搜索引擎原理 6.2 搜索引擎架构 6.3 搜索引擎核心模块 6.4 搜索广告
描述了当前突发公共事件中社会认知管理的现状,针对当前...针对传统PageRank算法偏重旧网页的现象,对算法进行了改进,增加了时间权重。在Hadoop分布式计算平台上实现了该算法,并对比分析了算法改进前后的排序结果。