pagerank 算法 快速入门

pagerank 算法 快速入门pagerank基本思想数量假设:一个页面越被其他页面链接,说明他越重要质量假设:越是被高质量页面链接,说明该页面越重要pagerank模型pagerank模型模拟的是一个用户在互联网上浏览到每个网页的概率。

大家好,欢迎来到IT知识分享网。

pagerank 算法 快速入门

背景

pageRank 是Google CEO 拉里佩奇提出的一种算法,来计算互联网里的网站的重要性,以对搜索进行排名。

此处为啥算法叫pagerank,因为是以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。所以为了出名,大家努力的,发明个算法,以自己名字来命名的。

pagerank 基本思想

  • 数量假设:一个页面越被其他页面链接,说明他越重要(ps:难怪好多技术博客的都互相链接)
  • 质量假设:越是被高质量页面链接,说明该页面越重要(ps:最好能被大博主推荐一波,粉丝蹭蹭蹭往上涨)

pagerank 模型

pagerank 模型模拟的是一个用户在互联网上浏览到每个网页的概率。

下面来一个简单计算,更好的理解下

pagerank 算法 快速入门

pg(A) = pg(C)/1 + pg(B) /2

A网页的pagerank值由网页B和网页C的pagerank贡献而来,因为B网页有两个外链,假设等概率贡献,则贡献给A的值为自身的一半。

再看一个例子

pagerank 算法 快速入门

此处C因为没有外链,所以我们假设他给其他所有网页都贡献了pg,于是:

pg(A) = pg(C)/4 + pg(B) /2

在考虑一个情况,即用户在浏览网页的过程中,直接输入新网址进行浏览,即一个网页都有可能跳转到任意其他网页,于是针对下图:

pagerank 算法 快速入门

pg(A) = (a * pg(B) /2) + (1-a) / 4)

上面公式的含义是:

在任意时刻,用户到达某页面后并继续向后浏览的概率为a,则用户停止浏览的概率为(1-a),此时用户停止浏览后,可能会直接通过输入浏览器地址进行浏览网页,此时跳转到任意网址的概率都一样,于是上面的 a * pg(B) /2 表示从b跳转过来的概率,(1-a) / 4 表示直接输入网址跳转过来的概率。

下面对上面公式进行推广:

pagerank 算法 快速入门

写成矩阵形式:

pagerank 算法 快速入门

上面式子中l(pi,pj)表示网页j指向网页i,其值为:

l(pi,pj) = 1 / L(pj)

其中L(pj)表示pj外链的数量。

计算示例

下面我们来看一个具体的例子,假设有如下图:

pagerank 算法 快速入门

pagerank 算法 快速入门

根据上面的矩阵,我们可以得到下面的矩阵:

pagerank 算法 快速入门

于是整个迭代公式为:

pagerank 算法 快速入门

注意:pagerank如果只考虑从其他网页转移过来,会出现下面的两个问题:

  • 终止点问题:只入不出,则所有节点的概率最后会变为0
  • 陷阱问题:网页只有指向自己的链接,则最后所有的概率都会转移到这些网站

更具体的解释可以看 PageRank算法简介及Map-Reduce实现

map reduce 实现

mapreduce关键在于设计map和reduce,先来看pr值的计算公式:

pagerank 算法 快速入门

所以每个pr值都是由其他网页pr值贡献得到,因此我们还是以下图为例子:

pagerank 算法 快速入门

1. A B C D 2. B A D 3. C 0 4. D B 

现在每一行输入到map中,map输出为:

(B,1/3*pg(A)) (C,1/3*pg(A)) (D,1/3*pg(A)) 

此处我们发现缺少的为每个网页的当前pg值,另外每个网页的pg值是单独存放的,因此我们需要先来一个map-reduce,将pg值映射到每个对应的行,具体流程如下图:

pagerank 算法 快速入门

图片来自:PageRank算法简介及Map-Reduce实现

总结

本文是对pagerank算法的一个简单总结,pagerank主要思想就是模拟互联网用户浏览网页的行为,从而计算出停留在每个网页的概率,关于pg更多的信息可以google的。

你的鼓励是我继续写下去的动力,期待我们共同进步。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/88033.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信