TextRank算法提取关键词的Java实现

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

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

PageRank的计算公式:

正规的TextRank公式

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

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

另外,如果你想提取关键句(自动摘要)的话,请参考姊妹篇《TextRank算法自动摘要的Java实现》。

TextRank的Java实现

先看看测试数据:

程序员(英文Programmer)是从事程序开发、维护的专业人员。一般将程序员分为程序设计人员和程序编码人员,但两者的界限并不非常清楚,特别是在中国。软件从业人员分为初级程序员、高级程序员、系统分析员和项目经理四大类。
我取出了百度百科关于“程序员”的定义作为测试用例,很明显,这段定义的关键字应当是“程序员”并且“程序员”的得分应当最高。

首先对这句话分词,这里可以借助各种分词项目,比如Ansj分词,得出分词结果:

[程序员/n, (, 英文/nz, programmer/en, ), 是/v, 从事/v, 程序/n, 开发/v, 、/w, 维护/v, 的/uj, 专业/n, 人员/n, 。/w, 一般/a, 将/d, 程序员/n, 分为/v, 程序/n, 设计/vn, 人员/n, 和/c, 程序/n, 编码/n, 人员/n, ,/w, 但/c, 两者/r, 的/uj, 界限/n, 并/c, 不/d, 非常/d, 清楚/a, ,/w, 特别/d, 是/v, 在/p, 中国/ns, 。/w, 软件/n, 从业/b, 人员/n, 分为/v, 初级/b, 程序员/n, 、/w, 高级/a, 程序员/n, 、/w, 系统/n, 分析员/n, 和/c, 项目/n, 经理/n, 四/m, 大/a, 类/q, 。/w]

然后去掉里面的停用词,这里我去掉了标点符号、常用词、以及“名词、动词、形容词、副词之外的词”。得出实际有用的词语:

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

之后建立两个大小为5的窗口,每个单词将票投给它身前身后距离5以内的单词:

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

然后开始迭代投票:

for (int i = 0; i < max_iter; ++i)
{
Map<String, Float> m = new HashMap<String, Float>();
float max_diff = 0;
for (Map.Entry<String, Set<String>> entry : words.entrySet())
{
String key = entry.getKey();
Set<String> value = entry.getValue();
m.put(key, 1 – d);
for (String other : value)
{
int size = words.get(other).size();
if (key.equals(other) || size == 0) continue;
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) break;
}

排序后的投票结果:

[程序员=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]

程序员果然荣登榜首,并且分数也有区分度,嗯,勉勉强强。

开源项目地址

本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html

目前能够提供分词、词性标注、命名实体识别、关键字提取、短语提取、自动摘要、自动推荐,依存关系、句法树等功能。

原文:http://www.hankcs.com/nlp/textrank-algorithm-to-extract-the-keywords-java-implementation.html

 

package com.hankcs.textrank;

import org.ansj.domain.Term;
import org.ansj.splitWord.analysis.ToAnalysis;

import java.util.*;

/**
* @author hankcs
*/
public class TextRankKeyword
{

public static final int nKeyword = 10;
/**
* 阻尼系数(DampingFactor),一般取值为0.85
*/
static final float d = 0.85f;
/**
* 最大迭代次数
*/
static final int max_iter = 200;
static final float min_diff = 0.001f;

public TextRankKeyword()
{

// jdk bug : Exception in thread “main” java.lang.IllegalArgumentException: Comparison method violates its general contract!
System.setProperty(“java.util.Arrays.useLegacyMergeSort”, “true”);

}

public String getKeyword(String title, String content)
{

List<Term> termList = ToAnalysis.parse(title + content);
//        System.out.println(termList);
List<String> wordList = new ArrayList<String>();
for (Term t : termList)
{

if (shouldInclude(t))
{

wordList.add(t.getName());

}

}
//        System.out.println(wordList);
Map<String, Set<String>> words = new HashMap<String, Set<String>>();
Queue<String> que = new LinkedList<String>();
for (String w : wordList)
{

if (!words.containsKey(w))
{

words.put(w, new HashSet<String>());

}
que.offer(w);
if (que.size() > 5)
{

que.poll();

}

for (String w1 : que)
{

for (String w2 : que)
{

if (w1.equals(w2))
{

continue;

}

words.get(w1).add(w2);
words.get(w2).add(w1);

}

}

}
//        System.out.println(words);
Map<String, Float> score = new HashMap<String, Float>();
for (int i = 0; i < max_iter; ++i)
{

Map<String, Float> m = new HashMap<String, Float>();
float max_diff = 0;
for (Map.Entry<String, Set<String>> entry : words.entrySet())
{

String key = entry.getKey();
Set<String> value = entry.getValue();
m.put(key, 1 – d);
for (String other : value)
{

int size = words.get(other).size();
if (key.equals(other) || size == 0) continue;
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) break;

}
List<Map.Entry<String, Float>> entryList = new ArrayList<Map.Entry<String, Float>>(score.entrySet());
Collections.sort(entryList, new Comparator<Map.Entry<String, Float>>()
{

@Override
public int compare(Map.Entry<String, Float> o1, Map.Entry<String, Float> o2)
{

return (o1.getValue() – o2.getValue() > 0 ? -1 : 1);

}

});
//        System.out.println(entryList);
String result = “”;
for (int i = 0; i < nKeyword; ++i)
{

result += entryList.get(i).getKey() + ‘#’;

}
return result;

}

public static void main(String[] args)
{

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

}

class Document
{

Map<String, Set<String>> words;
Map<String, Float> score;

}

/**
* 是否应当将这个term纳入计算,词性属于名词、动词、副词、形容词
* @param term
* @return 是否应当
*/
public boolean shouldInclude(Term term)
{

if (
term.getNatrue().natureStr.startsWith(“n”) ||
term.getNatrue().natureStr.startsWith(“v”) ||
term.getNatrue().natureStr.startsWith(“d”) ||
term.getNatrue().natureStr.startsWith(“a”)
)
{

// TODO 你需要自己实现一个停用词表
//            if (!StopWordDictionary.contains(term.getName()))
//            {

return true;
//
}

}

return false;

}

}

Leave a Reply