文档章节

PageRank算法并行实现(一)

东方神剑
 东方神剑
发布于 2014/11/26 13:43
字数 958
阅读 252
收藏 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/

共有 人打赏支持
东方神剑

东方神剑

粉丝 65
博文 126
码字总数 93166
作品 0
朝阳
程序员
私信 提问
张尉东/GraphMapReduce

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

张尉东
2016/01/22
0
0
深入探讨PageRank(一):PageRank算法原理入门

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

monkey_d_meng
2011/06/19
0
0
从赌钱游戏看PageRank算法

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

fourinone
2013/03/27
0
19
PageRank算法原理与实现

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

致Great
07/20
0
0
PageRank原理、举例、实现及使用networkX库简单调用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/quiet_girl/article/details/81227904 PageRank是google搜素算法用到的算法思想。关于PageRank的背景网上有很...

nana-li
07/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

window下安装maven

1.下载软件包: 2.解压到当前的安装路径: D:\Maven3.5.3 3.添加环境变量: 新建一个名为:MAVEN_HOME 填写解压路径:D:\Maven3.5.3 打开path,添加:%MAVEN_HOME%\bin 确定即可。 4.验证环境...

狼王黄师傅
9分钟前
0
0
聊聊flink的FsCheckpointStorage

序 本文主要研究一下flink的FsCheckpointStorage CheckpointStorage flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/CheckpointStorage.java /** * CheckpointStor......

go4it
31分钟前
2
0
makefile 常用函数

Linux 环境下的程序员如果不会使用GNU make来构建和管理自己的工程,应该不能算是一个合格的专业程序员,至少不能称得上是 Unix程序员。今天我们来学习下makefile的常用函数。 《GNU make》h...

科陆李明
今天
17
0
Android 报错 Could not find com.android.tools.build:aapt2:3.2.1-4818971.

报错信息: Could not find com.android.tools.build:aapt2:3.2.1-4818971.Searched in the following locations: file:/C:/Users/96110/AppData/Local/Android/Sdk/extras/m2reposito......

lanyu96
今天
9
0
我的Linux系统九阴真经

我的Linux系统九阴真经 在今天,互联网的迅猛发展,科技技术也日新月异,各种编程技术也如雨后春笋一样,冒出尖来了。各种创业公司也百花齐放百家争鸣,特别是针对服务行业,新型互联网服务行...

linuxCool
今天
34
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部