基于正余弦算法的文本特征選擇*

文 武，萬玉輝，文志云

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

1 引言

隨著信息時(shí)代的來臨，越來越多的民眾通過互聯(lián)網(wǎng)獲取信息，這些網(wǎng)絡(luò)資源大多以文本的形式存在。因此，文本自動(dòng)分類技術(shù)作為處理大數(shù)據(jù)的關(guān)鍵技術(shù)，發(fā)揮著越來越重要的作用。隨著以文本形式存在的網(wǎng)絡(luò)數(shù)據(jù)量的增加，龐大的文本特征空間嚴(yán)重影響了數(shù)據(jù)分析性能。過多的噪聲和冗余特征，不僅降低了訓(xùn)練模型的效率，更影響了分類準(zhǔn)確性。因此，從特征空間中選出最能表達(dá)文本屬性的特征，對(duì)提升文本分類性能至關(guān)重要。

在文本特征選擇上，互信息MI(Mutual Information)[1]、卡方統(tǒng)計(jì)CHI(CHI-square statistics)[2]和信息增益IG(Information Gain)[3]等經(jīng)典過濾式特征選擇算法能夠篩選出類別相關(guān)性較強(qiáng)的特征，但忽略了詞與詞之間的冗余性。為了獲取精選特征集合，許多特征選擇算法被提出。文獻(xiàn)[4]結(jié)合皮爾遜相關(guān)系數(shù)和互信息函數(shù)，選出了類別相關(guān)性高且冗余度低的特征。文獻(xiàn)[5]先通過多種封裝式方法進(jìn)行特征初選，再采用改進(jìn)后的遺傳算法來減小特征的數(shù)量，去除冗余的同時(shí)提高了分類精度。朱文峰等[6]通過IG提取與類別相關(guān)性較強(qiáng)的特征，在最大相關(guān)最小冗余mRMR(Max-Relevance and Min-Redundancy)中引入類差分度來更新特征與類別權(quán)重，去除冗余，提升了分類準(zhǔn)確率。此外，隨著群智能算法在特征選擇上的應(yīng)用，文獻(xiàn)[7]結(jié)合粒子群算法和MI，采用準(zhǔn)確率作為適應(yīng)度函數(shù)，提高了分類精度。文獻(xiàn)[8]首先從UMLS(Unified Medical Language System)中提取關(guān)鍵特征，再通過粒子群對(duì)提取的特征進(jìn)一步優(yōu)化組合，提高了對(duì)醫(yī)學(xué)類文檔的分類性能。文獻(xiàn)[9]通過正余弦算法SCA(Sine Cosine Algorithm)在18個(gè)數(shù)據(jù)集上進(jìn)行特征選擇，準(zhǔn)確率相比粒子群算法和遺傳算法均得到了一定的提升。溫廷新等[10]通過CHI進(jìn)行特征初選，在果蠅優(yōu)化算法中引入交叉算子和輪盤賭方法等來進(jìn)行二次特征選擇，保證了種群多樣性，同單一的CHI方法相比用較少的特征數(shù)取得了較優(yōu)的分類效果。文獻(xiàn)[11]先通過CHI進(jìn)行預(yù)選，再采用水波優(yōu)化算法進(jìn)行二次特征尋優(yōu)，同多種傳統(tǒng)算法相比，在5個(gè)特征維度下均提高了分類性能。

本文結(jié)合已有的研究，提出了一種二階段尋優(yōu)算法。該算法采用信息增益進(jìn)行特征預(yù)選，再結(jié)合擁有全局和局部搜索能力的正余弦優(yōu)化算法進(jìn)行二次精選。

2 基本算法

2.1 信息增益

信息增益IG依據(jù)某特征s為整個(gè)分類系統(tǒng)所能提供的信息量多少來衡量該特征的重要程度，從而決定對(duì)該特征的取舍，是一種基于信息熵的評(píng)估算法。熵可以視為描述一個(gè)隨機(jī)變量的不確定性的數(shù)量，熵越大，不確定性越高，那么，正確估計(jì)其值的可能性就越小。IG是在加入此特征前后文本的熵的差值，計(jì)算方法如式(1)所示：

(1)

2.2 正余弦算法

2016年，澳大利亞學(xué)者M(jìn)irjalili[12]通過總結(jié)群智能算法，提出了一種新的智能算法——正余弦算法SCA。該算法主要通過正弦和余弦函數(shù)來實(shí)現(xiàn)對(duì)優(yōu)化問題的求解，具有原理簡單、參數(shù)少和搜索機(jī)制獨(dú)特等優(yōu)點(diǎn)，獲得了廣泛的研究與應(yīng)用。

正余弦算法在求解高維問題時(shí)，先初始化種群規(guī)模為m，搜索空間為n維，xi=(xi1,xi2,xi3,…,xin)表示第i個(gè)個(gè)體的位置，i=1,2,…,m。第i個(gè)個(gè)體按式(2)進(jìn)行迭代更新:

(2)

(3)

其中，a為常數(shù)2，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)。在正余弦算法中，控制參數(shù)r1是一個(gè)隨著迭代次數(shù)的增加，從2慢慢減小到0的系數(shù)，用于控制局部開發(fā)與全局探索。參數(shù)r2決定了當(dāng)前解向最優(yōu)解遠(yuǎn)離或者接近所能達(dá)到的距離極值。r3為隨機(jī)權(quán)重，是指最優(yōu)解對(duì)當(dāng)前解的影響程度，|r3|>1表示最優(yōu)解對(duì)當(dāng)前解有較強(qiáng)影響力，|r3|<1表示最優(yōu)解對(duì)當(dāng)前解影響力較弱。r4描述了隨機(jī)選擇正弦還是余弦進(jìn)行位置更新，擬消除移動(dòng)步長和方向存在的聯(lián)系。當(dāng)|r1·sin(r2)|>1或|r1·cos(r2)|>1時(shí)，新個(gè)體位置位于候選解和最優(yōu)解之外，處于全局探索階段；當(dāng)|r1·sin(r2)|<1或|r1·cos(r2)|<1時(shí)，新個(gè)體位置位于候選解和最優(yōu)解之間，處于局部開發(fā)階段。算法通過參數(shù)的隨機(jī)性，在正弦函數(shù)和余弦函數(shù)之間不斷進(jìn)行全局探索和局部開發(fā)來迭代更新，直至找到最佳位置。

3 基于SCA的特征選擇

IG進(jìn)行特征初選后會(huì)存在特征冗余問題，為進(jìn)一步優(yōu)化特征質(zhì)量，本文對(duì)原始SCA進(jìn)行改進(jìn)，對(duì)特征進(jìn)行二次篩選。本文在原始SCA算法的基礎(chǔ)上，分別添加了自適應(yīng)權(quán)重因子、新的適應(yīng)度函數(shù)和位置更新機(jī)制來進(jìn)一步優(yōu)化特征子集。混合特征選擇算法在本文中簡稱為IGISCA(Information Gain and Improved Sine Cosine Algorithm)。

3.1 個(gè)體編碼

本文采用二進(jìn)制編碼的方式來表示特征的選擇與否，每一個(gè)個(gè)體都是一個(gè)可能的最優(yōu)解。首先，需要對(duì)個(gè)體位置進(jìn)行離散化處理，假設(shè)有m個(gè)個(gè)體，每個(gè)個(gè)體的位置為xi=(xi1,xi2,xi3,…,xin)，由n個(gè)[0,1]的隨機(jī)數(shù)組成，n表示特征的維數(shù)。這樣，個(gè)體的位置由一組[0,1]的小數(shù)組成。根據(jù)一定的轉(zhuǎn)化方法，將個(gè)體位置xi轉(zhuǎn)化為長度為n的二進(jìn)制位置x′i=(x′i1,x′i2,x′i3,…,x′in)，其中x′ij∈{0,1},j∈[1,n]。x′ij代表一個(gè)特征，值為1表示該特征被選擇，值為0則表示該特征未被選擇。每一個(gè)二進(jìn)制位置都表示一個(gè)特征子集。個(gè)體的二進(jìn)制位置x′ij可由式(4)得到:

(4)

其中，對(duì)于二進(jìn)制編碼，假設(shè)數(shù)據(jù)集中有6個(gè)特征{a1,a2,a3,a4,a5,a6}，隨機(jī)初始化個(gè)體的位置，根據(jù)式(4)假如有個(gè)體的二進(jìn)制位置為{1，0，1，1，1，0}，表示特征a1,a3,a4,a5被選取。特征a2,a6未被選取。m個(gè)個(gè)體各自遍歷一次后可得到m個(gè)特征子集，根據(jù)適應(yīng)度函數(shù)從中選擇出最優(yōu)的特征子集。

3.2 自適應(yīng)權(quán)重

慣性權(quán)重[13]是群智能優(yōu)化算法中重要的一項(xiàng)權(quán)重，描述的是上一代候選解集對(duì)當(dāng)代候選解的影響程度。從式(2)可以看出，在傳統(tǒng)的SCA中，候選解分量具有固定慣性權(quán)重1，固定慣性權(quán)重有可能會(huì)影響算法探索和開發(fā)的能力，進(jìn)而影響整體的求解效果。為了避免這種情況，本文提出隨著迭代次數(shù)的增加動(dòng)態(tài)更新權(quán)重的公式，如式(5)所示：

(5)

其中，wmax為最大權(quán)重，wmin為最小權(quán)重，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)。這樣可以保證在算法初期，w的值相對(duì)較大，具有較大的搜索范圍，而在后期，w的值相對(duì)較小，能夠進(jìn)行良好的局部搜索，快速找到全局最優(yōu)。由此得到第i個(gè)個(gè)體的迭代更新如式(6)所示：

(6)

3.3 適應(yīng)度函數(shù)及更新機(jī)制

適應(yīng)度函數(shù)對(duì)于特征選擇有重要影響，特征選擇的目的是獲取最優(yōu)的特征子集，使分類效果得到提高。通常將分類準(zhǔn)確率作為評(píng)價(jià)特征子集的一個(gè)重要因素；同時(shí)，用越少的特征得到更好的分類效果，是理想的特征子集。結(jié)合以上2種因素，本文采用的適應(yīng)度函數(shù)如式(7)所示：

(7)

其中，p是分類準(zhǔn)確率，nt是被選中個(gè)體的特征長度，Nt是特征的長度。α，β是2個(gè)參數(shù)，β=1-α，α是趨近于1的常數(shù)。適應(yīng)度函數(shù)值越小表示結(jié)果越好。

如果只考慮適應(yīng)度函數(shù)作為更新評(píng)判標(biāo)準(zhǔn)，當(dāng)新一代個(gè)體適應(yīng)度函數(shù)值和上一代最佳相等時(shí)，此時(shí)保留上一代最優(yōu)個(gè)體，但有可能新一代個(gè)體的特征個(gè)數(shù)更少。因此，本文借鑒已有研究[14,15]，提出了2種條件下的新的位置更新機(jī)制：

(1)如果新一代個(gè)體的適應(yīng)度函數(shù)值優(yōu)于之前全局最優(yōu)個(gè)體，則更新最優(yōu)個(gè)體。

(2)如果新一代個(gè)體的適應(yīng)度函數(shù)值等于之前全局最優(yōu)個(gè)體，并且新一代個(gè)體選擇的特征個(gè)數(shù)較少，則更新最優(yōu)個(gè)體。

4 IGISCA特征選擇流程

IGISCA算法通過二進(jìn)制個(gè)體的位置來表達(dá)所選擇的特征子集，再通過適應(yīng)度函數(shù)來評(píng)價(jià)該位置的優(yōu)劣。圖1描述了二階段特征選擇的主要流程，在信息增益初選特征集合的基礎(chǔ)上通過正余弦算法尋優(yōu)，具體算法流程如算法1所示。

Figure 1 Flow chart of feature selection of IGISCA圖1 IGISCA的特征選擇流程

算法1IGISCA

輸入：預(yù)處理后的特征集合Feature，種群大小m，最大迭代次數(shù)tmax，最大權(quán)重wmax，最小權(quán)重wmin。

輸出：終選特征IGISCAFeature。

Step1對(duì)特征集合Feature進(jìn)行IG初選，選取結(jié)果存入IGFeature中。

Step2初始化種群x，維度n，每個(gè)個(gè)體位置xi=(xi1,xi2,…,xin)，i=1,2,…,m。

Step3計(jì)算種群個(gè)體適應(yīng)度值，記錄當(dāng)前最佳個(gè)體。

Step4更新參數(shù)r1,r2,r3,r4。

Step5若r4<0.5，采用正弦函數(shù)更新，否則采用余弦函數(shù)更新，迭代次數(shù)加1。

Step6計(jì)算新的個(gè)體適應(yīng)度值，根據(jù)更新機(jī)制選出最佳個(gè)體位置。

Step7若t

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

本次實(shí)驗(yàn)操作系統(tǒng)為Windows 10，借用Anoconda庫，采用Python語言編寫。為驗(yàn)證本文算法的有效性，實(shí)驗(yàn)采用MI、CHI、IG、IGSCA(Information Gain and Sine Cosine Algorithm)和IGISCA對(duì)文本集合進(jìn)行特征選擇，在KNN(K-Nearest Neighbor)和貝葉斯分類器下進(jìn)行實(shí)驗(yàn)。其中，IGSCA算法是指通過文獻(xiàn)[12]中提出的SCA算法在IG基礎(chǔ)上進(jìn)行二次特征選擇，適應(yīng)度函數(shù)采用分類準(zhǔn)確率。首先使用jieba分詞對(duì)數(shù)據(jù)文檔進(jìn)行分詞，隨后使用哈爾濱工業(yè)大學(xué)的停用詞表對(duì)數(shù)據(jù)去停用詞，通過向量空間模型進(jìn)行文本表示，特征權(quán)重由TF-IDF(Term Frequency-Inverse Document Frequency)計(jì)算。評(píng)價(jià)指標(biāo)為分類準(zhǔn)確率，如式(8)所示:

(8)

5.1 實(shí)驗(yàn)數(shù)據(jù)與參數(shù)

實(shí)驗(yàn)數(shù)據(jù)選取了復(fù)旦大學(xué)數(shù)據(jù)庫中的5 442篇文檔，包括能源、農(nóng)業(yè)、歷史、體育、政治和法律6個(gè)類別，如表1所示。

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

IGSCA算法和IGISCA算法中的種群大小均設(shè)置為m=40，最大迭代次數(shù)tmax=80。IGISCA算法中最大權(quán)重wmax=0.9，最小權(quán)重wmin=0.3，適應(yīng)度函數(shù)權(quán)重α=0.9。

5.2 結(jié)果與分析

為保證所有算法對(duì)比的有效性，用5種算法在100～1 900的10個(gè)維度下進(jìn)行實(shí)驗(yàn)，在相同維度下(IGSCA和IGISCA中為IG初選維度)進(jìn)行分類準(zhǔn)確率對(duì)比，分別采用KNN和貝葉斯分類器進(jìn)行分類，分類器參數(shù)保持一致。此外，為更進(jìn)一步分析IGISCA算法的分類性能，統(tǒng)計(jì)出了各個(gè)類別下的分類準(zhǔn)確率和二次選擇后的特征個(gè)數(shù)。

(1)特征維度實(shí)驗(yàn)。

表2表明，在特征維度為300和700～1 900時(shí)，IGISCA的分類準(zhǔn)確率比其它特征選擇算法的高。維度為100時(shí)，IGSCA的分類準(zhǔn)確率最高。維度為500時(shí)，CHI的分類準(zhǔn)確率最高。整體上來看，在大部分維度下IGISCA相對(duì)于IGSCA準(zhǔn)確率提高了0.7%～2.5%，IGISCA相對(duì)于IG分類準(zhǔn)確率提高了約1.1%～4.2%，在大部分維度下IGISCA相對(duì)于CHI準(zhǔn)確率提高了0.8%～4.4%，在所有維度下IGISCA相對(duì)于MI準(zhǔn)確率提高了2.4%～7.1%。簡言之，二階段特征選擇算法IGISCA在KNN分類器下能夠在絕大部分特征維度下提高分類準(zhǔn)確率。

Table 2 Feature dimension experiment under KNN表2 KNN下的特征維度實(shí)驗(yàn)

從表3看出，在500～1 900特征維度下，IGISCA的分類準(zhǔn)確率優(yōu)于其它特征選擇算法的。維度為100時(shí)，CHI的分類準(zhǔn)確率最高。維度為300時(shí),IGSCA的分類準(zhǔn)確率最高。整體上來說，在大部分維度下IGISCA相對(duì)于IGSCA準(zhǔn)確率提高了0.5%～2.7%，在所有維度下IGISCA相對(duì)于IG準(zhǔn)確率提高了0.7%～3.2%，在大部分維度下IGISCA相對(duì)于CHI準(zhǔn)確率提高了1.5%～3.9%，在所有維度下IGISCA相對(duì)于MI準(zhǔn)確率提高了2.0%～6.8%。說明了二階段特征選擇算法IGISCA在貝葉斯分類器下能夠獲取較優(yōu)特征集合。

(2)類別實(shí)驗(yàn)。

由表2和表3知，在KNN和貝葉斯分類器下，IGISCA分別在IG初選為1 500維和1 300維時(shí)達(dá)到最高分類性能。為進(jìn)一步驗(yàn)證IGISCA的可行性，單一過濾式特征選擇算法在KNN分類器下選取1 500維，在貝葉斯下選取1 300維,IG初選后的特征再分別通過改進(jìn)前后的SCA算法分別進(jìn)行二階段特征提取，計(jì)算出對(duì)各個(gè)類別的分類準(zhǔn)確率。

Table 3 Feature dimension experiment under NB classifier表3 貝葉斯分類器下的特征維度實(shí)驗(yàn)

由圖2可知，IGISCA和IGSCA 2種混合特征選擇算法的分類準(zhǔn)確率相對(duì)于其它單一特征選擇算法，在所有類別文本上均有提升，表明混合特征選擇算法能夠在去除冗余的同時(shí)實(shí)現(xiàn)分類性能的一定提升。由圖3可知，貝葉斯分類器下，盡管在法律類別文本上，IGSCA算法的準(zhǔn)確率低于單一特征選擇算法CHI的，但在其它類別文本上，混合特征選擇算法的分類性能均高于過濾式特征選擇算法的。此外，IGISCA算法在各個(gè)類別上的分類性能相對(duì)于對(duì)比算法均有不同幅度的提升，表明了本文算法的有效性。

Figure 2 Category experiment under KNN classifier圖2 KNN分類器下的類別實(shí)驗(yàn)

Figure 3 Category experiment under NB classifier圖3 貝葉斯分類器下的類別實(shí)驗(yàn)

(3)特征個(gè)數(shù)。

為驗(yàn)證本文提出的以特征個(gè)數(shù)和分類準(zhǔn)確率加權(quán)的適應(yīng)度函數(shù)和更新機(jī)制的有效性，更進(jìn)一步說明IGISCA算法能夠去除冗余。IG初選特征后通過SCA和ISCA分別進(jìn)行尋優(yōu)，統(tǒng)計(jì)出了2種分類器下各算法在不同初選特征維度下尋優(yōu)后最終選出的特征個(gè)數(shù)，如表4和表5所示。其中，IGSCA采用分類準(zhǔn)確率作為適應(yīng)度函數(shù)。

Table 4 Number of features selected by each algorithm under KNN classifier表4 KNN分類器下各算法選擇的特征個(gè)數(shù)

Table 5 Number of features selected by each algorithm under NB classifier表5 貝葉斯分類器下各算法選擇的特征個(gè)數(shù)

通過表4和表5可以看到，在2種分類器下，二階段特征選擇算法相比于傳統(tǒng)單一特征選擇算法，在各個(gè)維度下實(shí)現(xiàn)了特征數(shù)量的大幅度約減，說明了混合特征選擇算法能夠在單一特征選擇算法的基礎(chǔ)上剔除冗余特征及類別相關(guān)性不強(qiáng)的特征。此外，同原始IGSCA算法相比，IGISCA算法篩選出的特征個(gè)數(shù)在絕大部分維度下進(jìn)一步減少了，驗(yàn)證了改進(jìn)SCA算法的有效性。

6 結(jié)束語

本文借鑒了過濾式特征選擇算法和群智能算法相結(jié)合的模型進(jìn)行文本特征選擇，根據(jù)正余弦優(yōu)化算法較強(qiáng)的尋優(yōu)能力，提出了結(jié)合信息增益和正余弦優(yōu)化算法的新的特征選擇算法。該算法在信息增益的基礎(chǔ)上，通過正余弦優(yōu)化算法的全局和局部搜索尋找更能代表文本屬性的特征子集。為更好地平衡早期階段的全局搜索和后期階段的局部尋優(yōu)，在SCA算法中加入自適應(yīng)慣性權(quán)重，引入了新的適應(yīng)度函數(shù)和更新機(jī)制，來精確評(píng)價(jià)特征子集，實(shí)現(xiàn)了特征數(shù)量的消減。在KNN和貝葉斯分類器下進(jìn)行實(shí)驗(yàn)驗(yàn)證，與MI、CHI、IG和IGSCA算法對(duì)比，IGISCA能夠在絕大多數(shù)維度下得到更高的分類準(zhǔn)確率，并能實(shí)現(xiàn)接近一半特征數(shù)量的消減，證明了本文算法的有效性。未來將對(duì)IGISCA算法繼續(xù)進(jìn)行優(yōu)化，并嘗試將正余弦算法與其它文本特征選擇算法相結(jié)合，進(jìn)一步檢驗(yàn)算法的穩(wěn)定性。