基于超圖的文本摘要與關鍵詞協同抽取研究

莫鵬，胡珀，黃湘冀，何婷婷

（華中師范大學計算機學院，湖北武漢430079）

1 引言

文本摘要是從給定的文本中生成能夠表達原文主題的精簡摘要；關鍵詞抽取是從給定文章中抽取出重要的詞或短語，這些詞或短語能夠代表原文的重要信息。上述兩種研究任務有一定的相似性，它們的目的都是獲取文章的簡潔表達。文本摘要和關鍵詞抽取之所以受到很大關注，是因為它們在文本挖掘的很多領域有著重要的應用，包括文本檢索、文本聚類等。例如，文本摘要能夠方便用戶快速瀏覽搜索的結果并且快速找到所需信息；而關鍵詞可以作為文章的索引，以此來提高文本檢索的準確性。

文本摘要和關鍵詞抽取都可以分為一般式的和查詢相關的。一般式的文本摘要和關鍵詞抽取要盡可能覆蓋原文的重要信息，它面向的是所有用戶。而查詢相關的文本摘要和關鍵詞抽取是在給定一個查詢條件下，生成的摘要和抽取出的關鍵詞要盡可能地和這個查詢相關，它面向的是特定用戶需求。還可按照處理文本的數量將其劃分為單文檔式和多文檔式。本文關注的是一般式的單文檔摘要和關鍵詞抽取。

文本摘要和關鍵詞抽取已經在自然語言處理和信息檢索領域被廣泛研究。近年來，基于圖的排序算法已經成功地應用于文本摘要［1－2］和關鍵詞抽取［1］。通常，這些方法利用投票機制從文本中抽取出句子或關鍵詞。雖然這兩個任務有很多共同之處，但是大多數方法僅研究其中一個任務。

Wan等人提出了一種基于圖的迭代強化方法［3］在一個框架下同時處理這兩個任務。該方法基于兩個假設，假設1：一個句子如果與其他重要的句子有密切的關系，那么這個句子也是重要的；一個詞如果與其他重要的詞關系密切，則這個詞也是重要的。假設2：一個句子如果包含許多重要的詞，那么這個句子應該是重要的；一個詞如果出現在許多重要的句子中，則這個詞也是重要的。該方法同時考慮了句子與詞之間的三種關系（句子與句子之間的同質關系，詞與詞之間的同質關系，句子與詞之間的異質關系），分別構造了三種關系圖（SS－Graph、WW－Graph、SW－Graph），句子和詞之間的上述三種關系相互強化，迭代計算出句子和詞的重要性得分，直到收斂。此方法僅能表達句子與詞之間的各種二元關系，而忽視了不同文本單元間潛在的若干重要的高階關系。為此，本文提出了一種基于超圖的文本摘要和關鍵詞協同抽取方法HBCE（Hypergraphbased Collaborative Extraction），以句子作為超邊，以詞作為節點構建超圖，在一個統一的超圖模型下同時利用句子與詞之間的高階信息來生成摘要和關鍵詞。另外，該方法不需要利用知識庫或背景語料，使得該方法在模型和計算復雜度上都更有優勢。

2 相關工作

2.1 文本摘要

文本摘要的方法通常分為抽取式和摘要式，本文主要研究抽取式單文本摘要。抽取式文本摘要首先給文章中的每個句子打分，根據分數將句子排序。句子分數的計算通常結合了統計學和語言學特征，包括詞頻、句子位置特征、線索詞和主題標簽［4－5］等。也有一些利用機器學習抽取句子的方法，有非監督的方法［6］和監督的方法［7－8］，除此之外，還有最大邊際相關性（MMR）［9］、潛在語義分析（LSA）［10］等方法。基于圖的方法也被廣泛應用于抽取式文本摘要任務中，包括TextRank［1］和LexPageRank［2］，這些方法基于句子相似性，構建關系矩陣，每個句子的重要性由和它相關的句子來決定。這些方法通常都只考慮了句子和句子之間的關系。Wan等人提出了一種基于圖的迭代強化方法［3］，該方法同時考慮了句子與句子、詞與詞、句子與詞之間的各種關系，在句子排序的過程中融入了詞的強化作用。

2.2 關鍵詞抽取

傳統的關鍵詞抽取方法僅僅使用文本中包含的顯式信息，如詞頻和位置等。Salton和Buckley提出了一個簡單的基于詞頻的關鍵詞抽取方法［11］。基于圖的方法有TextRank［1］，該方法使用了三種統計屬性信息，包括tf×idf、距離和關鍵短語頻率。還有Wan等人提出的基于圖的迭代強化方法［3］，考慮了句子對詞的強化作用。Ercan和Cicekli提出了使用詞匯鏈特征的方法［12］。比較流行的還有基于機器學習的關鍵詞抽取方法［13－15］，通過機器學習算法為候選詞分類，進而判斷候選詞是否屬于關鍵詞。目前，已經有很多方法開始使用Wikipedia作為背景知識來抽取文本中的關鍵詞［16－17］。

3 基于超圖的協同抽取方法

3.1 構造超圖

定義HG（V，E，w）為一個有權無向超圖，點集合為V，邊集合為E。超邊e是V的一個子集∪e∈Ee＝V，e的權重為w：E→。如果v∈e，則超邊e與v關聯。超圖的關聯矩陣定義為H∈?｜V｜×｜E｜如式（1）所示。

點和超邊的度定義如式（2）、（3）所示。

De和Dv分別代表超邊和點的度對角矩陣。We是邊權重對角矩陣。

3.2 超邊權重計算

超圖里的每一條邊代表一個句子，句子的權重可以由這個句子的主題信息密度來衡量。對于詞w∈V，假設詞w所包含的主題信息為T（w），則句子的主題信息密度的計算方式如式（4）所示。

3.3 基于邊的隨機游走

我們可以把漫游者在超圖上的隨機游走過程看作是在傳統圖上游走的一個推廣，在傳統的圖上，漫游者沿著邊的游走可以看作是選擇與該邊相連的點，然后轉移到另外一條邊上。但是，在超圖上一條邊可能與多個點相連，因此我們需要一般化這個過程。漫游者在超圖上游走分為兩步：第一步，漫游者從當前所在超邊ei上隨機選擇一個點v；第二步，漫游者以w（ej）與包含v的所有邊的權重之和的比值作為概率選擇邊ej，且滿足v∈ei∩ej。ei到ej的轉移概率，計算方法如式（5）所示。

矩陣表示形式為：

De為公式（3）中的超邊的度對角矩陣，HT是關聯矩陣H的轉置矩陣，行為邊，列為點。Dv是公式（2）中的帶權的度對角矩陣。We為邊權重對角矩陣，對角線上的值為對應邊的權重。為了避免回路，我們把Pe中的對角線元素置為0，然后再把Pe歸一化，使每一行元素之和為1。

3.4 基于點的隨機游走

基于點的隨機游走過程與基于邊的隨機游走過程類似，漫游者的游走過程也分為兩步：第一步，漫游者從與當前所在點vi關聯的所有邊中，以w（e）與包含vi的所有邊的權重之和的比值作為概率選擇一條邊e；第二步，漫游者從e上隨機選擇一個點vj，且滿足vi，vj∈e。vi到vj的轉移概率，計算方法如式（7）所示。

矩陣表示形式為：

De為公式（3）中的超邊度對角矩陣，HT是關聯矩陣H的轉置矩陣，行為邊，列為點。Dv是公式（2）中的有權的度對角矩陣。We為邊權重對角矩陣，對角線上的值為對應邊的權重。為了避免回路，我們把Pv中的對角線元素置為0，然后再把Pv歸一化，使每一行元素之和為1。

我們采用PageRank方法來進行隨機游走，→v為待排序的點向量，α為阻尼系數，具體如式（8）所示。

3.5 協同抽取方法

我們用兩個列向量u＝［u（si）］n×1和v＝［v（ti）］m×1分別表示一篇特定文章中句子和詞的重要性得分。α的值設為0.85。u和v的所有元素的初值分別設為1／n和1／m，即初始時每個句子包含的主題信息密度為1／n，每個詞包含的主題信息為1／m。我們迭代交替執行以下兩步，直至u和v的值收斂。

1.根據v的值，我們可以計算Dv，We，然后用公式（9）計算句子重要性得分。

2.根據u的值，我們可以重新計算Dv，We，然后用公式（10）計算詞重要性得分。

u（n）和v（n）分別表示句子得分向量和詞得分向量在第n次迭代的計算結果。如果相鄰兩次迭代u（n）和u（n－1），v（n）和v（n－1）對應位置的元素差值的絕對值小于某固定閾值（本文設為0.0001），則停止迭代，同時我們得到了句子和詞的最終得分，我們抽取得分最高的若干句子生成摘要，取得分最高的若干詞作為文章的關鍵詞。

4 實驗與分析

4.1 摘要評價

4.1.1 數據集及評價標準

實驗語料采用NLPCC 2015面向微博的新聞文本摘要任務數據集。該數據集包括250篇來自新浪的新聞文本，包括原始文本和已分句的文本，本實驗采用后者。

評價方法采用ROUGE［18］工具（1.5.5版），此工具被DUC作為標準評測工具，在歷年的自動文本摘要任務中被廣泛使用。它通過計算待評價摘要與標準摘要在n－gram上的重疊度來衡量機器生成摘要的質量。ROUGE可以分別計算1、2、3、4－gram和最大共現子序列ROUGE－L的分數。在這些分數中，基于1－gram的ROUGE分數（ROUGE－1）被公認為和人工評價的結果最接近［18］。在表1中展示了ROUGE－1、ROUGE－2、ROUGE－3、ROUGE－4和ROUGE－L。另外由于摘要長度限定在140字以內，所以我們在評價時使用了“－l”命令。

4.1.2 評價結果

我們選取了四個baseline與本文提出的HBCE方法比較，這四個方法是：HBR（Hyperedge－based Ranking）、GBIR（Graph based Iterative Reinforcement）、SentenceRank和Log likelihood。HBR［19］是基于超邊的排序方法，該方法首先使用Topic Signatures［5］方法找出文章的主題詞，每個主題詞權重為1，非主題詞權重為0，用公式（4）計算句子權重，然后用基于邊的隨機游走算法（即公式（5）～（6））計算句子的最終得分。GBIR［3］方法是基于圖的迭代強化方法，它在計算詞與詞之間的語義相似性用到的方法是基于語料的滑動窗口法，窗口大小設置為5，把250篇新聞文本作為背景語料。SentenceRank［1］方法是Mihalcea和Tarau在2004年提出來的，該方法利用句子與句子之間的關系來對所有句子排序。Log Likelihood方法是將HBR方法計算出帶權重的句子，按權重大小排序，這里的句子權重為主題詞密度。評價結果見表1。

表1 摘要評價結果

4.1.3 結果分析

從實驗結果來看，本文提出的HBCE方法在所有ROUGE指標上都優于其他方法，證明了此方法的有效性。HBR方法在沒有利用詞的強化作用下，僅利用基于超邊的隨機游走算法，其結果比SentenceRank方法要好，證明句子與詞之間的高階關系是一個十分重要的關系，但是基于圖的排序方法中無法表示這種關系。基于圖的迭代強化方法GBIR和利用句子之間關系的圖排序算法SentenceRank方法效果相當。Log Likelihood按照句子主題詞密度給句子排序，從表1可以看出這個方法是有效的，同時證明我們在HBCE方法中采用主題信息密度作為句子的權重是合理的。

4.2 關鍵詞評價

4.2.1 評價方法

實驗語料采用NLPCC 2015面向微博的新聞文本摘要任務數據集中的前30篇新聞文本，人工標注出每篇文本中的關鍵詞，每篇最多標注10個關鍵詞。對這30篇文本，利用本文提出的方法，每篇文本提取出10個得分最高的詞。我們通過計算候選詞在標注詞上的正確率P，召回率R以及F值（F＝2PR／（P＋R））來評價方法的有效性。

4.2.2 評價結果

在實驗中，分別用GBIR、WordRank和Topic Signatures為每一篇文檔提取出10個候選詞來與本文的方法作對比。WordRank［1］方法是Mihalcea和Tarau在2004年提出來的，該方法利用詞與詞之間的共現關系來對所有詞排序。Topic Signatures［5］方法提取每篇新聞文本關鍵詞的時候，把除去這篇文本的剩下249篇新聞文本作為背景語料。評價結果見表2。

表2 關鍵詞評價結果

4.2.3 結果分析

從表2中的對比實驗結果可以看出，本文的方法比只考慮詞與詞之間關系的WordRank方法效果要好，但是和基于背景語料的方法相比還存在一定的差距，如果從計算的時間復雜度和是否使用背景語料來綜合考慮，本文的方法優勢較為明顯。

5 總結與展望

本文提出了一種基于超圖的協同抽取方法HBCE，可以同時對一篇文檔生成摘要和抽取出關鍵詞，該方法以句子作為超邊，以詞作為結點構建超圖，在一個統一的超圖模型下同時利用句子與詞之間的高階信息來生成摘要和關鍵詞。最后的評價結果表明本文的方法在文本摘要上的效果要優于其他基于圖的方法，同時優于僅考慮句子與句子間關系而忽視了詞與句子間潛在的高階關系的方法，關鍵詞抽取的評價結果也優于僅考慮詞與詞之間關系的方法，雖然與基于語料或知識庫的方法相比還存在一定的差距，但是本方法的綜合性能優勢較為明顯。下一步我們打算把該方法應用于英文數據集，以驗證本文方法的有效性。除此之外，本文在進行迭代的過程中，無論是基于點的隨機游走過程還是基于邊的隨機游走過程，都是以一個固定的概率在超邊上選擇點，下一步我們將驗證以該詞的權重占句子權重的比值作為概率來選擇點的有效性。

［1］ Mihalcea R，Tarau P.TextRank：Bringing order into texts［C］／／Proceedings of Association for Computational Linguistics.2004.

［2］ Erkan G，Radev D R.LexPageRank：Prestige in Multi－Document Text Summarization［C］／／Proceedings of EMNLP.2004，4：365－371.

［3］ Wan X，Yang J，Xiao J.Towards an iterative reinforcement approach for simultaneous document summarization and keyword extraction［C］／／Proceedings of Annual Meeting－Association for Computational Linguistics.2007，45（1）：552.

［4］ Hovy E，Lin C Y.Automated text summarization and the SUMMARIST system［C］／／Proceedings of a workshop on held at Baltimore，Maryland：October 13－15，Association for Computational Linguistics，1998：197－214.

［5］ Lin C Y，Hovy E.The automated acquisition of topic signatures for text summarization［C］／／Proceedings of the 18th Conference on Computational Linguistics－Volume 1.Association for Computational Linguistics，2000：495－501.

［6］ Nomoto T，Matsumoto Y.A new approach to unsupervised text summarization［C］／／Proceedings of the 24th Annual international ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2001：26－34.

［7］ Kupiec J，Pedersen J，Chen F.A trainable document summarizer［C］／／Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，1995：68－73.

［8］ Conroy J M，O'leary D P.Text summarization via hidden markov models［C］／／Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2001：406－407.

［9］ Carbonell J，Goldstein J.The use of MMR，diversitybased reranking for reordering documents and producing summaries［C］／／Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，1998：335－336.

［10］ Gong Y，Liu X.Generic text summarization using relevance measure and latent semantic analysis［C］／／Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.ACM，2001：19－25.

［11］ Salton G，Buckley C.Term－weighting approaches in automatic text retrieval［J］.Information processing ＆management，1988，24（5）：513－523.

［12］ Ercan G，Cicekli I.Using lexical chains for keyword extraction［J］.Information Processing ＆Management，2007，43（6）：1705－1714.

［13］ Turney P D.Learning algorithms for keyphrase extraction［J］.Information Retrieval，2000，2（4）：303－336.

［14］ Wu Y B，Li Q，Bot R S，et al.Domain－specific keyphrase extraction［C］／／Proceedings of the 14th ACM International Conference on Information and Knowledge Management.ACM，2005：283－284.

［15］ Witten I H，Paynter G W，Frank E，et al.KEA：Practical automatic keyphrase extraction［C］／／Proceedings of the 4th ACM Conference on Digital Libraries.ACM，1999：254－255.

［16］ Mihalcea R，Csomai A.Wikify：linking documents to encyclopedic knowledge［C］／／Proceedings of the 16th ACM conference on Conference on Information and Knowledge Management.ACM，2007：233－242.

［17］ Grineva M，Grinev M，Lizorkin D.Extracting key terms from noisy and multitheme documents［C］／／Proceedings of the 18th International Conference on World wide web.ACM，2009：661－670.

［18］ Lin C Y，Hovy E.Automatic evaluation of summaries using n－gram co－occurrence statistics［C］／／Proceedings of the 2003Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology－Volume 1.Association for Computational Linguistics，2003：71－78.

［19］ Bellaachia A，Al－Dhelaan M.Multi－document Hyperedge－based Ranking for Text Summarization［C］／／Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management.ACM，2014：1919－1922.