论文: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 | for _ in range(10): |
源代码还处理了孤立节点的情况,另外在迭代时用了提前终止: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 | for _ in range(iter_num): |
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 | # 定义一个过滤器 |
可以看到结果还是有点问题,需要进一步后处理,除了合并相邻词之外,可能还需要剔除不是词的词(要负、原有之类)。另外,需要注意以下几点:
- 中文的动词很多时候比较重要,可能是关键词。
- 词性多的时候召回高一些,精度可能会下降。
- 效果与词性标注模型相关。
Discussion
关于论文中讨论部分需要注意以下几点:
- 窗口大并没有帮助,而且越大效果越差,说明远距离的词之间并不能构成关系。
- 词性限制为名词和形容词时效果最好。这点比较好理解,关键词一般都是名词或形容词。只使用词(利用停用词过滤而不是词性)效果不好。
- 有向图效果不如无向图。说明关键词之间并没有文本这样的 “方向性”。原因可能和只提取 “词” 有关。
- 无监督算法,且语言无关。这也是我最钟爱 TextRank 的地方。
除此之外,我们讨论一下文本非常长或非常短的情况。根据前面的分析,这两种情况对于算法本身应该是无感的,这就好比 PageRank 不会 care 到底有多少网页一样。但文本有个不一样的地方在于,越是长的文本,关键词越抽象,当达到文章级别时,关键词可能都不出现在文中。所以,可能一两千字以内比较合适。对于更长的文本,可能标题、开头和结尾会涉及到关键词,可以把重心放在这几个地方。当然,也要看具体的任务。
Sentence Extraction
- 节点是句子,句子可以过滤(比如按长度、词性等;举个例字:长度小于 5 的句子不要;没有名词或形容词的句子不要)。
- 边看句子之间的 Similarity(可以使用内容重叠来衡量)。
分母用两个句子的长度做归一化因子,分子是两个句子词 Set 交集的词数,这里的词也可以用词性过滤。
因为结果是对所有句子进行排序,所以很方便获得短的或长的 Summary。
算法整体比较简单,letiantian/TextRank4ZH: 从中文文本中自动提取关键词和摘要 利用 NetworkX 已经做了实现,可以参考。
Summary
本文主要介绍了基于 PageRank 的 TextRank 算法,以及该算法在关键词提取领域的应用。TextRank 基于词为节点、窗口词共现为关系,共现次数为权重构建图,然后基于 PageRank 算法迭代至收敛,最终得到节点的重要性得分。