基于改進樽海鞘群算法的特征選擇方法

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

(1.山西大同大學 計算機與網絡工程學院，山西 大同 037009；2.山西大同大學 網絡信息中心，山西 大同 037009)

0 引 言

數據分類是許多應用中的熱點問題，現在一般采用機器學習進行分類，但分類的性能會受到冗余特征和噪聲的影響，特征選擇在提高機器學習技術的準確性和響應時間方面起著重要作用。特征選擇的目標是去除不相關、冗余和噪聲的數據，從而降低特征維度，提高分類精度。

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

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

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

1 基本樽海鞘群算法

樽海鞘群以鏈狀進行活動，前端的樽海鞘稱為領導者，其余的是追隨者，基于樽海鞘群算法的數學模型如式(1)～式(3)[3]：

SSA領導者位置更新如式(1)

(1)

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

(2)

式中：l和lmax分別表示當前迭代次數和最大迭代次數。

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

(3)

基本SSA采用隨機初始化種群，種群多樣性較差；領導者位置更新隨機性大，收斂速度慢；追隨者進行局部開發，對新解一律接受，不考慮解的優劣，可能會導致陷入局部最優。上述原因，使基本SSA算法收斂精度不高，收斂速度慢且易陷入局部最優解。

2 改進的樽海鞘群算法

對于基本SSA的缺點，本文分別從種群初始化及領導者和追隨者的位置更新對SSA進行改進。

2.1 種群初始化

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

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

(4)

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

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

圖1 對比Logistic、Chebyshev和ICMIC映射分布

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

(5)

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

(6)

2.2 領導者位置更新方式改進

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

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

(7)

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

(8)

ω(l) 反映樽海鞘領導者受全局最優解影響程度的變化，ω(l)控制算法在搜索空間中更好地進行全局勘探和局部開發。增加ICMIC映射和非線性算子的算法稱為CSSA。

2.3 追隨者位置更新改進

(9)

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

(10)

c4=exprnd(0.6)

(11)

2.4 CESSA偽代碼

增加ICMIC映射并使用2.2節、2.3節中的領導者和追隨者位置修改的算法命名為CESSA，算法步驟如下：

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

步驟2 計算每個樽海鞘的適應度值，找出最優的適應度值，作為食物源F。

步驟3 根據式(8)計算領導者樽海鞘的位置更新。

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

步驟5 種群的每個樽海鞘位置均已經更新，執行步驟6，否則跳轉到步驟3。

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

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

步驟8 輸出最優解食物源F。

3 基于CESSA的特征選擇算法

CESSA算法與K近鄰分類器結合形成一種特征選擇分類模型CESSAFS。在模型中，采用CESSA算法在搜索空間選擇特征子集，K近鄰分類器對選擇的特征子集進行評估。

3.1 初始化

特征選擇問題是二元優化問題，CESSAFS首先通過ICMIC生成P個個體，每個個體代表給定優化問題的解，維度是分類數據集的特征總數。然后，采用式(12)把每個解轉換為二進制BX

(12)

3.2 適應度函數

特征選擇的目標是要求分類的準確率高(即分類錯誤率低)，選擇的特征子集盡量小，構造的適應度函數如式(13)，通過適應度函數評估每個解的質量

(13)

式中：α和β是權重因子，用于確定偏重分類準確率還是選擇的特征數，|n| 是選擇的特征數，|D| 是數據集的總特征數。

3.3 特征選擇實現流程

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

圖2 CESSAFS算法的流程

4 實驗與結果分析

4.1 CESSA性能分析

為了驗證本文改進算法在優化問題中的收斂速度和解的精度等性能，選取8個基準測試函數對改進算法進行仿真實驗，F1～F4是單峰函數，單峰函數在定義域內只有一個最小值，測試算法的收斂速度和精度，F5～F8是多峰函數，多峰函數含有多個局部最優解，測試算法跳出局部最優值，進行全局勘探的能力。其中F1函數維度30，F8函數維度是4，其余函數維度均為10，8個函數自變量的范圍和最小值均采用默認值。

4.1.1 優化性能分析

實驗使用的操作系統是Windows10，CPU 2.6 GHz，內存16 G，Matlab R2016a編寫程序代碼，迭代次數500，種群數30。比較基本算法SSA，改進后的算法CSSA、ESSA和CESSA的運行情況，各算法分別獨立運行30次，獲取實驗結果的平均值和標準差進行評價，實驗結果見表1。

表1 基準測試函數優化結果

由表1中的平均值反映算法的收斂精度，CSSA、ESSA和CESSA都比標準的SSA尋優精度高，說明加入不同策略可以增強算法的性能。對于4個單峰函數，CESSA在求解精度上最高達到1e-135。對于4個多峰函數，F5和F7達到了理論的極值點0，表明引入指數隨機數算子進行擾動，對算法跳出局部最優具有較大作用，F6的收斂精度大大改進，F8的收斂精度與SSA的相當，但仍優于SSA的收斂精度。CSSA、ESSA和CESSA的標準差都比SSA的小，說明改進的算法尋優具有穩定性。可見，CESSA算法在求解單峰、多峰的高維基準函數時具有明顯的優勢。

4.1.2 收斂性分析

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

圖3 函數收斂曲線

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

4.2 CESSAFS性能分析

選取機器學習數據集UCI中的10個典型數據集測試算法CESSAFS的性能，數據集的信息見表2。

表2 UCI中的部分數據集

采用十折交叉驗證，每個數據集被隨機分成10份，每份大小相同，其中1份作為測試集，9份作為訓練集，重復10次實驗，結果取平均值。

4.2.1 實驗設計

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

算法分別在每個數據集上獨立運行10次，取結果的平均值，比較算法的平均適應度值、平均分類準確度、平均選擇的特征數，實驗環境設置同4.1。

4.2.2 實驗結果分析

算法在10個UCI數據集上的實驗結果見表3和表4。

表3 不同算法在UCI數據集上的平均適應度值對比

表4 不同算法在UCI上平均分類準確率和所選特征數的對比

CESSAFS算法的適應度函數由分類錯誤率和所選特征率組成，函數的適應度值越低，說明算法效果越好。分類錯誤率越低，則數據分類的準確率越高；所選特征越少，則算法的降維效果越好。平均適應度值反映以上兩個目標的綜合情況，從表3可以看出，CESSAFS的平均適應度值整體最優，在10個數據集中的6個達到比較算法中最低值，然后是SCA和ALO，分別在2個數據集上達到平均適應度值的最小值。上面數據說明，CESSAFS的綜合性能在搜索空間中表現是最佳的。

數據分類準確率分析。從表4可以看出，CESSAFS在10個數據集的6個數據集中達到最優的分類準確率，剩余的4個數據集中，SCA在兩個數據集上達到最優，ALO在兩個數據集上達到最優。在Tic-tac-toe數據集上，CESSAFS的準確率僅比排在第一的ALO低0.040，在Ionosphere數據集上，CESSAFS的準確率僅比排在第一的SCA低0.014，在lymphography數據集上僅比排第一的SCA低0.020，在Chess數據集中，比排第一的ALO低0.001。說明CESSAFS對數據分類的準確率整體是良好的。

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

對比CESSAFS算法與其它算法的平均適應度值，平均分類準確率和平均選擇的特征個數，可以看出CESSAFS的整體性能較優，說明本文引入的改進策略是有效的。

5 結束語

本文提出了一種改進的SSA算法CESSA，為了評估CESSA的性能，在8個基準函數上進行了測試，仿真結果表明CESSA算法能平衡全局和局部搜索，提高解的精度。CESSA與K近鄰分類器結合構成分類算法CESSAFS，進行特征選擇，把CESSAFS在UCI的10個數據集中進行測試，并對比包裝式特征選擇算法PSO、BOA、SCA、ALO和WOA，結果表明，CESSAFS在整體性能指標上優于其它特征選擇算法，說明算法是有效的。未來可以將改進算法應用到不同優化問題，如任務調度、云計算和圖像分割等，還可以探索算法的多目標優化問題。