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

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

1.廣西農業職業技術學院 信息與機電工程系，南寧 530007

2.合肥工業大學 管理學院 計算機網絡系統研究所，合肥 230009

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

1 引言

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

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

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

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

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

3 特征選擇的相關研究

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

3.1 特征子集產生

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

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

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

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

3.2 特征子集評價

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

過濾式的評價函數是以特征子集的相關度作為評價準則，并通過搜索有序特征子集來直接計算特征子集的屬性（如距離屬性、信息屬性、獨立屬性、顯著檢驗等）[13]，最后通過統計學的方法來對搜索到的特征子集進行評價。雖然該方法的計算成本較小，并且泛化能力強，但是不一定能夠尋找到最優的特征子集。

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

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

3.3 停止標準

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

（1）達到預先設置的特征子集的總數量；

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

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

（4）尋找到了理論最優的特征子集；

（5）達到了預先設置的分類準確率。

3.4 結果驗證

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

4 特征選擇算法設計

4.1 離散化編碼

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

X′i是Xi經過離散化處理之后的位置。

4.2 適應度函數設計

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

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

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

其中，Num_correct_pre為正確預測的樣本數量；Total_num_pre為預測的總樣本數量。

4.3 爆炸算子

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

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

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

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

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

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

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

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

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

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

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

4.4 變異算子

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

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

4.5 越界處理

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

4.6 選擇策略

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

4.7 k 最近鄰算法

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

4.8 十折交叉驗證

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

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

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

步驟1 初始化煙花種群；

步驟2 把煙花個體搜索到的特征子集的相關數據放到kNN 分類器，然后按式（2）來計算該煙花個體的適應度值；

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

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

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

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

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

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

5 仿真實驗

5.1 選用的UCI數據集

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

表1 實驗選用的UCI數據集

5.2 實驗的參數設置

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

表2 五種算法的相關參數

5.3 實驗結果分析

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

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

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

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

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

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

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

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

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

6 結束語

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