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

2022-08-19 09:59:10萬玉輝文志云

計算機工程與科學 2022年8期

文武，萬玉輝，文志云

(1.重慶郵電大學通信與信息工程學院，重慶 400065； 2.重慶郵電大學通信新技術應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

1 引言

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

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

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

2 基本算法

2.1 信息增益

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

(1)

2.2 正余弦算法

2016年，澳大利亞學者Mirjalili[12]通過總結群智能算法，提出了一種新的智能算法——正余弦算法SCA。該算法主要通過正弦和余弦函數來實現對優化問題的求解，具有原理簡單、參數少和搜索機制獨特等優點，獲得了廣泛的研究與應用。

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

(2)

(3)

3 基于SCA的特征選擇

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

3.1 個體編碼

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

(4)

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

3.2 自適應權重

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

(5)

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

(6)

3.3 適應度函數及更新機制

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

(7)

其中，p是分類準確率，nt是被選中個體的特征長度，Nt是特征的長度。α，β是2個參數，β=1-α，α是趨近于1的常數。適應度函數值越小表示結果越好。

如果只考慮適應度函數作為更新評判標準，當新一代個體適應度函數值和上一代最佳相等時，此時保留上一代最優個體，但有可能新一代個體的特征個數更少。因此，本文借鑒已有研究[14,15]，提出了2種條件下的新的位置更新機制：

(1)如果新一代個體的適應度函數值優于之前全局最優個體，則更新最優個體。

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

4 IGISCA特征選擇流程

IGISCA算法通過二進制個體的位置來表達所選擇的特征子集，再通過適應度函數來評價該位置的優劣。圖1描述了二階段特征選擇的主要流程，在信息增益初選特征集合的基礎上通過正余弦算法尋優，具體算法流程如算法1所示。

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

算法1IGISCA

輸入：預處理后的特征集合Feature，種群大小m，最大迭代次數tmax，最大權重wmax，最小權重wmin。

輸出：終選特征IGISCAFeature。

Step1對特征集合Feature進行IG初選，選取結果存入IGFeature中。

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

Step3計算種群個體適應度值，記錄當前最佳個體。

Step4更新參數r1,r2,r3,r4。

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

Step6計算新的個體適應度值，根據更新機制選出最佳個體位置。

Step7若t

5 實驗與結果分析

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

(8)

5.1 實驗數據與參數

實驗數據選取了復旦大學數據庫中的5 442篇文檔，包括能源、農業、歷史、體育、政治和法律6個類別，如表1所示。

Table 1 Experimental data表1 實驗數據

IGSCA算法和IGISCA算法中的種群大小均設置為m=40，最大迭代次數tmax=80。IGISCA算法中最大權重wmax=0.9，最小權重wmin=0.3，適應度函數權重α=0.9。

5.2 結果與分析

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

(1)特征維度實驗。

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

Table 2 Feature dimension experiment under KNN表2 KNN下的特征維度實驗

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

(2)類別實驗。

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

Table 3 Feature dimension experiment under NB classifier表3 貝葉斯分類器下的特征維度實驗

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

Figure 2 Category experiment under KNN classifier圖2 KNN分類器下的類別實驗

Figure 3 Category experiment under NB classifier圖3 貝葉斯分類器下的類別實驗

(3)特征個數。

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

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

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

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

6 結束語

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