基于LexRank的中文單文檔摘要方法

劉海燕，張 鈺

(裝甲兵工程學(xué)院 信息工程系，北京 100072)

?

【信息科學(xué)與控制工程】

基于LexRank的中文單文檔摘要方法

劉海燕，張 鈺

(裝甲兵工程學(xué)院 信息工程系，北京 100072)

針對目前中文自動文本摘要方法主要使用基于特征詞詞頻、基于物理位置以及聚類統(tǒng)計(jì)的方法準(zhǔn)確率較低、不適合單文檔摘要，提出了一個(gè)改進(jìn)的中文單文檔摘要方法；該方法將LexRank算法與VSM相結(jié)合，充分考慮特征詞、特征句、特征段位置等因素；利用java語言對其進(jìn)行實(shí)驗(yàn)測試，實(shí)驗(yàn)結(jié)果表明：改進(jìn)的自動文本摘要方法和傳統(tǒng)摘要方法相比能夠更好的實(shí)現(xiàn)對文章的自動摘要；該摘要方法可應(yīng)用到信息挖掘、信息分類、信息索引等領(lǐng)域，在現(xiàn)今信息化的社會，具有較高的現(xiàn)實(shí)意義及實(shí)用使用價(jià)值。

文本摘要；LexRank算法；VSM；測評

隨著大數(shù)據(jù)時(shí)代的到來，互聯(lián)網(wǎng)上的數(shù)據(jù)呈現(xiàn)出爆炸性增長。面對網(wǎng)上紛繁的信息，對于現(xiàn)在的人們來說，能夠快速過濾出自己所需要的信息變得格外重要。自動文本摘要能夠滿足人們這一需求，具有很大的實(shí)際應(yīng)用價(jià)值。

自動文本摘要技術(shù)在國外的研究起源比較早。在20世紀(jì)50年代，IBM公司的H.P.Luhn[1]開啟了研究的先河，他在1958年進(jìn)行了自動摘要系統(tǒng)實(shí)驗(yàn)，標(biāo)志著自動摘要技術(shù)的誕生。相比之下，國內(nèi)自動文本摘要技術(shù)的研究起步較晚，1988年，上海交通大學(xué)的王永成[2]教授研制出SJTUAA系統(tǒng)，該系統(tǒng)夠較好地實(shí)現(xiàn)中文文本自動摘要。近些年來中文自動文本摘要技術(shù)的研究日益火熱。目前，主要使用[3]基于特征詞詞頻、基于物理位置以及聚類統(tǒng)計(jì)的方法，這些方法一般不考慮句子之間、段落之間的相似關(guān)系，并且主要應(yīng)用在多文檔摘要生成中，不適合單文檔摘要領(lǐng)域。

本文提出了一個(gè)基于LexRank算法，結(jié)合TF-IDF算法、結(jié)合VSM，并考慮特征詞、特征句、特征段位置的適合單文檔的中文自動文本摘要系統(tǒng)，能夠快速且較準(zhǔn)確地生成文本摘要。

1 LexRank算法

LexRank算法[4]是密西根大學(xué)的Gunes Erkan和Dragomir R Radev提出的一種基于圖論的自然語言處理方法，主要通過句子之間相似度的判斷對文本、詞匯進(jìn)行分類。如圖1所示，用于自動文本摘要時(shí)，LexRank算法對文章中的句子進(jìn)行處理，將句子作為節(jié)點(diǎn)構(gòu)造出一個(gè)標(biāo)量圖，節(jié)點(diǎn)間的連線代表兩個(gè)句子的相似程度。如果兩個(gè)句子無關(guān)，則兩個(gè)句子所代表的節(jié)點(diǎn)間就沒有連線；兩個(gè)句子相似程度越大，節(jié)點(diǎn)間的連線就越粗。在對每個(gè)句子進(jìn)行關(guān)鍵句評分時(shí)，要充分考慮每個(gè)句子所對應(yīng)節(jié)點(diǎn)的連線數(shù)量以及連線粗細(xì)，即句子的核心性與相關(guān)程度大小。最終按照評分，根據(jù)一定閾值，選擇其中分?jǐn)?shù)較高的句子作為文章的關(guān)鍵句。

圖1 文本摘要中LexRank算示意圖

和基于詞頻的算法相比，LexRank算法采用基于圖的方法，更能有效地考慮句子之間相似度，排除了噪聲句對摘要結(jié)果的影響。但是單一的LexRank算法只是對句子間的相似度進(jìn)行計(jì)算比較，沒有考慮在文章中各個(gè)自然段落之間的關(guān)系。在本文設(shè)計(jì)的中文單文檔摘要系統(tǒng)中，將LexRank算法與VSM相結(jié)合，并將段落之間的關(guān)系考慮進(jìn)去。

2 改進(jìn)的中文單文檔摘要系統(tǒng)

改進(jìn)后的中文摘要系統(tǒng)流程如圖2所示，該系統(tǒng)在LexRank算法的基礎(chǔ)上，充分考慮自然段落相似關(guān)系、句子相似關(guān)系、句子段落的物理位置等因素，可用于單文檔摘要的生成。

圖2 中文單文檔摘要流程

2.1 預(yù)處理

面對一篇完整的文檔，首先要將其文字轉(zhuǎn)化成可進(jìn)行數(shù)學(xué)計(jì)算的模型形式，即首先對其進(jìn)行預(yù)處理，把文章進(jìn)行分詞、分句、分段。分句和分段分別根據(jù)文章的標(biāo)點(diǎn)符號以及回車字符就可判斷，難點(diǎn)主要在于分詞處理。

在現(xiàn)階段，中文分詞技術(shù)主要分為3種[5]：基于字符串匹配的分詞方法、基于理解的分詞方法、基于統(tǒng)計(jì)的分詞方法。本文選取第一種方法。采用大型的語料庫對輸入的需要測試的文本進(jìn)行詞語比對，然后對其進(jìn)行分割詞匯操作。這種方法對于英文同樣適用，只需在語料庫中錄入英文的語料庫即可對英語進(jìn)行分詞。

2.2 TF-IDF算法計(jì)算權(quán)重

本文在計(jì)算特征詞權(quán)值時(shí)使用了詞頻-逆文檔頻率TF-IDF(Term Frequency-Inverse Document Frequency)[6]算法。其中：TF為詞頻，用來計(jì)算文檔中詞語出現(xiàn)的頻率；IDF為逆文檔頻率，用來排除一些副詞、介詞等無意義的高頻詞語。

計(jì)算詞頻TF使用的公式如下：

(1)

計(jì)算逆文檔頻率IDF所采用的公式如下式所示：

(2)

其中，t表示被測試的詞語，D表示總文檔集，N表示文檔的總個(gè)數(shù)，nt表示含有被測詞t的文檔數(shù)量。在單文檔摘要系統(tǒng)中，N則代表句子的總個(gè)數(shù)，nt代表含有被測詞t的句子數(shù)量。nt越大，表示被測詞t的新穎度越低，多為無意義的虛詞。式(2)可以看出nt越大，IDF值越小，因此可以體現(xiàn)詞語具有實(shí)際意義程度。

為了達(dá)到綜合考慮的效果，將TF與IDF二者評分相乘，即最后的單個(gè)詞語權(quán)值如下：

W=TF·IDF

(3)

和傳統(tǒng)計(jì)算詞頻求特征值相比，采用TF-IDF算法能夠有效排除虛詞等無實(shí)義詞的干擾，提高權(quán)值計(jì)算的準(zhǔn)確程度。

2.3VSM計(jì)算段落相似度

向量空間模型VSM(VectorSpaceModel)[7]是常用的相似度計(jì)算模型，在自然語言處理中有著廣泛的應(yīng)用，通常應(yīng)用在多文檔摘要中。如圖3所示，兩個(gè)文本向量的夾角表示的就是它們的相似程度，夾角越小證明兩篇文檔越靠近，即相似度越大[8]。

圖3 VSM文檔相似度比較

多文檔摘要算法中，VSM計(jì)算公式如下：

(4)

式中：T1為文檔1；T2為文檔2；w1k為文檔1中的第k個(gè)特征詞的權(quán)重；w2k為文檔2中的第k個(gè)特征詞的權(quán)重。

在本文設(shè)計(jì)的自動文本摘要系統(tǒng)中，利用VSM，將各個(gè)段落視為小文檔，利用式(4)進(jìn)行段落相似度計(jì)算，如下所示：

(5)

式中：P1為段落1；P2為段落2；W1k為段落1中的第k個(gè)特征詞的權(quán)重；W2k為段落2中的第k個(gè)特征詞的權(quán)重。

由于向量空間的多維性，可以將特征句、特征句權(quán)值和特征句所在段落的權(quán)值以向量形式表現(xiàn)。將特征句權(quán)值、段落權(quán)值初始值均記為0，通過循環(huán)迭代計(jì)算，段落權(quán)值累加直至運(yùn)算結(jié)束，保存在向量中留作評判句子最終權(quán)重的一個(gè)因素。

和其他算法相比，VSM具有將特征詞、特征句、特征段以及權(quán)值構(gòu)建成對應(yīng)關(guān)系模型的特點(diǎn)，方便對其進(jìn)行隨后的摘要句判別篩選。

2.4 LexRank算法綜合評分

因摘要最后以句子形式組合而成，這里采用LexRank算法對文中句子進(jìn)行相似度計(jì)算，本摘要系統(tǒng)設(shè)計(jì)主要包括3步：全文句子的相似度計(jì)算、相鄰句的相似度計(jì)算以及句子最終評分。

1) 全文句子的相似度計(jì)算。將作相似度計(jì)算的兩個(gè)句子S1和S2中的詞語提取出來，分別記作t1,1，t1,2，…，t1,i和t2,1，t2,2，…，t2,j，將它們兩兩作相似度比較，記作sim(t1,i,t2,j)，將其權(quán)值分別記w1,1,w1,2,…,w1,n和w2,1,w2,2,…,w2,m，這里使用的權(quán)值即為前面TF-IDF算法求出的特征詞權(quán)值。所以句子間語義的相似度的如下式所示：

(6)

式中：m1,i為sim(t1,i,t2,j)中的最大值；m2,i為sim(t2,j,t1,i)中的最大值。

2) 相鄰句相似度計(jì)算。在某些情況下，幾個(gè)不需要的句子互相相關(guān)提高其權(quán)重，從而對摘要的品質(zhì)產(chǎn)生負(fù)面影響。然而對于核心句子而言，其附近的句子會圍繞這個(gè)核心展開，即與之相關(guān)程度、自身權(quán)值均保持較高水平。因此考慮設(shè)計(jì)計(jì)算句子S核心程度的公式如下：

(7)

式中，score(S)表示句子S的核心程度，S′表示S附近的句子，degree(S′)表示S′的數(shù)量。

3) 句子最終評分。綜合句子所在段落權(quán)值、句子核心程度以及句子所在物理位置、提示性短語影響等多方面因素，設(shè)計(jì)句子最終評分為：

weight(S)=α·ParaScore+β·Score+

χ·OtherScore

(8)

式中：ParaScore表示段落權(quán)值，OtherScore表示位置、提示性短語其他因素影響評分，通過分別計(jì)算其在被測文檔的平均分，再結(jié)合實(shí)際情況進(jìn)行加權(quán)計(jì)算求得。

2.5 摘要句篩選

本文使用統(tǒng)計(jì)分析的方法確定摘要篩選的閾值，選出得分最高的句子S后，其他句子和S的相似度大于閾值則會被視為冗余句篩除。本文定義提取率如下：

提取率=生成摘要字?jǐn)?shù)/原文字?jǐn)?shù)

(9)

由于閾值的范圍為0～1，以0.1分度對哈爾濱工業(yè)大學(xué)的《哈工大信息檢索研究室單文檔自動文摘語料庫》中文檔測試，確定閾值范圍在0～0.3。再對0～0.35區(qū)間以0.02分度進(jìn)行精確閾值測試，結(jié)果如圖4所示。

為了保證摘要的提取率，還要確保摘要語義完整的最大化，本文根據(jù)圖4確定選擇閾值為0.1。使與S相似度大于0.1的被篩除，其他摘要句按照原文順序排列輸出。

圖4 提取率隨閾值變化示意圖

3 實(shí)驗(yàn)與評測

為了驗(yàn)證設(shè)計(jì)的中文單文檔摘要方法的有效性，本文對TF-IDF計(jì)算結(jié)果、中文摘要結(jié)果進(jìn)行測試，并將結(jié)果與原有方法進(jìn)行了比較。

3.1 TF-IDF計(jì)算結(jié)果

本文對設(shè)計(jì)中各個(gè)詞語的TF-IDF進(jìn)行評分檢查，觀察是否能夠?qū)崿F(xiàn)對文章中各個(gè)詞語的權(quán)值估計(jì)。本文對摘自“新浪網(wǎng)”1篇534字的文章進(jìn)行摘要提取，得到各個(gè)詞語的TF-IDF分值，并對詞語TF-IDF值進(jìn)行統(tǒng)計(jì)，挑選出TF-IDF值大于0的詞語并按照其對應(yīng)的TF-IDF值排序如圖5所示。

圖5 TF-IDF值折線

為驗(yàn)證此TF-IDF值是否對文本摘要結(jié)果產(chǎn)生影響，選擇TF-IDF值排名最高的5個(gè)詞“決定”“民眾”“過程”“家長”“重慶市”進(jìn)行研究，觀察經(jīng)過本文設(shè)計(jì)的中文單文檔摘要提取系統(tǒng)后，生成的摘要句中是否包含這幾個(gè)詞。

圖6中劃線的詞就是TF-IDF值最高的詞，可以看出，摘要的每個(gè)句子都至少包含了一個(gè)TF-IDF值前5的詞語。因此可見TF-IDF在這個(gè)摘要系統(tǒng)中起著重要作用。

3.2 中文摘要結(jié)果

本文對哈爾濱工業(yè)大學(xué)的《哈工大信息檢索研究室單文檔自動文摘語料庫》進(jìn)行測試，將系統(tǒng)生成的摘要與專家摘要用Edmundson方法[9]加以測評。Edmundson方法比較的是句子，計(jì)算公式如下：

重合率p=匹配句子數(shù)/專家摘要句子數(shù)×100%

(10)

其中，匹配句子數(shù)指的是生成摘要與專家摘要相同的句子的數(shù)量。

圖6 摘要結(jié)果

測試語料提取率/%原文的10%專家摘要重合率/%原文的20%專家摘要重合率/%奧運(yùn)22．6332．6728．56記敘文13．6128．5726．33說明文11．4737．6429．49議論文21．2039．4240．33應(yīng)用文9．37531．7620．44

從表1以及圖7可以看出，在提取率在10%～20%時(shí)，本文設(shè)計(jì)的中文單文檔摘要系統(tǒng)對于各種文體均能夠有較好的摘要效果，且和原文的10%專家摘要進(jìn)行比對的效果要好于原文的20%專家摘要，因此本系統(tǒng)對提取最大核心句效果較好。

圖7 中文摘要提取結(jié)果

系統(tǒng)速度方面，為了測試系統(tǒng)速度，選擇《百年孤獨(dú)》的前4個(gè)章節(jié)。由于篇幅過大，使用txt文件進(jìn)行比較分析。進(jìn)行摘要計(jì)算的文件為 91 653B，摘要結(jié)果為 27 247B，因此提取率為29.73%，可見該方法能夠?qū)崿F(xiàn)長文本中文單文檔提取摘要。而且實(shí)驗(yàn)用時(shí)小于15s，因此證明系統(tǒng)運(yùn)行比較流暢、高效、快速。

3.3 與原有方法比較

在保證相同提取率的前提下，本文將改進(jìn)的算法與只使用詞頻、TF-IDF算法對《哈工大信息檢索研究室單文檔自動文摘語料庫》中語料進(jìn)行摘要提取的比較測試，Edmundson測評結(jié)果如圖8、圖9所示。

圖8 原文的10%專家摘要重合率結(jié)果

圖9 原文的20%專家摘要重合率結(jié)果

從圖8、圖9可以看出，本文設(shè)計(jì)的改進(jìn)的基于LexRank算法中文單文檔摘要系統(tǒng)在各種測試文體中表現(xiàn)均顯著優(yōu)于基于詞頻、基于TF-IDF算法。

4 結(jié)論

針對目前中文自動文本摘要提取方法準(zhǔn)確度不夠高、計(jì)算方法速度較慢的問題，本文提出設(shè)計(jì)一個(gè)改進(jìn)的中文單文檔摘要系統(tǒng)。該系統(tǒng)基于LexRank算法，將VSM、TF-IDF算法結(jié)合進(jìn)去，達(dá)到了較好的摘要提取效果。

從實(shí)驗(yàn)結(jié)果看，它計(jì)算速度快，摘要效果良好，和基于詞頻、TF-IDF算法相比能夠顯著提高摘要水平，達(dá)到預(yù)期的實(shí)驗(yàn)設(shè)計(jì)目的。

本系統(tǒng)的核心思想所涉及的信息挖掘技術(shù)、信息分類技術(shù)、信息索引技術(shù)等在現(xiàn)今信息化的社會，還具有極高的現(xiàn)實(shí)意義及實(shí)用價(jià)值。

[1]LUHNHP.TheAutomaticCreationofLiteratureAbstracts[J].IBMJournalofResearchandDevelopment，1958,2(2):159.

[2]WANGYongcheng.AutomaticExtractionofWordsfromChineseTextualData[J].JournalofComputerScienceandTechnology，1987,2(4):287-291.

[3] 胡俠.自動文本摘要技術(shù)綜述[J].情報(bào)雜志，2010,29(8):144-147.

[4]GUNESE,RADEVDR.LexRank:Graph-BasedCentralityasSalienceinTextSummarization[J].JournalofArtificialIntelligenceResearch,2004,22(10):51-54.

[5] 楊陽.基于Web知識的中文分詞結(jié)果優(yōu)化[J].計(jì)算機(jī)應(yīng)用與軟件，2015,32(12):55-58.[6]AKIKOA.AnInformation-TheoreticPerspectiveofTF-IDFMeasures[J].InformationProcessingandManagement，2002(7):52-57.

[7] 陳炎龍.基于向量空間模型的英文文本難度判定[J].電腦知識與技術(shù)，2010,12(6):101-107.

[8] 劉曉麗.文本分類檢索技術(shù)在工程中的應(yīng)用[J].無線電工程，2008,38(10):44-49.

[9]EDMUNDSONHP.NewMethodsinAutomaticExtracting[J].JournaloftheACM，1969,16(2):264.

[10]劉星含.基于互信息的文本自動摘要[J].合肥工業(yè)大學(xué)學(xué)報(bào)，2014,37(10):1198-1203.

[11]曾哲軍.基于連續(xù)LexRank的多文本自動摘要優(yōu)化算法研究[J].計(jì)算機(jī)應(yīng)用與軟件，2013,30(10):209-212.

[12]紀(jì)文倩.一種基于LexRank算法的改進(jìn)的自動文摘系統(tǒng)[J].計(jì)算機(jī)科學(xué)，2010,37(5):151-154.

(責(zé)任編輯 楊繼森)

Chinese Single Document Summarization Based on LexRank

LIU Hai-yan, ZHANG Yu

(1.Department of Information Engineering, Academy of Armored Force Engineering, Beijing 10072, China)

Chinese automatic text summarization mainly uses the method based on key words’ frequencies, the method based on physical location and the clustering statistics method at present, but the accuracy is low, besides, they are not suitable for the single document summarization. To solve these problems, an improved Chinese single document summarization is mentioned. This improved method combines LexRank algorithm with VSM, and takes full account of factors, such as key words, key sentences and key paragraphs’ physical location. Then this designed method is tested by using java language. It turned out that the improved automatic text summarization method can achieve the automatic summarization of the article better than the traditional abstract ones. This summarization method can also be applied in the fields of information mining, information classification, information indexing and else. In this information society, this method has a high practical significance and practical value.

summary; LexRank algorithm; VSM; evaluation

2017-03-05；

2017-03-30

劉海燕(1970—)，女，博士，教授，碩士生導(dǎo)師，主要從事信息安全與網(wǎng)絡(luò)對抗研究。

張鈺(1994—)，女，碩士研究生，主要從事信息安全與網(wǎng)絡(luò)對抗研究。

10.11809/scbgxb2017.06.019

format:LIU Hai-yan, ZHANG Yu.Chinese Single Document Summarization Based on LexRank [J].Journal of Ordnance Equipment Engineering,2017(6):85-89.

TP393

A

2096-2304(2017)06-0085-05

本文引用格式：劉海燕，張鈺.基于LexRank的中文單文檔摘要方法[J].兵器裝備工程學(xué)報(bào)，2017(6):85-89.