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

劉 云 肖 雪 黃榮乘

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

1 引言

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

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

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

2 相關(guān)工作

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

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

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

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

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

圖1 類依賴特征選擇算法

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

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

3 類依賴特征選擇算法

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

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

5 結(jié)語(yǔ)

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