1. Chine King
  2. PageRank

Wiki

Clone wiki

PageRank / Home

介绍

海量数据分析(Massive Data Processing)课程实验。主要用hadoop分析wiki语料,并用PageRank算法得出各页面的PR值。

说明

实验所使用的wiki语料默认放在HDFS下的“/wiki/in”中。运行的结果在“/wiki/result“中。

原理

PageRank的具体算法不再赘述。主要通过以下公式来进行计算(具体可以查看这篇paper的section2.1.1):

PR(A) = (1-d) / N + d( PR(B) / Cout(B) + … + PR(C) / Cout(C) )

步骤分为以下几步:

  1. 解析原始数据
  2. 计算PR值,并进行迭代
  3. 输出结果

解析原始数据

输入集为一系列的文本文件。每一行为一个wiki页面。页面链接通常用两个方括号表示(但并不是所有都满足)。每一行同时包含该维基文件的名字,包含在在HTML标签块“<title></title>”中(在实际情况中,符号“<”和“>”进行了转义,所以实际包含在“&lttitle&gt”和“&lt/title&gt”中)。在解析原始数据的任务中,我们主要是输出一个页面的所有链接,并进行初始化。解析原始数据由包com.chine.pagerank.mapreduce.parseoriginaldata进行。

Map任务

Map任务非常简单,我们简单得解析每一行的文件,并以该文件名作为key,该文件中的链接作为value输出。结果比如:

key  value

doc1 doc2
doc1 doc3
...
docN docM

Reduce任务

在Reduce任务中,我们将文件中的链接(iterable)进行整合,并初始化该文件的PR值为1.0,默认输出到“/wiki/iter00”中。结果比如:

key  value

doc1 1.0\tdoc2,doc3
doc2 1.0\t...
...
docN ...

计算PR值,并进行迭代

这个步骤初始运行,以“解析原始数据”步骤的输出作为输入。为了保持迭代的连续性,所以,每次计算完PR值的输出数据应该有着同样的格式,以保证能作为下次迭代的输入数据。这个任务由包com.chine.pagerank.mapreduce.calpagerank进行。

Map任务

对于每一行输入,key为文件名,value为PR值以及每个链接的名字,我们将每个链接作为key,该文件名、文件的PR值、文件的总链接数作为value输出。如有以下输入:

key  value

doc1 1.0\tdoc2,doc3
doc2 1.0\t...
...
docN ...

输出如下:

key  value
doc2 doc1\t\1.0\t2
...

值得注意的是,由于不是每个链接都在初始的输入集中存在,所以,我们在Map任务中对于每个key输出一个value值为“!”。这样在接下来的reduce中,对于一个key,它的values中如果不存在“!”,则说明该链接并不存在,所以在reduce中也就不进行计算。

Reduce任务

利用以上的Map结果,我们利用每个key对应的一系列链接的PR值来进行计算。

输出结果

利用迭代的结果,我们只需将value中的PR值作为key,文件名(输入key)作为value输出。结果按照从大到小进行排列。这个过程由包com.chine.pagerank.mapreduce.pagerankresult进行。这里覆写了FloatWritable类,以支持结果从大到小排列。

运行

下载PageRank4.jar。并运行:

hadoop jar PageRank4.jar

支持的选项

  • wiki.in:输入集在HDFS中位置。默认为“/wiki/in”。
  • wiki.iter:迭代过程数据所存放的文件夹。运行时会根据正在迭代的次数来设置。默认为“/wiki/ranking/iter”,如运行第一次迭代时,输出为“/wiki/ranking/iter01”。
  • wiki.out:最终输出集所在文件位置。
  • wiki.iter.count:迭代的次数。

运行时在命令行后用“-D”进行参数设置。如:

hadoop jar PageRank4.jar -D wiki.in=/wiki/in

获得源码

$ hg clone https://bitbucket.org/chineking/pagerank

Updated