一種改進的k均值文本聚類算法

張銀明，黃廷磊，林　科，張嬙嬙

(桂林電子科技大學(xué) 計算機與信息安全學(xué)院，廣西 桂林　541004)

?

一種改進的k均值文本聚類算法

張銀明，黃廷磊，林科，張嬙嬙

(桂林電子科技大學(xué) 計算機與信息安全學(xué)院，廣西 桂林541004)

針對k均值算法在文本聚類中由于初始聚類質(zhì)心隨機選擇，使得聚類結(jié)果陷入局部最優(yōu)，且孤立點和不確定的聚類個數(shù)造成k均值算法準確性低、收斂速度慢的問題，提出了一種改進的k均值文本聚類算法。該算法采用fp-growth算法挖掘文本頻繁項集，過濾頻繁項集得到核心頻繁項集，并利用核心頻繁項集指導(dǎo)文本初始聚類質(zhì)心和聚類個數(shù)的生成，最后k均值算法利用初始聚類質(zhì)心和聚類個數(shù)完成文本聚類。在新浪微博數(shù)據(jù)集上進行文本聚類實驗，實驗結(jié)果表明，改進的k均值算法提高了文本聚類的準確性，加快了收斂速度，具有較強的魯棒性。

文本聚類；fp-growth；k均值

隨著網(wǎng)絡(luò)信息的爆炸式增長，在海量文本中高效、準確地提煉有價值的信息已成為研究熱點。文本聚類作為文本挖掘的重要手段，將有價值的信息通過文本聚集呈現(xiàn)，是一個自動劃分類別的過程。k均值算法簡單易懂，是應(yīng)用最廣泛的聚類方法，但k均值算法存在2個不足：1)在聚類之前需要確定數(shù)據(jù)的聚類個數(shù)；2)初始聚類質(zhì)心的隨機選擇導(dǎo)致聚類結(jié)果局部最優(yōu)而非全局最優(yōu)。針對上述不足，李小武等[1]提出了基于最優(yōu)劃分的k均值初始聚類中心選取算法，該算法通過劃分樣本確定初始聚類中心的分布，但文本維數(shù)較高時遞歸次數(shù)增多。Krishna等[2]采用k均值聚類算法和二分k均值聚類算法分別對文本進行聚類，二分k均值聚類算法不會出現(xiàn)聚類結(jié)果局部最優(yōu)，效果優(yōu)于k均值聚類算法。Liu等[3]提出了內(nèi)核k均值算法，減少了非線性支持向量機的訓(xùn)練樣本，在保持較高的測試精度的同時降低了采樣時間的復(fù)雜度。然而，這些算法未考慮聚類個數(shù)，導(dǎo)致聚類效率低，聚類效果不理想。為此，基于fp-growth算法，提出了一種改進的k均值文本聚類算法。

1　算法的基本思想和框架

1.1k均值文本聚類算法

k均值文本聚類算法首先對文本進行分詞，然后采用tf-idf、vsm算法對特征詞和特征詞的頻度建模[4]，將文本映射為n維的特征向量，并通過特征向量測量文本之間的語義距離，最后利用k均值算法對文本進行聚類。例如，對3篇文章進行分詞并提取特征，可得特征向量

(1)

其中ai、bi、ci(i=1，2，…，n)分別表示特征在3篇文章中出現(xiàn)的次數(shù)，n為文章的特征數(shù)。向量空間模型采用特征向量余弦測量文章的相似度。余弦值越大，則文章相似度越差，否則文章相似度越好。特征向量余弦

(2)

其中：文本特征向量A=(a1,a2,…,an)，B=(b1,b2,…,bn)。

k均值算法流程[5]為：

1)通過隨機函數(shù)，創(chuàng)建k個起始質(zhì)心。

2)計算文本項與每個質(zhì)心的相似度，將文本項分配到相似度值最小的簇。

3)重新計算每個簇的質(zhì)心，質(zhì)心為簇中文本項特征出現(xiàn)次數(shù)的平均值。若質(zhì)心收斂，則聚類完成，否則繼續(xù)步驟2)。

k均值算法由于質(zhì)心的隨機性導(dǎo)致聚類結(jié)果局部最優(yōu)，若隨機選擇的質(zhì)心是孤立點，則孤立點將單獨成為一個簇，而且影響其他簇的生成，這與聚類的目的相違背[6]。

1.2改進的k均值算法

改進的k均值算法采用fp-growth算法挖掘文本的頻繁項集，過濾頻繁項集得到核心頻繁項集，并利用核心頻繁項集指導(dǎo)k均值算法的初始聚類質(zhì)心和簇的個數(shù)，最后結(jié)合k均值算法完成文本聚類。fp-growth算法挖掘的初始聚類質(zhì)心降低了k均值算法的計算復(fù)雜度，避免了孤立點對k均值算法的影響。主要表現(xiàn)為：

1)核心頻繁項集代表數(shù)據(jù)集中表達主題的個數(shù)，精確地描述了聚類個數(shù)。

2)通過核心頻繁項集得到的初始聚類質(zhì)心在文本相似度上屬于每個簇，減少了聚類過程的迭代次數(shù)。

fp-growth算法將數(shù)據(jù)存儲于高度壓縮的數(shù)據(jù)結(jié)構(gòu)fp-tree，減少了多次遍歷數(shù)據(jù)庫，而且fp-growth算法通過統(tǒng)計元素項、挖掘頻繁項建立fp-tree，并采用遞增的方式利用條件fp-tree挖掘頻繁項集[7]。

fp-growth算法挖掘頻繁項集的過程為：對給定的事物數(shù)據(jù)庫進行2次掃描，第一次掃描數(shù)據(jù)庫，得到元素項的出現(xiàn)次數(shù)為w，設(shè)定出現(xiàn)次數(shù)閾值ε1，若w>ε1，則該元素項稱為頻繁項。由于fp-tree是一棵有序的樹，且挖掘條件模式基依賴頻繁元素的出現(xiàn)次數(shù)，因此第二次掃描數(shù)據(jù)庫，去除不頻繁元素，篩選出項集中的頻繁元素，并且按照頻繁元素出現(xiàn)的次數(shù)完成元素的排序。在挖掘頻繁項集的過程中，原始項集包含頻繁元素和非頻繁元素，而挖掘的頻繁項集只包含頻繁元素。元素項處理結(jié)果如表1所示，完成了元素項的篩選及排序。

表1　元素項處理結(jié)果

fp-tree是一棵根節(jié)點為空的樹，除根節(jié)點外，其他節(jié)點包含元素的名字和元素出現(xiàn)的次數(shù)。fp-tree的構(gòu)建規(guī)則為：

1)讀入項集，若項集已存在，則在原來路徑中修改計數(shù)值。

2)若項集不存在，則創(chuàng)建一條新路徑，已存在的部分路徑更改計數(shù)值。

為了高效地訪問fp-free，增加了頭指針表，頭指針指向給定類型的第一個實例，相同類型彼此連接。在訪問fp-tree時，通過頭指針表，可以快速地訪問給定類型的所有元素。為了形象地描述建樹過程[8]，采用表1的數(shù)據(jù)建立fp-tree，如圖1所示。

圖1　fp-treeFig.1　fp-tree

在fp-tree中挖掘項集的條件模式基，利用條件模式基構(gòu)建條件fp-tree。條件模式基是條件fp-tree上查找元素為葉子的路徑集合，條件fp-tree屬于fp-tree。挖掘頻繁項集是一個遞歸的過程，其原理為：

元素項t的條件基為{z,x,y,s}:2,{z,x,y,r}:1,元素項s、r均滿足最小支持度，但項集{t,s}、{t,r}不滿足最小支持度，不是頻繁項集。而項集{t,z}、{t,x}、{t,y}是頻繁項集。下一步查找{t,z}的條件模式基，遞歸挖掘條件模式基，得到所有的頻繁項集。

對頻繁項集進行過濾，得到核心頻繁項集。其過濾規(guī)則為：

1)創(chuàng)建一個核心頻繁項集的集合，用于存儲確定的頻繁項集。

2)若頻繁項集Si?Sj，則將頻繁項集Si放入核心頻繁項集。

3)若不存在包含關(guān)系，則比較Si、Sj的相似度。若其相似度大于相似度閾值ε，則合并頻繁項集作為核心頻繁項集，否則創(chuàng)建一個新的核心頻繁項集。

核心頻繁項集個數(shù)代表聚類的個數(shù)，每個核心頻繁項集可作為k均值的初始聚類質(zhì)心。算法通過調(diào)節(jié)閾值確定聚類的個數(shù)，若對聚類粒度要求較高，可增大閾值，否則減小閾值。改進的k均值算法流程為：

1)采用fp-growth算法指導(dǎo)初始聚類質(zhì)心和聚類個數(shù)的生成。

2)利用初始聚類質(zhì)心和聚類個數(shù)作為k均值的輸入，完成文本聚類。

2　實驗結(jié)果與分析

為了測試改進算法的性能，挖掘新浪幾十個熱門話題的10萬條微博，內(nèi)容包括體育、韓劇、手機等。其中大話題包括多個小話題，對微博聚類測試算法的性能。實驗采用復(fù)旦大學(xué)的分詞系統(tǒng)對文本分詞，然后使用fp-growth算法挖掘文本的核心頻繁項集，核心頻繁項集的個數(shù)由相似度閾值決定，在算法中聚類個數(shù)由核心頻繁項集的個數(shù)決定，根據(jù)聚類結(jié)果要求的粗略程度調(diào)節(jié)閾值。在確定聚類個數(shù)和初始聚類質(zhì)心的前提下，利用k均值算法完成對文本的聚類。

實驗通過改變fp-growth頻繁項集相似度閾值ε，觀察聚類的個數(shù)及聚類的效果，并使用準確率P、召回率R和F值評價聚類結(jié)果。

(3)

(4)

(5)

其中：T為同類文本被分到同一個簇的個數(shù)；M為不同類文本被分到不同簇的個數(shù)；N為同類文本被分到不同簇的個數(shù)。F為準確率和召回率的協(xié)同表現(xiàn)，綜合體現(xiàn)聚類效果的優(yōu)劣。

改變頻繁項集相似度閾值ε，尋找最佳聚類結(jié)果的相似度閾值ε，不同相似度閾值的聚類結(jié)果如表2所示。

表2　不同相似度閾值的聚類結(jié)果

文本聚類結(jié)果的評判方法是文本是否正確歸為本應(yīng)所屬的簇。簇的個數(shù)越多，文本歸屬到對應(yīng)的簇的概率就越大。若簇的個數(shù)足夠多，則每個文本單獨屬于一個簇，顯然聚類個數(shù)不能用來衡量聚類效果[9]。由表2可知，當(dāng)ε=0.75時，F(xiàn)值最大，文本聚類結(jié)果最佳。

為了消除參數(shù)對算法的影響，改進算法、k均值算法、二分k均值算法3種算法在相同數(shù)據(jù)集和參數(shù)下聚類。取ε=0.75，聚類個數(shù)為82個，得到3種算法的聚類結(jié)果，如圖2所示。從圖2可看出，改進算法的準確率、召回率、F值均高于k均值算法和二分k均值算法，二分k均值算法高于k均值算法。

圖2　3種算法的聚類結(jié)果Fig.2　The clustering results of three algorithms

改進算法、k均值算法、二分k均值算法的迭代次數(shù)如圖3所示。從圖3可看出，改進算法的迭代次數(shù)在不同數(shù)據(jù)條數(shù)下高于k均值算法和二分k均值算法。由于二分k均值算法將整個數(shù)據(jù)集作為一個簇，然后將該簇一分為二，并選擇最大程度降低聚類代價函數(shù)(誤差平方和)的簇劃分為2個簇，誤差平方和是簇中每個元素與聚類質(zhì)心距離的平方和。相比k均值算法，二分k均值算法避免了聚類結(jié)果的局部最優(yōu)。但是二分k均值算法的初始聚類質(zhì)心依然是隨機的，并未避免質(zhì)心的移動，且誤差平方和增加了算法的計算復(fù)雜度，效率沒有顯著提高。改進算法采用核心頻繁項集指導(dǎo)初始聚類質(zhì)心，聚類質(zhì)心在文本相似度上與該簇的主題相似，聚類過程中減少了聚類質(zhì)心的移動，降低了計算復(fù)雜度，提高了算法的收斂速度，且獲得了最佳的聚類個數(shù)。

圖3　3種算法的迭代次數(shù)Fig.3　The iteration number of three algorithms

3　結(jié)束語

基于fp-growth算法，提出了一種改進的k均值文本聚類算法。該算法采用fp-growth算法挖掘頻繁項集，利用頻繁項集過濾核心頻繁項集，通過核心頻繁項集指導(dǎo)聚類個數(shù)以及初始聚類質(zhì)心的生成，最后將其作為k均值算法的輸入，完成了文本聚類。該算法克服了k均值算法容易陷入局部最優(yōu)的缺陷，提升了算法的收斂速度。

[1]李小武,邵劍飛,廖秀玲.一種基于K-means的分布式聚類算法[J].桂林電子科技大學(xué)學(xué)報,2011,31(6):460-463.

[2]KRISHNABSV,SATHEESHP,SUNEELKUMARR.Comparativestudyofk-meansandbisectingk-meanstechniquesinwordnetbaseddocumentclustering[J].InternationalJournalofEngineeringandAdvancedTechnology,2012,2249:8958.

[3]LIUXiaozhang,FENGGuocan.Kernelbisectingk-meansclusteringforSVMtrainingsamplereduction[C]//19thIEEEInternationalConferenceonPatternRecognition,2008:1-4.

[4]彭敏,黃佳佳,朱佳暉,等.基于頻繁項集的海量短文本聚類與主題抽取[J].計算機研究與發(fā)展,2015,52(9):1941-1953.

[5]XUJiaming,XUBo,TIANGuanhua,etal.Shorttexthashingimprovedbyintegratingmulti-granularitytopicsandtags[J].LectureNotesinComputerScience,2015,9041:444-455.

[6]TIANYun,LIHaisheng,CAIQiang,etal.Measuringthesimilarityofshorttextsbywordsimilarityandtreekernels[C]//IEEEYouthConferenceonInformationComputingandTelecommunications,2010:363-366.

[7]HUXia,SUNNan,ZHANGChao,etal.Exploitinginternalandexternalsemanticsfortheclusteringofshorttextsusingworldknowledge[C]//ACMConferenceonInformationandKnowledgeManagement,2009:919-928.

[8]BHARTIKK,SINGHPK.Hybriddimensionreductionbyintegratingfeatureselectionwithfeatureextractionmethodfortextclustering[J].ExpertSystemswithApplications,2015,42(6):3105-3114.

[9]張建沛，楊悅，楊靜，等.基于最優(yōu)劃分的k-means初始聚類中心選取算法[J].系統(tǒng)仿真學(xué)報，2009，21(9):2586-2589.

編輯：曹壽平

An improved k-means algorithm for text clustering

ZHANG Yinming, HUANG Tinglei, LIN Ke, ZHANG Qiangqiang

(School of Computer and Information Security, Guilin University of Electronic Technology, Guilin 541004, China)

Random selection of initial cluster centroid ink-means algorithm for text clustering resulted in local optimization of clustering results, and isolated points and indeterminate cluster number led to low accuracy and slow convergence speed ofk-means algorithm. So an improvedk-means algorithm for text clustering was proposed. In the proposed algorithm, fp-growth algorithm was used for mining frequent item sets of text, and frequent item sets of text were filtered to obtain the core frequent item sets, and then the core frequent item sets were adopted to generate initial cluster centroid and the number of clustering. Finallyk-means algorithm was applied for text clustering with the generated initial cluster centroid and the number of clustering. The results of text clustering experiment on Sina microblog dataset show that the improvedk-means algorithm can effectively improve the accuracy of text clustering and accelerate the convergence speed, and has strong robustness.

text clustering; fp-growth;k-means

2016-04-07

國家863計劃(2012AA011005)

黃廷磊(1971-)，男，安徽肥東人，教授，博士，研究方向為數(shù)據(jù)挖掘、無線Mesh網(wǎng)絡(luò)等。E-mail：tlhuang@guet.edu.cn

TP311

A

1673-808X(2016)04-0311-04

引文格式：張銀明，黃廷磊，林科，等.一種改進的k均值文本聚類算法[J].桂林電子科技大學(xué)學(xué)報，2016,36(4):311-314.