采用改進(jìn)黑猩猩優(yōu)化算法的特征選擇

張婉瑩，冷 欣，賈鶴鳴

（1.東北林業(yè)大學(xué)機(jī)電工程學(xué)院 黑龍江省 哈爾濱 150040；2.三明學(xué)院信息工程學(xué)院 福建 三明 365004）

隨著社會逐漸趨于數(shù)字化，如何從繁雜龐大的數(shù)據(jù)中有效提取出有用信息成為了近些年的研究重點(diǎn)，機(jī)器學(xué)習(xí)因其較強(qiáng)的數(shù)據(jù)處理能力得到了廣泛應(yīng)用。傳統(tǒng)機(jī)器學(xué)習(xí)包括隨機(jī)森林算法、樸素貝葉斯算法和支持向量機(jī)(support vector machine,SVM)等[1]。王聯(lián)英等[2]利用C4.5算法構(gòu)造決策樹，顯著提高了分類效果；李鮮[3]基于隨機(jī)森林的特征選擇算法解決了圖像處理中灰度對比度低、邊界模糊等問題；崔良中[4]通過改進(jìn)樸素貝葉斯算法解決了近年來機(jī)器學(xué)習(xí)領(lǐng)域數(shù)據(jù)分類時間過長的問題；張健沛[5]提出了一種利用支持向量機(jī)進(jìn)行主動學(xué)習(xí)的方法，解決了部分機(jī)器學(xué)習(xí)問題中獲取訓(xùn)練樣本代價過大的問題。上述文獻(xiàn)研究探索了不同的機(jī)器學(xué)習(xí)算法，而目前許多研究者們提出將優(yōu)化算法與特征選擇工作任務(wù)相結(jié)合來研究如何高效無差錯地進(jìn)行數(shù)據(jù)預(yù)處理工作[6]。特征選擇就是從樣本中選擇特征子集[7]，特征子集的獲取有過濾式、封裝式和嵌入式三種類型[8-10]。封裝式就是將子集的選擇看作是一個搜索尋優(yōu)問題。如Mafarja等[11]提出了一種基于鯨魚優(yōu)化的封裝式特征選擇方法；張霞等[12]提出一種增強(qiáng)蜂群算法優(yōu)化的封裝式特征選擇方法。以上研究表明，封裝式特征選擇能夠有效與元啟發(fā)式優(yōu)化算法相結(jié)合，并取得較好的實(shí)際應(yīng)用效果。

傳統(tǒng)黑猩猩優(yōu)化算法(chimp optimization algorithm,ChOA)將猩猩分為不同等級，使其能很好地解決收斂速度慢的問題。但是該算法仍存在陷入局部最優(yōu)的風(fēng)險。黃倩等[13]人提出了一種多策略黑猩猩優(yōu)化算法以提高種群的局部開發(fā)能力和勘探能力，從而提高算法的收斂精度。Mandeep Kaur等[14]提出了一種正弦余弦黑猩猩優(yōu)化算法來克服黑猩猩優(yōu)化算法收斂速度慢的缺點(diǎn)。針對黑猩猩優(yōu)化算法易陷入局部最優(yōu)的缺點(diǎn)提出了一種改進(jìn)的黑猩猩優(yōu)化算法(improved chimp optimization algorithm,IChOA)。通過改進(jìn)低等級黑猩猩的位置來提高黑猩猩的全局搜索能力。首先引入斯皮爾曼等級相關(guān)系數(shù)計算低等級和高等級黑猩猩之間的距離，針對距離高等級黑猩猩較遠(yuǎn)的黑猩猩再引入甲蟲天線搜索算法，使其能根據(jù)周圍環(huán)境改變自己的運(yùn)動方向，從而提高局部搜索能力，進(jìn)而提高黑猩猩算法的全局搜索尋優(yōu)能力。

本文的主要研究內(nèi)容如下，首先在原始黑猩猩算法中引入斯皮爾曼等級相關(guān)系數(shù)和甲蟲天線搜索算法，以增強(qiáng)全局搜索能力；然后，利用改進(jìn)后的黑猩猩優(yōu)化算法對支持向量機(jī)進(jìn)行優(yōu)化，將此模型應(yīng)用于封裝式特征選擇中；最后，將該改進(jìn)算法與四種優(yōu)化算法在10種數(shù)據(jù)集中進(jìn)行比較，證明該算法在提高全局優(yōu)化精度、減少所需特征數(shù)和避免陷入局部最優(yōu)方面有明顯優(yōu)勢，具有較高的工程實(shí)用價值。

1 背景知識

1.1 支持向量機(jī)

支持向量機(jī)是Vapnik在統(tǒng)計學(xué)基礎(chǔ)上提出的[15]，因其擁有較強(qiáng)的計算能力，所以被廣泛應(yīng)用于模式識別和回歸分析中[16]。它通過構(gòu)造最優(yōu)的分離超平面對數(shù)據(jù)進(jìn)行分類，構(gòu)造出的分離超平面不僅要盡可能不出錯地分離兩種數(shù)據(jù)，而且要使兩者之間的分離間隔盡可能達(dá)到最大[17]，超平面的數(shù)學(xué)方程如下：

式中，w為垂直于超平面的權(quán)值，x為超平面上的特征向量，b為偏置常數(shù)，原點(diǎn)到超平面中間的垂直距離用‖b‖/‖w‖表示。

支持向量機(jī)的最優(yōu)超平面如圖1所示。

圖1 SVM的最優(yōu)超平面示意圖

1.2 黑猩猩優(yōu)化算法

黑猩猩優(yōu)化算法是一個基于群智能多樣性的數(shù)學(xué)模型[18]。該算法由攻擊者、障礙者、追逐者和驅(qū)動者四種不同類型的黑猩猩配合完成狩獵。狩獵步驟分為兩個階段：第一階段為勘探階段，如圖2所示；第二階段為開發(fā)階段，如圖3所示?？碧诫A段為驅(qū)趕、阻擋和追逐獵物。而后進(jìn)入開發(fā)階段，此階段由攻擊者直接攻擊獵物。驅(qū)趕和追逐過程可表示為：

圖2 黑猩猩優(yōu)化算法的勘探階段[18]

圖3 黑猩猩優(yōu)化算法的開發(fā)階段[18]

式中：xprey代表獵物位置矢量；xchimp代表黑猩猩位置矢量；t為當(dāng)前迭代次數(shù)；a、c、m為系數(shù)矢量，這三個系數(shù)矢量由以下式子求出：

式中：f為從2.5下降到0的非線性矢量；r1和r2是0到1之間的隨機(jī)數(shù)；m是混沌向量。同時黑猩猩可以根據(jù)其他黑猩猩的位置來更新自己的位置，更新過程可以用下式表示：

2 改進(jìn)的黑猩猩優(yōu)化算法

2.1 斯皮爾曼等級相關(guān)系數(shù)

斯皮爾曼等級相關(guān)系數(shù)利用單調(diào)方程評價兩個統(tǒng)計變量的相關(guān)性，單調(diào)方程如下：

式中：ρ為斯皮爾曼等級相關(guān)系數(shù)的值；di為每對樣本的等級差；n為序列的維數(shù)。如果數(shù)據(jù)中沒有重復(fù)值，當(dāng)兩個變量完全單調(diào)相關(guān)時，斯皮爾曼相關(guān)系數(shù)的絕對值為1。

2.2 甲蟲天線搜索算法

甲蟲天線搜索算法是根據(jù)長角甲蟲尋找食物的過程提出的[19]。甲蟲在尋找食物時能通過觸角探測食物的氣味，從而發(fā)現(xiàn)食物的位置。

在尋找食物時，甲蟲通過擺動觸角來探測附近區(qū)域同時感知?dú)馕?，?dāng)甲蟲檢測到左側(cè)區(qū)域的氣味濃度高于右側(cè)時，甲蟲會像左移動，反之，甲蟲向右移動，如圖4所示。

圖4 甲蟲運(yùn)動示意圖

甲蟲的運(yùn)動方向可以由以下數(shù)學(xué)模型得到：

甲蟲在左右側(cè)搜索區(qū)域的位置分別由以下兩個數(shù)學(xué)模型得到：

式中：xl和xr分別表示甲蟲在左右搜索區(qū)域內(nèi)的位置；xt表示甲蟲在t時刻的位置；dt表示甲蟲天線所感知到的長度，此長度會隨著時間的推移逐漸減小。

甲蟲的位置更新可以用如下方程表示：

式中：δ為搜索的步長，步長的初始范圍為搜索區(qū)域；x處的氣味濃度用表示，f(x)也稱為適應(yīng)度函數(shù)。

2.3 改進(jìn)策略

由于種群的位置更新是由四個等級的黑猩猩共同決定的，為了避免種群陷入局部極小值，所以需要對低等級的黑猩猩的位置進(jìn)行改進(jìn)。通過計算驅(qū)動者和攻擊者之間的斯皮爾曼等級相關(guān)系數(shù)，可以確定它們之間的距離。斯皮爾曼等級相關(guān)系數(shù)等于0時，這兩種黑猩猩不相關(guān)，此時可以看作驅(qū)動者與攻擊者之間的距離很遠(yuǎn)。對于離攻擊者較遠(yuǎn)的黑猩猩引入甲蟲天線搜素算法，使低等級的黑猩猩獲得類似甲蟲的搜索能力，讓其能夠判斷周圍的環(huán)境，從而決定移動的方向。通過這種方式改進(jìn)低等級黑猩猩的位置，以防止此算法陷入局部最優(yōu)值。

2.4 IChOA優(yōu)化SVM與特征選擇（IChOA-SVM）

IChOA-SVM模型通過懲罰參數(shù)c和核參數(shù)g生成初級粒子，并計算適應(yīng)度值來評估黑猩猩的位置。最后輸出c、g的最優(yōu)值和最佳精度，得到最終的分類結(jié)果。

IChOA-SVM的實(shí)現(xiàn)步驟如下，流程圖如圖5所示。

圖5 IChOA-SVM算法流程圖

輸入：最大迭代次數(shù)Maxiterations，種群規(guī)模N，上界ub，下界lb，參數(shù)c的最大值cmax和最小值cmin，參數(shù)g的最大值gmax和最小值gmin。

輸出：最佳參數(shù)c和g，對應(yīng)的分類精度和適應(yīng)度。

步驟1初始化黑猩猩的數(shù)量、位置和適應(yīng)度值。

步驟2支持向量機(jī)隨機(jī)生成c和g的值，然后計算初始適應(yīng)度值。

步驟3訓(xùn)練模型由支持向量機(jī)中的訓(xùn)練集得到。

步驟4對種群重新進(jìn)行排序，得到個體的位置和適應(yīng)度值。

步驟5引入斯皮爾曼等級相關(guān)系數(shù)和甲蟲天線搜索算法來提高低等級黑猩猩更新位置的能力。

步驟6更新懲罰參數(shù)c和和核參數(shù)g后，在支持向量機(jī)上再次進(jìn)行訓(xùn)練。

步驟7進(jìn)行迭代優(yōu)化，得到最優(yōu)的c和g值以及最佳精度。

3 實(shí)驗(yàn)

本文采用UCI數(shù)據(jù)庫中的10個數(shù)據(jù)集來評價所提出的IChOA-SVM方法，表1分別給出了10個數(shù)據(jù)集的特征數(shù)、樣本數(shù)和類別數(shù)。

表1 數(shù)據(jù)集列表

為了驗(yàn)證算法的性能，本文將IChOA算法與ChOA、PSO(particle swarm algorithm)、WOA(Whale Optimization Algorithm)、GOA(g'rasshopper optimization algorithm)算法進(jìn)行比較。同時將每組實(shí)驗(yàn)重復(fù)30次，以減少隨機(jī)影響。其中種群大小為30，當(dāng)?shù)螖?shù)達(dá)到100時停止運(yùn)行。所有實(shí)驗(yàn)均在由美國 Math Works公司出品的 MATLAB軟件上進(jìn)行，所用版本為 R2016a，計算機(jī)配置為Intel(R)Core(TM)i5-1035G1 CPU@1.00GHz 1.19GHz，使用 Microsoft Windows 10 系統(tǒng)。

實(shí)驗(yàn)中所有算法的參數(shù)設(shè)置如表2所示。

表2 不同算法的參數(shù)設(shè)置

表3給出了五種算法在十個數(shù)據(jù)集上分類精度的平均值和標(biāo)準(zhǔn)差。圖6給出了其中4個數(shù)據(jù)集的精度箱型圖。由表3觀察到IChOA優(yōu)化算法在7個數(shù)據(jù)集上都獲得了最佳性能，以Bupa數(shù)據(jù)集為例，IChOA的精度約比ChOA高出4% ，這表明該數(shù)據(jù)集IChOA中的SVM參數(shù)可以得到更好的優(yōu)化；同時從精度箱形圖中的分布可以看出，IChOA的精度較為穩(wěn)定，該算法的精度在10個數(shù)據(jù)集上變化不大。值得注意的是，雖然在包含Glass數(shù)據(jù)集在內(nèi)的三個數(shù)據(jù)集中，WOA優(yōu)化算法取得了最優(yōu)精度，但從箱型圖上不難發(fā)現(xiàn)，其穩(wěn)定性略有不足。綜合分析可知IChOA在保持較高平均精度的同時也保持了較好的穩(wěn)定性。

圖6 基于4個數(shù)據(jù)集的IChOA等算法的精度箱型圖

表3 五種算法在10個數(shù)據(jù)集上的分類精度比較

表4給出了五種算法在10個數(shù)據(jù)集上所需特征數(shù)的均值和標(biāo)準(zhǔn)差。IChOA在其中9個數(shù)據(jù)集中所需的特征數(shù)量都是最低的，特別是在Iris和Liver數(shù)據(jù)集中，所需特征數(shù)的平均值非常接近1，這表明IChOA可以更有效探尋搜索空間。在Cancer和Sonar數(shù)據(jù)集中，有幾種優(yōu)化算法所需要的特征數(shù)量比其他優(yōu)化算法高得多（如WOA），但I(xiàn)ChOA無該情況發(fā)生。值得注意的是，在Iris數(shù)據(jù)集中，ChOA所需要的特征數(shù)量比IChOA高94% ，這也說明了IChOA在所需特征數(shù)量方面優(yōu)于ChOA等算法。

表4 五種算法在10個數(shù)據(jù)集上所需特征個數(shù)的比較

表5給出了五種算法在10個數(shù)據(jù)集上的適應(yīng)度值的平均值和標(biāo)準(zhǔn)差。圖7為4個實(shí)驗(yàn)所用數(shù)據(jù)集的適應(yīng)度值折線圖。IChOA的適應(yīng)度值在其中7個數(shù)據(jù)集中均取得最小值。通過收斂曲線圖可以看出大部分?jǐn)?shù)據(jù)集中，IChOA收斂時間要短于其他算法。雖然WOA在Glass，QCM和Sonar數(shù)據(jù)集中適應(yīng)度值均為最小，但其在Lymphography數(shù)據(jù)集中的適應(yīng)度值遠(yuǎn)大于其他算法。反觀IChOA算法，即使適應(yīng)度值不是最小，但其適應(yīng)度值也接近適應(yīng)度值最小的算法。綜上可以看出，IChOA比大多數(shù)算法更加優(yōu)異和穩(wěn)定。

表5 五種算法在10個數(shù)據(jù)集上的適應(yīng)度比較

續(xù)表5

圖7 基于4個數(shù)據(jù)集的IChOA等算法的適應(yīng)度值的折線圖

4 總結(jié)

針對傳統(tǒng)黑猩猩優(yōu)化算法在運(yùn)行時容易陷入局部極小值的缺陷，本文提出了一種改進(jìn)的黑猩猩優(yōu)化算法，并且將改進(jìn)的黑猩猩優(yōu)化算法結(jié)合支持向量機(jī)進(jìn)行特征優(yōu)化選擇。該方法能夠?qū)χС窒蛄繖C(jī)核函數(shù)的參數(shù)進(jìn)行調(diào)整，同時進(jìn)行特征選擇，并達(dá)到最佳的精度。從實(shí)驗(yàn)結(jié)果來看，IChOA算法在精度、特征數(shù)和適應(yīng)度值上相較于其他4種優(yōu)化算法都具有一定優(yōu)勢，且其綜合性能相對穩(wěn)定。在今后的工作中，可以進(jìn)一步嘗試提高IChOA算法的精度，使其能夠更好地應(yīng)用于特征選擇領(lǐng)域。