相似度質心多層過濾策略的動態文摘方法

于洋，范文義，劉美玲，王慧強

(1.東北林業大學林學院，黑龍江哈爾濱150040;2.哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001)

動態多文檔文摘的主要任務是在人們已經了解同一主題相關歷史信息的基礎上，獲得隨時間推移的相同主題下的動態變化的新穎性信息。一個新聞話題，通常有它自己的生命周期，包括出現階段、發展階段、衰退階段和消亡階段。不同的階段具有不同的側重點，而不同時刻的話題重心之間具有關聯性，動態多文檔文摘技術需要在主題相關性的基礎上考慮多個文檔集之間的時序關系。

動態文摘任務是由document understanding conference(DUC)［1］2007 年提出的，并且成為了 Text Analysis Conference(TAC)2008年的一項子任務，由美國NIST［2］承辦。在 IARPA的支持下于2007年舉行了第一屆評測會議。主要研究的主題是分析出歷史信息和當前信息之間的關系，找出它們之間的相同信息和相異信息然后提取新信息，過濾歷史信息，實現對文檔集信息演化性的建模。因此，人們希望快速高效的識別出重要的新穎的信息，以減少獲取信息的代價。

張瑾［3］等提出了高性能的動態多文檔文摘方法，利用模糊理論中的隸屬度來衡量當前候選文摘句與歷史信息的關聯性，設定閾值，過濾掉關聯性度量值高于閾值的候選文摘句，這屬于第1大類動態文摘方法。參加TAC2008 Update task評測的系統中的大部分使用的動態文摘方法都屬于第2大類。第3大類動態文摘方法是面向語義的文摘方法，多應用在面向領域的文摘系統和多語言環境中，參加TAC2009 Update task評測的系統絕大部分都是基于語義的建模方法。綜上可知，以上3大類動態文摘方法是該領域中的主導方法。

本研究從分析歷史文檔與當前文檔關系的角度，研究動態演化環境下動態文摘求解模型。首先給出了基于文本相似度累加(text similarity cumulative model，TSCM)的動態多文檔文摘模型和基于質心整體優選(centroid integer selection model，CISM)的動態多文檔文摘模型，應用TSCM來給候選文摘句加權打分，為使文摘具有較低的信息冗余度，使用提出的動態MMR(maximal marginal relevance)算法，然后用CISM進行質心判別和多層過濾。并在TAC2008測試集上進行測試。

1 動態文摘建模方法

1.1 基本概念和思想

1)文本相似度累加思想。

文本相似度累加思想體現在分析歷史文檔和當前文檔間的關系上。文本相似度累加的思路是計算文檔中所有句子的相似度并進行累加，對比以往的詞級相似度計算，提高了內容過濾的可理解性和準確性。因此在文檔內容一層過濾時，首先從動態性的演化性分析的角度對歷史文檔集合和當前文檔集合做句子相似度計算，以時間信息和相似度值為依據過濾掉重復的文本信息，對過濾后的新產生的文檔句子集合重新排序，并抽取出相似度值最低最能反映出信息新穎性的句子集合。句子級的相似度累加所產生的文摘比詞級計算更能反應當前時序階段內容的側重點。

2)質心整體優選。動態多文檔文摘生成文摘結構包括如下幾個步驟:①預處理相關文檔集;②對候選文摘句加權打分;③從候選文摘句集合中提取文摘句想成文摘;④根據相關時間信息對文摘句排序，進而生成連貫合理的文摘。無論動態文摘方法還是靜態文摘方法，這4個步驟都缺一不可。文摘句選取階段是動態多文檔文摘方法的關鍵階段，該階段算法的好壞直接影響該動態文摘方法的性能。質心多層過濾優選方法以文本相似度累加模型為參照，涉及了多文檔文摘技術的3大類型，改進了相應的解決方案。并在動態多文檔文摘的信息顯著度、信息新穎度和信息冗余度3項主要標準指標中應用了新的算法提高性能。

1.2 主要評測方法

多文檔文摘系統的關鍵問題是如何識別重要性信息和刪去冗余性信息。自動多文檔文摘系統在最近幾年獲得了足夠的重視，而對動態多文檔文摘的研究工作才剛剛開始。他們共同的問題是，在不同文檔中出現的信息不可避免的會互相重疊，即有較高的冗余度。因此，高效的動態多文摘方法，需要仔細分析測試任務，解決當前文摘高冗余度和歷史文摘低關聯度的問題。

目前在動態多文檔文摘領域的評價方法主要包括自動評價 ROUGE［4］、BE(basic elements)［5］方法和人工評價金字塔PYRAMID［6］方法。

1)ROUGE和BE方法。

ROUGE方法是由Lin Chin Yew等于2002年提出并在2004年的DUC會議上正式使用。這個評價方法通過計算系統產生的文摘和人工文摘間所重疊的最長單詞數目來評價系統文摘。其評價方法的計算比較復雜。Eduard Hovy等提出了BE方法，它以最小的基本詞素作為比較單元，對ROUGE進行了很好的擴展。

2)Pyramid方法。

該方法是由Nenkova和Passonneau于2004年提出的。它采用一致確認的方法來進行評測。該方法以多年累積的權威性參考文摘中提取得到的短語表做為參考(這些短語由短而長排列，形如金字塔)，通過比較機器文摘和參考文摘中在短語表中包含相同成分的多少來評測機器文摘的質量。

1.3 文本相似度累加模型

具體實現過程如算法1所示。

算法1:基于TSCM的多文檔文摘算法

Input:多文檔集合

Output:生成的動態文摘結果

1)設歷史信息句子集合為Sh，當前信息句子集合為Sc，統計Sh中句子長度;

2)對Sc中的每個句子Sci(0＜i＜ count(Sc))計算Sci與Shi(0＜j＜ count(Sh))相似度值 Sim(senti，sentj)，應用提出的句子級的相似度計算方法進行相似度計算;

3)計算相似度的累加迭代的值:

式中:Weight(Sci)(j)表示句子Sci與Sh中前j(0＜j＜count(Sh))個句子相似度值的累加;

4)根據當前文檔句子集合Sc中的句子Sci的Weight(Sci)(j(j=count(Sh))值按照從高到底的順序排列。設置一個閾值n表示過濾掉的句子的數目，刪除當前文檔句子集合Sc中的前n個句子。count(Sc)代表當前文檔集合中句子的數目。剩下的count(Sc)-n個句子就是當前文檔中包含新信息的句子。在利用TSCM分析歷史信息和當前信息的一層信息過濾之后，動態演化性特征已經凸顯，接下來，使用CISM進行多層的動態信息過濾。

本文提出的CISM涉及了MDS技術的3種類型，改進了相應的解決方案，并應用在動態MDS的信息顯著度、信息新穎度和信息冗余度3項主要標準指標中，增強了模型性能。

1)信息顯著度指標。

為提高質心整體優選動態模型產生文摘的信息顯著度，本章提出應用文本相似度算法來給候選文摘句加權打分。基于句子相似度計算的句子加權方法參見1.5節

2)信息新穎度指標。

信息新穎度是動態MDS的又一重要度量指標，為了動態MDS在信息動態演化過程中保持信息新穎度，本章CISM采用上述提到的第1大類方法過濾與歷史信息具有高關聯度的句子，即在對文摘句加權之前，對文檔集句子集合進行過濾處理，過濾掉當前文檔集中的歷史信息，對文檔集的信息差異性建模，然后從經過濾處理后的句子集合中產生文摘。

3)信息冗余度指標。為了動態文摘能具有較低的信息冗余度，需要選擇高性能的去冗余算法。此模型應用提出的動態MMR算法，參見1.4節。首先從候選文摘句集合中選出權值最高的句子作為正式文摘集合的第1個句子，下一步依據候選文摘句與正式文摘句集合中所有句子的相關性度量值，給候選文摘句集合中所有句子一定懲罰值后獲得新的權值，然后提取權值最高的后選文摘句加入正文摘句集合當中，這樣迭代執行，直到文摘句達到指定的數目。

為提高該動態文摘方法產生文摘的信息顯著度，本模型首先應用文本相似度算法來給候選文摘句加權打分。為使文摘具有較低的信息冗余度，需要選擇高性能的去冗余算法，現階段主流的去冗余算法是最大邊緣相關算法(MMR)［7］使生成的文摘具有低信息冗余性。MMR是一種有效的去冗余度算法，該算法流程如下:

1)首先從候選文摘句集合中選出權值最高的句子作為正式文摘集合的第1個句子;

2)依據候選文摘句與正式文摘句集合中所有句子的相關性度量值，給候選文摘句集合中所有句子一定懲罰值后獲得新的權值;

3)提取權值最高的候選文摘句加入文摘句集合當中，這樣迭代執行直到文摘句達到指定的數目。

MMR算法毋庸置疑的使文摘的性能具有較大幅度的提升，但是它也帶來了相關的問題，即對首句文摘句選擇的成功與否對文摘的性能有較大的影響。如果第1句文摘句選擇失敗，整個文摘將不會具有好的性能。為了解決此問題，提出了一種基于質心整體選優的動態文摘方法。

1.4 質心整體選優模型

基于質心整體選優的動態文摘方法著重考慮了文摘中第一個句子的選擇對文摘的影響，在文摘生成過程中分別以多個高分句子為初始句，利用已有的動態文摘句選擇方法生成多個候選文摘，再引入質心概念對多個候選文摘從整體的內容完整性、新穎性進行衡量。即以文檔集合的質心作為評價依據，以候選文摘整體作為評價對象，對其表述信息的完整性進行衡量，最終從多個候選文摘中選擇內容完整性最好的候選文摘作為該文檔集合的文摘。

基于質心整體選優的文摘句選擇方法包括以下幾個方面:初始句的選擇、多候選文摘的生成以及最終文摘的選擇。CISM方法包括以下幾個方面:初始句的選擇、多候選文摘的生成以及最終文摘的選擇。過程如圖1所示。

1)初始文摘句的選擇。

首先運用文摘句過濾算法過濾掉當前候選文摘句集合中信息新穎度低的句子，生成一個信息新穎度高的候選文摘句集合。用句子的長度信息、位置信息和所包含詞語的TF*IDF*ISF權值(詳見1.5節)對句子進行打分，計算上述處理后的候選文摘句集合中所有句子的信息顯著度，根據句子信息顯著對句子排序。從排序后的序列中，一次選取分值高的指定書目N個的非重復句子作為多個候選文摘的初始句。

圖1 CISM流程Fig.1 CISM process diagram

2)多候選文摘算法描述。

算法2:相似度質心多層過濾文摘算法

Input:文檔集合

Output:N個候選文摘

利用句子的位置信息，長度信息以及所包含詞語的TF*IDF*ISF權值對句子打分。根據權重值對加權后的句子按照從高到低的順序排列，形成句子隊列A。從隊列A選出分值最高的指定數目的N(這里N初值設置給10)個句子作為多候選文摘的初始句。對每一個初始句執行以下操作:

①清空已選文摘句隊列S，將初始句加入S中;

②按句子權重依次選取后續句子，選擇排名最高的候選句加入已選文摘句集合S;

③重復步驟②，直到已選文摘句集合S達到文摘的目標尺寸(句子數、字數)，終止;

④將生成的候選文摘加入到候選文摘隊列M;

3)最優文摘的選擇。

對隊列M中的每一個候選文摘計算權重:

式中:Score(Di)代表候選文摘打分;senti是候選文摘中句子;Di代表候選文摘;C代表當前文檔集合的句子集合;sentj代表當前句子集合中的句子;sentk代表歷史文摘中的句子;H代表歷史文摘句集合;α和β分別代表候選文摘與當前文檔句的相似度和與歷史文摘句的相似度所占的比例。應用此模型算法，將候選文摘的權重進行重排列，選出打分最高的最優文摘作為最終結果。

1.5 動態多文檔文摘句子加權方法

應用本項目前期工作中作者［8］提出的3種改進的句子加權方法:分別是動態短語的信息粒度［9］表示方法，動態TF-IDF-ISF的句子加權方法和動態句子級相似度計算的加權方法。

動態短語信息粒度的表示方法為

式中:Phrase_Weight(j)是句子中短語的權重:

式中:FR(Phrase)是短語的詞頻，MaxFR是詞頻最大短語的詞頻，SentLength_Weight(senti)是句子長度權重。

在實際的計算過程中，如果SentLength＜x，舍掉此句，不參與運算;

如SentLength＞=x則SentLength_Weight(senti)=0;x是動態的句子長度閾值，根據實際需要進行調整。

動態TF-IDF-ISF的句子加權方法:

式中 :Weight(senti)表示句子Si的打分，fWordWgt=ISF表示句子 senti的詞語權重，其中，TF(w)表示詞w在文檔中的出現頻率，IDF(w)表示詞w的反文檔頻率，ISF(w)表示詞w的反句子頻率，f(w)是頻率統計函數，DF(w)為整個文檔集合中包含詞w的文檔數，SF(w)為整個文檔集中包含詞w的句子數。

基于句子相似度計算的句子加權方法:

式中:Weight(Si)(0＜i＜count)表示句子Si的權重;count表示文檔集合中句子的總數 Simij=，表示句子Si與Sj相似度值.

2 實驗結果與分析

2.1 實驗數據及評價

從DUC 2007開始，Update Summarization測試語料從主要任務的45個話題中挑選10個話題，每個話題由3個連續進化的時間片組成。假定讀者對先前的文檔有一定的了解，Update Summarization任務的目的就是針對每一個時間片給出100字的動態多文檔文摘，該文摘反映隨著時序的變化和基于同一主題的文檔集合內容的動態演化，可見文摘技術向網絡動態數據信息處理方向發展。

在TAC 2008中，測試預料假設已有歷史多文檔集合，按照時間順序后產生的集合均看做是演化的多文檔集合。Update Summarization任務的測試語料由來自AQUAINT-2的48個話題組成，每個話題包含兩個時間片，均由10個大小相當的文檔組成。

在TAC2008的Update Summarization測試數據上，評價標準采用文摘評測領域著名的ROUGE工具，其中最主要的2個指標ROUGE-2和 ROUGESU4*是評價動態多文檔文摘性能的。將動態文摘結果的(R-2)和(R-SU4*)得分與TAC 2008 Update國際標準參賽系統的得分進行了對比，結果表明不同模型在性能上各有所長。

Example

＜topic id=“D0801A”＞

＜title＞Airbus A380＜title＞

＜narrative＞Describe developments in the production and launch of the Airbus A380.

＜narrative＞

＜docsetA id=“D0801A-A”＞

＜doc id=“AFP ENG 20050115.0485”＞

……

＜doc id=“AFP ENG 20050504.0328”＞＜docsetA＞

＜docsetB id=“D0801A-B”＞

＜doc id=“AFP ENG 20050601.0580”＞

……

＜doc id=“APW ENG 20060329.0349”＞

＜docsetB＞

＜topic＞

2.2 實驗結果

在以上模型基礎上，以4組實驗進行結果的比較。

實驗1 是在文本相似度累加動態多文檔文摘模型下3種不同加權算法生成的動態文摘的ROUGE評價結果，如表1所示。

表1 TSCM 3種算法的文摘性能對比Table 1 Comparison of three TSCM algorithms

實驗2 測試模型中文檔過濾過程中的所設置的句子數對動態多文檔文摘的影響，對受句子長度影響最大的TSCM_C進行了分析。實驗在10到110的取值范圍內對句子個數進行測試，實驗結果如圖2所示。

圖2 TSCM_C文摘長度閾值分析Fig.2 TSCM_C digest length threshold analysis

由圖2以看出，TSCM_C在句子數為100時達到最優性能。此時，在ROUGE-2和ROUGE-SU4*上的得分分別為0.050 13和0.138 60，在ROUGE-2上進一步縮小了與第一名的差距，同時在ROUGESU4*上更加凸顯了TSCM_C模型的動態演化性。

實驗3 CISM模型和TSCM模型最好性能性能的比較，如表2所示:

表2 CISM模型和TSCM模型性能對比Table 2 CISM and TSCM performance comparison

實驗4 如表3所示，其中CISM模型整體性能接近最好成績，TSCM_C中短語信息粒度的句子加權方法的R-2比第1名的系統稍差，但是R-SU4*的分數已經超過了第1名。TSCM_B模型中綜合打分進入前3名，說明這2種動態文摘模型在不同側重點上，具有很好的性能和潛力，具有發展的空間，是值得研究的算法。

表3 與TAC2008實際系統的性能對比Table 3 Comparison with performance of TAC2008

2.3 實驗分析

通過以上實驗結果，綜合分析提出的2種模型，動態多文檔候選集多層過濾模型，基于文本相似度累加模型實驗打分位于TAC2008發布的所有系統結果的上游。使用的改進的基于短語的句子加權方法時，它的ROUGE-SU4*打分已高出了TAC2008中第1名的系統，基于文本相似度累加模型實驗打分位于TAC2008發布的所有系統結果的上游。可見TSCM是一種動態性能較好的模型。適用于動態性較強的新聞領域及實時社會計算領域。CISM系統的ROUGE-2打分僅次于第2名的系統，ROUGESU4*打分也在前列，表明通過修改去冗余方法也可使該模型生成的文摘具有較強的顯著性和代表性。以生成的文摘集合為候選集合的方法，具有更強的靈活性，經算法調整可適用于有不同要求的領域，是一種適應性較強的動態文摘模型。

3 結束語

在動態多文檔文摘領域中，動態多文檔文摘模型研究是一個全新的課題，前正處于起步階段。已有研究者提出了多種類型的動態文摘方法，有基于候選文摘句過濾的，有基于信息懲罰加權的，也有基于語義的，并且都獲得了良好的性能。本項目提出的2種改進模型改善了原來動態文摘模型的性能，提高了文本抽取和文本理解的效率，與其他的模型比較，具有良好的動態性和生成高質量文摘。但是還存在許多問題需要解決，比如如何提高首句提取的精確率，如何使提取的首句具有動態演化性等問題。下一步工作是解決該改進算法所存在的問題，進一步提高改進算法的性能，應用于多種實際數據介質，增強文摘演化的識別能力。此類研究對于大數據集及數據挖掘的研究具有積極意義。

［1］LIN C Y，HOVY E.Automatic evaluation of summaries using n-gram co-occurrence statistics［C］//Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology.Morristown，USA，2003:71-78.

［2］WAN Xiaojun.Using bilingual information for cross-language document summarization［C］//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics:HumanLanguageTechnologies. Portland，USA，2011:1546-1555.

［3］張瑾，許洪波，程學旗.面向網絡演化信息的動態文摘方法研究［J］.計算機學報，2008，3(4):696-696.ZHANG Jin，XU Hongbo，CHENG Xueqi.Research abstracts method for dynamic information network evolution［J］.Journal of Computers，2008，3(4):696-696.

［4］LIN C Y.Rouge:a package for automatic evaluation of summaries［C］//Text Summarization Branches Out:Proceedings of the ACL-04 Workshop.Barcelona，Spain，2004:74-81.

［5］HOVY E，LIN C Y，ZHOU L，et al.Automated summarization evaluation with basic elements［C］//Proceedings of the Fifth Conference on Language Resources and Evaluation(LREC 2006).Genoa，Italy，2006:604-611.

［6］NENKOVA A，PASSONNEAU R，MCKEOWN K.The pyramid method:incorporating human content selection variation in summarization evaluation［J］.ACM Transactions on Speech and Language Processing(TSLP)，2007，4(2):1-8

［7］GOLDSTEIN J，MITTAL V，CARBONELL J，et al.Creating and evaluating multi-document sentence extract summaries［C］//Proceedings of The Ninth International Conference on Information and Knowledge Management.Washington DC，USA，2000:165-172.

［8］劉美玲，任洪娥，于洋.基于網絡的動態多文檔文摘系統框架［J］.軟件學報，2013，24(5):1006-1021.LIU Meiling，REN Honge，YU Yang.Based on dynamic multi-document summarization system network framework［J］.J Of Software，2013，24(5):1006-1021.

［9］劉美玲，鄭德權，趙鐵軍，等.動態多文檔文摘模型研究［J］.軟件學報，2012，23(2):289-298 .LIU Meiling，ZHENG Dequan，ZHAO Tiejun，et al.Dynamic multi-document summarization model［J］.J of Software，2012，23(2):289-298.