基于自適應煙花算法和k近鄰算法的特征選擇算法

黃 欣 莫海淼 趙志剛

1(廣西農業職業技術學院信息與機電工程系 廣西 南寧 530007)2(合肥工業大學管理學院計算機網絡系統研究所 安徽 合肥 230009)3(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

特征選擇(Feature Selection，FS)也稱為屬性選擇，它是維數約簡中最常用的方法。特征選擇是指從原始數據的所有特征中選取特征真子集，并使用該特征真子集來對學習算法的模型進行訓練，它不僅能夠提高學習算法的學習性能，而且能夠有效地對原始數據集進行屬性約簡，并減少原始數據的冗余信息。

特征選擇本質就是一個優化問題，而群智能優化算法則是解決實際工程應用的優化問題的有效工具，這為群智能算法與特征選擇相結合提供了一個理論基礎[1]，并且吸引了大量學者的關注。張杰慧等[2]將自適應蟻群算法應用于特征選擇，然后使用SVM分類器對特征子集進行評價，并且將該特征選擇算法應用到計算機輔助孤立肺結節診斷系統，提高了系統的檢測和輔助診斷方面的性能。滕旭陽等[3]以信息熵作為評價準則，將粒子群算法和遺傳算法各自的優勢相融合，并根據特征選擇的特點將比特率交叉算法和信息交換策略引入到特征選擇算法中，使粒子群和遺傳算法種群協同演化，然后一起協作搜索特征子集。陳媛媛等[4]提出了改進蝙蝠算法，將其應用到光譜的相關特征選擇，并且可以快速地搜索到全局最優值，能有效地提高波長選擇的準確性和穩定性，被選擇的波長物理意義明確，采用選擇的特征波段建立的定量模型優于用全譜建立的模型。戚孝銘[5]提出了一種基于模擬退火機制的蜂群優化特征選擇算法，該特征選擇算法在蜂群算法的基礎上引入了模擬退火算法的思想，然后對原始數據的特征集進行搜索，使原始數據到達維數約簡的目的，并且提高文本分類的效果。路永和等[6]將基本煙花算法進行離散化，然后通過改進煙花算法的相關參數，再將離散化的煙花算法運用到文本分類問題的特征選擇中，最終在高維的文本分類問題中得到較好的實驗效果。文獻[7]將煙花算法和SVM相融合，提出了一種基于融合特征約簡(FFR)和煙花算法優化多類支持向量機(MSVM)的混合CCPS識別方法，其中，FFR算法主要由統計特征和形狀特征、特征融合和核主成分分析特征維數約簡三個子網絡組成，從而使搜索到的特征子集對分類結果更加有效，在MSVM分類器算法中，核心函數參數對混合CCPS的識別精度起著非常重要的作用。周丹等[8]提出了一種基于改進量子進化算法的特征選擇算法，它是以Fisher比和特征維度來構造新的評價函數，作為評價特征子集優劣的標準，并且能夠增加種群的多樣性，同時也提高了算法的性能。

1 自適應煙花算法

自適應煙花算法(Adaptive Fireworks Algorithm，AFWA)[9]是根據煙花在夜空中爆炸的自然現象來模擬種群在解空間的尋優過程而提出的一種改進煙花算法。自適應煙花算法的迭代過程和其他群智能算法大同小異，其主要迭代原理為：首先初始化煙花種群；然后計算爆炸強度、爆炸半徑、生成爆炸火花種群、生成高斯火花種群；根據“隨機-精英”選擇策略來選擇下一代煙花。通過以上步驟不斷地迭代，直到到達終止條件，則算法停止迭代。

2 特征選擇

2.1 特征子集產生

特征選擇的方法主要分為三種[12]，分別是窮舉法、隨機方法和啟發式。其中，窮舉法又分為完備集(完備集包括遍歷所有和廣度優先)和非完備集(非完備集包括分支定界和最好優先)。但是，雖然采用窮舉法來進行特征選擇能夠保證得到最優的特征子集，但是此方法的時間成本太高，會消耗大量的計算時間，因此在實際工程應用中一般不采取該方法。

隨機方法又包括完全概率和概率隨機這兩種方法。前者是完全按照隨機的方式來產生特征子集，這種方法存在很大的不確定性，往往不能夠得到最優特征子集；后者是按照一定的概率去選擇特征子集。

啟發式方法包括向前(向后)選擇、決策樹、群智能優化算法等。像決策樹、向前選擇和向后選擇這幾種方法，能夠尋找到在可接受范圍內的較優特征子集，但是不一定能夠尋找到最優子集；并且在尋找特征子集的過程中，可能在某幾個階段能夠較快收斂，但在其他階段可能收斂得很很慢，甚至會陷入局部最優。而群智能優化算法的方法主要是采取遺傳算法、模擬退火算法、粒子群算法和煙花算法等群智能優化算法對數據的特征集進行選擇特征子集。由于群智能優化算法具有較強的局部搜索能力，能夠在尋優的某個階段跳出局部最優解，并具有相對較快的收斂速度，在實際工程應用中往往能得到最優特征子集。

2.2 特征子集評價

特征子集的評估方法主要有基于距離的度量方法、基于信息的度量方法、基于依賴性或者相關性的度量方法、基于一致性的度量方法以及基于分類錯誤率的度量方法。特征子集的評價是通過評價函數來對特征子集進行評分，并以此作為衡量得到的特征子集的優劣。評價函數主要包括過濾式、封裝式、嵌入式[12-13]。

過濾式的評價函數是以特征子集的相關度作為評價準則，并通過搜索有序特征子集來直接計算特征子集的距離屬性(如歐式距離、chernoff概率距離、馬氏距離等)、信息屬性(如信息熵、條件熵、信息增益等)、獨立屬性(如相關性、相似性)、顯著檢驗(t-檢驗，F-檢驗，卡方檢驗)等[18]，最后根據統計檢驗法來對其特征子集的優劣進行評價。使用該方法對特征子集進行評價，不僅具有較好的泛化能力，而且比較穩健，計算資源消耗小，還可以從一定程度上避免過擬合的情況出現，但是不一定能夠得到最優的特征子集。

封裝式的評價函數是以學習器(如擬合器、分類器、聚類器)作為黑盒，然后把搜索到的特征子集放到黑盒進行預測，得到的預測效果越好，則說明該特征子集的有用程度越高，反之，則該特征子集的有用程度越低，即通過將搜索到的特征子集對學習器的后期性能的好壞來評價該特征子集的優劣[19]。該評價函數的優點是尋找到的特征子集對后期的學習更有幫助，并且理論上可以尋找到最優特征子集，但是消耗的計算資源較大，并且極易出現過擬合的現象。

在嵌入型特征選擇中，特征選擇算法是作為學習算法的部分嵌入其中的[20]。嵌入式在原則上能夠搜索到最優特征子集，它不僅具備過濾式在尋找特征子集的高效率、不容易出現過擬合現象，并且還具有封裝式的高精度。本文采用的是嵌入式的評價函數。

2.3 停止標準

特征子集經過評估之后，需要判斷是否滿足停止條件，若達到停止條件，特征選擇算法停止迭代，否則繼續尋找新的特征子集，直到達到停止條件為止。特征選算法的停止條件通常選擇以下情況之一或多個組合：

(1) 已經達到設定的特征屬性的數目；

(2) 達到特征選擇算法的最大評價次數；

(3) 增加或減少特征不能使子集的評價函數值有所提高；

(4) 尋找到了理論最優的特征子集；

(5) 達到了特征選擇算法設定的尋優精度。

2.4 結果驗證

特征選擇算法的結果驗證一般是將與特征子集相關的數據進行訓練和預測，根據訓練和預測的數據與原始的數據集進行比較，然后得到學習器(如分類器、聚類器、擬合器等)的準確度、訓練模型的時間成本、預測的時間成本、模型的復雜程度。但是，最重要的是學習器在預測數據時的準確度。

3 特征選擇算法設計

3.1 離散化編碼

在基于自適應煙花算法的特征選擇算法中，個體的位置xi=(xi1,xi2,…,xin)代表一個特征子集。在離散化的自適應煙花算法中，如果xi1等于1，則第1個特征被選中；如果xi1等于0，則表示第1個特征沒有被選中。假設xi=(0,1,0,1,1)，表示有5個特征集，0的個數共有2個，1的個數共有3個，則此時該個體選中了第2個特征、第4個特征和第5個特征，而第1個特征和第3個特征沒有被選中。由于自適應煙花算法一般解決的是連續性的問題，因此在解決離散化問題時需要將其進行離散化處理。位置xi的離散化處理表示為：

(1)

3.2 適應度函數設計

當選擇到的特征子集的特征總數為0時，則無法對數據進行分類。因為特征選擇的目的是為了將原始數據進行降維處理，但經過降維處理之后的特征子集的特征總數要大于0，這樣的特征子集才使得數據的分類有意義。因此，當出現特征子集的總數為0時，需要對這種情況進行處理。針對這樣的約束，需要使用外部懲罰函數對其進行懲罰處理。由于本文討論的是求解最小化的問題，因此同時將其轉化為最小化問題，具體表示為：

(2)

式中：sum(xi)表示個體i選中的特征子集的特征總數；pre表示分類精度。

分類精度pre的計算式表示為：

(3)

式中：TP為正確預測的測試樣本數量；FP為錯誤預測的測試樣本數量。

3.3 爆炸算子

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

(4)

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

為了避免爆炸火花數量過大，因此使用下式進行約束：

(5)

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

爆炸幅度(即爆炸半徑)是指煙花個體發生爆炸之后所發生的位移量。為了計算自適應爆炸半徑，需要選擇一個個體，其與最優個體，即下一代煙花之間的距離，作為下一次爆炸的半徑。選取的個體需要滿足兩個條件：條件1，適應度值比這一代的煙花要差；條件2，到最優個體的距離，是滿足條件1的個體中最短的。條件2表示為：

(6)

式中：si表示煙花生成的所有火花；s*表示所有火花和煙花中適應度值最好的；X表示煙花；d是某一種距離的度量(如無窮范數)。

核心煙花的爆炸半徑的計算式表示為：

(7)

非核心煙花的爆炸半徑的計算式表示為：

(8)

式中：Ai是第i個煙花個體的爆炸半徑；Amax是最大的爆炸半徑，Ymin是最優煙花個體的適應度值。由式(8)可知，適應度值越好的煙花個體，產生的爆炸半徑越小；反之，產生的爆炸半徑越大。

在煙花算法中，隨機選擇煙花個體的z個維度來進行位移操作，具體的位移操作如下：

(9)

式中：rand(0，Ai)是一個(0，Ai)范圍內服從均勻分布的隨機函數。

3.4 變異算子

(10)

式中：N(1，1)是服從均值為1、方差為1的高斯分布函數。

3.5 映射規則

在尋優的過程中，需要對越界的煙花個體進行如下的越界處理：

(11)

3.6 選擇策略

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

3.7 k最近鄰算法

k最近鄰算法(k-Nearest Neighbor，kNN)是機器學習領域中最常用的一種學習算法，它既是一種分類算法，也是一種回歸的非參數統計方法，并且被廣泛應用于分類問題。kNN算法的操作：首先，對原始數據進行預處理，并將處理好的數據分成訓練組和測試組；其次，設置合適的參數k；然后，在訓練組中選擇初始的最近鄰元組；計算初始近鄰元組和測試組之間的距離D，并計算訓練組和測試組之間的距離L，比較Dmax和L之間的大小，若L大于或者等于Dmax，則停止迭代，否則重復前面的步驟，直到達到終止條件為止。

3.8 十折交叉驗證

十折交叉驗證是一種用來測試算法準確性的測試方法。它的主要操作是：首先，把數據分成十份，其中九份是訓練數據，一份是測試數據，并輪流將訓練數據和測試數據進行實驗；然后記錄每次實驗輸出的準確率或者錯誤率，再把十次實驗的輸出結果的平均值作為對算法準確性的衡量標準。一般需要做N次十折交叉驗證的實驗，然后再將N次十折交叉的實驗結果的平均值作為最終評價算法準確性的標準。

3.9 算法流程

綜上所述，本文提出了基于自適應煙花算法和k近鄰算法的特征選擇算法(Feature Selection algorithm based on Adaptive Fireworks Algorithm and k-Nearest Neighbor algorithm，AFWA- kNN-FS)，該算法的主要流程如算法1所示。

算法1 AFWA- kNN-FS算法流程

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

輸出：煙花種群更新之后的位置、分類精度pre

Step 1 初始化煙花種群；

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

Step 3 根據式(4)計算爆炸強度；

Step 4 根據式(6)和式(7)計算核心煙花的爆炸半徑，按式(8)計算非核心煙花的爆炸半徑；

Step 5 煙花個體根據式(9)進行位移操作，并產生對應的爆炸火花，然后按式(11)對越界的爆炸火花個體進行越界處理，再按式(1)進行離散化處理；

Step 6 每一個煙花個體根據式(10)產生對應的高斯火花，然后按式(11)對越界的爆炸火花個體進行越界處理，再按式(1)進行離散化處理；

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

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

4 仿真實驗

4.1 選用的UCI數據集

本文的仿真實驗采用機器學習常用的UCI數據集來對AFWA- kNN-FS算法的分類性能進行測試，被選取數據集(來源https://archive.ics.uci.edu/ml/datasets.html)如表1所示。

表1 實驗選用的UCI數據集

續表1

4.2 實驗的參數設置

為了驗證AFWA- kNN-FS算法的性能，本文選用了表1的UCI數據集，并且與自適應煙花算法(AFWA)[9]、增強煙花算法(EFWA)[14]、煙花算法(FWA)[15]、蝙蝠算法(BA)[16]、標準粒子群算法(SPSO)[17]進行對比實驗，即使用AFWA算法、EFWA算法、FWA算法、BA算法和SPSO算法來進行搜索特征子集，并且將每種算法在搜索過程中搜到的特征子集的相關數據放到kNN分類器進行學習，最終輸出相關的分類精度進行比較。其中，五種算法的參數設置如表2所示。

表2 五種算法的相關參數

4.3 實驗結果分析

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

表3 五種算法的實驗數據(popsize=8，evalsMax=200)

續表3

表4 五種算法在DS1-DS10平均分類精度的排名

由表3可知，根據平均分類精度avg_acc這一欄的數據，對于數據集DS1-DS3、DS5-DS7以及DS9，AFWA- kNN-FS算法的平均分類精度均優于其他四種算法；對于DS4，AFWA- kNN-FS算法的平均分類精度劣于基于EFWA和kNN的特征選擇算法，卻優于其他三種算法；對于DS8，AFWA- kNN-FS算法的平均分類精度優于基于FWA和kNN的特征選擇算法，卻劣于其他三種算法；對于DS10，AFWA- kNN-FS算法的平均分類精度劣于基于EFWA和kNN的特征選擇算法、基于BA和kNN的特征選擇算法，卻優于其他兩種算法。

根據表3的最大分類精度max_acc這一欄的數據可知：對于DS1-DS3、DS5-DS7以及DS9，AFWA- kNN-FS算法的最大分類精度均優于其他四種算法，并且對DS1和DS2的分類精度(最小分類精度、最大分類精度和平均分類精度)遠遠優于其他四種算法。尤其在搜索數據集DS2的高維特征時，AFWA- kNN-FS算法的性能遠優于其他四種算法。

由表4可知，AFWA- kNN-FS算法的平均分類精度的總體排名優于其他四種算法。因此，在對表1的數據集進行搜索特征子集時，AFWA算法的總體性能優于其他四種算法。

為了進一步驗證基于AFWA算法和kNN算法的特征選擇算法的有效性，再選用Ionosphere、sonar和wdbc這三個數據集，并且與文獻[1]提出的基于自適應粒子群(APSO)的特征選擇算法進行對比實驗。其中，最大評價次數evalsMax設置為2 000次，AFWA算法的參數設置參照表2，APSO算法的參數設置參照文獻[1]。由表5得到的實驗結果可知，基于AFWA算法和kNN算法的特征選擇算法的總體性能優于基于文獻[1]的特征選擇算法。

表5 AFWA和APSO的平均分類精度

5 結 語

本文將自適應煙花算法進行離散化處理，使用k近鄰算法作為分類器，將特征子集引入目標函數，并使用懲罰因子來處理約束條件，提出了新的特征選擇算法，采用十折交叉驗證法來檢驗算法的分類效果。自適應煙花算法具有較好的全局搜索能力，避免在搜索特征子集的過程中過快地陷入局部最優解，并且特別適合于處理高維數據的維數約簡問題。仿真實驗結果表明，與增強煙花算法、煙花算法、蝙蝠算法、粒子群算法以及自適應粒子群算法相比，本文提出的算法具有相對更好的分類效果。