Categories
程式開發

搜索引擎如何推荐网页


搜索引擎如何推荐网页?

Google 的选择是 PageRank。

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

PageRank 与矩阵的关系

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

搜索引擎如何推荐网页 1

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

搜索引擎如何推荐网页 2

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

搜索引擎如何推荐网页 3

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

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

搜索引擎如何推荐网页 4

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

搜索引擎如何推荐网页 5

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

搜索引擎如何推荐网页 6

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

搜索引擎如何推荐网页 7

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

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

搜索引擎如何推荐网页 8

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

搜索引擎如何推荐网页 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)

运行结果如图:

搜索引擎如何推荐网页 10

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

搜索引擎如何推荐网页 11

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

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

搜索引擎如何推荐网页 12

搜索引擎如何推荐网页 13

参考

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