Google矩阵

标签: Algorithm Google 矩阵 | 发表时间:2013-04-03 00:35 | 作者:四火
出处:http://www.raychase.net

文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》

Google矩阵 使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,Google为它最核心的排序算法PageRank申请了专利。在PageRank以前,排序大多依靠对搜索关键字和目标页的匹配度来进行的,这种排序方式弊端明显,尤其对于善于堆砌关键字舞弊的页面,很容易就跳到了搜索结果的首页。Larry Page和Sergey Brin开始着手解决这个问题,Google排序的继承来自于互联网上网页之间的链接关系。一张网页被其它网页引用的次数越多,可以简单地认为这样的网页越受欢迎,当然在结果列表中应该越靠前。

前面提到了目标网页被引用网页的“数量”,另一条重要的判定PageRank级别的依据则是“质量”。换言之,质量高的网页所引用的网页,质量往往也比较高,所以质量高的网页投票所占权重理应更高。

在用户访问某一张网页时,假设他有q的概率去点击网页上的链接,并且点击该网页每条链接的概率都是相等的。如果该网页有n条链接的话,那么点击每条链接的概率就是1/n。

在表现网页之间链接关系时,Google使用了矩阵。假设互联网上共有N个页面,那么我们可以写出一个N×N的矩阵,其中的元素p ij,如果存在从页i被页j指向的链接(为什么使用“被指向”而非“指向”,前文已经解释了),那么p ij就大于0,反之就等于0。同时,每一列元素的取值都除以链接数n(前文提到了),使得各列矢量总和成为1,行矢量则表示了各个状态之间的迁移概率,这个最大特征值为1的矩阵就成为了PageRank矩阵。

现在给出N为4的一个例子(共有A、B、C、D四张网页)帮助说明这个矩阵(这个例子来自于 这篇文章):

  Google矩阵

可以看到矩阵L的几个非零元素的取值:

  • p 13=1; 表示被A指向的只有C
  • p 12=1; 表示被B指向的只有A
  • p 13=p 43=1/2; 表示被C指向的有A和D
  • p 14=p 24=p 34=1/3; 表示被D指向的有A、B、C

于是,对于A来说,它的PageRank取值就可以表示为:

PR(A) = PR(B)/1 + PR(C)/2 + PR(D)/3

但这是在用户百分之百点击网页链接的情况下发生的,实际上,只有p概率的用户会点击网页链接,剩下(1-p)概率的用户会跳到无关的页面上去,而访问的页面恰好是4这个页面中A的概率只有(1-p)/4(p正是前文提到的“阻尼系数”(damping factor),Google取p等于0.85),所以:

PR(A) = (1-p)/4 + p(PR(B)/1 + PR(C)/2 + PR(D)/3)

推广到一般公式(p i表示第i张网页,L(p j)表示从p i链出网页的数量):

Google矩阵

有了PageRank(p i)的概念以后,PageRank矩阵就可以用一个特征向量来表示:

Google矩阵

由上述两个公式,可以得到(其中l(p i,p j)就是前文提到过的p i j):

Google矩阵 

以上未特殊注明的公式截图来自于维基百科。

截止到2010年,Google索引的网页总数已经超过5000亿,也就是说,Google必须解这个阶数的特征向量,这个过程我不得而知,但这是不是真的就是MapReduce之类的由来呢?

文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》

分享到:
你可能也喜欢:

相关 [google 矩阵] 推荐:

Google矩阵

- - 四火的唠叨
文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》. 使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,Google为它最核心的排序算法PageRank申请了专利. 在PageRank以前,排序大多依靠对搜索关键字和目标页的匹配度来进行的,这种排序方式弊端明显,尤其对于善于堆砌关键字舞弊的页面,很容易就跳到了搜索结果的首页.

矩阵分解的Jungle

- SuperLucky - 增强视觉 | 计算机视觉 增强现实
美帝的法国貌似是美法混血的有心人士(此有心人士长期从事航天飞机研究. )收集了市面上的矩阵分解的几乎所有算法和应用,由于源地址在某神秘物质之外,特转载过来,源地址. Matrix Decompositions has a long history and generally centers around a set of known factorizations such as LU, QR, SVD and eigendecompositions.

需求跟踪矩阵的作用

- - 非技术 - ITeye博客
  如果建立了需求跟踪矩阵,我们对照需求跟踪矩阵的进行测试用例的评审,则会更加方便,如果建立了需求跟踪矩阵,作者本人很容易在评审之前就会很容易发现未被测试用例覆盖的需求.         需求跟踪矩阵的作用有两个:  一是检查需求是否被实现了,是否被测试了,执行需求的验证,进行功能审计;二是在发生需求变更时,通过检索需求跟踪矩阵发现需要修改的需求、设计及测试用例等.

推荐算法之矩阵分解

- - 标点符
推荐领域的人一般都会听说过十年前 Netflix Prize 的比赛,随着Netflix Prize推荐比赛的成功举办,近年来隐语义模型(Latent Factor MOdel,LFM)受到越来越多的关注. 隐语义模型最早在文本挖掘领域被提出,用于寻找文本的隐含语义,相关的模型常见的有潜在语义分析(Latent Semantic Analysis,LSA)、LDA(Latent Dirichlet Allocation)的主题模型(Topic Model)、矩阵分解(Matrix Factorization)等等.

Geek的生日聚会游戏:藏在矩阵中的年龄

- 夲 - 果壳网 guokr.com - 果壳网
在生日聚会上玩什么游戏最好呢. 不过 Geek 们有自己的选择. 设想《生活大爆炸》里的 Leonard、Sheldon、Howard、Rajesh 聚在一起,庆祝其中一人 25 岁的生日. Sheldon 在一张纸上写下了下面这个 4×4 的数字方阵:. 然后从 Leonard 开始,每个人从中任选一个数字画上圈,同时把这个数字所在的那一行和那一列的其它数字都划掉.

矩阵分解在推荐系统中的应用(转)

- -
本文将简单介绍下最近学习到的矩阵分解方法. 开始觉得这种方法很神奇很数学,而且在实际使用的时候也非常好用. 但最近读了Yehuda大神的paper之后,觉得这种方法比较猥琐. 其实,矩阵分解的核心是将一个非常稀疏的评分矩阵分解为两个矩阵,一个表示user的特性,一个表示item的特性,将两个矩阵中各取一行和一列向量做内积就可以得到对应评分.

基于矩阵分解的推荐算法,简单入门 - kobeshow

- - 博客园_首页
       本文将要讨论基于矩阵分解的推荐算法,这一类型的算法通常会有很高的预测精度,也活跃于各大推荐系统竞赛上面,前段时间的百度电影推荐最终结果的前10名貌似都是把矩阵分解作为一个单模型,最后各种ensemble,不知道正在进行的阿里推荐比赛( http://102.alibaba.com/competition/addDiscovery/index.htm),会不会惊喜出现.

不同编程语言之间转换的项目矩阵

- - 博客园_新闻
最近流行跨界,不同编程语言之间喜欢通过一些开源项目来实现相互调用、转换. 同时也有一些项目可实现语言之间的集成,例如 JRuby 可让你在 Java 应用中执行 Ruby 脚本. 而这里有一个网站给出了一个完整的不同编程语言之间的转换矩阵,通过这个矩阵你可以了解到两个语言需要使用什么工具可以进行转换.

基于MapReduce的ItemBase推荐算法的共现矩阵实现

- -
    这2个月研究根据用户标签情况对用户的相似度进行评估,其中涉及一些推荐算法知识,在这段时间研究了一遍《推荐算法实践》和《Mahout in action》,在这里主要是根据这两本书的一些思想和自己的一些理解对分布式基于ItemBase的推荐算法进行实现. 其中分两部分,第一部分是根据共现矩阵的方式来简单的推算出用户的推荐项,第二部分则是通过传统的相似度矩阵的方法来实践ItemBase推荐算法.

你不可不知的社会化营销战略矩阵10字法则

- 瑾 - 互联网的那点事...
最近明显的感觉派代上关于微博营销的帖子多了,虽然自己也发了些关于微博营销的帖子,知道很多人对微博的重视,之前也写过《不懂社会化媒体营销,传统电商已失败一半》,总有一种难受的感觉,许多人对于微博,对于社会化营销就产生以下疑问:. 1、微博就是社会化营销的全部,难道其他渠道都不用了吗. 2、社会化营销这么厉害,是电商的救命稻草,那服务和产品算什么.