专栏首页算法channel机器学习|PageRank算法原理

机器学习|PageRank算法原理

01

网页排名主要考虑因素

学术界评判学术论文重要性通用方法是看论文的引用次数,原理很多时候都是可以通用的,学术界的思想可以应用到工业界。

google创始人拉里佩奇等将衡量论文重要性的方法应用到了网页的排名上,提出:如果一个网页A被很多其他网页链接到地话,说明网页A比较重要,也就是A的PageRank值会相对较高,意思是有很多其他网页指向这个网页A,也就是说网页A的入度比较大,当然如果链接到网页A的那些网页的PageRank都比较高,那无疑更加表明网页A的PageRank会很高,因为不仅有量,还有质。

02

以此为据,建立图模型

假定一共只有4个网页,是的,一共只有4个网页,现在要求它们的PageRank,我们还知道它们之间的引用关系如下所示:

可以看到网页A被网页B和C都引用了,网页B被网页A和D引用了,网页C被网页A和D引用,网页D被网页A和B引用。

如何求出网页A的PageRank呢?以下PageRank简写为PR

网页A的PR值就可以表示为:PR(A) = PR(B)+PR(C),这个公式是能准确地刻画出网页A的PR吗,假象你现在正在读网页B,文章末尾有两个链接,分别指向网页A和D,此时,你进入网页A的概率是0.5,如果你在网页C,那么此时你点到链接A的概率是1.0,所以PR(A) = 0.5PR(B)+1.0*PR(C),我们已经往前走了一步,但是这不是终点,为什么?

我们在浏览B网页的时候,读到文章末尾后,虽然给出了两个链接,但是你可能是一个比较另辟蹊径的人,根本不关心给出的链接,直接在地址栏中输入其他网址,直接到C网页了。

这的确是个问题,怎么解决呢?

03

意外之喜

当你停留在B网页时,你可能没有点击里面的两个链接,这个的意思是我们要对PR(B)的系数0.5做一个惩罚,比如乘以一个惩罚系数0.85,这样PR(A)=0.85*0.5*PR(B)+0.85*1.0*PR(C),既然你没有通过两个内部链接找到A,但是在世界的另一个角,一个叔叔直接在地址栏输入了一个网址,直接找到了网页A,这对A来讲,是意外之喜,所以PR(A)还要考虑这个因素,进一步修正PR(A)为,

PR(A)=0.85 * 0.5 * PR(B) + 0.85 *1.0 * PR(C) +(1-0.85) / 4

其中,4是网页的总个数

04

将公式抽象

上面这个公式,其实就是最终的求某个网页PR的公式了,只不过总网页的个数为4个,还假定了4个网页的链接关系,为了不失一般性,据此,推理出一般性的公式:

其中,

Mpi描述了指向网页Pi的所有网页集合,L(Pj)是网页Pj的出链数目,N是网页的总数,a是惩罚因子,一般取值为0.85.

根据上面的公式,我们可以计算每个网页的PR值,在不断迭代趋于平稳的时候,即为最终结果,关于算法的Map-Reduce实现代码,请看接下来推送。

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-01-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3分钟理解 支持向量机中最出神的第一笔

    之前推送过SVM,今天,又有了更容易理解SVM的目标函数和约束怎么得来的思路,因此,记录下来,与大家一起分享。

    double
  • 自然语言处理|语言模型介绍

    01 — 回顾 昨天说到自然语言处理中如何将词语转化为词向量,主要用 Distributed Representation 思想,比如谷歌的word2vec就是...

    double
  • 送6本精选的算法,机器学习,深度学习的书

    1Discrete Mathematics and Its Applications 7th ? 计算机只能懂得离散(甚至是有限的语言),所以离散数学在当今的作...

    double
  • 什么是静态和动态网页?

    杨逸轩
  • 静态网页VS动态网页

    在做《牛腩新闻发布系统》的时候,建立的网页有.html的,还有.aspx,刚开始接触,还以为这些东西是一样的呢,当看ASP.NET视频的时候,听见里面讲课的老...

    令仔很忙
  • 全球主要城市实时天气查询

    作为学习javascript的练习,我制作了一个网页,可以查询全球主要城市此时此刻的天气,请点击进入。

    ruanyf
  • 6款超级提高效率的chrome插件

    是一款网页标签插件,我们通常会因为工作需要,去浏览大量的网页,结果是,打开的网页越来越多,又不敢轻易关掉,害怕再也找不回来。 One Tab可以让你把网页瞬间集...

    沉默的白面书生
  • 数据挖掘PageRank算法(网页排名原理)及Map-Reduce实现

    方法/步骤 1 一、什么是pagerank PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google...

    学到老
  • 关于网页设计的一些统计数字

    ● 2003年,全世界网页的平均大小是93.7KB,2008年增长到312KB,5年中翻了3.3倍。(这里的网页大小包括图片、CSS文件、Javascript文...

    ruanyf
  • 智能算法——PageRank

    PageRank,即网页排名算法,又称为网页级别算法,是由佩奇和布林在1997年提出来的链接分析算法。PageRank是用来标识网页的等级、重要性的一种方法...

    zhaozhiyong

扫码关注云+社区

领取腾讯云代金券