基于改進(jìn)樽海鞘群算法的特征選擇方法

申晉祥，鮑美英，張景安，周建慧

(1.山西大同大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)工程學(xué)院，山西 大同 037009；2.山西大同大學(xué) 網(wǎng)絡(luò)信息中心，山西 大同 037009)

0 引 言

數(shù)據(jù)分類是許多應(yīng)用中的熱點(diǎn)問(wèn)題，現(xiàn)在一般采用機(jī)器學(xué)習(xí)進(jìn)行分類，但分類的性能會(huì)受到冗余特征和噪聲的影響，特征選擇在提高機(jī)器學(xué)習(xí)技術(shù)的準(zhǔn)確性和響應(yīng)時(shí)間方面起著重要作用。特征選擇的目標(biāo)是去除不相關(guān)、冗余和噪聲的數(shù)據(jù)，從而降低特征維度，提高分類精度。

特征選擇主要有兩種方法，過(guò)濾式方法和包裝式方法。傳統(tǒng)的特征選擇方法在處理高維數(shù)據(jù)時(shí)時(shí)間成本高且不一定能得到真正的最優(yōu)解。目前，通過(guò)把啟發(fā)式算法引入特征選擇，提高特征選擇的性能，用于特征選擇的啟發(fā)式算法有粒子群算法、遺傳算法、鯨魚(yú)優(yōu)化算法[1]、正余弦算法[2]、樽海鞘群算法[3]、蝴蝶優(yōu)化算法[4]、蟻獅優(yōu)化算法[5]、頭腦風(fēng)暴優(yōu)化算法[6]、布谷鳥(niǎo)優(yōu)化算法[7]和果蠅優(yōu)化算法[8]等。

樽海鞘群算法[3](salp swarm algorithm，SSA)是Mirjalili等受深海中樽海鞘覓食和運(yùn)動(dòng)的啟發(fā)而開(kāi)發(fā)的一種新的群智能算法，該算法參數(shù)少，易實(shí)現(xiàn)，在解決低維優(yōu)化問(wèn)題時(shí)表現(xiàn)出良好的性能，目前已經(jīng)廣泛應(yīng)用到多個(gè)領(lǐng)域，如機(jī)械設(shè)計(jì)、頻率調(diào)控、圖像閾值分割和特征選擇等。在特征選擇領(lǐng)域的研究主要有：文獻(xiàn)[9]采用基于主成分分析和快速獨(dú)立成分分析的混合數(shù)據(jù)變換方法對(duì)原始數(shù)據(jù)進(jìn)行變換，使用二進(jìn)制SSA算法進(jìn)行特征選擇，算法去除了不相關(guān)特征，提高了分類精度。文獻(xiàn)[10]混合SSA和PSO算法用于特征選擇，混合算法進(jìn)行特征選擇時(shí)性能和精度都有所增強(qiáng)。文獻(xiàn)[11]在SSA中引入對(duì)立學(xué)習(xí)和局部搜索算法，增加了種群的多樣性，提高了局部開(kāi)發(fā)，在特征選擇中效果良好。文獻(xiàn)[12]在SSA中增加動(dòng)態(tài)時(shí)變策略和局部最優(yōu)解，提出一種多目標(biāo)SSA算法，有效平衡勘探和開(kāi)發(fā)，算法收斂速度快且不易陷入局部最優(yōu)。文獻(xiàn)[13]提出動(dòng)態(tài)SSA算法，位置更新公式中引入Singer混沌映射，增強(qiáng)解的多樣性；采用新的局部搜索算法，改善局部開(kāi)發(fā)。

為提高SSA的收斂速度和精度，本文提出一種融合多種策略的改進(jìn)算法CESSA。首先，采用無(wú)限折疊混沌映射(iterative chaotic map with infinite collapses，ICMIC)生成初始種群，使個(gè)體均勻分布在搜索空間，增強(qiáng)種群多樣性；其次，在領(lǐng)導(dǎo)者位置更新中引入非線性收斂算子，控制搜索范圍，加快收斂速度；最后，在追隨者位置更新處根據(jù)樽海鞘個(gè)體的適應(yīng)度值優(yōu)劣分別采用線性算子和隨機(jī)數(shù)進(jìn)行更新。利用改進(jìn)后的算法全局搜索能力增強(qiáng)，尋優(yōu)精度增高的特點(diǎn)，將CESSA與K近鄰(k-nearest neighbor，KNN)分類器結(jié)合形成特征選擇算法CESSAFS。通過(guò)實(shí)驗(yàn)對(duì)算法進(jìn)行驗(yàn)證，為數(shù)據(jù)分類提供新方法。

1 基本樽海鞘群算法

樽海鞘群以鏈狀進(jìn)行活動(dòng)，前端的樽海鞘稱為領(lǐng)導(dǎo)者，其余的是追隨者，基于樽海鞘群算法的數(shù)學(xué)模型如式(1)～式(3)[3]：

SSA領(lǐng)導(dǎo)者位置更新如式(1)

(1)

c1=2e-(4l/lmax)2

(2)

式中：l和lmax分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

SSA追隨者位置更新如式(3)

(3)

基本SSA采用隨機(jī)初始化種群，種群多樣性較差；領(lǐng)導(dǎo)者位置更新隨機(jī)性大，收斂速度慢；追隨者進(jìn)行局部開(kāi)發(fā)，對(duì)新解一律接受，不考慮解的優(yōu)劣，可能會(huì)導(dǎo)致陷入局部最優(yōu)。上述原因，使基本SSA算法收斂精度不高，收斂速度慢且易陷入局部最優(yōu)解。

2 改進(jìn)的樽海鞘群算法

對(duì)于基本SSA的缺點(diǎn)，本文分別從種群初始化及領(lǐng)導(dǎo)者和追隨者的位置更新對(duì)SSA進(jìn)行改進(jìn)。

2.1 種群初始化

基本SSA隨機(jī)初始化種群，如式(4)

X=rand(N，D).*(ub-lb)+lb

(4)

式中：rand(N，D) 生成一個(gè)N×D的隨機(jī)矩陣，每個(gè)元素值都在(0，1)范圍內(nèi)，N是種群個(gè)數(shù)，D是解的維度。ub和lb分別表示搜索空間的上、下邊界，“.*”表示矩陣的點(diǎn)乘，X是搜索空間的N×D矩陣。

混沌理論是數(shù)學(xué)方法，它可以提高元啟發(fā)式算法的性能，文獻(xiàn)[14，15]中指出，用混沌映射代替模型中的隨機(jī)數(shù)可以提高算法的全局收斂能力，防止陷入局部最優(yōu)。現(xiàn)有的混沌映射有多種，有些已經(jīng)引入優(yōu)化算法，如Logistic映射、Chebyshev映射等，ICMIC[16]映射在混沌區(qū)域內(nèi)的均勻分布特性優(yōu)于Logistic映射和Chebyshev映射，對(duì)比Logistic、Chebyshev和ICMIC映射的分布(如圖1所示)，取初值相同，迭代次數(shù)相同，迭代150次，發(fā)現(xiàn)ICMIC映射分布更均勻。種群的初始位置對(duì)算法的收斂速度和尋優(yōu)精度有很大影響，本文采用ICMIC映射初始化種群，比隨機(jī)方式生成的種群多樣性更好，分布更均勻，避免算法早熟或陷入局部極值。

圖1 對(duì)比Logistic、Chebyshev和ICMIC映射分布

ICMIC映射產(chǎn)生初始種群如下，首先通過(guò)ICMIC映射在[0，1]區(qū)間產(chǎn)生混沌序列，如式(5)

(5)

式中：α∈(0，1) 是控制參數(shù)，xn的初始值是0.152，α越大產(chǎn)生的混沌序列越好，選取α=0.9。

(6)

2.2 領(lǐng)導(dǎo)者位置更新方式改進(jìn)

優(yōu)化算法一般有一個(gè)平衡全局和局部搜索的參數(shù)，在SSA算法中是c1， 算法迭代前期進(jìn)行全局勘探，尋找有希望的解空間，迭代后期在最優(yōu)解附近進(jìn)行開(kāi)發(fā)，提高解的精確度?；維SA中，領(lǐng)導(dǎo)者位置更新采用概率方法，領(lǐng)導(dǎo)者從迭代開(kāi)始直接向食物源移動(dòng)，移動(dòng)的步長(zhǎng)和方向都是隨機(jī)的，搜索范圍不確定，可能出現(xiàn)早熟收斂，也可能跳出全局最優(yōu)，為改善這種情況，提高精確搜索，引入非線性算子(如式(7)所示)，使迭代后期可以在小范圍內(nèi)進(jìn)行精確搜索

ω(l)=3-20(l/lmax)

(7)

式中：l和lmax是當(dāng)前迭代次數(shù)和最大迭代次數(shù)，利用ω(l) 控制搜索范圍，迭代前期，領(lǐng)導(dǎo)者搜索范圍較大，隨著迭代增加，搜索范圍減小，迭代后期，收斂在最優(yōu)解附近進(jìn)行小范圍精確搜索，提高尋優(yōu)精度。如式(8)

(8)

ω(l) 反映樽海鞘領(lǐng)導(dǎo)者受全局最優(yōu)解影響程度的變化，ω(l)控制算法在搜索空間中更好地進(jìn)行全局勘探和局部開(kāi)發(fā)。增加ICMIC映射和非線性算子的算法稱為CSSA。

2.3 追隨者位置更新改進(jìn)

(9)

g(l)=0.5*(lmax-l)/lmax

(10)

c4=exprnd(0.6)

(11)

2.4 CESSA偽代碼

增加ICMIC映射并使用2.2節(jié)、2.3節(jié)中的領(lǐng)導(dǎo)者和追隨者位置修改的算法命名為CESSA，算法步驟如下：

步驟1 設(shè)置算法初始參數(shù)。種群規(guī)模N， 搜索空間維度D， 最大迭代次數(shù)lmax， 搜索空間上界ub和下界lb等，使用ICMIC產(chǎn)生初始種群Xi(i=1，2，…，N)。

步驟2 計(jì)算每個(gè)樽海鞘的適應(yīng)度值，找出最優(yōu)的適應(yīng)度值，作為食物源F。

步驟3 根據(jù)式(8)計(jì)算領(lǐng)導(dǎo)者樽海鞘的位置更新。

步驟4 根據(jù)式(9)計(jì)算追隨者樽海鞘的位置。

步驟5 種群的每個(gè)樽海鞘位置均已經(jīng)更新，執(zhí)行步驟6，否則跳轉(zhuǎn)到步驟3。

步驟6 根據(jù)搜索空間的上下界ub、lb修正越界的樽海鞘的位置。

步驟7 若迭代終止條件不滿足，則跳轉(zhuǎn)到步驟2。

步驟8 輸出最優(yōu)解食物源F。

3 基于CESSA的特征選擇算法

CESSA算法與K近鄰分類器結(jié)合形成一種特征選擇分類模型CESSAFS。在模型中，采用CESSA算法在搜索空間選擇特征子集，K近鄰分類器對(duì)選擇的特征子集進(jìn)行評(píng)估。

3.1 初始化

特征選擇問(wèn)題是二元優(yōu)化問(wèn)題，CESSAFS首先通過(guò)ICMIC生成P個(gè)個(gè)體，每個(gè)個(gè)體代表給定優(yōu)化問(wèn)題的解，維度是分類數(shù)據(jù)集的特征總數(shù)。然后，采用式(12)把每個(gè)解轉(zhuǎn)換為二進(jìn)制BX

(12)

3.2 適應(yīng)度函數(shù)

特征選擇的目標(biāo)是要求分類的準(zhǔn)確率高(即分類錯(cuò)誤率低)，選擇的特征子集盡量小，構(gòu)造的適應(yīng)度函數(shù)如式(13)，通過(guò)適應(yīng)度函數(shù)評(píng)估每個(gè)解的質(zhì)量

(13)

式中：α和β是權(quán)重因子，用于確定偏重分類準(zhǔn)確率還是選擇的特征數(shù)，|n| 是選擇的特征數(shù)，|D| 是數(shù)據(jù)集的總特征數(shù)。

3.3 特征選擇實(shí)現(xiàn)流程

CESSAFS的特征選擇流程如圖2所示。

圖2 CESSAFS算法的流程

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

4.1 CESSA性能分析

為了驗(yàn)證本文改進(jìn)算法在優(yōu)化問(wèn)題中的收斂速度和解的精度等性能，選取8個(gè)基準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)，F(xiàn)1～F4是單峰函數(shù)，單峰函數(shù)在定義域內(nèi)只有一個(gè)最小值，測(cè)試算法的收斂速度和精度，F(xiàn)5～F8是多峰函數(shù)，多峰函數(shù)含有多個(gè)局部最優(yōu)解，測(cè)試算法跳出局部最優(yōu)值，進(jìn)行全局勘探的能力。其中F1函數(shù)維度30，F(xiàn)8函數(shù)維度是4，其余函數(shù)維度均為10，8個(gè)函數(shù)自變量的范圍和最小值均采用默認(rèn)值。

4.1.1 優(yōu)化性能分析

實(shí)驗(yàn)使用的操作系統(tǒng)是Windows10，CPU 2.6 GHz，內(nèi)存16 G，Matlab R2016a編寫(xiě)程序代碼，迭代次數(shù)500，種群數(shù)30。比較基本算法SSA，改進(jìn)后的算法CSSA、ESSA和CESSA的運(yùn)行情況，各算法分別獨(dú)立運(yùn)行30次，獲取實(shí)驗(yàn)結(jié)果的平均值和標(biāo)準(zhǔn)差進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 基準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果

由表1中的平均值反映算法的收斂精度，CSSA、ESSA和CESSA都比標(biāo)準(zhǔn)的SSA尋優(yōu)精度高，說(shuō)明加入不同策略可以增強(qiáng)算法的性能。對(duì)于4個(gè)單峰函數(shù)，CESSA在求解精度上最高達(dá)到1e-135。對(duì)于4個(gè)多峰函數(shù)，F(xiàn)5和F7達(dá)到了理論的極值點(diǎn)0，表明引入指數(shù)隨機(jī)數(shù)算子進(jìn)行擾動(dòng)，對(duì)算法跳出局部最優(yōu)具有較大作用，F(xiàn)6的收斂精度大大改進(jìn)，F(xiàn)8的收斂精度與SSA的相當(dāng)，但仍優(yōu)于SSA的收斂精度。CSSA、ESSA和CESSA的標(biāo)準(zhǔn)差都比SSA的小，說(shuō)明改進(jìn)的算法尋優(yōu)具有穩(wěn)定性。可見(jiàn)，CESSA算法在求解單峰、多峰的高維基準(zhǔn)函數(shù)時(shí)具有明顯的優(yōu)勢(shì)。

4.1.2 收斂性分析

為了更清楚觀察算法的收斂性能，繪制算法SSA、CSSA、ESSA、CESSA在求解30維函數(shù)時(shí)的收斂曲線，如圖3所示。

圖3 函數(shù)收斂曲線

圖3是各算法在8個(gè)基準(zhǔn)函數(shù)運(yùn)行的收斂曲線，從圖上可以更加直觀地看出各算法的收斂精度和收斂速度的差異，圖中橫坐標(biāo)是迭代次數(shù)，縱坐標(biāo)是適應(yīng)度值。由圖3(a)～圖3(h)觀察發(fā)現(xiàn)，迭代初期，CSSA、ESSA和CESSA都迅速下降，這是混沌映射初始化種群的效果，使種群具有多樣性，出現(xiàn)快速收斂，隨著迭代次數(shù)的增加持續(xù)下降，未出現(xiàn)停滯現(xiàn)象并且尋優(yōu)精度較高。SSA算法收斂曲線下降較慢，隨迭后期停止。F5和F7收斂速度快，并達(dá)到理論最優(yōu)值0。由圖3可以看出，CESSA算法在對(duì)8個(gè)基準(zhǔn)函數(shù)優(yōu)化時(shí)，收斂速度都是最優(yōu)，尤其在函數(shù)F1、F3、F7上，收斂速度明顯優(yōu)于其它算法。結(jié)果驗(yàn)證本文對(duì)算法的改進(jìn)是有效的，改進(jìn)的算法尋優(yōu)效果好，性能穩(wěn)定，最優(yōu)解精度更高。

4.2 CESSAFS性能分析

選取機(jī)器學(xué)習(xí)數(shù)據(jù)集UCI中的10個(gè)典型數(shù)據(jù)集測(cè)試算法CESSAFS的性能，數(shù)據(jù)集的信息見(jiàn)表2。

表2 UCI中的部分?jǐn)?shù)據(jù)集

采用十折交叉驗(yàn)證，每個(gè)數(shù)據(jù)集被隨機(jī)分成10份，每份大小相同，其中1份作為測(cè)試集，9份作為訓(xùn)練集，重復(fù)10次實(shí)驗(yàn)，結(jié)果取平均值。

4.2.1 實(shí)驗(yàn)設(shè)計(jì)

為了客觀評(píng)價(jià)CESSAFS算法的性能，本文采用包裝式特征選擇算法PSO、BOA、SCA、ALO和WOA與本文的特征選擇算法CESSAFS進(jìn)行比較。算法的種群規(guī)模設(shè)置為20，迭代次數(shù)為100，KNN中的k取值5，維度是分類數(shù)據(jù)集的特征個(gè)數(shù)，與其它算法保持一致，CESSAFS的適應(yīng)度函數(shù)的權(quán)重α=0.99，β=0.01。PSO的c1=2，c2=2，慣性設(shè)置0.9；SCA的參數(shù)A設(shè)置為2。

算法分別在每個(gè)數(shù)據(jù)集上獨(dú)立運(yùn)行10次，取結(jié)果的平均值，比較算法的平均適應(yīng)度值、平均分類準(zhǔn)確度、平均選擇的特征數(shù)，實(shí)驗(yàn)環(huán)境設(shè)置同4.1。

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

算法在10個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果見(jiàn)表3和表4。

表3 不同算法在UCI數(shù)據(jù)集上的平均適應(yīng)度值對(duì)比

表4 不同算法在UCI上平均分類準(zhǔn)確率和所選特征數(shù)的對(duì)比

CESSAFS算法的適應(yīng)度函數(shù)由分類錯(cuò)誤率和所選特征率組成，函數(shù)的適應(yīng)度值越低，說(shuō)明算法效果越好。分類錯(cuò)誤率越低，則數(shù)據(jù)分類的準(zhǔn)確率越高；所選特征越少，則算法的降維效果越好。平均適應(yīng)度值反映以上兩個(gè)目標(biāo)的綜合情況，從表3可以看出，CESSAFS的平均適應(yīng)度值整體最優(yōu)，在10個(gè)數(shù)據(jù)集中的6個(gè)達(dá)到比較算法中最低值，然后是SCA和ALO，分別在2個(gè)數(shù)據(jù)集上達(dá)到平均適應(yīng)度值的最小值。上面數(shù)據(jù)說(shuō)明，CESSAFS的綜合性能在搜索空間中表現(xiàn)是最佳的。

數(shù)據(jù)分類準(zhǔn)確率分析。從表4可以看出，CESSAFS在10個(gè)數(shù)據(jù)集的6個(gè)數(shù)據(jù)集中達(dá)到最優(yōu)的分類準(zhǔn)確率，剩余的4個(gè)數(shù)據(jù)集中，SCA在兩個(gè)數(shù)據(jù)集上達(dá)到最優(yōu)，ALO在兩個(gè)數(shù)據(jù)集上達(dá)到最優(yōu)。在Tic-tac-toe數(shù)據(jù)集上，CESSAFS的準(zhǔn)確率僅比排在第一的ALO低0.040，在Ionosphere數(shù)據(jù)集上，CESSAFS的準(zhǔn)確率僅比排在第一的SCA低0.014，在lymphography數(shù)據(jù)集上僅比排第一的SCA低0.020，在Chess數(shù)據(jù)集中，比排第一的ALO低0.001。說(shuō)明CESSAFS對(duì)數(shù)據(jù)分類的準(zhǔn)確率整體是良好的。

選擇特征個(gè)數(shù)分析。從表4中可以看出，CESSAFS在10個(gè)數(shù)據(jù)集中選擇的特征數(shù)均值達(dá)到最小的有5個(gè)數(shù)據(jù)集，SCA在10個(gè)數(shù)據(jù)集中的4數(shù)據(jù)集中選擇的特征數(shù)數(shù)最小，其次是BOA，在1個(gè)數(shù)據(jù)集中所選擇的特征數(shù)最小。在Wine數(shù)據(jù)集上，雖然SCA選擇的特征數(shù)最小，但CESSAFS的平均分類準(zhǔn)確率比SCA高0.0057。綜合分析，CESSAFS在數(shù)據(jù)降維方面表現(xiàn)良好，在大多數(shù)數(shù)據(jù)集中縮減數(shù)據(jù)特征的同時(shí)還能保持較高的分類準(zhǔn)確率。

對(duì)比CESSAFS算法與其它算法的平均適應(yīng)度值，平均分類準(zhǔn)確率和平均選擇的特征個(gè)數(shù)，可以看出CESSAFS的整體性能較優(yōu)，說(shuō)明本文引入的改進(jìn)策略是有效的。

5 結(jié)束語(yǔ)

本文提出了一種改進(jìn)的SSA算法CESSA，為了評(píng)估CESSA的性能，在8個(gè)基準(zhǔn)函數(shù)上進(jìn)行了測(cè)試，仿真結(jié)果表明CESSA算法能平衡全局和局部搜索，提高解的精度。CESSA與K近鄰分類器結(jié)合構(gòu)成分類算法CESSAFS，進(jìn)行特征選擇，把CESSAFS在UCI的10個(gè)數(shù)據(jù)集中進(jìn)行測(cè)試，并對(duì)比包裝式特征選擇算法PSO、BOA、SCA、ALO和WOA，結(jié)果表明，CESSAFS在整體性能指標(biāo)上優(yōu)于其它特征選擇算法，說(shuō)明算法是有效的。未來(lái)可以將改進(jìn)算法應(yīng)用到不同優(yōu)化問(wèn)題，如任務(wù)調(diào)度、云計(jì)算和圖像分割等，還可以探索算法的多目標(biāo)優(yōu)化問(wèn)題。