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

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

0 引 言

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

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

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

1.1 K 均值聚類算法

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

聚類中心計算公式［2］

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

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

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

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

3)對每個樣本點，計算與K 個簇中心的距離，并選擇距離最小的簇為該樣本點所屬簇。

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

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

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

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

1.2 文本聚類

1.2.1 文本向量化

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

1.2.2 文本距離

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

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

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

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

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

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

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

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

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

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

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

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

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

1)找出樣本集的N 個樣本點中距離最大的2 個點。

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

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

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

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

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

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

6)在N－count(C)個樣本點中找出滿足公式(10)的第m 個樣本點，轉(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 個向量化后的文本集。

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

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

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

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

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

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

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

3 實驗與分析

3.1 算法評價指標(biāo)

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

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

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

3.2 算法驗證

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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