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

劉 歡

（渤海船舶職業學院，遼寧興城125105）

0 引言

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

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

傳統的層次聚類算法因為合并方法單一且計算量巨大，造成聚類質量大大降低。因此本文提出了基于Sollin的快速層次聚類算法，使得運行效率和聚類質量都有明顯的提升。

1 相關知識

1.1 層次聚類

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

圖1 傳統層次聚類過程

輸入：n個樣本點

輸出：k個類

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

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

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

4） 重復步驟 （2） 和 （3），直到所有數據對象在一個簇中或者達到某個終結條件。

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

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

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

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

圖2 簇間相似性表示方法

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

1.2 Sollin算法

Sollin算法是構建最小生成樹的典型算法，它是基于貪心策略的局部最優算法，與Kruskal算法和Prim算法相比，Sollin算法容易實現并行運算。

Sollin算法構建最小生成樹的基本步驟是將連通圖中所有頂點當作一棵樹，原連通圖就成為了一個森林；然后每棵樹同時決定其連向其他樹的最小權值臨邊（臨邊可以是同一條邊），并與這個最相鄰的節點結合成一棵樹；最后重復上一步驟，直到所有節點都在一棵樹上為止。圖3為Sollin算法構建最小生成樹的實例。

圖3 Sollin算法構建最小生成樹

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

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

輸入：n個數據對象

輸出：k個類

步驟：1）設有n個數據對象，將每個數據對象當作一個簇；

2）計算各簇之間的相似度；

3） 通過Sollin構建最小生成樹的算法將數據合并成m（m＜n）個最小生成樹；

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

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

Sollin算法是構建最小生成樹的典型算法，因此基于Sollin的快速層次聚類算法在每層的聚合過程都可以看作是構建最小生成樹的過程。這樣既可以實現聚類算法的并行運算，提升其聚類效率；又可以消除孤立點單獨成類問題，提升其聚類質量。

3 實驗

3.1 實驗數據

本實驗選擇復旦分類語料和搜狗分類語料（下載于“數據堂”） 作為實驗數據，如表1和表2所示。

表1 復旦語料

表2 搜狗語料

3.2 實驗預處理

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

N—文本集中總的文章個數；

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

3.3 評測方法

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

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

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

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

3.4 實驗分析

第一，運行效率對比實驗。從運行時間上進行對比，如表3所示，可以看出基于Sollin的快速層次聚類算法比傳統的層次聚類算法的運行效率高。

表3 運行效率對比

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

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

第三，用傳統的層次聚類算法和基于Sollin的快速層次聚類算法分別在復旦語料和搜狗語料上做實驗，用平均鏈接來衡量各個簇之間的相似度。通過對最終的兩個聚類結果進行比較，證明基于Sollin的快速層次聚類算法的聚類質量比傳統的層次聚類算法的聚類質量好，且基于Sollin的快速層次聚類算法處理噪聲點和孤立點的能力比傳統的層次聚類算法強，如圖4和圖5所示。

圖4 復旦語料聚類結果

圖5 搜狗語料聚類結果

由圖4和圖5可以看出，復旦語料的聚類個數在10～18類之間時，搜狗語料的聚類個數在5～18類之間時，基于Sollin的快速層次聚類算法的聚類質量要比傳統的層次聚類算法的聚類質量高。而當聚類個數大于18類之后，傳統的層次聚類算法的聚類質量高于Sollin算法的聚類質量。造成這種現象的主要原因是傳統的層次聚類算法對噪聲點和孤立點的處理力能較弱。

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

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

利用基于Sollin的快速層次聚類算法，通過在復旦語料和搜狗語料上的聚類實驗，證明了基于Sollin的快速層次聚類算法在運行效率和聚類質量上都優于傳統層次聚類算法。但是基于Sollin的快速層次聚類算法也存在問題，如每層聚合過程中每個簇都會與自己最相近的簇進行合并，這樣會造成提前聚類結束的簇與其他的簇繼續聚合，會嚴重影響最終聚類結果。

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

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

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

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