一種基于LSA與FCM的文本聚類算法

王文霞

(運(yùn)城學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，山西運(yùn)城044000)

一種基于LSA與FCM的文本聚類算法

王文霞

(運(yùn)城學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，山西運(yùn)城044000)

在文本聚類中，基于向量空間模型(VSM)的文本特征空間存在高維度和稀疏空間、同義詞與多義詞干擾等問(wèn)題；而K-means算法依賴于初始聚類中心，聚類結(jié)果隨不同的初始輸入而有所波動(dòng)。針對(duì)這些問(wèn)題，本文提出了一種基于潛在語(yǔ)義分析（LSA）與優(yōu)化的模糊C均值(FCM)的文本聚類算法——LF。該算法首先采用一種新的詞特征提取方法建立詞-文本矩陣；然后對(duì)該詞-文本矩陣進(jìn)行奇異值分解在潛在語(yǔ)義空間進(jìn)行降維；接著用優(yōu)化的模糊C均值聚類算法實(shí)現(xiàn)對(duì)文本的聚類分析。最后通過(guò)實(shí)驗(yàn)，結(jié)果表明LF算法能更好地改善了文本聚類的結(jié)果，提高了文本的查全率和查準(zhǔn)率。

文本聚類；FCM；LSA；遺傳優(yōu)化；k-means算法

近年來(lái)隨著互聯(lián)網(wǎng)的發(fā)展與普及，各種信息呈爆炸式的增長(zhǎng)。在這海量的文本信息中如何快速、準(zhǔn)確地挖掘出有價(jià)值的、用戶感興趣的信息，是當(dāng)前計(jì)算機(jī)信息理論研究的重點(diǎn)和熱點(diǎn)。其中，文本聚類作為數(shù)據(jù)挖掘的重要分支之一，不需要預(yù)先設(shè)定文本類別，也不需要訓(xùn)練過(guò)程，自動(dòng)化處理能力較高且具有一定的靈活性，在信息檢索、信息過(guò)濾、數(shù)字化圖書館、搜索引擎等很多領(lǐng)域都有著廣闊的應(yīng)用前景。

目前，對(duì)文本的聚類分析，通常是基于向量空間模型(VSM)的文本表示法和K-means聚類算法實(shí)現(xiàn)對(duì)文本的聚類分析。VSM的文本表示法將文本用詞語(yǔ)向量表示出來(lái)，對(duì)應(yīng)為空間中的點(diǎn)，并通過(guò)計(jì)算空間中兩點(diǎn)間的距離獲得文本之間的相似度，進(jìn)而基于經(jīng)典的K-means聚類方法實(shí)現(xiàn)對(duì)文本的聚類[1-2]。但是VSM存在著兩大缺點(diǎn)：（1）當(dāng)文本比較長(zhǎng)時(shí)，詞匯量就會(huì)變得很大，這往往會(huì)產(chǎn)生高維的文本向量，使得很多傳統(tǒng)算法難以處理；（2）VSM中對(duì)于詞語(yǔ)權(quán)重的計(jì)算主要是基于統(tǒng)計(jì)的，只考慮文本中關(guān)鍵詞出現(xiàn)的次數(shù)，而不考慮關(guān)鍵詞在上下文語(yǔ)境中的語(yǔ)義，忽略同義詞與多義詞的干擾，往往使得聚類結(jié)果不準(zhǔn)確。K-means聚類算法是一種基于劃分的聚類算法，其基本思想是不斷迭代更新直至目標(biāo)函數(shù)取得極小值，從而取得最優(yōu)聚類效果。但是，該算法依賴于初始聚類中心的選定，分類的個(gè)數(shù)K也需事先確定，且種子選取的好壞都直接影響著文本聚類的效果，進(jìn)而影響文本的檢索質(zhì)量。

因此，本文提出了一種LF：基于LSA和FCM的文本聚類算法。該算法首先采用LSA模型來(lái)代替?zhèn)鹘y(tǒng)的VSM，再用模糊C均值對(duì)文本進(jìn)行聚類，最后用遺傳算法優(yōu)化聚類結(jié)果。該算法不僅可壓縮問(wèn)題規(guī)模，而且聚類結(jié)果又用遺傳算法進(jìn)行全局最優(yōu)化處理，使得聚類分析在時(shí)間性能和質(zhì)量上都能獲得較好的效果。

1 LSA模型

1.1 LSA的基本思想

潛在語(yǔ)義分析(LSA)模型是1990年S T Dumais等人提出了一種新的信息檢索代數(shù)模型。LSA的基本思想是首先構(gòu)造一個(gè)包含m個(gè)文本和n個(gè)詞的文本集的詞匯-文本矩陣A，再基于數(shù)學(xué)中的奇異值分解(SVD)理論對(duì)矩陣A進(jìn)行分解得到A=USVT。其中，U是一個(gè)m*m的正交矩陣，其列為矩陣A的左奇異值向量；V是一個(gè)n*n的正交矩陣。其列為A的右奇異值向量；S為對(duì)角矩陣,其元素稱為A的奇異值[3]。假設(shè)A的秩為r，通過(guò)取U的前k(k＜=r)列,V的前k行，以及S中的前k個(gè)奇異值可得Ak=UkSkVkT，這樣就可以很好解決傳統(tǒng)向量空間模型所存在的問(wèn)題，實(shí)現(xiàn)：（1）通過(guò)奇異值分解大大降低向量空間的維數(shù)；（2）A k是原矩陣A在k維子空間上最小二乘意義上的最佳近似，應(yīng)用于信息的分解和重構(gòu)，可以提取有用信息，消除噪聲，實(shí)現(xiàn)語(yǔ)義檢索[4]。

為了實(shí)現(xiàn)文本的聚類，需要獲得文本與文本間的相似度。LSA模型表示文本后，便可以求得詞語(yǔ)與詞語(yǔ)之間的相似度、文本與文本之間以及詞語(yǔ)與文本之間的相似度。本文中采用向量間的余弦值來(lái)計(jì)算文本間相似的的方法，文本Di與Dj之間的相似度用如下公式求得：

其中，表示k階單位矩陣的第i列。

1.2 新的特征權(quán)重算法

在傳統(tǒng)的特征權(quán)重計(jì)算方法TF-IDF中，只考慮了同一文本中詞的出現(xiàn)頻率和包括某次的文本數(shù)，并沒(méi)考慮其他因素。而實(shí)際上由于不同詞在文本中的作用不同，對(duì)文本的重要程度也不同。因此，在構(gòu)造詞-文本矩陣時(shí)往往要考慮該因素對(duì)不同的詞賦予不同權(quán)重。本文對(duì)傳統(tǒng)的TF-IDF特征選擇算法進(jìn)行了改進(jìn),增加了對(duì)詞的熵權(quán)重這個(gè)因素的考慮。

基于信息理論，提出的熵權(quán)重是一種最復(fù)雜的權(quán)重計(jì)算方法,其計(jì)算方法為：

其中，M表示特征詞i的平均熵。

本文中，將兩者結(jié)合起來(lái)，給出了一種新的特征權(quán)重計(jì)算法，其計(jì)算公式為：

2 優(yōu)化的FCM算法

2.1 FCM的基本思想

模糊C均值(FCM)算法[5]的基本思想是基于某種準(zhǔn)則，把沒(méi)有類別標(biāo)記的樣本集劃分為若干子集，使相似的樣本盡可能劃分到一類，而把不相似的樣本歸于不同的類中。傳統(tǒng)的K-means聚類分析是一種硬劃分,把每個(gè)樣本嚴(yán)格劃分到某類中，但這與實(shí)際不符，因?yàn)楝F(xiàn)實(shí)中大多數(shù)待分類樣本并沒(méi)有嚴(yán)格分界限,在各種特征上都存有一定中介性。FCM就是用模糊的方法進(jìn)行聚類分析，是對(duì)樣本類別的不確定描述,從而更客觀的反應(yīng)世界；且該算法思想簡(jiǎn)單、收斂速度快,便于處理大規(guī)模數(shù)據(jù)且易于計(jì)算機(jī)實(shí)現(xiàn)，因而成為了聚類分析的主流算法[6]。

FCM實(shí)現(xiàn)的具體步驟如下：

Step 1：在[0,1]間取隨機(jī)數(shù)來(lái)初始化隸屬矩陣U(1)，需滿足一個(gè)數(shù)據(jù)集的隸屬度的和總等于1，即初始化迭代截至誤差a(a＞0)。

Step 2：計(jì)算聚類中心Ci，i=1,…,c，

Step 3：計(jì)算價(jià)值函數(shù)。若計(jì)算結(jié)果小于某個(gè)給定的閥值，或相對(duì)改變量小于另一個(gè)給定的閥值，則聚類分析結(jié)束。

Step 4：計(jì)算新的U矩陣。返回步驟2,直到

但是，F(xiàn)CM算法性能依賴于初始聚類中心,其容易陷入局部極值點(diǎn)；且得到的結(jié)果是模糊的，仍需確定化。因此，本文基于遺傳算法對(duì)FCM算法進(jìn)行了優(yōu)化，其基本思想是從文本集中隨機(jī)抽樣選取文本，應(yīng)用FCM算法，獲取模糊聚類結(jié)果；再以該結(jié)果作為遺傳算法的初始群體，進(jìn)行優(yōu)化處理，從而輸出最優(yōu)聚類解[7]。

2.2 遺傳算法進(jìn)行聚類優(yōu)化

FCM算法的計(jì)算過(guò)程是迭代的，一次迭代很容易陷入局部極值點(diǎn)，從而得不到最優(yōu)解。本文基于遺傳算法對(duì)FCM算法進(jìn)行了優(yōu)化，其基本思想是從文本集中隨機(jī)抽樣選取文本，應(yīng)用FCM算法獲取模糊聚類結(jié)果，再以該結(jié)果作為遺傳算法的初始群體，進(jìn)行優(yōu)化處理，從而輸出最優(yōu)聚類解。

假設(shè)文本聚類結(jié)果C={c1，c2，…，ck}是通過(guò)模糊C均值聚類算法得到的，其中聚類的個(gè)數(shù)表示為k。用遺傳算法進(jìn)行聚類優(yōu)化過(guò)程的詳細(xì)步驟如下所示：

Step 1：染色體編碼和初始群體的產(chǎn)生。本文采用二進(jìn)制編碼方式對(duì)染色體進(jìn)行編碼，其編碼長(zhǎng)度設(shè)定為聚類個(gè)數(shù)k；同時(shí)，隨機(jī)會(huì)產(chǎn)生Psize個(gè)長(zhǎng)度為k的二進(jìn)制編碼染色體作為初始群體（Psize為種群規(guī)模）。

Step 2：適應(yīng)度評(píng)估。在該算法中對(duì)染色體適應(yīng)度的評(píng)估分為兩步：新聚類的創(chuàng)建和適應(yīng)度的計(jì)算。

隨機(jī)選擇一個(gè)染色體S創(chuàng)建新聚類，其聚類過(guò)程為：

適應(yīng)度的計(jì)算用于評(píng)估聚類的質(zhì)量，本文采用了誤差平方和準(zhǔn)則函數(shù)JC來(lái)進(jìn)行適應(yīng)度評(píng)估，其定義為：

其中，xi代表文本集中的文本向量；nj代表第j個(gè)類中含有的文本數(shù)。Jc的值越小，說(shuō)明類內(nèi)相似度就越高，聚類質(zhì)量越好；反之Jc的值越大，聚類質(zhì)量越差。

Step 3：遺傳操作主要包括選擇、交叉和變異三個(gè)部分。

選擇：選擇是從當(dāng)前群體中選取優(yōu)良個(gè)體，適應(yīng)度越大的個(gè)體被選取的概率就越高，使其有機(jī)會(huì)作為父代繁殖下代。本文采用了輪盤賭選擇法(也就是適應(yīng)度比例法)來(lái)進(jìn)行個(gè)體的選擇。假定第i個(gè)染色體的適應(yīng)度值為fi，那么i被選中的概率可用下面公式計(jì)算可得：

交叉：交叉操作體現(xiàn)了信息交換的思想，將原來(lái)的優(yōu)良基因遺傳給下一代，生成更復(fù)雜基因結(jié)構(gòu)的個(gè)體。一般采用的交叉方式有一點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉、一致交叉等。這里，采用兩點(diǎn)交叉并按照一定的交叉概率PC來(lái)產(chǎn)生新個(gè)體，取PC的值為0.80。

變異：變異操作可反映出群體的多樣性。這里，對(duì)其變異值采取“非”操作，并取變異概率PM的值為0.010。

步驟4：算法終止。以滿足最大迭代數(shù)或者保持種群中最優(yōu)個(gè)體適應(yīng)度持續(xù)30代不變作為算法的終止條件。

3 LF算法

LF算法是LSA文本表示模型與優(yōu)化的FCM算法結(jié)合的文本聚類算法，首先采用一種新的特征權(quán)重計(jì)算建立詞-文本矩陣，同時(shí)對(duì)該詞-文本矩陣進(jìn)行奇異值分解，并用文本語(yǔ)義向量的余弦來(lái)表示文本之間的相似度；然后用優(yōu)化的模糊C均值(FCM)對(duì)上述計(jì)算文本相似度的結(jié)果進(jìn)行聚類分析。

LF算法的步驟如下：

Step 1：輸入原始文本集，語(yǔ)義空間的維數(shù)為K,模糊加權(quán)指數(shù)b;

Step 2：采用公式(3)構(gòu)造詞-文本矩陣A;

Step 3：基于LSA模型對(duì)矩陣A進(jìn)行奇異值的分解，構(gòu)建原始文本集的潛在語(yǔ)義空間為Ak;

Step 4：將文本向量映射成為語(yǔ)義空間Ak中語(yǔ)義向量，并計(jì)算文本之間的相似度;

Step 5：實(shí)現(xiàn)文本聚類，采用FCM算法計(jì)算出各類的聚類中心以及相應(yīng)的隸屬度值;

Step 6：去除模糊聚類結(jié)果的模糊化,把模糊聚類變?yōu)榇_定性分類;

Step 7：用遺傳算法對(duì)上述的聚類結(jié)果進(jìn)行優(yōu)化。

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

本文實(shí)驗(yàn)的文本集來(lái)自某門戶網(wǎng)站1100個(gè)頁(yè)面,從中提取了1000個(gè)文本，這些文本被主題分為：經(jīng)濟(jì)、軍事、政治、教育、科技和體育。定義了三個(gè)評(píng)估指標(biāo)，查準(zhǔn)率p(Precision)、查全率r(Recall)和F-Score[7]。查準(zhǔn)率p代表了類別C中的文本在實(shí)際相符的文本中所占的比例；查全率r則代表專家判定屬于類別C的文本中，聚類后被正確歸類的文本所占的比例；F-Score方法代表綜合評(píng)價(jià)聚類結(jié)果，F(xiàn)-Score定義如下：

本文采用LF算法和K-means算法進(jìn)行聚類,并對(duì)它們的結(jié)果進(jìn)行比較,如圖1所示為其實(shí)驗(yàn)結(jié)果。從圖1中可以看出，采用LF算法對(duì)文本進(jìn)行聚類時(shí)，其查準(zhǔn)率、查全率以及F-Score系數(shù)均高于k-means算法。故LF算法通過(guò)引入優(yōu)化策略能夠很好地改善文本聚類的效果，聚類結(jié)果的準(zhǔn)確度比較高，同時(shí)能有效地克服向量空間模型存在的弊端。

圖1 LF算法與K-means算法聚類結(jié)果比較

圖2和圖3是LF算法在K和b分別取不同值時(shí)的文本聚類結(jié)果統(tǒng)計(jì)。由圖可知,聚類的準(zhǔn)確性受到語(yǔ)義空間維數(shù)K的影響，當(dāng)選取的K值太小,文本集中留下來(lái)的語(yǔ)義信息將太少,從而導(dǎo)致區(qū)分文本的能力不足；反之,當(dāng)選取的K值太大時(shí)，就失去了LSA模型的優(yōu)勢(shì)，接近于向量空間模型,失去其降維、降噪的能力。因此，文本聚類時(shí)要選取的K值要合適，這樣使得文本聚類準(zhǔn)確度達(dá)到最高。同時(shí)，模糊加權(quán)指數(shù)b對(duì)聚類準(zhǔn)確度也有一定影響,如b取2時(shí)比b取1時(shí)的聚類結(jié)果要好。

圖2 LF在不同語(yǔ)義空間維數(shù)K和b=1聚類結(jié)果

圖3 LF在不同語(yǔ)義空間維數(shù)K和b=2的聚類結(jié)果

5 總結(jié)

針對(duì)傳統(tǒng)向量空間模型在文本聚類過(guò)程中所存在的高維稀疏性，無(wú)法解決同義詞、多義詞問(wèn)題，K-means算法需要預(yù)定聚類個(gè)數(shù)和依賴于初始聚類中心的弊端。本文提出的文本聚類算法，采用了潛在語(yǔ)義分析以及優(yōu)化的模糊C均值，實(shí)現(xiàn)了高維文本向量的降維處理，降低了文本處理的復(fù)雜度；同時(shí)采用了模糊C均值算法對(duì)文本進(jìn)行聚類，簡(jiǎn)單且收斂速度又快,并用遺傳算法對(duì)聚類的結(jié)果進(jìn)行優(yōu)化。通過(guò)實(shí)驗(yàn)驗(yàn)證，LF算法能更好地改善了文本聚類的結(jié)果，提高了文本的查全率和查準(zhǔn)率。LSA算法是基于統(tǒng)計(jì)的方法,盡管優(yōu)化的LSA算法考慮了詞的熵權(quán)重，它并沒(méi)有詞在文本中上下文環(huán)境，但是上下文環(huán)境對(duì)文本語(yǔ)義有著非同尋常的意義。在將來(lái)的工作中，把詞在文本中上下文環(huán)境考慮進(jìn)來(lái)，以將聚類的準(zhǔn)確度進(jìn)一步提高。

[1]任姚鵬，陳立潮，張英俊，等.結(jié)合語(yǔ)義的特征權(quán)重計(jì)算方法研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,31（10）：2381-2383．

[2]胡永麗，龔沛曾.基于模糊C均值和改進(jìn)的LSA的文檔聚類研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010,20（12）：126-129．

[3]俞輝.基于改進(jìn)LSA的文本聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30(5)：963-966.

[4]LANDAUER T K,FOLTZ P W,LAHAM D.Introduction to latent semantic analysis[J].Discourse Processes,1998,27(25)：259-284.

[5]李雷,羅紅旗,丁亞麗.一種改進(jìn)的模糊C均值聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2009,19(12)：71-73.

[6]DUNN J C.Well-separated clusters and the optimal fuzzy partition[J].Journal of Cybernetic,1974(4)：95-104.

[7]張英俊，任姚鵬，陳立潮，等.基于語(yǔ)義相似度與優(yōu)化的構(gòu)件聚類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,31（11）：2531-2535．

The Text Clustering Algorithm Based on LSA and FCM

WANG Wen-xia
(Department of Computer Science and Technology,Yuncheng University,Yuncheng Shanxi,044000)

The text clustering based on Vector Space Model has problems,such as high-dimensional and sparse,unable to solve synonym and polyseme etc.And meanwhile,k-means clustering algorithm has shortcomings,which depends on the initial clustering center and needs to fix the number of clusters in advance.Aiming at these problems,in this paper,a text clustering algorithm based on Latent Semantic Analysis and Improvded fuzzy C-means is proposed——LF.The algorithm first uses a new feature extraction method for establishing the word-text matrix;then the word-text by singular value decomposition of the matrix and the latent semantic space dimensionality reduction for text semantic vectors;then using fuzzy C means on the text of the similarity calculation results clustering,genetic algorithm is used to optimize clustering result.our algorithm is proved which can preferably improve the effect of text clustering,and upgrade the precision ratio and recall ration of text.

text clustering;FCM;LSA;genetic optimization;k-means clustering algorithm

TP311

A

1674-0874(2016)01-0008-04

2015-08-24

運(yùn)城學(xué)院教學(xué)改革研究項(xiàng)目[JG201418]

王文霞(1979-)，女，山西運(yùn)城人，碩士，講師，研究方向：數(shù)據(jù)挖掘及算法分析。

〔責(zé)任編輯 高?！?/p>