大数据经典算法pagerank讲解

《大数据经典算法pagerank讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PageRank算法一小组：王高翔，李渠，刘晴，柳永康，刘昊骋二小组:王飞，李天照，赵俊杰，陈超，陈瑾翊基本PageRank面向主题PageRankLinkSpam与反作弊导航页与权威页一.Pagerank定义及终点，自连接点的概念早期搜索引擎的弊端Pagerank的定义终止点自连接点12341.早期搜索引擎的弊端不评价早期很多搜索引擎根本不评价结果重要性，而是直接按照某自然顺序（例如时间顺序或编号顺序）返回结果。一旦结果集变大，简直就是一场灾难，这也注定这种方法不可能用于现代的通用搜索引擎基于

2、检索词的评价基于检索词评价的思想非常朴素：检索关键词出现次数越多的页面匹配度越高，而匹配度越高的页面重要性越高词项作弊作弊者可在他网页上增加一个词项，并将该词项重复千百次，搜索引擎可能以为该网页与检索关键词高度相关而把该网页放在搜索结果的前列Pagerank思想：“被越多优质的网页所指的网页，它是优质的概率就越大”2.Pagerank的定义Pagerank是一个函数，它对Web中的每个网页赋予一个实数值。它的意图在于，网页的Pagerank越高，那么它就越“重要”。首先，我们将Web做如下抽象：

3、1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条有向边从A到B。因此，整个Web被抽象为一张有向图。2.Pagerank的定义双击添加标题文字一个N维矩阵，其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵、对应的转移矩阵如左图设初始时每个页面的rank值为1/N，这里就是1/4。按A-D顺序将页面rank为向量v：第一步之后，冲浪者的概率分布为Mv；第二步之后，冲浪者的概率分布为M²v；第i步之后，依次类推，可得冲浪者经过i步之后的位置概率分

4、布向量为Miv。我们可以从初向量v出发，不断左乘矩阵M，直到前后两轮迭代产生的结果向量差异很小时停止，从而得到M的主特征向量。实际上，对于Web本身而言，迭代50-75次已经足够收敛。3.终止点双击添加标题文字一个没有出链的网页称为终止点。这里D页面不存在外链，是一个终止点。由矩阵论的知识可推知，迭代结果将最终归零。那么该如何处理终止点呢？迭代拿掉图中的终止点及终止点相关的边（之所以迭代拿掉是因为当目前的终止点被拿掉后，可能会出现一批新的终止点），直到图中没有终止点。对剩下部分计算rank，然后

5、以拿掉终止点逆向顺序反推终止点的rank值。双击添加标题文字4.自连接点如下图，D有外链所以不是终止点，但是它只链向自己（注意链向自己也算外链，当然同时也是个内链）。这种节点叫做自连接点，如果对这个图进行计算，会发现D的rank越来越大趋近于1，而其它节点rank值几乎归零。单击添加击添加为了克服这种问题，需要对PageRank计算方法进行一个平滑处理，具体做法是加入“跳转因子（teleporting）”。所谓跳转因子，就是我们认为在任何一个页面浏览的用户都有可能以一个极小的概率瞬间转移到另外一

6、个随机页面。当然，这两个页面可能不存在超链接，因此不可能真的直接转移过去，跳转因子只是为了算法需要而强加的一种纯数学意义的概率数字。单击此处添加段落文字内容其中β往往被设置为一个比较小的参数（0.2或更小），e为N维单位向量，加入e的原因是这个公式的前半部分是向量，因此必须将β/N转为向量才能相加。这样，整个计算就变得平滑，因为每次迭代的结果除了依赖转移矩阵外，还依赖一个小概率的心灵转移。如果按这个公式迭代算下去，会发现自连接点的问题解决了，从而每个页面都拥有一个合理的pagerank。单击此处

7、添加段落文字内容分块式Pagerank算法：原来的算法存在的问题：1.时间开销大。每次迭代就算时间开销为2.因特网中数据大部分是分布式的，计算过程需要多次传递数据，网络负担太大。3.n维矩阵式一个稀疏矩阵，无论计算还是存储都很浪费资源。能否考虑先算出局部的Pagerank值？？单击此处添加段落文字内容分块式Pagerank算法：1.分数据块，计算每一个网络图G[i]的的LocalPagerank。算法实现步骤：2.根据各数据块之间的相关性，计算缩略图p的Blockrank。3.将所得LocalP

8、agerank和Blockrank按照一定原则进行计算，得到一个新的n维Pagerank.4.将n维Pagerank多次迭代，得到最后收敛的pagerank向量。面向主题PageRank动机不同的人有不同的兴趣，而有时完全不同的兴趣却采用相同的查询词项来表达。如果搜索引擎能够推断出用户的兴趣，那么在返回相关页面的时候会表现得更好比如用户搜索"苹果"理想情况实际情况做法做法每个用户有一个私人的PageRank向量对每一个主题方向建立偏向该主题的一个PageRank向量OpenDirectory(D