摘 要：由于文本呈現(xiàn)的多樣性和大量性，模糊聚類在文本聚類中扮演著越來越重要的角色。而應(yīng)用最廣泛的FCM算法存在著初始中心敏感的問題，對此本文提出了一種基于采樣遺傳的FCM算法（SGFCM）。該方法通過遺傳算法的全局尋優(yōu)能力來優(yōu)化FCM算法的初始聚類中心，由此來提高聚類的質(zhì)量及聚類的速度。實驗證明該方法在文本軟聚類應(yīng)用中是有效的。

關(guān)鍵詞：文本聚類；文本挖掘；模糊C-均值；遺傳算法

中圖分類號：TP391.1

文本聚類是文本挖掘中研究的最早也是最成熟的領(lǐng)域之一[1]，國內(nèi)外對其已經(jīng)進行了大量的研究，并成功地應(yīng)用在了文本挖掘和信息檢索等領(lǐng)域。同時，隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，文本越來越呈現(xiàn)出多樣性和大量性，一篇文檔往往包含多個主題，因此越來越多的研究者開始關(guān)注文本軟聚類的研究與發(fā)展。比如文獻[2]提出了一種模糊信息檢索的方法，該方法通過模糊層次聚類和模糊推論技術(shù)來擴展用戶的詢問，更靈活更智能。但是此方法只解決了FCM聚類時文本向量大小的問題，而FCM初始聚類中心敏感的問題卻沒有得到解決。

1 模糊c均值算法

模糊C-均值算法簡稱FCM（Fuzzy C-Means），其算法復(fù)雜性小，局部尋優(yōu)能力強而得到廣泛的應(yīng)用，其理論也趨于成熟?；驹砣缦拢?/p>

特征空間X={x1，x2，…，xn}的模糊C劃分可用模糊矩陣U=[uij] Rcn表示，矩陣U的元素uij表示第j（j=1，2，…，n）個數(shù)據(jù)點屬于第i（i=1，2，…，c）類的隸屬度。vi Rn為類別中心，V={vi|vi Rn，i=1，2，…c}，dij（xj，vi）為數(shù)據(jù)點xj到聚類中心vi的距離。最小化目標函數(shù)為：

FCM算法是一個使目標函數(shù)Jm（U，V）最小化的迭代收斂過程。

2 初始中心優(yōu)化的原理

遺傳算法（Genetic Algorithm）屬于進化算法的一種，它通過模仿自然界生物選擇與遺傳的機理來尋找最優(yōu)解，簡單穩(wěn)定，并且適合于并行處理。對于聚類而言，初始聚類中心的優(yōu)劣又該如何來判斷呢？通常我們認為一個好的初始聚類中心集應(yīng)該滿足兩個條件，一是選擇的初始中心要屬于不同的簇，也就是說任意兩個中心不能屬于同一簇；二是初始聚類中心要能夠作為該簇的代表，換句話說這些初始中心應(yīng)該盡量靠近簇中心。

更好地說明這個問題，其中A圖為原始數(shù)據(jù)集，隨機抽取了16個樣本數(shù)據(jù)，得到B圖。從數(shù)據(jù)的分布上我們看到兩者是非常接近的，這樣我們對B圖聚類得到的4個聚類中心與原始的最優(yōu)聚類中心是接近的，這也是我們采用采樣技術(shù)的根本原因。

3 基于采樣遺傳的文本軟聚類方法

根據(jù)對采樣結(jié)果的分析，本文提出了一種SGFCM（Sampling GA-based FCM）方法，該方法需先提取一定數(shù)量的樣本數(shù)據(jù)，使處理之后的初始聚類中心以較大概率地分屬于不同的簇，并且具有較強的代表性。SGFCM方法主要分以下三步：

（1）從原始數(shù)據(jù)集中隨機抽取1個樣本集，該樣本集包括一定數(shù)量的原始數(shù)據(jù)；

（2）設(shè)計遺傳算法的各個要素，對樣本集進行遺傳聚類操作，得到最終的遺傳個體；

（3）選取其中的最優(yōu)個體作為初始中心，并使用FCM算法進行軟聚類。

其中遺傳算法的過程設(shè)計如下：

遺傳編碼：對聚類中心進行編碼，一個聚類中心表示為個體上的一個基因，一組聚類中心組成一個個體。

初始化：確定初始群體個體數(shù)量n、交叉概率Pc、變異概率Pm以及最大遺傳代數(shù)Gmax。并隨機產(chǎn)生n個個體，形成初始種群P（t）={Vk（t）|k=1，2，…，n}，其中t為遺傳代數(shù)。

個體適應(yīng)度函數(shù)的設(shè)計尤為重要，本文的函數(shù)為 ，其中i=1，2，…，n，Φ為足夠小的正數(shù)。

進行選擇、交叉及變異操作，保留父代以及下一代個體中適應(yīng)度高的，合成為新的下一代，直到滿足結(jié)束條件為止。

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

實驗數(shù)據(jù)是從網(wǎng)上下載的5類460篇中文文檔。包括科技類105篇，財經(jīng)類90篇，體育類85篇，軍事類87篇，政治類93篇。其中27個文檔既屬于科技類又屬于財經(jīng)類，18個文檔既屬于軍事類又屬于政治類。這些文檔經(jīng)過分詞和特征選擇后，取得250個單詞作為特征。先用SGFCM方法隨機地從460篇文檔中抽取200篇作為訓(xùn)練樣本語料。

由于球型FCM只是對FCM算法中的向量和類中心進行了正規(guī)化處理，它們的耗時是基本一致的，這里只對SGFCM和FCM作了比較。表2對兩種方法分別做了三次實驗，每次的FCM迭代次數(shù)不同，分別為50，100和300。表中可以看出第2次和第3次的精度是一樣的，雖然SGFCM用了較多的時間在初始中心優(yōu)化上，但是該時間仍然可以接受，而且如果處理的數(shù)據(jù)量很大時FCM算法的每次迭代將花很長時間，這時通過減少迭代次數(shù)反而可能會節(jié)省更多的時間。

5 結(jié)束語

本文通過對遺傳算法的合理設(shè)計，提出了一種基于采樣遺傳的文本軟聚類方法——SGFCM，實驗證明該方法適合于解決大樣本高維度的問題，通過在文本聚類中的應(yīng)用可以看到該方法比FCM和球型FCM均要好，其得到的聚類結(jié)果更能充分地體現(xiàn)出文本的多樣性和大量性，使得文本的分類更具客觀性。

參考文獻：

[1]諶志群，張國煊.文本挖掘研究進展[J].模式識別與人工智能，2005（01）：65-74.

[2]Yih-Jen Horng，Shyi-Ming Chen etc.A new method for fuzzy information retrieval based on fuzzy hierarchical clustering and fuzzy inference techniques[C].Fuzzy Systems，IEEE Transactions，2005（02）：216-228.

作者簡介：徐浙君（1980.08-），男，浙江紹興人，碩士，講師，研究方向：數(shù)據(jù)挖掘和云計算研究。

作者單位：浙江郵電職業(yè)技術(shù)學(xué)院，浙江紹興 312016

基金項目：2012浙江省教育廳科研項目：基于云計算的海量文本聚類研究（項目編號：Y201225992）。