類依賴特征選擇算法在文本分類中的優(yōu)化研究?

劉 云 肖 雪 黃榮乘

（昆明理工大學(xué)信息工程與自動化學(xué)院 昆明 650500）

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，大量電子文檔出現(xiàn)日常生活中，文本分類技術(shù)［1～3］越來越重要。在文本分類過程中，文檔的每個詞都被看作一個特征。一個文檔常具有數(shù)以萬計(jì)個特征，由于這些特征大多數(shù)都是不相關(guān)或多余的，因此在分類過程中，這不僅增加了分類的計(jì)算復(fù)雜度，而且大量特征可能會對分類準(zhǔn)確性產(chǎn)生負(fù)面影響。為了提高分類性能，有必要進(jìn)行特征選擇［4～5］，通常利用卡方統(tǒng)計(jì)（CHI）［6～7］、信息增益（IG）［8～9］等特征評估函數(shù)來選取出重要特征以保留具有最大歧義的特征。

Baykan等提出了基于信息增益和粒子群優(yōu)化的特征選擇算法［10］，該算法通過選擇文檔中特征的詞根，創(chuàng)建特征向量空間，刪除了使用頻率較低的特征，然后基于粒子群優(yōu)化算法對特征進(jìn)行選擇后，使用信息增益特征的重要性的降序排列。El?berrichi等提出了基于遺傳算法的特征選擇方法［11］，該算法使用遺傳算法選擇具有較高適應(yīng)度值的特征，找到具有最小維數(shù)的特征子集，使的分類性能最大化。

本文提出了一種類別依賴特征選擇算法（CD），首先通過給定的訓(xùn)練集，基于卡方統(tǒng)計(jì)量計(jì)算出每個特征的特征評估值（FEF），根據(jù)所有特征的FEF值計(jì)算出每個訓(xùn)練文檔的關(guān)聯(lián)值（DR），然后由這些已知類別的訓(xùn)練文檔的DR值，計(jì)算出這個類別的閾值CT，并挑選出DR值大于其類別閾值CT的所有同類訓(xùn)練文檔，最后在同一類別下的訓(xùn)練文檔中根據(jù)特征評估函數(shù)，每個訓(xùn)練文檔都計(jì)算出一個具有最大FEF值的特征，挑選出每個訓(xùn)練文檔中具有最大FEF值的特征構(gòu)成了該類的特征向量FS。

2 相關(guān)工作

在樸素貝葉斯分類器［12～14］中，針對一個N分類問題，根據(jù)最大后驗(yàn)概率規(guī)則，將文本x歸為后驗(yàn)概率最大的類別：

p(x|ci)是特征的類概率密度函數(shù)，p(ci)是類的先驗(yàn)概率。其中為了避免零概率問題，使用“拉普拉斯平滑”技術(shù)［15～17］進(jìn)行處理，并使用極大似然估計(jì)［18～20］方法，對c類下每個特征詞的概率p?ic進(jìn)行估計(jì)，估計(jì)值為

lic是c類的文檔中第i個特征詞出現(xiàn)的次數(shù)，lc是c類文檔中特征詞的總數(shù)，λ1=1和λ2=M是恒定的平滑參數(shù)。

由式（1）得，特征的類概率密度函數(shù)直接影響到了貝葉斯分類器的分類性能，所以需要找到最優(yōu)的特征子集使得分類器的性能最大化。

為了找到最優(yōu)特征子集，本文提出了一種類別依賴特征選擇算法。由圖1知，其中訓(xùn)練集Dtr包含di∈NV個文檔，其中V是詞匯量。首先通過給定的訓(xùn)練集，基于卡方統(tǒng)計(jì)量計(jì)算出每個特征的特征評估值FEF，根據(jù)所有特征的FEF值計(jì)算出每個訓(xùn)練文檔的文檔關(guān)聯(lián)值DR，然后由這些已知類別的訓(xùn)練文檔的DR值，計(jì)算出這個類別的閾值CT，將DR值大于其類別閾值CT的訓(xùn)練文檔挑選出來，并找出其中具有最大EEF值的特征存入FS向量中，將所有訓(xùn)練文檔遍歷一遍，最終得到了該類的特征向量FS。

圖1 類依賴特征選擇算法

其中，由于某些文檔包含了大量低FEF值的特征使得文檔的DR值超過了閾值將其保留，卻丟棄了含有少量高FEF值特征的文檔，導(dǎo)致具有高辨別力特征的文檔被忽略。為了避免該現(xiàn)象，本文將文檔的DR值由其特征的FEF值的平均值所計(jì)算出，類別的CT值由該類別的所有文檔的DR平均值計(jì)算出。

因此，本文旨在通過解決這兩個問題來提高分類準(zhǔn)確度：閾值定義和DR值的計(jì)算。所提出的算法基于其文檔的重要性為每個類別定義不同的閾值，并將DR值大于其類別CT值的文檔用于特征選擇。這樣就能找到每個類別最具有歧義的特征向量，使得分類器分類性能得以提升。

3 類依賴特征選擇算法

3.1 特征向量的構(gòu)建

根據(jù)訓(xùn)練集，基于卡方統(tǒng)計(jì)量計(jì)算出每個特征的FEF值，并將FEF值存儲在S向量中：

其中P(ω|cj)表示類別cj中出現(xiàn)特征ω的文本的概率，P(ωˉ|cˉj)表示除了類別cj的其他類別中沒有出現(xiàn)特征ω的文本的概率，P(ω|cˉj)表示除了類別cj的其他類別中出現(xiàn)特征ω的文本的概率，P(ωˉ|cj)表示類別cj中沒有出現(xiàn)特征ω的文本的概率，p(cj)表示類別cj的文本出現(xiàn)的概率，p(ω)表示有特征詞ω的文本出現(xiàn)的概率。然后，計(jì)算出每個訓(xùn)練文檔的DR值：

其中di是文檔，V是詞匯量，sh是第h個特征的FEF值，ωh，i是第i個文檔的第h個特征。如果在第i個文檔中有第h個特征，則νalued(·)的函數(shù)將返回1，否則返回0。下一步是計(jì)算CT向量，該向量存儲了每個類別的閾值。CT的計(jì)算公式為

其中cj是類別，D是訓(xùn)練集中的文檔數(shù)，di是第i個文檔。如果文檔di屬于類別cj，則函數(shù)belοngs(·)返回1，否則返回0。

通過給定的訓(xùn)練集，基于卡方統(tǒng)計(jì)量計(jì)算出每個特征的特征評估值FEF，根據(jù)所有特征的FEF值計(jì)算出每個訓(xùn)練文檔的DR值，由這些已知類別的訓(xùn)練文檔的DR值，計(jì)算出這個類別的閾值CT，挑選出DR值大于其類別閾值CT的所有訓(xùn)練文檔，并提取出該文檔具有最大EEF值的特征。在這過程中，如果每當(dāng)出現(xiàn)一個新特征，則將新的特征存儲在FS向量中并按降序排列。然后，繼續(xù)下一個文檔，重復(fù)該過程，最后得到了這個類最終的特征向量FS。

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

在對文本進(jìn)行分類時，為評估系統(tǒng)的性能，常使用準(zhǔn)確率，精確率和召回率指標(biāo)，其定義如下：

TP表示判定為正確時屬于此類的文本數(shù)，TN表示判定為正確時不屬于此類的文本數(shù)，F(xiàn)P表示判斷為錯誤時不屬于此類的文本數(shù)，F(xiàn)N表示判定為錯誤時不屬于此類的文本數(shù)。為了更全面地進(jìn)行性能分析，使用精確率和召回率得到了F1指標(biāo)［21～22］，定義如下：

4 仿真分析

本文采用了REUTERS數(shù)據(jù)集［23］，REUTERS數(shù)據(jù)集包含了各類新聞和金融數(shù)據(jù)的多媒體新聞。其中REUTERS中的ModApte數(shù)據(jù)集有65個類由12902個文本構(gòu)成，隨機(jī)選擇了9603個文本作為訓(xùn)練集，并把3299個文本作為測試集，其中抽取了數(shù)據(jù)集REUTERS-10中的前10個類來進(jìn)行判定。

基于樸素貝葉斯分類器，本文將CD算法與IG-PSO和GA兩種算法進(jìn)行對比。用分類準(zhǔn)確率和F1指標(biāo)來對三種特征選擇算法的性能進(jìn)行評估，選擇的特征詞數(shù)量范圍從10個到1000個。

圖2和圖3分別代表了CD算法和IG-PSO、GA算法進(jìn)行實(shí)驗(yàn)時其準(zhǔn)確率和F1指標(biāo)的曲線圖。由圖2看出當(dāng)特征詞數(shù)量為50時，本文提出的CD算法的準(zhǔn)確率接近最高值93%，大幅領(lǐng)先GA算法，且IG-PSO算法當(dāng)特征詞數(shù)量為100時準(zhǔn)確率才接近CD算法。由圖3看出當(dāng)特征詞數(shù)量為50時，提出的CD算法的F1指標(biāo)接近最大值為89.14%，在特征詞個數(shù)較少時F1指標(biāo)大幅領(lǐng)先于IG-PSO算法和GA算法。

圖2 三種不同算法的準(zhǔn)確率對比圖

圖3 三種不同算法的F1指標(biāo)對比圖

從上述數(shù)據(jù)得知，CD特征選擇算法與其他兩種特征選擇算法相比，CD特征選擇算法在特征詞數(shù)量相對少的時候，就可以獲得較高的準(zhǔn)確率和F1指標(biāo)，其他對比算法需要更多的特征詞數(shù)量參考，才能達(dá)到相近的準(zhǔn)確率和F1指標(biāo)。

5 結(jié)語

在對文本分類時，特征選擇會影響分類的精度，所以本文提出了一種類依賴特征選擇算法。通過給定的訓(xùn)練集，計(jì)算出每個特征的FEF值，對特征的FEF值求平均后得到文檔的關(guān)聯(lián)值DR，又通過對訓(xùn)練文檔的DR值求平均后得到類別的閾值CT，挑選出DR值大于其類別閾值CT的訓(xùn)練文檔進(jìn)行特征選擇得到了每個類的特征向量FS。仿真結(jié)果表明，對比IG-PSO和GA兩種特征選擇算法，CD特征選擇算法根據(jù)不同類別的訓(xùn)練文檔得到特有的特征子集，并在特征選擇時通過對EEF和DR取平均值，使得含有少量高FEF值特征的文檔得以保留。通過上述優(yōu)化，使用本文提出的CD特征選擇算法能明顯提高分類的性能，特別是只需要選取少量特征詞就能獲得同其他算法一樣的分類精度。