TextRank Keyword Extraction

论文:TextRank: Bringing Order into Texts

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

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

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

PageRank

先看公式:

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

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

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

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

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

参考 NetworkX — NetworkX 的实现(这里是带权版本):

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

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

1
2
3
4
5
6
7
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 字:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 定义一个过滤器
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(可以使用内容重叠来衡量)。

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

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

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

Summary

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