TextRank算法

update: 2020.2.20

基本介绍

PageRank算法

参考

现在有若干的网页链接，每个网页可能链接到其他的链接，假设有4个网页（A，B，C，D），其中没有链接的网页称为悬空页面，每个网页不会链接到自己，每个网页与其他网页的链接若干链接只视为一条。将每个网页初始的值设为0.25（0-1，此处有四个网页）。

例子中具体的链接情况如下：

网页	链接目标
A	无
B	A,C
C	A
D	A,B,C

有如下公式

\[PR(u)=\sum_{v\in B_u}\frac{PR(v)}{L(v)}\]

其中\(L(v)\)为网页\(v\)的链接总数，\(B_u\)为有链接可以链接到\(u\)的网页的集合，简单点说，就是在每一轮迭代时，每个链接到目标网页的源网页都会将它的PageRank值中的部分等分传递给目标网页，且对应的网页会减少相应的PR值。

如例子中所说，在第一轮迭代时

\[PR(A)=\frac{PR(B)}{2}+\frac{PR(C)}{1}+\frac{PR(D)}{3}.\]

因为B指向A，且其一共指向2个网页；C指向A，且其一共指向1个网页；D指向A，且其一共指向3个网。

由于考虑到人为点击网页时不会出现一直点击的情况，设置一个阻尼系数（damping factor），此时PR公式如下

\[PR(p_i)=\frac{1-d}{N}+d\sum_{p_j\in M(p_i)}\frac{PR(pj)}{L(p_j)}\]

其中\(d\)为阻尼系数，\(N\)是所有页面的总数（有些也可以不考虑N）。

不停的迭代，直到得到较为稳定的结果，就像水流一样，被导向成为目标多的page，最终会像管道多的蓄水池一般获得较大的值。

更进一步的话，可以使用矩阵来完成上述步骤。如果页面\(j\)没有指向页面\(i\)的链接，那么\(j\)跳转到\(i\)的概率\(l(i,j)=0\)否则\(l(i,j)=\frac{1}{L(j)}\)。于是有\(PR^\prime(i)=\sum l(i,j)\times PR(j)\)。在考虑阻尼系数的情形下，于是有矩阵乘法：

\[\mathbf{R} = \begin{bmatrix} PR(p_1) \\ PR(p_2) \\ \vdots \\ PR(p_N) \end{bmatrix} \mathbf{R} = \begin{bmatrix} {(1-d)/ N} \\ {(1-d) / N} \\ \vdots \\ {(1-d) / N} \end{bmatrix} + d \begin{bmatrix} \ell(p_1,p_1) & \ell(p_1,p_2) & \cdots & \ell(p_1,p_N) \\ \ell(p_2,p_1) & \ddots & & \vdots \\ \vdots & & \ell(p_i,p_j) & \\ \ell(p_N,p_1) & \cdots & & \ell(p_N,p_N) \end{bmatrix} \mathbf{R}\]

其中\(\sum_{i=1}^Nl(p_i,p_j)=1\)

TextRank

TextRank是基于PageRank提出的从文章中提取关键词的算法。

在TextRank中，每个词为一个节点（page），节点之间的边为共现关系（这里不再是有向边，而是无向边）

过程

1. 给定一个文本T，对其按照完整句子进行切割
2. 句子中的词进行分词、词性标注和去除停用词等处理，符合要求的词作为候选关键词
3. 每个候选词视为图G=(V, E)中一个节点，节点之间是否有边由它们的共现关系决定（在长度为k的窗口中是否共现）
4. 初始化关系矩阵（依据不同的词语属性信息赋予不同初始值），进行迭代更新各节点权值，直到收敛
5. 取前n个权值最大的节点所对应的词语作为关键词
6. 如果第5中有相邻在文章中出现的词语，组合为一个关键词

在jieba库中，有jieba.analyse.textrank函数封装了该方法，其中初始化M矩阵时的各边权重为其对应词语出现的共现次数