基于Sollin算法的快速聚類研究

劉 歡

（渤海船舶職業(yè)學(xué)院，遼寧興城125105）

0 引言

文本作為信息載體，因其數(shù)量巨大而難以甄別。文本聚類技術(shù)作為處理和組織大量文本數(shù)據(jù)的一項(xiàng)重要技術(shù)，能夠在很大程度上解決由于信息爆炸所帶來的問題。文本聚類是通過數(shù)據(jù)集的空間分布情況以及相似性度量方法對數(shù)據(jù)進(jìn)行分析。根據(jù)聚類方式的不同，文本聚類可以分為劃分式聚類和層次聚類。由于層次聚類算法簡單容易實(shí)現(xiàn)且適合多種形狀分布的數(shù)據(jù)，因此本文主要對層次聚類進(jìn)行研究。

層次聚類按照聚類過程的不同可以分為自上而下的分裂式聚類方法和自下而上的凝聚式聚類方法。較經(jīng)典的層次聚類算法有BIRCH算法和CURE算法。

傳統(tǒng)的層次聚類算法因?yàn)楹喜⒎椒▎我磺矣?jì)算量巨大，造成聚類質(zhì)量大大降低。因此本文提出了基于Sollin的快速層次聚類算法，使得運(yùn)行效率和聚類質(zhì)量都有明顯的提升。

1 相關(guān)知識

1.1 層次聚類

層次聚類又稱為樹聚類算法，它根據(jù)數(shù)據(jù)之間的相似度，通過一種層次架構(gòu)方式，反復(fù)的將數(shù)據(jù)進(jìn)行分裂和聚合，從而形成一種樹狀的層次聚類解。本文主要研究自底向上的聚合方法，首先將每一個(gè)對象作為一個(gè)簇，然后每次合并相似度最大的兩個(gè)簇，直到所有的數(shù)據(jù)對象都在一個(gè)簇中或者達(dá)到某個(gè)終結(jié)條件為止。傳統(tǒng)層次聚類算法如圖1所示。

圖1 傳統(tǒng)層次聚類過程

輸入：n個(gè)樣本點(diǎn)

輸出：k個(gè)類

步驟：1）將每個(gè)數(shù)據(jù)對象看作一個(gè)簇，計(jì)算它們之間的相似度sim（i，j），簇之間的相似度就是它們所包含的對象之間的相似度；

2）將相似度最大的兩個(gè)簇合并成為一個(gè)新的簇；

3）重新對新的簇與其他簇之間的相似度進(jìn)行計(jì)算；

4） 重復(fù)步驟 （2） 和 （3），直到所有數(shù)據(jù)對象在一個(gè)簇中或者達(dá)到某個(gè)終結(jié)條件。

層次聚類在聚類的過程中需要對簇進(jìn)行合并或分裂操作，因此除定義樣本點(diǎn)之間的距離外，還要定義簇與簇之間的距離，常用的簇間距離表示方法有以下3種：

單鏈接，即使用兩簇之間最相似的兩個(gè)樣本點(diǎn)之間的相似度作為兩簇之間的相似度，如圖2（a） 所示。

全鏈接，即使用兩簇之間最不相似的兩個(gè)樣本點(diǎn)之間的相似度作為兩簇之間的相似度，如圖2（b） 所示。

平均鏈接，即使用兩簇之間所有樣本點(diǎn)之間的相似度之和的平均值作為兩簇之間的相似度，如圖2（c） 所示。

圖2 簇間相似性表示方法

在以上3種距離表示方法中，相對于單鏈接和全鏈接而言，平均鏈接介于兩者之間，它充分考慮到了簇與簇之間每個(gè)樣本點(diǎn)之間的距離，計(jì)算出來的簇間距離更接近實(shí)際情況，具有一定的優(yōu)越性能。

1.2 Sollin算法

Sollin算法是構(gòu)建最小生成樹的典型算法，它是基于貪心策略的局部最優(yōu)算法，與Kruskal算法和Prim算法相比，Sollin算法容易實(shí)現(xiàn)并行運(yùn)算。

Sollin算法構(gòu)建最小生成樹的基本步驟是將連通圖中所有頂點(diǎn)當(dāng)作一棵樹，原連通圖就成為了一個(gè)森林；然后每棵樹同時(shí)決定其連向其他樹的最小權(quán)值臨邊（臨邊可以是同一條邊），并與這個(gè)最相鄰的節(jié)點(diǎn)結(jié)合成一棵樹；最后重復(fù)上一步驟，直到所有節(jié)點(diǎn)都在一棵樹上為止。圖3為Sollin算法構(gòu)建最小生成樹的實(shí)例。

圖3 Sollin算法構(gòu)建最小生成樹

2 基于Sollin的快速層次聚類算法

層次聚類算法實(shí)現(xiàn)簡單，且聚類精度較高，但是其時(shí)間復(fù)雜度也較高，對于孤立點(diǎn)的處理能力非常弱?；赟ollin的快速層次聚類算法通過并行合并各子簇來降低聚類過程中的時(shí)間消耗，每層各個(gè)子簇都會找到與自己最相似的子簇進(jìn)行合并，即可以消除孤立點(diǎn)單獨(dú)成類的問題?；赟ollin的快速層次聚類算法的基本思想如下：

輸入：n個(gè)數(shù)據(jù)對象

輸出：k個(gè)類

步驟：1）設(shè)有n個(gè)數(shù)據(jù)對象，將每個(gè)數(shù)據(jù)對象當(dāng)作一個(gè)簇；

2）計(jì)算各簇之間的相似度；

3） 通過Sollin構(gòu)建最小生成樹的算法將數(shù)據(jù)合并成m（m＜n）個(gè)最小生成樹；

4） 重復(fù)步驟 （2） 和 （3） 的過程，直到m＜=k為止；

5） 如果m＜k，則將 （k-m） 條相似度最小的邊斷開，從而形成k個(gè)類。

Sollin算法是構(gòu)建最小生成樹的典型算法，因此基于Sollin的快速層次聚類算法在每層的聚合過程都可以看作是構(gòu)建最小生成樹的過程。這樣既可以實(shí)現(xiàn)聚類算法的并行運(yùn)算，提升其聚類效率；又可以消除孤立點(diǎn)單獨(dú)成類問題，提升其聚類質(zhì)量。

3 實(shí)驗(yàn)

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

本實(shí)驗(yàn)選擇復(fù)旦分類語料和搜狗分類語料（下載于“數(shù)據(jù)堂”） 作為實(shí)驗(yàn)數(shù)據(jù)，如表1和表2所示。

表1 復(fù)旦語料

表2 搜狗語料

3.2 實(shí)驗(yàn)預(yù)處理

所有實(shí)驗(yàn)語料均通過中科院分詞工具“NLPIR漢語分詞系統(tǒng)”進(jìn)行分詞，根據(jù)哈工大的停用詞表去除停用詞。然后用向量空間模型表示每篇文章，其中詞的權(quán)重用tf-idf表示，計(jì)算公式如下：

N—文本集中總的文章個(gè)數(shù)；

用向量夾角余弦值來表示各個(gè)文章之間的相似度，第i篇文章和第j篇文章之間的相似度為:

3.3 評測方法

給定數(shù)據(jù)集的正確分類結(jié)果D={L1，L2，…Li，…Lm}，第i個(gè)類的數(shù)目記為Li=ni，聚類以后，得到一個(gè)聚類結(jié)果C={c1，F(xiàn)···，cj，···，cm}，其中第j個(gè)簇中數(shù)據(jù)對象的數(shù)目記為cj=nj。在聚類結(jié)果中，類Li中被劃分到類Cj中的數(shù)據(jù)對象的數(shù)目記為Li∩Cj=Nij。

式中P（i，j）—Li中元素在Cj中的正確率；

R（i，j）—Cj中Li元素的召回率。

一個(gè)聚類結(jié)果C的評分是D中所有類別在C中所有簇的最大值F的和。

3.4 實(shí)驗(yàn)分析

第一，運(yùn)行效率對比實(shí)驗(yàn)。從運(yùn)行時(shí)間上進(jìn)行對比，如表3所示，可以看出基于Sollin的快速層次聚類算法比傳統(tǒng)的層次聚類算法的運(yùn)行效率高。

表3 運(yùn)行效率對比

第二，用基于Sollin的快速層次聚類算法分別在復(fù)旦語料和搜狗語料上做實(shí)驗(yàn)，分別用單鏈接、全鏈接和平均鏈接的方法來衡量各個(gè)簇之間的相似度。通過這3種方法的聚類結(jié)果分析得出用平均鏈接來衡量簇與簇之間的相似度最準(zhǔn)確，如表4所示。平均鏈接考慮到了兩簇中各個(gè)樣本點(diǎn)之間的相似性，從而減弱了簇內(nèi)噪聲點(diǎn)的影響。

表4 基于Sollin的快速層次聚類

第三，用傳統(tǒng)的層次聚類算法和基于Sollin的快速層次聚類算法分別在復(fù)旦語料和搜狗語料上做實(shí)驗(yàn)，用平均鏈接來衡量各個(gè)簇之間的相似度。通過對最終的兩個(gè)聚類結(jié)果進(jìn)行比較，證明基于Sollin的快速層次聚類算法的聚類質(zhì)量比傳統(tǒng)的層次聚類算法的聚類質(zhì)量好，且基于Sollin的快速層次聚類算法處理噪聲點(diǎn)和孤立點(diǎn)的能力比傳統(tǒng)的層次聚類算法強(qiáng)，如圖4和圖5所示。

圖4 復(fù)旦語料聚類結(jié)果

圖5 搜狗語料聚類結(jié)果

由圖4和圖5可以看出，復(fù)旦語料的聚類個(gè)數(shù)在10～18類之間時(shí)，搜狗語料的聚類個(gè)數(shù)在5～18類之間時(shí)，基于Sollin的快速層次聚類算法的聚類質(zhì)量要比傳統(tǒng)的層次聚類算法的聚類質(zhì)量高。而當(dāng)聚類個(gè)數(shù)大于18類之后，傳統(tǒng)的層次聚類算法的聚類質(zhì)量高于Sollin算法的聚類質(zhì)量。造成這種現(xiàn)象的主要原因是傳統(tǒng)的層次聚類算法對噪聲點(diǎn)和孤立點(diǎn)的處理力能較弱。

從基于Sollin的快速層次聚類算法的聚類結(jié)果中可以得出，復(fù)旦語料被聚為15類的時(shí)候F值最高（0.771），搜狗語料被聚為5類的時(shí)候F值最高（0.801），且F值隨著聚類的個(gè)數(shù)增加呈下降的趨勢。這表明隨著聚類個(gè)數(shù)的增加同一類的樣本集被分開，從而導(dǎo)致F值下降，進(jìn)而證明基于Sollin的快速層次聚類算法具有較強(qiáng)的處理噪聲點(diǎn)和孤立點(diǎn)的能力。

復(fù)旦語料包含10類文章，搜狗語料包含5類文章，從圖4和5中可以看出在接近正確的聚類個(gè)數(shù)時(shí)，基于Sollin的快速層次聚類算法比傳統(tǒng)的層次聚類算法的聚類質(zhì)量要高很多。

利用基于Sollin的快速層次聚類算法，通過在復(fù)旦語料和搜狗語料上的聚類實(shí)驗(yàn)，證明了基于Sollin的快速層次聚類算法在運(yùn)行效率和聚類質(zhì)量上都優(yōu)于傳統(tǒng)層次聚類算法。但是基于Sollin的快速層次聚類算法也存在問題，如每層聚合過程中每個(gè)簇都會與自己最相近的簇進(jìn)行合并，這樣會造成提前聚類結(jié)束的簇與其他的簇繼續(xù)聚合，會嚴(yán)重影響最終聚類結(jié)果。

[1]蘇喻.基于語義的文本聚類搜索研究[D].合肥:安徽大學(xué),2011.

[2]蔣盛益,李霞.一種改進(jìn)的BIRCH聚類算法[J].計(jì)算機(jī)應(yīng)用,2009(1):293-296.

[3]孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學(xué)報(bào),2008(1):48-61.

[4]陳海珠,鄭卉.基于Sollin算法的最小生成樹求解[J].計(jì)算機(jī)光盤軟件與應(yīng)用,2012(15):92-93.