输入关键字 抓取所有网页(TextRank提取的算法，用于提取短语和自动摘要的方法)

　　输入关键字 抓取所有网页(TextRank提取的算法，用于提取短语和自动摘要的方法)

　　今天要介绍的TextRank是一种用于关键词提取的算法，也可以用于词组提取和自动摘要。因为TextRank是基于PageRank的，先简单介绍一下PageRank算法。

　　1.PageRank 算法

　　PageRank 最初是为谷歌的页面排名而设计的，以公司创始人拉里佩奇的名字命名。谷歌用它来反映网页的相关性和重要性，常用于评价网页优化在搜索引擎优化操作中的有效性。PageRank 使用互联网中的超链接关系来确定网页的排名。公式是由一个投票的想法设计的：如果我们要计算网页A的PageRank值（以下简称PR值），那么我们需要知道哪些网页如果链接到网页A，意味着得到先获取网页A的链接，然后通过链接投票给网页A，计算网页A的PR值。这样的设计可以保证实现这样的效果：当一些高质量的网页指向网页A时，那么网页A的PR值会因为这些高质量的投票而增加，网页A被较少的网页指向或者被一些PR值较低的网页指向时，A的PR值不会很大大，可以合理反映一个网页的质量水平。基于以上思路，Page设计了如下公式：

　　在这个公式中，Vi代表某个网页，Vj代表链接到Vi的网页（即Vi的in-link），S(Vi)代表网页Vi的PR值，In(Vi)代表集合在网页 Vi 的所有 in-link 中，Out(Vj) 代表网页，d 代表阻尼系数，用于克服该公式中“d *”后部分的固有缺陷：如果只有求和部分，那么公式将无法处理非链内网页的PR值，因为此时根据公式，这些网页的PR值为0，但实际情况并非如此。添加了阻尼系数，保证每个网页的PR值都大于0。 根据实验结果，在0.85的阻尼系数下，大约100次迭代后，PR值可以收敛到一个稳定值。当阻尼系数接近1时，需要的迭代次数会突然增加，排名不会稳定。公式中S(Vj)前面的分数是指Vj指向的所有网页都应该平均分享Vj的PR值，这样你就可以为你链接的网页统计你的票数。

　　2.1 TextRank算法提取关键词

　　TextRank 是由 PageRank 改进而来，其公式有很多相似之处。下面是 TextRank 的公式：

　　可以看出，这个公式只比PageRank多了一个权重项Wji，用于表示两个节点之间的边连接具有不同的重要程度。TextRank用于关键词提取的算法如下：

　　1) 根据完整的句子对给定的文本T进行切分，即

　　2)对于每个句子

　　, 进行分词和词性标注，过滤掉停用词，只保留指定的词性词，如名词、动词、形容词，即

　　, 其中ti,j 为保留后的候选关键词。

　　3)构造候选关键词图G = (V,E)，其中V为节点集，由(2）生成的候选关键词组成，然后采用共现关系(co-occurrence) 在任意两点之间构造一条边。两个节点之间只有当它们对应的词在长度为K的窗口中共同出现时才存在边。K表示窗口大小，即在大多数 K 个词可以同时出现。

　　4)根据上面的公式，迭代传播每个节点的权重，直到收敛。

　　5) 将节点权重逆序排序，得到最重要的T字作为候选关键词。

　　6) 从5中找出最重要的T字，并在原文中做标记。如果形成相邻的短语，则将它们组合成多个词关键词。

　　2.2 TextRank算法提取关键词词组

　　提取关键词词组的方法基于关键词提取。可以简单地认为：如果提取出的几个关键词在文本中相邻，那么它们就构成了一个提取出的关键短语。

　　2.3TextRank 生成摘要

　　将文本中的每个句子视为一个节点。如果两个句子相似，则认为这两个句子对应的节点之间存在无向右边缘。检验句子相似度的方法是以下公式：

　　式中，Si和Sj分别代表两个句子，Wk代表句子中的词，那么分子部分表示两个句子中同时出现的同一个词的个数，分母为词的个数在句子中对数的总和。分母的这种设计可以抑制长句在相似度计算中的优势。

　　我们可以根据上述相似度公式循环计算任意两个节点之间的相似度，根据阈值去除两个节点之间相似度低的边连接，构建节点连接图，然后计算TextRank值，最后所有的 TextRank 按值排序，选取 TextRank 值最高的节点对应的句子作为汇总。

　　参考