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

劉海燕，張 鈺

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

?

【信息科學與控制工程】

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

劉海燕，張 鈺

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

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

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

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

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

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

1 LexRank算法

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

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

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

2 改進的中文單文檔摘要系統

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

圖2 中文單文檔摘要流程

2.1 預處理

面對一篇完整的文檔，首先要將其文字轉化成可進行數學計算的模型形式，即首先對其進行預處理，把文章進行分詞、分句、分段。分句和分段分別根據文章的標點符號以及回車字符就可判斷，難點主要在于分詞處理。

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

2.2 TF-IDF算法計算權重

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

計算詞頻TF使用的公式如下：

(1)

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

(2)

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

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

W=TF·IDF

(3)

和傳統計算詞頻求特征值相比，采用TF-IDF算法能夠有效排除虛詞等無實義詞的干擾，提高權值計算的準確程度。

2.3VSM計算段落相似度

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

圖3 VSM文檔相似度比較

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

(4)

式中：T1為文檔1；T2為文檔2；w1k為文檔1中的第k個特征詞的權重；w2k為文檔2中的第k個特征詞的權重。

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

(5)

式中：P1為段落1；P2為段落2；W1k為段落1中的第k個特征詞的權重；W2k為段落2中的第k個特征詞的權重。

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

和其他算法相比，VSM具有將特征詞、特征句、特征段以及權值構建成對應關系模型的特點，方便對其進行隨后的摘要句判別篩選。

2.4 LexRank算法綜合評分

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

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

(6)

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

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

(7)

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

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

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

χ·OtherScore

(8)

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

2.5 摘要句篩選

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

提取率=生成摘要字數/原文字數

(9)

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

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

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

3 實驗與評測

為了驗證設計的中文單文檔摘要方法的有效性，本文對TF-IDF計算結果、中文摘要結果進行測試，并將結果與原有方法進行了比較。

3.1 TF-IDF計算結果

本文對設計中各個詞語的TF-IDF進行評分檢查，觀察是否能夠實現對文章中各個詞語的權值估計。本文對摘自“新浪網”1篇534字的文章進行摘要提取，得到各個詞語的TF-IDF分值，并對詞語TF-IDF值進行統計，挑選出TF-IDF值大于0的詞語并按照其對應的TF-IDF值排序如圖5所示。

圖5 TF-IDF值折線

為驗證此TF-IDF值是否對文本摘要結果產生影響，選擇TF-IDF值排名最高的5個詞“決定”“民眾”“過程”“家長”“重慶市”進行研究，觀察經過本文設計的中文單文檔摘要提取系統后，生成的摘要句中是否包含這幾個詞。

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

3.2 中文摘要結果

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

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

(10)

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

圖6 摘要結果

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

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

圖7 中文摘要提取結果

系統速度方面，為了測試系統速度，選擇《百年孤獨》的前4個章節。由于篇幅過大，使用txt文件進行比較分析。進行摘要計算的文件為 91 653B，摘要結果為 27 247B，因此提取率為29.73%，可見該方法能夠實現長文本中文單文檔提取摘要。而且實驗用時小于15s，因此證明系統運行比較流暢、高效、快速。

3.3 與原有方法比較

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

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

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

從圖8、圖9可以看出，本文設計的改進的基于LexRank算法中文單文檔摘要系統在各種測試文體中表現均顯著優于基于詞頻、基于TF-IDF算法。

4 結論

針對目前中文自動文本摘要提取方法準確度不夠高、計算方法速度較慢的問題，本文提出設計一個改進的中文單文檔摘要系統。該系統基于LexRank算法，將VSM、TF-IDF算法結合進去，達到了較好的摘要提取效果。

從實驗結果看，它計算速度快，摘要效果良好，和基于詞頻、TF-IDF算法相比能夠顯著提高摘要水平，達到預期的實驗設計目的。

本系統的核心思想所涉及的信息挖掘技術、信息分類技術、信息索引技術等在現今信息化的社會，還具有極高的現實意義及實用價值。

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

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

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

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

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

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

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

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

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

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

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

(責任編輯 楊繼森)

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—)，女，博士，教授，碩士生導師，主要從事信息安全與網絡對抗研究。

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

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].兵器裝備工程學報，2017(6):85-89.