文 武，萬玉輝，張?jiān)S紅，文志云

(1.重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué)通信新技術(shù)應(yīng)用研究中心，重慶 400065； 3.重慶信科設(shè)計(jì)有限公司，重慶 401121)

1 引言

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

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

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

2 相關(guān)算法

2.1 主成分分析

主成分分析PCA在盡可能保留較多原始特征信息的基礎(chǔ)上，根據(jù)方差最大化，將原始的高維特征重新組合在低維空間上表達(dá)出來，提取出貢獻(xiàn)率大的綜合特征，實(shí)現(xiàn)降維。PCA算法將數(shù)據(jù)空間表示成矩陣的形式，通過標(biāo)準(zhǔn)化處理來求得矩陣的協(xié)方差矩陣，對協(xié)方差矩陣的特征值進(jìn)行排序，計(jì)算出靠前的特征值對應(yīng)的特征向量，構(gòu)成一組線性無關(guān)的降維矩陣，實(shí)現(xiàn)到低維空間的映射，算法框圖如圖1所示。

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

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

(1)

(2)

(3)

(4)

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

BTBF=λF

(5)

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

(6)

2.2 卡方統(tǒng)計(jì)

卡方統(tǒng)計(jì)(CHI)常在實(shí)驗(yàn)中用于衡量觀察結(jié)果和預(yù)期結(jié)果的差異，即確定2個(gè)隨機(jī)變量之間的聯(lián)系。在文本分類中CHI常用來評估特征詞和文本類別的相關(guān)程度，基本思想如下所示：

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

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

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

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

(7)

其中，Nd表示文本集合中文檔的總數(shù)，A表示ci類中含有特征tk的文檔數(shù)，B表示含特征tk但不屬于ci類的文檔數(shù)，C表示ci類中不含特征tk的文檔數(shù)，D表示不屬于ci類且不含特征tk的文檔數(shù)。特征對某類的CHI統(tǒng)計(jì)值越高，則代表含有此類別的信息量越大，它與該類別相關(guān)性越強(qiáng)。

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

(8)

(9)

其中，z表示類別數(shù)，p(ci)表示ci類中的文檔數(shù)占總文檔數(shù)的比值。式(8)是指特征詞與類別CHI值的最大值，式(9)指特征詞與所有類別CHI值的平均值?，F(xiàn)有的文本數(shù)據(jù)，往往含有較多類別，算術(shù)平均值的評價(jià)模式常常因?yàn)槲谋緮?shù)據(jù)過大及分布不均，造成準(zhǔn)確率偏低。因此，本文采用式(8)直接對特征的CHI值比較，優(yōu)先選取具有強(qiáng)相關(guān)性的特征。

3 卡方統(tǒng)計(jì)的不足與改進(jìn)

特征詞僅出現(xiàn)在個(gè)別類別中，并在此類別中的多個(gè)文檔中多次出現(xiàn)，則此特征詞對此類別代表性越強(qiáng)。針對上述思想，對傳統(tǒng)CHI算法分別引入對應(yīng)的調(diào)整因子，來獲取更精確的CHI計(jì)算模型，在本文中簡稱為ICHI(Improved CHI)。

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

(10)

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

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

(11)

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

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

(12)

其中，n是總的類別數(shù)，n(tk)是特征詞所出現(xiàn)的類別個(gè)數(shù)。

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

χ2(tk,ci)=

(13)

4 基于ICHI和PCA的特征選擇

4.1 特征選擇

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

(14)

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

(15)

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

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

(16)

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

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

(17)

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

4.2 基于ICHIPCA的特征選擇流程

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

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

下面對ICHIPCA算法進(jìn)行詳細(xì)描述。

算法1ICHIPCA

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

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

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

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

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

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

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

步驟6對特征詞集合ICHIFeature的卡方值進(jìn)行排序；

步驟7根據(jù)需要，選取前T個(gè)特征詞放入集合FinalICHI，為最終的篩選結(jié)果；

步驟8對FinalICHI中的特征詞計(jì)算權(quán)重(TF-IDF)，構(gòu)建文檔-詞矩陣；

步驟9標(biāo)準(zhǔn)化處理矩陣，求協(xié)方差矩陣；

步驟10計(jì)算特征值及對應(yīng)特征向量，選取前K個(gè)特征值；

步驟11由前K個(gè)特征值對應(yīng)的特征向量構(gòu)成降維矩陣進(jìn)行投影，存入終選特征集合FinalICHIPCA。

5 實(shí)驗(yàn)與結(jié)果分析

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

5.1 評價(jià)指標(biāo)

目前，使用最多的評價(jià)指標(biāo)為分類準(zhǔn)確率、查全率、查準(zhǔn)率和F1值，其計(jì)算方式如式(18)～式(21)所示。

準(zhǔn)確率:

(18)

查準(zhǔn)率：

(19)

查全率：

(20)

F1:

(21)

其中，各指標(biāo)代表的含義如表1所示。

Table 1 Parameters meaning in evaluation indicators表1 評價(jià)指標(biāo)中的參數(shù)意義

5.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

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

Table 2 Experimental data表2 實(shí)驗(yàn)數(shù)據(jù)

5.3 結(jié)果分析

(1)ICHI特征選擇。

為證明ICHI算法的有效性，以200～2 000中選擇10個(gè)特征維數(shù)進(jìn)行實(shí)驗(yàn)對比分析，對每一維度下的最佳值加黑標(biāo)記。

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

Table 3 Classification accuracy rate of each algorithm表3 各算法的分類準(zhǔn)確率

(2)ICHIPCA特征選擇。

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

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

Figure 3 Cumulative contribution rate圖3 累積貢獻(xiàn)率

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

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

(3)分類性能對比。

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

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

Figure 4 Precision rate圖4 查準(zhǔn)率

Figure 5 Recall rate圖5 查全率

Figure 6 F1value圖6 F1值

6 結(jié)束語

本文利用CHI能夠較準(zhǔn)確選出重要特征及PCA算法能夠?qū)μ卣鹘M合實(shí)現(xiàn)降維的特點(diǎn)，提出了結(jié)合卡方統(tǒng)計(jì)和主成分分析法的特征選擇算法。對CHI算法的不足引入了歸一化文檔詞頻和特征分布因子，并去除負(fù)相關(guān)特性的影響，提出了改進(jìn)CHI計(jì)算模型，解決了文檔長短不一、忽略特征分布及負(fù)相關(guān)特性造成的選詞不精問題。為降低維度的同時(shí)不失去重要特征信息，在改進(jìn)CHI的基礎(chǔ)上，通過PCA進(jìn)行重要特征提取，實(shí)現(xiàn)二次降維。通過實(shí)驗(yàn)驗(yàn)證，ICHI算法同原始CHI、IG及文獻(xiàn)[16]中算法對比，在多個(gè)不同維度下及大部分類別中，分類性能均得到了一定的提高，表明了ICHI的有效性。ICHIPCA算法在絕大部分維度下的準(zhǔn)確率、所有類別中的F1值均得到了提升，表明了ICHIPCA進(jìn)行特征選擇能夠在大幅度降低維度的同時(shí)提升分類效果。由于本文工作在ICHI初選和KNN分類器下完成，未來工作將嘗試多種過濾式文本特征選擇方法與PCA算法結(jié)合，在多種分類器下進(jìn)一步檢驗(yàn)?zāi)Ｐ偷挠行浴?/p>