文本聚類算法初探

西安外事學院工學院 馬軍紅

1.引言

隨著信息技術的發展，各種科技文獻以及互聯網上的信息爆炸式的出現在人們面前，如何自動處理大量的數字化文本已經成為文本挖掘、信息過濾和信息檢索等方面的研究成為當前研究的熱點。快速高質量的文本聚類技術可以將大量文本信息組成少數有意義的簇，能夠提供導航和瀏覽機制，通過聚類驅動的降維或權值調整來改善檢索性能，是文本信息挖掘技術中的核心技術。

2.文本聚類的應用與研究

2.1 文本聚類的應用

聚類是一種非監督學習，其類別不是人為指定的而是分析數據的結果，完全由計算機自動進行，不需要人工干預。

文本聚類一般可以用于以下幾個方面：

1）提供對一個大的文本集內容的概括；

2）識別隱藏的共同點；

3）使找到相近或相關的瀏覽程序簡單化。

通過比較數據的相似性和差異性，能發現數據的內在特征及分布規律，從而獲得對數據更深刻的理解與認識。

2.2 文本聚類算法的特點

文本聚類是在傳統聚類分析的基礎上發展而來的，是傳統聚類算法在文本挖掘領域的應用。可以說它既是一種知識獲取技術，也是一種文本處理過程。

文本聚類是基于“聚類假設”，即：相關文本之間的相似性比無關文本之間的相似性更大。它把一個文本集分成若干稱為簇（cluster）的子集，每個簇中的文本之間具有較大的相似性，而簇之間的文本具有較小的相似性。但是，應用傳統聚類算法得到的文本聚類結果在實踐中并不十分理想。目前，文本聚類的區別于其他領域的特點主要是集中在以下幾個方面：

1）文本數據是半結構化的數據。

在這里的半結構化是指文本數據既不是完全結構化的，也不是完全無結構化的。這就使得一些基于數據庫的算法不能適用于文本聚類，所以文本聚類首先應該考慮文本的表示問題。

2）文本數據的高維化問題。

文本集合所采用的向量空間模型表示法會使向量空間的維度非常高，一般在103-104的量級上，高維數據和以往的聚類對象最重要的區別在于：在高維空間中，如果仍然采用距離作為衡量對象之間相似度的標準，經計算，有時距離很近的對象反而比距離很遠的對象之間的差別大。這意味著基于距離的距離算法不再那么有效，大量采用距離尺度的傳統聚類算法將很難取得令人滿意的聚類效果。因此，特征集的縮減成為文本聚類中必不可少的一步。

3）文本聚類與語義的結合問題。

文本聚類是文本信息處理領域的一個重要分支，文本信息處理的根本目標是使機器能夠“一定程度上理解并自動處理”文本信息，而文本聚類的目的也不外乎是使機器能夠在“一定程度上理解并自動組織”文本信息。換句話說，處理只是手段，自動組織才是最重的目標。如果在文本中出現“足球”和“體育”兩個名詞，按照傳統的聚類思想，這兩個詞是毫無相關的，但是眾所周知“足球”是“體育”的一項運動。它屬于“體育”的范疇，并非毫無相干。那么，在聚類是如何識別？因此，在語義問題上文本聚類還有很大研究空間。

4）聚類算法中的參數確定問題。

目前大多數算法都需要預先輸入一些參數，這些參數設置的準確與否直接影響到文本聚類的效率和結果，預先輸入的參數是在這樣一個前提下：人們已經知道這些參數或知道大致范圍。而實際上在大多數情況下，做到這一點非常困難。

3.常用聚類算法及其分析

3.1 基于劃分的算法

給定n個對象的數據集，基于劃分方法構建數據的k個劃分，每個劃分表示一類，并滿足：每個劃分至少包含一個對象；每個對象必須屬于并且只屬于一個劃分。其基本思想是給定要構建的劃分數目k，首先創建一個初始劃分，然后采用一種迭代的重定位技術，嘗試通過對象在劃分間移動來改進劃分。其典型算法是K-means，其原理是：

首先從數據集合X={X1，X2，……Xn}中隨機地選取k個對象，每個對象初始地代表了一個簇的中心。對于X中任意對象Xi，計算它到各個簇中心的距離(采用歐式距離或者余弦相似度)，根據其與各個簇中心的距離，將它賦給最近的簇。然后重新計算每個簇的中心(計算簇中數據的平均值)。這個過程不斷重復，直到簇中心不再發生改變或準則函數收斂。

K－means算法的優點是：

1）對數值屬性有很好的幾何和統計意義；

2）對順序不太敏感；

3）對凸型聚類有較好結果；

4）可在任意范數下進行聚類。

缺點是：

1）對初始聚類中心選取較敏感，往往得不到全局最優解，而常常得到的是次優解；

2）關于K值的確定沒有可行的依據；

3）聚類結果有時會失衡；

4）對“噪聲”和孤立點數據是敏感的，少量的該數據能對平均值產生很大的影響。

3.2 層次聚類算法

層次聚類算法是對給定的對象集合進行層次的分解。其基本思想是將模式樣本按距離準則逐步聚類，直到滿足分類為止，其聚類過程可表示為一棵二叉層次樹，葉節點表示一個樣本，中間節點便是將數據分成兩個不同的類，或者是一個類由它的兩個子類合并而成。根據層次的分解形成原理，層次的方法可分為凝聚方法和分裂方法。

如果給定文檔集合是D={d1；d2；……dn}，層次凝聚法的具體步驟如下：

Step1.將D中的每個文檔di試看作是一個具有單個成員的類ci={di}，這些類構成了的一個聚類C={C1；C2；……Cn}；

Step2.計算C中每對類{Ci，Cj}之間的相似度Sim（Ci，Cj）；

Step3.選取具有最大相似度的類對argmax Sim（Ci，Cj），并將Ci和Cj合并為一個新的類，從而構成了的一個新的聚類C={C1；C2；……Cn-1}；

Step4.重復以上步驟，直至C中剩下一個類或者達到一終止條件。

層次聚類算法的優點是適用于任意形狀，適用于任意形式的相似度或距離形式，固有的對聚類粒度的靈活性。缺點是終止條件不很精確，一旦聚類結果形成，一般不再重新構建提高聚類性能，并且難以適應動態數據集，計算復雜度非線性。

3.3 基于模型的方法

基于模型的方法為每個簇假設一個模型，尋找數據對給定模型的最佳擬合。它試圖優化給定的數據和某些數學模型之間的適應性。這樣的方法經常是基于這樣的假設：數據是根據潛在的概率分布產生的。基于模型的方法主要有兩類：統計學方法和神經網絡方法。

除了以上介紹的幾類聚類算法，還有許多其他的聚類算法。

4.分析與總結

文本聚類是典型的高維數據的聚類，因而也具有一般高維聚類的特點。以前的研究著重于層次聚類算法，隨著web文檔的高速增長，由于傳統的層次聚類時間復雜度的非線性，它難以處理日益增多的數據量。出于效率考慮，當前人們更多研究的是如何改進平面劃分算法（比如k-means、SOM算法）。

目前，各種算法的融合問題也是比較熱門的研究方向。通過對各種聚類算法的研究分析，發現聚類算法的優缺點，將其他算法引入聚類算法中以達到優化改進聚類算法的某一過程，從而達到提高聚類算法性能的目的。

[1]馮少榮,肖文俊.基于語義距離的高效文本聚類算法[J].華南理工大學學報,2008,36(5).

[2]丘志宏,宮雷光.利用上下文提高文本聚類的效果[J].中文信息學報,2007,21(6).

[3]尉景輝,何丕廉，,孫越恒.基于k-means的文本層次聚類算法研究[J].計算機應用,2010(10).