0x00 前言
Google出品必属精品！作为一名生长在Google大树下的草根程序员，Google的各种技术还是好好膜拜一下的。仔细也一想自己也算看了不少Google不少的论文：Goods、Spanner、F1、GFS、MapReduce、BigTable和Dremel。不过Google成名的PageRank算法没怎么重视，正好最近工作和业务时间都玩了一下，整理一两篇小短文，留个纪念。
我一直认为，程序员不应该对任何算法有所畏惧，因为大部分算法的核心思想和基本设计都不是那么晦涩难懂的。我们可以先搞定基本的算法设计和实现，等到需要用于生产环境时，再加以完善。
内容
本篇大致分为下面三部分：
- PageRank产生的背景
- PageRank的原理
- 用Python实现一个简单的PageRank算法
背景大致过一下，这部分借用一下Mark大神内部分享时候的PPT内容；原理的话只会包含基本的原理，不会太深入（别人问的时候能讲出来最基本的思想和设计）；最后的算法实现，只会有二十多行代码，只实现一个最基本的算法模样。
0x01 背景
聊PageRank算法，首先要聊一下搜索引擎，这是一个比较大的话题，居士没搞过搜索引擎加上能力有限，听了Mark大神的内部分享加上各种查资料后还是不知道怎么写合适。战战兢兢，下面智能大致写一点。
我们从技术的角度上来看搜索引擎需要解决的三个问题：
- 建立资料库
- 建立一种数据结构，这种数据结构能够通过keyword找到链接（文档）
- 对检索到的文档进行排序。
1. 建立资料库
建立资料库，我们暂且把它认为是一个爬虫问题，通过爬虫获取整个互联网的资料。（一直好奇Google和百度的爬虫技术是怎么样的。）
2. 索引
获取数据之后，就要对这些数据建立一种数据结构，使用这种数据能够通过关键词快速地找到链接（文档）。
它的实现方式有：倒排索引，签名文件，后缀树等。我们最熟悉的是倒排索引。
这部分内容可以看一下《信息检索导论》，实在惭愧，明明这本书的内容都学过了一遍，但是想写点东西表达一下自己的知识储备时却写不出来......
3. 排序
排序是Google的搜索引擎能够兴起的一个决定性因素。
对网页排序有很多种方式，我们来看三种：
- 不评价
- 词频位置加权
- PageRank算法
不评价
就是原封不懂地把索引到的链接直接返回给用户，缺点就不说了，想找自己感兴趣的内容估计要费不少功夫。
词频位置加权
这种方式是一种只从关键词出现的次数和位置进行排序的方法。该方法以一个关键词与网页的相关度大小作为排序标准，而关键词在网页的相关度大小作为排序标准，而关键词在网页中的相关度则由它在网页中出现的频次和位置两方面加权计算得出。
缺点也很明显，容易出现刷分的情况，整篇文章中大量地刷关键词就能提高排名。
PageRank算法
真正找到计算网页自身质量的完美的数学模型是Google的创始人拉里佩奇和谢尔盖布林。 下一节讲一下原理。
0x02 PageRank的原理
先理清一下PageRank的主要思想，再看一下它的设计原理。
1. 思想
我们模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率，这个概率就代表这个网页的重要性两个特性：
-
如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是PageRank值会相对较高
-
如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高
2. 原理
注意下面的矩阵相乘，是PageRank算法的一个基本原理，稍微仔细看一遍就大致懂了。
模型抽象
将网页抽象中图中的一个节点，网页之间的链接关系表示一条有向边，整个web被抽象成一个有向图。如下图。
这个例子中只有四个网页，如果当前在A网页，那么悠闲的上网者将会各以1/3的概率跳转到B、C、D，这里的3表示A有3条出链，如果一个网页有k条出链，那么跳转任意一个出链上的概率是1/k，同理D到B、C的概率各为1/2，而B到C的概率为0。
我们在做计算的时候会将该图表示成一个二维的矩阵，我们做一个转换，就会变成下图的矩阵形式。M(i,j)表示j节点指向i节点的概率 ，一般来说每列和为1。
迭代计算
那么PageRank是怎么求出来的？
在算法的第一轮计算中，我们假设上网者在每一个网页的概率都是相等的，即1/n，于是初试的概率分布就是一个所有值都为1/n的n维列向量V0，用V0去右乘转移矩阵M，就得到了第一步之后上网者的概率分布向量MV0,（nXn）(nX1)依然得到一个nX1的矩阵V1，这个V1就是一轮迭代计算出来的PageRank值*。下面是V1的计算过程：
注意矩阵M中M[i][j]不为0表示用一个链接从j指向i，M的第一行乘以V0，表示累加所有网页到网页A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最终V会收敛，即Vn=MV(n-1)，上面的图示例，不断的迭代，最终V=[3/9,2/9,2/9,2/9]：
3. Dead Ends 问题
当出现web不是强连通的，即存在某一类节点不指向别人，如下图的D。这个时候我们的算法就会出问题了，它不满足收敛性了。
好吧，为什么不满足收敛性了？
我们上面描述的上网者的行为是一个其实马尔科夫过程的实例，要满足收敛性，需要具备一个条件：图是强连通的，即从任意网页可以到达其他任意网页。一旦出现如上图的D的节点，就不满足收敛性的。（这里还是先这样理解，感兴趣的可以看一下马尔可夫过程，其实我也没细看，嘿嘿。）
那该怎样解决呢？
悠闲的上网者除了不断的点击网页上的链接来跳转之外，还有一定概率去输入地址的方式来访问（这样是不是更合理了？）。
所以迭代公式转化为下图：
对应带矩阵相乘的话就是下图，这样就不怕出现孤立点的问题了。其中，a一般都取0.8。
0x03 实现
这是最初自己写着玩，用二三十行代码来熟悉算法的基本实现。 真正线上的程序还是要用MR来写的。后续专门来一篇MR写PageRank算法的实现，以及在工程上的深度优化。
0xFF 总结
文章是战战兢兢写的，PageRank是已经很成熟的算法了，自己只是来膜拜的。 参考了不少的内容，图也有不少是直接拿来用的。不过整体还是按照自己的理解来整理的。
作者：dantezhao |简书 | CSDN | GITHUB
个人主页：http://dantezhao.com
文章可以转载, 但必须以超链接形式标明文章原始出处和作者信息
网友评论