pagerank算法_TextRank算法提取文本关键词

TextRank算法是由 Google 搜索的核心网页排序算法 PageRank 改编而来，利用图模型来提取文章中的关键词，首先介绍一下 PageRank 排序算法

一、PageRank 算法

PageRank通过网页之间的超链接来确定页面的重要性，它将整个互联网可以看作是一张有向图，网页是图中的节点，网页之间的链接就是图中的边。根据重要性传递的思想，如果一个大型网站A含有一个超链接指向了网页B，那么网页B的重要性排名会根据A的重要性来提升。

构造完图后，使用下面的公式来计算网页i的重要性（PR值）：

• 其中V表示网页，S表示每个网页的score，S越大表示网页的重要程度越高。d是阻尼系数，一般取0.85
• In(V) 表示存在指向网页 i 的链接的网页集合。Out(V)表示网页 j 中的链接指向的网页的集合；|Out(V)| 是集合中元素的个数
• 在评价网页的重要性时，根据所有指向该网页 i 的网页 j 的重要性以及网页 j 中的链接指向的网页的数目。比如：一篇文章被许多权重高的网页指向，而且指向它的网页本身指出去的链接并不多，那这篇文章就十分重要，其得分就很高。（换句话来说，这篇文章被很多人借鉴，并且是唯一被引用的）
• 初始时，可以设置每个网页的重要性为 1，进行迭代。当S（V）的变化量小于阈值（0.0001）时停止迭代。

二、TextRank 算法

TextRank在构建图的时候将节点由网页改成了句子，并为节点之间的边引入了权值，其中权值表示两个句子的相似程度，本质上构建的是一个带权无向图，其计算公式如下：

在 TextRank 构建的图中，默认节点就是句子，权重

计算图中各节点的得分时，同样需要给图中的节点指定任意的初值，通常都设为1。然后递归计算直到收敛。

例如要从下面的文本中提取关键词：

1）对这句话分词，去掉里面的停用词

2）现在建立一个大小为 9 的窗口，即相当于每个单词要将票投给它身前身后距离 5 以内的单词：

然后开始迭代投票，直至收敛：

可以看到“程序员”的得票数最多，因而它是整段文本最重要的单词，我们将文本中得票数多的若干单词作为该段文本的关键词。