TextRank Keyword Extraction 论文+代码笔记

代码：networkx/pagerank_alg.py at master · networkx/networkx

核心思想：TextRank 是基于 Google PageRank 的一种关键词（句子）提取方法，它的本质是对文本 Token 按窗口构建节点和边（实际为节点在一定窗口范围内的共现关系），根据 PageRank 得到节点的 Score 排序。

导读：最近在看 Deep Graph Learning 相关的东西，涉及到很多图理论，大名鼎鼎的 PageRank 当然不能不提，于是就有了这篇文章。本文也是首次以一种新的方式阅读论文、学习理论，大致包括以下方面内容（并不一定严格按照顺序）：算法模型结构（是什么）、算法模型实施（怎么弄）和特殊情况下的处理，另外 “为什么” 会贯穿所有内容。

PageRank

先看公式：

S(V_i) = (1-d) + d * \sum_{j\in In(V_i)} \frac{1}{Out(V_j)} S(V_j)

S 表示 Score。
In 和 Out 分别表示指向自己和自己指向的节点，分别称为前任和后继。
d 是阻尼因子，在 PageRank 那里表示用户随机点击一个网页的概率，然后跳转到一个完全新网页的概率是 1-d，经常被设置为 0.85。

该公式表示：节点 i 的分数主要与它的入度以及入节点的出度有关。简而言之，如果指向某个节点的节点数多，而且这些节点的分数也高的话，该节点的分数就高。

举个例子，比如我们有一个网页 A，要让它的评分高，就应该让更多评分高的网页上添加我们的网页地址。假设现在我们想作弊，有这么些可能的搞法：

做了很多网页指向 A。可以看到，这时候虽然入度增加了，但前任节点的分值不够。注意，它们的分也要用同样的方法计算。如果在前任节点上增加指向高分网页呢？因为前任节点的分数是固定的（因为它们没有入节点），所以添加的越多对 A 的贡献反而越低。
在网页 A 上增加高分网页（如 Google Facebook）。通过公式可以看出这其实对分数是没有影响的，这只是对那些高分网页增加了一点分数（添加的越多，每个网页分摊到的越少）。

如果高分网页（比如 H）指向了 A，那就不一样了，因为 H 的分高，所以对 A 的贡献也大，但是如果 H 指向了很多网页，那对每个网页的贡献都会被分摊，这样也同时避免了高分网页作弊。

参考 NetworkX — NetworkX 的实现（这里是带权版本）：

for _ in range(10):
    xlast = x
    x = dict.fromkeys(xlast.keys(), 0)
    for j in x:
        for i in W[n]:
            x[i] += d * xlast[j] * W[j][i]["weight"] # 核心代码
        x[j] += (1.0 - alpha) * p.get(j, 0) # p 这个是对结果标准化

源代码还处理了孤立节点的情况，另外在迭代时用了提前终止：err = sum([abs(x[n] - xlast[n]) for n in x])，也就是连续两次迭代 Score 差如果小于指定阈值就提前退出迭代。

每次感受这个算法，都觉得它非常不可思议，非常简单却又有效的评估排序方法，可谓是大道至简。

TextRank

PageRank 利用的网页的入出引用，这点和网页的 Score（重要性）强相关，这也是它有效性的表现。那么 TextRank 该如何处理呢？如何利用像 PageRank 这样的图来表示文本、关联词、实体等关系呢？答案是取决于具体的应用，可以使用字、词、句子等，具体包括以下步骤：

确定能最佳定义任务的文本单元作为图的节点（类似于一个个网页）。
确定能连接这些节点的关系，利用这些关系确定图的边，可以有向、无向、有权、无权。
运行算法直到收敛。
根据分数对结果排序，得到顶点的重要性排序。

公式如下：

WS(V_i) = (1-d) + d * \sum_{V_j \in In(V_i)} \frac{\omega_{ji}}{\sum_{V_k \in Out(V_j)} \omega_{jk}}WS(V_j)

WS 表示带权重的 Score。
求和里的分数表示前任节点 j 的权重占比，回顾一下 PageRank，其实是一个稍微改进了的版本，当 Wjk 均为 1 时就退化为 PageRank 了。Vj 除了指向 i，还可能指向其他节点，这些节点都带权重。
在文本中一般使用无向图，迭代会更加平滑。

参考 fxsjy/jieba: 结巴中文分词的实现：

for _ in range(iter_num):
    for vi in graph.nodes:
        s = 0
        for e in graph[vi]:
            vi, vj, weight = e # v1 is just v
            s += (weight / outSum[vj]) * ws[vj] # 核心代码，把下面的 d 写上来就和 NetworkX 一样了
        ws[vi] = (1-d) + d * s

ws 是初始值（无关紧要，最终会收敛），outSum 是每个节点对应边的权重。如果是有向图则为前任节点后继构成的边对应的权重，无向图会同时构造双向。

这个实现和 NetworkX 的实现类似，只不过后者是直接把 weight 先求出来放到 Graph。

Keyword Extraction

接下来就是利用 TextRank 进行关键词提取了。关键词提取任务是用一组词代表一段给定文本。将通过一定规则提取的一系列词加入节点，词之间的关系（任何关系都可以）作为边。在本任务中，选择共现关系作为关系的标准。具体而言，两个节点如果出现在一个窗口内，那么这两个词之间有一条边。窗口从 2 到 N（最大值）。其实际上是将选定节点 N 大小窗口内的节点均作为另一个节点，与选定节点构成边。

举个例子，文本内容为：["我", "爱", "北京", "天安门"]，N 等于 2，从节点 “我” 开始的边为：

1	[("我", "爱"), ("我", "北京"), ("我", "天安门")]

当然，过程中可以把权重加上，权重就是边出现的次数。

算法的具体步骤如下：

对文本进行词性标记，一般是词粒度的。
通过词性过滤节点，并在 N 窗口内构建边，将节点和边加入图。
设置每个节点的初始 Score（1 或 1/num_nodes），使用 TextRank 迭代，一般会选择一个阈值（如 0.0001）以便提前结束迭代。
对节点按 Score 排序，关键词的数量一般选择节点数的 1/3。
将相邻的词合并成一个词。比如 “计算机”、“中心”，可以合并成 “计算机中心”。

我们用代码尝试一下，比如在《王小波文集》中随便选了 500 字：

直到年登不惑，才明白萧翁的见解原有偏颇之处；但这是后话——无论如何，萧翁的这些议论，对那些浅薄之辈、狂妄之辈，总是一种解毒剂。\n\n萧翁说明辨是非难，是因为这些是非都在伦理的领域之内。俗话说得好，此人之肉，彼人之毒；一件对此人有利的事，难免会伤害另一个人。真正的君子知道，自己的见解受所处环境左右未必是公平的，所以他觉得明辨是非是难的。倘若某人以为自己是社会的精英，以为自己的见解一定对，虽然有狂妄之嫌，但他会觉得明辨是非很容易。明了萧翁这重意思以后，我很以做明辨是非的专家为耻——但这已经是二十年前的事了。当时我是年轻人，觉得能洁身自好不去害别人就可以了。现在我是中年人——一个社会里，中年人要负很重的责任：要对社会负责，要对年轻人负责，不能只顾自己。因为这个缘故，我开始写杂文。现在奉献给读者的这本杂文集，篇篇都在明辨是非，而且都在打我自己的嘴。\n\n伦理问题虽难，但却不是不能讨论。罗素先生云，真正的伦理原则把人人同看待。考虑伦理问题时，想替每个人都想一遍是不可能的事，但你可以说，这是我的一得之见，然后说出自己的意见，把是非交付公论。讨论伦理的问题时也可以保持良心的清白——这是我最近的体会，

人肉分析一下，大概可以提取这些词：是非、伦理、负责。然后我们看看自动提取的情况：

# 定义一个过滤器
stop_words = []
ALLOW_POS = set(('ns', 'n', 'vn', 'v', 'a', 'an'))
def pos_filter(pair):
    return (pair.flag in ALLOW_POS and 
            len(pair.word) >=2 and 
            pair.word.lower() not in stop_words)

# 分词和词性标注
import jieba.posseg as pseg
win = 2
wps = pseg.lcut(text)
num_token = len(wps)
cm = defaultdict(int)
for i, wp in enumerate(wps):
    if pos_filter(wp):
        for j in range(i+1, i+win):
            if j >= num_token:
                break
            if pos_filter(wps[j]):
                cm[(wp.word, wps[j].word)] += 1

# 节点和关系入图
graph_data = []
for key,value in cm.items():
    item = (key[0], key[1], value)
    graph_data.append(item)
G = nx.Graph()
G.add_weighted_edges_from(graph_data)
# 搞成双向（可以看成无向图）
G = G.to_directed()

# 运行算法并获得结果
nodes_with_score = nx.pagerank(G)
sorted(nodes_with_score.items(), key=lambda x:x[1], reverse=True)[: G.number_of_nodes()//3]
[('伦理', 0.10094394955388881),
 ('要负', 0.06345574782809552),
 ('负责', 0.06345574782809552),
 ('交付', 0.06345574782809552),
 ('讨论', 0.0457534053187857),
 ('见解', 0.043478260869565216),
 ('原有', 0.043478260869565216)]

可以看到结果还是有点问题，需要进一步后处理，除了合并相邻词之外，可能还需要剔除不是词的词（要负、原有之类）。另外，需要注意以下几点：

中文的动词很多时候比较重要，可能是关键词。
词性多的时候召回高一些，精度可能会下降。
效果与词性标注模型相关。

Discussion

关于论文中讨论部分需要注意以下几点：

窗口大并没有帮助，而且越大效果越差，说明远距离的词之间并不能构成关系。
词性限制为名词和形容词时效果最好。这点比较好理解，关键词一般都是名词或形容词。只使用词（利用停用词过滤而不是词性）效果不好。
有向图效果不如无向图。说明关键词之间并没有文本这样的 “方向性”。原因可能和只提取 “词” 有关。
无监督算法，且语言无关。这也是我最钟爱 TextRank 的地方。

除此之外，我们讨论一下文本非常长或非常短的情况。根据前面的分析，这两种情况对于算法本身应该是无感的，这就好比 PageRank 不会 care 到底有多少网页一样。但文本有个不一样的地方在于，越是长的文本，关键词越抽象，当达到文章级别时，关键词可能都不出现在文中。所以，可能一两千字以内比较合适。对于更长的文本，可能标题、开头和结尾会涉及到关键词，可以把重心放在这几个地方。当然，也要看具体的任务。

Sentence Extraction

节点是句子，句子可以过滤（比如按长度、词性等；举个例字：长度小于 5 的句子不要；没有名词或形容词的句子不要）。
边看句子之间的 Similarity（可以使用内容重叠来衡量）。

\text {Similarity}\left(S_{i}, S_{j}\right)=\frac{\left|\left\{w_{k} | w_{k} \in S_{i} \& w_{k} \in S_{j}\right\}\right|}{\log \left(\left|S_{i}\right|\right)+\log \left(\left|S_{j}\right|\right)}

分母用两个句子的长度做归一化因子，分子是两个句子词 Set 交集的词数，这里的词也可以用词性过滤。

因为结果是对所有句子进行排序，所以很方便获得短的或长的 Summary。

算法整体比较简单，letiantian/TextRank4ZH: 从中文文本中自动提取关键词和摘要利用 NetworkX 已经做了实现，可以参考。

Summary

本文主要介绍了基于 PageRank 的 TextRank 算法，以及该算法在关键词提取领域的应用。TextRank 基于词为节点、窗口词共现为关系，共现次数为权重构建图，然后基于 PageRank 算法迭代至收敛，最终得到节点的重要性得分。

Yam

Feeling, Coding, Thinking