文档章节

PageRank算法并行实现(一)

东方神剑
 东方神剑
发布于 2014/11/26 13:43
字数 958
阅读 233
收藏 3

pagerank-mapreduce

前言

Google通过PageRank算法模型,实现了对全互联网网页的打分。但对于海量数据的处理,在单机下是不可能实现,所以如何将PageRank并行计算,将是本文的重点。

目录

  1. PageRank算法并行化原理

  2. MapReduce分步式编程

1. PageRank算法分步式原理

pagerank-sample

PageRank的分步式算法原理,简单来讲,就是通过矩阵计算实现并行化。

1). 把邻接矩阵的列,按数据行存储

邻接矩阵

          [,1]   [,2]   [,3]   [,4]
[1,] 0.0375000 0.0375 0.0375 0.0375
[2,] 0.3208333 0.0375 0.0375 0.8875
[3,] 0.3208333 0.4625 0.0375 0.0375
[4,] 0.3208333 0.4625 0.8875 0.0375

按行存储HDFS

1       0.037499994,0.32083333,0.32083333,0.32083333
2       0.037499994,0.037499994,0.4625,0.4625
3       0.037499994,0.037499994,0.037499994,0.88750005
4       0.037499994,0.88750005,0.037499994,0.037499994

2). 迭代:求矩阵特征值

pagerank-mr

map过程:

  • input: 邻接矩阵, pr值

  • output: key为pr的行号,value为邻接矩阵和pr值的乘法求和公式

reduce过程:

  • input: key为pr的行号,value为邻接矩阵和pr值的乘法求和公式

  • output: key为pr的行号, value为计算的结果,即pr值

第1次迭代

0.0375000 0.0375 0.0375 0.0375     1     0.150000
0.3208333 0.0375 0.0375 0.8875  *  1  =  1.283333
0.3208333 0.4625 0.0375 0.0375     1     0.858333
0.3208333 0.4625 0.8875 0.0375     1     1.708333

第2次迭代

0.0375000 0.0375 0.0375 0.0375     0.150000      0.150000
0.3208333 0.0375 0.0375 0.8875  *  1.283333  =   1.6445833
0.3208333 0.4625 0.0375 0.0375     0.858333      0.7379167
0.3208333 0.4625 0.8875 0.0375     1.708333      1.4675000

… 10次迭代

特征值

0.1500000
1.4955721
0.8255034
1.5289245

3). 标准化PR值

0.150000                                              0.0375000
1.4955721  / (0.15+1.4955721+0.8255034+1.5289245) =   0.3738930
0.8255034                                             0.2063759
1.5289245                                             0.3822311

2. MapReduce分步式编程

MapReduce流程分解

PageRankJob

HDFS目录

  • input(/user/hdfs/pagerank): HDFS的根目录

  • input_pr(/user/hdfs/pagerank/pr): 临时目录,存储中间结果PR值

  • tmp1(/user/hdfs/pagerank/tmp1):临时目录,存储邻接矩阵

  • tmp2(/user/hdfs/pagerank/tmp2):临时目录,迭代计算PR值,然后保存到input_pr

  • result(/user/hdfs/pagerank/result): PR值输出结果

  •  

开发步骤:

  • 网页链接关系数据: page.csv

  • 出始的PR数据:pr.csv

  • 邻接矩阵: AdjacencyMatrix.java

  • PageRank计算: PageRank.java

  • PR标准化: Normal.java

  • 启动程序: PageRankJob.java

1). 网页链接关系数据: page.csv

新建文件:page.csv

1,2
1,3
1,4
2,3
2,4
3,4
4,2

2). 出始的PR数据:pr.csv

设置网页的初始值都是1

新建文件:pr.csv

1,1
2,1
3,1
4,1

3). 邻接矩阵: AdjacencyMatrix.java

adjacencyMatrix

矩阵解释:

  • 阻尼系数为0.85

  • 页面数为4

  • reduce以行输出矩阵的列,输出列主要用于分步式存储,下一步需要转成行

新建程序:AdjacencyMatrix.java

package org.conan.myhadoop.pagerank;
import java.io.IOException;
import java.util.Arrays;
import java.util.Map;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapred.JobConf;
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.input.TextInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat;
import org.conan.myhadoop.hdfs.HdfsDAO;
public class AdjacencyMatrix {
    private static int nums = 4;// 页面数
    private static float d = 0.85f;// 阻尼系数
    public static class AdjacencyMatrixMapper extends Mapper<LongWritable, Text, Text, Text> {
        @Override
        public void map(LongWritable key, Text values, Context context) throws IOException, InterruptedException {
            System.out.println(values.toString());
            String[] tokens = PageRankJob.DELIMITER.split(values.toString());
            Text k = new Text(tokens[0]);
            Text v = new Text(tokens[1]);
            context.write(k, v);
        }
    }
    public static class AdjacencyMatrixReducer extends Reducer<Text, Text, Text, Text> {
        @Override
        public void reduce(Text key, Iterable values, Context context) throws IOException, InterruptedException {
            float[] G = new float[nums];// 概率矩阵列
            Arrays.fill(G, (float) (1 - d) / G.length);
            float[] A = new float[nums];// 近邻矩阵列
            int sum = 0;// 链出数量
            for (Text val : values) {
                int idx = Integer.parseInt(val.toString());
                A[idx - 1] = 1;
                sum++;
            }
            if (sum == 0) {// 分母不能为0
                sum = 1;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < A.length; i++) {
                sb.append("," + (float) (G[i] + d * A[i] / sum));
            }
            Text v = new Text(sb.toString().substring(1));
            System.out.println(key + ":" + v.toString());
            context.write(key, v);
        }
    }
    public static void run(Map<String, String> path) throws IOException, InterruptedException, ClassNotFoundException {
        JobConf conf = PageRankJob.config();
        String input = path.get("input");
        String input_pr = path.get("input_pr");
        String output = path.get("tmp1");
        String page = path.get("page");
        String pr = path.get("pr");
        HdfsDAO hdfs = new HdfsDAO(PageRankJob.HDFS, conf);
        hdfs.rmr(input);
        hdfs.mkdirs(input);
        hdfs.mkdirs(input_pr);
        hdfs.copyFile(page, input);
        hdfs.copyFile(pr, input_pr);
        Job job = new Job(conf);
        job.setJarByClass(AdjacencyMatrix.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);
        job.setMapperClass(AdjacencyMatrixMapper.class);
        job.setReducerClass(AdjacencyMatrixReducer.class);
        job.setInputFormatClass(TextInputFormat.class);
        job.setOutputFormatClass(TextOutputFormat.class);
        FileInputFormat.setInputPaths(job, new Path(page));
        FileOutputFormat.setOutputPath(job, new Path(output));
        job.waitForCompletion(true);
    }
}

本文转载自:http://blog.fens.me/algorithm-pagerank-mapreduce/

共有 人打赏支持
东方神剑

东方神剑

粉丝 64
博文 126
码字总数 93166
作品 0
朝阳
程序员
张尉东/GraphMapReduce

#GraphMapReduce: 基于MapReduce编程模型的图计算框架 (名词约束: 顶点Vertex-图中顶点;节点Process-计算单元节点),目录说明: 代码主要包含四个文件: gmr.cpp gmr.h algorithms.h graph.h |g...

张尉东
2016/01/22
0
0
从赌钱游戏看PageRank算法

谈到并行计算应用,会有人想到PageRank算法,我们有成千上万的网页分析链接关系确定排名先后,借助并行计算完成是一个很好的场景。长期以来,google的创始发明PageRank算法吸引了很多人学习研...

fourinone
2013/03/27
0
19
深入探讨PageRank(一):PageRank算法原理入门

深入探讨PageRank(一):PageRank算法原理入门 一、PageRank简介 大名鼎鼎的PageRank算法是Google排名运算法则(排名公式)的一个非常重要的组成部分,其用于衡量一个网站好坏的标准。在揉合...

monkey_d_meng
2011/06/19
0
0
PageRank算法原理与实现

1 PageRank 1.1 简介 PageRank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)...

致Great
07/20
0
0
pagerank 算法 快速入门

背景 pageRank 是Google CEO 拉里佩奇提出的一种算法,来计算互联网里的网站的重要性,以对搜索进行排名。 此处为啥算法叫pagerank,因为是以Google公司创办人拉里·佩奇(Larry Page)之姓来...

yuejiewc
05/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSX | SafariBookmarksSyncAgent意外退出解决方法

1. 启动系统, 按住⌘-R不松手2. 在实用工具(Utilities)下打开终端,输入csrutil disable, 然后回车; 你就看到提示系统完整性保护(SIP: System Integrity Protection)已禁用3. 输入reboot回车...

云迹
今天
4
0
面向对象类之间的关系

面向对象类之间的关系:is-a、has-a、use-a is-a关系也叫继承或泛化,比如大雁和鸟类之间的关系就是继承。 has-a关系称为关联关系,例如企鹅在气候寒冷的地方生活,“企鹅”和“气候”就是关...

gackey
今天
4
0
读书(附电子书)|小狗钱钱之白色的拉布拉多

关注公众号,在公众号中回复“小狗钱钱”可免费获得电子书。 一、背景 之前写了一篇文章 《小狗钱钱》 理财小白应该读的一本书,那时候我才看那本书,现在看了一大半了,发现这本书确实不错,...

tiankonguse
今天
4
0
Permissions 0777 for ‘***’ are too open

异常显示: @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ WARNING: UNPROTECTED PRIVATE KEY FILE! @ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ ......

李玉长
今天
5
0
区块链10年了,还未落地,它失败了吗?

导读 几乎每个人,甚至是对通证持怀疑态度的人,都对区块链的技术有积极的看法,因为它有可能改变世界。然而,区块链技术问世已经10年了,我们仍然没有真正的用上区块链技术。 几乎每个人,甚...

问题终结者
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部