文档章节

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

x
 xinwenzx8
发布于 2016/04/29 14:55
字数 1370
阅读 109
收藏 0

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

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

PageRank的计算公式:

 

bubuko.com,布布扣

正规的TextRank公式

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

bubuko.com,布布扣

但是很明显我只想计算关键字,如果把一个单词视为一个句子的话,那么所有句子(单词)构成的边的权重都是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]

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

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

获取下载地址   java大数据 高并发 系统框架 springmvc mybatis Bootstrap html5 shiro maven SSM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

然后开始迭代:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
         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]

 

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

© 著作权归作者所有

x
粉丝 0
博文 3
码字总数 3936
作品 0
福州
私信 提问

暂无文章

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
53分钟前
3
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
3
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部