关键词抽取算法的研究 | 吴良超的学习笔记

标签: 关键词 算法 研究 | 发表时间:2017-10-21 16:24 | 作者:
出处:http://wulc.me

关键词抽取的一般步骤为:

分词–>过滤停止词,得到候选关键词–>从候选关键词中选出文章的关键词

从候选关键词中选出文章的关键词需要通过关键词抽取算法实现,而关键词抽取算法可以根据是否需要人工标注的语料进行训练而分为有监督的提取和无监督的提取。



有监督的提取需要人工标注的语料进行训练,人工预处理的代价较高。而无监督的抽取算法直接利用需要提取关键词的文本即可进行关键词的提取,因此适用性较强。

关键词抽取中无监督的抽取算法可分为三大类:

1)基于统计特征的,如TF-IDF

2)基于词图模型的,如TextRank

3)基于主题模型的,如LDA

本文主要讲述TF-IDF算法、TextRank算法、以及通过组合两者得到的三种新方法,然后通过Java实现这几种方法并比较这几种方法在特定语料库上进行关键词抽取的效果。

TF-IDF算法

TF-IDF(Term Frequency-Inverse Document Frequency)算法是一种基于统计特征的非常经典的算法,通过计算一个词的TF值和IDF值的乘积作为该值的得分,然后根据得分从大到小对词语排序,选择分数高的词语作为关键词。

TF值指词语在文本中出现的频率,如某篇文章分词并过滤停止词后的词语的数量为n,而其中的某个词语w出现的个数为m,则词w的TF值为

IDF值则指词语在整个语料库中的出现的频率大小。这里首先要指出的是TF-IDF算法是针对一个语料库(也就是多篇文档进行)进行关键词提取的算法。假如语料库中共有N篇文档,而出现了词语w的文档数为M。则词w的IDF值为

$TF(w)*IDF(w)$则为词w的TF-IDF值,根据这个值对候选词从大到小排序,选择前n个作为候选关键词即可。

通过Java的实现并不难,主要是利用Java的集合框架Map、List等存储词语的中间得分、以及候选关键词等。

实现的完整代码见:

https://github.com/WuLC/KeywordExtraction/blob/master/src/com/lc/nlp/keyword/algorithm/TFIDF.java

TextRank算法

TextRank算法是借鉴PageRank算法在语言处理中的一个算法,关于PageRank算法可参考这篇文章。无论是PageRank还是TextRank,其关键思想都是重要性传递

以PageRank为例,假如一个大型网站有一个超链接指向了某个小网站,那么小网站的重要性会上升,而上升的量则依据指向它的大网站的重要性。下图所示的就是一个例子:

假设网页A,B原来的重要性为100和9,那么根据他们指向的网页,传递给C、D的重要性分别为53和50。

在TextRank中将上图的网页替换成词语,将网页间的超链接换成词语间的语义关系;假如两个词的距离小于预设的距离,那么就认为这两个词间存在语义关系,否则不存在。这个预设的距离在TextRank算法中被称为同现窗口(co-occurance window)。这样便可构建出一个词的图模型。

但是在实际中应用时我们是无法预先知道网页A、B的重要性的,又或者说假如我们已经知道了网页的重要性,那么也不需要通过算法计算出网页的重要性了。这就成了一个先有鸡还是先有蛋的问题。

PageRank的原始论文提出了解决这个问题的方法,这篇文章中通过具体的例子提到了相关的理论依据,就是幂法求特征向量与初始值无关。具体做法就是,先给每个网页随机附一个初值,然后通过迭代计算直至收敛,理论证明了收敛的值与初始值无关。

同样的,TextRank也采取了相同的方法,就是先随机赋初值,然后通过迭代计算得到每个

词的重要性的得分。词语$V_i$的得分计算公式如下所示:

上式中各符号表示如下

实现的一个关键点在于构建词的图模型,在Java中通过队列实现,队列大小即为同现窗口的大小,移动队列的过程中将队列内部的词语互相连接。连接的形式通过java的Map<String,Set<String>>类型实现,表示指向词语(第一个String)的所有其他词语(Set<String>)的实现的关键代码如下:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

Map<String, Set<String>> words =newHashMap<String, Set<String>>();

Queue<String> que =newLinkedList<String>();

for(String w : wordList)//wordList为候选关键词

{

if(!words.containsKey(w))

{

words.put(w,newHashSet<String>());

}

que.offer(w);// 入队

if(que.size() > coOccuranceWindow)

{

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);

}

}

}

另外一个实现关键点就是判断算法是否收敛,可以认为前后两次计算出来的值小于指定的阈值(一般取值较小,如0.000001)时算法收敛,或者超过设定的最大迭代次数时停止。实现的关键代码如下所示:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

min_diff =0.000001

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

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())

{

String key = entry.getKey();

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

m.put(key,1- d);

for(String other : 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?1: score.get(key))));

}

score = m;



//exit once recurse

if(max_diff <= min_diff)

break;

}

完整的实现代码见:

https://github.com/WuLC/KeywordExtraction/blob/master/src/com/lc/nlp/keyword/algorithm/TextRank.java

综合TextRank 多同现窗口

由于TextRank的同现窗口的大小会影响提取的效果,如下图是同现窗口为2~10的时候评估值为F1值的变化情况。(测试语料

而原始的TextRank算法仅仅是建议该值设为2~10,无法知道对于一篇文章的最优同现窗口,因此本方法会综合TextRank多同现窗口的结果,将一个词语在不同大小的窗口下的得分相加,作为该词的总得分,然后根据总得分对词语排序,选择得分较高的前n个词作为候选关键词 。

该算法的效果与原始的TextRank算法的效果对比如下(测试语料

图中的textrank表示原始的TextRank算法的效果,而multi_window_textrank表示综合了大小为2~10的同现窗口的结果的效果。从图中可知,在提取关键词个数大于4个的时候,该方法的效果要优于原始的TextRank算法,但是F1值的提升幅度不大,并且实际运行的时候,综合多同现窗口的方法花费的时间是原始TextRank算法的14倍左右。

代码的具体实现见:

https://github.com/WuLC/KeywordExtraction/blob/master/src/com/lc/nlp/keyword/algorithm/TextRankWithMultiWin.java

TextRank 与 TF-IDF 综合

考虑词语的IDF值

由于TextRank算法仅考虑文档内部的结构信息,导致一些在各个文档的出现频率均较高且不属于停止词的词语最总的得分较高。原因是没有考虑词语在整个语料库中的权重。因此在TextRank算法得到的每个词的得分基础上,乘上这个词在整个语料库的IDF值,IDF值是TF-IDF算法中的一个概念,该值越大,表示这个词在语料库中出现的次数越少,越能代表该文档。

将词语的TextRank得分乘上这个词的IDF值后作为该词的新得分,然后根据得分从大到小排序,选择得分高的前n个词作为关键词即可。

下面是考虑了词语的IDF值的方法与原始的TextRank算法的效果对比图(测试语料

从图中可知,考虑了词语的IDF值后的方法的效果要优于原始的TextRank算法,运行时间约为TextRank算法的两倍。

完整的代码实现见:

https://github.com/WuLC/KeywordExtraction/blob/master/src/com/lc/nlp/keyword/algorithm/TextRankWithTFIDF.java

TextRank与TF-IDF投票

这种方法也是针对TextRank算法仅考虑文档内部的信息而忽略了文档外部的信息,综合TextRank算法和TF-IDF算法提取出来的结果。

具体的流程为:确定要抽取的关键词个数n,通过TextRank算法和TF-IDF算法对语料库分别提取2n个关键词,选择同时在两个算法得到的结果中出现的词语作为关键词,假如同时出现的词语不足n个,那么剩下的词语从TextRank的结果或TF-IDF的结果中补。

下面是TextRank和TF-IDF投票方法的结果与原始的TextRank算法的结果的对比图(测试语料

从结果可知,两个算法综合投票的方法的效果要优于原始的TextRank算法。运行的时间约为原始的TextRank的两倍。

完整的代码实现见:

https://github.com/WuLC/KeywordExtraction/blob/master/src/com/lc/nlp/keyword/algorithm/TextRankWithTFIDF.java

总结

本文主要讲述了TextRank算法以及对其进行简单改进的三种方法:综合多同现窗口的结果、考虑词语的IDF值、TF-IDF与TextRank共同投票。通过Java实现并比较其效果(评判指标为F1值)。下图是这几个算法的总效果对比图。(测试语料

综合多同现窗口的改进方案后的效果虽然要略优于原始的 TextRank 算法,但是消耗的时间是原始 TextRank 算法的 14 倍左右;综合 TextRank 算法和 TF-IDF 算法后的结果是改进算法后最优的,其次是考虑 TextRank 提取出的关键词的 IDF 值的改进方案,两者的效果均要优于原始的 TextRank 算法, 消耗的时间也比原始的 TextRank 算法要多。

因此,若需要对单篇文档提取的关键词时,可采用原始的TextRank算法或综合多同现窗口的方法, 假如对提取效果的要求较高且对时间要求不高时,可以采用综合多同现窗口的方法, 反之直接采用原始的TextRank算法。如果需要对多文档进行关键词抽取时,四种方法都可以采用,但是考虑提取的效果以及消耗的时间, 建议使用 TextRank 算法和 TF-IDF 算法综合投票的方法或 TextRank 结合IDF值的方法,并且根据着重点是时间还是提取的精度,选择 TF-IDF 算法综合投票的方法或 TextRank 结合 IDF 值的方法。

上文提到的所有代码的地址为:https://github.com/WuLC/KeywordExtraction

除了算法的实现,还包括了语料库的导入、F1值的计算方法的实现等。

相关 [关键词 算法 研究] 推荐:

关键词抽取算法的研究 | 吴良超的学习笔记

- -
分词–>过滤停止词,得到候选关键词–>从候选关键词中选出文章的关键词. 从候选关键词中选出文章的关键词需要通过关键词抽取算法实现,而关键词抽取算法可以根据是否需要人工标注的语料进行训练而分为有监督的提取和无监督的提取. 有监督的提取需要人工标注的语料进行训练,人工预处理的代价较高. 而无监督的抽取算法直接利用需要提取关键词的文本即可进行关键词的提取,因此适用性较强.

关键词研究可以为你带来收入

- - 译言-每日精品译文推荐
你的博客可能没法把你带上福布斯杂志封面,但大多数人都可以靠博客获得一份不错的收入. 你需要的努力程度与职业道德与做别的工作并无差别. 靠博客赚钱你需要想在前头,而不必工作了两年之后才发现你做的是个不赚钱的活计. 如果你已经开始经营博客,别担心,本文将会帮你从博客里挤出点钞票来. 而这一切,还是来自于关键词研究.

关键词权重计算算法:TF-IDF

- - 标点符
TF-IDF(Term Frequency–Inverse Document Frequency)是一种用于资讯检索与文本挖掘的常用加权技术. TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度. 字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降.

TextRank算法提取关键词和摘要 - 小昇的博客 | Xs Blog

- -
提到从文本中提取关键词,我们第一想到的肯定是通过计算词语的TF-IDF值来完成,简单又粗暴. 但是由于 TF-IDF 的结构过于简单,有时提取关键词的效果会很不理想. 本文将介绍一个由 Google 著名的网页排序算法PageRank改编而来的算法——TextRank,它利用图模型来提取文章中的关键词.

研究人员破解W3C XML加密标准算法

- 远 - Solidot
在芝加哥举行的ACM计算机与通信安全会议上,两位德国研究人员宣称他们找到了方法破解XML文档中的加密数据,XML文档使用的是W3C制定的XML加密标准. XML加密作为服务器到服务器Web服务连接一部分而得到广泛使用,其加密技术是基于密码块链接,将安全信息和非敏感信息混合起来. 例如,在基于XML的订单中加密用于支付的信用卡信息.

MIT教授研究出治交通拥堵的算法

- - 36氪 | 关注互联网创业
交通拥堵堵的不仅仅是车也堵心. 把头伸出车窗外,看着前面一望无际一动不动的长龙,每个人都恨不得自己长了一双翅膀. 不过,在我们进化出翅膀之前,麻省理工学院的教授Berthold Horn已经在试图去缓解一下这种状况. 他想出了一种控制算法,让车辆利用这种算法可以以近乎完美的节奏与周边的车辆保持距离的一致.

现在有没有帮助建筑设计的app,或者程序或是研究出来的算法?

- - 知乎每日精选
建筑设计的自动化,早先上课听人讲过,但总的来说不靠谱. 1是多数情况下都是直接拿现成模式改改,根本不用算. 2是情况复杂,根本没有靠谱的算法. 功能上1 的情况更多,实际上我们这行业人流,空间,位置这些根本没啥可算的,规范和经验都定的很死,不值得一算. 而形态立面这些基本上又无迹可寻,2的情况多,完全看领导的个人口味,也没啥蒜头.

官方媒体谴责新浪微博过滤关键词

- ivan - Solidot
官方媒体新华社-中国网事在腾讯微博发帖谴责新浪微博,指责新浪微博过滤关键词“达芬奇”. 中国网事称,“新浪微博为何助纣为虐. 近一段时间以来,凡是在新浪微博上发布的有关“达芬奇”的帖子都无端被“封杀”:帖子只有自己能看见,而粉丝和公屏都不显示,其中包括新华社中国网事昨日发布的有关帖子. 经过有关交涉后,该微博于12日下午六时左右暂时恢复“达芬奇”这个它们设定的敏感词.

Tango 的蛛丝马迹:关键词是诺基亚,低价…

- SotongDJ - 爱范儿 · Beats of Bits
直到今天为止,关于微软 Windows Phone 演进版本的信息仍然不多,大概的关键词是这么几个:. Mango :今年秋天的重要版本,有数百项更新,已经进入 RTM 阶段. Tango:在 Mango 之后的版本. Apollo:Windows Phone 8 的开发代号. 微软这次的习惯是,开发代号皆以“o”结尾(包括之前的 NoDo).