一種改進(jìn)的K 均值文本聚類算法*

安計(jì)勇，高貴閣，史志強(qiáng)，孫 磊

(1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116;2.73682 部隊(duì)，江蘇 徐州221116;3.中國(guó)礦業(yè)大學(xué) 圖文信息中心，江蘇 徐州221116)

0 引 言

文本聚類是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)熱點(diǎn)。傳統(tǒng)聚類算法分為基于劃分的、密度的、分層的、網(wǎng)格的、模型的等幾種［1］。K 均值聚類算法是基于劃分的聚類算法，它具有算法簡(jiǎn)單、收斂速度快、能有效處理大數(shù)據(jù)集等多方面的優(yōu)點(diǎn)。但是K 均值聚類算法隨機(jī)選擇初始簇中心會(huì)導(dǎo)致得到的聚類結(jié)果中容易出現(xiàn)局部最優(yōu)，而不是全局最優(yōu)、聚類結(jié)果具有不穩(wěn)定性、聚類質(zhì)量較差等缺點(diǎn)。

針對(duì)K 均值算法存在的不足，本文提出了一種改進(jìn)的K 均值文本聚類算法。該算法的改進(jìn)基于以下兩點(diǎn):1)基于簇密度與文本間距離選取初始簇中心，引入置信半徑來(lái)得到簇密度，即選取距離最遠(yuǎn)且簇密度最大的點(diǎn)為初始簇中心;2)基于權(quán)重的海明距離來(lái)計(jì)算文本相似度，同時(shí)采用輪廓系數(shù)來(lái)衡量不同聚類算法的聚類質(zhì)量。實(shí)驗(yàn)結(jié)果表明:該算法相比原始的K 均值文本聚類算法和文獻(xiàn)［1］中算法具有更好的聚類質(zhì)量。

1 K 均值聚類算法與文本聚類

1.1 K 均值聚類算法

K 均值聚類算法［2］的核心思想在于中心探索法。該算法是一個(gè)迭代算法，主要思想是從屬于該簇的每個(gè)點(diǎn)的位置計(jì)算每個(gè)簇的中心位置，然后將這些點(diǎn)劃分到距離它們最近的中心，這個(gè)過(guò)程一直重復(fù)直到足夠的收斂。該算法相關(guān)計(jì)算公式如下:

聚類中心計(jì)算公式［2］

收斂測(cè)度函數(shù)［2］

K 均值聚類算法執(zhí)行步驟如下:

1)依次輸入簇的數(shù)目K，N 個(gè)樣本值、最大迭代次數(shù)maxstep 及收斂條件θ。

2)隨機(jī)選擇K 個(gè)簇中心。

3)對(duì)每個(gè)樣本點(diǎn)，計(jì)算與K 個(gè)簇中心的距離，并選擇距離最小的簇為該樣本點(diǎn)所屬簇。

4)重新計(jì)算K 個(gè)簇中心，中心使用公式(1)計(jì)算，用公式(2)計(jì)算此時(shí)的收斂測(cè)度函數(shù)值E。

5)如果達(dá)到最大迭代次數(shù)maxstep 或者滿足公式(3)，代表簇成員不再發(fā)生變化，結(jié)束聚類;否則，返回步驟(3)

其中，θ 為一個(gè)極小的數(shù)，E1和E2分別為前后兩次迭代的收斂測(cè)度函數(shù)值。

6)輸出K 個(gè)簇和迭代次數(shù)。

1.2 文本聚類

1.2.1 文本向量化

文本聚類的首要任務(wù)是文本向量化表示。文本向量化的傳統(tǒng)方法為向量空間模型(VSM)。這種方法認(rèn)為每篇文本都包含一些用概念詞表達(dá)的，揭示其內(nèi)容的獨(dú)立屬性，而每個(gè)屬性都可以看成是概念空間的一個(gè)維數(shù)，這些獨(dú)立屬性稱為文本特征項(xiàng)，文本就可以表示為這些特征項(xiàng)的集合。因此，文本就可以表示成形如d=(t，w1;t，w2;t，w3;…t，wn)的向量形式，其中，t 為特征項(xiàng)，w 為其對(duì)應(yīng)的權(quán)重。權(quán)重通過(guò)TF-IDF［2］的方法來(lái)計(jì)算如公式(4)［1］

1.2.2 文本距離

文本聚類算法通常采用余弦?jiàn)A角來(lái)［3］計(jì)算2 個(gè)文本之間的相似度。但在K 均值聚類算法中，通常需要計(jì)算兩個(gè)文本之間的距離，因此，單純使用余弦?jiàn)A角來(lái)作為度量文本之間的距離不合適。當(dāng)然，可以通過(guò)某些方法把余弦?jiàn)A角轉(zhuǎn)換為文本距離，如文獻(xiàn)［3］提出的取對(duì)數(shù)法等。

考慮到變換帶來(lái)的不確定性，本文采用海明距離［4］來(lái)計(jì)算兩個(gè)文本之間的相似度。海明距離公式為

其中，n 為向量維數(shù)。在海明距離中沒(méi)有考慮各個(gè)屬性的權(quán)重，改進(jìn)的海明距離公式為

其中，ewm為文本向量各個(gè)屬性的權(quán)重。

本文改進(jìn)的算法采用海明距離的好處在于:1)無(wú)需在文本相似度與文本距離之間進(jìn)行轉(zhuǎn)換;2)基于權(quán)重的海明距離更能體現(xiàn)文本的相似度。

2 改進(jìn)的K 均值文本聚類算法

2.1 基于簇密度的初始簇中心的選取

針對(duì)原始K 均值聚類算法初始簇中心選取的隨機(jī)性，容易導(dǎo)致聚類結(jié)果局部最優(yōu)、聚類結(jié)果不穩(wěn)定等缺點(diǎn)。本文提出了基于簇密度與文本間距離選取初始簇中心的方法，該方法主要依賴以下事實(shí):1)距離最遠(yuǎn)(文本相似度小)的樣本點(diǎn)分到同一簇的可能性小;反之，距離最近(文本相似度最大)的樣本點(diǎn)分到同一簇的可能性大。2)以某樣本點(diǎn)為中心，以某個(gè)正數(shù)值r 為半徑的超維球內(nèi)簇密度最大的點(diǎn)，最有可能為聚類中心。簇密度公式為

其中，r 為半徑，count(r)為以某點(diǎn)為圓心，r 為半徑的超維球內(nèi)的樣本點(diǎn)的個(gè)數(shù)，density(r)為以r 為半徑的簇密度。

本文改進(jìn)的算法確定聚類半徑r 的值非常關(guān)鍵，通常很難找到一個(gè)最佳的r 值，r 取值太大或太小都失去了對(duì)象點(diǎn)密度的意義，從而找不出合理的初始中心點(diǎn)。因此，確定一個(gè)合適的聚類半徑r 是本文算法選族初始簇中心的關(guān)鍵。改進(jìn)的算法中聚類半徑r 采用文獻(xiàn)［5］中提出的置信半徑［5］作為初始簇半徑r。置信半徑為在已知簇密度函數(shù)的情況下，對(duì)簇密度函數(shù)求梯度，尋找樣本點(diǎn)數(shù)據(jù)密度曲線上梯度的最大和最小值點(diǎn)，分別記為Dmax和Dmin，這2 個(gè)位置描述了樣本點(diǎn)數(shù)據(jù)從稠密到稀疏，或者從稀疏到稠密的分界位置，則置信半徑Dr為

基于以上認(rèn)識(shí)的基礎(chǔ)上，本文基于簇密度與文本間距離選取初始簇中心的方法可以描述為:選取距離最大且簇密度最大的點(diǎn)為初始簇中心。距離最大是要保證初始簇中心的選取盡量分散，不要過(guò)度集中。在距離最大的點(diǎn)中選取簇密度最大的(保證距離遠(yuǎn)的離散點(diǎn)不被選取成為初始簇中心)，即在半徑為r 的超維球內(nèi)的點(diǎn)數(shù)最多的，如果點(diǎn)數(shù)小于某個(gè)閾值countmax，剔除該點(diǎn)為初始簇中心，繼續(xù)選擇距離最大的點(diǎn)為候選簇中心，滿足以上2 個(gè)條件的作為候選初始簇中心，直到選出K 個(gè)簇中心。本文算法中countmax的計(jì)算公式為

其中，N 為樣本點(diǎn)數(shù)，K 為初始簇個(gè)數(shù)，?為系數(shù)，大小為(0，1)之間，算法中根據(jù)情況進(jìn)行賦值;在第3 節(jié)實(shí)驗(yàn)驗(yàn)證環(huán)節(jié)，通過(guò)多次執(zhí)行算法，得出通常?取值(0.3 ～0.4)之間會(huì)有更好的聚類效果。

選取初始簇中心的算法描述如下:

1)找出樣本集的N 個(gè)樣本點(diǎn)中距離最大的2 個(gè)點(diǎn)。

2)計(jì)算某點(diǎn)為中心，r 為半徑，落到該超維球內(nèi)的樣本點(diǎn)數(shù)，如果樣本點(diǎn)數(shù)不小于countmax，該樣本點(diǎn)可以作為初始簇中心;否則，剔除改點(diǎn)，令樣本點(diǎn)數(shù)N=N－1。

3)判斷是否滿足如下條件

count(C)為當(dāng)前選出的簇中心個(gè)數(shù)，K 為初始簇個(gè)數(shù)。

4)在N－2 個(gè)樣本點(diǎn)中找出滿足公式(9)［1］的樣本點(diǎn)

其中，di是除d1，d2，d3外的任何一個(gè)樣本點(diǎn)，轉(zhuǎn)到步驟(2)。

5)在N 個(gè)點(diǎn)中找出與選中的第一個(gè)初始簇中心點(diǎn)距離最遠(yuǎn)的點(diǎn)，轉(zhuǎn)到步驟(2)。

6)在N－count(C)個(gè)樣本點(diǎn)中找出滿足公式(10)的第m 個(gè)樣本點(diǎn)，轉(zhuǎn)到步驟(2)。

7)算法結(jié)束。

2.2 用改進(jìn)的K 均值算法進(jìn)行文本聚類

算法流程圖1 所示。

圖1 改進(jìn)的K 均值聚類算法流程圖Fig 1 Flow chart of improved K-means clustering algorithm

算法的具體描述如下:

1)輸入簇的總數(shù)目K 和N 個(gè)向量化后的文本集。

2)采用2.1 節(jié)中的方法選取K 個(gè)初始簇中心。

3)輸入迭代終止條件θ 和最大迭代次數(shù)maxstep。

4)對(duì)于剩余的(N－K)個(gè)樣本，計(jì)算每個(gè)樣本與K 個(gè)簇中心的距離，將樣本歸入距離最近的某個(gè)簇。

5)重新計(jì)算K 個(gè)簇的中心，如公式(11)所示，并計(jì)算此時(shí)的收斂測(cè)度函數(shù)值E，如公式(12)所示。由于簇中心的選取基于2.1 節(jié)方法得到，所以，簇中心不能以原始K 均值聚類算法中通過(guò)計(jì)算簇內(nèi)的所用樣本點(diǎn)的算術(shù)平均值得到，而是應(yīng)該通過(guò)計(jì)算簇內(nèi)所有點(diǎn)到簇中心的距離之和，即標(biāo)準(zhǔn)偏差滿足如下條件

其中，R 為標(biāo)準(zhǔn)偏差即簇內(nèi)平均半徑，r 為2.1 節(jié)中該簇的置信半徑

6)如果迭代次數(shù)達(dá)到maxstep 或者滿足公式(13)，則算法結(jié)束;否則，繼續(xù)迭代

其中，E1和E2分別為上一次和本次的收斂測(cè)度函數(shù)值。

3 實(shí)驗(yàn)與分析

3.1 算法評(píng)價(jià)指標(biāo)

本文改進(jìn)的K 均值聚類算法主要是針對(duì)聚類質(zhì)量進(jìn)行評(píng)價(jià)，因此，評(píng)價(jià)指標(biāo)采用輪廓系數(shù)［6］來(lái)衡量算法的聚類質(zhì)量。輪廓系數(shù)S 的定義為

其中，ai為點(diǎn)i 到其所屬簇中所有其他點(diǎn)的平均距離;bi為計(jì)算點(diǎn)i 到其所不在的任何簇的所有點(diǎn)的距離中的最小值;分子是兩個(gè)簇之間的“空白空間”的度量值;分母是兩個(gè)長(zhǎng)度較大的一個(gè)，即簇的半徑和2 個(gè)簇之間的距離。

通過(guò)構(gòu)造，輪廓系數(shù)的取值范圍為－1 ～1 之間。如果S 的值為負(fù)值，表明簇的半徑比兩個(gè)簇之間的距離大，說(shuō)明這些簇是重疊的，是一個(gè)糟糕的簇。S 的值越大，表明聚類算法的聚類質(zhì)量越高。因此，本文的算法中，用單個(gè)簇內(nèi)所有點(diǎn)的輪廓系數(shù)的平均值來(lái)衡量整個(gè)簇的聚類質(zhì)量，以此來(lái)衡量算法的聚類效果。

3.2 算法驗(yàn)證

本文分別對(duì)原始K 均值聚類算法、文獻(xiàn)［1］和本文的算法進(jìn)行了分析比較。實(shí)驗(yàn)驗(yàn)證的數(shù)據(jù)集來(lái)源中文文本分類語(yǔ)料庫(kù)，本文選擇了該語(yǔ)料庫(kù)的1600 篇文檔，6 個(gè)聚類主題，分別為電子商務(wù)、教育、體育、軍事、汽車(chē)。在實(shí)驗(yàn)中，分別設(shè)置了6 個(gè)不同的特征提取率，進(jìn)行了6 次實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表1 所示。

從表1 中可以得出:改進(jìn)的K 均值聚類算法相比原始K 均值聚類算法總耗時(shí)增加了10 571.16 ms，但均值輪廓系數(shù)平均提高了25%;相比文獻(xiàn)［1］提出的最大距離法選取初始簇中心的K 均值文本聚類算法總耗時(shí)增加了16 289.21 ms，但均值輪廓系數(shù)平均提高了16%。

本文改進(jìn)的算法耗時(shí)長(zhǎng)，主要原因在于初始簇中心選取時(shí)簇密度的計(jì)算量，而原始的K 均值算法不需要計(jì)算得到初始簇中心，文獻(xiàn)［1］提出的最大距離法選取初始簇中心的K 均值文本聚類算法只計(jì)算距離最遠(yuǎn)的點(diǎn)，不需要計(jì)算簇密度。改進(jìn)的算法在聚類總耗時(shí)相比兩種算法有所增加，但是在聚類質(zhì)量上有了明顯的提高。其主要原因?yàn)?原始的K 均值聚類算法隨機(jī)選取初始簇中心，容易導(dǎo)致本應(yīng)該在同一簇的2 個(gè)樣本點(diǎn)，被放在了不同的簇中，使得容易導(dǎo)致局部最優(yōu)、聚類質(zhì)量較差;文獻(xiàn)［1］提出的最大距離法選取初始簇中心的K 均值文本聚類算法雖然在初始簇中心的選取相比原始算法有了改進(jìn)，但只基于距離最大法選擇初始簇中心，容易導(dǎo)致2 個(gè)本是距離遠(yuǎn)的離散點(diǎn)，被當(dāng)成了初始簇中心;本文改進(jìn)的算法不是單純的把距離最遠(yuǎn)的點(diǎn)作為初始簇中心，如果某個(gè)點(diǎn)要作為候選初始簇中心，必須滿足距離最遠(yuǎn)且簇密度最大，這樣基本上可以克服上文提到的兩種算法在初始簇中心選取上的缺點(diǎn)，本文算法選出的初始簇中心具有很強(qiáng)的區(qū)分性;從而使得聚類質(zhì)量相比原始K 均值算法和文獻(xiàn)［1］提出的算法有很大提高。此外，由于本文算法在初始簇中心選取上的優(yōu)勢(shì)，使得文本聚類結(jié)果有較好的穩(wěn)定性。

表1 三種文本聚類算法的結(jié)果比較Tab 1 Results comparison of three kinds of text clustering algorithm

4 結(jié)束語(yǔ)

針對(duì)原始K 均值聚類算法初始簇中心的隨機(jī)選取容易導(dǎo)致的聚類結(jié)果局部最優(yōu)，聚類結(jié)果不穩(wěn)定等缺點(diǎn)，本文提出了一種改進(jìn)的K 均值聚類算法，該算法的改進(jìn)基于以下兩點(diǎn):1)基于簇密度與文本間距離選取初始簇中心，引入置信半徑來(lái)得到簇密度，即選取距離最遠(yuǎn)且簇密度最大的點(diǎn)為初始簇中心;2)基于權(quán)重的海明距離來(lái)計(jì)算文本相似度，同時(shí)采用輪廓系數(shù)來(lái)衡量不同聚類算法的聚類質(zhì)量。實(shí)驗(yàn)結(jié)果證明了本文算法的有效性。

［1］ 翟東海，魚(yú) 江，高 飛，等.最大距離法選取初始簇中心的Kmeans 文本聚類算法的研究［J］.計(jì)算機(jī)應(yīng)用研究，2014，31(3):714－719.

［2］ 熊忠陽(yáng)，陳若田，張玉芳.一種基于K-means 簇中心初始化方法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(11):4188－4190.

［3］ 張健沛，楊 銳，楊 靜，等.基于最優(yōu)劃分的K-means 初始聚類中心選取算法［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21(9):2586－2589.

［4］ 姜士強(qiáng)，楊濟(jì)亭，任芹玉.基于改進(jìn)海明距離的二元表示聚類研究［J］.信息技術(shù)，2013(4):88－91.

［5］ 張科澤，楊鶴標(biāo)，沈項(xiàng)軍，等.基于節(jié)點(diǎn)數(shù)據(jù)密度的分布式Kmeans 聚類算法研究［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(10):3643－3645，3655.