李靜月，徐濟(jì)成，朱　昊

(中澳科技職業(yè)學(xué)院信息技術(shù)與藝術(shù)傳媒系， 安徽　合肥　230000)

?

一種改進(jìn)的CURE的事件聚類方法

李靜月，徐濟(jì)成，朱昊

(中澳科技職業(yè)學(xué)院信息技術(shù)與藝術(shù)傳媒系， 安徽合肥230000)

[摘要]一個(gè)文檔往往包含多個(gè)主題的事件，把分散在多個(gè)文本中的同一主題事件組織起來依靠傳統(tǒng)的文本聚類是無法實(shí)現(xiàn)的.本文通過對(duì)已有的CURE算法進(jìn)行分析，根據(jù)事件的特征，對(duì)代表點(diǎn)的選取和小類合并機(jī)制進(jìn)行改進(jìn)，實(shí)現(xiàn)了一個(gè)改進(jìn)的CURE算法.實(shí)驗(yàn)結(jié)果表明：改進(jìn)后的方法在保證執(zhí)行效率的情況下取得了更好的聚類效果.

[關(guān)鍵詞]層次聚類；CURE；代表點(diǎn)；事件聚類 從互聯(lián)網(wǎng)上獲取關(guān)于H1N1的文檔460篇，這些文章經(jīng)過提取后，獲取關(guān)鍵語句7 589句作為測(cè)試語料.人工把句子分成6類，實(shí)驗(yàn)采用了查準(zhǔn)率P、查全率R和F-Measure綜合評(píng)價(jià)的方法來判斷聚類的效果.具體定義如下：

隨著計(jì)算機(jī)的普及和網(wǎng)絡(luò)的飛速發(fā)展，互聯(lián)網(wǎng)上的各類信息以及各種電子文檔資源以空前速度增長(zhǎng).但是，占信息比重最大的文本數(shù)據(jù)卻存在組織無結(jié)構(gòu)的問題，并且散布于網(wǎng)絡(luò)各個(gè)角落，大大降低了網(wǎng)絡(luò)文本信息的利用效率.如何對(duì)文本信息進(jìn)行有效組織和提取，并分門別類地呈現(xiàn)給用戶，是我們面臨的一個(gè)問題.文本聚類方法可以為各種文本信息處理應(yīng)用提供有效的處理方法.傳統(tǒng)的聚類方法有：劃分方法、層次方法、基于密度的方法、網(wǎng)格的方法以及基于模型的方法，此外還有改進(jìn)的混合聚類方法[1,2].絕大多數(shù)聚類算法或者擅長(zhǎng)處理球形與相似大小的聚類，或者在存在孤立點(diǎn)時(shí)變得比較脆弱.但是，一個(gè)文檔往往包含多個(gè)主題的事件，把分散在多個(gè)文本中的同一主題事件組織起來依靠傳統(tǒng)的文本聚類是無法實(shí)現(xiàn)的.

本文以同一事件的多個(gè)相關(guān)文本為研究對(duì)象，實(shí)驗(yàn)文本具有以下主要特點(diǎn)：第一，文本相關(guān)性大，同一句式出現(xiàn)較為頻繁；第二，句子與事件某一方面的對(duì)應(yīng)關(guān)系較為明確.因此把相似的句子歸為一類，就可得到關(guān)于某一事件的各個(gè)側(cè)面信息并分別呈現(xiàn)給用戶.CURE[3](Clustering Using Representatives)算法用多個(gè)代表點(diǎn)來表示一個(gè)類可以發(fā)現(xiàn)任何形狀的簇，并且在處理孤立點(diǎn)上也更加健壯.本文在借鑒傳統(tǒng)的聚類方法的基礎(chǔ)上，將CURE方法在代表點(diǎn)的選取和合并策略方面進(jìn)行改進(jìn)，同時(shí)根據(jù)待聚類句子的特征優(yōu)化句子相似度計(jì)算方法.實(shí)驗(yàn)證明：本文提出的方法可以提高句子相似度計(jì)算和聚類結(jié)果的準(zhǔn)確性，形成關(guān)于各主題的由句子組成的類.

1CURE層次凝聚算法分析

在聚類算法中，類的表達(dá)方式有兩種：一是用一個(gè)點(diǎn)來表示，這個(gè)點(diǎn)可以是最靠近均值點(diǎn)的那個(gè)實(shí)際數(shù)據(jù)點(diǎn)，也可以使用不存在的均值點(diǎn).該方法使用于類分布良好、呈現(xiàn)超球形狀而且密度大小變化不大的情況.第二是用全部數(shù)據(jù)點(diǎn)表示，這種方法能發(fā)現(xiàn)任意形狀的類，但受噪聲點(diǎn)影響大，當(dāng)數(shù)據(jù)量較大時(shí)運(yùn)行時(shí)間很長(zhǎng).CURE[4,5]采用固定個(gè)數(shù)的點(diǎn)來表示一個(gè)類，先從類中選出分布良好、能體現(xiàn)類形狀的點(diǎn)，再把這些點(diǎn)向類的中心收縮，得到類的代表點(diǎn)；然后根據(jù)類間的相似度來選取要合并的類，在類合并過程中，如果一個(gè)類增長(zhǎng)太慢，就認(rèn)為該類中的點(diǎn)是噪聲，去掉它.這種方法使得CURE不但能識(shí)別任意形狀的類，而且能削弱噪聲的影響.

CURE方法的實(shí)現(xiàn)步驟如下：

1)把每個(gè)點(diǎn)當(dāng)作一類，選取兩個(gè)距離最近類進(jìn)行合并.

2)選取類的代表點(diǎn)：落在每個(gè)新形成的類中的代表點(diǎn)根據(jù)用戶定義的一個(gè)收縮因子收縮或向類中心移動(dòng).

3)刪除異常點(diǎn)：如果一個(gè)類增長(zhǎng)太慢就刪除它，在聚類的最后將非常小的簇刪除.

但是該算法仍然存在不足，容易把邊緣的噪聲點(diǎn)選為代表點(diǎn)，而且在小類合并的時(shí)候僅考慮兩個(gè)類中代表點(diǎn)對(duì)的最小距離，在一些情況下無法得到好的聚類效果.本文從代表點(diǎn)的選取和合并規(guī)則兩個(gè)方面改進(jìn)CURE算法.

2改進(jìn)的CURE聚類方法

2.1　代表點(diǎn)的選取

CURE算法中類代表點(diǎn)通過如下方式產(chǎn)生：第一代表點(diǎn)是距離該聚類中心點(diǎn)最遠(yuǎn)的數(shù)據(jù)點(diǎn)，其后的代表點(diǎn)是選取距離前一個(gè)選出的代表點(diǎn)距離最遠(yuǎn)的數(shù)據(jù)點(diǎn).然后根據(jù)一個(gè)特定的分?jǐn)?shù)或收縮因子“收縮”或移動(dòng)代表點(diǎn)得到最終的代表點(diǎn).當(dāng)簇的形狀、分布或密度不一致時(shí)可能選取不合理的代表點(diǎn)，例如：一個(gè)簇中共有20個(gè)句子，其中15個(gè)句子很相似，另外5個(gè)句子散在15個(gè)句子周圍，利用原有的代表點(diǎn)選取方法，會(huì)選擇分布稀疏的點(diǎn)作為代表點(diǎn)，一些情況下，這些點(diǎn)很有可能是噪聲點(diǎn).其本質(zhì)原因在于CURE選取簇邊緣的數(shù)據(jù)點(diǎn)作代表點(diǎn)的概率比較大，而在很多情況下簇邊緣的點(diǎn)往往并不能代表簇，并且成為噪聲點(diǎn)的概率較大.

基于以上分析，本文對(duì)代表點(diǎn)的選取進(jìn)行了改進(jìn).同一句子在一類文章中出現(xiàn)的次數(shù)越多，則說明該句子對(duì)表達(dá)事件主題有重要影響，能很好地描述事件的一個(gè)主題；在一個(gè)小類中，如果到一個(gè)代表點(diǎn)的距離最近的句子總數(shù)比較多則說明該代表點(diǎn)是個(gè)好的代表點(diǎn).如果到一個(gè)代表點(diǎn)距離最近的句子數(shù)只有一個(gè)或者很少，則說明該代表點(diǎn)是一個(gè)很不好的代表點(diǎn).設(shè)Sm是中心點(diǎn),則句子Sq到中心點(diǎn)的距離為：

(1)

其中：f為句子在整個(gè)文本集中出現(xiàn)的頻率，N為當(dāng)前類中所有句子的出現(xiàn)頻率之和，Sim(Sm,Sq)是兩個(gè)句子的相似度.相似度計(jì)算采用基于相同詞串和權(quán)值的方法.

1)選取小類的中心點(diǎn)作為第一個(gè)代表點(diǎn).

2)在剩余的句子中選取距離已選取的代表點(diǎn)最小距離最大的句子作為新的代表點(diǎn).不斷進(jìn)行，直到找到c個(gè)代表點(diǎn)為止.

2.2　小類合并的改進(jìn)

CURE在小簇合并時(shí)，選擇有最近距離代表點(diǎn)對(duì)的兩個(gè)簇進(jìn)行合并(計(jì)算兩個(gè)小簇的相似度時(shí)僅考慮了兩個(gè)小簇的代表點(diǎn)之間的最小距離).這種策略使得簇的個(gè)別代表點(diǎn)可能較嚴(yán)重地影響簇間的相似度，而且這種相似性度量忽略了簇本身的部分信息.

為了盡量避免上述情況發(fā)生，本文選擇兩個(gè)直接互相接近的數(shù)據(jù)點(diǎn)多的類進(jìn)行合并，用句子相似度來表示代表點(diǎn)之間的距離，相似度越大距離越小.合并策略為：代表點(diǎn)之間的最小距離小于閾值個(gè)數(shù)k來代表類之間的相關(guān)度，k值越大則類間相關(guān)度越大.在每次小類的合并時(shí)都選出相關(guān)度最大的兩個(gè)類進(jìn)行合并，然后計(jì)算新類的相關(guān)度.

2.3　基于CURE的句子聚類流程

根據(jù)待聚類句子的特點(diǎn)，先對(duì)句子進(jìn)行預(yù)處理，以提高聚類效果.首先，統(tǒng)一命名實(shí)體、時(shí)間和數(shù)字的格式.表達(dá)相同內(nèi)容的詞語或者是表達(dá)相同類的詞語被看作不同項(xiàng)會(huì)降低聚類效果.因此，統(tǒng)一人名、數(shù)字、機(jī)構(gòu)名、地名和時(shí)間短語，只考慮這些詞的詞性信息而忽視詞形的差異.這樣能提高關(guān)鍵詞抽取效果.其次，對(duì)句子中的關(guān)鍵動(dòng)詞進(jìn)行同義詞擴(kuò)充.句子相似度計(jì)算[6]通常采用的是基于詞語建立向量空間模型的方法，一個(gè)句子可視為n維空間中的一個(gè)向量.通過計(jì)算向量間的夾角余弦值得到句子相似度[7]，同義詞被看成不同的詞語降低了句子的相似度，影響了句子聚類的效果.由于句子包含信息量少，漢語句子以字和詞語為中心表達(dá)意思，在一個(gè)句子內(nèi)可用于聚類的特征少，這直接影響了聚類的效果.為了消除這種影響和減少句子相似度計(jì)算的難度，首先對(duì)句子中的關(guān)鍵動(dòng)詞進(jìn)行同義詞擴(kuò)充.同義詞擴(kuò)充使得同一類中的句子包含多種表達(dá)形式，而且進(jìn)行句子相似度計(jì)算時(shí)不用考慮同義詞的計(jì)算.

具體步驟如下：

1)預(yù)處理：統(tǒng)一人名、機(jī)構(gòu)名、地名、數(shù)字以及時(shí)間短語，擴(kuò)充句子中的關(guān)鍵動(dòng)詞和關(guān)鍵名詞；

2)把每個(gè)句子及其擴(kuò)充后的句子歸為一類，合并含有相同句子的小類.把合并后的類作為初始的聚類數(shù)據(jù)；

3)在每個(gè)類中選取代表點(diǎn)；

4)根據(jù)類間距離合并小類；

5)刪除異常點(diǎn).

3實(shí)驗(yàn)結(jié)果與分析

(2)

(3)

(4)

(5)

(6)其中：N1為自動(dòng)聚類中正確的屬于類i的句子數(shù)目，N2為聚類結(jié)果中屬于類i的所有句子數(shù)目，N3為人工標(biāo)記屬于類i的所有句子的數(shù)目.P(i)為第i個(gè)類的查準(zhǔn)率，R(i)為第i個(gè)類的查全率.實(shí)驗(yàn)結(jié)果如表1所示.

表1　句子聚類結(jié)果評(píng)價(jià)

本文根據(jù)聚類句子的特點(diǎn)，對(duì)其進(jìn)行同義詞擴(kuò)充，減少了句子相似度計(jì)算處理同義詞的難度，代表點(diǎn)的選取充分考慮了小類的總體特征和代表點(diǎn)的代表性能，小類合并策略也考慮了小類的總體特征.實(shí)驗(yàn)結(jié)果表明：改進(jìn)后的算法能夠取得更好的聚類結(jié)果.由于句子包含信息量少，漢語句子以字和詞語為中心表達(dá)意思，在一個(gè)句子內(nèi)可用于聚類的特征少.這直接影響到聚類效果.此外，以命名實(shí)體識(shí)別、指代消解、詞義排歧等多種自然語言處理技術(shù)作為基礎(chǔ)，但目前的實(shí)用系統(tǒng)難以達(dá)到滿意的效果.這也影響了句子聚類的效果.

4結(jié)語

CURE算法能夠識(shí)別非球形和大小變化比較大的類，而且從兩個(gè)階段消除噪聲的影響.本文在對(duì)同一事件的多個(gè)文本分析的基礎(chǔ)上對(duì)CURE算法進(jìn)行改進(jìn)，用于句子聚類：代表點(diǎn)的選取不僅考慮到類的形狀，而且考慮句子對(duì)描述事件的貢獻(xiàn)大??；句子包含信息量少，根據(jù)兩個(gè)類中代表點(diǎn)的最小距離來合并小類很容易丟失類的總體信息.本文在小類合并時(shí)充分考慮了小類的總體特征.實(shí)驗(yàn)表明，該方法能夠取得較好的聚類效果.

[參考文獻(xiàn)]

[1]Murty N, Krishna G. A hybrid clustering procedure for concentric and chain-like clusters [J]. International Journal of Computer and Information Sciences, 1981, 10(6): 397-412.

[2]Karpis G, Kumar V, Chameleon .A hierarchical clustering algorithm using dynamicmodeling[J]. Computer, 1999,32: 68-75.

[3]Wang L, Kitsuregawa M. Use link-based clustering to improve web search results [A]. In: proceedings of the second international conference on web information systems engineering [C]. Washington,DC:WISE, 2001：119-128.

[4]倪維健,黃亞樓,李飛 一種基于加權(quán)多代表點(diǎn)的層次聚類算法[J]. 計(jì)算機(jī)科學(xué)，2005，32(5)：150-154.

[5]魏桂英,鄭玄軒.層次聚類方法的CURE算法研究[J]. 科技和產(chǎn)業(yè)，2005(11)：22-24.

[6]王榮波,池哲儒,常寶寶.基于詞串粒度及權(quán)值的漢語句子相似度 衡量[J]. 計(jì)算機(jī)工程，2005，31(13)：142-144.

[7]馮曉云.基于云計(jì)算的文本聚類算法研究[D]. 南京：南京理工大學(xué)，2014：29-33.

(責(zé)任編輯穆剛)

An event clustering approach on the improved CURE algorithm

LI Jingyue, XU Jicheng， ZHU Hao

(Department of Information Technology and Media Arts, Anhui ZHONG-AO Institute of Technology, Hefei Anhui 230041, China)

Abstract：A document commonly contains many events with different topics, so it’s really hard for traditional clustering algorithms to organize such events with the same topic in multi-documents. Through the analysis of the feature of traditional CURE algorithm, and according to the feature of the events. This paper proposes an improved CURE algorithm that improved the selecting of representative points and clusters nesting mechanism. The experimental results show that our approach can provide better performance than that of other methods.

Key words：hierarchical clustering; CURE; representative points; event clustering

[中圖分類號(hào)]TP31

[文獻(xiàn)標(biāo)志碼]A

[文章編號(hào)]1673-8004(2015)05-0121-04

[作者簡(jiǎn)介]李靜月(1982—)，女，河南安陽人，助教，碩士，主要從事中文信息處理方面的研究.

[基金項(xiàng)目]安徽省級(jí)質(zhì)量工程項(xiàng)目 (2013TSZY088).

[收稿日期]2014-12-31