计算机文化基础（李秀）谷歌背后的数学奥秘

《计算机文化基础（李秀）谷歌背后的数学奥秘》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、谷歌怎样给搜索结果排序?sqybi2011-09-2716:16拉里•佩奇(LarryPage)和谢尔盖•布林(SergeyBrin)正是依靠先进的算法发家并创立谷歌google的。9J]27日谷歌推岀新款doodle,庆祝自己13岁生日。在这个世界上，谷歌几乎无人不晓了。但鲜为人知的是，在13年前，拉里•佩奇(LarryPage)和谢尔盖•布林(SergeyBrin)止是依靠先进的算法发家并创立谷歌的。在这个世界上最自由和创新公司的生日里，来听听死理性派讲述它当年的数学故事吧。GoogleSearchPmFeeling

2、Lucky网页排名和谷歌算法的诞生一个正常的搜索引擎，其核心功能自然是网页搜索。那搜索结果应该怎样排序才最好呢？实际上，在谷歌主导互联网搜索Z前，人们为此伤透脑筋。当时人们认为，通过判断能够得知哪个网页更重要，对搜索引擎的发展十分有帮助——很显然，搜索引擎应该把重要的网页放到搜索结果中比较靠前的地方。这个问题看起来很容易，但是解决的方法却没有想象的那么简单。在谷歌诞生之前那段时间，流行的网页排名算法都很类似，它们都使用了一个非常简单的思想：越是重要的网页，访问量就会越大。许多大公司就通过统计网页的访问量来进行网页排名。但

3、是这种排名算法有两个很显著的问题：一是因为只能够抽样统计，所以统计数据不一定准确，而且访问量的波动会比较大，想要得到准确的统计需要大量的时间和人力，还只能维持很短的有效时间；二是访问量并不一定能体现网页的“重要程度”——可能一些比较早接触互联网的网民还记得，那时有很多人推岀了专门“刷访问量”的服务。有没有更好的方法，不统计访问量就能够为网页的重要度排序呢？就是在这种情况下,1996年初，谷歌公司的创始人，当时还是美国斯坦福大学研究牛的佩奇和布林开始了对网页排序问题的研究。在1999年，一篇以佩奇为第一作者的论文发表了，论

4、文中介绍了一种叫做PageRank的算法，这种算法的主要思想是：越“重要”的网页，页面上的链接质量也越高，同时越容易被其它憧要”的网页链接。于是，算法完全利用网页之间互相链接的关系来计算网页的重要程度，将网页排序彻底变成一个数学问题，终于摆脱了访问量统计的框框。三个孩子和豌豆游戏在详细讲述这个算法之前，不妨让我们用一个游戏，先来简单模拟一下PageRank算法的运行过程，以便读者更好地理解。三兄弟分30颗豌豆。起初每人10颗，他们每次都要把手里的豌豆全部平均分给自己喜欢的人。下图表示了三兄弟各自拥有的初始豌豆数量，以及相

5、互喜欢的关系（箭头方向表示喜欢，例如老二喜欢老大，老大喜欢老二和老三）。老二(10)第一次分配后，我们会得到结果如下:就这样，让游戏一直进行下去。直到他们乎中的豌豆数不再变化为止。那么这个游戏到底是否可以结束呢，如果可以，最终的结果又是什么样的？在此我们用电脑模拟了这个过程，得出的结果是：老犬和老二的盘子里各有12颗豌豆，而老三的盘子里有6颗豌豆。这吋候无论游戏怎么进行下去，盘子里的豌豆数量都不会再变化。看到这里，读者可能会问：这个游戏和网页排序有什么关系？实际上，PageRank会给每个网页一个数值，这个数值越高，就说

6、明这个网页越“重要”。而刚刚的游戏中，如果把豌豆的数量看作这个数值(可以不是整数)，把孩子们看作网页，那么游戏的过程就是PageRank的算法，而游戏结束时豌豆的分配,就是网页的PageRank值。PageRank的数学模型不同于之前的访问量统计，PageRank求解了这样一个问题：一个人在网络上浏览网页，每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页x己经确疋，那么网页x上每个链接被点击的概率也是确定的，可以用向量Nx表示。在这种条件下，这个人点击了无限多次链接后，恰好停留在每个网页上

7、的概率分别是多少？在这个模型中，我们用向量Ri来表示点击了i次链接Z后可能停留在每个网页上的概率（Ro则为一开始就打开了每个网页的概率，后面我们将证明Ro的取值对最终结果没有影响）。很显然巳的L1范式为1,这也是PageRank算法木身的要求。仍以上面的游戏为例，整个浏览过程的一开始，我们有:其屮，A表示每一次点击链接概率的矩阵。A的第i列第j行A"的含义是，如果当前访问的网页是网页i,那么下一次点击链接跳转到网页j的概率为Aij。这样设计矩阵A的好处是，通过矩阵A和向量Rn.相乘，即可得出点击一次链接后每个网页可能的停

8、留概率向量Rno例如，4Ri=ARo，可以得到点击一次链接后停留在每个网页的概率：之后一直迭代下去，有:Rn="•"o对于上面的例子，迭代结果如下图:可以看到，每个网页停留的概率在振荡之后趋于稳定。在这种稳定状态下，我们可以知道，无论如何迭代，都有Rn=R0-1o这样我们就获得了一个方程:而整个迭代的过程，就是在寻求