使用TextRank算法为文本生成关键字和摘要

TextRank算法基于PageRank,用于为文本生成关键字和摘要。

目录[-]

TextRank算法基于PageRank,用于为文本生成关键字和摘要。其论文是:

Mihalcea R, Tarau P. TextRank: Bringing order into texts[C]. Association for Computational Linguistics, 2004.

先从PageRank讲起。

PageRank

PageRank最开始用来计算网页的重要性。整个www可以看作一张有向图图,节点是网页。如果网页A存在到网页B的链接,那么有一条从网页A指向网页B的有向边。

构造完图后,使用下面的公式:

S(Vi)是网页i的中重要性(PR值)。d是阻尼系数,一般设置为0.85。In(Vi)是存在指向网页i的链接的网页集合。Out(Vj)是网页j中的链接存在的链接指向的网页的集合。|Out(Vj)|是集合中元素的个数。 PageRank需要使用上面的公式多次迭代才能得到结果。初始时,可以设置每个网页的重要性为1。上面公式等号左边计算的结果是迭代后网页i的PR值,等号右边用到的PR值全是迭代前的。 举个例子:

上图表示了三张网页之间的链接关系,直觉上网页A最重要。可以得到下面的表:

结束\起始

A

B

C

A

0

1

1

B

0

0

0

C

0

0

0

横栏代表其实的节点,纵栏代表结束的节点。若两个节点间有链接关系,对应的值为1。 根据公式,需要将每一竖栏归一化(每个元素/元素之和),归一化的结果是:

结束\起始

A

B

C

A

0

1

1

B

0

0

0

C

0

0

0

上面的结果构成矩阵M。我们用matlab迭代100次看看最后每个网页的重要性:

?

M = [0 1 1 
    0 0 0
    0 0 0];

PR = [1; 1 ; 1];

for iter = 1:100
    PR = 0.15 + 0.85*M*PR;
    disp(iter);
    disp(PR);
end

运行结果(省略部分):

?

......

    95

    0.4050
    0.1500
    0.1500

    96

    0.4050
    0.1500
    0.1500

    97

    0.4050
    0.1500
    0.1500

    98

    0.4050
    0.1500
    0.1500

    99

    0.4050
    0.1500
    0.1500

   100

    0.4050
    0.1500
    0.1500

最终A的PR值为0.4050,B和C的PR值为0.1500。 如果把上面的有向边看作无向的(其实就是双向的),那么:

?

M = [0 1 1 
    0.5 0 0
    0.5 0 0];

PR = [1; 1 ; 1];

for iter = 1:100
    PR = 0.15 + 0.85*M*PR;
    disp(iter);
    disp(PR);
end

运行结果(省略部分):

?

.....

    98

    1.4595
    0.7703
    0.7703

    99

    1.4595
    0.7703
    0.7703

   100

    1.4595
    0.7703
    0.7703

依然能判断出A、B、C的重要性。

使用TextRank提取关键字

将原文本拆分为句子,在每个句子中过滤掉停用词(可选),并只保留指定词性的单词(可选)。由此可以得到句子的集合和单词的集合。

每个单词作为pagerank中的一个节点。设定窗口大小为k,假设一个句子依次由下面的单词组成:

w1, w2, w3, w4, w5, ..., wn

w1, w2, ..., wk、w2, w3, ...,wk+1、w3, w4, ...,wk+2等都是一个窗口。在一个窗口中的任两个单词对应的节点之间存在一个无向无权的边。

基于上面构成图,可以计算出每个单词节点的重要性。最重要的若干单词可以作为关键词。

使用TextRank提取关键短语

参照“使用TextRank提取关键词”提取出若干关键词。若原文本中存在若干个关键词相邻的情况,那么这些关键词可以构成一个关键短语。 例如,在一篇介绍“支持向量机”的文章中,可以找到三个关键词支持、向量、机,通过关键短语提取,可以得到支持向量机。

使用TextRank提取摘要

将每个句子看成图中的一个节点,若两个句子之间有相似性,认为对应的两个节点之间有一个无向有权边,权值是相似度。

通过pagerank算法计算得到的重要性最高的若干句子可以当作摘要。 论文中使用下面的公式计算两个句子Si和Sj的相似度:

分子是在两个句子中都出现的单词的数量。|Si|是句子i的单词数。 由于是有权图,PageRank公式略做修改:

实现TextRank

因为要用测试多种情况,所以自己实现了一个基于Python 2.7的TextRank针对中文文本的库TextRank4ZH。位于: https://github.com/someus/TextRank4ZH 下面是一个例子:

?

#-*- encoding:utf-8 -*-

import codecs
from textrank4zh import TextRank4Keyword, TextRank4Sentence

text = codecs.open('./text/01.txt', 'r', 'utf-8').read()
tr4w = TextRank4Keyword(stop_words_file='./stopword.data')  # 导入停止词

#使用词性过滤,文本小写,窗口为2
tr4w.train(text=text, speech_tag_filter=True, lower=True, window=2)  

print '关键词:'
# 20个关键词且每个的长度最小为1
print '/'.join(tr4w.get_keywords(20, word_min_len=1))  

print '关键短语:'
# 20个关键词去构造短语,短语在原文本中出现次数最少为2
print '/'.join(tr4w.get_keyphrases(keywords_num=20, min_occur_num= 2))  
     
tr4s = TextRank4Sentence(stop_words_file='./stopword.data')

# 使用词性过滤,文本小写,使用words_all_filters生成句子之间的相似性
tr4s.train(text=text, speech_tag_filter=True, lower=True, source = 'all_filters')

print '摘要:'
print '\n'.join(tr4s.get_key_sentences(num=3)) # 重要性最高的三个句子

运行结果如下:

?

关键词:
媒体/高圆圆/微/宾客/赵又廷/答谢/谢娜/现身/记者/新人/北京/博/展示/捧场/礼物/张杰/当晚/戴/酒店/外套
关键短语:
微博
摘要:
中新网北京12月1日电(记者 张曦) 30日晚,高圆圆和赵又廷在京举行答谢宴,诸多明星现身捧场,其中包括张杰(微博)、谢娜(微博)夫妇、何炅(微博)、蔡康永(微博)、徐克、张凯丽、黄轩(微博)等
高圆圆身穿粉色外套,看到大批记者在场露出娇羞神色,赵又廷则戴着鸭舌帽,十分淡定,两人快步走进电梯,未接受媒体采访
记者了解到,出席高圆圆、赵又廷答谢宴的宾客近百人,其中不少都是女方的高中同学

另外, jieba分词提供的基于TextRank的关键词提取工具。 snownlp也实现了关键词提取和摘要生成。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2016-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JackieZheng

Java豆瓣电影爬虫——使用Word2Vec分析电影短评数据

  在上篇实现了电影详情和短评数据的抓取。到目前为止,已经抓了2000多部电影电视以及20000多的短评数据。   数据本身没有规律和价值,需要通过分析提炼成知...

3268
来自专栏海天一树

结巴中文分词介绍

Python中分分词工具很多,包括盘古分词、Yaha分词、Jieba分词、清华THULAC等。它们的基本用法都大同小异,这里先了解一下结巴分词。

1144
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

13行代码实现最快速最高效的积分图像算法。

  研究图像到一定程度的人,应该都对积分图像有所了解,大家在百度或者google中都可以搜索到大量的相关博客,我这里不做多介绍。用积分图也确实能解决很多实际的问...

2978
来自专栏闪电gogogo的专栏

压缩感知重构算法之子空间追踪(SP)

SP的提出时间比CoSaMP提出时间稍晚一些,但和压缩采样匹配追踪(CoSaMP)的方法几乎是一样的。SP与CoSaMP主要区别在于“In each itera...

1857
来自专栏王杰的专栏

跳点搜索算法JPS及其优化

寻路算法用途众多,例如在游戏和地图中。A*算法已经众所周知,对于其优化也是层出不穷,然而性能并没有取得突破性进展。本文介绍一种跳点搜索算法JPS以及其四个优化算...

5791
来自专栏人工智能

用Pandas在Python中可视化机器学习数据

您必须了解您的数据才能从机器学习算法中获得最佳结果。

3076
来自专栏AI启蒙研究院

从一个双控开关思考神经网络(上)

692
来自专栏小樱的经验随笔

“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&&源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp

黑白图像直方图 发布时间: 2017年7月9日 18:30   最后更新: 2017年7月10日 21:08   时间限制: 1000ms   内存限制: 12...

2945
来自专栏数据科学与人工智能

【算法】TextRank算法为文本生成关键字和摘要

TextRank算法基于PageRank,用于为文本生成关键字和摘要。其论文是:

712
来自专栏闪电gogogo的专栏

压缩感知重构算法之压缩采样匹配追踪(CoSaMP)

压缩采样匹配追踪(CompressiveSampling MP)是D. Needell继ROMP之后提出的又一个具有较大影响力的重构算法。CoSaMP也是对OM...

24610

扫码关注云+社区