6、摘要提取算法_基于图论的摘要算法有哪些

目前主要方法有：

• 基于统计：统计词频，位置等信息，计算句子权值，再简选取权值高的句子作为文摘，特点：简单易用，但对词句的使用大多仅停留在表面信息。
• 基于图模型：构建拓扑结构图，对词句进行排序。例如，TextRank/LexRank
• 基于潜在语义：使用主题模型，挖掘词句隐藏信息。例如，采用LDA，HMM
• 基于整数规划：将文摘问题转为整数线性规划，求全局最优解。

TextRank 算法是一种用于文本的基于图的排序算法。其基本思想来源于谷歌的 PageRank算法, 通过把文本分割成若干组成单元(单词、句子)并建立图模型, 利用投票机制对文本中的重要成分进行排序, 仅利用单篇文档本身的信息即可实现关键词提取、文摘。和 LDA、HMM 等模型不同, TextRank不需要事先对多篇文档进行学习训练, 因其简洁有效而得到广泛应用

Textrank：

1、把给定的文本T按照完整句子进行分割，即

          

 

2、对于每个句子，进行分词和词性标注处理，并过滤掉停用词，只保留指定词性的单词，如名词、动词、形容词，即，其中是保留后的候选关键词。

    

3、构建候选关键词图G = (V,E)，其中V为节点集，由（2）生成的候选关键词组成，然后采用共现关系（co-occurrence）构造任两点之间的边，两个节点之间存在边仅当它们对应的词汇在长度为K的窗口中共现，K表示窗口大小，即最多共现K个单词。

计算每两个句子之间的相似度：

Si 代表的是第 i 个句子。

wk 代表的是句子中第 k 个单词。

|Si| 代表的是句子中单词的个数。

{ wk| wk ∈ Si & wk ∈ Sj } 代表着同时在 Si 和 Sj 中出现的单词。

举个例子。

I am a fool. A big fool. I like fool.

前两句句子当中都有的单词是 a 和 fool，两个单词。

第一句话和第三句话都有的单词是 I 和 fool。

后两句句子当中都有的单词是 fool .

第一句话长度是 4，第二句话长度是3, 第三句话长度是3.

Similarity(S1,S2) = 2 / ( log(3) + log(4) ) = 0.80

Similarity(S1,S3) = 2 / ( log(3) + log(3) ) = 0.91

Similarity(S2,S3) = 1 / ( log(3) + log(4) ) = 0.40

Similarity(S1,S2) = Similarity(S2,S1)

 

WS(Vi) 代表的是Vi这个页面的分数

d 代表的是一个阻尼常数 (0<d<1)，用来确保每一个页面都至少有 (1-d)的分数。

In(Vi) 代表的是推荐Vi的页面。

Out(Vi) 代表的是Vi推荐的页面。

wji 代表的是 Vi 和 Vj 之间的相似度。

我们拿第一句句子作为例子，看一看它的得分。同样的，初始分数都是 1 

WS(V1) = (1 - 0.85) + 0.85 *

( /*第二句句子*/ (0.80 * 1) / (0.80 + 0.40) +

  /*第三句句子*/ (0.91 * 1) / (0.91 + 0.40) ) = 1.30

4、根据上面公式，迭代传播各节点的权重，直至收敛。

5、对节点权重进行倒序排序，从而得到最重要的T个单词，作为候选关键词。

6、由5得到最重要的T个单词，在原始文本中进行标记，若形成相邻词组，则组合成多词关键词

 

Word2vec+TextRank

 

同过word2vec训练得到词向量，再利用训练得到的词向量得到两个句子之间的相似度（求每个句子中所有单词的平均向量），从而通过迭代可以得到每个句子的权重，进行排序。

 

LDA+TextRank

 

利用LDA对文档集进行主题建模和候选关键词的主题影响力计算，将候选关键词的重要性按照主题影响力和邻接关系进行非均匀传递，并构建新的概率转移矩阵用于词图迭代计算和关键词抽取。

一篇文档被表示为K个隐含主题混合分布，每个主题在W个 词语上的多项分布，如上图所示。φ表示主题-词语的概率分布，θ表示文档-词语的概率分布。αβ表示超参数，空心圆表示隐含变量，实心圆表示可观察到的变量。对于文档d来说。ti(w|d)表示该词在文档d中的影响力。文档d由t个主题组成，w在一个主题z中出现概率越大，表明越重要；一个主题z在d中出现概率越大，z越重要，相对来说w也就越重要。所以

φ表示w在z中的概率，θ表示z在d中概率。W在d中的影响力如上式。

C1(d,j)表示d中的词赋给主题j的词数；C2(w,j)表示w赋给主题j的词数。N表示词汇表的大小。

这与textrank计算公式相同。

节点v分为两个部分，一部分为节点的当前重要性，权重为1，并在迭代过程中按照相邻节点的值进行调整，即为TR(Vi);另一部分为节点本身的主题影响力，为TI(Vi)。

这上面参数都是为计算概率转移矩阵的。

初始权重分布。

转移概率矩阵

 

迭代更新。