李明麗，孫連英，邢 邗，石曉達

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

?

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

李明麗，孫連英，邢 邗，石曉達

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

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

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

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

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

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

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

1　密度峰值算法

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

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

dc是截斷距離（cutoff distance），dc值可結(jié)合實際需要進行確定，其中χ的函數(shù)公式為

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

密度最大的點與其他參考點的δi計算公式為

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

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

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

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

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

2.1文檔預(yù)處理

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

2.2句子聚類

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

2.2.1余弦相似度

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

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

2.2.2句子聚類

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

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

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

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

3　實驗對比分析

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

3.1評測庫的創(chuàng)建

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

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

3.2評測方法

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

1）內(nèi)部評測

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

2）余弦相似度評測

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

3）調(diào)整標(biāo)題評測方法（簡稱K）

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

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

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

3.3實驗結(jié)果及分析

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

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

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

表2　評測結(jié)果對比表Table 2 Comparison of the results

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

表3　評測提升表Table 3 Improved system upgrade data

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

評測實驗結(jié)果表明:

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

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

4　結(jié)束語

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

［參考文獻］

［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］ 楊建林.一種使用自動聚類思想的自動文摘方法［J］.情報學(xué)報，2001，20（5）:532-536.

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

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

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

［8］ 郭海蓉，張暉，趙旭劍，等.一種基于改進K-means的動態(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

［中圖分類號］O 212.4

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

［文章編號］1005-0310（2016）02-0046-04

DOI：10.16255/j.cnki.ldxbz.2016.02.08

［收稿日期］2015-11-19

［作者簡介］李明麗（1989-），女，河北省唐山市人，北京聯(lián)合大學(xué)信息學(xué)院碩士研究生，研究方向為知識工程。

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