Java算法 关键字提取 java从文章中提取关键词

谈到自动摘要算法，TF是最常见和最容易实现的-IDF，但感觉TF-IDF效果一般，不如Textrank好。

Textrank 受GooglePagerank算法的启发，文本中句子设计的权重算法的目标是自动摘要。它利用投票的原则，让每个单词给邻居(术语称窗口) 投赞成票，票的权重取决于自己的票数。这是一个“先有鸡还是先有蛋”的悖论，Pagerank通过矩阵迭代收敛解决了这个悖论。Textrank也是 不例外：

Pagerank的计算公式：

正式Textrank公式

在Pagerank公式的基础上，正式的Textrank公式引入了边权值的概念，代表了两句话的相似性。

但很明显，我只想计算关键字。如果把一个单词当成一个句子，所有句子(单词)构成的边缘的权重都是0(没有交集，没有相似性)，所以分子分母的权重w约掉了，算法退化为Pagerank。因此，在这里称关键词提取算法为Pagerank并不过分。

另外，如果要提取关键句(自动摘要)，请参考姐妹文章《Textrank算法自动摘要Java实现》。

TextrankJava实现

先看测试数据：

程序员（英语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以内的单词:

{开发=[专业， 程序员, 维护, 英文, 程序, 人员],

软件=程序员， 分为, 界限, 高级, 中国, 特别, 人员],

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

分析员=[程序员， 系统, 项目, 经理, 高级],

维护=[专业， 开发, 程序员, 分为, 英文, 程序, 人员],

系统=[程序员， 分析员, 项目, 经理, 分为, 高级],

项目=[程序员， 分析员, 系统, 经理, 高级],

经理=[程序员， 分析员, 系统, 项目],

分为=[专业， 软件, 设计, 程序员, 维护, 系统, 高级, 程序, 中国, 特别, 人员],

英语=[专业， 开发, 程序员, 维护, 程序],

程序=[专业， 开发, 设计, 程序员, 编码, 维护, 界限, 分为, 英文, 特别, 人员],

特别是=[软件， 编码, 分为, 界限, 程序, 中国, 人员],

专业=[开发， 程序员, 维护, 分为, 英文, 程序, 人员],

设计=[程序员， 编码, 分为, 程序, 人员],

编码=[设计， 界限, 程序, 中国, 特别, 人员],

界限=[软件， 编码, 程序, 中国, 特别, 人员],

高级=[程序员， 软件, 分析员, 系统, 项目, 分为, 人员],

中国=[程序员， 软件, 编码, 分为, 界限, 特别, 人员],

人员=[开发， 程序员, 软件, 维护, 分为, 程序, 特别, 专业, 设计, 编码, 界限, 高级, 中国]}

开始迭代投票：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

for(inti=0;i<max_iter;++i)

{

Map<String,Float>m=newHashMap<String,Float>();

floatmax_diff=0;

for(Map.Entry<String,Set<String>>entry:words.entrySet())

{

Stringkey=entry.getKey();

Set<String>value=entry.getValue();

m.put(key,1-d);

for(Stringother:value)

{

intsize=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.924977，

人员=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]

 

程序员真的是榜首，分数也有区别，嗯，勉强。