pagerank 算法.ppt

基于MapReduce的PageRank算法
2
主要内容
Pagerank 算法的简介。
Hadoop-MapReduce 框架介绍
Hadoop-MapReduce 下的 PageRank算法
3
Pagerank 算法的简介
算法的思想
算法的不足与改进
4
主要思想:
PageRank 形如投票系统一样,一个链接结构从网页 x指向另一网页y,则y得票一次。PageRank 的 PR 值不仅跟自己得票相关,而且跟向自己投票的网页也相关,x向y投票,x重要就代表 y 更重要。
PageRank 算法描述如下:
( 1) PR 值具有传递性。x指向y时,x的PR值也部分传递给y。
( 2) 重要性具有传递性,一个重要的网页比一个不重要网页传递的权威更多.
当考虑一个页面的所有入度和出度时,页面 Z 的PageRank 值计算公下:
PR(Z)=(1-D)+D×∑PR(a)/Na ( a∈A(Z) )
其中 A(Z)代表有链接直接指向页面Z的网页集,即页面Z的度;PR(Z)代表页面Z的PageRank数值; Na表示网页a正向链接数量;PR(a)/Na表示网页a 将自己的 PageRank 值平均分配给自身的正向链接;
D 是阻尼系数,0 < D < 1,通常取 0. 85,由于用户在行网页浏览时不可能按当前页面中的链接前进,而是随机跳跃完全无关页面,则 D 实际上代表的是用户跟随网页链接浏览,不产生随机跳跃的概率值。加入阻尼系数 D 是能保证 PageRank算法总是收敛的。
5
主要优点:
PageRank算法通过网页间的链接来评价网页的重要性,在一定程度上避免和减少了人为因素对排序结果的影响;采用与查询无关的离线计算方式,使其具有较高的响应速度;一个网页只能通过别的网页对其引用来增加自身的PR值,且算法的均分策略使得一个网页的引用越多,被引用网页所获得的PR值就越少。因此,算法可以有效避免那些为了提高网站的搜索排名而故意使用链接的行为。
6
主要缺点:
算法在Google搜索引擎的成功运用,说明其是高效、可行的。但由于完全基于链接分析,且链接信息相对静态,没有考虑网页使用的动态信息,因此算法还存在一些缺陷,主要可归纳为:
(1)主题漂移问题
PageRank算法仅利用网络的链接结构,无法判断网页内
容上的相似性;且算法根据向外链接平均分配权值使得主题
不相关的网页获得与主题相关的网页同样的重视度,出现主
题漂移。
7
(2)偏重旧网页问题
决定网页PR值的主要因素是指向它的链接个数的多少。一个含有重要价值的新网页,可能因为链接数目的限制很难出现在搜索结果的前面,而不能获得与实际价值相符的排名。算法并不一定能反映网页的重要性,存在偏重旧网页现象。
(3)忽视用户个性化问题
PageRank算法在设计之初,没有考虑用户的个性化需要。个性化搜索引擎的兴起,对PageRank排序算法提出新的挑战。
8
Hadoop-MapReduce 框架介绍
MapReduce是一个用于大规模数据处理的分布式计算模型。当用户定义一个 Map 函数来处理一个key / value 对然后生成一批中间的 key / value 对再定义一个 Reduce 函数将所有这些中间的有相同 key 的values 合并起来。现实生活中有很多这种模型,Hadoop 的 Map / Reduce 框架也是基于这个原理实现。一个 MapReduce 任务,在运行程序之前,必须保证 Master节点的 NameNode,SecondaryNameNode,JobTracker 等进程和 Slaves 节点的 DataNode,TaskTracker等进程启动,JobTracker 进程和 TaskTracker 进程分别运行在 Master 和 Slaves 上。MapReduce 首先将作业通过JobClient 提交作业给 Master 的 JobTracker,接着 JobTracker 将作业放在等待队列中。Slaves 节点的TaskTracker 随机地通过远程过程调用( RPC) 发送询问信息,询问是否有作业任务安排。
9
若有,JobTracker 分派任务作业给 TaskTracker,TaskTracker 再分配具体的物理节点机执行任务。Master/Slave 是一种 Slave 主动询问、Master 被动答复的过程。整个过程分为三步: JobClient 提交作业任务、Job-Tracker 调度作业任务TaskTracker 分配具体节点机运行作业。
(1) JobClient 提交作业任务: 当用户在提交作业时,JobClient 会调用静态方法 runJob 实例化一个