自然语言处理：关键词提取（TF-IDF、Textrank）_自然语言处理需要提取该新闻文本的关键词。在提取关键词之前,需要对csgnews.txt中

TF-IDF

词频-逆文档频率（Term Frequency-Inverse Document Frequency, TF-IDF)，基于词在当前文档和全文档出现的频率，度量词的重要性. 基本思想是，词的重要性正比于在当前文档中出现的频率，反比于在全文档中出现的频率（词的主体预测能力）.

Model

以$\text{TF}(w)$表示词$w$的当前文档频率，$\text{IDF}(w)$表示词$w$的逆文档频率，$\text{D}$表示全文档数，$\text{DF}(w)$表示包含词$w$的文档数，则
$$\text{TF-IDF(w)}=\text{T}F(w)\cdot \text{IDF}(w)=\text{TF}(w)\log \frac{\text{D}}{\text{DF}(w)}$$

Smoothing

$$\text{IDF}(w)=\log \frac{\text{D}+1}{\text{DF}(w)+1}+1$$

• log项中分子项和分母项均加1，表示增加一篇包含任意词的文档，避免分母项为0；
• 最终值加1，避免某单词在所有文档中出现时，IDF的值为0，即不忽略出现在所有文档中的词；

Regularization

不难发现，若w在不同文档中的频率相同，则w的TF-IDF值相同. 可见，TF-IDF值的计算未考虑文档自身词的分布. 直观想法是，w在总词数（词集合）较少的文档中TF-IDF值较大.

假设文档的TF-IDF特征向量为$v\text{v}v=(\text{TF-IDF}(w_1),\cdots ,\text{TF-IDF}(w_n))$ ，对$v\text{v}v$做L2正则化得
$${v\text{v}v}_{l2}=\frac{v}{||v|{|}_2}=\frac{v}{\sqrt{v_1^2+v_2^2+\cdots +v_n^2}}$$

若 A = { w 1 . w 2 , w 2 } A=\{w_1.w_2,w_2\} A={w1​.w2​,w2​}，$B=(w_1,w_2,w_3)$，则
TF-IDF ( A ) = { ( 0.333 , 0.666 , 0 ) ⊙ IDF ( w A ) , 未 正 则 化 ( 0.447 , 0.894 , 0 ) , L 2 正 则 化 TF-IDF ( B ) = { ( 0.333 , 0.333 , 0.333 ) ⊙ IDF ( w B ) , 未 正 则 化 ( 0.556 , 0.557 , 0.557 ) , L 2 正 则 化

$$\begin{aligned} & \text{TF-IDF}(A)= \begin{cases} (0.333,0.666,0)\odot\text{IDF}(\pmb w_A), &未正则化\\[1ex] (0.447,0.894,0),&L2正则化 \end{cases}\\[2ex] &\text{TF-IDF}(B)= \begin{cases} (0.333,0.333,0.333)\odot\text{IDF}(\pmb w_B), &未正则化\\[1ex] (0.556,0.557,0.557),&L2正则化 \end{cases} \end{aligned}$$ ​TF-IDF(A)={(0.333,0.666,0)⊙IDF(wwwA​),(0.447,0.894,0),​未正则化L2正则化​TF-IDF(B)={(0.333,0.333,0.333)⊙IDF(wwwB​),(0.556,0.557,0.557),​未正则化L2正则化​​
可见，正则化前${\text{TF-IDF}}_A(w_1)={\text{TF-IDF}}_B(w_1)$，正则化后${\text{TF-IDF}}_A(w_1)<{\text{TF-IDF}}_B(w_1)$.

Implemetation

参考sklearn.feature_extraction.text中的CountVectorizer和TfidfVectorizer类.

PageRank

Algrithm source

斯坦福大学研究生佩Larry Page和Sergey Brin借鉴学术论文排序方法，即论文被引用次数，提出评价网页质量的方法：

• 若一个网页被其他网页链接，说明该网页重要性较高；
• 被高质量网页链接的网页，其重要性相应提高；

Model

如图所示A、B、C和D网页之间的链接图：

有向图的概率转移矩阵又称Markov矩阵，如下：
T = ( 0 1 / 2 1 0 1 / 3 0 0 1 / 2 1 / 3 0 0 1 / 2 1 / 3 1 / 2 0 0 ) T = \left(

$$\begin{matrix} 0 & 1/2 & 1 & 0\\[1ex] 1/3 & 0 & 0 & 1/2\\[1ex] 1/3 & 0 & 0 & 1/2\\[1ex] 1/3 & 1/2 & 0 & 0 \end{matrix}$$ \right) T=⎝⎜⎜⎜⎜⎛​01/31/31/3​1/2001/2​1000​01/21/20​⎠⎟⎟⎟⎟⎞​
$T_{ij}$表示结点$j$跳转至结点$i$的概率，列向量元素之和为1. 初始各具有相同PR值，经$n$次转移后：
$$V_0=[1/41/41/41/4{]}^T,V_n=T\cdot V_{n-1}=T^n\cdot V_0$$
$n\to +\infty$时，若概率转移矩阵$T$满足以下条件，则$V_n$收敛：

• 概率转移矩阵是随机矩阵，即$T_{ij}\ge 0$，且${\sum }_i{T}_{ij}=1$；
• 概率转移矩阵是不可约的，即图中任何节点都可以到达其他节点，即$T$中不存在终止节点（全0列）、陷阱节点（对角线元素为1）；
• 概率转移矩阵是非周期的，即$T$为素矩阵，自身的某次幂为正矩阵；

上例得最终PR向量为
$$\underset{n\to +\infty }{\lim }{V}_n=\underset{n\to +\infty }{\lim }{T}^n\cdot V_0=[3/92/92/92/9{]}^T$$
经过$n$次跳转后，用户停留在$A$网页的概率为$3/9$，高于其他网页。

Terminal node

终止节点是指没有任何出链的节点，如C节点：

概率转移矩阵中终止节点对应列的元素全为0，如C节点：
T = ( 0 1 / 2 0 0 1 / 3 0 0 1 / 2 1 / 3 0 0 1 / 2 1 / 3 1 / 2 0 0 ) T = \left(

$$\begin{array}{rrrr} 0 & 1/2 & \color{red}\pmb 0 &0\\[1ex] 1/3 & 0 & \color{red}\pmb 0 & 1/2\\[1ex] 1/3 & 0 & \color{red}\pmb 0 & 1/2\\[1ex] 1/3 & 1/2 & \color{red}\pmb 0 & 0 \end{array}$$ \right) T=⎝⎜⎜⎜⎜⎛​01/31/31/3​1/2001/2​000000000000​01/21/20​⎠⎟⎟⎟⎟⎞​
容易验证，执行第$n$次转移后，PR向量的元素和不断减小，即
$$\sum _i{V}_n[i]=\sum _i{V}_{n-1}[i]-V_{n-1}[3]$$
最终得到的PR向量为
$$\underset{n\to +\infty }{\lim }{V}_n=[0000{]}^T$$

Trap Node

陷阱节点是指只有跳转至自身链接的节点，如C节点：

陷阱节点在概率转移矩阵中，对应的对角线元素为1，如下：
T = ( 0 1 / 2 0 0 1 / 3 0 0 1 / 2 1 / 3 0 1 1 / 2 1 / 3 1 / 2 0 0 ) T = \left(

$$\begin{matrix} 0 & 1/2 & 0 & 0\\[1ex] 1/3 & 0 & 0 & 1/2\\[1ex] 1/3 & 0 & \color{red}\pmb 1 & 1/2\\[1ex] 1/3 & 1/2 & 0 & 0 \end{matrix}$$ \right) T=⎝⎜⎜⎜⎜⎛​01/31/31/3​1/2001/2​001110​01/21/20​⎠⎟⎟⎟⎟⎞​
容易验证，执行第n次后，陷阱节点对应的PR值不断增大，即
$$V_n[3]=V_{n-1}[3]+\sum _{j\ne 3}T[3][j]\cdot V_{n-1}[j]$$
最终得到PR向量为
$$\underset{n\to +\infty }{\lim }{V}_n=[0010{]}^T$$

Solving Idea

当用户遇到终止节点网页或陷阱节点网页，用户可通过在浏览器重新输入新的地址，以逃离这个网页。因此，对转移公式进行如下修正：
$$V_n=\alpha T\cdot V_{n-1}+(1-\alpha )V_0$$
可见，用户以$1-\alpha$的概率通过地址栏跳至其它网页，$\alpha$值反比于算法收敛速度，一般为0.85。

Deficiency

第一，未区分站内导航链接。与站内导航链接相比，外链更能体现PR值的传递关系.

第二，未过滤广告链接和功能链接。如没有实际价值的广告链接，以及“分享到微博”等功能链接.

第三，对新网页不友好。新网页的入链较少，即使其内容质量很高，要获得高PR值仍需要很长时间.

TextRank

基于PageRank思想判断词的权重，指定窗口大小构建无向图（字典存储），具体步骤如下：

• 文本分词，根据需要剔除停词等，从前向后遍历词表，并从当前位置向后扫描d个单词加入无向图，无向图边的权重为两节点出现的次数；
• 计算各结点的转移概率，根据初始PR向量，迭代求解最终PR向量，其中
  $$V_{n+1}[w]=\alpha \sum _{w\sim w_i}{V}_n[w_i]T[w][w_i]+(1-\alpha )V_0[w]$$