何春輝，李云翔，王孟然，王夢賢

?

改進(jìn)的TextRank雙層單文檔摘要提取算法

何春輝1，李云翔2，王孟然3，王夢賢4

(1. 湘潭大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，湖南 湘潭 411105；2. 湖南城市學(xué)院 理學(xué)院，湖南 益陽 413000；3. 長沙縣印山學(xué)校，長沙 410135；4. 湖南城市學(xué)院 管理學(xué)院，湖南 益陽 413000)

本文提出了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法和改進(jìn)的TextRank雙層單文檔摘要提取算法﹒摘要提取算法采用了分層結(jié)構(gòu)，在不同層上融合了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法，同時使用了長句和短句兩種不同分割方式相結(jié)合的策略來構(gòu)建摘要提取算法﹒用手工整理的中文單文檔摘要數(shù)據(jù)集驗證了算法的性能，結(jié)果表明：提取的摘要質(zhì)量非常好﹒

TextRank；信息抽??；摘要算法；累計貢獻(xiàn)率

隨著信息技術(shù)的發(fā)展，文本數(shù)據(jù)出現(xiàn)了指數(shù)級的增長趨勢﹒面對如此豐富多樣的信息，如何從大量的文本內(nèi)容中快速篩選出自己所需信息就顯得格外重要﹒文本摘要提取算法起源于1958年，最初由IBM公司的H. P. Luhn[1]提出﹒國內(nèi)在摘要提取算法方面的研究起步較晚，早期的文本摘要系統(tǒng)由王永成[2]教授在1988年研制成功﹒通過對文獻(xiàn)[3]的分析發(fā)現(xiàn)目前主流的文本自動摘要提取算法主要分為了2大類：一類是生成式摘要提取算法，它們對大規(guī)模數(shù)據(jù)集的依賴程度很大，而且算法計算復(fù)雜度較高，目前還處于理論研究階段；另一類是抽取式摘要提取算法，該類算法計算復(fù)雜度低、易操作，因此應(yīng)用較廣泛，但算法通常是以單一句子為單元進(jìn)行摘要抽取，生成的摘要會包含一些噪聲數(shù)據(jù)﹒

對于摘要句的篩選方式，目前主流的做法就是根據(jù)句子的重要度進(jìn)行降序排序，然后采用某種指標(biāo)來選取重要度排名靠前的句子進(jìn)行合并來生成文檔的摘要﹒目前這些主流的摘要句篩選方法還不是很成熟，不利于提取高質(zhì)量的摘要﹒

為了克服現(xiàn)有算法的不足，在摘要句篩選方面，提出了一個基于累積貢獻(xiàn)率的摘要句篩選算法；摘要提取算法方面，在經(jīng)典TextRank算法基礎(chǔ)上提出了改進(jìn)的TextRank雙層單文檔摘要提取算法﹒文章各節(jié)內(nèi)容分別對TextRank算法進(jìn)行了相關(guān)介紹，根據(jù)相關(guān)文獻(xiàn)資料詳細(xì)闡述了文檔句子重要度計算方法，給出了基于句子重要度累積貢獻(xiàn)率的摘要句篩選算法的步驟和改進(jìn)的TextRank雙層單文檔摘要提取算法的流程圖及核心步驟，最后用相應(yīng)的數(shù)據(jù)集來驗證了算法的性能并根據(jù)實驗結(jié)果給出了相應(yīng)的結(jié)論﹒

1 經(jīng)典TextRank算法

TextRank[4]算法是Mihalcea和Tarau于2004年在自動摘要提取任務(wù)中得到的成果，原理與PageRank[5]算法類似，但它未考慮文檔的篇章結(jié)構(gòu)等信息﹒為提升算法性能，有學(xué)者提出了改進(jìn)的iTextRank[6]摘要提取算法來提高摘要質(zhì)量﹒

2 句子重要度計算和摘要句的篩選方法

2.1 基于TF-IDF和余弦距離計算句子相似度

文檔經(jīng)過預(yù)處理以后，得到段落、句子、詞語等信息﹒本文采用詞頻-逆文檔頻率TF-IDF[7]算法計算詞語的權(quán)重﹒詞頻TF的計算公式為

下一步結(jié)合空間向量模型并采用余弦距離計算句子間的相似度，余弦距離計算公式為

矩陣的所有元素是由各個句子間的相似度構(gòu)成，它是一個對稱矩陣，且對角線上元素均為1﹒

2.2 句子重要度計算方法

2.3 摘要句篩選算法

經(jīng)過了文本預(yù)處理步驟一篇文檔會被分解成若干個句子，相似句去重后，通過2.2節(jié)的方法計算文檔里面所有句子的重要度結(jié)果，根據(jù)結(jié)果來篩選摘要句﹒對于摘要句的篩選方式，本文提出了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法，該算法可以根據(jù)設(shè)定的累積貢獻(xiàn)率閾值自動給出文檔中摘要句子的集合﹒其如下：

算法輸入：向量和累積貢獻(xiàn)率閾值0

算法輸出：文檔的摘要句子總數(shù)

步驟(1)：輸入非空向量=[1，2，3，...，n]，0；

步驟(2)：求句子重要度總和，即=sum(r)，(=1，2，...，)；

步驟(4)：計算累積貢獻(xiàn)率得到摘要句子總數(shù)sent_num的值，再循環(huán)執(zhí)行：(=1，r；//對句子重要度求和，=/；//計算累積貢獻(xiàn)率

if(>=0){//判斷當(dāng)前累積貢獻(xiàn)率是否達(dá)到了設(shè)定的累計貢獻(xiàn)率閾值0

sent_num=；//獲取摘要句子總數(shù)

break；//跳出循環(huán)，得到sent_num

}else{

=+1；

}

銳騏6正是在“SS”六大標(biāo)準(zhǔn)下，基于日產(chǎn)納瓦拉平臺全新打造，是一款具備合資基因、國產(chǎn)價格的高品質(zhì)SUV級皮卡。

}

步驟(5)：return sent_num；//返回摘要句子的總數(shù)﹒

根據(jù)上述算法步驟可以自動獲取文檔的摘要句子總數(shù)sent_num，結(jié)合句子重要度向量降序排名結(jié)果，可取出所有句子中重要度排名在前sent_num的句子作為摘要句，根據(jù)這些摘要句的重要度在未排序的句子重要度向量P中找到與之對應(yīng)的值所在的下標(biāo)，根據(jù)下標(biāo)值找到對應(yīng)的原始句子，按照出現(xiàn)先后順序?qū)⒄页鼍渥拥膬?nèi)容進(jìn)行合并生成最終的摘要﹒這個算法考慮了句子總數(shù)和句子本身內(nèi)容所帶有的重要度信息來自動篩選摘要句，能較好的彌足現(xiàn)有算法的不足﹒

3 改進(jìn)的TextRank雙層單文檔摘要提取算法

現(xiàn)有抽取式摘要提取算法大都以句子為單位進(jìn)行抽取，這樣會導(dǎo)致句子存在很高的相似度時，算法無法避免對相似句子的計算，從而影響摘要質(zhì)量﹒為了較好的解決該問題，本文主要作如下改進(jìn)：將抽取式的文本自動摘要算法當(dāng)做一個過濾的過程，把摘要提取算法當(dāng)作一個過濾器，可通過增加過濾器的層數(shù)或者改變過濾器的內(nèi)部結(jié)構(gòu)來減少過濾后留下的噪聲﹒基于這種啟發(fā)，提出了改進(jìn)的TextRank雙層單文檔摘要提取算法，算法的具體流程圖如圖1所示﹒

根據(jù)圖1所示的流程圖，下面對算法實施方式及各參數(shù)的取值情況和兩層之間存在差異性的步驟給出相關(guān)說明﹒算法在結(jié)構(gòu)上分了兩層，從表面上看第1層與第2層大致是相同的，但功能卻不一樣，因此一些關(guān)鍵步驟的處理方式存在較大差異﹒算法核心步驟及具體差異說明如下：

算法輸入：單篇中文文檔的內(nèi)容

算法輸出：對應(yīng)文檔提取的摘要內(nèi)容

步驟(1)：文檔分句及預(yù)處理步驟﹒主要是對文檔執(zhí)行分句、去除特殊字符及空格、舍棄長度較短的句子、分詞、計算詞語的TF-IDF值等常規(guī)的預(yù)處理操作﹒第1層和第2層除了文檔的分句標(biāo)準(zhǔn)與舍棄長度較短的句子上存在差異之外，其余地方無差異﹒第1層是精篩層，句子切分的細(xì)粒度較粗，分句的不同在于第1層中采用漢語中常用的句號、問號、分號、感嘆號、冒號、省略號這6個符號作為分句標(biāo)準(zhǔn)，這樣便于快速有效的篩選出重要的長句；第2層是一個去噪層，分句標(biāo)準(zhǔn)是在第1層的基礎(chǔ)上加了逗號，這樣就將原始長句變成細(xì)粒度更小的短句，方便剔除原始句子中的噪聲﹒在舍棄較短的句子方面，第1層精篩層主要是舍棄長度為零的空句，第2層去噪層主要是舍棄長度小于4的句子，經(jīng)測試可以有效降低噪聲﹒

圖1 改進(jìn)的TextRank雙層單文檔摘要提取算法

步驟(2)：計算所有句子間的相似度﹒這一步利用公式(3)來進(jìn)行求解，對句子相似度高于90%的句子進(jìn)行后向去重，并對重復(fù)句子做出特殊標(biāo)記，這樣可避免計算重復(fù)句子與其它句子之間的相似度，此步驟兩層之間的處理方式無差異﹒

步驟(3)：相似句子去重﹒此步只在第1層中設(shè)置，第2層中未設(shè)置，它的功能是從原始文檔的句子列表中剔除掉第1層在步驟(2)中做了特殊標(biāo)記的句子﹒

步驟(4)：根據(jù)句子間相似度來構(gòu)建權(quán)重轉(zhuǎn)移矩陣SS×n，構(gòu)建方式如公式(4)所示，此步兩層之間無差異﹒

步驟(5)：根據(jù)權(quán)重轉(zhuǎn)移矩陣來調(diào)節(jié)句子重要度，計算方式見式(5)，此步兩層之間無差異﹒

步驟(6)：迭代計算句子重要度向量P，計算方式見式(6)，此步驟兩層之間處理方式無差異﹒

步驟(7)：判斷句子重要度向量P是否收斂﹒若否，返回步驟(5)；若是，輸出句子重要度向量P，此步兩層之間無差異﹒

步驟(8)：將上一步得到的句子重要度向量的元素值按照降序方式進(jìn)行排序，此步驟兩層之間無差異﹒

步驟(9)：摘要句篩選算法﹒其具體計算過程在2.2節(jié)的摘要句篩選算法部分給出了詳細(xì)描述，這是本文的核心部分，在兩層之間存在較大的差異，主要差異在于不同層之間算法設(shè)定的句子重要度累積貢獻(xiàn)率閾值0是不同的﹒第1層是精篩層，目標(biāo)是在大量的句子中選出極少數(shù)重要的句子，根據(jù)實驗測試發(fā)現(xiàn)，算法將第1層的累積貢獻(xiàn)率閾值0設(shè)為0.2會取得較好效果；而第2層是去噪層，目標(biāo)是剔除前面提出重要句子中的少數(shù)噪聲數(shù)據(jù)，經(jīng)試驗測試，發(fā)現(xiàn)將第2層的累積貢獻(xiàn)率閾值0設(shè)為0.8時，算法會取得較好效果，其余處理方式無差異﹒

步驟(10)：摘要文檔的生成﹒經(jīng)過第1層處理后，得到精篩層提取出來的句子列表，根據(jù)這些摘要句子重要度的值在未排序的句子重要度向量P中找到與之對應(yīng)的值所在的下標(biāo)，根據(jù)下標(biāo)值在原始文檔中找出對應(yīng)句子內(nèi)容，再按照出現(xiàn)的先后順序?qū)⒄页鼍渥拥膬?nèi)容進(jìn)行合并并生成最終的摘要，且將它作為第2層輸入，經(jīng)過第2層的去噪處理后，得到最終的句子列表，然后按照這些摘要句重要度的值在未排序的句子重要度向量P'中找到與之對應(yīng)的值所在的下標(biāo)，根據(jù)下標(biāo)值找出第1層給出的粗摘要文檔中對應(yīng)句子的內(nèi)容，將找出句子的內(nèi)容按照先后順序進(jìn)行合并，以生成最終的摘要﹒

4 算法驗證

4.1 摘要句篩選算法的驗證

為了驗證摘要句篩選算法的效果，通過隨機(jī)抽取1篇關(guān)于文本挖掘的中文文檔來進(jìn)行自動摘要測試，根據(jù)摘要的質(zhì)量來驗證算法的效果﹒本實驗所用的樣例文檔內(nèi)容如下：

文本挖掘是抽取有散布在文本文件中有價值的知識，并且利用這些知識更好地組織信息的過程﹒國家重點研究發(fā)展規(guī)劃首批實施項目中明確指出，文本挖掘是“自然語言理解與知識挖掘”中的重要內(nèi)容﹒文本挖掘是信息挖掘的一個研究分支，用于基于文本信息的知識發(fā)現(xiàn)﹒文本挖掘利用智能算法，如神經(jīng)網(wǎng)絡(luò)、基于案例的推理、可能性推理等，并結(jié)合文字處理技術(shù)，分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等，抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系，并按照內(nèi)容對文檔進(jìn)行分類，獲取有用的知識和信息﹒文本挖掘是包括數(shù)據(jù)挖掘技術(shù)、信息抽取、信息檢索的交叉學(xué)科﹒

本文算法結(jié)構(gòu)有兩層，實驗中第1層累積貢獻(xiàn)率閾值為0.2，第2層累積貢獻(xiàn)率閾值為0.8﹒根據(jù)算法結(jié)構(gòu)，第1層得到了長句子重要度遞減曲線圖和各句重要度的值，結(jié)果如圖2所示﹒

圖2 第1層長句子重要度遞減曲線圖

根據(jù)圖2的結(jié)果，原始句子一共有5句，結(jié)合設(shè)定的累積貢獻(xiàn)率閾值0.2，算法自動給出了摘要句子數(shù)量為1，然后利用句子重要度最高的句子的下標(biāo)在原始文檔的句子列表中找出相應(yīng)的句子為第4句，對應(yīng)的句子內(nèi)容為“文本挖掘利用智能算法，如神經(jīng)網(wǎng)絡(luò)、基于案例的推理、可能性推理等，并結(jié)合文字處理技術(shù)，分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等，抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系，并按照內(nèi)容對文檔進(jìn)行分類，獲取有用的知識和信息﹒”，再將上面句子的內(nèi)容作為粗摘要文檔輸入第2層，經(jīng)過預(yù)處理步驟之后，算法第2層得到了短句子重要度遞減曲線圖及各短句重要度的值，如圖3所示﹒

圖3 第2層短句子重要度遞減曲線圖

根據(jù)圖3結(jié)果，原始短句子一共有7句，設(shè)定的累積貢獻(xiàn)率閾值為0.8，算法自動給出了摘要句數(shù)量為5，然后利用句子重要度最高的前5個句子的下標(biāo)依次在粗摘要文檔的句子列表中找出相應(yīng)的句子為第1、3、4、5、7句，各句對應(yīng)的原始句子內(nèi)容分別為(中括號里的內(nèi)容)：[文本挖掘利用智能算法，]、[并結(jié)合文字處理技術(shù)，]、[分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等，]、[抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系，]、[獲取有用的知識和信息﹒]﹒根據(jù)上述兩份摘要結(jié)果可以看出，第2份摘要的質(zhì)量比第1份摘要的質(zhì)量高很多，在保證摘要的簡潔性、準(zhǔn)確性和連貫性的同時，有效的剔除了噪聲句子﹒

4.2 改進(jìn)的TextRank雙層單文檔摘要提取算法在不同數(shù)據(jù)集上的試驗對比

本文在公開的中文摘要數(shù)據(jù)集[8]LCSTS上，通過人工選擇了6個領(lǐng)域共1 000篇內(nèi)容比較完善的文檔，按照文檔標(biāo)題表達(dá)的意思，由3個不同的人從文本內(nèi)容中抽取了相應(yīng)的短句組成目標(biāo)摘要，并且只允許從原文中抽取短句子，不允許根據(jù)原文的理解重新生成新句子，以便跟算法抽取的摘要結(jié)果形成對比﹒最后，在抽取的數(shù)據(jù)集上進(jìn)行了試驗，采用Edmundson[9]方法驗證算法性能﹒Edmundson方法以句子為單位進(jìn)行比較，用重復(fù)率來評測，其具體公式為

式(7)中是指提取的摘要句子與目標(biāo)句子內(nèi)容相同的句子數(shù)；是指文檔中的句子總數(shù)﹒式(8)中表示文檔總數(shù)量；R表示第篇文檔的重復(fù)率﹒數(shù)據(jù)集一共包含1 000篇文檔，涵蓋了6個領(lǐng)域，其中混合集是指將以上1 000篇不同的文檔經(jīng)過混合后隨機(jī)抽取200篇文檔組成的混合數(shù)據(jù)集，具體劃分情況見表1﹒

表1 數(shù)據(jù)集在6個不同領(lǐng)域的劃分

算法在上述數(shù)據(jù)集上的測試結(jié)果見表2﹒

表2 改進(jìn)TextRank雙層單文檔摘要提取算法在不同數(shù)據(jù)集上的試驗結(jié)果

數(shù)據(jù)集說明：因為LCSTS數(shù)據(jù)集在不同領(lǐng)域所包含的文檔數(shù)量不同，根據(jù)實際情況，由人工整理了1個非平衡測試數(shù)據(jù)集，其中經(jīng)濟(jì)和教育領(lǐng)域各100篇文檔，其余4個領(lǐng)域以及混合集各200篇文檔﹒根據(jù)表2試驗結(jié)果可看出，算法在不同數(shù)據(jù)集上的性能表現(xiàn)良好，在科技領(lǐng)域的數(shù)據(jù)集上表現(xiàn)最好，平均重復(fù)率達(dá)到了79.8%；教育領(lǐng)域表現(xiàn)一般，平均重復(fù)率只有74.7%；在混合集上的平均重復(fù)率為78.1%﹒由實驗結(jié)果可知該算法既可以處理特定領(lǐng)域的摘要提取任務(wù)，又能處理多個交差領(lǐng)域的摘要提取任務(wù)，在摘要提取的覆蓋率方面，算法的性能有較大的提升﹒

5 結(jié)論

自動文本分類技術(shù)的研究已成為模式識別領(lǐng)域的一個熱點[10]﹒文本摘要更是信息抽取領(lǐng)域的一個難點﹒本文在經(jīng)典TextRank摘要提取算法的基礎(chǔ)上提出了改進(jìn)的TextRank雙層單文檔摘要提取算法，該算法很好的融合了新提出的基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法來構(gòu)建智能的文本摘要提取算法﹒從實驗結(jié)果來看，算法提取的摘要質(zhì)量較高，可適應(yīng)多領(lǐng)域文本摘要提取的任務(wù)﹒而不足之處在于只使用了人工整理的1 000篇中文文檔進(jìn)行驗證，算法沒在其它大規(guī)模數(shù)據(jù)集上做相關(guān)測試﹒未來的工作將嘗試結(jié)合句法依存分析進(jìn)一步的提高自動摘要提取算法的性能﹒

[1]LUHN H P. The automatic creation of literature abstracts[J]. IBM Journal of Research and Development, 1958, 2(2): 159-165.

[2]WANG Y C. Automatic extraction of words from Chinese textual data[J]. Journal of Computer Science and Technology, 1987, 2(4): 287-291.

[3]曹洋. 基于TextRank算法的單文檔自動文摘研究[D]. 江蘇: 南京大學(xué), 2016.

[4]MIHALCEA R, TARAU P. Textrank: Bringing order into texts[C]. Conference on Empirical Methods in Natural Language Processing, EMNLP 2004, 2004: 404-411.

[5]PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: Bringing order to the web[J]. Stanford Digital Libraries Working Paper, 1998, 9(1): 1-17.

[6]余珊珊, 蘇錦鈿, 李鵬飛. 基于改進(jìn)的TextRank的自動摘要提取方法[J]. 計算機(jī)科學(xué), 2016, 43(6): 240-247.

[7]AIZAWA A. An information-theoretic perspective of TF–IDF measures[J]. Information Processing & Management, 2003, 39(1): 45-65.

[8]HU B T, CHEN Q C, ZHU F Z. LCSTS: A large scale Chinese short text summarization dataset[J]. Computer Science, 2015, 1967-1972.

[9]EDMUNDSON H P. New methods in automatic extracting[J]. Journal of the Acm, 1969, 16(2): 264-285.

[10]秦玉平, 邱鳳鳳, 冷強(qiáng)奎. 組合凸線器和Hadamard糾錯碼相結(jié)合的多類文本分類算法[J]. 渤海大學(xué)學(xué)報: 自然科學(xué)版, 2017, 38(1): 71-75.

(責(zé)任編校：龔倫峰)

Improved TextRank Double Layers Single-document Summation Extracting Algorithm

HE Chunhui1, LI Yunxiang2, WANG Mengran3, WANG Mengxian4

(1. School of Mathematics and Computational Sciences, Xiangtan University, Xiangtan, Hunan 411105, China; 2. School of Science, Hunan City University, Yiyang, Hunan 413000, China; 3. Yinshan School of Changsha County , Changsha, Hunan 410135,China; 4. School of Management, Hunan City University, Yiyang, Hunan 413000, China)

A summation sentence selection algorithm based on accumulating contribution rate of sentence importance and an improved TextRank double layers single-document summation extraction algorithm are proposed in this paper. The summation extraction algorithm adopts the hierarchical structure, on the different layer, the summation sentence selection algorithm based on accumulating contribution rate of sentence importance is blended, at the same time, using long sentences and short sentences in two different ways to construct summation extraction algorithm. The manual finishing Chinese single-document summation data set is used to verify the performance of the algorithm, the results show that the quality of the extraction summation is very fine.

TextRank; information extraction; summation algorithm; accumulating contribution rate

TP391

A

10.3969/j.issn.1672-7304.2017.06.0012

1672–7304(2017)06–0055–06

2017-10-23

益陽市科技計劃項目(2014JZ40)

何春輝(1991- )，男，湖南永州人，工程師，碩士，主要從事數(shù)據(jù)挖掘與信息處理研究﹒E-mail: xtuhch@163.com