基于Canopy+K-means的中文文本聚類算法*

張 琳，牟向偉

0 引言

互聯(lián)網(wǎng)的普及使得在線電子文本資源劇增，也使文本成為信息傳播的主要載體。文本數(shù)據(jù)是一種半結(jié)構(gòu)化數(shù)據(jù)，具有高維、數(shù)據(jù)量大、與上下文相關(guān)，甚至存在一詞多義或多詞一義等特點。所以，與結(jié)構(gòu)化數(shù)據(jù)相比，文本數(shù)據(jù)大大增加了數(shù)據(jù)處理和知識發(fā)現(xiàn)的難度。因此，如何對網(wǎng)上的文本數(shù)據(jù)進行快速、有效的分析，并挖掘其中隱藏的價值是一個亟待解決的問題。文本聚類是解決這個問題的一種可行方法。

文本聚類是文本挖掘過程的一項關(guān)鍵技術(shù)，它根據(jù)一定的標準通過將文本劃分到有意義的幾個簇中，使同一個簇中文本之間的相似度高于不同簇間文本之間的相似度[1]，從而實現(xiàn)對文本信息的有效組織和管理。有效的文本聚類可以幫助人們更好地理解和導航信息檢索工具的檢索結(jié)果[2]，例如在信息檢索領(lǐng)域，Scatter/Gather[3]系統(tǒng)通過采用非監(jiān)督式的聚類方法(如K-m eans)對搜索結(jié)果進行劃分來幫助用戶理解和消化檢索結(jié)果；可以為用戶根據(jù)實際需要深入挖掘某一特定主題提供自由[4]；可以促進引文分析，自動文摘，科技信息檢索等研究的發(fā)展[5]，等等。

文本聚類技術(shù)發(fā)展迅速，相應地產(chǎn)生了很多聚類算法。這些算法大致可分為兩類：基于劃分的方法和基于層次的方法[6]。在這些聚類方法中，應用最廣泛的是以劃分為基礎的K-m eans算法。K-m eans算法在聚類時需要事先指定簇的個數(shù)k和k個初始中心點，但往往我們無法預先確定簇的個數(shù)并選擇合適的初始聚類中心，這會導致K-m eans聚類的誤差很大，甚至可能陷入局部最優(yōu)。針對K-m eans算法這兩方面的不足，不同學者從不同角度對其進行了改進。

例如，針對K-m eans初始聚類中心隨機選擇的問題，文獻[7]提出了一種基于LDA主題概率模型的初始聚類中心選擇算法，即先從文本集中選擇m個主題，并在這m個主題所在的維度上對文本集進行初步聚類，得到k個聚類中心后，再以這k個聚類中心為初始聚類中心對文本集在所有維度上進行聚類；文獻[8]通過不斷尋找最大聚類(即包含數(shù)據(jù)對象最大的一個類)，并利用最大聚類中距離最大的兩個數(shù)據(jù)對象作為聚類中心對數(shù)據(jù)集進行劃分，如此反復，直到找出k個聚類中心為止；文獻[9]則通過引入密度和最近鄰的思想，提出了初始聚類中心選擇算法，該算法提高了K-m eans算法的聚類質(zhì)量和穩(wěn)定性。針對K-m eans無法預先確定k值的問題，文獻[10]通過樣本數(shù)據(jù)分層來確定算法的聚類范圍，并利用類內(nèi)、類間夾角余弦值的比值作為聚類有效性指標，從而在聚類數(shù)范圍內(nèi)獲得最佳聚類數(shù)。與同類算法相比，該算法的運行效率較高，能夠得到良好的聚類效果；文獻[11]根據(jù)類內(nèi)相似度最大差異度最小和類間差異度最大相似度最小的原則，提出了一種基于距離評價函數(shù)的k值檢驗方法，并通過實驗驗證了算法的有效性；文獻[12]利用二分思想遞歸分裂簇內(nèi)相似度大于給定閾值的簇，通過合并簇間相似度小于給定閾值的簇來獲得最終聚類數(shù)目。

上述研究都是針對K-m eans某一方面的問題進行的改進。為了提高K-m eans算法的聚類效果，本文在對中文文本進行聚類時，采用Canopy和K-m eans相結(jié)合的聚類算法，將Canopy聚類作為K-m eans聚類的前奏，為K-m eans提供k值和初始聚類中心點。

1 文本預處理

1.1 基于Word2vec的詞語相似度計算

W ord2vec是谷歌在2013年開源的一款語言建模工具，它以文本集為輸入，通過訓練生成每個詞對應的詞向量。這些詞向量可以作為詞的特征應用到一些自然語言處理問題中，比如中文分詞、尋找同義詞、進行詞性分析，等等[13]。W ord2vec實現(xiàn)了兩種訓練模型CBOW(Continuous Bag-O f-W ords)和Skip-gram模型[14]，如圖1所示。其中，CBOW模型是通過上下文來預測當前詞出現(xiàn)的概率；Skip-gram模型與CBOW模型相反，它是通過當前詞來預測其上下文詞語出現(xiàn)的概率。為了提高詞向量的訓練效率，W ord2vec提供了兩種詞向量優(yōu)化模型，分別是Hierarchy Softm ax模型和Negative Sam pling模型。

本文采用搜狗實驗室提供的全網(wǎng)新聞語料(http：//www.sogou.com/labs/resource/ca.php，該語料包含若干新聞站點2012年6～7月間國內(nèi)、國際、體育、社會和娛樂等18個頻道的新聞數(shù)據(jù))訓練Word2vec模型，并利用訓練好的模型獲得某一個詞語的同義詞或近義詞。具體步驟包括：

(1)獲取所有新聞＜content＞＜/content＞標簽之間的內(nèi)容。

(2)采用 NLPIR2016工具(http：//ictclas.nlpir.org/)進行分詞，并對分詞結(jié)果進行停用詞過濾和詞性標注，保留名詞、動詞和形容詞，同時刪除分詞結(jié)果中僅有一個字的詞語，最后將得到的所有詞語以空格隔開。

(3)執(zhí)行w ord2vec-train命令，采用Skipgram訓練模型和Hierarchy Softm ax優(yōu)化模型對分好詞的訓練語料進行訓練，得到詞向量，進而得到詞典D的詞匯相似矩陣。

(4)利用訓練好的Word2vec模型，獲得某一個詞語的同義詞或近義詞。方法是：輸入詞語，獲得該詞語在詞典D中的詞向量表征，然后遍歷詞典D，通過向量夾角余弦公式計算該詞向量與詞典D中其他詞向量之間的相似度，從而可以得到詞典D中與該詞語最相似的top N個詞語。

1.2 特征詞權(quán)重計算

TF-IDF(Term Frequency-Inverse Docum ent Frequency)[15]是一種應用較為廣泛的權(quán)值計算方法。其中，TF指的是詞頻，IDF指的是逆向文檔頻率。TF-IDF的基本思想是：如果某個詞項或短語在某篇文檔中頻繁出現(xiàn)(TF很高)，但是在文本集的其他文檔中甚少出現(xiàn)(IDF很高)，那么這個詞項或短語對這篇文檔具有很好的辨識能力。對于這樣的詞項、短語，我們應該賦予較高的權(quán)重。相反，如果某個詞項或短語在文本集的大多數(shù)文檔中出現(xiàn)的頻率都很高，那么根據(jù)這個詞項或短語很難將包含它的多篇文檔區(qū)分開來。因此，對于這樣的詞項或短語，我們應該賦予較低的權(quán)重。

TF-IDF的基本形式如式(1)所示：

其中，wt，D表示詞項t在文檔D中的權(quán)重；tft，D表示詞項t在文檔D中出現(xiàn)的頻次；N表示文檔集的大小；dft表示包含詞項t的文檔總數(shù)。本文根據(jù)式(2)對出現(xiàn)頻次tf進行歸一化表示，其中，doc_length表示文檔長度。

1.3 文本表示

最常用的文本表示方法是基于向量空間模型的方法。向量空間模型的基本思想[16]是：每一篇文檔都可以被表示成一個由預先規(guī)定好詞序的多個詞項組成的高維空間的一個向量。規(guī)定好次序的詞項可以看作是向量空間的維度，詞項的個數(shù)決定向量的維數(shù)，詞項的權(quán)重則表示詞項在文檔中的重要程度，可以看作是向量在高維空間某一維上的取值。

基于向量空間模型可以將每一篇文檔表示成如式(3)所示的向量形式：

其中，D表示一篇文檔；m表示向量的維數(shù)，其大小由文本集中不同的詞項個數(shù)決定；ti表示文本集中的一個詞項；W ti，D表示詞項ti在文檔D中的權(quán)重(即重要性)。

2 Canopy+K-means算法

2.1 Canopy算法

Canopy算法是一種快速近似的聚類技術(shù)。它的優(yōu)勢在于得到簇的速度非?？欤恍璞闅v一次數(shù)據(jù)即可得到結(jié)果，正因為如此，Canopy算法無法給出精準的簇結(jié)果[17]。

Canopy算法的基本流程如下[18]：

(1)確定Canopy的兩個距離閾值，即T1和T2，其中T1＞T2。

(2)從數(shù)據(jù)集中任取一個數(shù)據(jù)對象，計算它與所有Canopy中心之間的距離。

(3)如果當前不存在Canopy，則把該數(shù)據(jù)對象作為一個Canopy中心，并將它從數(shù)據(jù)集中刪除。否則，轉(zhuǎn)(4)。

(4)如果該數(shù)據(jù)對象到某個Canopy中心的距離在T2以內(nèi)，則把它添加到這個Canopy中，同時將它從數(shù)據(jù)集中刪除。因為該數(shù)據(jù)對象與此Canopy距離很近，因此它不可以再作為其他 Canopy中心。

(5)如果該數(shù)據(jù)對象到某個Canopy中心的距離在T2以外T1以內(nèi)，同樣把該數(shù)據(jù)對象添加到這個Canopy中，但是此時并不從數(shù)據(jù)集中刪除這個數(shù)據(jù)對象。也就是說，這個數(shù)據(jù)對象將參與下一輪的聚類過程。

(6)如果該數(shù)據(jù)對象到所有Canopy中心的距離都在T1以外，則把它作為一個Canopy中心，同時將它從數(shù)據(jù)集中刪除。

(7)重復迭代(2)到(6)，直到數(shù)據(jù)集中所有數(shù)據(jù)對象都劃分到了相應的Canopy。

2.2 K-means算法

K-m eans算法的核心思想是，通過迭代把所有數(shù)據(jù)對象劃分到k個不同的簇中，以使簇內(nèi)對象具有較高的相似度，而各個簇之間的對象具有較低的相似度。

K-m eans算法的基本流程如下[19]：

(1)輸入數(shù)據(jù)集D和要劃分的簇的數(shù)目k。

(2)從D中任意選擇k個對象作為初始簇中心。

(3)計算簇中任一對象到各個簇中心的距離，將其分配到距離最近的簇中心所在的簇。

(4)重新計算每個簇中所有數(shù)據(jù)對象的平均值，將其作為新的簇中心。

(5)重復(3)(4)，直到簇心不發(fā)生改變或者達到最大迭代次數(shù)。

2.3 Canopy+K-means算法

圖2 Canopy+K-means算法的聚類流程

在基于向量空間模型將文本表示成一個由特征詞TF-IDF權(quán)值表示的特征向量后，本文采用余弦公式衡量文本之間的相似度。在進行Canopy“粗”聚類時，設定T1＜T2，且設置T1和T2的取值都與文本集中所有文本的平均相似度相關(guān)。另外，為了防止Canopy中心點選取過密而導致算法陷入局部最優(yōu)，本文選擇離所有樣本點的中心最近的一個樣本作為第一個Canopy中心。Canopy+K-m eans算法的聚類流程如圖2所示。

總的來說，在對中文文本進行聚類時，為了解決K-m eans算法無法預先確定聚類數(shù)目和隨機選擇初始聚類中心點的問題，本文先使用Canopy算法對數(shù)據(jù)集進行“粗”聚類，在得到k值后，再使用K-m eans算法進行“細”聚類，并且將Canopy算法選擇出來的每個Canopy的近似中心位置作為K-m eans的初始中心點，以此來提高K-m eans算法的聚類效果。

3 文本聚類結(jié)果評價

對聚類算法進行評價主要可以采用三類有效性評價準則[20]：內(nèi)部準則、外部準則和相對準則。本文主要采用四種外部評價準則[21]對聚類結(jié)果進行評價。

(1)純度(purity)：是一個簡單、明晰的評價指標，它將每個簇分配給該簇中出現(xiàn)數(shù)目最多的文檔所在的類別，并通過正確分配的文檔數(shù)除以文檔總數(shù)N得到聚類的精度。purity的計算方法如式(4)所示。

其中，Ω={W1，W2，…，WK}是聚類的結(jié)果，C={C1，C2，…，CJ}是類別集合，Wk(k=1，2，…，K)和Cj(j=1，2，…，J)是由文檔組成的文檔集合。

(2)準確率(precision)：衡量的是每個簇中某一特定類別的對象所占的比例。其計算方法如式(5)所示。

其中，TP(True-positive，真陽性)指的是將兩篇相似文檔正確歸入同一個簇的決策；FP(False-positive，假陽性)指的是將兩篇不相似文檔錯誤歸入同一簇的決策。

(3)召回率(recall)：衡量的是每個簇包含某個特定類別的所有對象的程度。其計算方法如式(6)所示。

其中，F(xiàn)N(False-negative，假陰性)指的是將兩篇相似文檔歸入不同簇的決策。

(4)F-M easure：是一種綜合準確率和召回率的聚類評價指標，其計算方法如式(7)所示。

其中，β為調(diào)和系數(shù)，一般取β=1。

4 基于Canopy+K-means的中文文本聚類流程

本文采用NLPIR2016對中文文本集進行分詞和詞性標注，并剔除了分詞結(jié)果中對文檔主旨沒有任何提示作用的停用語，如“為何”“與其”“人們”等，以及一些數(shù)字和符號。一般而言，名詞、動詞和形容詞是句子的重要組成成分。因此，為了抽取能夠表征文檔主要內(nèi)容的詞語，對于停用詞過濾后的分詞結(jié)果，本文只保留名詞、動詞和形容詞三種詞性的詞語，去重之后將它們作為候選特征詞。

中文詞語之間有時會存在“多詞一義”的情況，因此，為了降低文本向量的維度，避免給文本向量的計算造成困難，本文基于W ord2vec生成詞向量，獲得候選特征詞之間的同義詞或近義詞，同時合并同義詞或近義詞在同一篇文檔中出現(xiàn)的詞頻及在文本集中出現(xiàn)的文檔列表。

在對文本集進行上述預處理之后，采用向量空間模型將每一篇文檔表示成一個由特征詞TFIDF權(quán)重組成的向量形式；然后使用Canopy+K-m eans算法對文本集進行類別劃分；最后基于純度、準確率、召回率和Fvalue對聚類效果進行評價?；贑anopy+K-m eans的中文文本聚類流程如圖3所示。

5 實驗

為了驗證Canopy+K-m eans算法的有效性，本文選取了兩個文本數(shù)據(jù)集，分別利用Canopy+K-m eans和K-m eans算法對它們進行類別劃分，并基于purity、precision、recall和F值對這兩種算法的聚類結(jié)果進行評價。

圖3 基于Canopy+K-means中文文本聚類流程

在基于Canopy+K-m eans算法進行文本聚類時，本文設置T2為文本集中所有文本的平均相似度，T1=1/2*T2。在基于傳統(tǒng)K-m eans算法進行文本聚類時，由于K-m eans算法需要預先確定k值，在實驗中本文設定k為文本集的實際類別數(shù)。另外，由于K-m eans算法的聚類效果與初始中心點的選取有關(guān)，因此為了更好地體現(xiàn)K-m eans算法的性能，本文在基于傳統(tǒng)K-m eans算法進行文本聚類時，重復運行該算法100次，取100次聚類評價指標的平均值作為K-m eans算法的性能評價。

實驗一：搜狗文本分類語料(http：//www.sogou.com/labs/resource/tce.php)是一個包含汽車、財經(jīng)、IT、健康、體育等18類新聞的數(shù)據(jù)集。本文從該數(shù)據(jù)集中選取了汽車、娛樂、體育、教育、IT和財經(jīng)六個類別3600篇新聞(每個類別各600篇)作為實驗數(shù)據(jù)集。實驗數(shù)據(jù)集中每篇新聞的字數(shù)在300～2000之間，較多集中于500字左右。Canopy+K-m eans算法和K-m eans算法對該數(shù)據(jù)集的聚類結(jié)果評價如表1所示。

表1 搜狗文本分類語料Canopy+K-m eans算法和K-means算法的聚類效果評價

實驗二：網(wǎng)易分類文本數(shù)據(jù)(http：//www.datatang.com/data/11965)是一個包含運動、汽車、經(jīng)濟、醫(yī)藥、體育和文化六個類別的文本數(shù)據(jù)集，該數(shù)據(jù)集的每一個文本為一篇新聞，字數(shù)在300～3000之間，較多集中于1000字左右。本文從該數(shù)據(jù)集每一個類別的新聞中各選取100條數(shù)據(jù)作為實驗數(shù)據(jù)集。兩種算法對該數(shù)據(jù)集的聚類結(jié)果評價如表2所示。

表2 網(wǎng)易分類文本數(shù)據(jù)Canopy+K-m eans算法和K-means算法的聚類效果評價

上述兩個實驗在設置了T1和T2后，Canopy算法將數(shù)據(jù)集劃分成了六類，為K-m eans算法提供了k值和初始聚類中心點。從表1和表2可以看出，無論是purity、precision、recall，還是F值，Canopy+K-m eans算法的聚類效果要明顯優(yōu)于K-m eans算法。這說明，相比于傳統(tǒng)的K-m eans算法，Canopy+K-m eans算法除了可以自動產(chǎn)生k值外，Canopy聚類也可以為K-m eans提供較好的初始聚類中心點，從而使Canopy+K-m eans算法的聚類結(jié)果更接近文本的真實類別。

6 結(jié)論

本文針對傳統(tǒng)K-m eans算法在聚類時需要預先確定k值和聚類效果受初始聚類中心影響的問題，將Canopy算法和K-m eans算法進行結(jié)合得到Canopy+K-m eans算法，并將其應用于中文文本分類中；闡述了Canopy+K-m eans算法的實現(xiàn)流程及基于Canopy+K-m eans算法的中文文本聚類步驟，并通過具體的實驗分析了基于該算法進行中文文本聚類的可行性。由于Canopy算法在聚類時需要確定閾值T1和T2，而T1和T2的大小會直接影響分類的準確率，因此如何更好地確定T1和T2取值是本文接下來的研究重點。另外，實驗也將選取更大的數(shù)據(jù)集并基于Hadoop平臺實現(xiàn)對大規(guī)模文本集的類別劃分。

[1]曹曉.文本聚類研究綜述[J].情報探索，2016（1）：131-134．

[2]Zeng，H J，He，Q C，Chen，Z，et al.Learning to cluster web search results[C]//Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval.ACM，2004：210-217.

[3]Cutting，D R，Karger，D R，Pedersen JO，etal.Scatter/gather：A cluster-based approach to browsing large document collections[C]//Proceedingsof the 15th annual international ACM SIGIR conference on Research and development in information retrieval，1992：318-329.

[4]王小華，徐寧，諶志群.基于共詞分析的文本主題詞聚類與主題發(fā)現(xiàn)[J].情報科學，2011，29（11）：1621-1624.

[5]劉遠超，王曉龍，徐志明，等.文檔聚類綜述[J].中文信息學報，2006，20（3）：55-62.

[6]趙世奇，劉挺，李生.一種基于主題的文本聚類方法[J].中文信息學報，2007，21（2）：58-62.

[7]王春龍，張敬旭.基于LDA的改進K-means算法在文本聚類中的應用[J].計算機應用，2014，34（1）：249-254.

[8]陳光平，王文鵬，黃俊.一種改進初始聚類中心選擇的K-means算法[J].小型微型計算機系統(tǒng)，2012，33（6）：1320-1323.

[9]張文明，吳江，袁小蛟.基于密度和最近鄰的K-means文本聚類算法[J].計算機應用，2010，30（7）：1933-1935.

[10]王勇，唐靖，饒勤菲，等.高效率的K-means最佳聚類數(shù)確定算法[J].計算機應用，2014，34（5）：1331-1335.

[11]韓凌波.K-均值算法中聚類個數(shù)優(yōu)化問題研究[J].四川理工學院學報（自然科學版），2012，25（2）：77-80.

[12]張忠平，王愛杰，柴旭光.簡單有效的確定聚類數(shù)目算法[J].計算機工程與應用，2009，45（15）：166-168.

[13]李躍鵬，金翠，及俊川.基于word2vec的關(guān)鍵詞提取算法[J].科研信息化技術(shù)與應用，2015，6（4）：54-59.

[14]周練.W ord2vec的工作原理及應用探究[J].科技情報開發(fā)與經(jīng)濟，2015，25（2）：145-148.

[15]Salton，G Buckley，C.Term-weighting approachesin automatic text retrieval[J].Information Processing&Management，1988，24（5）：513-523.

[16]郭慶琳，吳克河，吳慧芳，等.基于文本聚類的多文檔自動文摘研究[J].計算機研究與發(fā)展，2007，44（2）：140-144.

[17]Sean O，Robin A，Ted D，etal.Mahout實戰(zhàn)[M].北京：人民郵電出版社，2014：134-138.

[18]M cCallum A， Nigam K， Ungar L H.Efficient clustering ofhigh-dimensionaldata setswith application to reference matching[C]//Proceedings of the sixth ACM SIGKDD international conference on Know ledge discovery and datam ining，2000：169-178.

[19]Han JW，Kamber M，Pei J.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機械工業(yè)出版社，2012：293-295.

[20]Xu R，W unsch D C.C lustering[M].IEEE Press，2008：265-277.

[21]Manning C D，Raghavan P，Schütze H.信息檢索導論[M].北京：人民郵電出版社，2010：246-249.