離散型增強煙花算法和kNN 在特征選擇中的研究

黃 欣，莫海淼，趙志剛，曾 敏

1.廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 信息與機電工程系，南寧 530007

2.合肥工業(yè)大學(xué) 管理學(xué)院 計算機網(wǎng)絡(luò)系統(tǒng)研究所，合肥 230009

3.廣西大學(xué) 計算機與電子信息學(xué)院，南寧 530004

1 引言

特征選擇（Feature Selection，F(xiàn)S）也稱為屬性選擇，是維數(shù)約簡中最常用的方法。它從原始數(shù)據(jù)的所有特征中選取特征真子集，以減少數(shù)據(jù)的冗余信息以及噪聲，同時降低數(shù)據(jù)的維度，并且使用該特征真子集來對學(xué)習(xí)算法的模型進行訓(xùn)練，從而提高學(xué)習(xí)算法的學(xué)習(xí)性能。

特征選擇本質(zhì)就是一個優(yōu)化問題，而群智能優(yōu)化算法則是解決實際工程應(yīng)用的優(yōu)化問題的有效工具，這給群智能算法與特征選擇相結(jié)合提供了一個理論基礎(chǔ)[1]，并且吸引了大量學(xué)者的關(guān)注。文獻[2]使用人工蜂群算法來進行特征選擇，提出的特征選擇算法在降低數(shù)據(jù)維度和提高分類準確率方面具有十分顯著的實驗效果。文獻[3]采用一種新的自適應(yīng)遺傳算法和新的特征集評價準則作為特征選擇的方法，有效地搜索到了最優(yōu)的特征子集，降低了數(shù)據(jù)的維數(shù)，提高了雷達分類的準確度。文獻[4]提出了一種基于多目標骨架粒子群優(yōu)化的特征選擇算法，并且在選擇特征數(shù)量和分類準確率之間取一種折中的策略，最終提高了分類準確率且減少了運行時間。文獻[5]從增加種群多樣性、提高尋優(yōu)能力的角度，提出了一種基于改進量子進化算法的特征選擇算法，該算法能夠搜索到重要的特征，得到不錯的實驗效果。文獻[6]為了提高基于群智能算法的特征選擇算法的穩(wěn)定性，提出了針對穩(wěn)定性的基于多目標蟻群優(yōu)化算法的特征選擇算法。文獻[7]提出了一種新的特征選擇算法，該算法引入了混沌模型來初始化種群，以增加種群的多樣性，并且使用骨干粒子群算法來搜索特征子集，同時使用粗糙集作為評價函數(shù)。

上述研究沒有將分類準確率、搜索到的特征子集以及算法種群的多樣性同時考慮進去。本文將搜索到的特征子集，采用嵌入式的方法來評價該特征子集，同時設(shè)計新的目標函數(shù)（即把搜到的特征子集與約束條件融合到目標函數(shù)設(shè)計中），并且在搜索過程中考慮種群的多樣性（通過自適應(yīng)調(diào)整爆炸火花的數(shù)量來平衡局部勘探能力和全局挖掘能力），以避免算法過快地陷入局部最優(yōu)解。

2 增強煙花算法的基本原理

增強煙花算法（Enhanced Fireworks Algorithm，EFWA）[8]是模擬煙花爆炸之后產(chǎn)生爆炸火花，爆炸火花隨機散落在煙花附近的過程，這個過程可以看作是粒子在解空間的尋優(yōu)過程。增強煙花算法的主要步驟包括：種群初始化，計算爆炸強度，計算爆炸半徑，煙花個體產(chǎn)生爆炸火花，煙花個體變異之后產(chǎn)生高斯火花，對個體進行越界處理，使用“精英-隨機選擇”策略從煙花、爆炸火花、高斯火花組成的候選集合中選取下一代煙花。通過以上步驟不斷地迭代，直到到達終止條件，算法停止迭代。

3 特征選擇的相關(guān)研究

特征選擇是指從特征集合S={s1,s2,…,sN}中選擇出一個特征真子集S′={s′1,s′2,…,s′n} ，其中n ＜＜N，S是原始數(shù)據(jù)的特征集合，S′是經(jīng)過某種準則選擇之后的特征真子集[9]。特征選擇由特征子集產(chǎn)生、子集評估、停止標準和結(jié)果驗證這四部分組成[10]。

3.1 特征子集產(chǎn)生

特征選擇的方法主要分為三種[11]，分別是窮舉法、隨機方法和啟發(fā)式方法。

使用窮舉法來產(chǎn)生特征子集，需要消耗大量的時間成本，因此往往不采取這種方法來進行特征選擇。

隨機方法又包括完全概率和概率隨機這兩種方法。前者是按照完全隨機的方法來產(chǎn)生特征子集，這種方法具有很大的不確定性，因此最后產(chǎn)生的特征子集的分類效果不好；后者是按照一定的概率來選擇特征子集，這種方法比前者的效果好一些。

啟發(fā)式方法，如向前（向后）選擇、決策樹、群智能優(yōu)化算法。向前（向后）選擇、決策樹這兩種方法在搜索特征子集的過程中，收斂速度較慢，可能會陷入局部最優(yōu)，因此往往不一定能夠找到全局最優(yōu)特征子集，最終導(dǎo)致分類效果不好。而群智能算法，比如增強煙花算法，具有較強的局部搜索能力和較好的全局勘探能力，能夠通過自適應(yīng)調(diào)整步長和爆炸強度來平衡局部搜索和全局搜索，往往能夠在搜索過程中跳出局部最優(yōu)解，且收斂速度快，最終找到較好的特征子集，并且能夠提升分類效果。

3.2 特征子集評價

特征子集的評價是通過評價函數(shù)來對特征子集進行評分，并以此衡量搜索到的特征子集的優(yōu)劣。評價函數(shù)主要包括過濾式（filter）、封裝式（wrapper）、嵌入式（embedded）[11-12]。

過濾式的評價函數(shù)是以特征子集的相關(guān)度作為評價準則，并通過搜索有序特征子集來直接計算特征子集的屬性（如距離屬性、信息屬性、獨立屬性、顯著檢驗等）[13]，最后通過統(tǒng)計學(xué)的方法來對搜索到的特征子集進行評價。雖然該方法的計算成本較小，并且泛化能力強，但是不一定能夠?qū)ふ业阶顑?yōu)的特征子集。

封裝式的評價函數(shù)是以學(xué)習(xí)器（如擬合器、分類器、聚類器）作為黑盒，然后把搜到特征子集的相關(guān)數(shù)據(jù)集放到該黑盒中進行預(yù)測，并且把預(yù)測效果的好壞作為評價搜索到的特征子集的標準，即預(yù)測效果越好，則該特征子集的有效程度越高；反之，該特征子集的有效程度越低[14]。這種方法雖然在理論上可以尋找到最優(yōu)特征子集，但是泛化能力較弱而導(dǎo)致出現(xiàn)過擬合現(xiàn)象，并且計算的時間成本比較高。

在使用嵌入式的評價函數(shù)作為評價特征子集的評價準則時，特征選擇算法是作為學(xué)習(xí)算法的部分嵌入其中的[12]。嵌入式的特征選擇方法，不僅計算成本比較小，并且具有較強的泛化能力，還具有封裝式方法所擁有的高精度的分類效果。因此，本文采用嵌入式的方法作為特征子集的評價準則。

3.3 停止標準

特征選擇算法終止迭代的條件一般有以下幾方面：

（1）達到預(yù)先設(shè)置的特征子集的總數(shù)量；

（2）達到算法的最大評價次數(shù)（評估次數(shù)）；

（3）在已選中的特征子集中增加或者減少若干個特征，對最終的分類效果沒有影響；

（4）尋找到了理論最優(yōu)的特征子集；

（5）達到了預(yù)先設(shè)置的分類準確率。

3.4 結(jié)果驗證

對特征子集的結(jié)果驗證，主要有兩種方法：（1）評價計算的時間成本；（2）評價分類準確率。前者主要是指模型訓(xùn)練的時間成本以及預(yù)測的時間成本，即把搜索到的特征子集的相關(guān)數(shù)據(jù)集放到學(xué)習(xí)器中進行訓(xùn)練，得到訓(xùn)練模型之后，再把測試集放到訓(xùn)練好的模型中進行預(yù)測，在整個訓(xùn)練和預(yù)測完成之后，再統(tǒng)計其時間成本。后者主要以學(xué)習(xí)器最終輸出的分類準確率作為結(jié)果驗證的標準，即分類準確率越高，則該實驗效果越好；反之，實驗效果越差。在實際應(yīng)用中，一般以后者作為結(jié)果驗證的主要手段。

4 特征選擇算法設(shè)計

4.1 離散化編碼

在基于增強煙花算法的特征選擇算法中，一個個體的位置Xi=(Xi1,Xi2,…,Xin)代表一個決策變量。在離散化的增強煙花算法中，如果Xi3等于1，則表示第3個特征被選中；如果Xi3等于0，則表示第3個特征沒有被選中。假設(shè)Xi=(0,1,1,0,1,0,0)，此時表示原始數(shù)據(jù)集有7 個特征，其中等于1 的特征有3 個，表示有3 個特征被選中作為特征子集，即被選中的特征為第2個特征（第2 列數(shù)據(jù)）、第3 個特征（第3 列數(shù)據(jù)）和第5 個特征（第5 列數(shù)據(jù)），再將被選中的第2、3 和5 列的數(shù)據(jù)放到學(xué)習(xí)器進行訓(xùn)練和預(yù)測；等于0的特征有4個，表示有4個特征沒有被選中，即第1、第4、第6和第7個特征沒有被選中，沒有被選中的第1、第4、第6和第7列的數(shù)據(jù)就不需要放到學(xué)習(xí)器進行訓(xùn)練和預(yù)測。由于原始的增強煙花算法解決的是連續(xù)性優(yōu)化問題，而特征選擇是離散化的純0-1 整型規(guī)劃問題，因此需要將該算法的個體所在的位置進行二進制的離散化處理。位置Xi的離散化處理表示為：

X′i是Xi經(jīng)過離散化處理之后的位置。

4.2 適應(yīng)度函數(shù)設(shè)計

當(dāng)選擇到的特征子集的特征總數(shù)為0時，被選中的數(shù)據(jù)列數(shù)為0，即沒有數(shù)據(jù)輸入到分類器中，此時的分類無意義。因為特征選擇的目的是將原始數(shù)據(jù)進行降維處理，但經(jīng)過降維處理之后的特征子集的特征總數(shù)要大于0，這樣的特征子集才使得數(shù)據(jù)的分類有意義。因此，當(dāng)出現(xiàn)特征子集的總數(shù)為0時，則需要對這種約束條件進行處理。針對此約束，需要使用外部懲罰函數(shù)（也稱作懲罰因子或者懲罰項）對其進行懲罰處理。本文討論的是求解最小化的問題，因此同時將其轉(zhuǎn)化為最小化問題，具體表示為：

其中，sum(Xi)表示個體i選中的特征子集的特征總數(shù)；acc表示分類準確率。

分類準確率acc的計算公式為：

其中，Num_correct_pre為正確預(yù)測的樣本數(shù)量；Total_num_pre為預(yù)測的總樣本數(shù)量。

4.3 爆炸算子

爆炸算子主要由爆炸強度、爆炸幅度（即爆炸半徑）、位移操作這三部分組成。其中，爆炸強度是指煙花個體發(fā)生爆炸之后所產(chǎn)生爆炸火花的數(shù)量，爆炸火花數(shù)量越多，則該煙花個體的爆炸強度越大；并且該煙花個體的適應(yīng)度值越好，則產(chǎn)生爆炸火花的數(shù)量越多，反之，產(chǎn)生爆炸火花的數(shù)量越少。爆炸強度的更新計算公式為：

其中，λi是第i個煙花個體所產(chǎn)生的爆炸火花的數(shù)量；M是一個用來限制爆炸火花數(shù)量的常量；Ymax是適應(yīng)度值最差的個體；f(Xi)是第i個煙花個體的適應(yīng)度值；ε是一個極小的常數(shù)，以避免分母為0。

為了避免爆炸火花數(shù)量過大，使用式（5）進行約束：

其中，round()為四舍五入的取整函數(shù)；a和b都是常數(shù)變量。

爆炸幅度（即爆炸半徑）是指煙花個體發(fā)生爆炸之后所發(fā)生的位移量。煙花的爆炸半徑的計算公式為：

其中，Ri是第i個煙花個體的爆炸半徑；Rmax是最大的爆炸半徑；Ymin是最優(yōu)煙花個體的適應(yīng)度值。由式（6）可知，適應(yīng)度值越好的煙花個體，產(chǎn)生的爆炸半徑越小；反之，產(chǎn)生的爆炸半徑越大。

增強煙花算法的最小半徑檢測策略如式（7）所示：

其中，Rik表示第i個煙花在第k維度上的爆炸半徑；Rmin,k是指在第k維度上的爆炸半徑最小的檢測閾值。在Rmin,k的選擇上，采取了線性遞減爆炸半徑檢測策略或者非線性遞減爆炸半徑檢測策略，具體操作方法如式（8）和式（9）所示：

其中，t為當(dāng)前的評價次數(shù)；evalsmax為最大評價次數(shù)；Rinit和Rfinal分別是算法在初始和終止時的爆炸半徑檢測值。

煙花發(fā)生位移之后產(chǎn)生爆炸火花。在增強煙花算法中，煙花的位移操作如式（10）所示：

其中，Xi是第i個煙花個體所在的位置；Si是第i個煙花發(fā)生位移之后的位置（即第i個爆炸火花所在的位置）；U(-1,1)是在[-1,1]范圍內(nèi)服從均勻分布的隨機數(shù)。

4.4 變異算子

增強煙花算法的高斯變異算子如式（11）所示：

其中，Xik是第i個煙花在第k維所在的位置；GXik是第i個高斯火花在第k維的位置；N(0,1)為服從均值為0和方差為1的高斯分布函數(shù)；CFk為核心煙花（全局最優(yōu)煙花個體）在第k維的位置。

4.5 越界處理

按式（12）來對越界的個體進行越界處理：

4.6 選擇策略

在增強煙花算法中，采用“隨機-精英”選擇策略來選取下一代的煙花，即從煙花、爆炸火花、高斯火花組成的候選集中選擇適應(yīng)度值最好的個體作為下一代的其中一個煙花，下一代的其他煙花則隨機進行選取。

4.7 k 最近鄰算法

k最近鄰（k-Nearest Neighbor，kNN）算法是一種常用的分類方法，由于易于實現(xiàn)、易于理解、適用于多分類問題而被廣泛應(yīng)用于機器學(xué)習(xí)領(lǐng)域。kNN 的核心思想是某個樣本的特性可以使用距離它最近的k個樣本來代替。

4.8 十折交叉驗證

十折交叉驗證（10-fold crossvalidation）是一種用來測試算法準確性的測試方法。它的主要流程是：先把原始數(shù)據(jù)分成10 份，第i(i=1,2,…,10)份數(shù)據(jù)作為測試數(shù)據(jù)，剩余其他9份作為訓(xùn)練數(shù)據(jù)。把這10次實驗輸出的結(jié)果（準確率或者錯誤率）記錄下來，然后求10 次實驗輸出的結(jié)果的平均值，其平均值作為衡量算法對數(shù)據(jù)分類的準確性。一般來說，需要按照上述步驟做N次獨立重復(fù)的“十折交叉驗證”實驗，并求N次實驗的平均值來衡量算法的準確性。

4.9 算法流程

綜上所述，本文提出了基于二進制的離散型增強煙花算法和kNN 的特征選擇算法（Feature Selection algorithm based on binary discrete Enhanced Fireworks Algorithm andk-Nearest Neighbor algorithm，EFWA-kNN-FS），該算法的主要流程如算法1所示。

算法1 EFWA-kNN-FS算法

輸入：煙花種群的位置、經(jīng)過十折交叉驗證法處理之后的數(shù)據(jù)的全部特征集。

輸出：煙花種群更新之后的位置、分類準確率acc。

步驟1 初始化煙花種群；

步驟2 把煙花個體搜索到的特征子集的相關(guān)數(shù)據(jù)放到kNN 分類器，然后按式（2）來計算該煙花個體的適應(yīng)度值；

步驟3 根據(jù)式（4）、式（5）計算爆炸強度；

步驟4 根據(jù)式（6）、式（7）、式（9）計算煙花的爆炸半徑；

步驟5 煙花個體根據(jù)式（10）進行位移操作，并產(chǎn)生對應(yīng)的爆炸火花；然后按式（12）對越界的爆炸火花個體進行越界處理，再按式（1）進行離散化處理；

步驟6 根據(jù)式（11）產(chǎn)生高斯火花，然后按式（12）對其進行越界處理，再按式（1）進行離散化處理；

步驟7 采用“隨機-精英”選擇策略，從候選集中選取下一代煙花；

步驟8 重復(fù)步驟2～步驟7，若達到終止條件，則停止迭代，并輸出結(jié)果。

5 仿真實驗

5.1 選用的UCI數(shù)據(jù)集

本文選擇在機器學(xué)習(xí)領(lǐng)域中常用的UCI 數(shù)據(jù)集作為測試算法性能的數(shù)據(jù)集（為了便于進行對比實驗，所選擇的數(shù)據(jù)集均為平衡數(shù)據(jù)集，且數(shù)據(jù)集的屬性均為數(shù)值型）。UCI數(shù)據(jù)集來源于https：//archive.ics.uci.edu/ml/datasets.php，被選用的數(shù)據(jù)集如表1所示。

表1 實驗選用的UCI數(shù)據(jù)集

5.2 實驗的參數(shù)設(shè)置

為了驗證EFWA-kNN-FS 算法的性能，本文選用了表1 的UCI 數(shù)據(jù)集，并且與引導(dǎo)型煙花算法（GuidedFireworks Algorithm，GFWA）[15]、煙花算法（Fireworks Algorithm，F(xiàn)WA）[16]、蝙蝠算法（Bat Algorithm，BA）[17]、烏鴉算法（Crow Search Algorithm，CSA）[18]進行對比實驗。使用GFWA、FWA、BA和CSA來搜索特征子集，并且將每種算法搜索到的特征子集的相關(guān)數(shù)據(jù)放到kNN分類器進行學(xué)習(xí)，對最終輸出的相關(guān)分類準確率進行比較。其中，五種算法的參數(shù)設(shè)置如表2所示。

表2 五種算法的相關(guān)參數(shù)

5.3 實驗結(jié)果分析

為了更加科學(xué)地評價算法的性能，本文將五種算法的種群大小popsize均設(shè)置為8，最大評價次數(shù)evalsmax均設(shè)置為200 次，其他的參數(shù)設(shè)置參照表2，并且使用“十折交叉驗證”的方法做了20 次獨立重復(fù)實驗，實驗結(jié)果如表3所示。其中，min_acc、max_acc、avg_acc、std_acc分別是20 次獨立重復(fù)實驗的最小分類準確率、最大分類準確率、平均分類準確率、標準偏差。表4 是五種算法根據(jù)avg_acc平均分類準確率這一欄的排名統(tǒng)計出來的結(jié)果。表5是根據(jù)std_acc這一欄的排名統(tǒng)計出來的結(jié)果。

由表3 可知，根據(jù)平均分類準確率avg_acc這一欄的數(shù)據(jù)，對于DS1、DS8和DS9，EFWA-kNN-FS算法的平均分類準確率劣于BA，卻優(yōu)于其他三種算法；對于DS2，EFWA-kNN-FS 算法和 BA 的平均分類準確率相同，且優(yōu)于其他三種算法；對于數(shù)據(jù)集DS3～DS5、DS7和DS10，EFWA-kNN-FS算法的平均分類準確率均優(yōu)于其他四種算法；對于DS6，EFWA-kNN-FS 算法的平均分類準確率劣于BA 和GFWA，但是優(yōu)于其他兩種算法。根據(jù)表4可知，EFWA-kNN-FS算法在平均分類準確率方面的總體排名優(yōu)于其他四種算法。

表3 五種算法的分類準確率(evalsmax=200)%

標準偏差的大小反映了算法魯棒性的好壞，即標準偏差越小，該算法的魯棒性越好；反之，該算法的魯棒性越差。根據(jù)表4 的std_acc這一欄的數(shù)據(jù)可知，對于數(shù)據(jù)集 DS1，EFWA-kNN-FS 算法的魯棒性優(yōu)于 CSA，卻劣于其他三種算法；對于數(shù)據(jù)集 DS2、DS5、DS7、DS8和DS10，EFWA-kNN -FS 算法的魯棒性優(yōu)于其他四種算法；對于數(shù)據(jù)集DS3，EFWA-kNN-FS 算法的魯棒性劣于BA，卻優(yōu)于其他三種算法；對于數(shù)據(jù)集DS4，EFWA-kNN-FS 算法的魯棒性劣于BA 和CSA，卻優(yōu)于其他兩種算法；對于數(shù)據(jù)集DS6，EFWA-kNN-FS 算法的魯棒性優(yōu)于GFWA，卻劣于其他三種算法；對于數(shù)據(jù)集DS9，EFWA-kNN-FS 算法的魯棒性劣于其他四種算法。根據(jù)表5可知，EFWA-kNN-FS算法的總體魯棒性優(yōu)于其他四種算法。

表4 五種算法在DS1～DS10平均分類準確率的排名

表5 五種算法的魯棒性排名

綜上可知，在對表1 的數(shù)據(jù)集進行特征子集搜索時，EFWA算法的總體性能優(yōu)于其他四種算法。

為了進一步驗證本文算法的有效性，再選用DS3、DS7和DS9這三個數(shù)據(jù)集，然后與文獻[1]提出的基于自適應(yīng)粒子群算法（Adaptive Particle Swarm Optimization，APSO）的特征選擇算法做對比實驗。設(shè)置EFWA 算法的最大評價次數(shù)均為200次，其他參數(shù)設(shè)置參考表2；而APSO參數(shù)設(shè)置參考文獻[1]（該文獻將最大評價次數(shù)設(shè)置為2 000 次）。增強煙花算法和文獻[1]的APSO 算法的對比實驗結(jié)果如表6 所示。由表6 可知，對于DS3和DS7數(shù)據(jù)集，EFWA-kNN-FS 算法的平均分類準確率優(yōu)于APSO算法，并且使用的評價次數(shù)少于APSO算法；對于DS9數(shù)據(jù)集，EFWA-kNN -FS 算法的分類準確率比APSO的差。綜上，EFWA-kNN-FS算法的總體性能優(yōu)于APSO算法。

表6 AFWA和APSO的平均分類準確率%

6 結(jié)束語

本文通過將增強煙花算法進行二進制的離散化處理，然后使用離散化的增強煙花算法來搜索特征子集，將搜到的特征子集放到kNN 分類器中進行訓(xùn)練和預(yù)測，不僅將搜到的特征子集和約束條件融入到新的目標函數(shù)中，而且采用十折交叉驗證的方法進行了多次的獨立重復(fù)實驗作為評價分類效果的準則。增強煙花算法通過自動調(diào)整爆炸強度來平衡局部搜索能力和全局勘探能力，從而避免種群過快地陷入局部最優(yōu)解，并且擁有較快的收斂速度。仿真實驗的結(jié)果表明，本文提出的特征選擇算法的總體性能優(yōu)于引導(dǎo)型煙花算法、煙花算法、粒子群算法、蝙蝠算法以及文獻[1]的自適應(yīng)粒子群算法。