1. PageRank

PageRank 算法是谷歌根据网页重要程度给网页排名的算法。该值越高，说明网页越重要，当用户进行相关搜索时，就越有可能优先展现给用户。

我们通过一个例子来理解 PageRank 的计算过程。现在有 3 个网页，网页之间会相互链接，链接关系如下图：

网页 A 链接网页 C，对网页 C 的权重计算提供 1 的贡献。
网页 B 链接网页 A、网页 C，网页 B 对网页 A、C 的权重计算提供的贡献分别是 1/2。
网页 C 没有链接任何网页，对其他网页权重计算的贡献为 0。

从这个链接关系来看，A 被其他网页链接了 1 次，B 被其他网页链接 0 次，C 被其他网页链接了 2 次。看起来 C 网页的 PR 更大一些，也更重要一些。所以，PageRank 在评价网页时，是根据其他网页对当前网页的链接数量、链接质量来评价的，即：别人说你好，你才真的好。

网页 PR 值的计算公式如下：

1. In(V_i) 表示链接到网页 V_i 的所有网页，比如对于 C 网页而言，A、B 就是链接它的网页。
2. Out(V_j) 表示链接网页的出链数量，比如 C 网页的链接网页是 A、B，A 的出链数量是 1，B 的出链数量是 2。
3. P(V_j) 表示链接网页 A、B 的权重，即权重越大，对提升 C 网页权重的贡献就越大。
4. d 叫做阻尼系数。当一个网页没有任何外部网页链接到它时，它的权重为 0，阻尼系数可以给网页一个保底的权重值，一般 d 这个值被设置为 0.85。

如果一个网页的出链有 N 个，那么它对被链接网页的重要程度的贡献就是 1/N。我们把上面的网页出链贡献，即 out 分之一，写成如下矩阵形式：

上图中，左图第一行表示：网页 B 对网页 A 有链接，而网页 A 和网页 C 则没有到网页 A 的链接。

由于现在我们并不知道每个网页的 PR 值，共有 3 个网页，可以先把每个网页的 PR 值初始化为 1/3，即 (1/3, 1/3, 1/3)。

接下来，怎么计算这 3 个网页的重要程度呢？

我们用上面的 PageRank 公式进行迭代计算，直到 PR 值收敛或者小于某个阈值，代码如下：

import torch
import numpy as np


def page_rank():


    # 构建网页链接关系
    graph = torch.tensor([[0, 1, 0],
                         [0, 0, 0],
                         [1, 1, 0]])
    norm_graph = graph / torch.sum(graph, dim=0, keepdim=True)
    # 由于有些列全0，相除之后出现 nan，对这些 nan 列进行替换
    norm_graph[torch.isnan(norm_graph)] = 0

    # 设置网页初始 PR 值
    init_page_rank = torch.tensor([[1/3], [1/3], [1/3]], dtype=torch.float32)
    page_rank = init_page_rank

    # 设置阻尼系数
    d = 0.85

    # 开始迭代计算每个网页的 PR 值
    for _ in range(100):
        page_rank = (1 - d) * init_page_rank + d * (norm_graph @ page_rank)

    print(page_rank.reshape(1, -1))


if __name__ == '__main__':
    page_rank()

输出结果：

tensor([[0.0713, 0.0500, 0.1318]])

从运行结果来看，3 个网页的 PageRank 分别为：网页 A：0.0713，网页 B：0.0500，网页 C：0.1318。网页 C 更重要一些，其次是网页 A，最后是网页 B。

2. TextRank

TextRank 构造的是带权无向图，PageRank 构建的是带权有向图。

我们通过一个例子来理解 TextRank 的算法思想，假设文本内容如下：

人生就像一杯苦茶，不会苦一辈子，但会苦一阵子

接下来，我们对上面这段文本分词，去除停用词，去重（保持原有词顺序），结果为：

分词结果：[‘人生’, ‘一杯’, ‘茶’, ‘苦’, ‘一辈子’, ‘总会’, ‘苦’, ‘一阵子’]
去重结果：[‘人生’, ‘一杯’, ‘茶’, ‘苦’, ‘一辈子’, ‘总会’, ‘一阵子’]

我们用上面这些词，构建一个窗口大小为 2 的共现矩阵：

窗口滑动第一次 “人生一杯“，对应 [人生][一杯] 和 [一杯][人生] 位置标注为 1。
窗口滑动第二次 “一杯茶“，对应 [一杯][茶] 和 [茶][一杯] 位置标注为 1。
以此类推构建共现矩阵……

我们以上图为例，空白部分为 0，横轴表示其他词对当前这个词计算重要性的贡献。比如 “茶” 这个词的重要性，是由 “苦” 这个词贡献了 1/4。

词之间的共现关系如下图所示：

接下来，我们看每个词的 TextRank 计算公式：

1. TR(V_i) 表示第 i 个词的 TextRank 值，比如 “人生” 这个词的 TextRank 值。
2. In(V_i) 表示在窗口内与当前词具有共现关系的词，比如第 i 个词是 “人生”，它的 In(V_i) 就是 “一杯”。
3. Out(V_j) 表示某个词对其他词重要性输出的贡献总和，比如 “苦” 这个词对 “茶”、”一辈子”、”总会”、”一阵子” 贡献了 1/4。
4. w_ji 表示第 j 个词对当前第 i 个词的贡献，比如 “一杯” 这个词对 “人生” 的贡献就是 1。
5. d 阻尼系数表示每个词最少的 TextRank 值，避免某些词出现 0 的情况。

有了这个归一化的共现矩阵，我们就可以用上面的公式进行迭代计算了。

import torch
import networkx as nx
import matplotlib.pyplot as plt


def text_rank():

    # 共现矩阵
    graph = torch.tensor([[0, 1, 0, 0, 0, 0, 0],
                         [1, 0, 1, 0, 0, 0, 0],
                         [0, 1, 0, 1, 0, 0, 0],
                         [0, 0, 1, 0, 1, 1, 1],
                         [0, 0, 0, 1, 0, 1, 0],
                         [0, 0, 0, 1, 1, 0, 0],
                         [0, 0, 0, 1, 0, 0, 0]])

    # 共现矩阵归一化
    norm_graph = graph / torch.sum(graph, dim=0, keepdim=True)

    # 绘制词之间的共现关系
    graph = nx.from_numpy_matrix(norm_graph.numpy())
    node_name = { idx: name for idx, name
                  in enumerate(['人生', '一杯', '茶', '苦', '一辈子', '总会', '一阵子'])}
    nx.draw_networkx(graph, labels=node_name)
    plt.show()



    # 每个词的初始 TextRank 值
    init_text_rank = torch.tensor([[1/7],
                                   [1/7],
                                   [1/7],
                                   [1/7],
                                   [1/7],
                                   [1/7],
                                   [1/7]], dtype=torch.float32)
    # 阻尼系数
    d = 0.85
    # 迭代求解
    text_rank = init_text_rank
    for _ in range(100):
        text_rank = (1 - d) * init_text_rank + d * (norm_graph @ text_rank)

    # 每个词的 TextRank 值
    print(text_rank.reshape(1, -1))


if __name__ == '__main__':
    # [‘人生’, ‘一杯’,  ‘茶’,    ‘苦’,    ‘一辈子’,  ‘总会’,  ‘一阵子’]
    # [0.0714, 0.1429, 0.1429,  0.2857,  0.1429,  0.1429,   0.0714]
    text_rank()

程序输出结果：

tensor([[0.0887, 0.1582, 0.1445, 0.2627, 0.1344, 0.1344, 0.0773]])

最终，我们得到这几个词的 TextRank 值为：

人生	一杯	茶	苦	一辈子	总会	一阵子
0.0887	0.1582	0.1445	0.2627	0.1344	0.1344	0.0773

从结果来看，”苦”、”一杯”、”茶”、”总会” 比较适合做我们这段文本的关键词。

TextRank 算法

TextRank 算法

1. PageRank

2. TextRank