何春輝,李云翔,王孟然,王夢(mèng)賢
?
改進(jìn)的TextRank雙層單文檔摘要提取算法
何春輝1,李云翔2,王孟然3,王夢(mèng)賢4
(1. 湘潭大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,湖南 湘潭 411105;2. 湖南城市學(xué)院 理學(xué)院,湖南 益陽 413000;3. 長沙縣印山學(xué)校,長沙 410135;4. 湖南城市學(xué)院 管理學(xué)院,湖南 益陽 413000)
本文提出了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法和改進(jìn)的TextRank雙層單文檔摘要提取算法﹒摘要提取算法采用了分層結(jié)構(gòu),在不同層上融合了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法,同時(shí)使用了長句和短句兩種不同分割方式相結(jié)合的策略來構(gòu)建摘要提取算法﹒用手工整理的中文單文檔摘要數(shù)據(jù)集驗(yàn)證了算法的性能,結(jié)果表明:提取的摘要質(zhì)量非常好﹒
TextRank;信息抽??;摘要算法;累計(jì)貢獻(xiàn)率
隨著信息技術(shù)的發(fā)展,文本數(shù)據(jù)出現(xiàn)了指數(shù)級(jí)的增長趨勢(shì)﹒面對(duì)如此豐富多樣的信息,如何從大量的文本內(nèi)容中快速篩選出自己所需信息就顯得格外重要﹒文本摘要提取算法起源于1958年,最初由IBM公司的H. P. Luhn[1]提出﹒國內(nèi)在摘要提取算法方面的研究起步較晚,早期的文本摘要系統(tǒng)由王永成[2]教授在1988年研制成功﹒通過對(duì)文獻(xiàn)[3]的分析發(fā)現(xiàn)目前主流的文本自動(dòng)摘要提取算法主要分為了2大類:一類是生成式摘要提取算法,它們對(duì)大規(guī)模數(shù)據(jù)集的依賴程度很大,而且算法計(jì)算復(fù)雜度較高,目前還處于理論研究階段;另一類是抽取式摘要提取算法,該類算法計(jì)算復(fù)雜度低、易操作,因此應(yīng)用較廣泛,但算法通常是以單一句子為單元進(jìn)行摘要抽取,生成的摘要會(huì)包含一些噪聲數(shù)據(jù)﹒
對(duì)于摘要句的篩選方式,目前主流的做法就是根據(jù)句子的重要度進(jìn)行降序排序,然后采用某種指標(biāo)來選取重要度排名靠前的句子進(jìn)行合并來生成文檔的摘要﹒目前這些主流的摘要句篩選方法還不是很成熟,不利于提取高質(zhì)量的摘要﹒
為了克服現(xiàn)有算法的不足,在摘要句篩選方面,提出了一個(gè)基于累積貢獻(xiàn)率的摘要句篩選算法;摘要提取算法方面,在經(jīng)典TextRank算法基礎(chǔ)上提出了改進(jìn)的TextRank雙層單文檔摘要提取算法﹒文章各節(jié)內(nèi)容分別對(duì)TextRank算法進(jìn)行了相關(guān)介紹,根據(jù)相關(guān)文獻(xiàn)資料詳細(xì)闡述了文檔句子重要度計(jì)算方法,給出了基于句子重要度累積貢獻(xiàn)率的摘要句篩選算法的步驟和改進(jìn)的TextRank雙層單文檔摘要提取算法的流程圖及核心步驟,最后用相應(yīng)的數(shù)據(jù)集來驗(yàn)證了算法的性能并根據(jù)實(shí)驗(yàn)結(jié)果給出了相應(yīng)的結(jié)論﹒
TextRank[4]算法是Mihalcea和Tarau于2004年在自動(dòng)摘要提取任務(wù)中得到的成果,原理與PageRank[5]算法類似,但它未考慮文檔的篇章結(jié)構(gòu)等信息﹒為提升算法性能,有學(xué)者提出了改進(jìn)的iTextRank[6]摘要提取算法來提高摘要質(zhì)量﹒
文檔經(jīng)過預(yù)處理以后,得到段落、句子、詞語等信息﹒本文采用詞頻-逆文檔頻率TF-IDF[7]算法計(jì)算詞語的權(quán)重﹒詞頻TF的計(jì)算公式為
下一步結(jié)合空間向量模型并采用余弦距離計(jì)算句子間的相似度,余弦距離計(jì)算公式為
矩陣的所有元素是由各個(gè)句子間的相似度構(gòu)成,它是一個(gè)對(duì)稱矩陣,且對(duì)角線上元素均為1﹒
經(jīng)過了文本預(yù)處理步驟一篇文檔會(huì)被分解成若干個(gè)句子,相似句去重后,通過2.2節(jié)的方法計(jì)算文檔里面所有句子的重要度結(jié)果,根據(jù)結(jié)果來篩選摘要句﹒對(duì)于摘要句的篩選方式,本文提出了基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法,該算法可以根據(jù)設(shè)定的累積貢獻(xiàn)率閾值自動(dòng)給出文檔中摘要句子的集合﹒其如下:
算法輸入:向量和累積貢獻(xiàn)率閾值0
算法輸出:文檔的摘要句子總數(shù)
步驟(1):輸入非空向量=[1,2,3,...,n],0;
步驟(2):求句子重要度總和,即=sum(r),(=1,2,...,);
步驟(4):計(jì)算累積貢獻(xiàn)率得到摘要句子總數(shù)sent_num的值,再循環(huán)執(zhí)行:(=1,
if(>=0){//判斷當(dāng)前累積貢獻(xiàn)率是否達(dá)到了設(shè)定的累計(jì)貢獻(xiàn)率閾值0
sent_num=;//獲取摘要句子總數(shù)
break;//跳出循環(huán),得到sent_num
}else{
=+1;
}
銳騏6正是在“SS”六大標(biāo)準(zhǔn)下,基于日產(chǎn)納瓦拉平臺(tái)全新打造,是一款具備合資基因、國產(chǎn)價(jià)格的高品質(zhì)SUV級(jí)皮卡。
}
步驟(5):return sent_num;//返回摘要句子的總數(shù)﹒
根據(jù)上述算法步驟可以自動(dòng)獲取文檔的摘要句子總數(shù)sent_num,結(jié)合句子重要度向量降序排名結(jié)果,可取出所有句子中重要度排名在前sent_num的句子作為摘要句,根據(jù)這些摘要句的重要度在未排序的句子重要度向量P中找到與之對(duì)應(yīng)的值所在的下標(biāo),根據(jù)下標(biāo)值找到對(duì)應(yīng)的原始句子,按照出現(xiàn)先后順序?qū)⒄页鼍渥拥膬?nèi)容進(jìn)行合并生成最終的摘要﹒這個(gè)算法考慮了句子總數(shù)和句子本身內(nèi)容所帶有的重要度信息來自動(dòng)篩選摘要句,能較好的彌足現(xiàn)有算法的不足﹒
現(xiàn)有抽取式摘要提取算法大都以句子為單位進(jìn)行抽取,這樣會(huì)導(dǎo)致句子存在很高的相似度時(shí),算法無法避免對(duì)相似句子的計(jì)算,從而影響摘要質(zhì)量﹒為了較好的解決該問題,本文主要作如下改進(jìn):將抽取式的文本自動(dòng)摘要算法當(dāng)做一個(gè)過濾的過程,把摘要提取算法當(dāng)作一個(gè)過濾器,可通過增加過濾器的層數(shù)或者改變過濾器的內(nèi)部結(jié)構(gòu)來減少過濾后留下的噪聲﹒基于這種啟發(fā),提出了改進(jìn)的TextRank雙層單文檔摘要提取算法,算法的具體流程圖如圖1所示﹒
根據(jù)圖1所示的流程圖,下面對(duì)算法實(shí)施方式及各參數(shù)的取值情況和兩層之間存在差異性的步驟給出相關(guān)說明﹒算法在結(jié)構(gòu)上分了兩層,從表面上看第1層與第2層大致是相同的,但功能卻不一樣,因此一些關(guān)鍵步驟的處理方式存在較大差異﹒算法核心步驟及具體差異說明如下:
算法輸入:?jiǎn)纹形奈臋n的內(nèi)容
算法輸出:對(duì)應(yīng)文檔提取的摘要內(nèi)容
步驟(1):文檔分句及預(yù)處理步驟﹒主要是對(duì)文檔執(zhí)行分句、去除特殊字符及空格、舍棄長度較短的句子、分詞、計(jì)算詞語的TF-IDF值等常規(guī)的預(yù)處理操作﹒第1層和第2層除了文檔的分句標(biāo)準(zhǔn)與舍棄長度較短的句子上存在差異之外,其余地方無差異﹒第1層是精篩層,句子切分的細(xì)粒度較粗,分句的不同在于第1層中采用漢語中常用的句號(hào)、問號(hào)、分號(hào)、感嘆號(hào)、冒號(hào)、省略號(hào)這6個(gè)符號(hào)作為分句標(biāo)準(zhǔn),這樣便于快速有效的篩選出重要的長句;第2層是一個(gè)去噪層,分句標(biāo)準(zhǔn)是在第1層的基礎(chǔ)上加了逗號(hào),這樣就將原始長句變成細(xì)粒度更小的短句,方便剔除原始句子中的噪聲﹒在舍棄較短的句子方面,第1層精篩層主要是舍棄長度為零的空句,第2層去噪層主要是舍棄長度小于4的句子,經(jīng)測(cè)試可以有效降低噪聲﹒
圖1 改進(jìn)的TextRank雙層單文檔摘要提取算法
步驟(2):計(jì)算所有句子間的相似度﹒這一步利用公式(3)來進(jìn)行求解,對(duì)句子相似度高于90%的句子進(jìn)行后向去重,并對(duì)重復(fù)句子做出特殊標(biāo)記,這樣可避免計(jì)算重復(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é)句子重要度,計(jì)算方式見式(5),此步兩層之間無差異﹒
步驟(6):迭代計(jì)算句子重要度向量P,計(jì)算方式見式(6),此步驟兩層之間處理方式無差異﹒
步驟(7):判斷句子重要度向量P是否收斂﹒若否,返回步驟(5);若是,輸出句子重要度向量P,此步兩層之間無差異﹒
步驟(8):將上一步得到的句子重要度向量的元素值按照降序方式進(jìn)行排序,此步驟兩層之間無差異﹒
步驟(9):摘要句篩選算法﹒其具體計(jì)算過程在2.2節(jié)的摘要句篩選算法部分給出了詳細(xì)描述,這是本文的核心部分,在兩層之間存在較大的差異,主要差異在于不同層之間算法設(shè)定的句子重要度累積貢獻(xiàn)率閾值0是不同的﹒第1層是精篩層,目標(biāo)是在大量的句子中選出極少數(shù)重要的句子,根據(jù)實(shí)驗(yàn)測(cè)試發(fā)現(xiàn),算法將第1層的累積貢獻(xiàn)率閾值0設(shè)為0.2會(huì)取得較好效果;而第2層是去噪層,目標(biāo)是剔除前面提出重要句子中的少數(shù)噪聲數(shù)據(jù),經(jīng)試驗(yàn)測(cè)試,發(fā)現(xiàn)將第2層的累積貢獻(xiàn)率閾值0設(shè)為0.8時(shí),算法會(huì)取得較好效果,其余處理方式無差異﹒
步驟(10):摘要文檔的生成﹒經(jīng)過第1層處理后,得到精篩層提取出來的句子列表,根據(jù)這些摘要句子重要度的值在未排序的句子重要度向量P中找到與之對(duì)應(yīng)的值所在的下標(biāo),根據(jù)下標(biāo)值在原始文檔中找出對(duì)應(yīng)句子內(nèi)容,再按照出現(xiàn)的先后順序?qū)⒄页鼍渥拥膬?nèi)容進(jìn)行合并并生成最終的摘要,且將它作為第2層輸入,經(jīng)過第2層的去噪處理后,得到最終的句子列表,然后按照這些摘要句重要度的值在未排序的句子重要度向量P'中找到與之對(duì)應(yīng)的值所在的下標(biāo),根據(jù)下標(biāo)值找出第1層給出的粗摘要文檔中對(duì)應(yīng)句子的內(nèi)容,將找出句子的內(nèi)容按照先后順序進(jìn)行合并,以生成最終的摘要﹒
為了驗(yàn)證摘要句篩選算法的效果,通過隨機(jī)抽取1篇關(guān)于文本挖掘的中文文檔來進(jìn)行自動(dòng)摘要測(cè)試,根據(jù)摘要的質(zhì)量來驗(yàn)證算法的效果﹒本實(shí)驗(yàn)所用的樣例文檔內(nèi)容如下:
文本挖掘是抽取有散布在文本文件中有價(jià)值的知識(shí),并且利用這些知識(shí)更好地組織信息的過程﹒國家重點(diǎn)研究發(fā)展規(guī)劃首批實(shí)施項(xiàng)目中明確指出,文本挖掘是“自然語言理解與知識(shí)挖掘”中的重要內(nèi)容﹒文本挖掘是信息挖掘的一個(gè)研究分支,用于基于文本信息的知識(shí)發(fā)現(xiàn)﹒文本挖掘利用智能算法,如神經(jīng)網(wǎng)絡(luò)、基于案例的推理、可能性推理等,并結(jié)合文字處理技術(shù),分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等,抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系,并按照內(nèi)容對(duì)文檔進(jìn)行分類,獲取有用的知識(shí)和信息﹒文本挖掘是包括數(shù)據(jù)挖掘技術(shù)、信息抽取、信息檢索的交叉學(xué)科﹒
本文算法結(jié)構(gòu)有兩層,實(shí)驗(yàn)中第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,算法自動(dòng)給出了摘要句子數(shù)量為1,然后利用句子重要度最高的句子的下標(biāo)在原始文檔的句子列表中找出相應(yīng)的句子為第4句,對(duì)應(yīng)的句子內(nèi)容為“文本挖掘利用智能算法,如神經(jīng)網(wǎng)絡(luò)、基于案例的推理、可能性推理等,并結(jié)合文字處理技術(shù),分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等,抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系,并按照內(nèi)容對(duì)文檔進(jìn)行分類,獲取有用的知識(shí)和信息﹒”,再將上面句子的內(nèi)容作為粗摘要文檔輸入第2層,經(jīng)過預(yù)處理步驟之后,算法第2層得到了短句子重要度遞減曲線圖及各短句重要度的值,如圖3所示﹒
圖3 第2層短句子重要度遞減曲線圖
根據(jù)圖3結(jié)果,原始短句子一共有7句,設(shè)定的累積貢獻(xiàn)率閾值為0.8,算法自動(dòng)給出了摘要句數(shù)量為5,然后利用句子重要度最高的前5個(gè)句子的下標(biāo)依次在粗摘要文檔的句子列表中找出相應(yīng)的句子為第1、3、4、5、7句,各句對(duì)應(yīng)的原始句子內(nèi)容分別為(中括號(hào)里的內(nèi)容):[文本挖掘利用智能算法,]、[并結(jié)合文字處理技術(shù),]、[分析大量的非結(jié)構(gòu)化文本源如文檔、電子表格、客戶電子郵件、問題查詢、網(wǎng)頁等,]、[抽取或標(biāo)記關(guān)鍵字概念、文字間的關(guān)系,]、[獲取有用的知識(shí)和信息﹒]﹒根據(jù)上述兩份摘要結(jié)果可以看出,第2份摘要的質(zhì)量比第1份摘要的質(zhì)量高很多,在保證摘要的簡(jiǎn)潔性、準(zhǔn)確性和連貫性的同時(shí),有效的剔除了噪聲句子﹒
本文在公開的中文摘要數(shù)據(jù)集[8]LCSTS上,通過人工選擇了6個(gè)領(lǐng)域共1 000篇內(nèi)容比較完善的文檔,按照文檔標(biāo)題表達(dá)的意思,由3個(gè)不同的人從文本內(nèi)容中抽取了相應(yīng)的短句組成目標(biāo)摘要,并且只允許從原文中抽取短句子,不允許根據(jù)原文的理解重新生成新句子,以便跟算法抽取的摘要結(jié)果形成對(duì)比﹒最后,在抽取的數(shù)據(jù)集上進(jìn)行了試驗(yàn),采用Edmundson[9]方法驗(yàn)證算法性能﹒Edmundson方法以句子為單位進(jìn)行比較,用重復(fù)率來評(píng)測(cè),其具體公式為
式(7)中是指提取的摘要句子與目標(biāo)句子內(nèi)容相同的句子數(shù);是指文檔中的句子總數(shù)﹒式(8)中表示文檔總數(shù)量;R表示第篇文檔的重復(fù)率﹒數(shù)據(jù)集一共包含1 000篇文檔,涵蓋了6個(gè)領(lǐng)域,其中混合集是指將以上1 000篇不同的文檔經(jīng)過混合后隨機(jī)抽取200篇文檔組成的混合數(shù)據(jù)集,具體劃分情況見表1﹒
表1 數(shù)據(jù)集在6個(gè)不同領(lǐng)域的劃分
算法在上述數(shù)據(jù)集上的測(cè)試結(jié)果見表2﹒
表2 改進(jìn)TextRank雙層單文檔摘要提取算法在不同數(shù)據(jù)集上的試驗(yàn)結(jié)果
數(shù)據(jù)集說明:因?yàn)長CSTS數(shù)據(jù)集在不同領(lǐng)域所包含的文檔數(shù)量不同,根據(jù)實(shí)際情況,由人工整理了1個(gè)非平衡測(cè)試數(shù)據(jù)集,其中經(jīng)濟(jì)和教育領(lǐng)域各100篇文檔,其余4個(gè)領(lǐng)域以及混合集各200篇文檔﹒根據(jù)表2試驗(yàn)結(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%﹒由實(shí)驗(yàn)結(jié)果可知該算法既可以處理特定領(lǐng)域的摘要提取任務(wù),又能處理多個(gè)交差領(lǐng)域的摘要提取任務(wù),在摘要提取的覆蓋率方面,算法的性能有較大的提升﹒
自動(dòng)文本分類技術(shù)的研究已成為模式識(shí)別領(lǐng)域的一個(gè)熱點(diǎn)[10]﹒文本摘要更是信息抽取領(lǐng)域的一個(gè)難點(diǎn)﹒本文在經(jīng)典TextRank摘要提取算法的基礎(chǔ)上提出了改進(jìn)的TextRank雙層單文檔摘要提取算法,該算法很好的融合了新提出的基于句子重要度的累積貢獻(xiàn)率摘要句篩選算法來構(gòu)建智能的文本摘要提取算法﹒從實(shí)驗(yàn)結(jié)果來看,算法提取的摘要質(zhì)量較高,可適應(yīng)多領(lǐng)域文本摘要提取的任務(wù)﹒而不足之處在于只使用了人工整理的1 000篇中文文檔進(jìn)行驗(yàn)證,算法沒在其它大規(guī)模數(shù)據(jù)集上做相關(guān)測(cè)試﹒未來的工作將嘗試結(jié)合句法依存分析進(jìn)一步的提高自動(dòng)摘要提取算法的性能﹒
[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òng)文摘研究[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的自動(dòng)摘要提取方法[J]. 計(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糾錯(cuò)碼相結(jié)合的多類文本分類算法[J]. 渤海大學(xué)學(xué)報(bào): 自然科學(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
益陽市科技計(jì)劃項(xiàng)目(2014JZ40)
何春輝(1991- ),男,湖南永州人,工程師,碩士,主要從事數(shù)據(jù)挖掘與信息處理研究﹒E-mail: xtuhch@163.com