文本聚類算法初探

西安外事學(xué)院工學(xué)院 馬軍紅

1.引言

隨著信息技術(shù)的發(fā)展，各種科技文獻(xiàn)以及互聯(lián)網(wǎng)上的信息爆炸式的出現(xiàn)在人們面前，如何自動(dòng)處理大量的數(shù)字化文本已經(jīng)成為文本挖掘、信息過濾和信息檢索等方面的研究成為當(dāng)前研究的熱點(diǎn)?？焖俑哔|(zhì)量的文本聚類技術(shù)可以將大量文本信息組成少數(shù)有意義的簇，能夠提供導(dǎo)航和瀏覽機(jī)制，通過聚類驅(qū)動(dòng)的降維或權(quán)值調(diào)整來(lái)改善檢索性能，是文本信息挖掘技術(shù)中的核心技術(shù)。

2.文本聚類的應(yīng)用與研究

2.1 文本聚類的應(yīng)用

聚類是一種非監(jiān)督學(xué)習(xí)，其類別不是人為指定的而是分析數(shù)據(jù)的結(jié)果，完全由計(jì)算機(jī)自動(dòng)進(jìn)行，不需要人工干預(yù)。

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

1）提供對(duì)一個(gè)大的文本集內(nèi)容的概括；

2）識(shí)別隱藏的共同點(diǎn)；

3）使找到相近或相關(guān)的瀏覽程序簡(jiǎn)單化。

通過比較數(shù)據(jù)的相似性和差異性，能發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在特征及分布規(guī)律，從而獲得對(duì)數(shù)據(jù)更深刻的理解與認(rèn)識(shí)。

2.2 文本聚類算法的特點(diǎn)

文本聚類是在傳統(tǒng)聚類分析的基礎(chǔ)上發(fā)展而來(lái)的，是傳統(tǒng)聚類算法在文本挖掘領(lǐng)域的應(yīng)用?？梢哉f(shuō)它既是一種知識(shí)獲取技術(shù)，也是一種文本處理過程。

文本聚類是基于“聚類假設(shè)”，即：相關(guān)文本之間的相似性比無(wú)關(guān)文本之間的相似性更大。它把一個(gè)文本集分成若干稱為簇（cluster）的子集，每個(gè)簇中的文本之間具有較大的相似性，而簇之間的文本具有較小的相似性。但是，應(yīng)用傳統(tǒng)聚類算法得到的文本聚類結(jié)果在實(shí)踐中并不十分理想。目前，文本聚類的區(qū)別于其他領(lǐng)域的特點(diǎn)主要是集中在以下幾個(gè)方面：

1）文本數(shù)據(jù)是半結(jié)構(gòu)化的數(shù)據(jù)。

在這里的半結(jié)構(gòu)化是指文本數(shù)據(jù)既不是完全結(jié)構(gòu)化的，也不是完全無(wú)結(jié)構(gòu)化的。這就使得一些基于數(shù)據(jù)庫(kù)的算法不能適用于文本聚類，所以文本聚類首先應(yīng)該考慮文本的表示問題。

2）文本數(shù)據(jù)的高維化問題。

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

3）文本聚類與語(yǔ)義的結(jié)合問題。

文本聚類是文本信息處理領(lǐng)域的一個(gè)重要分支，文本信息處理的根本目標(biāo)是使機(jī)器能夠“一定程度上理解并自動(dòng)處理”文本信息，而文本聚類的目的也不外乎是使機(jī)器能夠在“一定程度上理解并自動(dòng)組織”文本信息。換句話說(shuō)，處理只是手段，自動(dòng)組織才是最重的目標(biāo)。如果在文本中出現(xiàn)“足球”和“體育”兩個(gè)名詞，按照傳統(tǒng)的聚類思想，這兩個(gè)詞是毫無(wú)相關(guān)的，但是眾所周知“足球”是“體育”的一項(xiàng)運(yùn)動(dòng)。它屬于“體育”的范疇，并非毫無(wú)相干。那么，在聚類是如何識(shí)別？因此，在語(yǔ)義問題上文本聚類還有很大研究空間。

4）聚類算法中的參數(shù)確定問題。

目前大多數(shù)算法都需要預(yù)先輸入一些參數(shù)，這些參數(shù)設(shè)置的準(zhǔn)確與否直接影響到文本聚類的效率和結(jié)果，預(yù)先輸入的參數(shù)是在這樣一個(gè)前提下：人們已經(jīng)知道這些參數(shù)或知道大致范圍。而實(shí)際上在大多數(shù)情況下，做到這一點(diǎn)非常困難。

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

3.1 基于劃分的算法

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

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

K－means算法的優(yōu)點(diǎn)是：

1）對(duì)數(shù)值屬性有很好的幾何和統(tǒng)計(jì)意義；

2）對(duì)順序不太敏感；

3）對(duì)凸型聚類有較好結(jié)果；

4）可在任意范數(shù)下進(jìn)行聚類。

缺點(diǎn)是：

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

2）關(guān)于K值的確定沒有可行的依據(jù)；

3）聚類結(jié)果有時(shí)會(huì)失衡；

4）對(duì)“噪聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該數(shù)據(jù)能對(duì)平均值產(chǎn)生很大的影響。

3.2 層次聚類算法

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

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

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

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

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

Step4.重復(fù)以上步驟，直至C中剩下一個(gè)類或者達(dá)到一終止條件。

層次聚類算法的優(yōu)點(diǎn)是適用于任意形狀，適用于任意形式的相似度或距離形式，固有的對(duì)聚類粒度的靈活性。缺點(diǎn)是終止條件不很精確，一旦聚類結(jié)果形成，一般不再重新構(gòu)建提高聚類性能，并且難以適應(yīng)動(dòng)態(tài)數(shù)據(jù)集，計(jì)算復(fù)雜度非線性。

3.3 基于模型的方法

基于模型的方法為每個(gè)簇假設(shè)一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。它試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。這樣的方法經(jīng)常是基于這樣的假設(shè)：數(shù)據(jù)是根據(jù)潛在的概率分布產(chǎn)生的。基于模型的方法主要有兩類：統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。

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

4.分析與總結(jié)

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

目前，各種算法的融合問題也是比較熱門的研究方向。通過對(duì)各種聚類算法的研究分析，發(fā)現(xiàn)聚類算法的優(yōu)缺點(diǎn)，將其他算法引入聚類算法中以達(dá)到優(yōu)化改進(jìn)聚類算法的某一過程，從而達(dá)到提高聚類算法性能的目的。

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

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

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