張 璐，曹 杰，蒲朝儀，伍之昂

(南京財(cái)經(jīng)大學(xué) 江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室，南京 210023) (*通信作者電子郵箱luzhang@njue.edu.cn)

基于詞句協(xié)同排序的單文檔自動(dòng)摘要算法

張 璐*，曹 杰，蒲朝儀，伍之昂

(南京財(cái)經(jīng)大學(xué) 江蘇省電子商務(wù)重點(diǎn)實(shí)驗(yàn)室，南京 210023) (*通信作者電子郵箱luzhang@njue.edu.cn)

對(duì)于節(jié)錄式自動(dòng)摘要需要從文檔中提取一定數(shù)量的重要句子，以生成涵蓋原文主旨的短文的問題，提出一種基于詞句協(xié)同排序的單文檔自動(dòng)摘要算法，將詞句關(guān)系融入以圖排序?yàn)榛A(chǔ)的句子權(quán)重計(jì)算過程中。首先給出了算法中詞句協(xié)同計(jì)算的框架；然后轉(zhuǎn)化為簡(jiǎn)潔的矩陣表示形式，并從理論上證明了收斂性；最后進(jìn)一步通過去冗余方法提高自動(dòng)摘要的質(zhì)量。真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，基于詞句協(xié)同排序的自動(dòng)摘要算法較經(jīng)典的TextRank算法在Rouge指標(biāo)上提升13%～30%，能夠有效提高摘要的生成質(zhì)量。

自動(dòng)摘要；節(jié)錄式摘要；單文檔；圖排序；詞句協(xié)同

0 引言

隨著Web2.0的迅猛發(fā)展，各種用戶原創(chuàng)內(nèi)容爆炸式增長(zhǎng)，造成了互聯(lián)網(wǎng)上嚴(yán)重的信息過載，使得有價(jià)值信息的獲取愈發(fā)困難。自動(dòng)摘要技術(shù)能夠從海量文本中抽取出最為重要的語句，形成高度概括原文主旨的精煉短文，能夠有效地緩解信息過載。

總體而言，自動(dòng)摘要分為基于抽象的自動(dòng)摘要和基于抽取的自動(dòng)摘要[1]。基于抽象的自動(dòng)摘要受制于自然語言處理的瓶頸，實(shí)現(xiàn)相對(duì)困難。目前主要的研究和應(yīng)用集中在基于抽取的自動(dòng)摘要，又稱節(jié)錄式摘要，計(jì)算文檔中句子的權(quán)重并進(jìn)行排序，從中抽取高權(quán)重語句生成摘要[2]?，F(xiàn)有工作中對(duì)句子權(quán)重的計(jì)算主要分為兩種思路：通過詞的權(quán)重推測(cè)句子的權(quán)重[3-4]或通過句子特征計(jì)算權(quán)重[5-6]。事實(shí)上，文檔中的詞與句是不可分割的整體，充分考慮詞句之間的協(xié)同關(guān)系有助于進(jìn)一步提高自動(dòng)摘要的質(zhì)量。本文面向單文檔自動(dòng)摘要，將文檔建模為以句子為頂點(diǎn)、句子間的關(guān)聯(lián)為邊的句網(wǎng)絡(luò)圖，以圖排序算法為基礎(chǔ)，重新設(shè)計(jì)迭代過程，在計(jì)算句子權(quán)重時(shí)融入詞對(duì)句子權(quán)重評(píng)分的影響，提出一種詞句協(xié)同排序(Word-Sentence-Rank，WSRank)的自動(dòng)摘要算法。實(shí)驗(yàn)表明，詞的融入有助于進(jìn)一步提高句子權(quán)重計(jì)算的準(zhǔn)確性，提升摘要的質(zhì)量。

1 相關(guān)工作

自動(dòng)摘要作為自然語言處理與信息檢索領(lǐng)域重要的研究議題，一直廣受關(guān)注。根據(jù)是否需要對(duì)原文語義進(jìn)行理解，自動(dòng)摘要可分為基于抽象的自動(dòng)摘要和基于抽取的自動(dòng)摘要[1]。基于抽象的自動(dòng)摘要需識(shí)別文本的主要內(nèi)容，然后利用自然語言處理技術(shù)重新組織或添加新內(nèi)容以生成摘要，受制于自然語言生成技術(shù)的局限性，目前相關(guān)的研究與應(yīng)用都有限。實(shí)用的自動(dòng)摘要技術(shù)主要基于語句抽取的方式，即通過計(jì)算文檔中句子的重要程度，從中選擇重要語句生成摘要，又稱節(jié)錄式摘要[2]。根據(jù)所處理的文檔數(shù)量不同，自動(dòng)摘要又分為單文檔摘要和多文檔摘要，單文檔摘要從單篇文檔中提取涵蓋原文主旨的概括性內(nèi)容[6-7];多文檔摘要?jiǎng)t將多篇探討相關(guān)主題的文檔融合在一起，從中提取主題相關(guān)的內(nèi)容[8-9]，并可通過摘要更新關(guān)注其演化信息[10-11]。

本文的研究主要面向單文檔節(jié)錄式自動(dòng)摘要，其核心議題是文檔中句子的權(quán)重評(píng)分。早期的評(píng)分手段主要利用句子及其中單詞的語義特征或統(tǒng)計(jì)性特征，通過構(gòu)建評(píng)價(jià)函數(shù)計(jì)算句子的權(quán)重?；趩卧~的特征主要包括詞頻、TF-IDF(Term Frequency-Inverse Document Frequency)、大小寫、共現(xiàn)信息(N-Gram)等[3-4,12-14];基于句子的特征包括是否包含總結(jié)性詞匯[5]、是否包含數(shù)字[12]、在文章或段落中的位置[15]、句子長(zhǎng)度[16-17]等。這類方法簡(jiǎn)單直觀，不依賴于外部語料庫和訓(xùn)練集，但由于需要人工擬合評(píng)價(jià)函數(shù)，主觀性較強(qiáng)，計(jì)算參數(shù)只能根據(jù)經(jīng)驗(yàn)設(shè)定，因此最終的摘要效果一般。

另一種句子評(píng)分方法基于機(jī)器學(xué)習(xí)，試圖通過訓(xùn)練樣本的學(xué)習(xí)構(gòu)建分類器，從而直接判定一個(gè)句子是否應(yīng)被選為摘要句[18]。如Kupiec等[19]選用詞頻、大小寫、句子位置、長(zhǎng)度、是否包含總結(jié)性詞匯等5種特征，構(gòu)建樸素貝葉斯分類器提取科技文獻(xiàn)的摘要;Conroy等[20]提出基于隱馬爾可夫模型的自動(dòng)摘要方法，相比樸素貝葉斯分類具有更少的獨(dú)立性假設(shè)要求。這類方法在針對(duì)特定體裁文本，特別是科技文獻(xiàn)時(shí)的效果很好，但在一些其他類型的文本，如新聞?wù)矫鎰t無明顯的優(yōu)勢(shì)[21]，其原因在于摘要的質(zhì)量受制于訓(xùn)練樣本和領(lǐng)域知識(shí)，因此通用性較差。

句子評(píng)分的第三類方法基于圖排序思想，這類方法將句子建模為圖的頂點(diǎn)，利用句子相似性或共現(xiàn)關(guān)系建立節(jié)點(diǎn)之間的邊，在此基礎(chǔ)上應(yīng)用PageRank[22]、HITS(Hyperlink-Induced Topic Search)[23]等圖排序算法迭代計(jì)算頂點(diǎn)權(quán)重，收斂后的權(quán)重即為相應(yīng)句子的評(píng)分。最為典型的圖排序自動(dòng)摘要算法是TextRank[6]，其由PageRank演化而來，在其后續(xù)加強(qiáng)版本中進(jìn)一步融入了語法和語義特征對(duì)句子得分進(jìn)行線性加權(quán)[7]，本文將以這兩種方法作為比較對(duì)象，驗(yàn)證WSRank算法的效果。其他以圖排序?yàn)榛A(chǔ)自動(dòng)摘要算法還包括基于親和圖的方法[24]、基于N-Gram圖的方法[25]、基于概念圖的方法[26]等。

基于圖排序的自動(dòng)摘要方法無需訓(xùn)練樣本，不受語言和應(yīng)用領(lǐng)域的限制，并且計(jì)算速度快，可擴(kuò)展性強(qiáng)，得到了越來越多的應(yīng)用。已有方法大多以句子為粒度進(jìn)行計(jì)算，即主要考慮句子層面的關(guān)系，但在基于單詞特征生成自動(dòng)摘要的研究工作中[3-4,12-14]，揭示出了詞對(duì)句子評(píng)分的重要影響，這種影響不應(yīng)忽略。雖然部分研究工作嘗試以單詞為頂點(diǎn)運(yùn)行圖排序算法[27-28]，但單詞權(quán)重與句子權(quán)重之間的相互增強(qiáng)關(guān)系并未得到清晰的表述，本文將針對(duì)這一問題展開研究，通過建立詞句間的協(xié)同增強(qiáng)模型，將詞的權(quán)重融入句子權(quán)重的計(jì)算過程中，從而生成更加準(zhǔn)確的自動(dòng)摘要。

2 詞句協(xié)同的自動(dòng)摘要算法

本文將詞與句的關(guān)系融入到句子權(quán)重評(píng)分中，提出一種詞句協(xié)同排序的節(jié)錄式單文檔自動(dòng)摘要算法。其背后隱含的基本思想是：當(dāng)一個(gè)句子包含越多的重要單詞(如關(guān)鍵詞)時(shí)，該句子的重要程度越高;相應(yīng)地，若一個(gè)單詞在重要語句中出現(xiàn)的頻率越高，則該單詞的重要性也越高。

在進(jìn)行算法描述之前，本文首先給出若干變量的符號(hào)定義，并對(duì)節(jié)錄式自動(dòng)摘要問題進(jìn)行形式化描述。假設(shè)文檔T中的句子集合為S并且|S|=m，詞的集合為W并且|W|=n，節(jié)錄式自動(dòng)摘要的目標(biāo)是計(jì)算得到一個(gè)m維向量X=[X1，X2，…，Xm]T，其中Xi表示第i個(gè)句子的權(quán)重得分，從中提取得分最高的Top-K個(gè)句子，將其按原文中的順序組合生成摘要。在自動(dòng)摘要研究領(lǐng)域，K的值可根據(jù)多種約束條件定義，如摘要中包含的句子數(shù)量、摘要的最大單詞數(shù)/字?jǐn)?shù)、摘要詞數(shù)/字?jǐn)?shù)在原文中所占的比例等。利用詞袋模型(bag-of-words)，文檔T可被描述為一個(gè)m×n的矩陣P=[pij](1≤i≤m，1≤j≤n)，其中pij表示第j個(gè)單詞在第i個(gè)句子中的詞頻。為計(jì)算句子權(quán)重，首先構(gòu)建一個(gè)無向加權(quán)圖G，稱為句網(wǎng)絡(luò)圖，以便運(yùn)行類似PageRank的圖排序算法。雖然PageRank算法主要應(yīng)用于有向圖中，但已有相關(guān)研究表明，對(duì)于非正則無向圖，PageRank同樣能夠得到有效的排序結(jié)果[29]，因此在文本摘要中，需要構(gòu)建非正則的句網(wǎng)絡(luò)圖，本文以文檔中的句子為頂點(diǎn)，句子間的相似關(guān)系為邊，建立句網(wǎng)絡(luò)圖，由于文檔中一般包含很多彼此間相似度為0的句子，這些句子間不存在邊，由此導(dǎo)致頂點(diǎn)的度數(shù)不可能相等，因此所構(gòu)建的句網(wǎng)絡(luò)圖為非正則圖。假設(shè)其鄰接矩陣為A=[aij](1≤i，j≤m)，其中aij為邊(i，j)的權(quán)重，由第i個(gè)句子與第j個(gè)句子間的相似度定義。本文采用雅可比相似度計(jì)算邊的權(quán)重，即：

(1)

其中：Si表示第i個(gè)句子，Wi表示句子Si中詞的集合。

2.1 計(jì)算過程

WSRank算法采用迭代的方式計(jì)算句子權(quán)重，由于詞的引入，需對(duì)基本的圖排序算法進(jìn)行擴(kuò)充，使其能夠在詞與句之間進(jìn)行重要度的傳播。首先，在句網(wǎng)絡(luò)圖G上運(yùn)行類似PageRank的圖排序算法，計(jì)算句子的初始權(quán)重：

(2)

其中，d∈[0，1]表示阻尼系數(shù)，用以處理圖中度為0的懸掛頂點(diǎn)[22]。在初始化時(shí)Xi可取任意非負(fù)值，后續(xù)迭代中則由上一輪迭代給出。

得到句子權(quán)重后，可根據(jù)句子計(jì)算單詞權(quán)重，進(jìn)行句-詞增強(qiáng)，假設(shè)Yj(1≤j≤n)表示W(wǎng)中第j個(gè)單詞的重要度，其計(jì)算方法如式(3)所示：

(3)

在獲得所有單詞的權(quán)重后，可根據(jù)單詞重新計(jì)算句子權(quán)重，進(jìn)行詞-句增強(qiáng)，計(jì)算方法如式(4)所示：

(4)

最后，將式(2)～(4)獲得的句子權(quán)重進(jìn)行線性組合，獲得該輪迭代的句子權(quán)重，并作為下一輪迭代的初值，計(jì)算方法如式(5)所示：

(5)

其中α為調(diào)節(jié)因子。當(dāng)某一輪迭代之后，所有句子權(quán)重與該輪迭代前的差值均小于預(yù)設(shè)閾值ε時(shí)，則達(dá)到收斂狀態(tài)，停止迭代。此時(shí)，可以得到m維句子評(píng)分向量X=[X1，X2，…，Xm]T，其中Xi表示第i個(gè)句子的權(quán)重得分，從中提取得分最高的Top-K個(gè)句子，將其按原文中的順序組合便可自動(dòng)生成摘要。

類似于任意隨機(jī)行走模型，以上計(jì)算過程也可轉(zhuǎn)換為矩陣運(yùn)算形式。假設(shè)Xt表示第t輪迭代得到的句評(píng)分向量，根據(jù)PageRank算法，式(2)可重新表示為：

X=AXt-1

(6)

Yt-1=QTXt-1

(7)

由此，詞-句增強(qiáng)過程即式(4)可轉(zhuǎn)換為：

Xt-1′=QYt-1

(8)

結(jié)合式(6)～(8)，線性組合過程即式(5)可重新表示為：

Xt=αAXt-1+(1-α)Xt-1=αAXt-1+(1-α)QQTXt-1= [αA+(1-α)QQT]Xt-1

(9)

矩陣表達(dá)方式給出了WSRank算法更加簡(jiǎn)潔的迭代過程，即首先使用隨機(jī)值初始化向量X0，然后根據(jù)式(9)迭代更新Xt直至收斂。

2.2 自動(dòng)摘要算法

在實(shí)際的文檔中，圍繞同一主題一般存在多個(gè)語句，并且這些句子往往會(huì)包含若干相同的關(guān)鍵詞，導(dǎo)致這些語句在評(píng)分上通常較為接近。如果某個(gè)句子得到較高的權(quán)重評(píng)分，與其相似的語句同樣會(huì)得到高分，如果自動(dòng)摘要算法簡(jiǎn)單地從排序后的句子中提取的Top-K個(gè)語句，則會(huì)出現(xiàn)若干語句重復(fù)表達(dá)同一主旨的情況，并且丟失一些評(píng)分次高但包含其他重要信息的句子，因此，本文在基本的WSRank算法上增加了一個(gè)冗余去除的過程，在提取摘要句時(shí)加入相似性判斷，從而剔除同義語句，保證摘要能夠更準(zhǔn)確全面地表達(dá)原文的主旨。假設(shè)AS表示當(dāng)前已提取到的摘要句集合，Si為剩余句子中權(quán)重評(píng)分最高的句子，去冗余過程考察Si與AS中最相似的語句的相似度，即：

(10)

通過設(shè)置閾值θ，僅當(dāng)Sim(Si，AS)≤θ時(shí)，將Si選為摘要句，否則繼續(xù)考察評(píng)分低于Si的語句。本文將加入冗余去除的自動(dòng)摘要算法命名為WSRank*，其偽代碼算法1所示。

算法1 WSRank*算法。

輸入:A表示句網(wǎng)絡(luò)圖鄰接矩陣;Q表示詞句關(guān)系矩陣;d、α、ε、θ、K為算法參數(shù)。 輸出:AS表示摘要句集合，初始化為?。

1)

Randomly initialize vectorXt，t←0;

2)

while ‖Xt-Xt-1‖2≥εdo

3)

t←t+1;

4)

UpdateXtaccording to 式(9);

5)

end while

6)

while|AS|≤Kdo

7)

SelectthesentenceSiwiththehighestscoreinSaccordingtoXt;

8)

ifSim(Si，AS)≤θthen

9)

AS←AS∪Si;

10)

endif

11)

S←S-Si;

12)

end while

值得注意的是，如果將算法第8)行中的判斷條件去除，WSRank*將蛻變?yōu)閃SRank。算法共包含5個(gè)參數(shù)，其中K為摘要句數(shù)量，由摘要長(zhǎng)度約束;阻尼系數(shù)d按照PageRank算法的建議，一般取值0.85;相似性閾值θ取0.8;其余參數(shù)將在實(shí)驗(yàn)部分討論。

算法的主要計(jì)算量集中在第4)行的X向量更新過程，根據(jù)式(9)，QQT在每次迭代中僅執(zhí)行1次，其中包含乘法操作mn次，因此，如果不進(jìn)行冗余去除，WSRank算法的計(jì)算復(fù)雜度為O(Imn)，I為迭代次數(shù)，由3.4節(jié)的實(shí)驗(yàn)可知，I的取值一般不會(huì)超過15。對(duì)于WSRank*算法而言，由于約束條件K的存在，冗余判斷的計(jì)算量最多為K2次，因此其計(jì)算復(fù)雜度為O(Imn+K2)。

2.3 收斂性證明

WSRank*與WSRank的差異主要在摘要句選取階段，這部分不存在收斂性問題，算法的收斂性主要取決于算法1第4)行的權(quán)重評(píng)分計(jì)算過程。根據(jù)隨機(jī)行走模型，要證明WSRank算法的收斂性，只需證明向量X和Y存在唯一的平穩(wěn)概率分布。令Ωm={X∈Rm|?Xi≥0,1≤i≤m}，Ωn={Y∈Rn|?Yi≥0,1≤i≤n}，并且Ω={[X,Y]∈Rm+n|X∈Ωm,Y∈Ωn}，可以看出，Ωn,Ωn及Ω均為等比凸集。由計(jì)算過程可知，Xt-1受Yt-1影響，不失一般性，本文分別將式(9)和(7)簡(jiǎn)寫為Xt=f1(Xt-1,Yt-1)，Yt=f2(Xt-1,Yt-1)。

在圖排序算法中，鄰接矩陣的不可約是一個(gè)基本假設(shè)，如PageRank[22]、MultiRank[30]、MutuRank[31]等，本文同樣假設(shè)句網(wǎng)絡(luò)圖G的鄰接矩陣A不可約，即圖中任意兩個(gè)頂點(diǎn)間至少存在一條路徑。本文給出如下兩個(gè)定理并證明。

定理1 如果A是不可約的，那么B=αA+(1-α)QQT同樣是不可約的。

證明 由于Q≥0且1-α≥0，因此，A不可約意味著句網(wǎng)絡(luò)圖中任意兩點(diǎn)間存在至少一條路徑。根據(jù)B的定義，邊權(quán)重增加一個(gè)非負(fù)的值不改變頂點(diǎn)間的連通性，因此B也是不可約的。

證畢。

定理2 如果A是不可約的，那么f1(X，Y)和f2(X，Y)分別存在一個(gè)平穩(wěn)概率X′∈Ωm和Y′∈Ωn，并且X′=f1(X′,Y′)，Y′=f2(X′,Y′)，且X′>0，Y′>0。

證明 此問題可轉(zhuǎn)換為不動(dòng)點(diǎn)問題(fixed point problem)。假設(shè)存在映射F:Ω→Ω：

F(X,Y)=[f1(X，Y),f2(X，Y)]

顯然，F(xiàn)(·)是良好定義的，即當(dāng)[X，Y]∈Ω時(shí)，F(xiàn)([X，Y])∈Ω并且是連續(xù)的。根據(jù)Brouwer不動(dòng)點(diǎn)定理[32]，必然存在[X′,Y′]∈Ω使得F[X′,Y′]=[X′,Y′]，即f1[X′,Y′]=X′，f2[X′,Y′]=Y′。

證畢。

定理2表明當(dāng)A不可約時(shí)，所有F(·)的不動(dòng)點(diǎn)均為正。根據(jù)文獻(xiàn)[33]，不動(dòng)點(diǎn)是唯一的，即當(dāng)所有界內(nèi)的點(diǎn)均非不動(dòng)點(diǎn)時(shí)，WSRank的平穩(wěn)概率是唯一的，因此，根據(jù)定理2，WSRank算法存在唯一的平穩(wěn)概率，算法是收斂的。

3 實(shí)驗(yàn)

本文利用公開數(shù)據(jù)集DUC02(http://www-nlpir.nist.gov/projects/duc/guidelines/2002.html)驗(yàn)證自動(dòng)摘要算法的性能，這是一種在單文檔自動(dòng)摘要中得到廣泛應(yīng)用的基準(zhǔn)數(shù)據(jù)集，包括TextRank[6]在內(nèi)的多種經(jīng)典算法均使用該數(shù)據(jù)集驗(yàn)證算法性能。針對(duì)單文檔自動(dòng)摘要，DUC02中共有533篇有效文檔(從DUC02的567篇文檔中去除34篇重復(fù)文檔)，每篇文檔包含單詞數(shù)為10，50，100，200等多個(gè)不同長(zhǎng)度的參考摘要，本文選擇生成100單詞數(shù)的自動(dòng)摘要，并與相同詞數(shù)的參考摘要進(jìn)行對(duì)比。驗(yàn)證的內(nèi)容包括：生成摘要的總體質(zhì)量、去冗余及關(guān)鍵詞對(duì)摘要質(zhì)量的提升、算法收斂速度、最佳參數(shù)選取等。

3.1 摘要質(zhì)量總體評(píng)價(jià)

本文通過WSRank與多種其他自動(dòng)摘要算法的對(duì)比，驗(yàn)證自動(dòng)摘要的質(zhì)量。DUC02中包含若干自動(dòng)摘要系統(tǒng)在數(shù)據(jù)集上的運(yùn)行數(shù)據(jù)，雖然無法獲得各系統(tǒng)的詳細(xì)名稱和算法細(xì)節(jié)，但數(shù)據(jù)集通過匿名編號(hào)的方式提供了了運(yùn)行結(jié)果，本文選擇其中綜合性能最佳的S28系統(tǒng)加入對(duì)比。此外，同樣采用句網(wǎng)絡(luò)排序的TextRank算法[6]及TextRankExt算法[7]也是本文的比較對(duì)象，其中TextRankExt是TextRank的擴(kuò)展版，在句子TextRank得分的基礎(chǔ)上融入了位置得分和動(dòng)名詞WordNet得分等語義因素，通過線性加權(quán)的方式計(jì)算句子的最終評(píng)分。

摘要質(zhì)量的評(píng)價(jià)方法采用自動(dòng)摘要領(lǐng)域廣泛使用的Rouge指標(biāo)[34]，Rouge是一種基于召回率(Recall)的自動(dòng)化評(píng)價(jià)方法，根據(jù)比較力度的不同，本文選擇Rouge-N、Rouge-W、Rouge-SU4四種具體的評(píng)價(jià)指標(biāo)，詳細(xì)定義可參考文獻(xiàn)[34]，其中Rouge-N中的N-gram采用1-gram和2-gram。由于數(shù)據(jù)集中包含多篇文檔，本文以所有文檔Rouge指標(biāo)的平均值作為比較對(duì)象。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 DUC02數(shù)據(jù)集中的自動(dòng)摘要質(zhì)量對(duì)比

從圖1中可以發(fā)現(xiàn)，TextRank除在Rouge-1中的效果好于S28外，其余4個(gè)指標(biāo)的得分均為最低，但通過加入語義因素，TextRankExt在Rouge-SU4指標(biāo)中縮小了與S28的差距，并且在Rouge-1、Rouge-2以及Rouge-L三個(gè)指標(biāo)上取得了優(yōu)于S28的得分，這說明在圖排序過程中僅在句子層面進(jìn)行迭代具有一定的局限性，適當(dāng)加入其他因素有助于提升摘要的生成質(zhì)量。而WSRank在全部5個(gè)指標(biāo)中均取得了最高得分，說明較之語義，在句子評(píng)分中融入詞的權(quán)重能夠取得更好的效果，從而生成更加準(zhǔn)確的摘要。

除宏觀的總體質(zhì)量比較外，本文還對(duì)數(shù)據(jù)集中的每篇文檔運(yùn)行WSRank、TextRank、TextRankExt三種算法生成的自動(dòng)摘要進(jìn)行了細(xì)粒度的比較，表1列出了每種算法在相應(yīng)指標(biāo)下得分最高的文檔數(shù)?？梢园l(fā)現(xiàn)，由于TextRankExt和WSRank分別在語義和單詞權(quán)重方面對(duì)TextRank進(jìn)行了提升，因此它們幾乎在每篇文檔中所取得的摘要效果均好于TextRank，僅有極少數(shù)文檔的TextRank摘要能夠取得最優(yōu)。而對(duì)于TextRankExt和WSRank兩種算法，WSRank在Rouge-N與Rouge-L指標(biāo)下的優(yōu)勢(shì)較為明顯，在Rouge-W與Rouge-SU4指標(biāo)下略少于TextRanKExt算法，但由于數(shù)量相差不大，且WSRank在優(yōu)勢(shì)文檔中得分更高，因此反映在平均分的總體評(píng)價(jià)上，WSRank仍領(lǐng)先于TextRankExt。

表1 DUC02數(shù)據(jù)集上自動(dòng)摘要算法最優(yōu)文檔數(shù)量對(duì)比

3.2 冗余去除對(duì)摘要質(zhì)量的提升

相似的語句在評(píng)分上較為接近，若這些語句都得到了較高的評(píng)分，自動(dòng)摘要算法從排序后的句子中提取的Top-K個(gè)語句組成的摘要就變成了相似語句的重復(fù)，反而會(huì)丟失一些評(píng)分次高但卻有著重要意義的句子。本文在生成自動(dòng)摘要的過程中加入了冗余去除過程，在提取摘要句時(shí)進(jìn)行相似性判斷，從而剔除文檔中的同義語句，保證了摘要的準(zhǔn)確性。表2展示了冗余去除對(duì)于摘要質(zhì)量的影響，其中，相似度閾值θ=0.8，選擇相對(duì)較大的θ的目的是希望放寬相似度的判定，從而更加尊重排序算法所得出的句子權(quán)重，同時(shí)也更能說明去冗余對(duì)摘要質(zhì)量的提升。實(shí)驗(yàn)結(jié)果表明，即使選擇相對(duì)寬松的相似性定義，WSRank*仍能在所有指標(biāo)上超越WSRank，說明去冗余對(duì)于提升摘要質(zhì)量具有重要的意義，而在算法的實(shí)際使用中，則要根據(jù)文檔的特點(diǎn)和摘要要求，靈活選擇θ的取值。

表2 冗余去除對(duì)摘要質(zhì)量的影響

3.3 關(guān)鍵詞對(duì)摘要質(zhì)量提升

WSRank與傳統(tǒng)句排序算法如TextRank最大的不同之處在于考慮了關(guān)鍵詞對(duì)句子評(píng)分的影響。關(guān)鍵詞可定義為句-詞增強(qiáng)中得分較高的單詞，其在詞-句增強(qiáng)過程中反作用于句子得分。本文通過比較WSRank和TextRank提取的摘要句數(shù)量驗(yàn)證關(guān)鍵詞對(duì)摘要質(zhì)量的提升，實(shí)驗(yàn)結(jié)果如圖2所示。在進(jìn)行統(tǒng)計(jì)前，首先根據(jù)參考摘要去除無效摘要句，即不在參考摘要中的句子，最終WSRank和TextRank算法共得出1 788個(gè)摘要句，Kappa統(tǒng)計(jì)值為50.53%，說明兩種算法在摘要句判定上基本是一致的，兩種算法同時(shí)計(jì)算出的摘要句1 281個(gè)，但WSRank計(jì)算出406個(gè)TextRank未計(jì)算出的摘要句，同時(shí)，TextRank計(jì)算出101條WSRank未計(jì)算出的摘要句。這說明融入關(guān)鍵詞參與排序后，可以多找出406個(gè)摘要句而丟失101個(gè)摘要句，性能提升較為明顯。

3.4 參數(shù)對(duì)摘要性能的影響

除阻尼系數(shù)d根據(jù)PageRank[22]的建議一般取0.85外，算法還包含兩個(gè)重要參數(shù)ε和α，其中ε決定了算法的收斂速度，α主要調(diào)節(jié)詞句協(xié)同排序時(shí)的相互的權(quán)重占比。對(duì)于ε，本文考察了其在區(qū)間[10-5，10-1]變化時(shí)算法的迭代次數(shù)，如圖3所示?？梢园l(fā)現(xiàn)，WSRank算法的收斂速度令人滿意，即使當(dāng)ε=10-5時(shí)，算法仍能在13次迭代之內(nèi)收斂。

圖2 WSRank與TextRank摘要句命中對(duì)比

圖3 參數(shù)ε對(duì)算法收斂速度的影響

參數(shù)α的主要作用是平衡詞與句在排序過程中的權(quán)重比例，α越大，句所占據(jù)的權(quán)重就越大，極端情況下，當(dāng)α=1時(shí)，WSRank算法將蛻變?yōu)門extRank算法。圖4顯示了α從0.4變化到0.9時(shí)WSRank算法摘要質(zhì)量的變化，可以發(fā)現(xiàn)，在Rouge-2、Rouge-L、Rouge-W以及Rouge-SU4四種指標(biāo)中，摘要質(zhì)量均隨著α的增大而變高，直到α=0.75時(shí)，摘要質(zhì)量達(dá)到最佳，此后α的增大將導(dǎo)致質(zhì)量的降低。這說明排序中句子的權(quán)重仍應(yīng)占據(jù)較大比例，但適當(dāng)融入詞的權(quán)重對(duì)句排序具有積極的影響，對(duì)于兩者的比例，通過比較四種Rouge指標(biāo)得分變化趨勢(shì)，建議調(diào)節(jié)因子取值0.7～0.75，大于0.75將會(huì)使摘要質(zhì)量急劇下降。

4 結(jié)語

本文提出一種詞句協(xié)同排序的單文檔自動(dòng)摘要算法，在基于圖模型的句排序算法中融入詞句關(guān)系的影響，從而有效提升了自動(dòng)摘要的質(zhì)量。通過轉(zhuǎn)化為矩陣運(yùn)算形式簡(jiǎn)化了算法的表述，并基于此證明了算法收斂性。在摘要句選擇階段，利用冗余去除進(jìn)一步提升了所生成的自動(dòng)摘要的質(zhì)量。通過真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了算法的效果和性能。下一步將試圖擴(kuò)展詞句協(xié)同排序至多文檔自動(dòng)摘要中，并引入語義處理機(jī)制，進(jìn)一步提升摘要的生成質(zhì)量的同時(shí)增強(qiáng)摘要的可讀性。

圖4 參數(shù)α對(duì)摘要質(zhì)量的影響

References)

[1] LLORET E, PALOMAR M. Text summarisation in progress: a literature review [J]. Artificial Intelligence Review, 2012, 37(1): 1-41.

[2] FERREIRA R, CABRAL L D S, LINS R D, et al. Assessing sentence scoring techniques for extractive text summarization [J]. Expert Systems with Applications, 2013, 40(14): 5755-5764.

[3] LUHN HP. The automatic creation of literature abstracts [J]. IBM Journal of Research & Development, 1958, 2(2): 159-165.

[4] NOBATAY C, SEKINEZ S, MURATAY M, et al. Sentence extraction system assembling multiple evidence [J]. Journal of Neurophysiology, 2001, 85(4): 1761-1771.

[5] GUPTA P, PENDLURI V S, VATS I. Summarizing text by ranking text units according to shallow linguistic features [C]// ICACT 2011: Proceedings of the 13th International Conference on Advanced Communication Technology. Piscataway, NJ: IEEE, 2011: 1620-1625.

[6] MIHALCEA R, TARAU P. TextRank: bringing order into texts [EB/OL]. [2016- 12- 20]. http://web.eecs.umich.edu/～mihalcea/papers/mihalcea.emnlp04.pdf.

[7] BARRERA A, VERMA R. Combining syntax and semantics for automatic extractive single-document summarization [C]// ICCLITP 2012: Proceedings of the 13th International Conference on Computational Linguistics and Intelligent Text Processing. Berlin: Springer, 2012: 366-377.

[8] 秦兵，劉挺，李生.基于局部主題判定與抽取的多文檔文摘技術(shù)[J].自動(dòng)化學(xué)報(bào)，2004，30(6):905-910.(QIN B, LIU T, LI S. Multi-document summarization based on local topics identification and extraction [J]. Acta Automatica Sinica, 2004, 30(6): 905-910.)

[9] NENKOVA A, VANDERWENDE L, MCKEOWN K. A composi-tional context sensitive multi-document summarizer: exploring the factors that influence summarization [C]// SIGIR 2006: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2006: 573-580.

[10] 劉美玲，鄭德權(quán)，趙鐵軍,等.動(dòng)態(tài)多文檔摘要模型[J].軟件學(xué)報(bào)，2012，23(2):289-298.(LIU M L, ZHENG D Q, ZHAO T J, et al. Dynamic multi-document summarization model [J]. Journal of Software, 2012, 23(2): 289-298.)

[11] HE R F, QIN B, LIU T. A novel approach to update summarization using evolutionary manifold-ranking and spectral clustering [J]. Expert Systems with Applications, 2012, 39(3): 2375-2384.

[12] FERREIRA R, LINS R D, CABRAL L, et al. Automatic docu-ment classification using summarization strategies [C]// SDE 2015: Proceedings of the 2015 ACM Symposium on Document Engineering. New York: ACM, 2015: 69-72.

[13] GUPTA P, PENDLURI V S, VATS I. Summarizing text by ranking text units according to shallow linguistic features [C]// ICACT 2011: Proceedings of the 13th IEEE International Conference on Advanced Communication Technology. Piscataway, NJ: IEEE, 2011: 1620-1625.

[14] MEENA Y K, GOPALANI D. Analysis of sentence scoring methods for extractive automatic text summarization [C]// Proceedings of the 2014 International Conference on Information and Communication Technology for Competitive Strategies. New York: ACM, 2014: Article No. 53.

[15] ABUOBIEDA A, SALIM N, ALBAHAM A T, et al. Text summarization features selection method using pseudo genetic-based model [C]// IRKM 2012: Proceedings of the 2012 International Conference on Information Retrieval & Knowledge Management. Piscataway, NJ: IEEE, 2012: 193-197.

[16] LLORET E, PALOMAR M. COMPENDIUM: a text summarization tool for generating summaries of multiple purposes, domains, and genres [J]. Natural Language Engineering, 2013, 19(2): 147-186.

[17] ANTIQUEIRA L, OLIVEIRA O N, COSTA L D F. A complex network approach to text summarization [J]. Information Sciences, 2009, 179(5): 584-599.

[18] SHEN D, SUN J T, LI H, et al. Document summarization using conditional random fields [C]// IJCAI 2007: Proceedings of the 20th International Joint Conference on Artificial Intelligence. Menlo Park: AAAI, 2007: 2862-2867.

[19] KUPIEC J, PEDERSEN J, CHEN F. A trainable document summarizer [C]// SIGIR 1995: Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 1995: 68-73.

[20] CONROY J M, O’LEARY D P. Text summarization via hidden Markov models [C]// SIGIR 2001: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2001: 406-407.

[21] ZHANG J J, CHAN H Y, FUNG P. Improving lecture speech summarization using rhetorical information [C]// ASRU 2007: Proceedings of the IEEE Workshop on Automatic Speech Recognition & Understanding. Piscataway, NJ: IEEE, 2007: 195-200.

[22] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the Web [EB/OL]. [2016- 12- 10].http://ilpubs.stanford.edu:8090/422/1/1999- 66.pdf.

[23] KLEINBERG J M. Authoritative sources in a hyperlinked environment [J]. Journal of the ACM, 1999, 46(5): 604-632.

[24] WAN X, XIAO J. Towards a unified approach based on affinity graph to various multi-document summarizations [C]// ECRATDL 2007: Proceedings of the 2007 European Conference on Research & Advance Technology for Digital Libraries. Berlin: Springer, 2007: 297-308.

[25] GIANNAKOPOULOS G, KARKALETSIS V, VOUROS G. Testing the use of N-gram graphs in summarization sub-tasks [J]. Natural Language Processing, 2008: 324-334.

[26] MORALES L P, ESTEBAN A D, GERVAS P. Concept-graph based biomedical automatic summarization using ontologies [C]// NLP 2008: Proceedings of the 3rd Textgraphs Workshop on Graph-Based Algorithms for Natural Language Processing, Association for Computational Linguistics. New York: ACM, 2008: 53-56.

[27] BARALIS E. GraphSum: Discovering correlations among multiple terms for graph-based summarization [J]. Information Sciences, 2013, 249: 96-109.

[28] GOYAL P, BEHERA L, MCGINNITY T M. A context-based word indexing model for document summarization [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(8): 1693-1705.

[29] GROLMUSZ V. A note on the PageRank of undirected graphs [J]. Information Processing Letters, 2012, 115(6/7/8): 633-634.

[30] NG M, LI X, YE Y. MultiRank: co-ranking for objects and relations in multi-relational data [C]// KDD 2011: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1217-1225.

[31] WU Z, CAO J, ZHU G, et al. Detecting overlapping communities in poly-relational networks [J]. World Wide Web Journal, 2015, 18(5): 1373-1390.

[32] BAZARAA M S, JARVIS J J, SHERALI H D. Linear Programming and Network Flows [M]. Hoboken, NJ: John Wiley & Sons, 2011:45.

[33] KELLOGG R. Uniqueness in the Schauder fixed point theorem [J]. Proceedings of the American Mathematical Society, 1976, 60(1): 207-207.

[34] LIN C Y. Rouge: a package for automatic evaluation of summaries [EB/OL]. [2016- 12- 18].http://anthology.aclweb.org/W/W04/W04- 1013.pdf.

This work is partially supported by the National Natural Science Foundation of China (71571093, 71372188), the National Center for International Joint Research on E-Business Information Processing (2013B01035), the Surface Projects of Natural Science Research in Jiangsu Provincial Colleges and Universities (15KJB520012), the Pre-Research Project of Nanjing University of Finance and Economics (YYJ201415).

ZHANGLu, born in 1983, Ph. D., lecturer. His research interests include natural language processing, data mining.

CAOJie, born in 1969, Ph. D., professor. His research interests include data mining, business intelligence.

PUChaoyi, born in 1993, M. S. candidate. Her research interests include natural language processing.

WUZhi’ang, born in 1982, Ph. D., associate professor. His research interests include data mining, social computing.

Singledocumentautomaticsummarizationalgorithmbasedonword-sentenceco-ranking

ZHANG Lu*, CAO Jie, PU Chaoyi, WU Zhi’ang

(JiangsuProvincialKeyLaboratoryofE-Business,NanjingUniversityofFinanceandEconomics,NanjingJiangsu210023,China)

Focusing on the issue that extractive summarization needs to automatically produce a short summary of a document by concatenating several sentences taken exactly from the original material. A single document automatic summarization algorithm based on word-sentence co-ranking was proposed, named WSRank for short, which integrated the word-sentence relationship into the graph-based sentences ranking model. The framework of co-ranking in WSRank was given, and then was converted to a quite concise form in the view of matrix operations, and its convergence was theoretically proved. Moreover, a redundancy elimination technique was presented as a supplement to WSRank, so that the quality of automatic summarization could be further enhanced. The experimental results on real datasets show that WSRank improves the performance of summarization by 13% to 30% in multiple Rouge metrics, which demonstrates the effectiveness of the proposed method.

automatic summarization; extractive summary; single document; graph-based ranking; word-sentence collaboration

TP399; TP391.1

:A

2017- 02- 20;

:2017- 02- 27。

國(guó)家自然科學(xué)基金資助項(xiàng)目(71571093, 71372188);國(guó)家電子商務(wù)信息處理國(guó)際聯(lián)合研究中心項(xiàng)目(2013B01035);江蘇省高校自然科學(xué)基金資助項(xiàng)目(15KJB520012);南京財(cái)經(jīng)大學(xué)校預(yù)研究資助項(xiàng)目(YYJ201415)。

張璐(1983—)，男，江蘇濱海人，講師，博士，CCF會(huì)員，主要研究方向：自然語言處理、數(shù)據(jù)挖掘； 曹杰(1969—)，男，江蘇姜堰人，教授，博士，CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘、商務(wù)智能； 蒲朝儀(1993—)，女，貴州遵義人，碩士研究生，主要研究方向：自然語言處理；伍之昂(1982—)，男，江蘇宜興人，副教授，博士，CCF會(huì)員，主要研究方向：數(shù)據(jù)挖掘、社會(huì)計(jì)算。

1001- 9081(2017)07- 2100- 06

10.11772/j.issn.1001- 9081.2017.07.2100