hadoop上跑一下网页排名算法之PageRank算法

????????? 也许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>,每个网页得到的贡献值。

??????? 代码：

?Reduce阶段：
????????? 分析：这个阶段操作就相对简单很多，读取map的输出<key,value>，并解析出来。
??????? ? 具体操作：如果value中首字母是“@”表示是贡献值，如果是“&”表示是链接情况。
?
??? main函数:
?
?
?
?
?
context.write(next_id, t);
Text tt = new Text("&" + nextId);
context.write(id, tt);

k2: 被某一指向的页面（暂且说是p）  v2: p从这个指出的页面得到的部分PR值

不知道这样对不对 ，帮解释下呗context.write(next_id, t);
Text tt = new Text("&" + nextId);
context.write(id, tt);

k2: 被某一指向的页面（暂且说是p）  v2: p从这个指出的页面得到的部分PR值

不知道这样对不对 ，帮解释下呗

我觉得有道理，map确实有问题。