密度峰值算法在中文自動(dòng)文摘中的應(yīng)用研究

李明麗，孫連英，邢 邗，石曉達(dá)

（北京聯(lián)合大學(xué)信息學(xué)院，北京 100101）

?

密度峰值算法在中文自動(dòng)文摘中的應(yīng)用研究

李明麗，孫連英，邢 邗，石曉達(dá)

（北京聯(lián)合大學(xué)信息學(xué)院，北京 100101）

［摘 要］隨著自然語言處理技術(shù)的不斷創(chuàng)新，自動(dòng)文摘的質(zhì)量得到顯著提高。面向科技成果文檔的中文自動(dòng)文摘成為研究熱點(diǎn)，具有一定的應(yīng)用價(jià)值。把聚類算法應(yīng)用到自動(dòng)文摘中，選取聚類中心的思想對(duì)文摘去冗余具有一定意義。結(jié)合密度峰值算法，設(shè)計(jì)實(shí)現(xiàn)了面向科技成果文檔的中文自動(dòng)文摘系統(tǒng)。實(shí)驗(yàn)結(jié)果表明：應(yīng)用密度峰值算法有利于文摘的冗余處理，具有借鑒意義。

［關(guān)鍵詞］自動(dòng)文摘；密度峰值；冗余處理

互聯(lián)網(wǎng)信息的指數(shù)級(jí)增長(zhǎng)，使得自動(dòng)文摘的實(shí)用價(jià)值不斷提高。隨著文本處理算法的創(chuàng)新，自動(dòng)文摘的質(zhì)量不斷提高，自動(dòng)提取文摘有利于科技成果的轉(zhuǎn)化推廣。自動(dòng)文摘從文摘產(chǎn)生的形式上看，可分為抽取式文摘和生成式文摘。抽取式文摘通過對(duì)文檔原句打分，抽取文檔原句組成文摘。生成式文摘通過重組句子或填充文摘模板來生成文摘［1］。生成式文摘的相關(guān)技術(shù)仍不夠成熟，較難應(yīng)用。從文本數(shù)量上看，可分為單文本文摘和多文本文摘。抽取式文摘從句子的權(quán)值計(jì)算方法上來看，可分為句子獨(dú)立打分式和通過句子之間關(guān)系打分式兩種方法。應(yīng)用于自動(dòng)文摘的方法有圖模型、語義分析、機(jī)器學(xué)習(xí)和聚類等。本文主要研究的是聚類算法在自動(dòng)文摘系統(tǒng)中的應(yīng)用。

應(yīng)用到自動(dòng)文摘中的聚類算法主要有層次聚類、K均值聚類和密度聚類算法等。層次聚類［2］算法在自動(dòng)文摘中的應(yīng)用比較簡(jiǎn)單，不需要給定文檔的聚類數(shù)目，但是一個(gè)對(duì)象被聚類后不可再做調(diào)整，可能造成較大的聚類偏差。K均值聚類的經(jīng)典算法為K-means算法，步驟如下:1）任意選擇K個(gè)句子作為初始聚類中心；2）分別計(jì)算剩余句子與每個(gè)聚類的中心距離，根據(jù)最小距離重新對(duì)句子進(jìn)行劃分；3）重新計(jì)算每個(gè)新類的聚類中心，即每類中全部對(duì)象的均值；4）每當(dāng)滿足一定條件，如均方差函數(shù)開始收斂時(shí)，則算法終止；否則返回步驟2。初始聚類中心的個(gè)數(shù)需要提前給定，聚類中心可采用虛擬點(diǎn)。它的局限在于受限于K值，難以發(fā)現(xiàn)自然聚類，聚類中心的個(gè)數(shù)受限，并且對(duì)噪聲較敏感。K-medoids算法與K-means算法的主要區(qū)別在于聚類中心的選擇方法，K-medoids算法的時(shí)間復(fù)雜度較低。K-mesns算法作為聚類的經(jīng)典算法，經(jīng)過長(zhǎng)期的應(yīng)用發(fā)展，在初始聚類中心的選擇上，有很多研究人員進(jìn)行了不同的探索。應(yīng)用到自動(dòng)文摘中的密度聚類算法主要是DBSCAN［3］算法，密度大的點(diǎn)向外擴(kuò)展聚類。

將聚類算法應(yīng)用到自動(dòng)文摘系統(tǒng)的實(shí)例有: 2001年，文獻(xiàn)［4］將聚類思想應(yīng)用到自動(dòng)文摘提取中，結(jié)合層次聚類算法與K-means算法，將文本聚類成若干段落類，選取與文獻(xiàn)主題相關(guān)的類，進(jìn)而提取文摘；2006年，劉海濤等采用K-medoids算法，根據(jù)詞頻統(tǒng)和位置信息形成關(guān)鍵詞向量，將文本進(jìn)行段落聚類提取文摘［5］；2007年，郭慶琳等將層次聚類和K-means分別應(yīng)用到自動(dòng)文摘［6］中，實(shí)現(xiàn)了面向塑料行業(yè)的中文自動(dòng)文摘系統(tǒng)；2009年，分別采用層次聚類算法和DBSCAN算法，將句子進(jìn)行聚類提取文摘［7］；2015年，基于改進(jìn)K-means［8］的動(dòng)態(tài)文摘，在初始聚類中心的選取上進(jìn)行改進(jìn)，以句子為單位，實(shí)現(xiàn)了根據(jù)時(shí)間更新的動(dòng)態(tài)文摘提取。

科技成果類文檔，主題明確、文章結(jié)構(gòu)比較規(guī)范，把句子間的余弦相似度看做句子之間的距離衡量標(biāo)準(zhǔn)，采用密度峰值算法選取句子的聚類中心，可以更好地提取文摘句。

1　密度峰值算法

2014年6月，在Science上發(fā)表的密度峰值算法［9］，兼顧密度聚類兩要素:密度和距離，采用二維平面提取聚類中心。該算法選取方法獨(dú)到、思維新穎、結(jié)果直觀。密度峰值算法在聚類中心的選取上，充分考慮了聚類中心之間的距離，對(duì)文摘去冗余有直接效用。

在密度聚類算法中，有兩個(gè)主要標(biāo)準(zhǔn):局部密度ρi和距離δi。ρi是與i的距離小于dc的點(diǎn)的個(gè)數(shù)，稱ρi為局部密度，ρi的公式為

dc是截?cái)嗑嚯x（cutoff distance），dc值可結(jié)合實(shí)際需要進(jìn)行確定，其中χ的函數(shù)公式為

根據(jù)密度降序排序，依次計(jì)算候選密度中心的距離。δi是點(diǎn)i與其他密度大于i的點(diǎn)之間的最小距離，其公式為

密度最大的點(diǎn)與其他參考點(diǎn)的δi計(jì)算公式為

密度峰值算法的核心思想是同時(shí)考慮ρi和δi，在二維空間中提取聚類中心點(diǎn)，即把ρi看作橫軸，δi看作豎軸，提取數(shù)軸右上角區(qū)域內(nèi)的點(diǎn)，就是密度較大且與其他參考點(diǎn)之間的距離較大的點(diǎn)，可提取為文章的聚類中心點(diǎn)。

2　系統(tǒng)實(shí)現(xiàn)

系統(tǒng)將句子作為抽取的最小單位，把句子看作是詞的線性組合，生成單文本的抽取式文摘，設(shè)計(jì)并實(shí)現(xiàn)了面向科技成果類文檔的中文自動(dòng)文摘系統(tǒng)。傳統(tǒng)的自動(dòng)文摘系統(tǒng)S1的處理流程為:預(yù)處理、句子余弦相似度計(jì)算、句權(quán)值計(jì)算、去冗余、文摘生成。結(jié)合應(yīng)用密度峰值算法的系統(tǒng)S2的文摘生成框架圖如圖1所示。

系統(tǒng)S1與系統(tǒng)S2的主要區(qū)別在于，S1采用去冗余方法，S2采用密度峰值聚類，嘗試達(dá)到共同的效果。S1的句權(quán)值為S2句權(quán)值減去聚類中心加權(quán)的差值。

系統(tǒng)S2主要把詞頻分布特征、詞性、句子長(zhǎng)度和句子類型作為句子篩選的標(biāo)準(zhǔn)。句子按權(quán)值排序，按文檔壓縮率抽取文摘句。

2.1文檔預(yù)處理

文檔預(yù)處理主要包括分詞、去停用詞和詞頻統(tǒng)計(jì)。分詞之前先進(jìn)行分句和選句，去除不宜選入文摘的句子。采用ansj_seg分詞和詞性標(biāo)注，去停用詞后，統(tǒng)計(jì)詞頻TF。選取名詞、動(dòng)詞、副詞和形容詞作為計(jì)算詞集。

2.2句子聚類

把文檔的所有句子當(dāng)做無向有權(quán)圖處理，采用余弦相似度算法計(jì)算句子之間的關(guān)系，采用密度峰值對(duì)句子進(jìn)行聚類，提取聚類中心。

2.2.1余弦相似度

把文檔中的每個(gè)句子都看作由詞組成的向量，假設(shè)句子向量A=（tfi1，tfi2，…，tfin），向量 B= （tfj1，tfj2，…，tfjn），則兩句子的余弦相似度 S （Similarity）的公式為

把一篇文檔中的所有句子看做是無向有權(quán)圖的節(jié)點(diǎn)，S值看做邊的權(quán)值。設(shè)一篇文章有n個(gè)句子，無向圖的邊為n（n-1）/2條，計(jì)算S并將S值降序排序。

2.2.2句子聚類

聚類中的距離d=1-S。dc是使得相鄰點(diǎn)的平均數(shù)占總數(shù)據(jù)點(diǎn)數(shù)的1.6%。

聚類中心點(diǎn)的選取:取右上角的點(diǎn)，橫縱坐標(biāo)從右上角為起點(diǎn)限定范圍，根據(jù)范圍里點(diǎn)的個(gè)數(shù)來確定是否繼續(xù)擴(kuò)大范圍。系統(tǒng)提取4到8個(gè)聚類中心，如遇到重疊嚴(yán)重，隨機(jī)在重疊點(diǎn)中抽取所需，并將提取出的聚類中心加權(quán)。

2.3句權(quán)值的計(jì)算和文摘生成

句權(quán)值=詞頻平均值+余弦相似度平均值+句子位置+C（聚類中心加權(quán)）。將句權(quán)值降序排序，根據(jù)文檔壓縮率提取文摘。

3　實(shí)驗(yàn)對(duì)比分析

結(jié)合密度峰值算法的系統(tǒng)S2與系統(tǒng)S1進(jìn)行實(shí)驗(yàn)對(duì)比，采用3種評(píng)測(cè)方法，分別以文本壓縮率為10%和20%進(jìn)行文摘測(cè)評(píng)。

3.1評(píng)測(cè)庫(kù)的創(chuàng)建

為了實(shí)驗(yàn)評(píng)測(cè)，建立一個(gè)科技成果語料庫(kù)，文章來自國(guó)家科技成果網(wǎng)。語料庫(kù)根據(jù)文檔長(zhǎng)度劃分成兩個(gè)文檔數(shù)據(jù)集，各100篇，共200篇科技成果文檔。文檔內(nèi)容包括題目、關(guān)鍵字和正文等。4名研究人員協(xié)同提取文摘和人工標(biāo)注，完成2個(gè)評(píng)測(cè)數(shù)據(jù)集SAT2015-L和SAT2015-S的建立。分別按10%和20%的壓縮率提取文摘，數(shù)據(jù)集的統(tǒng)計(jì)信息如表1所示。

表1　數(shù)據(jù)集的統(tǒng)計(jì)信息Table 1 Statistics of data sets

3.2評(píng)測(cè)方法

采用內(nèi)部評(píng)測(cè)和相似度評(píng)測(cè)兩種方法，對(duì)應(yīng)用密度峰值算法的自動(dòng)文摘系統(tǒng)進(jìn)行評(píng)測(cè)。

1）內(nèi)部評(píng)測(cè)

F-Measur（簡(jiǎn)稱F-M）。如果參考文摘為n個(gè)句子，機(jī)器文摘為k個(gè)句子，并且有p個(gè)參考文摘中的句子包含在機(jī)器文摘中，則F-M的公式為

2）余弦相似度評(píng)測(cè)

假設(shè)參考文摘詞的向量為S，機(jī)器文摘詞的向量為M，把它們組合成一個(gè)新文檔，向量計(jì)算方法參考2.2.1的公式（5）。

3）調(diào)整標(biāo)題評(píng)測(cè)方法（簡(jiǎn)稱K）

由于采用自建評(píng)測(cè)數(shù)據(jù)集，其中人工因素不可控。為了增加評(píng)測(cè)的客觀性，結(jié)合評(píng)測(cè)方法，將文檔的標(biāo)題和關(guān)鍵詞建立成評(píng)測(cè)標(biāo)注集，簡(jiǎn)稱關(guān)鍵字（Keyword）集。采用余弦相似度算法對(duì)機(jī)器文摘與關(guān)鍵詞集進(jìn)行相似度計(jì)算。關(guān)鍵詞集的不足在于詞類范圍比較局限。

內(nèi)部評(píng)測(cè)F-M和相似度評(píng)測(cè)比較，余弦相似度的算法比較穩(wěn)定。由于內(nèi)部評(píng)測(cè)方法過于武斷，當(dāng)兩個(gè)句子完全相同時(shí)為真，否則為假。相似度評(píng)測(cè)方法以數(shù)據(jù)集中的詞為基本單位進(jìn)行比較，所以評(píng)測(cè)效果較好。余弦相似度評(píng)測(cè)與K評(píng)測(cè)都是相似度評(píng)測(cè)，有較好的實(shí)驗(yàn)效果。

采用自建的科技成果語料庫(kù)，人工篩選文摘，K評(píng)測(cè)增加了評(píng)測(cè)結(jié)果的可信度。

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

采用密度峰值算法聚類中心提取結(jié)果如圖2所示。

圖中右上角框出的矩形區(qū)域內(nèi)，有4個(gè)聚類中心點(diǎn)，進(jìn)行加權(quán)。

考慮到文摘壓縮率對(duì)文摘測(cè)評(píng)的影響，分別以10%和20%的壓縮率進(jìn)行文摘提取。原系統(tǒng)S1和系統(tǒng)S2進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如表2所示。

表2　評(píng)測(cè)結(jié)果對(duì)比表Table 2 Comparison of the results

根據(jù)不同的評(píng)測(cè)方法，在文檔壓縮率為10%和20%的情況下，計(jì)算出改進(jìn)系統(tǒng)較原系統(tǒng)的文摘質(zhì)量提升值如表3所示。

表3　評(píng)測(cè)提升表Table 3 Improved system upgrade data

在不同文檔壓縮率的情況下，系統(tǒng)S2較系統(tǒng)S1的提升圖如圖3所示。

評(píng)測(cè)實(shí)驗(yàn)結(jié)果表明:

1）在系統(tǒng)S2中，不同壓縮率的情況下，當(dāng)文檔壓縮率為10%提取文摘時(shí)，加入密度峰值的系統(tǒng)提升效果更明顯。此差異與文檔和評(píng)測(cè)語料的大小相關(guān)，壓縮率繼續(xù)提升，測(cè)評(píng)結(jié)果不一定提升。

2）在壓縮率一定的情況下，采用余弦相似度評(píng)測(cè)和K評(píng)測(cè)時(shí)，提升效果較明顯。這是由于F-M評(píng)測(cè)方法，當(dāng)提取文摘句與評(píng)測(cè)文摘句完全相同時(shí)，才認(rèn)定為文摘句提取成功。相似度評(píng)測(cè)對(duì)比的最小單位是詞。

4　結(jié)束語

傳統(tǒng)方法普遍通過生成候選集后去除冗余的提取文摘方法，候選集的大小對(duì)文摘質(zhì)量有直接影響且不易設(shè)定。將密度峰值算法應(yīng)用到文摘中，可以同時(shí)考慮文本聚類中心的密度和文本聚類中心間的距離，即同時(shí)選取具有代表性的句子并減少句子間的冗余。結(jié)合密度峰值算法，設(shè)計(jì)面向科技成果文檔的自動(dòng)文摘系統(tǒng)，有較高的研究?jī)r(jià)值。

［參考文獻(xiàn)］

［1］ Radev D R，Hovy E，McKeown K.Introduction to the Special Issue on Summarization［J］.Computational Linguistics，2002，28（4）:399-408.

［2］ Corinna Cortes，Vladimir Vapnik.Support-vector networks［J］.Machine Learning，1995，20（1）:273-297.

［3］ Betous-Almeida C，Kanoun K.Construction and stepwise refinement of dependability models［J］.Performance Evaluation，2004（56）:277-306.

［4］ 楊建林.一種使用自動(dòng)聚類思想的自動(dòng)文摘方法［J］.情報(bào)學(xué)報(bào)，2001，20（5）:532-536.

［5］ 劉海濤，老松楊，韓智廣.自動(dòng)文摘系統(tǒng)中的段落自適應(yīng)聚類研究［J］.微計(jì)算機(jī)信息，2006，22（6-3）:288-291.

［6］ 郭慶琳，吳克河，吳慧芳，等.基于文本聚類的多文檔自動(dòng)文摘研究［J］.計(jì)算機(jī)研究與發(fā)展，2007，44（Z2）:140-144.

［7］ 張磊.基于聚類算法的中文自動(dòng)文摘方法研究［D］.福建:廈門大學(xué)，2009.

［8］ 郭海蓉，張暉，趙旭劍，等.一種基于改進(jìn)K-means的動(dòng)態(tài)文摘提取方法［J］.軟件導(dǎo)刊，2015，14（5）:77-79.

［9］ Alex Rodriguez，Alessandro Laio.Clustering by fast search and find of density peaks［J］.Science，2014（344）:1492.

（責(zé)任編輯 柴 智）

Application of Density Peak Algorithm in Chinese Automatic Summarization

LI Ming-li，SUN Lian-ying，XING Han，SHI Xiao-da
（College of Information Technology，Beijing Union University，Beijing 100101，China）

Abstract:With the innovation of natural language processing technology，the quality of automatic summarization has beensignificantlyimproved.Chineseautomaticsummarizationforthescientificandtechnological achievements has become a hot research topic，and has a certain application value.Clustering algorithm is applied to the automatic summarization，and the idea of extract clustering center has a certain significance to remove redundancy.With the application of the density peak algorithm to automatic summarization，the automatic summarization system for the scientific and technological achievements has been realized.

Key words:Automatic summarization；Density peak；Redundancy processing

［中圖分類號(hào)］O 212.4

［文獻(xiàn)標(biāo)志碼］A

［文章編號(hào)］1005-0310（2016）02-0046-04

DOI：10.16255/j.cnki.ldxbz.2016.02.08

［收稿日期］2015-11-19

［作者簡(jiǎn)介］李明麗（1989-），女，河北省唐山市人，北京聯(lián)合大學(xué)信息學(xué)院碩士研究生，研究方向?yàn)橹R(shí)工程。

［通訊作者］孫連英（1968-），女，吉林梅河口人，北京聯(lián)合大學(xué)信息學(xué)院教授，博士，研究方向?yàn)閿?shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)。E-mail:sunlychina@163.com