張世博，劉博愛

（1.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100876；2.北京石油化工學(xué)院 計(jì)算機(jī)系，北京 102600）

0 引言

近來文本自動(dòng)摘要技術(shù)是一個(gè)被廣泛關(guān)注的研究熱點(diǎn)。人們對(duì)于用最少的時(shí)間得到盡可能多信息的需求促使了自動(dòng)摘要技術(shù)的發(fā)展。

目前大多數(shù)自動(dòng)摘要系統(tǒng)使用句子提取方式［1］，從文檔中提取的句子經(jīng)過平滑處理被組織成為摘要的一部分。Dragomir及Jing等［2］人介紹了一種多文檔摘要技術(shù)，基于聚類中心從文檔中生成內(nèi)容，并給出了評(píng)估方案。Wong等［3］人利用機(jī)器學(xué)習(xí)技術(shù)組合內(nèi)容、相關(guān)性及各種特征設(shè)計(jì)了摘要方法，通過監(jiān)督學(xué)習(xí)確定句子的重要性，嘗試了多特征的權(quán)重，在DUC2001（Document Understanding Conference，2001）數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)取得了較好的效果。Ansamma和Wilscy 介紹了基于隨機(jī)森林分類器的多文檔摘要方法，用分類器鑒別數(shù)據(jù)集中的句子是否應(yīng)該屬于摘要，在DUC2002數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果顯示此方法得到的摘要質(zhì)量較好。武漢大學(xué)彭敏［5］最新提出一個(gè)通用的反饋式排序框架F-Rank，為不同類型和不同數(shù)量的自動(dòng)摘要提供一種能夠綜合反映摘要任務(wù)目標(biāo)的交互式排序結(jié)果融合方法，基于文檔、句子和詞三個(gè)文本粒度的相互增強(qiáng)關(guān)系，提出結(jié)合用戶查詢需求影響的相互增強(qiáng)鏈模型，實(shí)現(xiàn)了查詢導(dǎo)向的多文本粒度間的相似度測(cè)度和句子排序方法；在此基礎(chǔ)上，基于F-Rank框架對(duì)以上兩個(gè)摘要任務(wù)的基本排序結(jié)果進(jìn)行交互式反饋學(xué)習(xí)和融合排序，從而生成查詢導(dǎo)向的更新式摘要的綜合排序結(jié)果。

一般來說，自動(dòng)摘要采用機(jī)器學(xué)習(xí)算法依據(jù)給定的特征集和訓(xùn)練模型，分析前人的研究發(fā)現(xiàn)，如何獲得高質(zhì)量已標(biāo)注的語料訓(xùn)練集、提高分類器的學(xué)習(xí)能力并選取更有效的特征等成為獲得高質(zhì)量摘要的關(guān)鍵。

在本文中，我們嘗試用兩種方法從數(shù)據(jù)集中自動(dòng)產(chǎn)生摘要。一是對(duì)文檔集中的句子進(jìn)行重要性評(píng)分，但并不是貪婪的僅僅依照最高值評(píng)分選取句子，而是通過Stack Decoder算法進(jìn)行綜合評(píng)估。二是基于規(guī)則圖的方式，產(chǎn)生摘要的任務(wù)被轉(zhuǎn)換為在句子非相似性圖中查找小范圍集合的問題。圖中的一個(gè)子集合由一系列有強(qiáng)鏈接關(guān)系的頂點(diǎn)組成，從眾多的頂點(diǎn)中，選擇子集合頂點(diǎn)，并結(jié)合第一步的重要性評(píng)分來產(chǎn)生最終的摘要內(nèi)容。

1 相似度評(píng)分和特征

本節(jié)主要介紹了算法中用到的相似度評(píng)分以及表示文檔特征的特征項(xiàng)。

1.1 基于Word Net的語義相似度評(píng)分

在計(jì)算句子間的相似度時(shí)，我們使用了基于Lesk算法的語義相似度評(píng)價(jià)方法。該算法由Michael E.Lesk［6］于1986年提出，是一個(gè)基于詞典的詞義消歧方法。該算法認(rèn)為：一個(gè)詞在詞典中的詞義解釋與該詞所在句子具有相似性，這種相似性可以由相同單詞的個(gè)數(shù)來表示，只需計(jì)算多義詞中各個(gè)詞語在詞典中的定義與多義詞上下文詞語定義之間的詞匯重疊度，選擇重疊度最大的詞義作為其正確的詞義即可。算法過程如下：

第一步：去除停用詞，句子切分；

第二步：POS標(biāo)記；

第三步：詞干處理；

第四步：用Lesk詞義消歧方法查找合適的單詞；

第五步：基于單詞相似度計(jì)算句子相似度。

一旦得到每個(gè)單詞合適的詞義，則利用Word Net的路徑長(zhǎng)度相似度確定同義詞集合（synset）中的語義相似度。路徑代價(jià)越小，表示語義相似度越高。路徑長(zhǎng)度相似度的計(jì)算方法如下：

給出兩個(gè)句子，預(yù)先計(jì)算出在不同位置上的單詞詞義的語義相似度，得到相似關(guān)系矩陣［Xm，Yn］，其中m，n分別代表句子X和Y的長(zhǎng)度。句子間的語義相似度被表示為二分圖的最大匹配權(quán)重，得到圖中不相交的節(jié)點(diǎn)集，第一個(gè)集合取自第一個(gè)句子，第二個(gè)集合取自另外一個(gè)句子?；诘玫降亩謭D利用Hungarian算法計(jì)算全局最小值的最佳匹配。匹配成對(duì)的結(jié)果表示兩個(gè)句子的單一相似度值。為得到文檔集合中綜合相似度，采用如下的計(jì)算方法。

利用Word Net得到句子中各種單詞的語義分值，方法主要考慮同義詞集合的擴(kuò)展，進(jìn)而得到句子的相似度計(jì)算公式如下：

1.2 句子的重要性評(píng)分

每個(gè)句子都有一個(gè)重要性評(píng)分值，它是一種衡量句子作用的好措施。評(píng)分值可以用來對(duì)句子排序，挑選最重要的句子。被選擇的句子出現(xiàn)在摘要中的概率是同它的評(píng)分值成比例的，每個(gè)句子由一系列的特征表示，評(píng)分值則是各個(gè)特征的加權(quán)權(quán)重之和。

在文中使用到了如下的特征：

TF-IDF之和（TF-IDF Sum）：句子的重要性往往由組成的單詞決定，這個(gè)特征為句子中所有單詞的TF-IDF分值之和構(gòu)成。

句子長(zhǎng)度（Sentence Length）：句子中單詞的數(shù)量。句子越長(zhǎng)，更有可能容納更多的信息量。

命名實(shí)體數(shù)量（Named Entities count）：有命名實(shí)體的句子更具有意義，預(yù)示著有實(shí)體在發(fā)揮作用。通過Stanford NER類庫(kù)識(shí)別命名實(shí)體，把句子中的實(shí)體數(shù)量做為此特征項(xiàng)。

前k個(gè)重要詞（Top-k Important words）：前面的TF-IDF之和特征會(huì)導(dǎo)致傾向選擇長(zhǎng)句即使其包含了較多無價(jià)值的單詞。為防止出現(xiàn)這種結(jié)果，引入本特征，先把句子中單詞按tf-idf排序，特征取值為前k個(gè)單詞的個(gè)數(shù)。

句子位置（Sentence Position）：文檔往往會(huì)在第一段表示核心意思，在最后一段總結(jié)全文。因此句子位置被考慮為重要性與否的特征項(xiàng)。

數(shù)字個(gè)數(shù)（Numerical Literals count）：句子中出現(xiàn)的數(shù)字通常意味著某一種的確定屬性，如交通事故中的傷亡人數(shù)、歷年的統(tǒng)計(jì)信息等。把句子中所有出現(xiàn)的數(shù)字的個(gè)數(shù)作為本特征。

大寫單詞個(gè)數(shù)（Upper case letters count）：大寫的單詞通常表示實(shí)體，是事件中的主角，出現(xiàn)的個(gè)數(shù)設(shè)定為特征項(xiàng)。

得到的特征向量應(yīng)用在訓(xùn)練集中，采用邏輯回歸分類法計(jì)算特征權(quán)重值，然后在測(cè)試集中計(jì)算句子的重要性評(píng)分。

1.3 歸一化處理

在文中我們實(shí)驗(yàn)了各種歸一化方法。計(jì)算特征值，基于句子長(zhǎng)度和其他項(xiàng)對(duì)特征做歸一化。但是并沒有取得更好的效果，因?yàn)樵趫?zhí)行除法的時(shí)候丟失了諸多信息，比如，較長(zhǎng)的句子包含相對(duì)重要或者多的信息，但是因?yàn)殚L(zhǎng)度值作為分母，導(dǎo)致降低了特征項(xiàng)值，同樣，短句子則可能因?yàn)橥瑯拥姆椒ǚ炊嵘颂卣黜?xiàng)值。

因此，需要采用一種更合理的折中方案，對(duì)句子長(zhǎng)度等各特征項(xiàng)加權(quán)，使其結(jié)果既能反映長(zhǎng)度的重要性，又不至于因?yàn)殚L(zhǎng)度原因丟失特征項(xiàng)權(quán)重值。數(shù)學(xué)中有兩種函數(shù)具有良好的收斂性和穩(wěn)定性，它們分別是非線性函數(shù)和Sigmoid函數(shù)。

Fig.1 Curve of Sigmoid and non-linear function圖1 Sigmoid函數(shù)與非線性函數(shù)曲線圖

從圖1中可以看出，隨著n增大，兩個(gè)函數(shù)都收斂于1。其中Sigmoid函數(shù)在x軸坐標(biāo)大于6之后的收斂速度更快，穩(wěn)定性更強(qiáng)，因此，采用Sigmoid函數(shù)作為歸一化的參考方法。特征項(xiàng)的歸一化方法如下：

相對(duì)于非歸一化和句子長(zhǎng)度歸一化方法，此方法在實(shí)驗(yàn)中被驗(yàn)證是有效的。

2 算法

在本節(jié)闡述了兩種提取文檔摘要的方法。

2.1 基于Stack Decoder的方法

基于文檔的內(nèi)容，用Stack Decoder方法［7］尋找具有最優(yōu)綜合分值的摘要內(nèi)容。摘要的綜合重要性評(píng)分值等于所含所有句子評(píng)分值之和。

把文檔集中的所有句子及其對(duì)應(yīng)的重要性評(píng)分作為輸入，此方法中給解碼器設(shè)置maxlength＋1個(gè)堆棧，每種長(zhǎng)度的句子對(duì)應(yīng)一個(gè)解碼器，共有maxlength個(gè)，另外一個(gè)解碼器對(duì)應(yīng)于匯總的摘要，它比前面的各種長(zhǎng)度的句子的最大maxlength都大。每個(gè)堆棧均保留其對(duì)應(yīng)長(zhǎng)度的最優(yōu)摘要。我們使用優(yōu)先隊(duì)列處理堆棧邏輯，因此隊(duì)列的長(zhǎng)度是有限的。執(zhí)行過程中，通過判斷某一特定的堆棧，只要其有空余，則即可加入新的一組文檔集。因?yàn)椴捎昧薙igmoid算法，為了避免每個(gè)堆棧中集合指數(shù)式增長(zhǎng)，需要維護(hù)設(shè)定堆棧的大小。

初始，所有的句子被放在其對(duì)應(yīng)長(zhǎng)度的隊(duì)列中，隊(duì)列按照＜score，id＞的形式組織內(nèi)容，接下來過程見算法1所示。

算法1 基于Stack Decoder的方法Algorithm 1 Stack decoder based algorithus

2.2 基于圖的方法

在文獻(xiàn)［8］中，構(gòu)造了一個(gè)句子間的余弦相似度無向圖，用特征向量表示圖中的邊，被應(yīng)用在計(jì)算句子間的排序上。文獻(xiàn)［9］的作者使用了SumGraph結(jié)構(gòu)，利用Pathfinder算法獲取句子間的等級(jí)排序，計(jì)算句子頂點(diǎn)之間的相關(guān)性。

在我們的方法中，把提取文檔摘要過程表示為求解分團(tuán)問題（clique finding problem）?；谏弦还?jié)中計(jì)算得到的相似度評(píng)分，構(gòu)造了一個(gè)句子非相似性圖，圖中把句子當(dāng)作節(jié)點(diǎn)，如果兩個(gè)句子之間的相似度低于一個(gè)閾值，那在二者之間畫一條邊。邊的存在，意味著句子沒有足夠的相似，我們需要找到一個(gè)節(jié)點(diǎn)子集，集合中的節(jié)點(diǎn)兩兩相連，它們表示在文檔集合內(nèi)容上的較低的信息冗余，對(duì)應(yīng)于圖中的一個(gè)團(tuán)（clique），每個(gè)團(tuán)即是一個(gè)摘要內(nèi)容的候選者。通過運(yùn)行clique finder算法找到所有最大的團(tuán)，計(jì)算過程中使用了Java Graph［10］類庫(kù)。

圖G＝（V，E）的構(gòu)造方法如下：一旦確定一個(gè)分團(tuán)，則按照重要性評(píng)分對(duì)節(jié)點(diǎn)排序，依次添加句子形成摘要一直到集合為空。

因?yàn)榍蠼夥謭F(tuán)問題是個(gè)NP完備問題，計(jì)算耗時(shí)，不容易計(jì)算出最大的頂點(diǎn)集合，當(dāng)分團(tuán)間的相似度設(shè)定為小于0.5時(shí)，有250條句子的文檔集其邊的數(shù)量大約為15 000，如表1所示。最壞情況下一個(gè)有n個(gè)頂點(diǎn)的圖，查找最大分團(tuán)的時(shí)間復(fù)雜度為O（3n／3），對(duì)于一個(gè)高密度的圖來說計(jì)算量相當(dāng)大。

表1 Clique Finding問題的圖節(jié)點(diǎn)統(tǒng)計(jì)Table 1 Graph statistics of clique finding problem

為此在實(shí)際執(zhí)行過程中，使用了句子的子集，同樣為了防止運(yùn)行時(shí)間的指數(shù)性增長(zhǎng)，縮減了圖的密度，利用取文檔集中的60個(gè)句子進(jìn)行計(jì)算。從表中可見，邊的數(shù)量大幅度減少。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)中，使用的數(shù)據(jù)集是DUC 2004中的Task2語料庫(kù)［11］。在DUC 2004的多文檔摘要提取子任務(wù)中，參賽者要對(duì)50篇文檔的文檔集提取摘要，其中每10篇文檔為一個(gè)主題子類，要求給每個(gè)子類產(chǎn)生大約100個(gè)單詞的摘要。

3.2 相似度評(píng)分

先對(duì)詞匯進(jìn)行詞干處理，包含停用詞多的句子的重要性評(píng)分往往較低，為了消除頻繁出現(xiàn)的特征項(xiàng)的干擾，還需要移除停用詞。其他諸如NER和前k位單詞等特征項(xiàng)的使用使得帶有一般單詞的長(zhǎng)句并不會(huì)抑制帶有重要單詞的短句被視為候選摘要。

我們選擇了簡(jiǎn)單余弦相似度、TF-IDF距離和Word Net相似度作為候選度量尺度。余弦和TF-IDF方法性能相近，初始時(shí)Word Net的性能并沒有期望的高，但經(jīng)過歸一化處理得到了提升。

例如，基于Word Net計(jì)算如下DUC2004語料庫(kù)中的兩個(gè)句子的相似度：

"Christianconservativesarguethathatecrimelawsrestrictfreedomofspeech，whilegayrightsactivistsandotherssaytheselawssendamessagethatattacksonminoritieswillnotbetolerated."

和

"Butwhenhestopped，hefoundtheburned，batteredandnearlylifelessbodyofMatthewShepard，anopenlygaycollegestudentwhohadbeentiedtothefence18hoursearlier."

二者的相似度為0.68。而在非詞干化處理的情況下，以余弦方法計(jì)算相似度為0.08，詞干處理以后為0.28。這顯示了詞干處理的優(yōu)點(diǎn)，尤其當(dāng)單詞差異較大而在同義詞集中具有相似模式時(shí)用Word Net方法的有效性。

3.3 特征

測(cè)試集中的文檔均是關(guān)于某一類事件內(nèi)容的，多數(shù)情況下摘要單詞僅會(huì)在文檔題目中有所涉及，這就導(dǎo)致了這些重要單詞的TF-IDF趨向于零，為避免這種情況，對(duì)詞頻采用log計(jì)算。

采用Sigmoid函數(shù)對(duì)特征項(xiàng)歸一化處理并應(yīng)用在計(jì)算句子的重要性評(píng)分中。但是這會(huì)導(dǎo)致兩個(gè)較短的句子比一條長(zhǎng)句子有更高評(píng)分的情況發(fā)生。這是因?yàn)镾igmoid函數(shù)取值在［0，1］范圍內(nèi)，為此句子間的差別變小，為此又在其基礎(chǔ)上疊加采用線性函數(shù)計(jì)算句子的重要性評(píng)分值。

3.4 結(jié)果及分析

在數(shù)據(jù)集DUC2004上進(jìn)行了實(shí)驗(yàn)，使用了上述提到的各種相似性措施、重要性評(píng)分和歸一化方法生成文檔摘要，利用評(píng)測(cè)方法ROUGE評(píng)測(cè)產(chǎn)生的摘要。

處理高密度圖時(shí)間復(fù)雜度過高，在實(shí)驗(yàn)中選取每個(gè)主題的60條句子，建立了句子的非相似性圖。兩種方法生成摘要的時(shí)間對(duì)比如表2所示。

表2 每種方法生成摘要所消耗的時(shí)間對(duì)比Table 2 Time taken to generate a summary by each method

表3顯示了在各種歸一化方案下基于Stack Decoder方法生成摘要的ROUGE的評(píng)測(cè)值。歸一化方法包括：長(zhǎng)度值歸一和Sigmoid歸一。相似度評(píng)價(jià)方法是TF-IDF和余弦方法。從表中看出，Sigmoid歸一化相比較來說具有更好的性能，更能體現(xiàn)文檔集合中各項(xiàng)重點(diǎn)信息。

表3 Stack Decoder方法下采用不同歸一化措施產(chǎn)生摘要的ROUGE評(píng)測(cè)值Table 3 ROUGE scores of summaries generated using the Stack decoder mechanism with various normalization schemes.

表4顯示了兩種方法的最終對(duì)比，看出Stack Decoder方法和基于圖的方法性能比較接近。良好的相似度評(píng)價(jià)尺度和優(yōu)質(zhì)的訓(xùn)練集估計(jì)參數(shù)會(huì)幫助提升評(píng)分。上述表中的最后一行表示是在Stack Decoder下通過手動(dòng)設(shè)置參數(shù)得到的計(jì)算ROUGE評(píng)測(cè)值，其遠(yuǎn)高于另外二者，顯示了參數(shù)估計(jì)方法仍有較大提升的空間。在實(shí)施基于圖的計(jì)算時(shí)，發(fā)現(xiàn)相對(duì)于構(gòu)建句子相似性圖，構(gòu)建句子的非相似性圖效果更好，我們認(rèn)為其原因是前者會(huì)產(chǎn)生過長(zhǎng)的文檔句子節(jié)點(diǎn)關(guān)系鏈。

表4 利用兩種方法產(chǎn)生摘要的ROUGE評(píng)分（＊－手動(dòng)設(shè)置參數(shù)）Table 4 ROUGE scores of summaries generated using BOTH the methods（＊-hand set parameters）

4 總結(jié)

在本文中我們首先設(shè)計(jì)了句子重要性評(píng)分的策略，綜合應(yīng)用了TF-IDF、句子長(zhǎng)度、命名實(shí)體數(shù)量、句子位置、大寫字母以及數(shù)字等多個(gè)特征，并采用Sigmoid歸一化處理。然后基于Stack Decoder方法利用堆棧計(jì)算相似性評(píng)分，構(gòu)造句子非相似性圖，圖中把句子當(dāng)作節(jié)點(diǎn)，節(jié)點(diǎn)間的相似度小于閾值則存在邊，通過尋找一個(gè)節(jié)點(diǎn)子集，使得集合中的節(jié)點(diǎn)兩兩相連，即意味著文檔集合內(nèi)容上有較低的信息冗余，子集視為一個(gè)團(tuán)，表示摘要內(nèi)容的候選者，再利用clique finder算法求解最大分團(tuán)得到摘要。實(shí)驗(yàn)結(jié)果顯示在歸一化方案下設(shè)計(jì)的算法能取得較好的效果，提升了計(jì)算效率。

接下來的工作中，有兩點(diǎn)需要進(jìn)一步完善，一是計(jì)劃增加句子的特征候選項(xiàng)，比如節(jié)點(diǎn)的Page Rank屬性，可以幫助我們理解摘要過程中句子之間的關(guān)系；二是壓縮句子的技術(shù)，移除或縮減不必要的部分以提升摘要過程中的執(zhí)行效率。

［1］ Liu D X，He Y X，Ji D H.A Novel Chinese Multi-Document Summarization Using Clustering Based Sentence Extraction.Machine Learning and Cybernetics［C］∥2006 International Conference on.IEEE，2006：2592-2597.

［2］ Radev D R，Jing H，Budzikowska M.Centroid-based Summarization of Multiple Documents：Sentence Extraction，Utility－based Evaluation and User studies C Proceedings of the 2000 NAACL-ANLP Workshop on Automatic summarization.Association for Computational Linguistics，2010：21-30.

［3］ Wong K F，Wu M，Li W.Extractive Summarization Using Supervised and Semi-supervised Learning［C］／／Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1.Association for Computational Linguistics，2008：985-992.

［4］ Ansamma J，Wilscy M.Random Forest Classifier Based Multi-document Summarization System［J］.IEEE Recent Advances in Intelligent Computational Systems（RAICS），2013：31-36.

［5］ Peng M，Huang J，Sun S.Micro-blogger Influence Analysis Based on Use Feature［J］.Journal of Internet Technology，ISSN：1607-9264，2014，14（2）：307-314.

［6］ Lesk M.Automatic Sense Disambiguation Using Machine Readable Dictionaries：How to Tell a Pine Cone From an Ice Cream Cone［C］／／Proceedings of the 5th annual international conference on Systems documentation.ACM，1986：24-26.

［7］ Paul D B.An Efficient A＊ Stack Decoder Algorithm for Continuous Speech Recognition with a Stochastic Language Model.Acoustics，Speech，and Signal［C］／／Processing，1992.ICASSP-92.，1992 IEEE International Conference on.IEEE，1992，1：25-28.

［8］ Erkan，Günes，Dragomir R.Radev.LexRank：graph-based Lexical Centrality as Salience in Text Summarization［J］.Journal of Artificial Intelligence Research，2004，22：457-479.

［9］ Patil，Kaustubh，Pavel Brazdil.Text Summarization：Using Centrality in the Pathfinder Network［C］／／Int J Comput Sci Inform Syst 2，2007：18-32.

［10］ Barak N，JGraph T［EB／OL］.http：／／jgrapht.org／javadoc／overview-summary.html，2013-12-18.

［11］ National Institute of Standards and Technology，Document Understanding Conferences［EB／OL］.2004.http：／／wwwnlpir.nist.gov／projects／duc／data.html.2004.