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

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

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

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

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

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

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

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

0 引言

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

(1)

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

2.1 計算過程

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

X=AXt-1

(6)

Yt-1=QTXt-1

(7)

由此，詞-句增強過程即式(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)

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

2.2 自動摘要算法

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

(10)

通過設(shè)置閾值θ，僅當(dāng)Sim(Si，AS)≤θ時，將Si選為摘要句，否則繼續(xù)考察評分低于Si的語句。本文將加入冗余去除的自動摘要算法命名為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個參數(shù)，其中K為摘要句數(shù)量，由摘要長度約束;阻尼系數(shù)d按照PageRank算法的建議，一般取值0.85;相似性閾值θ取0.8;其余參數(shù)將在實驗部分討論。

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

2.3 收斂性證明

WSRank*與WSRank的差異主要在摘要句選取階段，這部分不存在收斂性問題，算法的收斂性主要取決于算法1第4)行的權(quán)重評分計算過程。根據(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及Ω均為等比凸集。由計算過程可知，Xt-1受Yt-1影響，不失一般性，本文分別將式(9)和(7)簡寫為Xt=f1(Xt-1,Yt-1)，Yt=f2(Xt-1,Yt-1)。

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

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

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

證畢。

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

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

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

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

證畢。

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

3 實驗

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

3.1 摘要質(zhì)量總體評價

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 WSRank與TextRank摘要句命中對比

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

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

4 結(jié)語

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

圖4 參數(shù)α對摘要質(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].自動化學(xué)報，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)，趙鐵軍,等.動態(tài)多文檔摘要模型[J].軟件學(xué)報，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。

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

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

1001- 9081(2017)07- 2100- 06

10.11772/j.issn.1001- 9081.2017.07.2100