一種用于解決特征選擇問題的新型混合演化算法

李天翼，陳紅梅

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院 四川 成都 611756)

0 引言

特征選擇作為一種有效降低數(shù)據(jù)維度的方法，已廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域，其主要任務(wù)是刪除原始數(shù)據(jù)集中的不相關(guān)特征和冗余特征。根據(jù)評(píng)估條件，特征選擇主要可以分為過濾、包裝和嵌入式三類方法[1]。基于過濾模型的方法與分類器相互獨(dú)立，這類算法會(huì)依照相應(yīng)的評(píng)價(jià)函數(shù)對(duì)數(shù)據(jù)集中的每一個(gè)特征進(jìn)行評(píng)估。包裝型方法則利用指定的分類器，通過不同的搜索策略來評(píng)估特征子集。嵌入式方法是指特征選擇算法將被結(jié)合到學(xué)習(xí)算法的訓(xùn)練過程中，旨在學(xué)習(xí)階段評(píng)估特征子集。

假設(shè)數(shù)據(jù)集中的特征數(shù)量為n，則搜索空間中將包含2n個(gè)候選解。故使用窮舉法來獲得最佳特征子集顯然是不切實(shí)際的。一些學(xué)者將特征選擇視為組合優(yōu)化問題，認(rèn)為其目標(biāo)是盡量減少特征數(shù)量并提高分類性能。因此在解決優(yōu)化問題時(shí)體現(xiàn)出良好性能的演化算法受到了廣泛的關(guān)注。如兩種可以有效選擇特征子集的二進(jìn)制灰狼優(yōu)化算法[2]、在尋優(yōu)過程中引入二進(jìn)制粒子群優(yōu)化算法搜索最佳特征子集[3]、基于二維粒子群算法的特征選擇方法[4]等。

但是演化算法也具有過早收斂、計(jì)算成本較高等缺點(diǎn)。此外，為提高獲得全局最優(yōu)解的概率，還需要平衡探索和開發(fā)之間的關(guān)系。近年來，學(xué)者們認(rèn)為將不同的算法進(jìn)行雜交、混合是獲得更好性能的重要方法。混合型算法會(huì)利用并結(jié)合單一優(yōu)化算法或策略的優(yōu)勢(shì)，同時(shí)更有效地平衡探索和開發(fā)的關(guān)系。如將鯨魚優(yōu)化算法與差分進(jìn)化算法相結(jié)合以克服原始鯨魚算法過早收斂的缺點(diǎn)[5]；將灰狼算法與正余弦算法結(jié)合的新型混合方法以結(jié)合兩種算法的優(yōu)勢(shì)[6]?；旌闲脱莼惴ㄔ诰垲怺7]、工程測(cè)試問題[8]、車間調(diào)度[9]、函數(shù)優(yōu)化[10]、運(yùn)動(dòng)跟蹤[11]、特征選擇[12-13]等眾多領(lǐng)域都有廣泛應(yīng)用。

本文提出一種基于包裝模型的特征選擇算法——HWOA。我們使用正余弦算法的位置更新方法代替鯨魚算法的收縮環(huán)繞機(jī)制，并引入改進(jìn)的灰狼優(yōu)化算法增加搜索過程中的多樣性。為加快收斂速度并增強(qiáng)算法跳出局部最優(yōu)的能力，我們還引入非線性參數(shù)調(diào)整策略和混沌映射。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法在一定程度上提高了分類性能，同時(shí)有效降低數(shù)據(jù)維度。

1 相關(guān)工作

在本節(jié)中，我們將介紹本研究的相關(guān)工作，內(nèi)容主要包括三個(gè)經(jīng)典的演化算法：鯨魚優(yōu)化算法(WOA)、正弦余弦算法(SCA)和灰狼優(yōu)化算法(GWO)。

1.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法的靈感來自座頭鯨的狩獵行為[14]。在開發(fā)階段，鯨魚使用泡泡網(wǎng)攻擊方式，通過產(chǎn)生圓形或“9”字形路徑來包圍獵物。這對(duì)應(yīng)了收縮環(huán)繞機(jī)制和螺旋更新機(jī)制兩種不同的方式，我們假設(shè)選擇兩種方式的概率相等，均為50%，則搜索代理的下一位置計(jì)算為

其中：X*表示當(dāng)前最優(yōu)解的位置；X表示當(dāng)前鯨魚的位置；t表示當(dāng)前迭代；b是用于定義螺旋線形狀的常數(shù)；l是[-1,1]中的隨機(jī)數(shù)；p是[0,1]中的隨機(jī)數(shù)；A=2·a·r-a和C=2·r是兩個(gè)系數(shù)向量；r是一個(gè)取值在[0，1]中的隨機(jī)向量，a負(fù)責(zé)平衡探索和開發(fā)之間的關(guān)系，在迭代過程中線性地從2遞減至0。

在探索階段，原始算法中的搜索代理可以利用向量A的變化來搜索獵物。當(dāng)|A|>1時(shí)，當(dāng)前鯨魚會(huì)隨機(jī)地選擇其他鯨魚的位置作為目標(biāo)位置，即在探索階段會(huì)迫使搜索代理遠(yuǎn)離當(dāng)前的最優(yōu)解，其數(shù)學(xué)模型為Xt+1=Xrand-A·|C·Xrand-Xt|，其中：Xrand是從當(dāng)前群體中隨機(jī)選擇一個(gè)搜索代理的位置向量。

1.2 正余弦算法

正余弦算法是Mirjalili于2016年提出的一種新型優(yōu)化算法[15]。該方法會(huì)創(chuàng)建不同的初始隨機(jī)解決方案，并要求他們使用基于正弦或余弦函數(shù)的數(shù)學(xué)模型向外波動(dòng)或朝向最佳解決方案前進(jìn)，位置更新公式為

其中：Xt是第t次迭代時(shí)搜索代理的位置；X*t是目標(biāo)全局最優(yōu)解決方案；r1、r2、r3、r4均為[0,1]內(nèi)的隨機(jī)數(shù)。

1.3 灰狼優(yōu)化算法

灰狼優(yōu)化算法(GWO)是Mirjalili等通過模擬灰狼種群的社會(huì)等級(jí)和狩獵行為提出的隨機(jī)算法[16]。根據(jù)社會(huì)地位從高到低排列，灰狼種群可分為四個(gè)級(jí)別：Alpha、Beta、Delta和Omega。在傳統(tǒng)灰狼算法中，具有最佳適應(yīng)度的解定義為Alpha，排名第2、第3的解分別定義為Beta和Delta，這三者也被稱為優(yōu)勢(shì)狼。其余的候選解被視為Omega?；依前鼑C物的行為可以描述為Xt+1=Xpt-A·|C·Xpt-Xt|，其中：t表示迭代次數(shù)；X是灰狼的位置；Xp是獵物的位置；A=2·a·r1-a和C=2·r2是兩個(gè)系數(shù)向量，r1與r2是兩個(gè)取值均在[0，1]中的隨機(jī)向量。

在狩獵階段，我們假設(shè)優(yōu)勢(shì)狼對(duì)獵物的潛在位置有更多的了解，Omega狼則需要根據(jù)優(yōu)勢(shì)狼的位置更新各自的位置?；依轻鳙C的數(shù)學(xué)模型為Xt+1=(X1+X2+X3)/3，其中：X1=|Xα-A1·|C1·Xα-X||。X2與X3的計(jì)算方法與X1類似。

2 提出新型特征選擇算法

在本文中我們將鯨魚優(yōu)化算法與正余弦算法、改進(jìn)后的灰狼優(yōu)化算法進(jìn)行結(jié)合，提出一個(gè)新型的混合演化算法——HWOA。此外，我們還引入?yún)?shù)的對(duì)數(shù)衰減調(diào)整方案，并使用混沌映射調(diào)整位置更新公式中的權(quán)重參數(shù)。最終我們將該方法應(yīng)用于解決特征選擇問題。

2.1 演化算法的混合

正余弦算法已被證實(shí)在開發(fā)階段表現(xiàn)良好。而在原始鯨魚算法的迭代初期，由于控制參數(shù)的值較高，更傾向于探索，因此更需要平衡探索和開發(fā)的關(guān)系。此外，鯨魚算法將在探索階段隨機(jī)地選擇“鯨魚”，并以此為參考對(duì)其他搜索代理進(jìn)行更新，這使得算法在早期搜索中具有過高的偶然性，最終導(dǎo)致創(chuàng)建一些質(zhì)量較差的解。因此我們使用正余弦算法的位置更新方案代替了原始鯨魚算法中的收縮環(huán)繞機(jī)制。由于螺旋更新機(jī)制使用對(duì)數(shù)螺旋函數(shù)，在較短時(shí)間內(nèi)能覆蓋較大范圍的搜索空間。故在HWOA中將保留螺旋更新機(jī)制。

為增加搜索方式的多樣性并避免算法陷入局部最優(yōu)，我們還引入了一種改進(jìn)的灰狼優(yōu)化算法。在傳統(tǒng)的灰狼算法中，由于種群對(duì)全局最優(yōu)解的過度學(xué)習(xí)，算法易陷入局部最優(yōu)。受到粒子群算法的啟發(fā)，我們將個(gè)人最佳位置(pbest)的概念加入到位置更新公式中。為更好地反映灰狼種群的社會(huì)等級(jí)，我們還引入一組權(quán)重參數(shù)(w1,w2,w3)。這三個(gè)參數(shù)分別表示Alpha、Beta和Delta在狩獵行為中的決策權(quán)重，且需要滿足條件0≤w3≤w2≤w1≤1;w1+w2+w3=1。

改進(jìn)灰狼算法的位置更新為Xt+1=w·X′+c1·rand1·(Xpbest-Xt)+c2·rand2·(X1-Xt)，其中：X′=w1·X1+w2·X2+w3·X3；Xpbest表示當(dāng)前搜索代理的個(gè)人歷史最佳位置；w表示慣性權(quán)重；t表示當(dāng)前迭代；c1和c2稱為學(xué)習(xí)因子，其值為0～4；rand1和rand2是[0,1]中的隨機(jī)數(shù)。

2.2 有效的參數(shù)調(diào)整策略

首先，學(xué)術(shù)界已經(jīng)證實(shí)慣性權(quán)重w對(duì)于準(zhǔn)確地尋找全局最優(yōu)解起到重要作用，而在原始的粒子算法中w是在一定范圍內(nèi)線性遞減或者取某個(gè)固定值。為提高整體多樣性并增強(qiáng)算法避免陷入局部最優(yōu)的能力，混沌理論中的邏輯映射被用于非線性地更新參數(shù)w，wt+1=μ×wt×(1-wt)。

其次，作為平衡探索與開發(fā)關(guān)系的控制參數(shù)a，在原始算法中線性地從2遞減到0。為提高開發(fā)效率，我們選擇對(duì)數(shù)衰減函數(shù)對(duì)a進(jìn)行非線性更新，描述為

其中：a0表示參數(shù)a的初始值；af是參數(shù)a的最終值；max_iter表示最大迭代次數(shù)。

2.3 應(yīng)用于特征選擇問題

由于特征選擇問題是二值優(yōu)化問題，我們會(huì)把位置向量中值為1處相應(yīng)的特征選入特征子集中，否則將其刪除。為實(shí)現(xiàn)將位置向量中的連續(xù)值轉(zhuǎn)換為離散值，我們使用Sigmoid函數(shù)轉(zhuǎn)換為

另一重要問題是選擇合適的適應(yīng)度函數(shù)。特征選擇作為組合優(yōu)化問題，主要目標(biāo)是提高后續(xù)的分類性能，并選擇盡可能少的特征。在本項(xiàng)研究中，適應(yīng)度函數(shù)描述為fitness=αER(D)+β|S|/|F|，其中：ER(D)是分類器的分類錯(cuò)誤率；|S|表示所選特征子集中的元素?cái)?shù)量；|F|表示原始特征集中的特征數(shù)量；α和β是平衡錯(cuò)誤率和所選特征比之間關(guān)系的參數(shù)，且α+β=1，一般參數(shù)的經(jīng)驗(yàn)值取α=0.99。

2.4 算法流程

結(jié)合前文所述，本部分給出HWOA算法的實(shí)現(xiàn)流程。

1)初始化相關(guān)參數(shù)和種群；

2)根據(jù)概率參數(shù)p與0.5之間的定量關(guān)系選擇不同的位置更新方法；

3)如果p<0.5，則使用SCA算法對(duì)當(dāng)前搜索代理進(jìn)行位置更新；

4)如果p≥0.5，則根據(jù)系數(shù)A的絕對(duì)值和1的定量關(guān)系選擇WOA的螺旋更新機(jī)制或改進(jìn)的灰狼算法；

5)如果|A|<1，我們使用螺旋更新方式，否則使用改進(jìn)的灰狼算法，注意更新相關(guān)參數(shù)；

6)對(duì)每個(gè)搜索代理執(zhí)行上述操作之后，通過Sigmoid函數(shù)離散位置向量；

7)計(jì)算每個(gè)搜索代理的適應(yīng)度函數(shù)值，根據(jù)該值對(duì)代理進(jìn)行升序排序；

8)更新當(dāng)前排名適應(yīng)度值前三的搜索代理，并更新每個(gè)搜索代理的個(gè)人歷史最佳位置(pbest)；

9)確定是否滿足停止條件，若滿足則輸出當(dāng)前最優(yōu)解作為結(jié)果，否則根據(jù)上述過程再次執(zhí)行算法。

3 實(shí)驗(yàn)與結(jié)果

在本節(jié)中，我們使用本文提出的HWOA算法與其他6個(gè)基于包裝模型的特征選擇算法在11個(gè)UCI數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，給出實(shí)驗(yàn)結(jié)果并進(jìn)行分析。

3.1 數(shù)據(jù)集介紹

為驗(yàn)證特征選擇方法的有效性，我們需要在真實(shí)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。表1展示了11個(gè)用于實(shí)驗(yàn)的真實(shí)數(shù)據(jù)集，他們來自UCI機(jī)器學(xué)習(xí)存儲(chǔ)庫，具有不同數(shù)量的實(shí)例和特征。數(shù)據(jù)集的詳細(xì)信息如表1所示。

表1 UCI數(shù)據(jù)集描述

3.2 參數(shù)設(shè)置

由于我們提出的算法基于包裝模型，因此算法需要與指定的分類器配合才能完成特征選擇任務(wù)。本文中我們選擇基于歐氏距離矩陣的KNN分類器(K=5)。為了進(jìn)行對(duì)比實(shí)驗(yàn)，我們選擇了6種對(duì)比算法(SCA、BGWO、BPSO、HGWOSCA、SCWOA和HPSO-WOA)。此外，我們使用10折交叉驗(yàn)證來評(píng)估所選特征子集的性能。所有參數(shù)均設(shè)置為經(jīng)驗(yàn)值，種群數(shù)量定義為10，迭代次數(shù)設(shè)置為100次，每個(gè)算法重復(fù)執(zhí)行20次。粒子群算法中的學(xué)習(xí)因子設(shè)置為1.5，控制參數(shù)a的初始值為2.0，慣性權(quán)重w的初始值為0.9。

3.3 評(píng)價(jià)指標(biāo)

特征選擇的評(píng)估標(biāo)準(zhǔn)的名稱與計(jì)算公式如下。

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

實(shí)驗(yàn)結(jié)果見表2～9，表中的黑體數(shù)字表示該行中的最佳值。

表2 每種特征選擇方法的平均分類正確率及標(biāo)準(zhǔn)差

表3 每種特征選擇方法的平均特征子集大小

3.4.3適應(yīng)度函數(shù)值(Mean、Best、Worst)的對(duì)比 基于包裝模型的特征選擇算法的另一個(gè)重要評(píng)估標(biāo)準(zhǔn)是適應(yīng)度函數(shù)值。表4展示的是平均適應(yīng)度值，實(shí)驗(yàn)數(shù)據(jù)表明HWOA算法可在9個(gè)數(shù)據(jù)集上獲得最優(yōu)值，且平均效果依舊最佳。此外，我們發(fā)現(xiàn)BPSO和HPSO-WOA的性能較差。盡管他們選擇的特征子集維度很低，但在分類正確率和適應(yīng)度函數(shù)值的比較中，他們的表現(xiàn)均不理想，說明這兩種算法并沒有選擇出最合適的特征子集。

表4 每種特征選擇方法的平均適應(yīng)度

表5展示了算法的最佳適應(yīng)度函數(shù)值。如我們所見，HWOA在本項(xiàng)比較中沒有明顯的壓倒性優(yōu)勢(shì)，但是它的平均最佳適應(yīng)度函數(shù)值仍排名第1。值得注意的是，對(duì)于某些數(shù)據(jù)集(例如breast-cancer、CMC等)，不同的算法可能會(huì)實(shí)現(xiàn)相同的最佳適應(yīng)度函數(shù)值。

表5 每種特征選擇方法的最佳適應(yīng)度

表6展示了最差適應(yīng)度函數(shù)值。根據(jù)表6中的實(shí)驗(yàn)數(shù)據(jù)，HWOA在最差的適應(yīng)度函數(shù)值方面表現(xiàn)良好，且在8個(gè)數(shù)據(jù)集中獲得了最佳結(jié)果。這也在一定程度上表明HWOA具有更好的穩(wěn)定性。盡管有時(shí)無法達(dá)到最佳適應(yīng)度值，但其下限較高，說明HWOA不會(huì)產(chǎn)生太多質(zhì)量較差的解。

表6 每種特征選擇方法的最差適應(yīng)度

3.4.4特征選擇結(jié)果的可解釋性 本文所提出的算法是基于包裝模型的群智能優(yōu)化算法，它本質(zhì)上屬于元啟發(fā)式算法。這類算法的一個(gè)重要特點(diǎn)就是算法中會(huì)存在隨機(jī)因素，即使是固定的輸入(即同一個(gè)數(shù)據(jù)集、相同的迭代次數(shù)、相同的參數(shù)初始值)，選擇的特征子集依舊會(huì)存在差異。因此表7展示的內(nèi)容包括HWOA算法在20次執(zhí)行中獲得的最高分類正確率、最佳適應(yīng)度函數(shù)值，以及此時(shí)對(duì)應(yīng)的特征子集。表中{}內(nèi)的數(shù)字即為所選特征在原始數(shù)據(jù)集中序號(hào)。為節(jié)約空間，若序號(hào)從x到y(tǒng)的特征均被選擇，則簡(jiǎn)寫為x～y。即{1～3}表示一個(gè)特征子集，其中包括序號(hào)為1、2、3的特征。

表7 HWOA算法獲得的最佳特征子集

3.4.5迭代初期解的質(zhì)量對(duì)特征選擇結(jié)果的影響 在算法初始，我們根據(jù)每個(gè)位置設(shè)置的隨機(jī)數(shù)隨機(jī)生成當(dāng)前個(gè)體的位置向量。因此算法在迭代初期具有隨機(jī)性，獲得的解也具有隨機(jī)性。表8展示對(duì)應(yīng)不同數(shù)據(jù)集，每個(gè)算法迭代早期的適應(yīng)度函數(shù)值(AvgF)。通過表8我們可以發(fā)現(xiàn)，BGWO算法在迭代初期的平均適應(yīng)度函數(shù)值較低，獲得的解質(zhì)量更高。HWOA、SCA、HGWOSCA和SCWOA 4個(gè)算法在迭代早期的平均適應(yīng)度值比較接近。但是從表4展示的結(jié)果我們發(fā)現(xiàn)，當(dāng)?shù)螖?shù)設(shè)置為100時(shí)，BGWO算法只在arrhythmia數(shù)據(jù)集上獲得最佳平均適應(yīng)度函數(shù)值，而HWOA算法則在9個(gè)數(shù)據(jù)集上獲得最佳值。這說明迭代初期解的質(zhì)量對(duì)特征選擇的最終結(jié)果無顯著影響，早期獲得質(zhì)量更優(yōu)的解并不意味著最終可以達(dá)到更好的特征選擇效果。

表8 每種特征選擇方法迭代初期的適應(yīng)度函數(shù)值

3.4.6顯著性檢驗(yàn) 為了更好地說明本文特征選擇方法性能的普遍優(yōu)越性，下面給出詳細(xì)的Friedman檢驗(yàn)和Nemenyi后續(xù)檢驗(yàn)結(jié)果(本文選用顯著性水平α=0.1)。首先，根據(jù)表2的平均分類正確率對(duì)實(shí)驗(yàn)涉及的7個(gè)算法在11個(gè)數(shù)據(jù)集上測(cè)得的分類精度高低進(jìn)行排序并賦值，具體結(jié)果如表9所示。

表9 不同數(shù)據(jù)集上算法性能排序結(jié)果

若算法性能相同則其平均序值相同，且第i個(gè)算法的平均序值ri服從自由度為(k-1)和(k-1)(N-1)的F分布。由表9數(shù)據(jù)可知各個(gè)算法的平均序值不同。由Friedman檢驗(yàn)可知，各類算法的性能顯著不同，需要進(jìn)行后續(xù)的Nemenyi檢驗(yàn)。利用Nemenyi檢驗(yàn)計(jì)算平均序值差別的臨界值域CD，其計(jì)算公式為

(1)

其中：k表示算法的個(gè)數(shù)；N表示數(shù)據(jù)集的個(gè)數(shù)；qa是一個(gè)由k值和顯著性α共同決定的參數(shù)。在本文中，k=7，N=11，查表可知，當(dāng)k=7時(shí)，qa=2.693(α=0.1)。代入公式(1)中，得到臨界值CD=2.481。

比較HWOA算法與其他對(duì)比算法間的平均序值差，結(jié)果可得，除與SCWOA和HGWOSCA算法的序值差小于CD外，其余均大于臨界值CD，故“兩個(gè)算法性能相同”的假設(shè)被拒絕。說明本文特征選擇方法性能顯著優(yōu)于其余算法，但與SCWOA算法和HGWOSCA算法相比優(yōu)勢(shì)并不明顯。

4 總結(jié)

本文提出了一種基于包裝模型的特征選擇算法——HWOA。我們將正弦余弦算法、鯨魚優(yōu)化算法和改進(jìn)后的灰狼優(yōu)化算法進(jìn)行混合，以利用不同算法的優(yōu)勢(shì)，提高算法的搜索能力，進(jìn)而獲得質(zhì)量更優(yōu)的解。同時(shí)引入邏輯映射和對(duì)數(shù)調(diào)整策略更新參數(shù)，以避免算法陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，該算法在一定程度上提高了分類性能。就適應(yīng)度函數(shù)值的比較而言，HWOA也獲得較好的性能。此外，對(duì)標(biāo)準(zhǔn)差結(jié)果的分析也證實(shí)了該算法具有較好的穩(wěn)定性。將來我們考慮使用不同的混沌映射來調(diào)整相關(guān)參數(shù)，并嘗試使用量子編碼。