关键词提取算法（一）

大体概况：

• 有监督：主要通过分类的方式进行，通过构建一个丰富完善的词表，判断每个文档与词表中每个词的匹配度，以类似打标签的形式达到关键词提取的效果。
• 无监督：受青睐的主流

TF/IDF算法

• 一种基于统计的计算方法，常用于评估在一个文档集中一个词对该文档的重要程度。
• 算法由两部分组成：
  • TF算法：统计一个词在一片文档中出现的频次，次数越多对文本越重要
    • 常用公式：
      ${tf_{ij}} = \frac{{{n_{ij}}}}{{\sum\nolimits_k {{n_{kj}}} }}$tfij​=∑k​nkj​nij​​
      其中$n_{ij}$nij​表示词$i$i在文档$j$j中的出现频次。
  • IDF算法：统计一个词在文档集的多少个文档中出现，在越少的文档中出现对文档的区分能力就越强。
    • 常用公式：
      ${idf_i} = \log \left( {\frac{{\left| D \right|}}{{1 + \left| {{D_i}} \right|}}} \right)$idfi​=log(1+∣Di​∣∣D∣​)
      其中$\left| D \right|$∣D∣为文档中总文档数，$\left| D_i \right|$∣Di​∣为文档集中出现词$i$i的文档数量。
  • TF-IDF算法
    $tf \times idf\left( {i,j} \right) = {tf_{ij}} \times {idf_i} = \frac{{{n_{ij}}}}{{\sum\nolimits_k {{n_{kj}}} }} \times \log \left( {\frac{{\left| D \right|}}{{1 + \left| {{D_i}} \right|}}} \right)$tf×idf(i,j)=tfij​×idfi​=∑k​nkj​nij​​×log(1+∣Di​∣∣D∣​)

TextRank算法

TextRank算法来自于Google的PageRank算法。

• 特点：可以脱离语料库背景
• PageRank算法
  • PageRank是一种网页排名算法，基本思想为：
    • 链接数量：一个网页被越多的其他网页链接说明网页越重要
    • 链接质量：一个网页被一个越高权值的网页链接，也表明该网页越重要
  • 计算公式
    $In\left( {{V_i}} \right)$In(Vi​)为$V_i$Vi​的入链集合，$Out\left( {{V_i}} \right)$Out(Vi​)为$V_i$Vi​的出链集合，$S\left( {{V_i}} \right)$S(Vi​)表示$V_i$Vi​的分数，则有：
    $S\left( {{V_i}} \right) = \sum\nolimits_{j \in In\left( {{V_i}} \right)} {\left( {\frac{1}{{\left| {Out\left( {{V_j}} \right)} \right|}} \times S\left( {{V_j}} \right)} \right)}$S(Vi​)=∑j∈In(Vi​)​(∣Out(Vj​)∣1​×S(Vj​))
    此时应该初始化每个页面得分为$1$1，但同样会导致一些孤立网页的得分为$0$0
  • 改进公式
    $S\left( {{V_i}} \right) =\left(1-d\right) + d \times \sum\nolimits_{j \in In\left( {{V_i}} \right)} {\left( {\frac{1}{{\left| {Out\left( {{V_j}} \right)} \right|}} \times S\left( {{V_j}} \right)} \right)}$S(Vi​)=(1−d)+d×∑j∈In(Vi​)​(∣Out(Vj​)∣1​×S(Vj​))
  • TextRand算法
    $WS\left( {{V_i}} \right) = \left( {1 - d} \right) + d \times \sum\nolimits_{{V_j} \in In\left( {{V_i}} \right)} {\left( {\frac{{{w_{ji}}}}{{\sum\nolimits_{{V_k} \in Out\left( {{V_j}} \right)} {{w_{jk}}} }} \times WS\left( {{V_j}} \right)} \right)}$WS(Vi​)=(1−d)+d×∑Vj​∈In(Vi​)​(∑Vk​∈Out(Vj​)​wjk​wji​​×WS(Vj​))
    其中$w_{ij}$wij​为$i,j$i,j之间的权重。
    • 区别
      • TextRank进行自动摘要
        • PageRank为有向无权图，TextRank则是有权图
        • 除了考虑链接句的重要性，还要考虑两个句子间的相似性
      • TextRank应用到关键词抽取时，与自动摘要有所不同
        • 词与词之间的关联没有权重：TextRank就退化为PageRank
        • 每个词不是与文档中所有词都有链接：提出了“窗口”概念，窗口中的词相互间都有链接关系。

LSA/LSI/LDA算法

前面两种算法仅使用的文本中统计信息，对于信息无法达到充分利用，所以出现了主题模型。

• 主题模型
  主题模型认为，词与文档之间没有直接的联系，应当还有一个维度将其串联在一起，将这个维度称为主题。
  
• 主题模型核心公式
  $p\left( {{w_i}\left| {{d_j}} \right.} \right) = \sum\nolimits_{k = 1}^K {p\left( {{w_i}\left| {{t_k}} \right.} \right) \times p\left( {{t_k}\left| {{d_j}} \right.} \right)}$p(wi​∣dj​)=∑k=1K​p(wi​∣tk​)×p(tk​∣dj​)

LSA/LSI算法

LSA（潜在语义分析）和LSI（潜在语义索引）几乎是一个算法，只是LSI在分析后还会利用分析的结果建立相关索引。

• LSA算法
  • 主要步骤
    • 使用BOW模型将每个文档表示为向量；
    • 将所有的文档词向量拼接构成词-文档矩阵$\left( {m \times n} \right)$(m×n);
    • 对词-文档矩阵进行奇异值分解（SVD）操作$\left( {\left[ {m \times r} \right] \cdot \left[ {r \times r} \right] \cdot \left[ {r \times n} \right]} \right)$([m×r]⋅[r×r]⋅[r×n]);
    • 根据SVD的结果，将词-文档矩阵映射到一个更低维度$k$k的近似SVD结果：$\left( {\left[ {m \times k} \right] \cdot \left[ {k \times k} \right] \cdot \left[ {k \times n} \right],0 &lt; k &lt; r} \right)$([m×k]⋅[k×k]⋅[k×n],0<k<r)。每个词和文档都可以表示为$k$k个主题构成的空间中的一个点，通过计算词与文档的相似度获取文档关键词。
  • 算法优点
    • 可以映射到低维空间
    • 在有限利用文本语义信息的同时降低计算代价，提高分析质量
  • 算法缺点
    • SVD计算复杂度高，特征空间维度较大时计算效率低下
    • 当有新文本进入时需要对整个空间进行重新训练
    • 对词的频率分布不敏感、物理解释性薄弱等

LDA算法

LDA算法是对LSA算法的改进，理论基础是贝叶斯理论。

• 基本假设
  假设文档中主题的先验分布和主题中词的先验分布都服从狄利克里分布。
• 吉布斯采样的LDA算法
  • 吉布斯采样
    吉布斯采样算法是一种启发式学习方法，它假定每一条序列只包含一个特定长度的模体实例，在各条序列上随机选取一个模体的起始位置，这样便得到了初始训练集，然后通过更新步骤和采样步骤迭代改进模体模型。
    假设我们从联合分布$p\left( {{x_1}, \cdots ,{x_n}} \right)$p(x1​,⋯,xn​)中抽取$X$X的$k$k个样本，记第$i$i个样本为${X^{\left( i \right)}} = \left( {x_1^{\left( i \right)}, \cdots ,x_n^{\left( i \right)}} \right)$X(i)=(x1(i)​,⋯,xn(i)​)，过程则如下：
    • 确定初始值${X^{\left( 1 \right)}}$X(1)
    • 假设已经获得样本${X^{\left( i \right)}}$X(i)，记下一个样本为${X^{\left( i+1 \right)}} = \left( {x_1^{\left( i+1 \right)}, \cdots ,x_n^{\left( i+1 \right)}} \right)$X(i+1)=(x1(i+1)​,⋯,xn(i+1)​)，于是将其看作一个向量，对其中某一分量$x_j^{\left( i+1 \right)}$xj(i+1)​，可通过在其他分量已知的条件下该分量的概率分布来抽取。
    • 对于此条件概率，使用样本${X^{\left( i+1 \right)}}$X(i+1)中已得的分量$x_1^{\left( i+1 \right)}$x1(i+1)​到$x_{j-1}^{\left( i+1 \right)}$xj−1(i+1)​以及上一个样本${X^{\left( i \right)}}$X(i)中的$x_{j+1}^{\left( i+1 \right)}$xj+1(i+1)​到$x_{n}^{\left( i+1 \right)}$xn(i+1)​,，即
      $p\left( {x_j^{\left( {i + 1} \right)}\left| {x_1^{\left( {i + 1} \right)}} \right., \cdots ,x_{j - 1}^{\left( {i + 1} \right)},x_{j + 1}^{\left( i \right)}, \cdots ,x_n^{\left( i \right)}} \right)$p(xj(i+1)​∣∣∣​x1(i+1)​,⋯,xj−1(i+1)​,xj+1(i)​,⋯,xn(i)​)
    • 重复上面的过程$k$k次
  • 训练LDA
    • 随机初始化：对语料中每篇文档中的每个词$w$w随机赋予一个topic编号$z$z
    • 重新扫描语料库，对每个词$w$w按照吉布斯采样公式重新采样其topic，在语料中进行更新
    • 重复以上语料库的重新采样直到吉布斯采样收敛
    • 统计语料库的topic-word共现频率矩阵，该矩阵为LDA的模型
  • 预估
    • 随机初始化，对当前文档中的每个词$w$w随机赋予一个topic编号$z$z
    • 重新扫描当前文档，按照吉布斯采样公式，重新采样它的topic
    • 重复以上过程直到吉布斯采样收敛
    • 统计文档中topic分布即为预估结果

参考文献

《Python与自然语言处理》