EntropyRank： 基于主题熵的关键短语提取算法

尹 红，陈 雁，李 平

(西南石油大学 计算机科学学院 智能与网络化系统研究中心，四川 成都 610500)

0 引言

互联网的快速发展，使得文档数量迅速增长。大量文档可为知识获取带来红利，但同时也给信息获取带来了挑战。关键短语反映了文档主题或主要内容，能够帮助用户快速理解文档并获取文档关键信息，它携带的重要信息可广泛用于自然语言处理和信息检索领域任务上，例如，聚类、分类、自动摘要、话题监测、问答系统、知识发现等[1-4]，因此人们一直对关键短语提取技术有着极大兴趣，并提出了大量新颖的方法。

关键短语提取方法主要沿着监督和无监督两个方向不断推进[5]。在监督方法中，通常将关键短语提取作为一个二分类问题[6-7]，利用机器学习中的分类算法学习分类模型。在无监督方法中,常见做法是将其作为一个基于图的排序问题，把单个文档转换为图，利用具体的排序算法[8-9]对节点进行排序，取前K个短语作为关键短语。由于监督方法需要大量的人工标注数据，而人工标注是一个耗时耗力的任务，因此本研究集中于无监督方法上。

传统的基于图的方法通过词语间的紧密程度和词语本身在文档中具有的影响力来计算词语得分。当前，在衡量词汇间的紧密程度方面，研究者们大都采用词汇间的语义关系以及共现频率来表示词语间的紧密性；在词语影响力方面，研究者们大多利用词的位置信息以及词对主题的偏好程度来表示词语本身的影响力。对于如何表示词对主题的偏好程度，目前研究都局限于利用词的主题分布与文档主题分布的相似度来表示。据我们所知，词的主题分布是针对整个语料集，不因文档的不同而产生差异，而每篇文档中的相同词可能对相同的主题有不同的偏好性，因此现有的方法不能准确的表示词对主题的偏好程度。针对现有方法的不足，本文提出了EntropyRank算法，它借助主题模型中的文档—主题分布和主题—词分布来表示词在具体文档中特定的主题分布，并提出用词主题分布的熵值来表示词的主题偏好程度。最后，融合熵值来提取关键短语。

1 相关工作

根据机器学习中的算法分类可将关键短语提取算法分为监督和无监督两种，监督关键短语提取方法通常将关键短语提取作为一个二分类问题，将关键短语与非关键短语分开标注，采用机器学习中的分类算法学习到一个分类模型，利用学习到的分类模型去判断一个新的词语是否为关键短语[7]。而无监督关键短语[10-17]提取方法不需要对样本进行标注，仅利用文档本身的信息就可以实现关键短语的提取。由于监督方法需要事先标注好的高质量数据，人工预处理代价高，所以目前国内外对于关键短语提取算法的研究主要集中在无监督方法上。

在无监督方法中，较为流行的一种方法是基于统计信息，最具代表性的方法TF-IDF于1988年由KS Jones等人提出，它利用词频和词出现在所有文本中的频率来计算词在文档中的重要性。该方法没有考虑到语义特征，导致忽略了一些重要的低频词汇，并且实现过程需要大量语料。因此，另一种流行的基于图排序的方法引起了研究者们的重视。其中TextRank[13]作为最经典的算法于2004年提出，它通过随机游走方法计算图中每个节点的分数值，对节点分数值进行排序，并取前K个词为关键词。TextRank方法在进行随机游走时指出节点得分由相邻节点的得分和节点自身影响力共同决定，它默认图中节点边权为1，即认为节点得分会均匀转移到相邻节点，并且也默认节点影响力为节点数的倒数。该方法没有考虑到节点得分的转移概率会受词语间的相关关系的影响，也没有考虑到词语影响力存在差异的情况。

随后，针对词语间相关关系，Wan和Xiao[14]在2008年提出了SingleRank算法，他指出边权由两节点的共现次数决定。同时，他提出的ExpandRank算法首次考虑利用除文档本身之外的其他额外信息来对文档建模，2014年Collapalli和CorageesSujatha根据Wan和Xiao[14]的想法提出Cite-TextRank[15]算法,利用科技文献中的引用关系寻找额外文档来对文档建模，同年顾益军提出节点在随机游走时会以更大的概率跳转到更重要的节点参考文献以及近几年提出的WeightedTextRank[16]、AttractionRank[17]融合共现关系和词语间的相似性、相互吸引力来表示词语间的相关关系。

对于如何计算词语影响力，Florescu等提出了positionRank[18]，利用词的位置信息来表示词语影响力，他们认为词语出现的位置越靠前词语影响力越大，然后统计每个词在文档中出现的位置，对每个位置的影响力求和作为词语影响力；Liu等提出了TPR算法[19]，认为每个词语都有一定的主题偏好性，累积词对所有主题的偏好性当作词语影响力，在此基础上，Sterckx、Teneva又相继提出了STPR[20]和SR[21]算法，这两种算法都是在TPR算法上做出的改进，其中STPR算法通过计算词语主题分布和文档主题分布的相似度作为词语影响力，SR算法则是在STPR算法基础上加入了词语的语料特性，最后融合主题相似度与语料特性共同作为词语影响力。除此之外，Liu等、Bougouin和Chage等人考虑用聚类的方法进行关键短语提取，将候选关键短语进行聚类，并把每个类别当作一个节点，类与类之间进行全连接构成图，其中类别之间的关系通过类别中的词来刻画，最后选取每个类别中最具代表性的短语作为关键短语。

综上所述，已有的算法中，没有研究者考虑词在具体文档中特定的主题分布情况，而一个词的主题分布可刻画词对主题的偏好性，若词的主题分布越均匀，那么词对每个主题的偏好性都相同，对于整个文档来说，这个词不能很好地去刻画文档的主题分布情况，反之则能很好地去刻画文档的主题分布情况。因此本文提出的EntropyRank算法采用信息熵来表示词语特定的主题分布情况，这样可以很好地捕捉到主题分布明显的词语，并以较为简洁的方式改善关键短语提取效果。

2 基于主题熵的词语影响力计算方法

2.1 利用LDA主题模型生成词主题分布

LDA[22]在2003年由D M Blei等人提出，是一种基于概率图模型的主题模型算法，用来识别语料库中的潜在主题信息。在LDA模型中，认为文档主题服从多项分布，而每个主题又是在多个词上的多项分布，则文档d可由以下过程生成： 首先以一定的概率从主题分布θd中选择某个主题t∈T(T为大小为M的主题集合)，接下来从该主题的词分布φt中以一定概率选择某个词w，重复上述过程可生成蕴含多个主题的文档，由于文档都是经过上述过程获得，于是对于大量文档集来说，可通过LDA模型训练得到一个文档—主题分布矩阵θ和主题—词分布矩阵φ。

(1)

2.2 基于主题熵的词语影响力计算

信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法，其中信息熵能够表示随机变量的不确定性，若随机变量分布越均匀，则它的不确定性越大，信息熵越大，反之不确定性越小，信息熵越小。

关键短语提取技术关键在于能提取出代表文档主题的词，本研究认为词的主题分布情况能刻画词的主题表达力。若词的主题分布明显，表明该词的主题表达力强，能更清楚的表示文档主题，则更可能是文档关键短语；若词的主题分布比较均匀，表明该词的主题表达力较弱，不能清楚的表示文档主题，成为关键短语的可能性就较小。当计算词语影响力时，我们利用词语的主题表达力来刻画词语影响力，这里我们将词的主题表达力称作主题熵。当词语的主题表达力越强，对应的主题熵越小；反之对应的主题熵越大。于是,我们采用主题熵的倒数来表示词语影响力，为保证词语影响力的计算具有意义，在计算词语影响力时将主题熵加1。因此，对于文档d中的词语w，令ti(w)表示词语影响力，其计算方式如式(2)所示。

(2)

其中,pj(wd)表示文档d中的词语w在第j个主题下的概率值。

3 EntropyRank关键短语提取

3.1 词图构建

采用图排序方式对文档进行关键短语提取时，将文档看做一个词序列S=(ω1,ω2,…,ωs)，ωs表示词序列中的第s个词。接下来根据S构建能够代表文档和体现词之间相互关系的词图G=(V,E)，其中V=(w1,w2,…，wq)为S构成的大小为q的候选词集合，E为具有权值的边集合。我们使用大小为λ的窗口对词序列S进行遍历，并统计两个词在窗口中的共现次数来作为边权。在词图构建过程中，连边既可以是有向的也可以是无向的，但Mihalcea和Tarau[14]在实验过程中发现词图类型对实验效果的影响较小，因此本文在实验中构建无向图。

3.2 基于随机游走的词语得分计算

采用上述词图构建方法将文档表示成词图G，令M表示G的邻接矩阵,mij∈M表示连边(wi,wj)权重，在词图上利用随机游走方法计算节点得分，按照式(3)迭代直至收敛，最后得到每个节点最终得分。

(3)

(4)

为防止在收敛结束时出现每个节点值都为0或者仅存在一个节点值为1的情况，在公式中加入了阻尼系数α保证每个节点都会收敛到一个正常值，因此节点得分计算公式修改后如式(5)所示。

(5)

(6)

则一个具体的词wi,最终得分如式(7)所示。

(7)

Adj(wi)： 节点wi的所有邻居节点集合。

3.3 基于短语得分的关键短语提取

通过EntropyRank得到每个词语得分之后，开始对候选关键短语进行排序。Hulth等人指出大多数的已标注关键短语为名词性短语，因此本文将从文档中筛选出名词短语作为候选关键短语。

本文按照以下方法获得文档的候选关键短语。首先对文档进行分词处理，再进行词性标注，最后选择形如(形容词)*(名词)+格式的名词短语参考文献，它表示零个或多个形容词后可接一个或多个名词。本文将这种形式的名词短语当作候选关键短语。

当识别出候选关键短语之后，使用Entropy-Rank计算出的词语得分来计算候选关键短语得分，因此候选关键短语的得分计算方式如式(8)所示。

(8)

随后对候选关键短语的得分进行降序排序得到一个降序候选关键短语列表，并取前K个短语作为文档关键短语。

4 实验与结果分析

4.1 数据集介绍

为验证算法的性能，本次实验在6个数据集上进行了实验。

500N-KPCrowd[23]数据集包括500篇新闻文档，每个类别包含50篇新闻，关键短语由亚马逊工作人员所标注；Inspec数据集[7]包括2 000篇科学论文摘要，其中关键短语由作者和读者分别标注；DUC[24]数据集包括308篇新闻标题及新闻文档，其中关键短语由作者和读者分别标注；NUS[25]数据集包括211篇会议论文，且每篇论文长度在4至12页之间，其中关键短语由作者和读者分别标注；Krapivin[26]数据集包括2 304篇科技论文，其中关键短语由作者和读者分别标注；KP20K[27]数据集包括200篇科技论文摘要及其标题，其中关键短语由作者和读者分别标注。经过Mihalcea和Tarau[13]中的描述分析，对Inspec数据集我们采用读者标注的作为文档的标注关键短语，其他数据集均采用作者标注的作为文档的标注关键短语。对数据集的详细描述，如表1所示。

表1 数据集介绍

因为数据集中包含的新闻或者期刊摘要、论文内容都较少，不足以学习到好的主题。因此，本文使用英文维基百科数据来学习主题模型。通过去除长度小于1 000的文档并去掉停用词，最终保留了4 614 519篇文档。对于主题模型中的缺省词，我们将词的主题分布设置为均匀分布。

4.2 评价指标

本研究选取了准确率P、召回率R、F1作为评价指标。其中P是指算法抽取出的关键短语列表中标注关键短语所占比例，R则是标注关键短语被抽取出的比例，而F1是对P和R的一个综合考虑。下面给出了3个评价标准的具体定义：

其中，ccorrect是算法提取出的正确的关键短语个数，cextract是提取出的关键短语个数，cstandard则是标注关键短语的个数。上述三个评价指标可以分别衡量实验效果。由于P、R指标有时会出现互相矛盾的情况，因此本文利用综合评价指标F1对提出的方法进行评估，可以得到相对客观的评价。

4.3 实验参数分析

EntropyRank算法中存在两个参数可能会影响算法性能，包括窗口λ和主题数目M。因为6个数据集上平均标注关键短语数量不同，因此在讨论参数λ和M时，将关键短语固定为所有数据集的平均标注短语个数。于是，当讨论主题数目M对算法的影响时，我们将窗口λ固定为3，关键短语个数K固定为15；当讨论窗口对算法的影响时，我们将主题数目M固定为5，关键短语个数K固定为15。

4.3.1 窗口大小

为分析窗口大小对关键短语提取性能的影响，本研究在6个数据集上进行实验，实验结果如图1所示。随着窗口的取值不断增大，算法性能逐渐提升，而在某些特定的数据集上，当窗口增大到一定程度时，算法性能开始下降。

图1 K=15,F1值随窗口λ的变化情况

当窗口λ=18、21时，Inspec数据集和KP20K数据集上的F1值逐渐减小，而其他数据集上F1值仍然增大。这是因为Inspec和KP20K数据集由论文标题及摘要构成，文档长度较短，若在实验过程中窗口设置过大，则该文档构成的词图将会是一个完全图，可能会出现所有连边边权相等的情况，这样在进行关键短语提取时将无法捕捉到词语的局部结构信息。

4.3.2 主题数目

本研究分析了LDA模型中的主题数目对关键短语提取性能的影响，在6个数据集上分别进行了实验，实验结果如图2所示，随着M的变化，6个数据集上的F1值变化比较平稳，这表明文档的语义信息仅集中于某几个主题。

图2 K=15，F1值随主题数目M的变化情况

4.4 对比实验

本研究一共选取了8种对比方法衡量本文方法的有效性。包括TextRank、WeightedTextRank、SingleRank、AttractionRank、PositionRank、TPR、STPR、SR算法，它们都采用随机游走的方法计算短语得分，其中TextRank、WeightedRank、AttractionRank算法仅考虑进一步去寻找节点间的语义关系，未考虑到词语本身具有差异性的情况。TPR、STPR、SR和PositionRank算法都考虑到了词语本身具有特异性，但在通过随机游走方法计算词语得分时，PositionRank算法将词语的位置信息作为词语自身影响力，未考虑到词语的主题信息，其他3个算法则利用整个语料库上的词主题分布与文档主题分布进行相似性计算并将其作为词语自身影响力，未考虑到相同词在不同文档下会有不同的主题分布的情况。

为验证EntropyRank算法的性能，我们固定窗口λ=3，主题数目M=5，分别在6个数据集上与其他算法进行了对比。如图3所示，在所有数据集上EntropyRank算法性能优于其他对比算法。例如，在500N数据集上，当K=10时，EntropyRank算法F1值平均提升了3.59%，与WeightedRank、AttractionRank算法相比平均提升3.87%，相比于TPR、STPR、SR、PositionRank算法，F1值提升了1.81%，在其他数据集上的F1值提升情况与500N数据集上相似。

图3 λ=3,M=5时，EntropyRank与其对比方法随着K的变化F1值的变化情况

综上所述，EntropyRank算法在所有数据集上的F1值都有了提升，同时与考虑到词语主题信息的方法相比，效果提升更明显。因此，我们可得出： ①在计算词的主题表达力时，利用词在具体文档中的主题分布比LDA模型中的主题分布更有效。②与词语主题分布和文档主题分布的相似性作为词语影响力的方法相比，词语的主题熵能更准确的刻画词语影响力。③可同时适用于摘要(短文本)与论文、新闻(长文本)。

本文算法与其他算法相比，性能上有了显著提升，但在模型效率上，本文算法的时间复杂度较高。我们将EntropyRank算法的时间复杂度分为两部分，第一部分为O(λnall)+O(n2)，第二部分为O(MN)+O(Mn)，其中第一部分为词图构建和词语分数计算的时间复杂度，第二部分为主题模型训练与词主题分布的时间复杂度。第一部分与传统的TextRank算法的时间复杂度相同，因此，EntropyRank算法多出的时间复杂度为O(MN)+O(Mn)。其中λ表示窗口大小，nall表示文本长度，m表示主题数目，n表示词图的节点数目，N表示维基百科词典大小。

5 总结及未来工作

本文提出利用主题模型训练得到的文档—主题分布矩阵和主题—词分布矩阵来表示词在具体文档中的主题分布，并采用信息熵来表示词的显著性，并基于随机游走算法计算每个词语的最终得分，最后利用得分计算候选短语得分，提取前K个短语作为关键短词。其中在随机游走过程中设置节点会以更大的概率随机跳转到更重要的节点上，从而使得一些低频词不被忽略。与其他8种对比算法相比，该算法在6个公开数据集上的F1值有了显著提升。

考虑到词之间的关系即边权可以通过词语间的语义关系和网络科学中图的性质来刻画，下一步工作将会挖掘词图中的节点间的结构关系以及节点本身在词图中的结构性质，将其与词语间的语义关系相融合来修改节点边权，以进一步提高关键短语的准确性以及多样性。