利用TextRank算法提取摘要关键词以及Java实现

谈起自动摘要算法，常见的并且最易实现的当属TF-IDF，但是感觉TF-IDF效果一般，不如TextRank好。

 一. TF-IDF与TextRank

1. TF-IDF简介

TF-IDF（Term Frequency/Inverse Document Frequency）是信息检索领域非常重要的搜索词重要性度量；用以衡量一个关键词w对于查询（Query，可看作文档）所能提供的信息。词频（Term Frequency, TF）表示关键词w在文档Di中出现的频率：

其中，count(w)为关键词w的出现次数，|Di|为文档Di中所有词的数量。逆文档频率（Inverse Document Frequency, IDF）反映关键词的普遍程度——当一个词越普遍（即有大量文档包含这个词）时，其IDF值越低；反之，则IDF值越高。IDF定义如下：

其中，N为所有的文档总数，I(w,Di)表示文档Di是否包含关键词，若包含则为1，若不包含则为0。若词w在所有文档中均未出现，则IDF公式中的分母为0；因此需要对IDF做平滑（smooth）：

关键词w在文档Di的TF-IDF值：

从上述定义可以看出：

• 当一个词在文档频率越高并且新鲜度高（即普遍度低），其TF-IDF值越高。
• TF-IDF兼顾词频与新鲜度，过滤一些常见词，保留能提供更多信息的重要词。

2. TextRank简介

TextRank是在Google的PageRank算法启发下，针对文本里的句子设计的权重算法，目标是自动摘要。它利用投票的原理，让每一个单词给它的邻居（术语称窗口）投赞成票，票的权重取决于自己的票数。这是一个“先有鸡还是先有蛋”的悖论，PageRank采用矩阵迭代收敛的方式解决了这个悖论，TextRank也不例外！

2.1 PageRank的计算公式：

2.2 正规的TextRank公式

正规的TextRank公式在PageRank的公式的基础上，引入了边的权值的概念，代表两个句子的相似度。

但是很明显，如果只想计算关键字，就把一个单词视为一个句子，那么所有句子（单词）构成的边的权重都是0（没有交集，没有相似性），所以分子分母的权值w约掉得了，算法退化为PageRank。所以说，这里称关键字提取算法为PageRank也不为过。

在这里算是简单说明了TextRank的内在原理，以下对其关键词提取应用做进一步说明。

2.3 关键词提取算法

TextRank用于关键词提取的算法如下：

• ①把给定的文本T按照完整句子进行分割，即
• ②对于每个句子Si属于T，进行分词和词性标注处理，并过滤掉停用词，只保留指定词性的单词，如名词、动词、形容词，即

其中 ti,j 是保留后的候选关键词。

• ③构建候选关键词图G = (V,E)，其中V为节点集，由（2）生成的候选关键词组成，然后采用共现关系（co-occurrence）构造任两点之间的边，两个节点之间存在边仅当它们对应的词汇在长度为K的窗口中共现，K表示窗口大小，即最多共现K个单词。
• ④根据上面公式，迭代传播各节点的权重，直至收敛。
• ⑤对节点权重进行倒序排序，从而得到最重要的T个单词，作为候选关键词。
• ⑥由⑤得到最重要的T个单词，在原始文本中进行标记，若形成相邻词组，则组合成多词关键词。

3. 对比总结

• TextRank与TFIDF均严重依赖于分词结果——如果某词在分词时被切分成了两个词，那么在做关键词提取时无法将两个词黏合在一起（TextRank有部分黏合效果，但需要这两个词均为关键词）。因此是否添加标注关键词进自定义词典，将会造成准确率、召回率大相径庭。
• TextRank的效果优于TFIDF。
• TextRank并不需要制作特定的语言模型，它只跟当前文章有关。

二、TextRank的java实现

TextRank的java实现主要参考了HanLP中开源，将其中的分词工具替换成ANSJ分词

1、算法类

import java.util.*;/*** @author summer* @date 2020/07/30*/
public class Demo {private static float min_diff = 0.001f; //差值最小private static int max_iter = 200;//最大迭代次数private static int k = 2;  //窗口大小/2private static float d = 0.85f;private static List<String> textRank(String field, int keywordNum) {//分词List<WOD<String>> wods = ToAnalysisParse(field);// StopWord.filter(wods);//过滤掉不需要的分词，可省略Map<String, Set<String>> relationWords = new HashMap<>();//获取每个关键词 前后k个的组合for (int i = 0; i < wods.size(); i++) {String keyword = wods.get(i).getName();Set<String> keySets = relationWords.get(keyword);if (keySets == null) {keySets = new HashSet<>();relationWords.put(keyword, keySets);}for (int j = i - k; j <= i + k; j++) {if (j < 0 || j >= wods.size() || j == i) {continue;} else {keySets.add(wods.get(j).getName());}}}Map<String, Float> score = new HashMap<>();//迭代for (int i = 0; i < max_iter; i++) {Map<String, Float> m = new HashMap<>();float max_diff = 0;for (String key : relationWords.keySet()) {Set<String> value = relationWords.get(key);//先给每个关键词一个默认rank值m.put(key, 1 - d);//一个关键词的TextRank由其它成员投票出来for (String other : value) {int size = relationWords.get(other).size();if (key.equals(other) || size == 0) {continue;} else {m.put(key, m.get(key) + d / size * (score.get(other) == null ? 0 : score.get(other)));}}max_diff = Math.max(max_diff, Math.abs(m.get(key) - (score.get(key) == null ? 0 : score.get(key))));}score = m;if (max_diff <= min_diff) {
//                System.out.println("迭代次数：" + i);break;}}List<WOD<String>> scores = new ArrayList<>();for (String s : score.keySet()) {WOD<String> score1 = new WOD(s, score.get(s));scores.add(score1);}scores.sort(new Comparator<WOD<String>>() {@Overridepublic int compare(WOD<String> o1, WOD<String> o2) {return o1.compareTo(o2);}});List<String> keywords = new ArrayList<>();int index = 0;for (WOD<String> score1 : scores) {keywords.add(score1.getName());index++;if (index==keywordNum)break;}return keywords;}public static List<WOD<String>> ToAnalysisParse(String str) {List<WOD<String>> wods = new ArrayList();List<Term> terms = ToAnalysis.parse(str);Iterator var4 = terms.iterator();while(var4.hasNext()) {Term term = (Term)var4.next();wods.add(new WOD(term.getName(), term.getNatureStr()));}return wods;}
}

2、WOD类

import java.io.Serializable;public class WOD<T> implements Comparable<WOD<T>>, Serializable {private static final long serialVersionUID = -2317609898674927526L;private T obj;private double score;private String nature = "";public WOD() {}public WOD(T obj) {this.obj = obj;}public WOD(T obj, double score) {this.obj = obj;this.score = score;}public WOD(T obj, String nature) {this.obj = obj;this.nature = nature;}public WOD(T obj, double score, String nature) {this.obj = obj;this.score = score;this.nature = nature;}public String getName() {return this.obj.toString();}public void setObj(T obj) {this.obj = obj;}public T getObj() {return this.obj;}public double getScore() {return this.score;}public void setScore(double score) {this.score = score;}public String getNature() {return this.nature;}public void setNature(String nature) {this.nature = nature;}public String toString() {return this.getName() + "/" + this.score;}public String toDetailString() {return this.getName() + "/" + this.nature + "/" + this.score;}public String toSimpleString() {return this.getName();}public int compareTo(WOD<T> o) {if (this.score > o.score) {return -1;} else {return this.score == o.score ? 0 : 1;}}public boolean equals(Object obj) {if (obj instanceof WOD) {WOD w = (WOD)obj;return w.getName().equals(this.getName());} else {return false;}}
}

3、调用方法

public static void main(String[] args) {String field = "哈利·波特，40岁生日快乐！ 1991年7月31日，11岁的哈利·波特收到一份特殊的生日礼物——霍格沃兹魔法学校的录取通知书，由此踏上他的魔法之旅……2020年7月31日，陪伴无数青少年长大的哈利迎来了他的40岁生日。 今年也是“哈利·波特”系列小说进入中国20周年，人民文学出版社推出《哈利·波特与魔法石》学院纪念版，包括格兰芬多、斯莱特林、赫奇帕奇和拉文克劳四个学院版本。 31日晚，该社将举办迄今为止最大型的线上直播暨哈利·波特学院杯争夺赛。与此同时，“哈利·波特”系列八部电影正在第23届上海国际电影节展映，第一部电影《哈利·波特与魔法石》4K修复3D版，定档8月14日在内地重映。   ";List<String> keywords = Demo.textRank(field,10);System.out.println("关键词：" + keywords);}

4、测试

语料：

哈利·波特，40岁生日快乐！

1991年7月31日，11岁的哈利·波特收到一份特殊的生日礼物——霍格沃兹魔法学校的录取通知书，由此踏上他的魔法之旅……2020年7月31日，陪伴无数青少年长大的哈利迎来了他的40岁生日。 今年也是“哈利·波特”系列小说进入中国20周年，人民文学出版社推出《哈利·波特与魔法石》学院纪念版，包括格兰芬多、斯莱特林、赫奇帕奇和拉文克劳四个学院版本。 31日晚，该社将举办迄今为止最大型的线上直播暨哈利·波特学院杯争夺赛。与此同时，“哈利·波特”系列八部电影正在第23届上海国际电影节展映，第一部电影《哈利·波特与魔法石》4K修复3D版，定档8月14日在内地重映。   

结果：

关键词：[哈利·波特, 学院, 魔法, 电影, 魔法石, 40岁, 无数, 大型, 青少年, 陪伴]