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

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

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

中圖分類號(hào)：TP391.1

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

1 模糊c均值算法

模糊C-均值算法簡(jiǎn)稱FCM（Fuzzy C-Means），其算法復(fù)雜性小，局部尋優(yōu)能力強(qiáng)而得到廣泛的應(yīng)用，其理論也趨于成熟。基本原理如下：

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

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

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

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

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

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

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

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

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

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

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

遺傳編碼：對(duì)聚類中心進(jìn)行編碼，一個(gè)聚類中心表示為個(gè)體上的一個(gè)基因，一組聚類中心組成一個(gè)個(gè)體。

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

[1]諶志群，張國(guó)煊.文本挖掘研究進(jìn)展[J].模式識(shí)別與人工智能，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.

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

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

基金項(xiàng)目：2012浙江省教育廳科研項(xiàng)目：基于云計(jì)算的海量文本聚類研究（項(xiàng)目編號(hào)：Y201225992）。