textrank 算法

向右看齐 2022-03-10 05:00 151阅读 0赞

#### 1. pagerank 算法： ####

pagerank是一个**有向图**，每个节点代表一个网页 V i V\_i Vi, 其**网页重要性**得分记为 P R ( V i ) PR(V\_i) PR(Vi)。  
我们认为一个网页的重要性与其网页指出去和链进来的网页数量有关。

计算公式为迭代公式：

P R ( V i ) = ( 1 − d ) + d ∗ ∑ j ∈ I n ( V i ) 1 ∣ O u t ( V j ) ∣ P R ( V j ) PR(V\_i) = (1-d) + d \* \\sum\_\{j \\in In(V\_i)\} \\frac\{1\}\{|Out(V\_j)|\}PR(V\_j) PR(Vi)=(1−d)\+d∗∑j∈In(Vi)∣Out(Vj)∣1PR(Vj)

I n ( V i ) In(V\_i) In(Vi) : 指向网页 i 的网页集合  
 O u t ( V j ) Out(V\_j) Out(Vj) ：从网页 j 指出去的网页集合  
 d d d：阻尼系数，当 指向网页 i 的个数为0时，上式右半部分为0，**阻尼系数避免了整个PR(V\_i)为0**；d一般设置为0.85时，经过100多词迭代就可以收敛；

#### 2. textrank 算法： ####

[textrank 论文][textrank]  
textrank 算法是一个**有权无向图**，仅仅比PageRank多了一个权重项Wji，用来表示**两个节点之间的边连接有不同的重要程度**。

W S ( V i ) = ( 1 − d ) + d ∗ ∑ j ∈ I n ( V i ) w j i ∑ V k ∈ O u t ( V j ) w j k W S ( V j ) WS(V\_i) = (1-d) + d \* \\sum\_\{j \\in In(V\_i)\} \\frac\{w\_\{ji\}\}\{\\sum\_\{V\_k \\in Out(V\_j)\} w\_\{jk\}\} WS(V\_j) WS(Vi)=(1−d)\+d∗∑j∈In(Vi)∑Vk∈Out(Vj)wjkwjiWS(Vj)

##### 2.1 关键词提取： #####

TextRank用于关键词提取的算法如下：

*  对于每个句子，进行**分词和词性标注处理**，并过滤掉停用词，只保留指定词性的单词，如名词、动词、形容词，**保留后的候选关键词**。
 *  构建**无权无向**的候选关键词图G = (V,E)，其中**V为节点集，由1.生成的候选关键词组成**，然后采用**共现关系**（co-occurrence）构造任两点之间的边，两个节点之间存在边仅当它们对应的词汇在长度为K的**窗口中共现**，K表示窗口大小，即最多共现K个单词。
 *  根据上面公式，迭代传播各节点的得分，直至收敛。
 *  对节点得分进行倒序排序，从而得到最重要的T个单词，作为候选关键词。
 *  由5得到最重要的T个单词，在原始文本中进行标记，若形成相邻词组，则组合成多词关键词。

##### 2.2 关键句提取 #####

将文本中的**每个句子分别看做一个节点**，如果两个句子有相似性，那么认为这两个句子对应的节点之间存在一条**无向有权边**。

S c o r e ( S i , S j ) = ∣ w k ∣ w k ϵ S i ∩ w k ϵ S j ∣ l o g ( ∣ S i ∣ ) + l o g ( ∣ S j ∣ ) ) Score(S\_i, Sj) = \\frac\{|w\_k | w\_k \\epsilon S\_i \\cap w\_k \\epsilon S\_j| \}\{log(|S\_i|)+log(|S\_j|))\} Score(Si,Sj)=log(∣Si∣)\+log(∣Sj∣))∣wk∣wkϵSi∩wkϵSj∣

Si,Sj分别表示两个句子，Wk表示句子中的词。

*  分子部分：Si,Sj两个句子中的含有同一个词的个数
 *  分母部分：句子中词的个数求**对数之和**。**分母log的设计**可以遏制较长的句子在相似度计算上的优势。

#### 代码 ####

[jieba 关键词提取][jieba]

[textrank]: http://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf
[jieba]: https://blog.csdn.net/suibianshen2012/article/details/68927060