一種基于圖和聚類的關鍵詞自動提取方法

謝勤政， 譚慶平， 顏 穎， 曾 平， 李盼盼

(國防科學技術大學 計算機學院 湖南 長沙 410073)

0 引言

關鍵詞集合是對一篇文檔的高層次的概述，這個集合由文檔中的一個詞語或者多個詞語組成.恰當?shù)年P鍵詞集合能夠作為文檔檢索的標簽，方便讀者迅速了解此文檔的內(nèi)容.對于如何自動提取關鍵詞，研究者們已提出了一些方法[1]，可以分為有監(jiān)督和無監(jiān)督兩種.

有監(jiān)督方法將關鍵詞抽取看成二元分類問題[2].訓練時提取關鍵詞特征構造分類模型，分類時根據(jù)模型判斷詞語是否為關鍵詞.然而有監(jiān)督方法標注訓練集非常耗時，分類器受限于特定領域且存在過擬合問題.

目前已有的關鍵詞提取算法并沒有考慮解決覆蓋所有話題的問題.我們在建立的圖上使用一種話題聚類的算法，用于覆蓋所有的話題.在計算詞與詞之間的關系的時候，引入了詞向量來計算它們之間的相似度.在進行話題聚類的時候，每個詞都是向量空間中的一個點，同一個領域的詞語在向量空間中的距離較近、相似度較高.在向量空間中對文章中出現(xiàn)的詞進行聚類，得到的每個簇都是文章覆蓋的某一個領域的話題，在此思路下可以用聚類的方法覆蓋文章中的每個話題.在創(chuàng)新地考慮了句子的影響和使用聚類覆蓋所有話題之后，關鍵詞提取的效果與傳統(tǒng)的算法相比有了明顯的提高.

1 相關工作

有監(jiān)督的關鍵詞提取算法把關鍵詞提取作為一個二元問題，即對于每一個候選的關鍵詞，判斷它是不是關鍵詞.這種有監(jiān)督的方法，訓練時需要大量有標注的數(shù)據(jù)，取得這些數(shù)據(jù)并進行訓練會非常消耗時間.

無監(jiān)督的方法涉及統(tǒng)計方法、圖模型方法以及語義方法.基于統(tǒng)計方法[1]的關鍵詞提取大部分以TF-IDF(term frequency-inverse document frequency)算法為基礎.在圖模型的研究中，文獻[3]基于詞匯的共現(xiàn)鏈提出TextRank模型排序關鍵詞.文獻[4]根據(jù)鄰近文檔知識將TextRank擴展成ExpandRank.文獻[5]將主題模型引入PageRank，實驗效果在數(shù)據(jù)集DUC2001和Inspec上優(yōu)于TF-IDF和TextRank算法.文獻[6]提出了一種假設：一句話如果包含重要的詞語，那么它是重要的，并且重要的詞語會出現(xiàn)在重要的句子中.基于這種假設，文獻[4]增加了兩種假設：一個重要的句子會和其他重要的句子相連接；一個重要的詞語會和其他重要的詞語相連接.基于以上3個假設，建立3個圖模型：將詞語與詞語之間的圖(word to word)簡稱為WW圖，將句子與詞語之間的圖(sentence to word)簡稱為SW圖，將句子與句子之間的圖(sentence to sentence)簡稱為SS圖.再在3個圖模型上選出重要度最高的句子和詞語作為文章的小結和關鍵詞集合，其弊端在于并不能保證提取出的關鍵詞覆蓋了所有的主題.

最基礎的無監(jiān)督的關鍵詞提取算法是TF-IDF[7]算法.TF-IDF算法是一種基于統(tǒng)計的關鍵詞提取算法.其主要思想是，如果某個詞語在一篇文章中出現(xiàn)的頻率(即TF值)高，并且在其他文章中很少出現(xiàn)，則認為這個詞語具有很好的類別區(qū)分能力，可以將這篇文章和其他文章區(qū)分開來，體現(xiàn)這篇文章的主旨大意，則可以將其作為關鍵詞提取出來.TF-IDF算法僅僅根據(jù)詞語的統(tǒng)計頻率對詞語進行排序，而沒有考慮到語義和句子的影響.即使一個單詞語在文章中統(tǒng)計頻率不高，這個詞語也有可能是文章的關鍵詞.

文獻[3]中基于圖的關鍵詞提取算法，是目前效果較好、使用較多[8]的算法.首先，TextRank算法根據(jù)詞語之間共同出現(xiàn)時表現(xiàn)出的語義聯(lián)系建立一張詞語之間的圖.然后，在建立的這張詞與詞之間的圖上運行PageRank算法[4].在TextRank算法中，即使一個詞本身的頻率不高，只要這個詞與其他高頻詞語共同出現(xiàn)，那么這個詞在排序時的分數(shù)也會得到提高.然而，TextRank算法在建立詞語之間的圖時容易引入噪聲，而且也沒有考慮句子的影響.

事實上可以把提取關鍵詞和提取關鍵句子的任務協(xié)同進行，這兩個任務相應地會增強對方的效果.文獻[6]提出了一種僅利用句子和詞之間的關系來同時提取關鍵詞和文章摘要的方法.文獻[9]在文獻[6]的基礎上增加了2個假設，用以覆蓋句子和詞上的全部3種關系(詞語和詞語、詞語和句子以及句子和句子之間的關系).

2 覆蓋所有話題的關鍵詞提取方法

我們提出的關鍵詞提取方法分成以下3步：構建SS、SW、WW圖；計算迭代直至收斂；聚類并得出結果.以下將按此3步詳細介紹本方法.

2.1 圖的構建

對于一篇文章，首先是把這篇文章分成一個個的單詞和句子.對于詞語的集合，使用停用詞表的方法去掉停用詞.詞語的集合中不會有重復的詞，即同一個詞在一篇文章中出現(xiàn)多次時，在圖上也只用一個點來表示.可以用圖1來直觀的表示我們建立的圖模型.

如圖1所示.對于一篇文章，白色的點代表一個單詞，黑色的點則代表一個句子.在圖1中可以直觀地看到，詞語和詞語、詞語和句子、句子和句子之間都有邊相連，而每一條邊都有相應的權重值.SS、SW、WW分別為句子與句子、詞語與句子、詞語與詞語之間的圖.

2.1.1詞語與詞語之間圖的構建 WW圖表示的是詞語與詞語之間的關系，兩個點之間的邊的權重值是這兩個點的語義相似度.我們使用詞向量來計算兩個詞的相似度，從而得到這兩個詞的語義聯(lián)系.

我們使用的詞向量是SENNA[10-11]詞回量.SENNA是使用維基百科的內(nèi)容訓練得到的詞向量，包含了130 000個單詞.本文采用余弦相似度來衡量兩個單詞的聯(lián)系，具體的計算公式為

(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為文章中的句子數(shù)量.第i行第j個元素存放的就是第i個句子和第j個句子的相似度，當i=j時相似度為0.

2.1.3句子與詞語之間圖的構建 將句子與詞語之間的圖稱為SW圖，記為GSW.SW圖是建立在WW圖和SS圖的基礎上的，每條SW圖的邊連接的是一個SS圖中的點和一個WW圖中的點，分別代表一個詞語和一個句子，這條邊的權重是連接的單詞和句子之間的聯(lián)系.對于一篇包含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中出現(xiàn)的次數(shù)；cj為該詞在文中出現(xiàn)的次數(shù)；cs為文章包含的句子總數(shù)；cswj為包含詞語wj的句子數(shù).

用一個矩陣Wm×n來記錄SW圖的內(nèi)容，即矩陣Wm×n中第i行第j個元素的值，就是第i個句子到第j個單詞之間的邊的權重值.

2.2 迭代過程

文獻[6]提出了一種觀點，重要的句子包含重要的單詞，重要的單詞會在重要的句子中出現(xiàn).在此基礎上，文獻[4]將其提煉為以下2個假設[9].

假設1一個句子如果和其他重要的句子聯(lián)系緊密，則說明這個句子也是重要的.一個詞語如果和其他重要的詞語聯(lián)系緊密，則說明這個詞語也是重要的.

假設2一個句子如果包含了許多重要的詞語，則說明這個句子也是重要的.一個詞語如果出現(xiàn)在許多重要的句子中，則說明這個詞語也是重要的.

使用兩個列向量S和w來存放句子和詞語用于排序的重要性分數(shù).所用公式為

迭代公式如下：

(3)

(4)

式(3)是句子一次迭代的計算方式，式(4)是詞語一次迭代的計算公式.參數(shù)α和參數(shù)β用于調(diào)節(jié)單詞和句子對于迭代的影響程度，α+β=1.

2.3 聚類過程

已有的關鍵詞提取方法，大多數(shù)沒有覆蓋文章的所有話題.一篇文章經(jīng)常會包含不止一個話題，如果不考慮覆蓋所有話題，那么基于圖方法提取的關鍵詞就很可能全部圍繞一個主題，而導致忽略了其他次要話題的關鍵詞.這會導致關鍵詞提取效果變差.為解決這個問題，根據(jù)實際情況，我們提出下面一個假設.

假設3在同一個話題中出現(xiàn)的關鍵詞，在語義上是相近的.

基于這個假設，我們認為使用聚類的方法得到的一個簇中的詞語是屬于同一個話題的.因此對于文章中的詞語進行聚類，去除離群點后，每個簇是文章中一個話題覆蓋的單詞，用這種方法來達到覆蓋所有話題的目的.本文使用的是K-means聚類算法.

3 實驗

3.1 數(shù)據(jù)集

我們在兩個標準數(shù)據(jù)集上運行本文方法，所得結果與現(xiàn)有的一些關鍵詞提取算法進行比較.這兩個數(shù)據(jù)集是在關鍵詞提取方面使用很多的兩個公認數(shù)據(jù)集.其中一個數(shù)據(jù)集是Hulth2003[12]，這個數(shù)據(jù)集包含了1 460篇論文的摘要部分.使用的另一個數(shù)據(jù)集是500N，是Luis Marujo使用web上的文本并對其進行了標記建立的數(shù)據(jù)集.其中包含了900篇文章，每一篇文章都有對應的關鍵詞表.

3.2 評價標準

使用3個數(shù)值對關鍵詞提取的性能進行評價，分別是精度precision、查全率recall和F值.精度即提取出的關鍵詞正確的比例，所用公式為

查全率即標注的關鍵詞被算法正確提取的比例，所用公式為

F值則是綜合考慮兩者，所用公式為

其中：Cextracted表示所有提取出的關鍵詞的數(shù)量；Ccorrect表示的是提取出來并且正確的關鍵詞的數(shù)量；Cstandard表示文章標記的關鍵詞的數(shù)量.

3.3 實驗結果

在上述的兩個數(shù)據(jù)集上運行我們的關鍵詞提取方法，迭代過程中句子和詞語對排序分數(shù)迭代的貢獻參數(shù)為α和β，都設為0.5，用TF-IDF、TextRank算法作為比較.

TF-IDF和TextRank是現(xiàn)在使用較廣泛的兩種關鍵詞提取方法.用這兩種方法和本文提出的方法進行對比，表1和表2是分別在Hulth2003和500N數(shù)據(jù)集上的實驗結果.

表1 在Hulth2003數(shù)據(jù)集上的實驗結果比較Tab.1 Results of experiment on Hulth2003 data set %

表2 在500N數(shù)據(jù)集上的實驗結果比較Tab.2 Results of experiment on 500N data set %

由表1和表2中的數(shù)據(jù)可以看出，本文的方法與已有的關鍵詞提取算法相比是有優(yōu)勢的.在Hulth2003數(shù)據(jù)集上，我們的方法在precision、recall和F值3個指標上都好于TF-IDF和TextRank.在500N上，本文方法的3個指標也比TF-IDF算法的結果好很多，與表現(xiàn)較好的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.