基于詞頻和信息熵改進(jìn)的卡方特征選擇

劉 輝，張振康，王韓林 ，晏飛揚(yáng)

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

1 引言

文本分類的表示模型一般采用向量空間模型，它有著高維稀疏的缺點(diǎn)，嚴(yán)重影響著文本分類的效果。特征選擇是解決向量空間模型高維度缺陷的有效方法，通過選取優(yōu)質(zhì)的特征子集來代表原始的字符集合，達(dá)到有效表示文本、提高表示效率的目的。信息論和統(tǒng)計(jì)學(xué)思想指導(dǎo)了特征選擇方法的設(shè)計(jì)，一些常用方法如基尼指數(shù)、文檔頻率、信息增益、互信息、卡方統(tǒng)計(jì)、期望交叉熵等均受此啟發(fā)[1]。已有研究表明，CHI相比于其它特征選擇方法更具有優(yōu)勢[2]。

傳統(tǒng)的CHI方法雖然有著時(shí)間復(fù)雜度低、效果良好等優(yōu)點(diǎn)，但也存在不足。該方法統(tǒng)計(jì)了特征詞的文檔頻率，用來評(píng)估特征詞對(duì)文本分類的重要程度，但是忽略了詞頻的影響力，造成了低頻詞缺陷；有些時(shí)候，對(duì)分類起到干擾作用的詞項(xiàng)，會(huì)被誤認(rèn)為重要詞匯，進(jìn)入到文本表示集合中，這就引入了負(fù)相關(guān)因素。針對(duì)以上不足，一些學(xué)者做了大量研究工作。徐明等人[3]將頻度參數(shù)引入到傳統(tǒng)模型中，用改進(jìn)的卡方統(tǒng)計(jì)方法進(jìn)行微博特征提取，取得了較好的實(shí)驗(yàn)效果。馬瑩等人[4]通過引入項(xiàng)的頻度、分散度、集中度等因子對(duì)模型進(jìn)行加權(quán)改進(jìn)，并驗(yàn)證了此方法的有效性。冀俊忠等人[5]由方差統(tǒng)計(jì)策略出發(fā)，聯(lián)合IG與CHI，挖掘了更多類別特征；裴英博等人[6]通過引入文本的分散度、集中度等因素對(duì)模型進(jìn)行加權(quán)，提高了其在類分布不均勻語料集上的分類精確度。閆健卓等人[7]基于類間詞頻和類內(nèi)分布熵，為卡方統(tǒng)計(jì)量添加了詞頻信息，提高了特征項(xiàng)的類別表示能力。李平等人[8]提出相關(guān)系數(shù)，增加特征項(xiàng)在類別中的影響力，從而減弱負(fù)相關(guān)性。宋呈祥等人[9]定義了頻度分布相關(guān)性系數(shù)，選擇局部強(qiáng)相關(guān)性特征，提升了不均衡數(shù)據(jù)集的分類指標(biāo)。謝娜娜等人[10]提出傾向性選擇因子，對(duì)小類別特征的“負(fù)相關(guān)性”起到一定抑制作用。忽略了不均衡數(shù)據(jù)集中特征詞類間分布差異性。李富星等人[11]針對(duì)類內(nèi)分散度、類間集中度同權(quán)的缺點(diǎn)，引入平衡因子，改進(jìn)了類別區(qū)分詞的提取效果。劉海峰等人[12]引入比例因子α，按照其正、負(fù)相關(guān)性進(jìn)行分類并賦以不同權(quán)重以改善CHI模型的特征選擇能力，但是比例因子需要通過經(jīng)驗(yàn)來選擇，誤差較大。樊存佳等人[13]提出自適應(yīng)比例因子，削減了人為選取比例因子帶來的誤差。

對(duì)于特征選擇而言，希望滿足這樣的原則，即特征詞在本類中均勻出現(xiàn)，覆蓋大多數(shù)文檔，且多次出現(xiàn)，在類外分布較少，凸顯本類特征詞的代表能力。針對(duì)以上原則，提出改進(jìn)的卡方統(tǒng)計(jì)方法彌補(bǔ)既有模型的不足。利用詞頻信息的分布，獲取類內(nèi)分散的詞匯；利用信息熵的權(quán)衡，獲取類間集中的詞匯。

2 CHI特征選擇方法

CHI特征選擇方法常被用來評(píng)估特征項(xiàng)tk和類別ci的相關(guān)程度?？ǚ街翟酱?，特征含有的類別信息越多，特征也就越重要。假設(shè)特征項(xiàng)tk和類別ci之間滿足一階自由度的分布條件，則特征tk對(duì)于類別ci的χ2統(tǒng)計(jì)值計(jì)算如式(1)所示

(1)

其中，A表示包含特征tk且屬于類別ci的文檔數(shù)，B表示包含特征tk且不屬于類別ci的文檔數(shù)，C表示不包含特征tk且屬于類別ci的文檔數(shù)，D表示不包含特征tk且不屬于類別ci的文檔數(shù)。

當(dāng)要從全類當(dāng)中挑選特征詞時(shí)，就需要在類別特征詞的基礎(chǔ)上進(jìn)行篩選。具體來說，有兩種策略，分別為求最大值和加權(quán)平均。計(jì)算公式如下：

(2)

(3)

其中，式(2)將出現(xiàn)的最大卡方值作為特征的全局卡方值，式(3)綜合看待各類別卡方值的貢獻(xiàn)，結(jié)合類別頻率，平衡了數(shù)據(jù)傾斜問題。

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

3.1 基于詞頻信息的改進(jìn)

由式(1)可以知道，它只考慮了特征項(xiàng)是否在文檔中出現(xiàn)，而不管其出現(xiàn)了多少次。對(duì)于同樣的只在某一類別ci中出現(xiàn)而在其它類別很少出現(xiàn)特征項(xiàng)，在某一文檔內(nèi)出現(xiàn)次數(shù)越多的特征項(xiàng)比出現(xiàn)次數(shù)少的類別表征能力更強(qiáng)。所以只統(tǒng)計(jì)在類別中出現(xiàn)的文檔數(shù)是不夠的，還應(yīng)該考慮到其在文檔內(nèi)的不同詞頻數(shù)對(duì)類別表征能力的影響。

卡方統(tǒng)計(jì)方法并沒有把詞頻考慮進(jìn)來，這樣就造成低頻詞泛濫的情況。如果同一類的兩個(gè)特征項(xiàng)，它們的文檔頻率相差不大，則卡方值也就接近。但是，在類內(nèi)頻繁出現(xiàn)的詞語應(yīng)該比不頻繁出現(xiàn)的詞語更具有代表性。所以應(yīng)當(dāng)考慮特征項(xiàng)在類內(nèi)的頻度信息，使得高頻詞匯的類別表征能力強(qiáng)于低頻詞匯。為了得到專屬類別的特征項(xiàng)，需要排除一些在本類中大量出現(xiàn)，在其它類中也大量出現(xiàn)的詞匯。

Yang等人[14]提出了CMFS特征選擇算法，結(jié)合了文檔頻率和DIA關(guān)聯(lián)因子的優(yōu)點(diǎn)，從類內(nèi)和類間兩個(gè)角度綜合地評(píng)判一個(gè)特征的分類重要性程度。為解決CHI的低頻詞缺陷，借鑒了CMFS的思想，在詞匯的基礎(chǔ)上，改進(jìn)原有方法，提出CMFS＿CHI特征選擇方法，改進(jìn)方法的公式如下

(4)

其中，tf(tk，ci)表示特征tk在類別ci中的詞匯頻率，tf(t，ci)表示在類別ci中所有特征的頻率總和，tf(tk)表示特征tk在整個(gè)訓(xùn)練集中的詞匯頻率，|V|表示特征的初始數(shù)目，|C|表示類別的數(shù)目。

3.2 基于類內(nèi)信息熵的改進(jìn)

卡方統(tǒng)計(jì)量衡量的是特征項(xiàng)tk和類別ci之間的相關(guān)程度，特征項(xiàng)對(duì)于某類的卡方值越高，其與該類之間的相關(guān)性越大，攜帶的類別信息越多?？ǚ浇y(tǒng)計(jì)量在衡量類別特征詞的權(quán)重時(shí)，會(huì)引入干擾，這是該方法的固有缺陷。根據(jù)相關(guān)程度判別特征項(xiàng)與類別的所屬關(guān)系，雖然簡單高效，但是有將負(fù)相關(guān)的特征項(xiàng)誤判為正相關(guān)的可能性，若負(fù)相關(guān)的特征項(xiàng)參與表示本類別，會(huì)對(duì)最終的文本分類結(jié)果產(chǎn)生消極影響。

為了消除負(fù)相關(guān)特征的不利作用，已有學(xué)者作了一些研究。袁磊等人[15]從判斷條件出發(fā)，對(duì)特征項(xiàng)的相關(guān)性進(jìn)行了區(qū)分，完全排除負(fù)相關(guān)特征。當(dāng)AD-BC> 0時(shí)，認(rèn)為特征項(xiàng)對(duì)分類起到積極作用，屬于正相關(guān)特征；當(dāng)AD-BC≤ 0時(shí)，認(rèn)為特征項(xiàng)對(duì)分類起到消極作用，屬于負(fù)相關(guān)特征，但是，忽略了中頻詞攜帶的文本分類信息，造成分類精度下降。劉海峰等人[12]引入賦權(quán)因子，按不同權(quán)重從正相關(guān)特征、負(fù)相關(guān)特征中提取分類信息，改善CHI模型的特征選擇能力，但是，賦權(quán)因子又造成了不可避免的調(diào)節(jié)誤差。

為了更好地識(shí)別特征詞的相關(guān)性，引入了類內(nèi)信息熵[16]的概念。通過比較本類的信息熵和全類平均信息熵，有效度量特征詞的相關(guān)性，排除負(fù)相關(guān)特征詞的干擾，將具有類別表征能力的特征詞納入本類。類內(nèi)信息熵的定義如下

(5)

其中tf(tk，diq)為特征tk在ci類的第q個(gè)文本出現(xiàn)的頻數(shù)。分析此式可以看出，當(dāng)特征詞在類內(nèi)分布得越均勻，而不是集中在某幾個(gè)文檔，越有資格代表該類，相應(yīng)熵值也在反映這一變化，表現(xiàn)為熵值越大。

綜上所述，針對(duì)低頻詞缺陷和負(fù)相關(guān)問題，在考慮文檔頻率的基礎(chǔ)上，融合分布狀況，加入詞頻信息，然后為了獲取類別詞匯，降低噪聲因素干擾，改進(jìn)了判決條件，提出最終改進(jìn)的卡方統(tǒng)計(jì)方法(ICHI)，其公式如下

(6)

基于ICHI的特征選擇算法如下：

輸入：訓(xùn)練集文本D，類別集合C，特征選擇維度N。

輸出：特征集合Fi。

1)將訓(xùn)練集文本D進(jìn)行預(yù)處理；

2)由類別ci生成類別集合Fi；

4)針對(duì)類別集合Fi中的每個(gè)特征詞，使用式(5)計(jì)算類內(nèi)信息熵和平均信息熵；

6)將各類別集合放到一起，使用式(2)確定重復(fù)詞的卡方值，然后依據(jù)卡方值進(jìn)行降序排序；

7)輸出TopN個(gè)特征作為Fi，算法結(jié)束。

4 實(shí)驗(yàn)與分析

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

實(shí)驗(yàn)在Pycharm2019環(huán)境下進(jìn)行，采用的編程語言是python3.7，電腦系統(tǒng)是windows10，使用了SVM分類器進(jìn)行文本數(shù)據(jù)的分類實(shí)驗(yàn)。整體流程如圖1所示。語料集合選用的是復(fù)旦大學(xué)李榮陸教授整理的新聞?wù)Z料庫。選取其中的電腦、運(yùn)動(dòng)、歷史、環(huán)境、政治，共5個(gè)類別。從中各抽取500篇文檔，按照4：1的比例分類訓(xùn)練集和測試集。分詞工具采用的是中科院的NLPIR漢語分詞系統(tǒng)[17]。數(shù)據(jù)集的分布如表1所示。

表1 數(shù)據(jù)集分布

圖1 文本分類流程

4.2 評(píng)價(jià)指標(biāo)

衡量具體類別上的實(shí)驗(yàn)性能有查準(zhǔn)率P(precision)、查全率R(recall)、F1值等指標(biāo)，如式(7)～(9)所示。衡量全體類別上的實(shí)驗(yàn)性能有宏查準(zhǔn)率(macro＿P)、宏查全率(macro＿R)、宏F1值(macro＿F1)、準(zhǔn)確率(accuracy)等指標(biāo)，如式(10)～(12)所示。

(7)

(8)

(9)

(10)

(11)

(12)

其中TP為真正例，F(xiàn)P為假正例，F(xiàn)N為假反例，TN為真反例。

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

對(duì)數(shù)據(jù)集中的文本數(shù)據(jù)進(jìn)行預(yù)先處理，包括分詞、去除停用詞等。使用IG、CHI、WCHI[18]、ICHI三種特征選擇方法對(duì)詞匯組成的特征集合依據(jù)分類重要性進(jìn)行特征尋優(yōu)，并

按照特征的重要程度進(jìn)行排序，依次選取位置靠前的多組特征子集展開實(shí)驗(yàn)。

圖2和圖3對(duì) IG、CHI、WCHI、ICHI進(jìn)行了對(duì)比實(shí)驗(yàn)，從而驗(yàn)證ICHI的分類正確性和性能。從圖2可以看出，ICHI的整體準(zhǔn)確率要高于CHI、WCHI和IG。隨著特征維度的增加，三種特征選擇方法的準(zhǔn)確率開始提高，后期由于冗余信息的加入，增長緩慢，甚至下降。其中ICHI的準(zhǔn)確率在1300維時(shí)達(dá)到最高，為87%；WCHI的準(zhǔn)確率在1600維時(shí)達(dá)到最高，為84%；CHI的準(zhǔn)確率也在1600維時(shí)達(dá)到最高，為83%；IG的準(zhǔn)確率在1900維時(shí)達(dá)到最高，為83%。從圖3可以看出，ICHI在大部分維度上的表現(xiàn)好于其它對(duì)比算法，四種特征選擇方法的宏F1值在1300維時(shí)達(dá)到最高，ICHI與IG、CHI、WCHI相比，分別提高了2.91%、2.02%、1.57%。

圖2 四種特征選擇方法的準(zhǔn)確率對(duì)比

圖3 四種特征選擇方法的宏F1值對(duì)比

ICHI在準(zhǔn)確率和宏F1值方面要比IG和CHI表現(xiàn)好，原因在于IG和CHI忽略了詞頻信息，而ICHI借助CMFS引入了詞頻因子，該詞頻因子從類內(nèi)、類間兩個(gè)角度考量了一個(gè)特征對(duì)分類的重要性；對(duì)于IG會(huì)將特征詞不出現(xiàn)的情況作為主導(dǎo)，CHI無法有效識(shí)別負(fù)相關(guān)特征的問題，ICHI借助類內(nèi)信息熵來識(shí)別有效特征，去除噪聲特征的干擾。WCHI在CHI的基礎(chǔ)上用tfidf加權(quán)，所以效果要好于CHI，但是，沒有考慮詞頻在類別中的分布，也沒有對(duì)負(fù)相關(guān)特征進(jìn)行處理，所以，表現(xiàn)不如ICHI。

為了進(jìn)一步驗(yàn)證ICHI的效果，進(jìn)行了具體類別上的實(shí)驗(yàn)，選取的特征維度是1300維。實(shí)驗(yàn)結(jié)果如圖4～6所示。

圖4 各類別的查準(zhǔn)率對(duì)比

圖5 各類別的查全率對(duì)比

圖6 各類別的F1值對(duì)比

分析圖4～6可知，改進(jìn)的CHI在大多數(shù)類別上明顯地比傳統(tǒng)的CHI、WCHI和IG表現(xiàn)要好。其中在精確率上，ICHI比IG在政治類上提升最明顯，為2.61%；ICHI比CHI、WCHI在環(huán)境類上提升最明顯，分別為1.57%和0.92%。在召回率上，ICHI比IG、CHI和WCHI在電腦類上提升最明顯，分別為4.00%、2.41%和3.54%。在F1值上，ICHI比IG和WCHI在電腦類上提升最明顯，分別為3.20%、2.94%；ICHI比CHI在環(huán)境類上提升最明顯，為1.66%?？梢缘贸觯琁CHI與IG、CHI、WCHI相比，特征選擇的效果要好一些。

分析原因在于改進(jìn)算法提高了模型的穩(wěn)定性，一方面從電腦類、環(huán)境類、政治類中提取了高關(guān)聯(lián)度特征詞，另一方面兼顧了運(yùn)動(dòng)類、歷史類特征詞數(shù)量較少的情況，補(bǔ)充了更具代表性的特征詞。

5 結(jié)語

傳統(tǒng)的CHI特征選擇方法考慮了特征詞在語料集的文本頻率，忽略了特征詞在具體文本的詞匯頻率，造成了高頻詞和低頻詞的同等看待問題。由于負(fù)相關(guān)缺陷，導(dǎo)致含有少量分類信息的特征進(jìn)入類別代表特征中，對(duì)分類造成了一定干擾。針對(duì)以上問題，本文提出了改進(jìn)的CHI，從類內(nèi)、類間兩個(gè)角度考慮詞頻信息的重要性，而且通過信息增益理論對(duì)負(fù)相關(guān)特征進(jìn)行了剔除。結(jié)合實(shí)驗(yàn)結(jié)果分析，ICHI比傳統(tǒng)方法的特征選擇效果要好。下一步的工作，將在特征詞的語義能力上進(jìn)行探索，借助神經(jīng)網(wǎng)絡(luò)技術(shù)識(shí)別更具代表性的特征進(jìn)入特征集合或生成豐富含義的特征輔助特征的表達(dá)。