写点什么

搜索引擎如何推荐网页

用户头像
dongge
关注
发布于: 2020 年 09 月 09 日
搜索引擎如何推荐网页

搜索引擎如何推荐网页?

Google 的选择是 PageRank。

PageRank,又称网页排名谷歌左侧排名PR,是Google公司所使用的对其搜索引擎搜索结果中的网页进行排名的一种算法。

PageRank 与矩阵的关系

我们先来看下 PageRank 是如何计算的。我假设一共有 4 个网页 A、B、C、D。它们之间的链接信息如图所示:





与图形对应的简化公式可以表示为:



我们再来对比看看矩阵点乘的计算公式。

以上两个公式在形式上是基本一致的。

因此,可以把 PageRank 简化公式的计算,分解为两个矩阵的点乘。一个矩阵是当前每张网页的 PageRank 得分,另一个矩阵就是邻接矩阵。所谓邻接矩阵,其实就是表示图结点相邻关系的矩阵。



为了方便理解,用下面这个拓扑图作为例子详细解释。





基于上面这个图,原始矩阵为:





有了上述这个邻接矩阵,我们就可以开始最简单的 PageRank 计算。PageRank 的计算是采样迭代法实现的。这里我把初始值都设为 1,并把第一次计算的结果列在这里。





已经成功迈出了第一步,但是还需要考虑随机跳转的可能性。

可以把上述公式分解为如下两个矩阵的点乘:

仍然使用前面的例子,来看看经过随机跳转之后,PageRank 值变成了多少。这里 α 取 0.9。





我们前面提到,PageRank 算法需要迭代式计算。为了避免计算后的数值越来越大甚至溢出,我们可以进行归一化处理,保证所有结点的数值之和为 1。经过这个处理之后,我们得到第一轮的 PageRank 数值,也就是下面这个行向量:

[0.37027027 0.24864865 0.37027027 0.00540541 0.00540541]

接下来,我们只需要再重复之前的步骤,直到每个结点的值趋于稳定就可以了。

PageRank 的程序实现

这个过程的 Python 实现:

import numpy as np
# 设置确定随机跳转概率的alpha、网页结点数
alpha = 0.9
N = 5
# 初始化随机跳转概率的矩阵
jump = np.full([2,1], [[alpha], [1-alpha]], dtype=float)
# 邻接矩阵的构建
adj = np.full([N,N], [[0,0,1,0,0],[1,0,1,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0]], dtype=float)
# 对邻接矩阵进行归一化
row_sums = adj.sum(axis=1) # 对每一行求和
row_sums[row_sums == 0] = 0.1 # 防止由于分母出现0而导致的Nan
adj = adj / row_sums[:, np.newaxis] # 除以每行之和的归一化
# 初始的PageRank值,通常是设置所有值为1.0
pr = np.full([1,N], 1, dtype=float)



# PageRank算法本身是采样迭代方式进行的,当最终的取值趋于稳定后结束。
for i in range(0, 20):
# 进行点乘,计算Σ(PR(pj)/L(pj))
pr = np.dot(pr, adj)
# 转置保存Σ(PR(pj)/L(pj))结果的矩阵,并增加长度为N的列向量,其中每个元素的值为1/N,便于下一步的点乘。
pr_jump = np.full([N, 2], [[0, 1/N]])
pr_jump[:,:-1] = pr.transpose()
# 进行点乘,计算α(Σ(PR(pj)/L(pj))) + (1-α)/N)
pr = np.dot(pr_jump, jump)
# 归一化PageRank得分
pr = pr.transpose()
pr = pr / pr.sum()
print("round", i + 1, pr)



运行结果如图:





有一个关于图论和网络建模的工具叫 NetworkX,它是用 Python 语言开发的工具,内置了常用的图与网络分析算法,可以方便我们进行网络数据分析。





希拉里邮件事件相信你也有耳闻,对这个数据的背景我们就不做介绍了。你可以从 GitHub 上下载这个数据集:https://github.com/cystanford/PageRank

执行后可以得到如下图示:







参考

https://zh.wikipedia.org/wiki/PageRank

https://time.geekbang.org/column/article/85194

https://time.geekbang.org/column/article/83034

https://time.geekbang.org/column/article/83471



发布于: 2020 年 09 月 09 日阅读数: 731
用户头像

dongge

关注

还未添加个人签名 2017.10.19 加入

还未添加个人简介

评论

发布
暂无评论
搜索引擎如何推荐网页