一种基于图和聚类的关键词自动提取方法

谢勤政， 谭庆平， 颜 颖， 曾 平， 李盼盼

(国防科学技术大学 计算机学院 湖南 长沙 410073)

0 引言

关键词集合是对一篇文档的高层次的概述，这个集合由文档中的一个词语或者多个词语组成.恰当的关键词集合能够作为文档检索的标签，方便读者迅速了解此文档的内容.对于如何自动提取关键词，研究者们已提出了一些方法[1]，可以分为有监督和无监督两种.

有监督方法将关键词抽取看成二元分类问题[2].训练时提取关键词特征构造分类模型，分类时根据模型判断词语是否为关键词.然而有监督方法标注训练集非常耗时，分类器受限于特定领域且存在过拟合问题.

目前已有的关键词提取算法并没有考虑解决覆盖所有话题的问题.我们在建立的图上使用一种话题聚类的算法，用于覆盖所有的话题.在计算词与词之间的关系的时候，引入了词向量来计算它们之间的相似度.在进行话题聚类的时候，每个词都是向量空间中的一个点，同一个领域的词语在向量空间中的距离较近、相似度较高.在向量空间中对文章中出现的词进行聚类，得到的每个簇都是文章覆盖的某一个领域的话题，在此思路下可以用聚类的方法覆盖文章中的每个话题.在创新地考虑了句子的影响和使用聚类覆盖所有话题之后，关键词提取的效果与传统的算法相比有了明显的提高.

1 相关工作

有监督的关键词提取算法把关键词提取作为一个二元问题，即对于每一个候选的关键词，判断它是不是关键词.这种有监督的方法，训练时需要大量有标注的数据，取得这些数据并进行训练会非常消耗时间.

无监督的方法涉及统计方法、图模型方法以及语义方法.基于统计方法[1]的关键词提取大部分以TF-IDF(term frequency-inverse document frequency)算法为基础.在图模型的研究中，文献[3]基于词汇的共现链提出TextRank模型排序关键词.文献[4]根据邻近文档知识将TextRank扩展成ExpandRank.文献[5]将主题模型引入PageRank，实验效果在数据集DUC2001和Inspec上优于TF-IDF和TextRank算法.文献[6]提出了一种假设：一句话如果包含重要的词语，那么它是重要的，并且重要的词语会出现在重要的句子中.基于这种假设，文献[4]增加了两种假设：一个重要的句子会和其他重要的句子相连接；一个重要的词语会和其他重要的词语相连接.基于以上3个假设，建立3个图模型：将词语与词语之间的图(word to word)简称为WW图，将句子与词语之间的图(sentence to word)简称为SW图，将句子与句子之间的图(sentence to sentence)简称为SS图.再在3个图模型上选出重要度最高的句子和词语作为文章的小结和关键词集合，其弊端在于并不能保证提取出的关键词覆盖了所有的主题.

最基础的无监督的关键词提取算法是TF-IDF[7]算法.TF-IDF算法是一种基于统计的关键词提取算法.其主要思想是，如果某个词语在一篇文章中出现的频率(即TF值)高，并且在其他文章中很少出现，则认为这个词语具有很好的类别区分能力，可以将这篇文章和其他文章区分开来，体现这篇文章的主旨大意，则可以将其作为关键词提取出来.TF-IDF算法仅仅根据词语的统计频率对词语进行排序，而没有考虑到语义和句子的影响.即使一个单词语在文章中统计频率不高，这个词语也有可能是文章的关键词.

文献[3]中基于图的关键词提取算法，是目前效果较好、使用较多[8]的算法.首先，TextRank算法根据词语之间共同出现时表现出的语义联系建立一张词语之间的图.然后，在建立的这张词与词之间的图上运行PageRank算法[4].在TextRank算法中，即使一个词本身的频率不高，只要这个词与其他高频词语共同出现，那么这个词在排序时的分数也会得到提高.然而，TextRank算法在建立词语之间的图时容易引入噪声，而且也没有考虑句子的影响.

事实上可以把提取关键词和提取关键句子的任务协同进行，这两个任务相应地会增强对方的效果.文献[6]提出了一种仅利用句子和词之间的关系来同时提取关键词和文章摘要的方法.文献[9]在文献[6]的基础上增加了2个假设，用以覆盖句子和词上的全部3种关系(词语和词语、词语和句子以及句子和句子之间的关系).

2 覆盖所有话题的关键词提取方法

我们提出的关键词提取方法分成以下3步：构建SS、SW、WW图；计算迭代直至收敛；聚类并得出结果.以下将按此3步详细介绍本方法.

2.1 图的构建

对于一篇文章，首先是把这篇文章分成一个个的单词和句子.对于词语的集合，使用停用词表的方法去掉停用词.词语的集合中不会有重复的词，即同一个词在一篇文章中出现多次时，在图上也只用一个点来表示.可以用图1来直观的表示我们建立的图模型.

如图1所示.对于一篇文章，白色的点代表一个单词，黑色的点则代表一个句子.在图1中可以直观地看到，词语和词语、词语和句子、句子和句子之间都有边相连，而每一条边都有相应的权重值.SS、SW、WW分别为句子与句子、词语与句子、词语与词语之间的图.

2.1.1词语与词语之间图的构建 WW图表示的是词语与词语之间的关系，两个点之间的边的权重值是这两个点的语义相似度.我们使用词向量来计算两个词的相似度，从而得到这两个词的语义联系.

我们使用的词向量是SENNA[10-11]词回量.SENNA是使用维基百科的内容训练得到的词向量，包含了130 000个单词.本文采用余弦相似度来衡量两个单词的联系，具体的计算公式为

(1)

其中w1和w2分别为参与比较的两个单词的词向量.

词语与词语之间的图简称为WW图，记为Gww.在实验中，对于一篇有n个词语的文章，使用一个矩阵Vn×n来存储Gww中包含的信息.比如第i个单词和第j个单词之间的权重，存储在矩阵中第i行第j列，即sim(wi,wj)=Vij(i,j=1，…，n)，当i=j时,Vij=0.

2.1.2句子与句子之间图的构建 句子与句子之间的图中，每个点代表文章中的一个句子，两个点之间的边的权重是这两个句子的相似度.每个句子由多个单词构成，我们用如下方法计算两个句子的相似度.

句子与句子之间的图简称为SS图，记为GSS.SS图上每两点之间如果有边，那么其边的权重值计算如上所述.与WW图不同的是， SS图不是全连接的.如果两个句子没有共有的单词，则这两个句子的相似度为0，两点之间没有边相连.用一个m×n的矩阵Vm×n存储GSS中的信息，其中N为文章中的句子数量.第i行第j个元素存放的就是第i个句子和第j个句子的相似度，当i=j时相似度为0.

2.1.3句子与词语之间图的构建 将句子与词语之间的图称为SW图，记为GSW.SW图是建立在WW图和SS图的基础上的，每条SW图的边连接的是一个SS图中的点和一个WW图中的点，分别代表一个词语和一个句子，这条边的权重是连接的单词和句子之间的联系.对于一篇包含m个句子、n个单词的文章，其句子集合为S={si1≤i≤m}，词语集合为W={wj1≤j≤n}，则SW图的权重计算方式如下，

(2)

其中：wj是在句子si中的一个单词；wfw和isfw分别代表了词语wj在句子si中的词频和词语.wj在其他句子中的词频，具体计算方式为

wfwj=cij/cj，isfwj=log (cs/cswj+1)，

其中：cij为词语wj在句子si中出现的次数；cj为该词在文中出现的次数；cs为文章包含的句子总数；cswj为包含词语wj的句子数.

用一个矩阵Wm×n来记录SW图的内容，即矩阵Wm×n中第i行第j个元素的值，就是第i个句子到第j个单词之间的边的权重值.

2.2 迭代过程

文献[6]提出了一种观点，重要的句子包含重要的单词，重要的单词会在重要的句子中出现.在此基础上，文献[4]将其提炼为以下2个假设[9].

假设1一个句子如果和其他重要的句子联系紧密，则说明这个句子也是重要的.一个词语如果和其他重要的词语联系紧密，则说明这个词语也是重要的.

假设2一个句子如果包含了许多重要的词语，则说明这个句子也是重要的.一个词语如果出现在许多重要的句子中，则说明这个词语也是重要的.

使用两个列向量S和w来存放句子和词语用于排序的重要性分数.所用公式为

迭代公式如下：

(3)

(4)

式(3)是句子一次迭代的计算方式，式(4)是词语一次迭代的计算公式.参数α和参数β用于调节单词和句子对于迭代的影响程度，α+β=1.

2.3 聚类过程

已有的关键词提取方法，大多数没有覆盖文章的所有话题.一篇文章经常会包含不止一个话题，如果不考虑覆盖所有话题，那么基于图方法提取的关键词就很可能全部围绕一个主题，而导致忽略了其他次要话题的关键词.这会导致关键词提取效果变差.为解决这个问题，根据实际情况，我们提出下面一个假设.

假设3在同一个话题中出现的关键词，在语义上是相近的.

基于这个假设，我们认为使用聚类的方法得到的一个簇中的词语是属于同一个话题的.因此对于文章中的词语进行聚类，去除离群点后，每个簇是文章中一个话题覆盖的单词，用这种方法来达到覆盖所有话题的目的.本文使用的是K-means聚类算法.

3 实验

3.1 数据集

我们在两个标准数据集上运行本文方法，所得结果与现有的一些关键词提取算法进行比较.这两个数据集是在关键词提取方面使用很多的两个公认数据集.其中一个数据集是Hulth2003[12]，这个数据集包含了1 460篇论文的摘要部分.使用的另一个数据集是500N，是Luis Marujo使用web上的文本并对其进行了标记建立的数据集.其中包含了900篇文章，每一篇文章都有对应的关键词表.

3.2 评价标准

使用3个数值对关键词提取的性能进行评价，分别是精度precision、查全率recall和F值.精度即提取出的关键词正确的比例，所用公式为

查全率即标注的关键词被算法正确提取的比例，所用公式为

F值则是综合考虑两者，所用公式为

其中：Cextracted表示所有提取出的关键词的数量；Ccorrect表示的是提取出来并且正确的关键词的数量；Cstandard表示文章标记的关键词的数量.

3.3 实验结果

在上述的两个数据集上运行我们的关键词提取方法，迭代过程中句子和词语对排序分数迭代的贡献参数为α和β，都设为0.5，用TF-IDF、TextRank算法作为比较.

TF-IDF和TextRank是现在使用较广泛的两种关键词提取方法.用这两种方法和本文提出的方法进行对比，表1和表2是分别在Hulth2003和500N数据集上的实验结果.

表1 在Hulth2003数据集上的实验结果比较Tab.1 Results of experiment on Hulth2003 data set %

表2 在500N数据集上的实验结果比较Tab.2 Results of experiment on 500N data set %

由表1和表2中的数据可以看出，本文的方法与已有的关键词提取算法相比是有优势的.在Hulth2003数据集上，我们的方法在precision、recall和F值3个指标上都好于TF-IDF和TextRank.在500N上，本文方法的3个指标也比TF-IDF算法的结果好很多，与表现较好的TextRank算法结果相近.

参考文献：

[1] MANNING C D. Foundations of statistical natural language processing-table of contents[J]. Information retrieval, 2002, 4(1):80-81.

[2] FRANK E, PAYNTER G W, WITTEN I H, et al. Domain-specific keyphrase extraction[C]// ACM CIKM International Conference on Information and Knowledge Management. Bremen, 1999:283-284.

[3] MIHALCEA R, TARAU P. TextRank: bringing order into texts[C]// Conference on Empirical Methods in Natural Language Processing. Barcelona, 2004:404-411.

[4] BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine [J]. Computer networks and isdn systems, 1998, 30(1-7):107-117.

[5] LIU Z, LI P, ZHENG Y, et al. Clustering to find exemplar terms for keyphrase extraction[C]// Conference on Empirical Methods in Natural Language Processing. Singapore, 2009:257-266.

[6] ZHA H. Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering[C]// International ACM SIGIR Conference on Research and Development in Information Retrieval. Tampere, 2002:113-120.

[7] SALTON G, BUCKLEY C. Term-weighting approaches in automatic text retrieval [J]. Information processing and management, 1988, 24(5):513-523.

[8] LIU Z, HUANG W, ZHENG Y, et al. Automatic keyphrase extraction via topic decomposition[C]// Conference on Empirical Methods in Natural Language Processing. Massachusetts, 2010:366-376.

[9] WAN X, XIAO J. CollabRank: towards a collaborative approach to single document keyphrase extraction[C]//International Conference on Computational Linguistics. Manchester, 2008:969-976.

[10] COLLOBERT R, WESTON J, KARLEN M, et al. Natural language processing (almost) from scratch[J]. Journal of machine learning research, 2011, 12(1):2493-2537.

[11] COLLOBERT R. Deep learning for efficient discriminative parsing[C]∥Proceedings of the fourteenth internation conference on artificial intelligence and statistics. Fort Lauderdale, 2011:224-232.

[12] HULTH A. Improved automatic keyword extraction given more linguistic knowledge[C]// Conference on Empirical Methods in Natural Language Processing. Sapporo, 2003:216-223.