词频与排序

TF-IDF

TF-IDF算法(Term Frequency-Inverse Document Frequency，词频-逆文档频次算法)由两部分组成：TF算法以及IDF算法。TF算法是统计一个词在一篇文档中出现的频次，其基本思想是，一个词在文档中出现的次数越多，则其对文档的表达能力越强。而IDF算法则是统计一个词在文档集的多少个文档中出现，其基本思想是，如果一个词在越少的文档中出现，则其对文档的区分能力也就越强。

TF的计算常用式： $tf_{ij}=\frac{n_{ij}}{\sum_kn_{kj}}$

其中 $n_{ij}$ 表示词 $i$ 在文档 $j$ 中出现的频次，但是仅用频次来表示，那长文本的词出现频次高的概率更大，这会影响到比较。所以计算时会对词频进行归一化，分母部分就是统计文档中每个词出现次数的总和，也就是文档的总词数。

IDF的计算常用式： $idf_i=log(\frac{|D|}{1+|D_i|})$

其中 $|D|$ 为文档集中总文档数， $|D_i|$ 为文档集中出现词 $i$ 的文档数量。分母加 $1$ 是采用了拉普拉斯平滑，避免有部分新的词没有在语料库中出现过而导致分母出现零的情况。

TF-IDF的计算常用式： $tf\times idf = tf_{ij}\times idf_{i} = \frac{n_{ij}}{\sum_kn_{kj}}\times log(\frac{|D|}{1+|D_i|})$

TF和IDF公式怎么融合，是相乘还是相加，IDF要不要取对数，经过理论推导与实验研究后，发现上式为较有效的计算方式之一。

TextRank

TextRank算法可以脱离语料库的背景，仅对单篇文档进行分析就可以提取该文档的关键词。TextRank算法的基本思想来源于PageRank算法。PageRank的基本思想有两条：

1) 链接数量。一个网页被越多的其他网页链接，说明这个网页越重要。

2) 链接质量。一个网页被一个越高权值的网页链接，说明这个网页越重要。

$In(V_i)$ 为 $V_i$ 的入链集合，$Out(V_i)$ 为 $V_i$ 的出链集合，$|Out(V_i)|$ 为 $V_i$ 的出链数量，每个网页将它自身的分数平均贡献给每个出链。若 $V_j$ 链向 $V_i$， 则 $\frac{1}{|Out(V_j)|}\times S(V_j)$ 即为 $V_j$ 贡献给 $V_i$ 的分数。将 $V_i$ 的所有入链贡献给他的分数全部加起来，就是 $V_i$ 自身的得分：

$S(V_i) = \sum_{j\in In(V_i)}(\frac{1}{|Out(V_i)|}\times S(V_i))$

算法开始时会将所有网页的得分初始化为 $1$ ，然后通过多次迭代来对每个网页分数进行收敛。收敛时的得分就是网页的最终得分，如不收敛则限定最大迭代数，停止时的分数为网页得分。为避免一些没有出链入链的网页得分为 $0$ 的情况，我们加入阻尼系数 $d$ 来帮助平滑，即从所有总分中分出一部分给这些网页：

$S(V_i) = (1-d)+d\times \sum_{j\in In(V_i)}(\frac{1}{|Out(V_j)|}\times S(V_i))$

以上是PageRank的理论，也是TextRank的基础。不同的是PageRank是有向无权图，而TextRank则是有权图，因为在计分时除了考虑链接句的重要性外，还要考虑两个句子间的相似性。计算每个句子给它链接句的贡献时，需要通过计算权重占总权重的比例来分配。在这里，权重就是两个句子的相似度，相似度的计算可采用编辑距离，余弦距离等。另外，我们在对一篇文章进行自动摘要时，默认每个句子和其他所有句子都是有链接关系的，也就是一个有向完全图。

$WS(V_i) = (1-d)+d\times\sum_{V_j\in In(V_i)}(\frac{w_{ji}}{\sum_{V_k\in Out(V_j)w_{jk}}}\times WS(V_j))$

当TextRank用于关键词抽取时，与应用在自动摘要时有两点不同：1、词与词之间的关联没有权重；2、每个词不是与文档中所有词都有链接。

基于第一点不同，TextRank与PageRank就一致了(链接无权重)，即

$WS(V_i) = (1-d)+d\times\sum_{V_j\in In(V_i)}(\frac{1}{|Out(V_j)|}\times WS(V_j))$

基于第二点不同，每个词不是与所有词链接，我们使用滑窗界定谁与谁链接，如下例：

“世界献血日，学校团体、献血服务志愿者等可到血液中心...”，经分词后“世界，献血，日，学校，团体，献血，服务，志愿者，等”，现窗口设为 $5$ ，则得：

1)[世界，献血，日，学校，团体] 2)[献血，日，学校，团体，献血]

3)[日，学校，团体，献血，服务] 4)[学校，团体，献血，服务，志愿者]

每个窗口内所有的词都有链接关系。得到了链接关系，我们就可以套用TextRank公式，对每个词进行得分计算，最后选择最高的 $n$ 个词作为关键词。