結合LSA的中文譜聚類算法研究

摘 要:傳統的文本譜聚類需要的文本相似矩陣依賴于向量空間模型，忽略了詞與詞之間的語義關系，存在詞頻維數過高、計算代價高等問題。針對這些問題，提出了一種基于潛在語義分析(latent semantic analysis，LSA)的文本相似矩陣構造方法，利用奇異值分解(singular value decomposition，SVD)降維，在低維的語義空間表示文本，以此來提高同類文本間的語義相似度，并進行了相關對比實驗。在該實驗中，改進方法的聚類效果要好于傳統的方法，從而驗證了改進方法的有效性和可行性。

關鍵詞:文本聚類; 潛在語義分析; 奇異值分解; 譜聚類

中圖分類號:TP391 文獻標志碼:A

文章編號:1001-3695(2010)03-0917-02

doi:10.3969/j.issn.1001-3695.2010.03.030

Research of Chinese spectral clustering with LSA

XIONG Zhong-yang， BAO Zi-qiang， LI Zhi-xing， ZHANG Yu-fang

(College of Computer Science， Chongqing University， Chongqing 400044， China)

Abstract:Traditional text samples similarity matrix for spectral cluster heavily rely on the vector space model which ignores the semantic relationship among terms. It will give rise to problems such as curse of dimensionality， feature redundancy and high computing cost. To solve the problems above， this paper proposed a new method based on LSA to solve it， which used SVD to lowering rank of matrices. The experimental results turn out that the new method enhances the cluster accuracy and less the data-process elapsed time.

Key words:text clustering; LSA; SVD; spectral cluster

0 引言

聚類分析是模式識別和機器學習的重要研究領域。所謂聚類(clustering)就是將數據對象分組成為多個類或簇(cluster)，使得在同一簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。聚類分析在文本數據挖掘中有著非常重要的應用，被廣泛地應用于文本數據挖掘和信息檢索等領域，可以用來改進信息檢索系統的查準率和查全率，也可用于查找最接近的文本，還可用于對Web上的文本進行分層次的聚類等[1]。傳統的聚類算法，如K-means、EM等都是建立在凸球形的樣本空間上，但當樣本空間不滿足凸形時，算法容易陷入局部最優。譜聚類算法(spectral clustering algorithm)避免了這個問題。該算法建立在圖論中的譜圖理論基礎上，其本質是將聚類問題轉換為圖的最優劃分問題。與傳統的聚類算法相比，譜聚類算法將聚類轉換為一個代數上的矩陣求解問題，具有能在任意形狀的樣本空間上聚類且收斂于全局最優解的優點[2]。

由于譜聚類算法起源于譜圖理論，當把它應用于文本聚類時，如何抽取文本特征來表示文本成為一個首要問題。傳統的思路是使用基于關鍵詞集的文檔向量表示模型，但是這種方式忽略了詞與詞之間的語義關系，存在詞頻維數過高、聚類算法計算復雜度高等問題，往往并不能準確描述文檔間的語義相關性。潛在語義分析(LSA)技術則可以在一個低維潛在概念語義空間重新描述自然語言文本，從而可以更好地反映文本之間的語義相似度[3]。

1 LSA簡介

文本數據的圖表示模型對基于圖的聚類算法最終的效果具有重要的影響。在傳統的基于關鍵詞集的向量空間模型中，文本間的相似性取決于文檔間的詞匯特征的共現率。然而，在自然語言文本中普遍存在著同義詞和多義詞的現象，多義詞的現象導致兩篇包含很多共有詞匯的文本并不一定很相似，而同義詞現象導致相似文本間可能并沒有太多的共現詞匯，這就造成了詞條的語義意義上的大量冗余。這樣，基于詞條特征空間的文檔表示有時并不能很好地反映文檔之間的語義相關性，而且文本數據的向量空間表示模型中，樣本都具有幾千幾萬的維度，算法僅處理這些高維數據就需要花費大量時間。針對文本的這一特點，LSA[4]利用奇異值分解(SVD)技術對高維的詞條—文檔矩陣進行處理，在潛在的語義結構子空間中重新表示文本及文本間的相似度，同時達到降維的目的。其數學描述如下:

設詞條—文檔矩陣X是個m×n矩陣，其中m為詞條數，n為文本集的文檔數。令k<

X=SVDT(1)

其中:S、D是m×r和n×r的正交矩陣，分別稱為矩陣X的左右奇異向量矩陣;V是r×r的對角矩陣，稱為矩陣X的奇異標準形，其對角元素為矩陣X的奇異值。

V=diag(σ1，σ2，…，σr) σ1≥σ2≥…≥σr>0(2)

矩陣X的奇異值按遞減排列成對角矩陣V，取V的前k個最大奇異值構成k×k的V，取S和D的前k列構成m×k的Sk和n×k的Dk，構建X的k-秩近似矩陣Xk。

Xk=SkVkDkT(3)

其中:Sk和Dk中的行向量分別作為詞條向量和文檔向量;k是降維后的維數。實際應用中k值常常取到幾百，極大地減小了文本向量的維數。

2 譜聚類算法介紹

譜聚類算法的思想來源于譜圖劃分理論。假定將每個數據樣本看做圖中的頂點V，根據樣本間的相似度將頂點間的邊E賦權重值W，這樣就得到一個基于樣本相似度的無向加權圖G=(V，E)。那么在圖G中，就可將聚類問題轉換為在圖G上的圖劃分問題。基于圖論的最優劃分準則就是使劃分成的兩個子圖內部相似度最大，子圖之間的相似度最小。劃分準則的好壞直接影響到聚類結果的優劣。常見的劃分準則有Minimum cut、Normalized cut、Ratio cut等。其中2000年Shi等人[5]提出的Normalized cut算法，由于較好地解決了劃分的傾斜問題，研究表明效果最好。本文采用了這一算法，使用Normalized cut的譜聚類算法數學表達如下:

a)給定或建立表示樣本集的相似矩陣W以及聚類數S。

b)計算拉普拉斯矩陣L=D-W。

c)計算D-1L的第一最小特征值到第n最小特征值分別對應的特征向量v1，v2，…，vs，令V=[v1，v2，…，vs]，則V∈Rn×s。令V=[y1，y2，…，yn]T，得到一個k維數據集合{y1，y2，…，yn}。

d)對于數據點y1，y2，…，yn，利用K-均值算法聚成s個類。

3 結合LSA的譜聚類算法

針對上述譜聚類算法存在的不足，本文提出一種結合LSA的譜聚類新方法。該方法的主要思路是:針對傳統的高維詞條文本矩陣，首先對其進行LSA處理，將其映射到一個低維度的語義空間，然后在此基礎上生成譜聚類算法需要的相似矩陣，進而在此基礎上運行譜聚類算法。該方法有兩個好處:a)通過LSA降維，可以減少數據處理時間，一般而言，可以將文本表示從上萬維降低到幾百維;b)將文本映射到潛在語義空間，增強了文本間的語義相關性，提高了譜聚類算法的精度。在中文文本數據集上的實驗表明，該方法達到了以上效果。

4 實驗

4.1 實驗數據集

實驗選取復旦大學李榮陸的中文文本語料庫，共10個類，刪除重復文檔后有中文文檔2 126篇，分詞后產生51 363個詞條，詞條權重使用如下的正則化TF*IDF公式表示:

weighttfidf(Tik)=tf(Tik)×idf(Tk)/∑nj=1(tf(Tik)×idf(Tk))2(4)

4.2 實驗評價標準

實驗采用正則互信息來度量聚類效果，CAT(category label)與CLS(cluster label)之間的正則互信息定義為

NMI=∑ki=1∑kj=1ni，j log(n#8226;ni，j/ni#8226;nj)

(∑ini log ni/n)(∑jnj log nj/n)(5)

其中:n是數據集文本數量;ni和nj分別表示實際類別i與聚類類別j中的文本數量;ni，j代表同時在實際類別i與聚類類別j中的文本數量。當NMI=1時，聚類與實際類別完全匹配;NMI=0時，表明文本完全隨機散布，NMI越高表明聚類效果越好。

4.3 實驗結果與分析

實驗針對進行過LSA處理和未經過LSA處理后的相似矩陣兩種情況進行對比實驗。實驗發現，當k(LSA降維后的維度)取150時，改進后的實驗效果最好。LSA降維處理后，生成相似矩陣時間由幾分鐘降低到不到1 s，時間復雜度大大降低。另外，實際應用譜聚類算法時，為加快運算速度，常常需要對詞條特征矩陣X使用KNN方法處理成稀疏矩陣，不同的K值會對實驗結果造成影響。本文實驗在進行LSA處理和未經過LSA處理兩種情況下，針對K分別取10、20、30、50、80、100、150、200值時的實驗結果進行了分析比較，結果如圖1所示。

圖中折線B代表結合LSA后的譜聚類實驗效果，折線C代表未結合LSA的譜聚類實驗結果。由圖中對比結果可以看出，改進算法的NMI值基本在0.65左右，相對于原始算法提高了15%~20%，這表明本文的算法不僅縮短了數據處理運行時間，而且提高了譜聚類的精度。

5 結束語

為提高譜聚類在文本聚類上的應用，本文引入了LSA技術。實驗結果表明，使用LSA處理后聚類效果有較大提高，而且使得譜聚類表現更穩定。譜聚類算法作為一個新方向，還有許多東西有待進一步發掘，筆者將結合領域知識來進一步改進譜聚類效果。

參考文獻:

[1]HAN J， KAMBER M. Data mining: concept and techniques[M]. San Fransisco: Morgan Kaufmann， 2001.

[2]蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，2008，35(7):14-18.

[3]戴新宇，田寶明，周俊生. 一種基于潛在語義分析和直推式譜圖算法的文本分類方法LSASGT[J].電子學報，2008，36(8):1628-1630.

[4]DEERWESTER S，DUMAIS S， FUMAS G W， et al. Indexing by latent semantic analysis[J]. Journal of the American Society for Information Science， 1990，41(6):391-407.

[5]SHI Jian-bo， MALIK J. Normalized cuts and image segmentation[J]. IEEE Trans on PatternAnalysis and Machine Intelligence， 2000，22(8):888-905.