第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
PageRank算法实时大数据实验报告广工（Map Reduce）（附源码）.doc
一、实验内容
二、实验设计（原理分析及流程）
实验报告
学
专
院
计算机学院
业 计算机科学与技术
年级班别
2015 级
学
号
学生姓名
指导教师
毛毛
张
2018 年 05 月
实验课程名称：__实时大数据分析_
实验项目名称
PageRank 算法
专业班级
实 验 者
实验日期
一、实验内容
实验成绩
学
号
1. 采用基于“抽税”法在 MapReduce 框架下，分析图 1 的网页 PageRank 排名；
2
5
1
6
3
4
图 1 Web 链接实例图
2. 图 1 中，若节点②和节点⑤是主题节点，采用面向主题的 PageRank 算法重新计算所有节点
的 PageRank 值。
二、实验设计（原理分析及流程）
1. 原理分析
PageRank 链接分析技术
首先，根据公平原则定义所有网页的初始概率分布向量是一个每维均为 1/n 的 n 维向量 v0；
然后，按照 PageRank 定义，由每个网页的出链数构造网页转移矩阵 M；
最后，依据 M 和 v0 计算多次迭代后的网页概率分布向量 Miv0，其中 i 为多次迭代的次数。
“抽税”PageRank 处理方法
修改 PageRank 计算公式，允许每个随机冲浪者以一个较小的跳转概率随机跳转到一个随
机网页，而不一定要沿着当前网页上的出链前进。
根据前面的 PageRank 估计值 v 和转移矩阵 M，修改后的 PageRank 值 v’的迭代公式为：
v’= βMv + (1-β)e / n，其中，β是抽税参数，1-β表示抽出的税率。
面向主题的 PageRank 技术
假定 S 是一个网页的集合，其中的网页属于类别 S(随机跳转集合)。es 是一个向量，如果
其分量对应的网页属于 S，则该分量置为 1，否则为 0。于是 S 的面向主题的 PageRank 的
迭代公式如下: v’= βMv + (1-β) es / |S|，其中，M 是 Web 的转移矩阵，|S|是集合 S
的大小。
PageRank 算法的 Map-Reduce 实现：
Map 阶段：
对 Web 网页的转移矩阵每一行进行操作，组成该行对应网页的入链键-值对，比如第一行
对应网页 A，则输出为，….
Reduce 阶段：
Reduce 操作收集网页键相同的值，累加并按权重计算，pj = β* ( p1 + p2 + … + pm ) +
(1 - β) * 1/n，其中 m 是链向网页 j 的网页数，n 是所有网页的网页数。
2. 流程
三、实验代码及数据记录
1. 代码
TaxPageRank 类
public class TaxPageRank
{
private static final int N = 6; // 网页数
private static final double β = 4.0 / 5; // 抽税率
private static final double accuracy = 0.0001;// 精度，小于此值迭代结束
private static int m = 0; // 迭代的次数
private static int index = 0; // 网页序号
private static double remainder = 0.0f; // 公式余项
private static ArrayList taxPageRank = new ArrayList(); // 最终
pageRank值
private static ArrayList tmpPageRank = new ArrayList(); // 临时
pageRank值
// 根据网页数，计算公式余项，并初始化pageRank值
private static void initialPageRank()
{
remainder = (1 - β) * (1.0 / N); // (1 - β)e / n
for (int i = 0; i < N; i++)
{
tmpPageRank.add(new Double(1.0 / N));
}
}
// 判断pageRank值是否改变
private static boolean isPageRankChange()
{
boolean isChange = false;
for (int i = 0; i < N; i++)
{
double tax = taxPageRank.get(i).doubleValue();
double tmp = tmpPageRank.get(i).doubleValue();
// 两者差值大于要求的精度，继续迭代
if (Math.abs(tax - tmp) > accuracy)
{
isChange = true;
break;
}
}
return isChange;
}
// 打印迭代过程中的pageRank值
private static void printPageRank()
{
for (int i = 0; i < taxPageRank.size(); i++)
{
System.out.print("网页" + (i + 1) + "的pageRank值：");
System.out.println(taxPageRank.get(i).doubleValue());
}
}
public static class MyMapper extends Mapper
{
@Override
public void map(Object key, Text value, Context context) throws IOException,
InterruptedException
{
String[] matrixItem = value.toString().split("\t");
Text text = new Text();
text.set(String.valueOf(index++));
for (int i = 0; i < N; i++)
{
// 对应行乘列计算，结果作为value值输出
double matrix = Double.parseDouble(matrixItem[i]);
double result = matrix * tmpPageRank.get(i).doubleValue();
context.write(text, new DoubleWritable(result));
}
}
}
public static class MyReducer extends Reducer
{
public void reduce(Text key, Iterable values, Context context)
throws IOException, InterruptedException
{
double sum = 0.0f; // sum = Mv
for (DoubleWritable value : values)
{
sum += value.get();
}
// 计算公式：v’= βMv + (1-β)e/n
double pageRankValue = β * sum + remainder;
taxPageRank.add(new Double(pageRankValue));
context.write(key, new DoubleWritable(pageRankValue));
}
}
public static void main(String[] args) throws Exception
{
Path input = new Path("hdfs://localhost:9000/data/input/transitionMatrix.txt");
Path output = new Path("/data/output/result");
initialPageRank(); // 初始化
while (true) // 循环计算pageRank值
{
Configuration conf = new Configuration();
Job job = Job.getInstance(conf, "pageRank");
job.setJarByClass(TaxPageRank.class);
job.setMapperClass(MyMapper.class);
job.setCombinerClass(MyReducer.class);
job.setReducerClass(MyReducer.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(DoubleWritable.class);
// 自动删除输出文件
FileSystem fs = FileSystem.get(conf);
fs.delete(output, true);
FileInputFormat.addInputPath(job, input);
FileOutputFormat.setOutputPath(job, output);
job.waitForCompletion(true);
System.out.println("第" + (++m) + "次迭代：");
printPageRank();
// 输出迭代的结果
if (!isPageRankChange())
{
break; // pageRank值不变，迭代完成
}
// 网页序号重新置为0
index = 0;
tmpPageRank.clear(); // 清空临时pageRank值
tmpPageRank.addAll(taxPageRank); // 加入最终pageRank值
taxPageRank.clear(); // 清空最终pageRank值
}
}
}
TopicPageRank 类
public class TopicPageRank
{
private static final int N = 6; // 网页数
private static final double β = 4.0 / 5; // 抽税率
private static final double accuracy = 0.0001;// 精度，小于此值迭代结束
private static int m = 0; // 迭代的次数
private static int index = 0; // 网页序号
private static double remainder[] = new double[N]; // 公式余项
private static ArrayList taxPageRank = new ArrayList(); // 最终
pageRank值
private static ArrayList tmpPageRank = new ArrayList(); // 临时
pageRank值
// 根据网页数，计算公式余项，并初始化pageRank值
private static void initialPageRank()
{
for (int i = 0; i < N; i++)
{
// 计算公式余项，是与TaxPageRank的主要区别
if(i == 1 || i == 4)
{
// 网页2、5作为主题节点，公式：(1 - β)es / |S|
remainder[i] = (1 - β) * (1.0 / 2);
}
else
{
}
remainder[i] = 0.0f;
tmpPageRank.add(new Double(1.0 / N));
}
}
// 判断pageRank值是否改变
private static boolean isPageRankChange()
{
boolean isChange = false;
for (int i = 0; i < N; i++)
{
double tax = taxPageRank.get(i).doubleValue();
double tmp = tmpPageRank.get(i).doubleValue();
// 两者差值大于要求的精度，继续迭代
if (Math.abs(tax - tmp) > accuracy)
{
isChange = true;
break;
}
}
return isChange;
}
// 打印迭代过程中的pageRank值
private static void printPageRank()
{
for (int i = 0; i < taxPageRank.size(); i++)
{
System.out.print("网页" + (i + 1) + "的pageRank值：");
System.out.println(taxPageRank.get(i).doubleValue());
}
}
public static class MyMapper extends Mapper
{
@Override
public void map(Object key, Text value, Context context) throws IOException,
InterruptedException
{
String[] matrixItem = value.toString().split("\t");
Text text = new Text();
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
