TextRank和PageRank初探

[JamCh01]

算法简介

Google的经典算法--PageRank。点击了解更多关于PageRank。

PageRank的核心目标在于计算网页的重要性，从而提供一个自上向下的排名。而TextRank主要为文章中的单元的重要性（或关键词）。

计算方法

我们煮一个简单的栗子。（如果你想看的更多请移步至PageRank算法简介及Map-Reduce实现，本例为其例子的简化版）

首先模拟一个PageRank的场景，如图（在本例中，假设互联网中只存在4个页面ABCD。且满足：1. 图是强连通的，即从任意网页可以到达其他任意网页；2.禁止出现网页不存在指向其他网页的链接，但存在指向自己的链接。）：

当某位用户在访问A页面时，他有1/3的概率去访问BCD页面中一（在AB之间的直线A→B表示A可以访问B，BA中的B→A表示B可以访问A。相对于A来说，前者为出链，后者为入链）。

同理，在D页面时，有1/2的概率访问BC，依次类推可以画出一个表格：

----	A	B	C	D
A	0	1/2	1	0
B	1/3	0	0	1/2
C	1/3	0	0	1/2
D	1/3	1/2	0	0

使用矩阵表示为：

在第一次访问时，由于现在的模型符合古典概型，即访问的页面是等可能的，即访问每个页面的可能性都为1/4，Vn表示第n次访问的概率

在未来的多次访问中，我们用相同的方法计算，直到矩阵收敛（Vn=MV(n-1)）：

即此时的矩阵为页面的PageRank。

DEMO

todo

More

我们可以有PageRank算法推演出TextRank算法。这个算法是由Rada Mihalcea and Paul Tarau 提出，论文在这里。将文章分割成若干单元（可能是句，也可能是词）后，简历图模型。利用投票机制使得文本中的单元可以进行重要性排序。这种模型相对于HMM来说不需要更多的训练；对于以前提到的两种重复文章识别算法——TF-IDF算法和余弦相似性来说，有好的机制。