NLP

TextRank算法提取关键词和摘要

把PageRank运用到自然语言处理上

Posted by Xiaosheng on April 8, 2017

提到从文本中提取关键词,我们第一想到的肯定是通过计算词语的 TF-IDF 值来完成,简单又粗暴。但是由于 TF-IDF 的结构过于简单,有时提取关键词的效果会很不理想。

本文将介绍一个由 Google 著名的网页排序算法 PageRank 改编而来的算法——TextRank,它利用图模型来提取文章中的关键词。

PageRank

PageRank 是一种通过网页之间的超链接来计算网页重要性的技术,以 Google 创办人 Larry Page 之姓来命名,Google 用它来体现网页的相关性和重要性。PageRank 通过网络浩瀚的超链接关系来确定一个页面的等级,把从 A 页面到 B 页面的链接解释为 A 页面给 B 页面投票,Google 根据 A 页面(甚至链接到 A 的页面)的等级和投票目标的等级来决定 B 的等级。简单的说,一个高等级的页面可以使其他低等级页面的等级提升。

整个互联网可以看作是一张有向图图,网页是图中的节点,网页之间的链接就是图中的边。如果网页 A 存在到网页 B 的链接,那么就有一条从网页 A 指向网页 B 的有向边。

构造完图后,使用下面的公式来计算网页 $i$ 的重要性(PR值):

$d$ 是阻尼系数,一般设置为 0.85。$In(V_i)$ 是存在指向网页 $i$ 的链接的网页集合。$Out(V_j)$ 是网页 $j$ 中的链接指向的网页的集合。$|Out(V_j)|$ 是集合中元素的个数。PageRank 需要使用上面的公式多次迭代才能得到结果。初始时,可以设置每个网页的重要性为 1。

TextRank

TextRank 公式在 PageRank 公式的基础上,为图中的边引入了权值的概念:

$w_{ij}$ 就是是为图中节点 $V_i$ 到 $V_j$ 的边的权值 。$d$ 依然为阻尼系数,代表从图中某一节点指向其他任意节点的概率,一般取值为0.85。$In(V_i)$ 和 $Out(V_i)$ 也和 PageRank 类似,分别为指向节点 $V_i$ 的节点集合和从节点 $V_i$ 出发的边指向的节点集合。

在 TextRank 构建的图中,默认节点就是句子,权值 $w_{ij}$ 就是两个句子 $S_i$ 和 $S_j$ 的相似程度。两个句子的相似度使用下面的公式来计算:

分子是在两个句子中都出现的单词的数量,$|S_i|$是句子 i 中的单词数。

使用 TextRank 算法计算图中各节点的得分时,同样需要给图中的节点指定任意的初值,通常都设为1。然后递归计算直到收敛,即图中任意一点的误差率小于给定的极限值时就可以达到收敛,一般该极限值取 0.0001。

使用 TextRank 提取关键词

现在是要提取关键词,如果把单词视作图中的节点(即把单词看成句子),那么所有边的权值都为 0(两个单词没有相似性),所以通常简单地把所有的权值都设为 1。此时算法退化为 PageRank,因而把关键字提取算法称为 PageRank 也不为过。

我们把文本拆分为单词,过滤掉停用词(可选),并只保留指定词性的单词(可选),就得到了单词的集合。假设一段文本依次由下面的单词组成:

如果我们设定窗口大小为 $k$,那么 $[w_1,w_2,…,w_k]$、$[w_2,w_3,…,w_{k+1}]$、$[w_3,w_4,…,w_{k+2}]$ 等都是一个窗口。

现在将每个单词作为图中的一个节点,同一个窗口中的任意两个单词对应的节点之间存在着一条边。然后利用投票的原理,将边看成是单词之间的互相投票,经过不断迭代,每个单词的得票数都会趋于稳定。一个单词的得票数越多,就认为这个单词越重要。

例如要从下面的文本中提取关键词:

程序员(英文Programmer)是从事程序开发、维护的专业人员。一般将程序员分为程序设计人员和程序编码人员,但两者的界限并不非常清楚,特别是在中国。软件从业人员分为初级程序员、高级程序员、系统分析员和项目经理四大类。

对这句话分词,去掉里面的停用词,然后保留词性为名词、动词、形容词、副词的单词。得出实际有用的词语:

程序员, 英文, 程序, 开发, 维护, 专业, 人员, 程序员, 分为, 程序, 设计, 人员, 程序, 编码, 人员, 界限, 特别, 中国, 软件, 人员, 分为, 程序员, 高级, 程序员, 系统, 分析员, 项目, 经理

现在建立一个大小为 9 的窗口,即相当于每个单词要将票投给它身前身后距离 5 以内的单词:

开发=[专业, 程序员, 维护, 英文, 程序, 人员]
软件=[程序员, 分为, 界限, 高级, 中国, 特别, 人员]
程序员=[开发, 软件, 分析员, 维护, 系统, 项目, 经理, 分为, 英文, 程序, 专业, 设计, 高级, 人员, 中国]
分析员=[程序员, 系统, 项目, 经理, 高级]
维护=[专业, 开发, 程序员, 分为, 英文, 程序, 人员]
系统=[程序员, 分析员, 项目, 经理, 分为, 高级]
项目=[程序员, 分析员, 系统, 经理, 高级]
经理=[程序员, 分析员, 系统, 项目]
分为=[专业, 软件, 设计, 程序员, 维护, 系统, 高级, 程序, 中国, 特别, 人员]
英文=[专业, 开发, 程序员, 维护, 程序]
程序=[专业, 开发, 设计, 程序员, 编码, 维护, 界限, 分为, 英文, 特别, 人员]
特别=[软件, 编码, 分为, 界限, 程序, 中国, 人员]
专业=[开发, 程序员, 维护, 分为, 英文, 程序, 人员]
设计=[程序员, 编码, 分为, 程序, 人员]
编码=[设计, 界限, 程序, 中国, 特别, 人员]
界限=[软件, 编码, 程序, 中国, 特别, 人员]
高级=[程序员, 软件, 分析员, 系统, 项目, 分为, 人员]
中国=[程序员, 软件, 编码, 分为, 界限, 特别, 人员]
人员=[开发, 程序员, 软件, 维护, 分为, 程序, 特别, 专业, 设计, 编码, 界限, 高级, 中国]

然后开始迭代投票,直至收敛:

程序员=1.9249977,
人员=1.6290349,
分为=1.4027836,
程序=1.4025855,
高级=0.9747374,
软件=0.93525416,
中国=0.93414587,
特别=0.93352026,
维护=0.9321688,
专业=0.9321688,
系统=0.885048,
编码=0.82671607,
界限=0.82206935,
开发=0.82074183,
分析员=0.77101076,
项目=0.77101076,
英文=0.7098714,
设计=0.6992446,
经理=0.64640945

可以看到“程序员”的得票数最多,因而它是整段文本最重要的单词。我们将文本中得票数多的若干单词作为该段文本的关键词,若多个关键词相邻,这些关键词还可以构成关键短语。

使用 TextRank 提取摘要

自动摘要,就是从文章中自动抽取关键句。人类对关键句的理解通常是能够概括文章中心的句子,而机器只能模拟人类的理解,即拟定一个权重的评分标准,给每个句子打分,之后给出排名靠前的几个句子。基于 TextRank 的自动文摘属于自动摘录,通过选取文本中重要度较高的句子形成文摘。

依然使用 TextRank 公式:

等式左边表示一个句子的权重(WS 是 weight_sum 的缩写),右侧的求和表示每个相邻句子对本句子的贡献程度。与提取关键字的时候不同,一般认为全部句子都是相邻的,不再通过窗口提取

边的权值 $w_{ij}$ 代表句子 $S_i$ 和 $S_j$ 的相似度,既可以使用上面介绍过的基于句子间内容覆盖率的方法计算,也可以使用基于编辑距离,基于语义词典,余弦相似度,BM25 算法等等。

因为我们是要抽取关键句,因而是以句子为基本单位。使用 TextRank 提取摘要的整个过程如下:

  1. 预处理:将文本分割成句子 $S_1,S_2,\cdots,S_m$,以句子为节点构建图。
  2. 计算句子相似度:对句子进行分词、取停用词等处理,以便于计算任意两个句子之间的相似度。将计算好的句子相似度作为两个句子构成的边的权值。
  3. 句子权重:根据公式,迭代传播权重计算各句子的得分。
  4. 抽取文摘句:得到的句子得分进行倒序排序,抽取重要度最高的 N 个句子作为候选文摘句。
  5. 形成文摘:根据字数或句子数要求,从候选文摘句中抽取句子组成文摘。

开源项目

  • 乐天使用 Python 编写的 TextRank4ZH,可以用来从文本中提取关键词和摘要(关键句)。
  • Hankcs 使用 Java 编写的全功能汉语言处理包 HanLP,提供了“TextRank关键词提取”和“TextRank自动摘要”的功能。
  • 啊哈自然语言处理包 AHANLP,句子之间的相似程度使用 Word2Vec 提供的函数计算。

参考

维基百科《佩奇排名》
乐天《使用TextRank算法为文本生成关键字和摘要》
Hankcs《TextRank算法提取关键词的Java实现》
Hankcs《TextRank算法自动摘要的Java实现》
flystarhe《TextRank探索与实践》
bbking《TextRank 自动文摘》