大数据经典算法PageRank讲解.ppt

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

1、PageRank算法一小组：王高翔，李渠，刘晴，柳永康，刘昊骋二小组:王飞，李天照，赵俊杰，陈超，陈瑾翊基本PageRank面向主题PageRankLinkSpam与反作弊导航页与权威页Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.一.Pagerank定义及终点，自连接点的概念早期搜索引擎的弊端Pagerank的定义终止点自连接点1234Evaluationonly.CreatedwithAs

2、pose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.1.早期搜索引擎的弊端不评价早期很多搜索引擎根本不评价结果重要性，而是直接按照某自然顺序（例如时间顺序或编号顺序）返回结果。一旦结果集变大，简直就是一场灾难，这也注定这种方法不可能用于现代的通用搜索引擎基于检索词的评价基于检索词评价的思想非常朴素：检索关键词出现次数越多的页面匹配度越高，而匹配度越高的页面重要性越高词项作弊作弊者可在他网页上增加一个词项，并将该词项重复千百次，搜索引擎可能以为该网页与检索

3、关键词高度相关而把该网页放在搜索结果的前列Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.Pagerank思想：“被越多优质的网页所指的网页，它是优质的概率就越大”2.Pagerank的定义Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.Pag

4、erank是一个函数，它对Web中的每个网页赋予一个实数值。它的意图在于，网页的Pagerank越高，那么它就越“重要”。首先，我们将Web做如下抽象：1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条有向边从A到B。因此，整个Web被抽象为一张有向图。2.Pagerank的定义Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.双击添加标题文字一个N维矩阵，其中i行j列的

5、值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵、对应的转移矩阵如左图Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.设初始时每个页面的rank值为1/N，这里就是1/4。按A-D顺序将页面rank为向量v：第一步之后，冲浪者的概率分布为Mv；第二步之后，冲浪者的概率分布为M²v；第i步之后，依次类推，可得冲浪者经过i步之后的位置概率分布向量为Miv。我们可以从初向量v出发，不断左乘

6、矩阵M，直到前后两轮迭代产生的结果向量差异很小时停止，从而得到M的主特征向量。实际上，对于Web本身而言，迭代50-75次已经足够收敛。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.3.终止点双击添加标题文字一个没有出链的网页称为终止点。这里D页面不存在外链，是一个终止点。由矩阵论的知识可推知，迭代结果将最终归零。那么该如何处理终止点呢？迭代拿掉图中的终止点及终止点相关的边（之所以迭代拿掉是因

7、为当目前的终止点被拿掉后，可能会出现一批新的终止点），直到图中没有终止点。对剩下部分计算rank，然后以拿掉终止点逆向顺序反推终止点的rank值。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.双击添加标题文字4.自连接点如下图，D有外链所以不是终止点，但是它只链向自己（注意链向自己也算外链，当然同时也是个内链）。这种节点叫做自连接点，如果对这个图进行计算，会发现D的rank越来越大趋近于1，而

8、其它节点rank值几乎归零。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5Clien