训练营第十三周作业 1

作业一：

（至少完成一个）

• 你所在的行业，常用的数据分析指标有哪些？请简述。

• Google 搜索引擎是如何对搜索结果进行排序的？（请用自己的语言描述 PageRank 算法。）

PageRank 算法，又称佩奇排名，是 Google 公司对其搜索引擎搜索结果中的网页进行排名的一种算法。

PageRank 算法通过输出概率分布来体现某人随机地点击某个链接的概率——PR 值。

算法定义有点抽象，我们通过一个简化版的示例来介绍一下如何计算 PR 值。假设总共只有四个网页 A、B、C、D，所有的页面只指向 A，那么 A 的 PR 值就是 B、C、D 的 PR 总和：

简单 PR 计算 1

再比如 B 链接到 A 和 C；C 链接到 A；并且 D 链接到 A、B、C：

简单 PR 计算 1

B 就会分出去半票 给 A 、C ；C 给 A 一票；D 给其他各页面三分之一票，结果 PR(A)的值就是：

加权的 PR 值

概括一下：算法会根据每个页面总出度 L(x)——指向其他页面的总个数——平分该页面的 PR 值，并将其加到所指向的页面：

加权的 PR 值

算法最后会添加一个系数 d 做修正：

• 给添加出度权重后的 PR 值再乘上该修正系数 d

• 并保证每个页面的最小值为 (1-d) / N， N 为集合中网页的数目

p.s. d 是根据上网者使用浏览器书签的平均频率估算而得，大约为 0.85

我们得到：

修正后的 PR 值

同理，我们把该公式泛化到所有的页面，即：

所有的 PR 值

写成矩阵形式：集合中所有页面的 PR 值可以由一个特殊的邻接矩阵的特征向量表示，这个特征向量 R 为：

向量形式 PR

PageRank 算法中，一个页面的 PR 值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的 PR 值，通过上述公式经过多次迭代，这些页面的 PR 值会收敛某个定值，即最终结果。

矩阵迭代