谷歌怎样给搜索结果排序

标签: 谷歌 搜索 结果 | 发表时间:2011-09-28 15:13 | 作者:(author unknown) lf
出处:http://www.feedzshare.com

来自: www.guokr.com - FeedzShare  
发布时间:2011年09月27日,  已有 2 人推荐


9 月 27 日谷歌推出新款doodle,庆祝自己 13 岁生日。在这个世界上,谷歌几乎无人不晓了。但鲜为人知的是,在13年前,拉里•佩奇( Larry Page )和谢尔盖•布林( Sergey Brin )正是依靠先进的算法发家并创立谷歌的。在这个世界上最自由和创新公司的生日里,来听听死理性派讲述它当年的数学故事吧。

/gkimage/mr/1i/8j/mr1i8j.png

网页排名和谷歌算法的诞生

一个正常的搜索引擎,其核心功能自然是网页搜索。那搜索结果应该怎样排序才最好呢?实际上,在谷歌主导互联网搜索之前,人们为此伤透脑筋。

当时人们认为,通过判断能够得知哪个网页更重要,对搜索引擎的发展十分有帮助——很显然,搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。

这个问题看起来很容易,但是解决的方法却没有想象的那么简单。

在谷歌诞生之前那段时间,流行的网页排名算法都很类似,它们都使用了一个非常简单的思想:越是重要的网页,访问量就会越大。许多大公司就通过统计网页的访问量来进行网页排名。但是这种排名算法有两个很显著的问题:一是因为只能够抽样统计,所以统计数据不一定准确,而且访问量的波动会比较大,想要得到准确的统计需要大量的时间和人力,还只能维持很短的有效时间;二是访问量并不一定能体现网页的“重要程度”——可能一些比较早接触互联网的网民还记得,那时有很多人推出了专门“刷访问量”的服务。有没有更好的方法,不统计访问量就能够为网页的重要度排序呢?

就是在这种情况下,1996 年初,谷歌公司的创始人,当时还是美国斯坦福大学研究生的佩奇和布林开始了对网页排序问题的研究。在1999年,一篇以佩奇为第一作者的论文发表了,论文中介绍了一种叫做 PageRank 的算法,这种算法的主要思想是:越“重要”的网页,页面上的链接质量也越高,同时越容易被其它“重要”的网页链接。于是,算法完全利用网页之间互相链接的关系来计算网页的重要程度,将网页排序彻底变成一个数学问题,终于摆脱了访问量统计的框框。

三个孩子和豌豆游戏

在详细讲述这个算法之前,不妨让我们用一个游戏,先来简单模拟一下 PageRank 算法的运行过程,以便读者更好地理解。

三兄弟分 30 颗豌豆。起初每人 10 颗,他们每次都要把手里的豌豆全部平均分给自己喜欢的人。下图表示了三兄弟各自拥有的初始豌豆数量,以及相互喜欢的关系(箭头方向表示喜欢,例如老二喜欢老大,老大喜欢老二和老三)。

/gkimage/iu/xv/em/iuxvem.png

第一次分配后,我们会得到结果如下:

/gkimage/t4/hz/ez/t4hzez.png

就这样,让游戏一直进行下去。直到他们手中的豌豆数不再变化为止。

那么这个游戏到底是否可以结束呢,如果可以,最终的结果又是什么样的?在此我们用电脑模拟了这个过程,得出的结果是:老大和老二的盘子里各有 12 颗豌豆,而老三的盘子里有 6 颗豌豆。这时候无论游戏怎么进行下去,盘子里的豌豆数量都不会再变化。

看到这里,读者可能会问:这个游戏和网页排序有什么关系?实际上, PageRank 会给每个网页一个数值,这个数值越高,就说明这个网页越“重要”。而刚刚的游戏中,如果把豌豆的数量看作这个数值(可以不是整数),把孩子们看作网页,那么游戏的过程就是 PageRank 的算法,而游戏结束时豌豆的分配,就是网页的 PageRank 值。

PageRank的数学模型

不同于之前的访问量统计,PageRank 求解了这样一个问题:一个人在网络上浏览网页,每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页 x 已经确定,那么网页 x 上每个链接被点击的概率也是确定的,可以用向量 Nx 表示。在这种条件下,这个人点击了无限多次链接后,恰好停留在每个网页上的概率分别是多少?

在这个模型中,我们用向量 Ri 来表示点击了 i 次链接之后可能停留在每个网页上的概率( R 0 则为一开始就打开了每个网页的概率,后面我们将证明 R 0 的取值对最终结果没有影响)。很显然 R i 的 L1 范式为 1 ,这也是 PageRank 算法本身的要求。

仍以上面的游戏为例,整个浏览过程的一开始,我们有:

/gkimage/u6/0y/sy/u60ysy.png

其中, A 表示每一次点击链接概率的矩阵。 A 的第 i 列第 j 行 A i, j 的含义是,如果当前访问的网页是网页i,那么下一次点击链接跳转到网页 j 的概率为 A i, j

这样设计矩阵 A 的好处是,通过矩阵 A 和向量 R n-1 相乘,即可得出点击一次链接后每个网页可能的停留概率向量 R n 。例如,令 R 1 = A R 0 ,可以得到点击一次链接后停留在每个网页的概率:

/gkimage/lz/6j/1c/lz6j1c.png

之后一直迭代下去,有:

/gkimage/nj/xh/be/njxhbe.png

对于上面的例子,迭代结果如下图:

/gkimage/cx/gf/ag/cxgfag.png

可以看到,每个网页停留的概率在振荡之后趋于稳定。

在这种稳定状态下,我们可以知道,无论如何迭代,都有 R n = R n-1 。这样我们就获得了一个方程:

/gkimage/tg/s5/vb/tgs5vb.png

而整个迭代的过程,就是在寻求方程 R = AR 的解。而无论 R 0 是多少,迭代无限多次之后,一定会取得令 R = AR 成立的 R 值。整个求解 R 的过程,就如同一个人在一张地图上的不同位置之间随机地行走一样,所以被称为“随机行走模型”。

随机行走模型有一个显著的特点,那就是每一次迭代的结果只与前一次有关,与更早的结果完全无关。这种过程又被称为马尔可夫过程( Markov Process )或马尔可夫链( Markov Chain )。

马尔可夫过程的数学定义是:如果对于一个随机变量序列 X 0 、 X 1 、 X 2 、…, 其中 X n 表示时间 n 的状态及转移概率P,有:

/gkimage/lg/q7/bf/lgq7bf.png

即 X n 只受 X n-1 的影响,则此过程成为马尔可夫过程。其中 P( X n+1 | X n ) 称作“一步转移概率”,而两步、三步转移概率则可以通过一步转移概率的积分求得。

当状态空间有限时,转移概率可以用用一个矩阵 A 来表示,称作转移矩阵( transition matrix )。此时转移概率的积分即为矩阵的幂,k步转移概率可以用 A k 表示,这也是随机行走模型中的情况。而对于一个正的(每个元素都为正的)转移矩阵 A ,可以证明一定有:

/gkimage/ua/wx/rz/uawxrz.png

这就完整解释了为什么 R 0 的取值对最终结果没有影响。

修正“悬挂网页”带来的不良影响

但是这里有一个问题:即便 R 0 的取值对最终结果没有影响,用 R 作为网页排序的依据是否真的合理?

其实并不合理,因为当一个网页只有链入链接没有链出链接的时候,这个网页就会像一个“黑洞”一样,将同一个连通子图中其它网页流向它的 PageRank 慢慢“吞掉”(因为算法中虚拟的用户一旦进入那样的网页, 就会由于没有对外链接而永远停留在那里),这种网页我们称之为“悬挂网页”( Dangling Link )。这种“黑洞”效应是如此显著, 以至于在一个连通性良好的互联网上, 哪怕只有一个 “悬挂网页”, 也足以使整个互联网的网页排序失效, 可谓是 “一粒老鼠屎坏了一锅粥”。

为了解决这个问题,佩奇和布林进行了修正。他们意识到, 当用户访问到 “悬挂网页” 时, 都不可能也不应该就停留在了这个页面, 而是会自行访问其它网页。虽然对每个用户来说, 自行访问的网页与各人的兴趣有关,但在平均意义上来讲,佩奇和布林假定用户将会在整个互联网上随机选取一个网页进行访问。

所以他们给 PageRank 算法加入了一个新的向量 E。它的作用是,按照其中所描述的比例来向全部网页分配悬挂网页每一次“吞掉”的 PageRank。这样,相当于为悬挂网页添加了链向网络上全部网页的链接,避免了悬挂链接的出现。

以上就是谷歌背后最重要的数学奥秘。 与以往那种凭借关键词出现次数所作的排序不同, 这种由所有网页的相互链接所确定的排序是不那么容易做假的, 因为做假者再是把自己的网页吹得天花乱坠, 如果没有真正吸引人的内容, 别人不链接它, 一切就还是枉然。 而且 “佩奇排序” 还有一个重要特点, 那就是它只与互联网的结构有关, 而与用户具体搜索的东西无关。 这意味着排序计算可以单独进行, 而无需在用户键入搜索指令后才临时进行。 谷歌搜索的速度之所以快捷, 在很大程度上得益于此。

结语

不过要强调的是,虽然PageRank是Google搜索结果排序的重要依据并以此发家,不过它并不是全部依据——实际上,Google发展到现在,已同时用了数百种不同的算法来确定最终显示给用户的搜索结果顺序。

关于PageRank还有一个小故事。拉里•佩奇是Google的创始人之一,也是现任Google的CEO。有意思的是:“佩奇”的英文是“Page”,恰好与“PageRank”的“Page”相吻合。这是巧合还是有意为之呢?在网络上笔者可以找到的许多资料中,均提到PageRank是以拉里•佩奇的姓命名。但是所有这些资料都没有提到这条信息的来源,所以其真实性无从得证。

不过,既然佩奇本人没有出来解释,那我们也没有必要纠结于Page的含义了。或许这个词本身就是佩奇利用双关语向我们开的一个小玩笑呢!


参考资料:

[1] 卢昌海, 谷歌背后的数学

[2] L. Page, S. Brin, R. Motwani and T. Winograd. The PageRank Citation Ranking: Bring Order to the Web. Jan, 1998.

[3] 维基百科: 马尔可夫过程

相关 [谷歌 搜索 结果] 推荐:

谷歌怎样给搜索结果排序

- lf - FeedzShare
来自: www.guokr.com - FeedzShare  . 发布时间:2011年09月27日,  已有 2 人推荐. 9 月 27 日谷歌推出新款doodle,庆祝自己 13 岁生日. 在这个世界上,谷歌几乎无人不晓了. 但鲜为人知的是,在13年前,拉里•佩奇( Larry Page )和谢尔盖•布林( Sergey Brin )正是依靠先进的算法发家并创立谷歌的.

未来搜索新趋势?谷歌推个性化与自动结果搜索

- - 业界
北京时间 6月28日消息,十多年来,网上搜索长期依赖于一种固定不变的模式:一个空白的搜索框,用户输入查询. 而现在,谷歌在I/O开发者大会上,推出了最新的创新搜索:Google Now,它能够根据你的日程表、搜索历史以及你的位置,通过Widget插件向用户主动提供相关的建议,而这一过程不必手动输入问题,甚至无需键入搜索框.

"谷歌是怎样给搜索结果排序——理性派应该看看

- ROY - Cao Liu
9 月 27 日谷歌推出新款doodle,庆祝自己 13 岁生日. 在这个世界上,谷歌几乎无人不晓了. 但鲜为人知的是,在13年前,拉里•佩奇( Larry Page )和谢尔盖•布林( Sergey Brin )正是依靠先进的算法发家并创立谷歌的. 在这个世界上最自由和创新公司的生日里,来听听死理性派讲述它当年的数学故事吧.

谷歌巨变:接管搜索结果页,自家业务欲独秀

- - 最科技 | 关注互联网科技与应用创新的TMT媒体
作为全球最大、最受欢迎的搜索引擎,谷歌的搜索服务范围极广,涉及多方领域,比如网页搜索、图片搜索、视频搜索、地图搜索、新闻搜索等等. 强大的Google拥有目前的业绩,也是一点点奋斗得来的,其主要的盈利模式是广告盈利,惊人的营收效益支撑着 Google搜索大亨的运作. 谷歌巨变:接管搜索结果页,自家业务欲独秀.

谷歌搜索将有大变化

- - 创业邦
  从下周二开始,谷歌将修改智能手机端搜索算法,这种变化将会影响上千万人购物、觅食和寻找信息的去向.   修改后的算法将向谷歌认为是“移动友好”的网站倾斜. 不符合谷歌“移动友好”标准的网站在搜索结果网页上的排名将会下降,而符合其标准的网站则有更大可能会排在靠前的位置,而靠前的排名意味着访问量和金钱.

谷歌指控微软必应抄袭谷歌搜索

- kezonet - 月光博客
  据Google官方博客报道,谷歌通过一系列实验证明,微软通过IE浏览器、必应工具栏等手段监测用户的谷歌搜索行为,并借用这些信息改进微软必应(Bing)搜索结果,谷歌因而指控微软必应搜索引擎抄袭谷歌的网络搜索结果.   谷歌研究员阿密特·辛格哈尔(Amit Singhal)在这篇博文中指出,谷歌注意到,在用户输入拼写错误的情况下,必应搜索结果与谷歌搜索结果显示的网站惊人地相似.

谷歌悄然推wdyl.com 或成谷歌产品搜索页面

- Aragorn - bbs - 王朝网络
  6月28日消息,据国外媒体报道,谷歌悄然推出wdyl.com,wdyl是“what do you love?”的简称. 消息人士称,这显然是谷歌试图“建立一个在谷歌多个产品中进行搜索的统一UI”.   现在访问wdyl.com将出现谷歌页面,但显示的是404报错页面. 加上“www”即可正常显示,说明wdyl.com尚未完全准备好.

正常访问谷歌搜索、Gmail和谷歌阅读器

- noairhere - 月光微博客
  Gmail和Google Reader是很多人日常工作的必备工具,但现在却遭到了定时的封锁,这里介绍一种新的解决方法,非常简单,可以在不使用任何第三方工具的情况下,正常而快速的访问Google搜索服务、Gmail、Google Reader等Google服务,并且极大提高Google服务的访问速度和访问稳定性,让Google和Gmail运行如飞.

谷歌在华推出团购搜索服务"谷歌时惠"

- olddog1st - cnBeta.COM
9月13日上午消息,谷歌推出针对中国用户的团购搜索服务――时惠(http://www.google.cn/shihui),正式进军电子商务市场. 拉手、美团、窝窝团等一线知名团购网站均在列,这也是谷歌在中国市场沉寂两年后向用户推出的重要服务.