基于改進CHI和PCA的文本特征選擇*

文 武，萬玉輝，張許紅，文志云

(1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學通信新技術應用研究中心，重慶 400065； 3.重慶信科設計有限公司，重慶 401121)

1 引言

文本分類是大數據分析的關鍵技術，在輿情分析、主題分類、情感分析、郵件過濾和金融預測等諸多現實領域中有著廣泛的應用。面對海量的文本數據，文本特征空間的高維稀疏性嚴重影響了分類器的訓練效率及分類精度。因此，從文本中選出與類別屬性相關性較強的特征詞，降低數據維度，剔除噪聲和冗余特征，具有重要研究意義。

目前常用的特征選擇算法有文檔頻率DF(Document Frequency)[1]、互信息MI(Mutual Information)[2]、卡方檢驗CHI(CHI-square Statistics)[3]和信息增益IG(Information Gain)[4]等。這些方法雖然能夠實現對高維度特征向量的縮減，提高分類精度，但都存在局限性，許多學者對此進行了改進。董微等[5]在IG中引入自適應比例因子來調節正負相關特性，通過貝葉斯分類器在不同語料庫下，取得了較好的分類效果。劉海峰等[6]在MI中通過修正因子對低頻詞進行抑制，改善了互信息的選擇效率。宋呈祥等[7]在CHI中根據詞的位置計算權重及相關性系數，提升了分類效果。此外，依靠群智能算法較強的尋優能力，王生武等[8]融合粗糙集和鯨魚優化算法，引入了以屬性依賴度和分類準確率進行加權的適應度函數，提升了分類準確率。劉成鍇等[9]在詞頻-逆文檔頻TF-IDF(Term Frequency-Inverse Document Frequency)的基礎上，用遺傳算法對文本特征進行再次選擇，大幅度降低了特征維度。為了更進一步去除冗余特征，Uguz[10]通過結合信息增益和主成分分析法，提升了分類精度。Ge等[11]將特征向量化，通過主成分分析法進行降維處理，同基于神經網絡的算法對比，得到的情感分析準確率更高。

CHI統計通過對特征打分，獲取靠前的特征，實現降維，在特征選擇上具有一定的優勢。但是，傳統的CHI統計卻沒有考慮詞頻問題，忽略了文檔長度及負相關特性造成的特征篩選不準確問題。為解決上述問題，本文引入了歸一化的文檔詞頻，加入特征分布因子，通過判斷正負去除了負相關特性帶來的影響，完善了CHI計算模型。通過改進CHI進行特征選擇，依然可能存在維度偏高，代表性不強問題，而主成分分析PCA(Principal Component Analysis)[12]利用協方差矩陣能夠在保留原始信息的基礎上實現降維。本文將兩者結合起來提出了一種通過兩階段進行特征篩選的算法ICHIPCA(Improved CHI-square Statistics and Principal Component Analysis)，以獲取精選特征集合。

2 相關算法

2.1 主成分分析

主成分分析PCA在盡可能保留較多原始特征信息的基礎上，根據方差最大化，將原始的高維特征重新組合在低維空間上表達出來，提取出貢獻率大的綜合特征，實現降維。PCA算法將數據空間表示成矩陣的形式，通過標準化處理來求得矩陣的協方差矩陣，對協方差矩陣的特征值進行排序，計算出靠前的特征值對應的特征向量，構成一組線性無關的降維矩陣，實現到低維空間的映射，算法框圖如圖1所示。

Figure 1 Block diagram of PCA algorithm 圖1 PCA算法框圖

圖1描述了算法基本流程，下面對算法進行詳細闡述。假設一個文本數據集有m篇文檔，每篇文檔中包含N個特征，就會形成一個m行N列的矩陣，如式(1)所示，矩陣A中xij表示第i篇文檔的第j維特征。隨后，計算每一列平均樣本如式(2)所示，標準化處理如式(3)所示，對應的協方差如式(4)所示。

(1)

(2)

(3)

(4)

隨后，求出BTB的特征值λ、特征向量F，則:

BTBF=λF

(5)

在對主成分選取時，通常是保證累計貢獻率不低于85%。特征值所占的比率也就是原始信息的多少，貢獻率如式(6)所示：

(6)

2.2 卡方統計

卡方統計(CHI)常在實驗中用于衡量觀察結果和預期結果的差異，即確定2個隨機變量之間的聯系。在文本分類中CHI常用來評估特征詞和文本類別的相關程度，基本思想如下所示：

(1)由CHI計算公式計算特征詞與類別的CHI值；

(2)根據所有特征與類別的CHI值大小排序；

(3)選取前T個特征詞作為輸出特征子集。

CHI算法的主要目的是篩選出和類別相關性強的特征，去除噪聲特征，實現降維。在文本分類中，假設有特征詞tk和類別cj，則CHI計算模型如式(7)所示：

(7)

其中，Nd表示文本集合中文檔的總數，A表示ci類中含有特征tk的文檔數，B表示含特征tk但不屬于ci類的文檔數，C表示ci類中不含特征tk的文檔數，D表示不屬于ci類且不含特征tk的文檔數。特征對某類的CHI統計值越高，則代表含有此類別的信息量越大，它與該類別相關性越強。

特征詞的卡方評價模型有2種方式，分別如式(8)和式(9)所示：

(8)

(9)

其中，z表示類別數，p(ci)表示ci類中的文檔數占總文檔數的比值。式(8)是指特征詞與類別CHI值的最大值，式(9)指特征詞與所有類別CHI值的平均值。現有的文本數據，往往含有較多類別，算術平均值的評價模式常常因為文本數據過大及分布不均，造成準確率偏低。因此，本文采用式(8)直接對特征的CHI值比較，優先選取具有強相關性的特征。

3 卡方統計的不足與改進

特征詞僅出現在個別類別中，并在此類別中的多個文檔中多次出現，則此特征詞對此類別代表性越強。針對上述思想，對傳統CHI算法分別引入對應的調整因子，來獲取更精確的CHI計算模型，在本文中簡稱為ICHI(Improved CHI)。

(1)詞頻。CHI算法僅考慮特征詞是否出現在文檔中，沒有考慮特征詞的出現次數，這會導致選詞不準。比如，在體育類中有20篇文檔，“解說”在20篇文檔中各出現1次，“籃球”在其中18篇中各出現20次，這使得特征詞“解說”的CHI值更高，而實際擁有更高頻率的特征詞“籃球”更重要。文獻[13]引入了詞頻，但實際的文檔長度往往差異很大。針對文檔長度不均，本文提出了一種基于類別文檔歸一化的特征頻度因子，如式(10)所示：

(10)

其中，m為每個類別中的文檔總數，tf(tk,dij)表示特征tk在ci類的第j篇文檔dij中出現的次數，N(t,dij)表示在文檔dij中出現的所有特征詞的次數總和，N(ci)為ci類中所有文檔數。直接引入特征詞出現的次數，會忽略各文檔長度和文檔數分布不均勻，所以對每篇文檔進行歸一化處理。

(2)文檔分布。對于具體類別內部，若某特征詞僅在此類中的個別文檔中出現，在其它文檔中不出現，則該特征詞所代表的類別信息就少很多。若某特征詞在類別中的所有文檔中都出現，則此特征就含有重要類別信息。基于此，本文提出了類別內部特征詞的文檔分布因子，如式(11)所示：

(11)

其中，d(tk,ci)表示特征tk在ci類中出現的文檔數，N(ci)為ci類中所有文檔數。

(3)類別頻。對于數據集中的所有類別，借助逆文檔頻率IDF[14]思想，若特征詞只出現在極少類別中，它就會比在較多類別中都出現的特征更重要。基于此，本文提出了逆類別分布因子，如式(12)所示:

(12)

其中，n是總的類別數，n(tk)是特征詞所出現的類別個數。

(4)負相關特性。負相關特性[15]會對特征的重要性產生負面的影響，從式(7)中可以看出，特征詞與類別成正相關，即A×D-B×C>0，卡方值越大，特征越重要。若特征詞與類別成負相關，即A×D-B×C<0，該特征詞對此類別越不重要，卡方值應越小，但實際卡方值卻變大，這就影響了分類效果。為避免上述干擾，當A×D-B×C<0時，特征項應忽略掉。綜合以上因素，ICHI計算方法如式(13)所示：

χ2(tk,ci)=

(13)

4 基于ICHI和PCA的特征選擇

4.1 特征選擇

首先通過ICHI算法從預處理后的特征集合中選取分值較高的特征(T項)作預選特征集合。將上述預選特征集合表示成TF-IDF值的文本向量，進行PCA二次抽取。經過處理之后，預選的特征結果表示成文檔-詞向量形式，文本向量表示如矩陣H所示:

(14)

通過式(2)～式(4)進行標準化處理，計算文本向量的N階協方差矩陣I=HTH，求得其對應特征值λj及其相應的特征向量ej，其中，j∈{1,2,…,T}。所有的特征向量按列構成向量矩陣E，則有：

(15)

根據式(15)中的對角矩陣的特征值從大到小排序，特征值λ1,λ2,…,λT分別對應特征向量e1,e2,…,eT，這些特征向量構成正交投影矩陣E。

E=[e1,e2,…,ek,…,eT]

(16)

取前k個特征值對應的特征向量構成新的矩陣P=[e1,e2,…,ek],其中各列向量線性無關。矩陣H在特征向量P上的投影為主成分矩陣，如式(17)所示：

D=H·P=[PC1,PC2,…,PCk]

(17)

其中，PC1為第1個主成分向量，依次類推，共獲取前k個主成分向量。通過上述ICHI算法和PCA算法，將特征空間降到k維。

4.2 基于ICHIPCA的特征選擇流程

ICHIPCA算法進行文本特征選擇的流程如圖2所示，其中虛線處為ICHI算法和PCA算法。

Figure 2 ICHIPCA feature selection process圖2 ICHIPCA特征選擇流程

下面對ICHIPCA算法進行詳細描述。

算法1ICHIPCA

輸入：文本數據集X，初始特征詞存放集合InitialFeature，ICHI處理過的特征詞集合ICHIFeature，ICHI篩選出的特征詞集合FinalICHI。

輸出：終選特征詞集合FinalICHIPCA。

步驟1對文本數據集X進行預處理(分詞、去停用詞)，將預處理后的特征詞存入初始特征詞集合InitialFeature中；

步驟2判斷初始特征集合中所有特征與類別的互相關特性值(AD-BC)，如果大于0，轉步驟3，如果小于0，則將ICHI值置為0，并將此特征從InitialFeature中去除；

步驟3計算特征詞的歸一化詞頻a(t)、文檔頻b(t)和類別頻c(t)；

步驟4根據ICHI算法計算特征詞的ICHI值，將特征詞的ICHI值放入特征詞集合ICHIFeature，并將此特征從InitialFeature中去除；

步驟5判斷集合InitialFeature是否含有特征詞，有轉步驟2，否則轉步驟6；

步驟6對特征詞集合ICHIFeature的卡方值進行排序；

步驟7根據需要，選取前T個特征詞放入集合FinalICHI，為最終的篩選結果；

步驟8對FinalICHI中的特征詞計算權重(TF-IDF)，構建文檔-詞矩陣；

步驟9標準化處理矩陣，求協方差矩陣；

步驟10計算特征值及對應特征向量，選取前K個特征值；

步驟11由前K個特征值對應的特征向量構成降維矩陣進行投影，存入終選特征集合FinalICHIPCA。

5 實驗與結果分析

為驗證本文算法的有效性，實驗采用IG、CHI、ICHI、文獻[16]中的特征選擇方法及ICHIPCA對文本集合進行特征選擇。首先使用jieba分詞及哈爾濱工業大學停用詞表對文本數據分別進行分詞和去停用詞；文本表示采用向量空間模型；TF-IDF計算特征權重，通過KNN(K- Nearest Neighbor)分類器進行驗證。

5.1 評價指標

目前，使用最多的評價指標為分類準確率、查全率、查準率和F1值，其計算方式如式(18)～式(21)所示。

準確率:

(18)

查準率：

(19)

查全率：

(20)

F1:

(21)

其中，各指標代表的含義如表1所示。

Table 1 Parameters meaning in evaluation indicators表1 評價指標中的參數意義

5.2 實驗環境與數據

本次實驗在Python和Pycharm 3.7的集成開發環境下，調用sklearn模塊進行實驗仿真。實驗數據從李榮陸教授提供的語料庫中選取，選出了包括藝術、教育、文學、計算機、歷史和醫療在內的6個類別，訓練集和測試集的文檔數量大致按1∶1比例劃分，共5 403篇文檔，詳細數據如表2所示。

Table 2 Experimental data表2 實驗數據

5.3 結果分析

(1)ICHI特征選擇。

為證明ICHI算法的有效性，以200～2 000中選擇10個特征維數進行實驗對比分析，對每一維度下的最佳值加黑標記。

表3表明，幾種特征選擇算法初始階段均是隨著維度的增加，分類準確率在慢慢提高，達到一定高度后開始回落。這表明，特征維數偏低會漏掉重要信息，降低分類準確率；特征維數過高，會摻雜噪聲特征，影響分類效果。此外，ICHI算法在7個特征維數下取得了最好分類效果，同IG和CHI相比，各個維度下的準確率分別提高了約0.3%～3.9%和0.5%～4.3%。同文獻[16]中的算法對比，ICHI算法盡管在1 200,1 600和2 000維度下分類準確率略低，但在其它維數下提高了大約0.7%～2.9%。總的來說，ICHI算法進行特征選擇時效果優于其他特征選擇算法，能夠獲取更能表達類別信息的特征集合。

Table 3 Classification accuracy rate of each algorithm表3 各算法的分類準確率

(2)ICHIPCA特征選擇。

通過上述實驗分析，ICHI在800～1 200維度間達到了最好分類準確率。因此，為了最大可能地保留有效特征，在上述ICHI算法下選取前1 200個特征詞，再利用PCA算法提取主要成分，在低維度下將上述特征信息重新表達，以驗證ICHIPCA算法的有效性。

由圖3看出，開始時累積貢獻率隨著主成分數量增加快速增加，后期增加速度變緩。這是由于方差最大化，靠前的特征值較大，所以增加相同的主成分時，前期的特征值累積和快速增加，靠后的特征值越來較小，累積貢獻率的增加速度會漸漸變小。

Figure 3 Cumulative contribution rate圖3 累積貢獻率

由表4可知，ICHIPCA在特征維度為100～600時，分類準確率快速增加，600維時達到最大值，由圖3知，此時累積貢獻率約為0.892，超過了0.85，保留了絕大部分有用信息。特征維度為700～1 000時，分類準確率略有回落并趨于穩定，正好和圖3匹配。因為隨著提取的主成分增加，大量特征信息被快速獲取，所以隨著特征維數的增加，分類準確率快速提升。后期特征值較小，含有少量相關性較弱或者干擾的特征信息，所以分類準確率會略微降低并趨于穩定。整體上來說，引入PCA算法后，盡管在1 000維度下，相比ICHI算法分類準確率降低了1.1%，100維度下相比文獻[16]算法減少了1.9%，但在200～900維度時，相比于其它特征選擇算法，在8個特征維度下都實現了分類效果的提升，表明了ICHIPCA的可行性。

Table 4 Classification accuracy rate of algorithms 表4 低維空間中各算法的分類準確率

(3)分類性能對比。

為更進一步驗證ICHIPCA算法的有效性，在保證分類準確率的前提下，對比算法選取1 200維特征，ICHI初選1 200維特征，輸入PCA算法后取前600維特征，計算各個類別下的查準率、查全率和F1值。

通過圖4可知在文學類別中，盡管文獻[16]算法相比ICHIPCA算法及其它算法在查準率上能夠取得較好的值，但在其它類別中，ICHIPCA算法的查準率更好。對于查全率，由圖5可知，在藝術類別中，ICHI方法和ICHIPCA方法相差無幾，達到最高，其他類別中，ICHIPCA的值最好。對于綜合評價分類性能的F1值，通過圖6可以看出,ICHI算法在5個類別中高于IG和CHI的，在歷史和醫療類別中高于文獻[16]中的算法，說明了ICHI算法相對于傳統經典算法能夠提高分類性能。ICHIPCA算法下在6個類別中的F1值均高于其他算法的，表明ICHIPCA能夠在降低維度的同時實現分類性能的提升。此外，觀察發現，在計算機和藝術類別，3種評價指標相對于其他類別較高，而教育、歷史類別的評估指標相對偏低。這主要是由于計算機和藝術有明顯的專業詞語，而教育和歷史存在類似的專業詞匯，會造成一定誤判。結果表明，ICHIPCA算法能夠在降低維度的同時提高特征子集的分類準確率，具有更好的分類能力。

Figure 4 Precision rate圖4 查準率

Figure 5 Recall rate圖5 查全率

Figure 6 F1value圖6 F1值

6 結束語

本文利用CHI能夠較準確選出重要特征及PCA算法能夠對特征組合實現降維的特點，提出了結合卡方統計和主成分分析法的特征選擇算法。對CHI算法的不足引入了歸一化文檔詞頻和特征分布因子，并去除負相關特性的影響，提出了改進CHI計算模型，解決了文檔長短不一、忽略特征分布及負相關特性造成的選詞不精問題。為降低維度的同時不失去重要特征信息，在改進CHI的基礎上，通過PCA進行重要特征提取，實現二次降維。通過實驗驗證，ICHI算法同原始CHI、IG及文獻[16]中算法對比，在多個不同維度下及大部分類別中，分類性能均得到了一定的提高，表明了ICHI的有效性。ICHIPCA算法在絕大部分維度下的準確率、所有類別中的F1值均得到了提升，表明了ICHIPCA進行特征選擇能夠在大幅度降低維度的同時提升分類效果。由于本文工作在ICHI初選和KNN分類器下完成，未來工作將嘗試多種過濾式文本特征選擇方法與PCA算法結合，在多種分類器下進一步檢驗模型的有效性。