TextRank算法关键词提取
参考论⽂：Rada Mihalcea《TextRank：Bring Order into texts》。
TextRank将⽂本中的语法单元视作图中的节点，如果两个语法单元存在⼀定语法关系（例如共现），则这两个语法单元在图中就会有⼀条边相互连接，通过⼀定的迭代次数，最终不同的节点会有不同的权重，权重⾼的语法单元可以作为关键词。
节点的权重不仅依赖于它的⼊度结点，还依赖于这些⼊度结点的权重，⼊度结点越多，⼊度结点的权重越⼤，说明这个结点的权重越⾼；任两点 Vi , Vj 之间边的权重为 wji , 对于⼀个给定的点 Vi, in(Vi) 为 指 向 该 点 的 点 集 合 , Out(Vi) 为点 Vi 指向的点集合。
TextRank迭代计算公式为：
其中, d 为阻尼系数, 取值范围为 0 到 1, 代表从某⼀特定点指向其他任意点的概率, ⼀般取值为 0.85。使⽤TextRank 算法计算各点的得分时, 需要给图中的点指定任意的初值, 并递归计算直到收敛, 即任意⼀点的误差率⼩于给定的极限值时就可以达到收敛, ⼀般该极限值取
0.0001。算法通⽤流程：
TextRank⽤于"关键词抽取"：
1. 预处理，⾸先进⾏分词和词性标注，将单个word作为结点添加到图中；
2. 设置语法过滤器，将通过语法过滤器的词汇添加到图中；出现在⼀个窗⼝中的词汇之间相互形成⼀条边；
3. 基于上述公式，迭代直⾄收敛；⼀般迭代20-30次，迭代阈值设置为0.0001；
4. 根据顶点的分数降序排列，并输出指定个数的词汇作为可能的关键词；
5. 后处理，如果两个词汇在⽂本中前后连接，那么就将这两个词汇连接在⼀起，作为关键短语；
⾸先定义⼀个⽆向有权图，然后对句⼦进⾏分词；依次遍历分词结果，如果某个词 i 满⾜过滤条件（词性在词性过滤集合中，并且词的长度⼤于等于2，并且词不是停⽤词），然后将这个词之后窗⼝长度为5范围内的词 j（这些词也需要满⾜过滤条件），将它们两两（词i和词j）作为key，出现的次数作为value，添加到共现词典中；
然后，依次遍历共现词典，将词典中的每个元素，key = （词i，词j），value = 词i和词j出现的次数，其中词i，词j作为⼀条边起始点和终⽌点，共现的次数作为边的权重，添加到之前定义的⽆向有权图中。
然后对这个⽆向有权图进⾏迭代运算textrank算法，最终经过若⼲次迭代后，算法收敛，每个词都对应⼀个指标值；
如果设置了权重标志位，则根据指标值值对⽆向有权图中的词进⾏降序排序，最后输出topK个词作为关键词；
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
其中，TextRank是为TextRank算法抽取关键词所定义的类。类在初始化时，默认加载了分词函数和词性
标注函数tokenizer = postokenizer = jieba.posseg.dt、停⽤词表stop_words = self.py()、词性过滤集合pos_filt = frozenset(('ns', 'n', 'vn', 'v'))，窗⼝span = 5，(("ns", "n", "vn", "v"))表⽰词性为地名、名词、动名词、动词。
其中，⽆向有权图的的定义及实现是在UndirectWeightedGraph类中实现的。根据UndirectWeightedGraph类的初始化函数__init__，我们可以发现，所谓的⽆向有权图就是⼀个词典，词典的key是后续要添加的词，词典的value，则是⼀个由（起始点，终⽌点，边的权重）构成的三元组所组成的列表，表⽰以这个词作为起始点的所有的边。
⽆向有权图添加边的操作是在addEdge函数中完成的，因为是⽆向图，所以我们需要依次将start作为起始点，end作为终⽌点，然后再将start作为终⽌点，end作为起始点，这两条边的权重是相同的。
def addEdge(self, start, end, weight):
# use a tuple (start, end, weight) instead of a Edge object
执⾏textrank算法迭代是在rank函数中完成的。
⾸先对每个结点赋予相同的权重，以及计算出该结点的所有出度的次数之和；
然后迭代若⼲次，以确保得到稳定的结果；
在每⼀次迭代中，依次遍历每个结点；对于结点n，⾸先根据⽆向有权图得到结点n的所有⼊度结点（对于⽆向有权图，⼊度结点与出度结点是相同的，都是与结点n相连的结点），在前⾯我们已经计算出这个⼊度结点的所有出度的次数，⽽它对于结点n的权值的贡献等于它本⾝的权值 乘以 它与结点n的共现次数 / 这个结点的所有出度的次数 ，将各个⼊度结点得到的权值相加，再乘以⼀定的阻尼系数，即可得到结点n的权值；
迭代完成后，对权值进⾏归⼀化，并返回各个结点及其对应的权值。
def rank(self):
weight是什么词性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

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