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 算法

取消回复