基于改進(jìn)K-means聚類與圖模型相結(jié)合的多文本自動(dòng)文摘研究

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

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

基于改進(jìn)K-means聚類與圖模型相結(jié)合的多文本自動(dòng)文摘研究

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

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

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

0 引言

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

自動(dòng)文摘按摘要方式可分為兩類，生成式和抽取式[1]。生成式需要根據(jù)原文的內(nèi)容進(jìn)行概括、簡(jiǎn)化、合成，以此產(chǎn)生原文中未出現(xiàn)的詞組。例如，“他們?nèi)ブ袊?guó)的火洲”，可縮寫為“他們?nèi)ネ卖敺?。因?yàn)樾枰^高的技術(shù)要求，這種方式目前還處于起步階段[2]；然而抽取式對(duì)于機(jī)器來(lái)說(shuō)較容易實(shí)現(xiàn)，一般提取原文能體現(xiàn)主題的句子形成文摘。這些通常制定一些特征，對(duì)句子進(jìn)行權(quán)重排序，以權(quán)重高的句子為文摘句進(jìn)行輸出[3]。本文研究的主要內(nèi)容是不同主題下的多文本抽取式摘要。

1 相關(guān)研究

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

1.1 基于聚類的方法

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

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

1.2 基于圖的方法

Furu Wei[6]在2010年開(kāi)發(fā)了一個(gè)通過(guò)靈敏相似度來(lái)構(gòu)建圖的自動(dòng)摘要。以往的查找句子方法中，只考慮句子的語(yǔ)義關(guān)系，但在該方法中，不僅查詢到句子的結(jié)點(diǎn)關(guān)系，而且還考慮到了句子與句子之間關(guān)系。

1.3 方法總結(jié)

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

2 聚類與圖模型

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

2.1 文本表示以及特征提取

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

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

2.2 改進(jìn)的K-means

由于經(jīng)典劃分聚類K-means聚類的局部最優(yōu)缺點(diǎn)導(dǎo)致聚類結(jié)果有偏差

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

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

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

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

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

Step4：重復(fù)步驟2和3直到質(zhì)心不再移動(dòng)，類別不再合并，改進(jìn)的K-means算法停止。

2.3 改進(jìn)的圖模型建立

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

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

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

常用句子連接詞：因果關(guān)系的“因?yàn)椤保八浴?，“因此”等；時(shí)間關(guān)系的“之前”，“之后”，“現(xiàn)在”等；對(duì)比關(guān)系的“相比于”等；轉(zhuǎn)折關(guān)系的“雖然”，“然而”；遞進(jìn)關(guān)系的“還有”，“此外”等；指示性短語(yǔ)的“綜上所述”、“文本宗旨”。

2.4 LexRank算法

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

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

2.5 抽取句子并生成摘要

3 結(jié)果評(píng)價(jià)及分析

3.1 文摘評(píng)價(jià)

目前，通過(guò)提取句子的自動(dòng)文摘的評(píng)價(jià)方法大概有兩類:內(nèi)部評(píng)價(jià)方法，它可以對(duì)自動(dòng)文摘的質(zhì)量進(jìn)行分析，一般使用準(zhǔn)確率、召回率、F值作為測(cè)試指標(biāo)；外部評(píng)價(jià)方法，它通過(guò)完成一個(gè)特定任務(wù)的效果來(lái)評(píng)價(jià)文摘系統(tǒng)。文中采用內(nèi)部摘要評(píng)測(cè)方法ROUGE值，比較實(shí)驗(yàn)方法生成文摘和人工生成文摘的相似度進(jìn)行評(píng)測(cè)。

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

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

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

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

為了能與自動(dòng)文摘作更好的對(duì)比，本實(shí)驗(yàn)召集了五名成績(jī)良好的碩士研究生作為專家做人工摘要，他們按照自己的理解做出文摘。

3.3 實(shí)驗(yàn)結(jié)果和分析

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

表2 TF-IDF空間向量模型與sentence2vec空間向量模型對(duì)比

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

文摘的壓縮比對(duì)文摘質(zhì)量也會(huì)產(chǎn)生一定的影響，為此本文在壓縮比上做了實(shí)驗(yàn)對(duì)比，已選擇更好的文摘句。表3為本文方法和普通摘要分別在壓縮率10%和20%下進(jìn)行ROUGE-1的對(duì)比評(píng)測(cè)。

表3 壓縮率10%和20%的ROUGE-1實(shí)驗(yàn)評(píng)測(cè)對(duì)比

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

4 結(jié)語(yǔ)

本文使用改進(jìn)的K-means聚類劃分不同文本主題，改進(jìn)句子相似度計(jì)算并建立圖模型使用圖排序算法LexRank生成摘要，同時(shí)對(duì)不同因素下的句子進(jìn)行加權(quán)結(jié)合最大邊界相關(guān)算法去除摘要句的冗余,實(shí)驗(yàn)表明此方法生成的摘要更接近人工生成的摘要。但是，因?yàn)橹形恼Z(yǔ)言的特殊性，結(jié)構(gòu)復(fù)雜，歧義繁多，所以加大了摘要的生成難度，比如圖排序或聚類時(shí)因句子歧義導(dǎo)致錯(cuò)誤分配句子的權(quán)重或類別，所以效果還不是很好。所以接下來(lái)還需要對(duì)中文的語(yǔ)義等比較復(fù)雜的部分進(jìn)行分析，例如句子多義性，以及更復(fù)雜的組合句子以達(dá)到更好的文摘效果。

[1]曹洋,成穎,裴雷.基于機(jī)器學(xué)習(xí)的自動(dòng)文摘研究綜述[J].圖書情報(bào)工作,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-)，高級(jí)實(shí)驗(yàn)師，碩士

郭竹為(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.

新疆自然科學(xué)基金項(xiàng)目（No.2014211A016）

趙美玲(1989-)，女，山東聊城人，碩士研究生，研究方向?yàn)檎Z(yǔ)義Web

劉勝全(1965-)，男，教授，碩士，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)、語(yǔ)義Web服務(wù)、分布式人工智能

2017-03-31

2017-06-10

1007-1423（2017）17-0026-05

10.3969/j.issn.1007-1423.2017.17.005

自動(dòng)文摘；多文本；聚類；圖模型

Automatic Summarization;Multi Text;Clustering;Graph Model