基于多特征的關(guān)鍵詞抽取算法

郭建波， 謝 飛，2

（1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽 合肥 230009；2.合肥師范學(xué)院 計算機學(xué)院，安徽 合肥 230061）

0 引 言

人們在生活中越來越多地使用互聯(lián)網(wǎng)，導(dǎo)致信息來源多樣化。面對各種信息來源，在網(wǎng)絡(luò)和現(xiàn)實生活中快速有效地獲得需要的信息也變得更加困難。因此，關(guān)鍵信息的獲取變得非常重要，文檔的關(guān)鍵詞抽取技術(shù)也應(yīng)運而生。所謂文檔關(guān)鍵詞是可以概括文檔主題的1個或多個詞語。關(guān)鍵詞在多個領(lǐng)域都扮演著非常重要的作用，如信息檢索、信息聚類［1］和搜索引擎［2－3］等，關(guān)鍵詞的應(yīng)用可以極大地提高信息檢索和搜索引擎等技術(shù)的效率。

本文提出的關(guān)鍵詞抽取算法是針對英文期刊、會議論文集中的文獻(xiàn)。已有的相關(guān)算法中，一部分可以歸結(jié)為有監(jiān)督的機器學(xué)習(xí)算法，基本思想是通過訓(xùn)練帶有關(guān)鍵詞的訓(xùn)練文檔，構(gòu)造分類器，再把該分類器應(yīng)用于測試集來提取測試文檔中的關(guān)鍵詞。典型的如Extractor算法［1］和KEA算法4，而這2個系統(tǒng)的不足之處在于需要訓(xùn)練文檔，因此需要花費大量的時間用于構(gòu)造分類器。另一部分可以歸結(jié)為無監(jiān)督的機器學(xué)習(xí)算法，如典型的KP－Miner算法［5］，該算法的不足之處在于只應(yīng)用了文檔中候選詞豐富的統(tǒng)計信息，而沒有應(yīng)用文檔中比較關(guān)鍵的候選詞的語義信息。

本文算法屬于無監(jiān)督的機器學(xué)習(xí)算法，無需訓(xùn)練文檔，直接提取單個文檔中的關(guān)鍵詞。通過定義更多的候選詞特征來選擇候選詞。同時，權(quán)重計算時，用更高效候選詞屬性來計算權(quán)重，使得算法的抽取結(jié)果和效率都得到很大的提高。

1 相關(guān)工作

關(guān)鍵詞抽取算法可以分為有監(jiān)督的算法和無監(jiān)督的算法。有監(jiān)督的算法一般把關(guān)鍵詞抽取算法看作分類問題，首先通過訓(xùn)練帶有關(guān)鍵詞的訓(xùn)練集構(gòu)造分類器，再把分類器應(yīng)用于測試集，通過分類測試集文檔中的詞是否為關(guān)鍵詞來選擇最終的關(guān)鍵詞；無監(jiān)督算法則直接根據(jù)對候選詞權(quán)重的計算給候選詞打分來確定最終的關(guān)鍵詞。

有監(jiān)督的算法中，Extractor算法［1］首先掃描文檔，去除文檔中的停止詞和標(biāo)點符號，得到ngrams，同時刪除長度大于3的n－grams，余下的n－grams為候選詞。根據(jù)候選詞的長度和首次出現(xiàn)位置分別計算訓(xùn)練文檔和測試文檔中的候選詞的權(quán)重。再利用已確定關(guān)鍵詞的訓(xùn)練文檔，構(gòu)造C4.5分類器，把分類器應(yīng)用到測試文檔中，從測試文檔的候選詞中選出關(guān)鍵詞。KEA算法［4］掃描文檔，去除標(biāo)點符號，得到n－grams，刪除首尾有停止詞的n－grams。與 Extractor［1］不同，KEA算法［4］不認(rèn)為停止詞是分隔符，停止詞可以出現(xiàn)在n－grams的中間位置。特征選擇時，算法選擇詞頻－逆向文檔頻率（term－frequent－inverse document frequency，TFIDF）和首次出現(xiàn)位置。另一方面，KEA算法［4］構(gòu)造樸素貝葉斯分類器。

文獻(xiàn)［6］提出了構(gòu)造支持向量機（support vector machine，SVM）模型抽取關(guān)鍵詞。文獻(xiàn)［7］在抽取關(guān)鍵詞時利用boosting and bagging策略。無監(jiān)督的算法中，典型的 KP－Miner算法［5］在文檔中提取n－grams，同樣認(rèn)為停止詞不是分隔符，同時該算法刪除出現(xiàn)次數(shù)小于3次，或者首次出現(xiàn)位置大于400的n－grams。在計算候選詞權(quán)重時，KP－miner算法提出了在計算詞的IDF值時，復(fù)合詞在文檔集中的出現(xiàn)頻率比單個詞出現(xiàn)的頻率小，所以算法對TFIDF計算做了改進，同時計算權(quán)重時考慮了首次出現(xiàn)位置；算法最后對提取的關(guān)鍵詞做了優(yōu)化，刪除關(guān)鍵詞集合中其他關(guān)鍵詞子串的關(guān)鍵詞，并認(rèn)為這些關(guān)鍵詞是冗余的。

另外，對于無監(jiān)督的學(xué)習(xí)算法，文獻(xiàn)［8］提出了構(gòu)建文檔語義網(wǎng)絡(luò)結(jié)構(gòu)來提取關(guān)鍵詞；文獻(xiàn)［9］提出在提取單個文檔關(guān)鍵詞時利用和文檔距離較近（相似）的文檔；文獻(xiàn)［10］提出基于語義聯(lián)系的新聞網(wǎng)頁關(guān)鍵詞抽取算法，利用《知網(wǎng)》中的詞語計算語義相似度；文獻(xiàn)［11］提出利用《同義詞詞林》語義詞典和統(tǒng)計信息得到語義擴展度，再結(jié)合詞匯鏈等方法計算候選詞權(quán)重，最終排序得到最終關(guān)鍵詞；文獻(xiàn)［12］構(gòu)建詞語語義相似度網(wǎng)絡(luò)并利用居間度密度度量詞語語義關(guān)鍵度，以此來度量關(guān)鍵詞的權(quán)重來獲取關(guān)鍵詞；文獻(xiàn)［13］提出基于圖論中心性的概念度量權(quán)重提取關(guān)鍵詞。

人們不僅在學(xué)術(shù)文章中提取關(guān)鍵詞，在新聞網(wǎng)頁和微博博文中也提取關(guān)鍵詞。文獻(xiàn)［14］利用社會化標(biāo)簽來提高抽取網(wǎng)頁關(guān)鍵詞的質(zhì)量；文獻(xiàn)［15］首先根據(jù)推特中推特內(nèi)容構(gòu)建推特的圖結(jié)構(gòu)，再根據(jù)圖中的中心度抽取推文中的關(guān)鍵詞；文獻(xiàn)［16］提出利用參考文獻(xiàn)信息提取關(guān)鍵詞；文獻(xiàn)［17］提出基于神經(jīng)網(wǎng)絡(luò)的中文關(guān)鍵詞抽取算法。

2 基于多特征抽取算法

通過對已有算法的分析，本文摒棄了已有算法中的不足之處，設(shè)計了一種基于多特征的關(guān)鍵詞抽取算法。算法總體上分為候選詞選擇、候選詞權(quán)重計算和最終關(guān)鍵詞確定3個步驟。

2.1 算法框圖

本文算法的整體流程如圖1所示。

圖1 基于多特征的關(guān)鍵詞抽取

2.2 候選詞的選擇

首先掃描文檔，根據(jù)特定的截斷符號（句號、問號、逗號、數(shù)字等）把文檔分為若干子句，然后根據(jù)指定的n，掃描子句得到n－grams（例如，子句w0w1w2w3w4的 3－grams 有 3 個w0w1w2，w1w2w3，w2w3w4，其中wj表示1個單詞），由于包含多個單詞的關(guān)鍵詞數(shù)量很少，因此對n也有限 制，本 文 只 掃 描 得 到 1－gram、2－grams、3－grams。盡管這樣，仍然會產(chǎn)生數(shù)量非常多的ngrams，所以需要刪除一部分不適合作為候選詞的n－grams，剩余的n－grams即為候選詞。

首先，刪除開始或結(jié)束位置含有停止詞的ngrams。停止詞為冠詞（a，the）、介詞（in，on）、副詞（now，here）、連詞（and，but）等沒有實際意義的詞，因此刪除這些短語；其次借鑒KP－Miner算法［3］，認(rèn)為越重要的詞在文章中出現(xiàn)的次數(shù)越多，且越靠前，因此去除出現(xiàn)次數(shù)小于3或首次出現(xiàn)在文檔中400個單詞之后的n－grams。

本文認(rèn)為關(guān)鍵詞大多表現(xiàn)為名詞短語。文獻(xiàn)［18－19］提出選擇名詞短語為候選詞，選擇名詞短語為候選詞比簡單地考慮短語的統(tǒng)計特征為候選詞的效果要好。由于本文是提取論文中的關(guān)鍵詞，名詞短語能夠更好地表明文章的主題，而形容詞短語等可以更好地表達(dá)情感，對于文章主題沒有加成作用。因此，本文在選擇候選詞時同樣選擇名詞短語作為候選詞。實驗中選擇Stanford分詞工具［20］對文章中的單詞作詞性標(biāo)注，從而選出其中的名詞短語。

2.3 候選詞的權(quán)重計算

權(quán)重計算階段是選取特定的特征計算候選詞的權(quán)重。這一步是關(guān)鍵詞抽取算法中最重要的一步，很多算法都是通過添加更多特征或改進一些特征來提取更優(yōu)的關(guān)鍵詞。其中最重要的特征是候選詞的TFIDF值和首次出現(xiàn)位置。

（1）在計算權(quán)重時考慮到首次出現(xiàn)位置。因為一般出現(xiàn)在文檔前面的詞語比較重要，對于科學(xué)類文檔來說，摘要和引言部分都在文章靠前的位置，而這兩部分中的內(nèi)容，基本上可以概括文章的主題，因此越靠前的詞，重要性一般越高，權(quán)重也應(yīng)該越大。首次出現(xiàn)位置值計算公式為：

其中，position（P，D）為候選詞P在文檔D中的首次出現(xiàn)位置，即出現(xiàn)在第多少個單詞的位置；size（D）為文檔D中的單詞總數(shù)。

在別的大城市里沒有這種情形，而在我家鄉(xiāng)里往往是這樣，坐了馬車，雖然是付過了錢，讓他自由去兜攬生意，但是他常常還仍舊等候在鋪子的門外，等一出來，他仍舊請你坐他的車。

（2）在計算候選詞權(quán)重時加入出現(xiàn)頻率（TF）。候選詞在文檔中的出現(xiàn)頻率是候選詞最重要的統(tǒng)計特征，文檔中反復(fù)出現(xiàn)的詞或者短語成為關(guān)鍵詞的概率非常大。TF的計算公式為：

其中，freq（P，D）為文檔D中候選詞P的出現(xiàn)次數(shù)；size（D）為文檔D中的單詞總數(shù)。

（3）長度越長的候選詞的重要性可能更高。因為短語的長度越長，其表達(dá)的意思一般更加精確，如“keyphrase extraction algorithm”比“keyphrase extraction”可能更適合作為該篇文章的關(guān)鍵詞。因此，在計算候選詞權(quán)重時，對不同長度的候選詞賦予不同的權(quán)重Wl，其計算公式為：

2.4 最終關(guān)鍵詞的選擇

根據(jù)候選詞的以上3個特征的權(quán)重計算公式可計算候選詞的最終權(quán)重，計算公式為：

其中，W（P，D）為文檔D中候選詞P的最終權(quán)重。計算得到每個候選詞的最終權(quán)重后，排序候選詞的最終權(quán)重，排名靠前的K個候選詞即為最終提取的Top－K個關(guān)鍵詞。由于本文算法已經(jīng)對候選詞的長度作了限制，因此，在最終的關(guān)鍵詞中，存在包含關(guān)系的關(guān)鍵詞的數(shù)量會非常少。最終的關(guān)鍵詞選擇階段，不對提取的最終關(guān)鍵詞作優(yōu)化。

由于本文算法只需要掃描1遍文檔即可得到候選詞，而在候選詞權(quán)重計算和關(guān)鍵詞確定部分都不需要掃描文檔，因此，該算法的時間復(fù)雜度為O（n），其中n為文檔中的單詞數(shù)。

3 實 驗

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

本文采用2010年舉辦的關(guān)鍵詞抽取比賽（SemEval－2010）中的數(shù)據(jù)集，其中包括訓(xùn)練集144篇英文文章和測試集100篇英文文章。數(shù)據(jù)集的特征見表1所列。

表1 數(shù)據(jù)集的特征

3.2 實驗結(jié)果與比較

3.2.1 提取關(guān)鍵詞的效果

在SemEval－2010數(shù)據(jù)集中，訓(xùn)練集和測試集中的每篇文檔均指定了關(guān)鍵詞。在訓(xùn)練集和測試集中都做了實驗，并與作者指定的關(guān)鍵詞做比較，分別對準(zhǔn)確率（P）、召回率（R）和F1值進行比較。其中P、R、F1值的計算公式分別為：

提取訓(xùn)練集144篇、測試集100篇文檔中關(guān)鍵詞的算法比較見表2所列。的學(xué)習(xí)算法效率更高，可以驗證在計算候選詞權(quán)重時，舍去IDF帶來的時間效率的提高，并沒有降低抽取效果。

表2 提取不同篇數(shù)文檔中關(guān)鍵詞的效果

3.2.3 參數(shù)調(diào)節(jié)

針對候選詞長度不同賦予不同的權(quán)重參數(shù)做一組實驗來說明參數(shù)選擇的正確性。實驗中選擇長度為1的候選詞的權(quán)重范圍為［0.1，1.0］，長度為2的候選詞權(quán)重范圍為［1.1，2.0］，長度為3的候選詞權(quán)重范圍為［2.1，3.0］，間隔都為0.1。對于不同長度的各個權(quán)重，在SemEval－2010的訓(xùn)練數(shù)據(jù)集上做了1 000組實驗，最終選擇候選詞權(quán)重計算部分的長度權(quán)重。不同長度的權(quán)重確定后，本文固定其中2個長度的權(quán)重，測試另一長度的權(quán)重變化對實驗結(jié)果的影響，實驗選擇訓(xùn)練集文檔，每篇文檔抽取15個關(guān)鍵詞，實驗結(jié)果如圖2所示。

從表2可以看出，本文算法在提取關(guān)鍵詞時，明顯比KP－Miner算法要好，在候選詞選擇時綜合考慮不同的特征對候選詞的選擇進行優(yōu)化，同時，在候選詞權(quán)重計算時對不同長度的候選詞賦予不同的權(quán)重，從而限定是有效的。

3.2.2 時間效率的比較

由于在計算TFIDF值的IDF值部分時需要多遍掃描文檔，需要耗費大量時間。為了驗證本文算法中沒有計算IDF值是否帶來時間效率的提高，本文做了如下對比實驗，在SemEval－2010訓(xùn)練數(shù)據(jù)集上對本文算法和KP－Miner算法進行比較，可得抽取所有文檔關(guān)鍵詞的總時間，見表3所列。

表3 不同算法的時間效率比較

從表3可以看出，本文算法比典型的無監(jiān)督

圖2 不同長度候選詞的權(quán)重變化

由圖2可以看出，候選詞長度的限定對最終關(guān)鍵詞選擇的影響很大，對于長度為1的候選詞，如果賦予更高的權(quán)重，算法的提取效果明顯降低。因此，本文直接對同長度的候選詞給定不同的權(quán)重是有效的。

4 結(jié)束語

本文提出了一種基于多特征的無監(jiān)督關(guān)鍵詞抽取算法，結(jié)合候選詞的統(tǒng)計特征對其進行評估，根據(jù)最終候選詞得分確定關(guān)鍵詞。實驗表明，在提取關(guān)鍵詞時，優(yōu)于現(xiàn)有的無監(jiān)督的抽取算法，同時在抽取效率上，該算法也優(yōu)于其他算法。但是在算法中僅用到很少的詞性信息，所以更多地利用詞性特征將是進一步研究的重點。另外，門戶網(wǎng)站的大量涌現(xiàn)，使得在網(wǎng)絡(luò)中瀏覽新聞變得非常普遍，因此，下一步將研究抽取新聞網(wǎng)頁中新聞關(guān)鍵詞的抽取算法。

［1］ Turney P D.Learning algorithms for keyphrase extraction［J］.Information Retrieval，2000，2（4）：303－336.

［2］ Gutwin C，Paynter G，Witten I H，et al.Improving browsing in digital libraries with keyphrase indexes［J］.Decision Support Systems，1999，27（1）：81－104.

［3］ Gong Zhiguo，Liu Qian.Improving keyword based web image search with visual feature distribution and term expansion［J］.Knowledge and Information Systems，2009，21（1）：113－132.

［4］ Witten I H，Paynter G W，F(xiàn)rank E，et al.KEA：practical automatic keyphrase extraction ［C］／／Proceedings of the Fourth ACM Conference on Digital Libraries.ACM，1999：254－255.

［5］ El－Beltagy S R，Rafea A.KP－Miner：a keyphrase extraction system for English and Arabic documents［J］.Information Systems，2009，34（1）：132－144.

［6］ Zhang Kuo，Xu Hui，Tang Jie，et al.Keyword extraction using support vector machine［M］／／Advances in Web－Age Information Management.Berlin：Springer，2006：85－96.

［7］ Lopez P，Romary L.HUMB：automatic key term extraction from scientific articles in GROBID［C］／／The 5th International Workshop on Semantic Evaluation Association for Computational Linguistics，2010：248－251.

［8］ Wan Xiaojun，Xiao Jianguo.Single document keyphrase extraction using neighborhood knowledge［C］／／Proceedings of the 23nd AAAI Conference on Artificial Intelligence，2008：855－860.

［9］ 謝 飛，吳信東，胡學(xué)鋼，等.基于語義聯(lián)系的新聞網(wǎng)頁關(guān)鍵詞抽?。跩］.廣西師范大學(xué)學(xué)報：自然科學(xué)版，2009，27（1）：145－148.

［10］ Huang Chong，Tian Yonghong，Zhou Zhi，et al.Keyphrase extraction using semantic networks structure analysis［C］／／Data Mining，2006，ICDM’06，Sixth International Conference on.IEEE，2006：275－284.

［11］ 劉瑞陽，王良芳.結(jié)合語義擴展度和詞匯鏈的關(guān)鍵詞提取算法［J］.計算機科學(xué)，2013，40（12）：264－291.

［12］ 王麗霞，淮曉永.基于語義的中文文本關(guān)鍵詞提取算法［J］.計算機工程，2012，38（1）：1－4.

［13］ Lahiri S，Choudhury S R，Caragea C.Keyword and keyphrase extraction using centrality measures on collocation networks［EB／OL］.［2014－01－25］.http:／／citeseerx.ist.psu.edu／viewdoc／download？doi＝10.1.1.433.3540＆req＝rep1＆type＝pdf.

［14］ 李 鵬，王 斌，石志偉，等.Tag－TextRank：一種基于 Tag的網(wǎng)頁關(guān)鍵詞抽取方法［J］.計算機研究與發(fā)展.2012，49（11）：2344－2351.

［15］ Lu Y，Li R，Wen K，et al.Automatic keyword extraction for scientific literatures using references［C］／／Innovative Design and Manufacturing （ICIDM），Proceedings of the 2014International Conference on.IEEE，2014：78－81.

［16］ Abilhoa W D，de Castro L N.A keyword extraction method from twitter messages represented as graphs［J］.Applied Mathematics and Computation，2014，240：308－325.

［17］ 白曉雷，黃廣君，段建輝.一種基于BP神經(jīng)網(wǎng)絡(luò)的關(guān)鍵詞抽取方法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2014，37（7）：808－811，896.

［18］ Hulth A.Improved automatic keyword extraction given more linguistic knowledge［C］／／Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing Association for Computational Linguistics，2003：216－223.

［19］ Hulth A，Megyesi B B.A study on automatically extracted keywords in text categorization［C］／／The 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics.Association for Computational Linguistics，2006：537－544.

［20］ Starford NLP Group.Stanford分詞工具［EB／OL］.［2014－09－08］.http：／／nlp.stanford.edu／software／tagger.shtml.