趙美玲，劉勝全,2，劉艷，郭竹為，符賢哲

（1.新疆大學信息科學與工程學院，烏魯木齊 830046；2.新疆大學網(wǎng)絡與信息中心，烏魯木齊 830046；3.新疆大學軟件學院，烏魯木齊 830046）

基于改進K-means聚類與圖模型相結合的多文本自動文摘研究

趙美玲1，劉勝全1,2，劉艷1，郭竹為1，符賢哲3

（1.新疆大學信息科學與工程學院，烏魯木齊 830046；2.新疆大學網(wǎng)絡與信息中心，烏魯木齊 830046；3.新疆大學軟件學院，烏魯木齊 830046）

目前多文檔文摘大多數(shù)對同一主題下的文本進行摘要，不同主題下的文本自動文摘的研究相對較少。已有的多文本自動摘要或多或少有不足，使用聚類方法存在初始質心k無法確定以及構造圖模型時句子相似度計算沒有考慮語義特征等現(xiàn)象。對不同主題的多文檔進行主題劃分，然后依據(jù)主題進行多文本自動摘要，針對以上多文檔文摘方法存在的不足，改進K-means聚類、句子相似度計算等缺陷，提出改進K-means聚類和圖模型相結合的方法。通過實驗表明，該方法的準確率高于基于聚類或者基于圖排序的算法。

0 引言

信息時代飛速發(fā)展，使得網(wǎng)絡文本越來越多，如何更準確地、快速地掌握文本內容是當前研究重點。摘要是一種能保留文本本質特征及文本可讀性同時減少其大小的一種方法，然而文獻數(shù)目的指數(shù)級增長導致手動處理方法不現(xiàn)實。對于這種情況，使用計算機來自動處理成為熱門，由此產生了自動文摘?，F(xiàn)今的網(wǎng)絡信息多以主題為主，獲得不同主題下的多個文本摘要是很有必要性的。

自動文摘按摘要方式可分為兩類，生成式和抽取式[1]。生成式需要根據(jù)原文的內容進行概括、簡化、合成，以此產生原文中未出現(xiàn)的詞組。例如，“他們去中國的火洲”，可縮寫為“他們去吐魯番”。因為需要較高的技術要求，這種方式目前還處于起步階段[2]；然而抽取式對于機器來說較容易實現(xiàn)，一般提取原文能體現(xiàn)主題的句子形成文摘。這些通常制定一些特征，對句子進行權重排序，以權重高的句子為文摘句進行輸出[3]。本文研究的主要內容是不同主題下的多文本抽取式摘要。

1 相關研究

文本摘要是提取多層次的粒度，例如最小單位、關鍵字、詞、句子或句子的集合，在大多數(shù)的研究中，旨在句子或段落的提取，因為列表或組包含了非常低的信息量，而段落和句子可以涵蓋信息內容以及文本摘要的方法[4]，目前比較流行的抽取式多文檔文摘方法有基于聚類、圖模型等。

1.1 基于聚類的方法

聚類算法的核心是有效地利用聚類算法對大量未標注語料進行快速劃分。聚類也取決于簇的質心，簇的數(shù)量和類型的應用（數(shù)據(jù)新聞、法律等）?；诰垲惖姆椒ㄖ饕A處理任務、聚類和匯總生成。

Xiao-Chen Ma[5]在2009年，說明了摘要系統(tǒng)中，通過建立向量空間模型（VSM）、構建相似矩陣、K-means聚類生產摘要，最后改進的MMR（最大邊緣相關）生成最終摘要。

1.2 基于圖的方法

Furu Wei[6]在2010年開發(fā)了一個通過靈敏相似度來構建圖的自動摘要。以往的查找句子方法中，只考慮句子的語義關系，但在該方法中，不僅查詢到句子的結點關系，而且還考慮到了句子與句子之間關系。

1.3 方法總結

一般使用K-means聚類進行多文檔摘要時，初始質心以及k值無法很好的確定，可能產生局部最優(yōu)的缺陷；構造圖模型時大依據(jù)句子之間的相似度構造圖，沒有結合句子的語義信息；生成的文摘句后冗余處理時有學者結合了主題但是沒有結合語義特征，有學者結合語義但是沒考慮主題。本文對K-means聚類[7]進行改進生成主題，然后結合改進的句子相似度計算方法構造圖模型以生成最終摘要。解決了聚類的局部最優(yōu)缺陷，構建圖模型句子相似度沒有語義的弊端。

2 聚類與圖模型

一篇文章一般會包含對一個主旨進行描述的多個句子，句子和句子之間的相似度比較高。而本文的主要任務就是找到最主要的句子來代表本文的主旨。對于多文本的摘要，根據(jù)不同主題把多文本進行劃分，然后在分別對每個類別中找出最能代表各主題的句子以生成摘要。

2.1 文本表示以及特征提取

我們首先對所有文本進行預處理，如分詞（ICT?CLAS分詞系統(tǒng)）、去停用詞等，并建立空間向量。常用空間向量模型有TF、TF-IDF等方法，但是這些方法沒有考慮句子與句子之間、詞與詞之間的語義關系，如果能在聚類過程考慮到句子之間的語義關系，聚類效果會更加理想。本文使用sentence2vec[8]的Skip-gram模型完成句子向量的建立，它是一種低維度帶有淺層深度學習的向量工具，對句子做語義分析且生成更易于聚類的分析的空間向量模型。此外工具中所使用的Skip-gram模型是通過詞來尋找上下文語境并生成相對應的向量。設句子向量為，為句子i的向量，m為生成句子對應向量的維數(shù)。

文章中動詞和名詞對主題內容的影響較大，有的文章標題可以概括文章內容的作用。本文提取每篇文章內容以及標題中的動詞、名詞進行去重、過濾同義詞等操作，選取一定詞頻的詞語并結合詞語的權重（句子中每個詞對應的向量）若為標題中的動名詞則權重加1，遵循Top n原則，選取前n個作為特征詞。這n個特征詞中動詞或者名詞數(shù)量最多的句子作為初始質心k。

2.2 改進的K-means

由于經典劃分聚類K-means聚類的局部最優(yōu)缺點導致聚類結果有偏差

，尤其數(shù)據(jù)量較大較復雜的語料更容易體現(xiàn)。對此，本文對此做了如下改進。首先初始質心是根據(jù)文本特征詞來設定的，這使得初始設定的質心和聚類結果更相近，更具有目的性；其次k值的設定是K-means聚類的一大難題，本文改進算法使用動態(tài)修正k值的方法由算法在計算的過程中得到最合適的類別數(shù)目k。該算法描述如下：

Input：文檔d，作為初始質心文檔d的特征詞，生成的聚類簇數(shù)k。Output：不同主題的文本

Step1：對文檔d提取特征詞，其中設定含有特征詞的句子為聚類的初始質心，既為k；

Step2：依次選取文檔d中的句子同各個質心計算距離，選定最小距離并放入；

Step3：每當劃分完一個句子，則重新計算當前類別的質心，并計算此質心同其他質心的距離，若兩質心的距離足夠小，則說明這兩個類別相似，需要合并，獲得更完整的類，返回步驟2；

Step4：重復步驟2和3直到質心不再移動，類別不再合并，改進的K-means算法停止。

2.3 改進的圖模型建立

根據(jù)已劃分好的類別分別建立各個主題下的圖模型[9]G={ }

V,E,V是頂點，E是圖的邊。每個圖模型的結點即為文本的句子，如果句子和句子之間相似度達到提前設定的閾值，那么這兩個頂點用一條邊鏈接。文中在計算句子相似度是以聚類質心為核心，每個句子都要與質心計算，保證聚類主題內容的覆蓋度以及減少冗余句。這里給出計算邊的權重計算公式：

由于摘要句大部分都是肯定句，并且句子與句子含有一些特殊的連接詞或者指示性短語，如影響結果、影響前后的連接詞，這種關系的句子一般具有較低的相似度；表示目的的指示性短語如“綜上所述”、“文章宗旨”，這種情況下句子的相似度就會增大。計算公式如下：

常用句子連接詞：因果關系的“因為”，“所以”，“因此”等；時間關系的“之前”，“之后”，“現(xiàn)在”等；對比關系的“相比于”等；轉折關系的“雖然”，“然而”；遞進關系的“還有”，“此外”等；指示性短語的“綜上所述”、“文本宗旨”。

2.4 LexRank算法

下面使用LexRank[10]算法對上述通過相似度計算的圖模型進行句子排序。LexRank算法也是現(xiàn)在圖模型的一個較常用的算法，它主要由PageRank算法演變而來。此算法認為如果一個句子和其他句子很相似，那么這個句子就較為重要。圖的各個節(jié)點的排序計算如下：

其中，p（u）表示頂點u的顯著度，adj（u）表示頂點u的鄰接頂點的集合，d表示從頂點U的當前狀態(tài)以（1-d）的概率跳到U的某個鄰居的當前狀態(tài)，以d的概率跳到無向圖中任意一個頂點的當前狀態(tài)，N表示無向圖中的頂點的總數(shù)目，d的值一般選為0.2。式（4）轉化為矩陣形式:

2.5 抽取句子并生成摘要

3 結果評價及分析

3.1 文摘評價

目前，通過提取句子的自動文摘的評價方法大概有兩類:內部評價方法，它可以對自動文摘的質量進行分析，一般使用準確率、召回率、F值作為測試指標；外部評價方法，它通過完成一個特定任務的效果來評價文摘系統(tǒng)。文中采用內部摘要評測方法ROUGE值，比較實驗方法生成文摘和人工生成文摘的相似度進行評測。

Lin Chin-Yew等人[11]提出ROUGE值來評價文摘質量，2004年在DUC上正式使用的。它的原理：通過比對自動文摘和人工文摘之間相同的單詞數(shù)目來評價。同時ROUGE準則由不同程度的方法組成，常用的有ROUGE-N,ROUGE-L,ROUGE-W等。這里給出ROUGE-N計算公式：

其中，n代表n-gram的長度，Countmatch代表同時出現(xiàn)在機器摘要和人工文摘中的n-gram的最大數(shù)目，RfSum是文中實驗的人工生成摘要。

3.2 實驗數(shù)據(jù)集

文中采用爬取工具爬取新聞網(wǎng)頁，總共獲取了250篇文章作為語料數(shù)據(jù)集，經聚類處理后分別為體育、政治、醫(yī)療、計算機類以及經濟等5個主題。

為了能與自動文摘作更好的對比，本實驗召集了五名成績良好的碩士研究生作為專家做人工摘要，他們按照自己的理解做出文摘。

3.3 實驗結果和分析

實驗在1臺PC（2.66 GHz CPU，2 GB內存）上進行測試，實驗平臺是Eclipse和Python。文中做空間向量采用含有語義信息的sentence2vec模型，這種模型較常用的TF-IDF模型更能表達出詞與詞以及句子與句子的語義信息并且可以降低向量的維數(shù)災難。為了證明該模型的效果，與TF-IDF模型做了實驗對比。對比結果如下表：

表2 TF-IDF空間向量模型與sentence2vec空間向量模型對比

因sentence2vec模型的維度可以人為定義，大于50維的向量進行聚類結果基本趨于穩(wěn)定。TD-IDF的向量會根據(jù)語料大小來生成，一般語料越大，向量維度越大。從表中可以看出對同等語料生成的向量TFIDF的維度遠遠大于sentence2vec模型生成的向量維度，說明后者使用很少的維度向量便能表達出所需的句子向量，更便于后續(xù)工作。此外生成時間因sen?tence2vec模型是迭代生成的向量空間，語料越大，維度越大，所需要生成的時間也更多。

文摘的壓縮比對文摘質量也會產生一定的影響，為此本文在壓縮比上做了實驗對比，已選擇更好的文摘句。表3為本文方法和普通摘要分別在壓縮率10%和20%下進行ROUGE-1的對比評測。

表3 壓縮率10%和20%的ROUGE-1實驗評測對比

從表中可以看到，本文算法生成自動文摘有較好的效果。相比于其他類文本，體育和經濟類的效果更佳，在10%壓縮率下準確率分別有8.6%和9.74%以及20%壓縮率下6.61%和10.86%的提高。最后在壓縮率為10%時，所有文本平均準確率提高了5.598%，在壓縮率20%時，所有文本平均準確率提高了6.01%。

4 結語

本文使用改進的K-means聚類劃分不同文本主題，改進句子相似度計算并建立圖模型使用圖排序算法LexRank生成摘要，同時對不同因素下的句子進行加權結合最大邊界相關算法去除摘要句的冗余,實驗表明此方法生成的摘要更接近人工生成的摘要。但是，因為中文語言的特殊性，結構復雜，歧義繁多，所以加大了摘要的生成難度，比如圖排序或聚類時因句子歧義導致錯誤分配句子的權重或類別，所以效果還不是很好。所以接下來還需要對中文的語義等比較復雜的部分進行分析，例如句子多義性，以及更復雜的組合句子以達到更好的文摘效果。

[1]曹洋,成穎,裴雷.基于機器學習的自動文摘研究綜述[J].圖書情報工作,2014,58（18）:122-130.

[2]Mani I,Maybury M T.Advances in Automatic Text Summarization[M].Cambridge：MIT Press，1999．

[3]Mani I,Bloedorn E.Machine Learning of Generic and User-focused Summarization[C].Proceedings of the Fifteenth National/tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence.American Association for Artificial Intelligence,1998:821-826.

[4]Meena Y K,Jain A,Gopalani D.Survey on Graph and Cluster Based Approaches in Multi-document Text Summarization[C].Recent Advances and Innovations in Engineering（ICRAIE）,2014.IEEE,2014:1-5.

[5]Ma X C,Yu G B,Ma L.Multi-Document Summarization Using Clustering Algorithm[C].Intelligent Systems and Applications,2009.ISA 2009.International Workshop on.IEEE,2009:1-4.

[6]Wei F,Li W,Lu Q,et al.A Document-Sensitive Graph Model for Multi-Document Summarization[J].Knowledge&Information Systems,2010,22（2）:245-259.

[7]MacQueen,J.Some Methods for Classification and Analysis of MultiVariate Observations[C].Berkeley Symposium on Math.1967:281-297.

[8]Le Q V,Mikolov T.Distributed Representations of Sentences and Documents[J].Eprint Arxiv,2014,4:1188-1196.

[9]Khan A,Salim N,Kumar Y J.Genetic Semantic Graph Approach for Multi-Document Abstractive Summarization[C].Fifth International Conference on Digital Information Processing and Communications.IEEE,2015.

[10]Erkan G,D R.Radev：―Lexrank：Graph-based centrality as Salience in Text Summarization[J].Jair,2004,22:2004.

[11]Lin Chin-Yew．Rouge：A Package for Automatic Evaluation of Summaries[C].Text Summarization Branches Out：Proceedings of the ACL-04 Workshop.Barcelona：ACL，2004：74-81．

劉艷(1969-)，高級實驗師，碩士

郭竹為(1987-)，碩士研究生

符賢哲(1990-)，碩士研究生

Research on Multi Text Automatic Summarization Based on the Combination Of Improved K-means Clustering and Graph Model

ZHAO Mei-ling1,LIU Shen-quan1,2,LIU Yan1,GUO Zhu-wei1,FU Xian-zhe3
（1.Colleges of Information Science and Engineering,Urumqi 830046；2.Network and Information Technology Center,Urumqi 830046；3.School of Software,Xinjiang University,Urumqi 830046）

At present,most of the abstracts of the same subject are mostly based on multi document summarization,and the research on text automatic summarization under different topics is relatively few.The existing multi text automatic summarization is more or less inadequate,and the clustering method is used to determine the k of the initial centroid and the sentence similarity without considering the semantic feature when constructing the graph model.First divides different topics for topic segmentation,and then makes multi automatic text summariza?tion based on the theme,according to the problems above multi document summarization method,makes some improvement in K-means clustering,sentence similarity calculation and other defects,puts forward methods of improving K-means clustering and graph model com?bination.Experiments show that the accuracy of the proposed method is higher than that based on clustering or graph sorting algorithm.

新疆自然科學基金項目（No.2014211A016）

趙美玲(1989-)，女，山東聊城人，碩士研究生，研究方向為語義Web

劉勝全(1965-)，男，教授，碩士，研究方向為計算機網(wǎng)絡、語義Web服務、分布式人工智能

2017-03-31

2017-06-10

1007-1423（2017）17-0026-05

10.3969/j.issn.1007-1423.2017.17.005

自動文摘；多文本；聚類；圖模型

Automatic Summarization;Multi Text;Clustering;Graph Model