TextRank算法原理简析、代码实现
前⾔—PageRank
注：PageRank原理另⾏查询
  在介绍TextRank前，我想先给⼤家介绍下PageRank，实质上个⼈认为可以把TextRank当做PageRank2.0。
  ⾕歌的两位创始⼈的佩奇和布林，借鉴了学术界评判学术论⽂重要性的通⽤⽅法，“那就是看论⽂的引⽤次数”。由此想到⽹页的重要性也可以根据这种⽅法来评价。于是PageRank的核⼼思想就诞⽣了：
TextRank算法
TextRank 算法是⼀种⽤于⽂本的基于图的排序算法。其基本思想来源于⾕歌的 PageRank算法, 通过把⽂本分割成若⼲组成单元(单词、句⼦)并建⽴图模型, 利⽤投票机制对⽂本中的重要成分进⾏排序, 仅利⽤单篇⽂档本⾝的信息即可实现关键词提取、⽂摘。和 LDA、HMM 等模型不同, TextRank不需要事先
对多篇⽂档进⾏学习训练, 因其简洁有效⽽得到⼴泛应⽤。
TextRank ⼀般模型可以表⽰为⼀个有向有权图 G =(V, E), 由点集合 V和边集合 E 组成, E 是V ×V的⼦集。图中任两点 Vi , Vj 之间边的权重为 wji , 对于⼀个给定的点 Vi, In(Vi) 为 指 向 该 点 的 点 集 合 , Out(Vi) 为点 Vi 指向的点集合。点 Vi
的得分定义如下:
公式的意思：TextRank中⼀个单词\large i的权重取决于与在\large i前⾯的各个点\large j组成的\large (j,i)这条边的权重，以及\large j这个点到其他其他边的权重之和
其中, d 为阻尼系数, 取值范围为 0 到 1, 代表从图中某⼀特定点指向其他任意点的概率, ⼀般取值为 0.85。使⽤TextRank 算法计算图中各点的得分时, 需要给图中的点指定任意的初值, 并递归计算直到收
敛, 即图中任意⼀点的误差率⼩于给定的极限值时就可以达到收敛, ⼀般该极限值取 0.0001。（个⼈觉得算法领域很多公式的可解释性不强，⼤多是为了解决某些限定条件，⽽⼈为选择的⽐较好的优化⽅式，⽐如阻尼系数d,(这个d通常取0.85实践出来的，好像没什么数学解释)，实质上是为了给数据做⼀个平滑处理，实质是为了替代为零项）
关键词抽取的任务就是从⼀段给定的⽂本中⾃动抽取出若⼲有意义的词语或词组。TextRank算法是利⽤局部词汇之间关系（共现窗⼝）对后续关键词进⾏排序，直接从⽂本本⾝抽取。其主要步骤如下：
（1）把给定的⽂本T按照完整句⼦进⾏分割，即
（2）对于每个句⼦，进⾏分词和词性标注处理，并过滤掉停⽤词，只保留指定词性的单词，如名词、动词、形容词，即
，其中是保留后的候选关键词。
（3）构建候选关键词图G = (V,E)，其中V为节点集，由（2）⽣成的候选关键词组成，然后采⽤共现关系（co-occurrence）构造任两点之间的边，两个节点之间存在边仅当它们对应的词汇在长度为K的窗⼝中共现，K表⽰窗⼝⼤⼩，即最多共现K个单词。
（4）根据上⾯公式，迭代传播各节点的权重，直⾄收敛。
（5）对节点权重进⾏倒序排序，从⽽得到最重要的T个单词，作为候选关键词。
（6）由（5）得到最重要的T个单词，在原始⽂本中进⾏标记，若形成相邻词组，则组合成多词关键词。例如，⽂本中有句
⼦“Matlab code for plotting ambiguity function”，如果“Matlab”和“code”均属于候选关键词，则组合成“Matlab code”加⼊关键词序列。
python编程实现
因为在了解textrank的时候，参考了jieba分词和TextRank4zh这2个开源库的写法。但是两者⽆论写法和运算规则都有很⼤出⼊，结合公式来说本⼈觉得jieba做的更符合公式，TextRank4zh更具有准确性，因为TextRank4zh在公式上⾯做了⼀定的优化。
Jieba分词TextRank：
例如： [‘有’,‘媒体’, ‘曝光’,‘⾼圆圆’, ‘和’, ‘赵⼜廷’,‘现⾝’, ‘台北’, ‘桃园’,‘机场’,‘的’, ‘照⽚’]
对于‘媒体‘这个单词，就有（‘媒体’, ‘曝光’）、（‘媒体’, ‘圆’）、（‘媒体’, ‘和’）、（‘媒体’, ‘赵⼜廷’）4条边，且每条边权值为1，当这条边在之后再次出现时，权值再在基础上加1.
<span ><code>def textrank(self, sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v'), withFlag=False):
self.pos_filt = frozenset(allowPOS)
# 定义⽆向有权图
g = UndirectWeightedGraph()
# 定义共现词典
cm = defaultdict(int)
# 分词
words = kenizer.cut(sentence))
# 依次遍历每个词
for i, wp in enumerate(words):
# 词i 满⾜过滤条件
if self.pairfilter(wp):
# 依次遍历词i 之后窗⼝范围内的词
for j in xrange(i + 1, i + self.span):
# 词j 不能超出整个句⼦
if j >= len(words):
break
# 词j不满⾜过滤条件，则跳过
if not self.pairfilter(words[j]):
continue
# 将词i和词j作为key，出现的次数作为value，添加到共现词典中
if allowPOS and withFlag:
cm[(wp, words[j])] += 1
else:
cm[(wp.word, words[j].word)] += 1
# 依次遍历共现词典的每个元素，将词i，词j作为⼀条边起始点和终⽌点，共现的次数作为边的权重
for terms, w in cm.items():
g.addEdge(terms[0], terms[1], w)
# 运⾏textrank算法
nodes_rank = g.rank()
# 根据指标值进⾏排序
if withWeight:
tags = sorted(nodes_rank.items(), key=itemgetter(1), reverse=True)
else:
tags = sorted(nodes_rank, key=nodes_rank.__getitem__, reverse=True)
# 输出topK个词作为关键词
if topK:
return tags[:topK]
else:
return tags
</code></span>
关于有向图的数据结构：
<span ><code>def addEdge(self, start, end, weight):
# use a tuple (start, end, weight) instead of a Edge object
</code></span>
关于TextRank的⼿写：
<span ><code>def rank(self):
ws = defaultdict(float)
outSum = defaultdict(float)
wsdef = 1.0 / (aph) or 1.0)
# 初始化各个结点的权值
# 统计各个结点的出度的次数之和
for n, out aph.items():
ws[n] = wsdef
outSum[n] = sum((e[2] for e in out), 0.0)
# this line for build stable iteration
sorted_keys = aph.keys())
# 遍历若⼲次
for x in xrange(10):  # 10 iters
# 遍历各个结点
for n in sorted_keys:
s = 0
# 遍历结点的⼊度结点
for e aph[n]:
# 将这些⼊度结点贡献后的权值相加
# 贡献率 = ⼊度结点与结点n的共现次数 / ⼊度结点的所有出度的次数                s += e[2] / outSum[e[1]] * ws[e[1]]
# 更新结点n的权值
ws[n] = (1 - self.d) + self.d * s
(min_rank, max_rank) = (sys.float_info[0], sys.float_info[3])
# 获取权值的最⼤值和最⼩值
for w in itervalues(ws):
if w < min_rank:
min_rank = w
if w > max_rank:
max_rank = w
# 对权值进⾏归⼀化
for n, w in ws.items():
# to unify the weights, don't *100.
ws[n] = (w - min_rank / 10.0) / (max_rank - min_rank / 10.0)
return ws
</code></span>
ank完整源码如下：
<span ><code>#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import sys
from operator import itemgetter
from collections import defaultdict
import jieba.posseg
from .tfidf import KeywordExtractor
from .._compat import *
class UndirectWeightedGraph:
d = 0.85
def __init__(self):
def addEdge(self, start, end, weight):网页float是什么意思
# use a tuple (start, end, weight) instead of a Edge object
def rank(self):
ws = defaultdict(float)
outSum = defaultdict(float)
wsdef = 1.0 / (aph) or 1.0)
for n, out aph.items():
ws[n] = wsdef
outSum[n] = sum((e[2] for e in out), 0.0)
# this line for build stable iteration
sorted_keys = aph.keys())
for x in xrange(10):  # 10 iters
for n in sorted_keys:
s = 0
for e aph[n]:
s += e[2] / outSum[e[1]] * ws[e[1]]
ws[n] = (1 - self.d) + self.d * s
(min_rank, max_rank) = (sys.float_info[0], sys.float_info[3])
for w in itervalues(ws):
if w < min_rank:
min_rank = w
if w > max_rank:
max_rank = w
for n, w in ws.items():
# to unify the weights, don't *100.
ws[n] = (w - min_rank / 10.0) / (max_rank - min_rank / 10.0)
return ws
class TextRank(KeywordExtractor):
def __init__(self):
self.stop_words = self.py()
self.pos_filt = frozenset(('ns', 'n', 'vn', 'v'))
self.span = 5
def pairfilter(self, wp):
return (wp.flag in self.pos_filt and len(wp.word.strip()) >= 2
and wp.word.lower() not in self.stop_words)
def textrank(self, sentence, topK=20, withWeight=False, allowPOS=('ns', 'n', 'vn', 'v'), withFlag=False):        """
Extract keywords from sentence using TextRank algorithm.
Parameter:
- topK: return how many top keywords. `None` for all possible words.
- withWeight: if True, return a list of (word, weight);
if False, return a list of words.
- allowPOS: the allowed POS list eg. ['ns', 'n', 'vn', 'v'].
if the POS of w is not in this list, it will be filtered.
- withFlag: if True, return a list of pair(word, weight) like posseg.cut
if False, return a list of words
"""
self.pos_filt = frozenset(allowPOS)
g = UndirectWeightedGraph()
cm = defaultdict(int)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。