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

王文霞

(運城學院計算機科學與技術系，山西運城044000)

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

王文霞

(運城學院計算機科學與技術系，山西運城044000)

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

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

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

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

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

1 LSA模型

1.1 LSA的基本思想

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

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

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

1.2 新的特征權重算法

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

基于信息理論，提出的熵權重是一種最復雜的權重計算方法,其計算方法為：

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

本文中，將兩者結合起來，給出了一種新的特征權重計算法，其計算公式為：

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

2.1 FCM的基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

適應度的計算用于評估聚類的質量，本文采用了誤差平方和準則函數(shù)JC來進行適應度評估，其定義為：

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

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

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

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

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

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

3 LF算法

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

LF算法的步驟如下：

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

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

Step 3：基于LSA模型對矩陣A進行奇異值的分解，構建原始文本集的潛在語義空間為Ak;

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

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

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

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

4 實驗結果及分析

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

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

圖1 LF算法與K-means算法聚類結果比較

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

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

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

5 總結

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

[1]任姚鵬，陳立潮，張英俊，等.結合語義的特征權重計算方法研究[J].計算機工程與設計，2010,31（10）：2381-2383．

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

[3]俞輝.基于改進LSA的文本聚類算法[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]李雷,羅紅旗,丁亞麗.一種改進的模糊C均值聚類算法[J].計算機技術與發(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ōu)化的構件聚類算法[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

運城學院教學改革研究項目[JG201418]

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

〔責任編輯 高海〕