分塊主成分分析在文本特征抽取中的應用

洪軍建,珠 杰

(西藏大學 計算機科學系,西藏 拉薩 850000)

?

分塊主成分分析在文本特征抽取中的應用

洪軍建,珠 杰

(西藏大學 計算機科學系,西藏 拉薩 850000)

為了降低原始文本特征空間的維數，獲得較高的分類精度與執行效率，對多種文本特征提取方法進行了研究，如卡方、互信息、信息增益、主成分分析(PCA)等。針對傳統文本特征抽取方法存在的精度不高、執行效率低等問題，提出了一種基于分塊主成分分析的文本特征提取算法。該算法通過K-均值詞聚類進行特征詞分塊，再對各分塊實施PCA操作抽取出更具代表性的特征項，最后使用支持向量機分類器對文本進行分類。實驗結果表明：分塊主成分分析的分類指標Fβ=1達到了88.7%,執行時間為353 s，能夠有效提高文本分類精度與執行效率。

主成分分析；分塊；特征抽取；詞聚類

0 引言

隨著網絡的發展，互聯網上涌現出大量的文本數據，處理海量數據的自動文本分類技術變得越來越重要，自動文本分類已成為處理和組織大量文檔數據的關鍵技術[1]。對于采用向量空間模型(vector space model,VSM)的大多數分類器來說，文本預處理成為分類的瓶頸，高維的特征空間不僅增加了存儲與計算的復雜度，而且其中很多特征是與分類無關的，甚至有一些是誤導分類的噪聲數據。為了達到降低特征空間維數、提高分類器的效率和精度的目的，需要從原始特征空間中挑選出一些具有代表性的特征。 研究發現：當特征維度高到一定程度時，分類器的精度隨著特征維度增高而下降[2-3]。因此，降維技術與合適的文檔表示形式對于構造一個良好的分類器來說是至關重要的。

主成分分析(principal component analysis,PCA)作為一種有效的特征提取技術，在數據壓縮與信息抽取方面得到了廣泛的應用并表現出了很好的性能[4-7]。然而，主成分分析的核心是多維隨機向量的協方差矩陣，當向量的維度過高時，協方差矩陣將會變得非常大，目前，普通微型計算機有限的內存很難滿足這一要求。即使內存足夠大，可以使其完全駐留在內存中，在對其施加運算如求特征值、特征向量時，其計算代價也是十分高昂的。

近幾年，有關PCA的研究，主要集中在利用PCA與其他方法的組合進行文本與圖像的特征抽取以及利用分塊PCA進行圖像特征抽取。文獻[8]研究了基于潛在狄利克雷分配(latent dirichlet allocation,LDA)與PCA組合的文本特征抽取方法，與未進行特征降維的分類結果相比，其F值、準確率、召回率均有顯著地提升。文獻[9]設計了一種集成主成分分析PCA與支持向量機分類算法的垃圾網頁檢測方法，結果表明該方案具有較高的檢測率(0.851)。文獻[10]研究了基于神經網絡模型的主成分分析在情感分類上的應用，驗證了基于PCA的反向傳播神經網絡(back propagation neural network,BPNN)進行特征降維對文本情感分類的有效性。文獻[11]采用PCA與遺傳規劃(genetic programming,GP)相結合的模型對漢語文本的可讀性進行了研究，表明該模型能夠極大地提高對文本理解難度預測的精度。文獻[12]提出了分塊PCA人臉識別方法，有效地抽取了圖像的局部特征，并在耶魯大學人臉數據庫上取得了較好的識別能力。文獻[13]對基于分塊主成分分析(block principal component analysis,Block-PCA)在圖像數據壓縮領域的應用進行了研究，結果表明該方法可以極大地提高圖像數據的壓縮比。

但是，有關分塊PCA在文本特征抽取方面的研究與應用幾乎難以找到，因此，本文嘗試性地將分塊PCA的特征抽取技術引入文本分析中，探討文本的特征抽取與降維方法，并在支持向量機(support vector machine,SVM)分類器上測試,取得了較好的分類效果。

1 PCA 的文本特征抽取

對經過分詞處理的文本進行詞頻統計，根據詞頻-逆向文檔頻率(term frequency-inverse document frequency, TF-IDF)權值計算公式，即可將一個文本表示為文本向量形式。計算公式為：

(1)

假設文本語料庫原始特征空間的維度為n,文檔總個數為m，每個文本可表示為向量Xk的形式：

Xk=(wk1,wk2,wk3,…,wki,…),k=1,2,3,…,m;i=1,2,3,…,n，其中：k為語料庫中第k個文本；wki為第i個特征詞的TF-IDF值。那么文本語料庫可表示為矩陣形式如下：

A=(X1,X2,X3,…,Xm)T，

其中：Xk為第k個文本的向量表示。由于矩陣A每一列對應一個特征詞：

wi=(w0i,w1i,…,wki)T，

那么A亦可表示為：

A=(w1,w2,w3,…,wn)。

然后，對矩陣A實施PCA操作。

將協方差矩陣表示為Zcov，大小為n×n,其中的各元素可以按照式(2)分別計算：

(2)

進一步可求得Zcov的特征值與特征向量對(λ1,e1),(λ2,e2),…,(λn,en)T，其中ei=(ei1,ei2,ei3,…,ein)，λ1≥λ2≥λ3≥…≥λn≥0，那么，可以根據式(3)得到第i主成分：

Yi=eiAT,i=1,2,3,…,n。

(3)

在諸多主成分Yi中，Y1在總方差中占的比重最大，其余主成分Y2,Y3,Y4,…,Yn在總方差中占的比重依次遞減，說明越往后的主成分綜合原信息的能力越弱。以后的分析可以用前面幾個方差最大的主成分來進行，一般情況下，要求前幾個主成分所包含的信息不少于原始信息的85%，這樣既減少了變量的數目，又能夠用較少的主成分反映原有變量的絕大部分信息，達到了數據降維與去除變量間相關的目的。

原始文本矩陣A經PCA變換得到主成分矩陣Apca，取其前r個主成分的矩陣可表示為：

2 Block-PCA的文本特征抽取

2.1 分塊矩陣表示

基于詞特征的文本處理中，由于高維特征空間存在維數災難、文本分類精度低等困難，本文利用分塊 PCA探討文本特征抽取的問題。分塊PCA的基本思想是從原始的文本向量矩陣出發，先對文本向量矩陣A進行分塊，分塊得到的子矩陣采用 PCA方法進行特征抽取，經過對各個分塊的特征組合形成新的特征空間，從而實現對原始特征空間的降維。

分塊PCA先將一個m×n的文本向量矩陣A分成q個分塊子矩陣，即原始文本向量矩陣可表示為：

經過詞聚類形成的第i個分塊可表示的矩陣形式如下：

2.2 特征詞聚類分塊

根據以上分析可知：一種可行的分塊方法是聚類分析，聚類的距離函數宜采用相關系數。在本文中，采用K-均值(K-means) 的聚類方法進行分塊，以向量間的相關系數作為聚類函數K-means的距離函數。

算法描述如下：

(Ⅲ)將每個特征詞向量分配給相關系數距離最近的聚類中心。

算法終止時，形成k個特征詞分塊B1,B2,B3,…,Bk。

2.3 特征抽取

3 實驗與結果分析

3.1 數據集及評價指標

為了評估基于Block-PCA的特征抽取方法在文本分類應用上的有效性，本文采用了復旦大學計算機信息與技術系國際數據庫中心提供的中文語料集。從其中含文檔數目較多的9類中隨機抽取3 000篇文檔，然后按訓練集與測試集的比例4∶1的原則進行實驗。

實驗中的分類器采用SVM分類器,其懲罰參數設置為57，高斯核函數設置為0.136，為了評價算法在語料集上的整體性能，采用了宏平均召回率MacroR,宏平均準確率MacroP，宏平均Fβ測度值，這里取β=1，即MacroFβ=1作為分類評價指標。其計算公式如下:

(4)

(5)

(6)

3.2 測試結果分析

表1 特征提取方法的SVM分類結果

表1比較了5種特征提取方法的SVM分類結果，特征提取方法分別為：卡方(CHI-square,CHI)、互信息(mutual information,MI)、信息增益(information gain,IG)、主成分分析(PCA)和分塊主成分分析(Block-PCA)。從表1可以看出：經過特征抽取后使用SVM分類器進行訓練和測試，Block-PCA總耗時最少，宏平均評估指標Fβ=1達到了88.7%。IG的宏平均評估指標Fβ=1達到了88.8%，比Block-PCA略高0.1%，但是其訓練與測試的總耗時卻高達4 342 s，是Block-PCA的12倍以上。MI的總耗時是除Block-PCA以外最低的，但是其宏平均評估指標Fβ=1也是最低的，比Block-PCA低了12%左右。原始的PCA效果是最差的，其總耗時最高，宏平均評估指標Fβ=1僅次于最低的MI，與改進的Block-PCA相差了近11%。因此，基于Block-PCA的特征提取在SVM分類器上的分類效果是理想的，總耗時是最少的，是一種行之有效的文本特征抽取方法。

在經過PCA保持85%以上信息的前提下，經過SVM分類器進行分類實驗，分析分塊數與分類性能之間的關系，實驗結果如圖1所示。

圖1 Block-PCA特征抽取時分塊個數對分類效果的影響

由圖1可以看出：基于Block-PCA特征抽取時的分塊策略對分類效果有很大影響。當分塊數為60～80時，分類器已經能取得很好的分類效果，繼續增加分塊個數，分類器的分類效果幾乎不再提升。相反，分塊個數越多，在通過詞聚類形成塊的過程中，K-means聚類算法收斂速度越慢；同時，當分塊個數太多時，各塊包含的詞特征個數會比較少，抽取的特征代表性比較差，需抽取較多的特征才能達到理想效果，無法實現較高的降維。當分塊個數較少時，極端情況為不分塊，即整體為一塊，塊內含有很多相關性很低的詞特征。由PCA理論可知：直接進行PCA操作，抽取的特征亦不理想，分類效果較差。因此，合適的分塊策略對Block-PCA特征抽取影響是很大的。

4 結束語

基于Block-PCA的文本特征抽取是一種行之有效的文本特征抽取方法，它對高維的文本特征空間具有很強的特征抽取與降維能力。通過Block-PCA與PCA、CHI、MI、IG抽取的特征在SVM分類器上的分類效果對比，證明Block-PCA抽取的特征評估指標達到了較理想的結果，時間代價是最低的。接著分析了分塊策略對特征抽取的影響，分析結果表明：合適的分塊策略可以抽取出更具代表性的特征，從而可以獲得更好的分類精度與降維效果。未來的工作準備在以下兩個方面開展：研究Block-PCA在大規模文本語料庫上的分布并行算法，以提高該特征抽取方法處理大數據的能力；利用該方法對藏文文本語料進行特征抽取，以驗證該方法在多語種處理上的一致性。

[1] 尚文倩，黃厚寬，劉玉玲，等.文本分類中基于基尼指數的特征選擇算法研究[J].計算機研究與發展，2006,43(10):1688-1694.

[2] Almuallim H,Dietterich T G.Learning with Many Irrelevant Features[C]//Proceedings of the Ninth National Conference on Artificial Intelligence.1991:547-552.

[3] Kira K,Rendell L A.A Practical Approach to Feature Selection[C]//Proceedings of the Ninth National Conference on Machine Learning.1992:249-256.

[4] Kano M,Nagao K,Hasebe S,et al.Comparison of Statistical Process Monitoring Methods:Application to the Eastman Challenge Problem[J].Computers & Chemical Engineering,2000,24(2/7):175-181.

[5] Hayes D J,Sader S A.Change Detection Techniques for Monitoring Forest Clearing and Regrowth in a Tropical Moist Forest 162[J].Photogrammetric Engineering & Remote Sensing,2001,67:1067-1088.

[6] Collins M,Dasgupta S,Schapire R E.A Generalization of Principal Components Analysis to the Exponential Family[C]//Advances in Neural Information Processing Systems.2001:617-624.

[7] Lei T,Sewchand W.Eigenstructure Approach to Region Detection and Segmentation[C]// IEEE International Conference IEEE.1994:456-459.

[8] 劉海旭.基于PCA和LDA的文本分類系統設計與實現[D].北京:北京郵電大學,2013.

[9] 李法良,朱焱,曾俊東.集成PCA降維與分類算法的垃圾網頁檢測[J].計算機應用與軟件,2014,31(10):269-272.

[10] Vinodhini G,Chandrasekaran R M.Sentiment Classification Using Principal Component Analysis Based Neural Network Model[C]// Information Communication and Embedded Systems (ICICES),2014 International Conference on IEEE.2014:1-6.

[11] Lee Y S,Tseng H C,Chen J L,et al.Constructing a Novel Chinese Readability Classification Model Using Principal Component Analysis and Genetic Programming[C]//Advanced Learning Technologies (ICALT),2012 IEEE 12th International Conference on IEEE.2012:164-166.

[12] 陳伏兵,謝永華,嚴云洋,等.分塊PCA鑒別特征抽取能力的分析研究[J].計算機科學,2006,33(3):155-159.

[13] Lim S T,Yap D F W,Manap N A.Medical Image Compression Using Block-based PCA Algorithm[C]//Computer,Communications,and Control Technology (I4CT),2014 International Conference on IEEE.2014:171-175.

國家自然科學基金項目(61262058)

洪軍建(1987-),男,河南商丘人,碩士生;珠杰(1973-),男,西藏拉薩人,副教授,博士,碩士生導師,主要研究方向為藏文信息處理與數據挖掘等.

2015-06-05

1672-6871(2015)06-0030-05

TP391.1

A