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

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

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

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

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

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

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

自動摘要；節錄式摘要；單文檔；圖排序；詞句協同

0 引言

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

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

1 相關工作

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

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

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

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

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

2 詞句協同的自動摘要算法

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

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

(1)

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

2.1 計算過程

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

X=AXt-1

(6)

Yt-1=QTXt-1

(7)

由此，詞-句增強過程即式(4)可轉換為：

Xt-1′=QYt-1

(8)

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

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

(9)

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

2.2 自動摘要算法

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

(10)

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

算法1 WSRank*算法。

輸入:A表示句網絡圖鄰接矩陣;Q表示詞句關系矩陣;d、α、ε、θ、K為算法參數。 輸出: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*將蛻變為WSRank。算法共包含5個參數，其中K為摘要句數量，由摘要長度約束;阻尼系數d按照PageRank算法的建議，一般取值0.85;相似性閾值θ取0.8;其余參數將在實驗部分討論。

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

2.3 收斂性證明

WSRank*與WSRank的差異主要在摘要句選取階段，這部分不存在收斂性問題，算法的收斂性主要取決于算法1第4)行的權重評分計算過程。根據隨機行走模型，要證明WSRank算法的收斂性，只需證明向量X和Y存在唯一的平穩概率分布。令Ω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)。

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

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

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

證畢。

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

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

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

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

證畢。

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

3 實驗

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

3.1 摘要質量總體評價

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

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

圖1 DUC02數據集中的自動摘要質量對比

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

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

表1 DUC02數據集上自動摘要算法最優文檔數量對比

3.2 冗余去除對摘要質量的提升

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

表2 冗余去除對摘要質量的影響

3.3 關鍵詞對摘要質量提升

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

3.4 參數對摘要性能的影響

除阻尼系數d根據PageRank[22]的建議一般取0.85外，算法還包含兩個重要參數ε和α，其中ε決定了算法的收斂速度，α主要調節詞句協同排序時的相互的權重占比。對于ε，本文考察了其在區間[10-5，10-1]變化時算法的迭代次數，如圖3所示。可以發現，WSRank算法的收斂速度令人滿意，即使當ε=10-5時，算法仍能在13次迭代之內收斂。

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

圖3 參數ε對算法收斂速度的影響

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

4 結語

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

圖4 參數α對摘要質量的影響

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] 秦兵，劉挺，李生.基于局部主題判定與抽取的多文檔文摘技術[J].自動化學報，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] 劉美玲，鄭德權，趙鐵軍,等.動態多文檔摘要模型[J].軟件學報，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。

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

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

1001- 9081(2017)07- 2100- 06

10.11772/j.issn.1001- 9081.2017.07.2100