李靜月，徐濟成，朱　昊

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

?

一種改進的CURE的事件聚類方法

李靜月，徐濟成，朱昊

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

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

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

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

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

1CURE層次凝聚算法分析

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

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

1)把每個點當作一類，選取兩個距離最近類進行合并.

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

3)刪除異常點：如果一個類增長太慢就刪除它，在聚類的最后將非常小的簇刪除.

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

2改進的CURE聚類方法

2.1　代表點的選取

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

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

(1)

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

1)選取小類的中心點作為第一個代表點.

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

2.2　小類合并的改進

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

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

2.3　基于CURE的句子聚類流程

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

具體步驟如下：

1)預處理：統(tǒng)一人名、機構名、地名、數(shù)字以及時間短語，擴充句子中的關鍵動詞和關鍵名詞；

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

3)在每個類中選取代表點；

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

5)刪除異常點.

3實驗結果與分析

(2)

(3)

(4)

(5)

(6)其中：N1為自動聚類中正確的屬于類i的句子數(shù)目，N2為聚類結果中屬于類i的所有句子數(shù)目，N3為人工標記屬于類i的所有句子的數(shù)目.P(i)為第i個類的查準率，R(i)為第i個類的查全率.實驗結果如表1所示.

表1　句子聚類結果評價

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

4結語

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

[參考文獻]

[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]倪維健,黃亞樓,李飛 一種基于加權多代表點的層次聚類算法[J]. 計算機科學，2005，32(5)：150-154.

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

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

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

(責任編輯穆剛)

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

[中圖分類號]TP31

[文獻標志碼]A

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

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

[基金項目]安徽省級質量工程項目 (2013TSZY088).

[收稿日期]2014-12-31