基于烏鴉搜索算法的新型特征選擇算法

　　摘要：基于元啟發(fā)式算法———烏鴉搜索算法(CrSA)，提出一種改進(jìn)的基于烏鴉搜索算法的特征選擇算法(IFSCrSA)，以解決目前特征選擇問題中存在的不足.通過與傳統(tǒng)的機(jī)器學(xué)習(xí)特征選擇算法和基于進(jìn)化計算的特征選擇算法進(jìn)行比較，結(jié)果表明，IFSCrSA能在數(shù)據(jù)集中選擇辨識度較強的特征，不僅大幅度降低了特征子集的規(guī)模，而且提高了分類準(zhǔn)確率.

　　關(guān)鍵詞：元啟發(fā)式算法,烏鴉搜索算法,特征選擇,分類準(zhǔn)確率

　　特征選擇是從原始數(shù)據(jù)集中選擇出最優(yōu)特征子集的過程，其通過降低數(shù)據(jù)集維度提高學(xué)習(xí)算法的性能，是機(jī)器學(xué)習(xí)過程中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟.使用特征選擇方法刪除數(shù)據(jù)集中不相關(guān)和冗余的特征，解決了數(shù)據(jù)集中特征數(shù)量龐大、特征之間相互作用復(fù)雜的問題[1]，從而降低了后續(xù)機(jī)器學(xué)習(xí)任務(wù)的難度.但隨著數(shù)據(jù)集規(guī)模的不斷增大，優(yōu)化效率也不斷降低，因此，設(shè)計并改進(jìn)特征選擇算法已成為特征選擇問題求解的關(guān)鍵.

　　為了解決該難題，一些研究者將元啟發(fā)式搜索應(yīng)用到特征選擇[2]尋找近似最優(yōu)解.元啟發(fā)式算法解決了大規(guī)模組合優(yōu)化問題，在一定程度上提高了特征選擇的優(yōu)化效率.根據(jù)元啟發(fā)式算法解的數(shù)量可將其分為基于單一解的算法和基于種群策略的算法[3].

　　其中基于單一解的算法在迭代過程中只有一個解，例如SFS(sequentialforwardselection)算法和SBS(sequentialbackwardselection)算法[4]，將其應(yīng)用到特征選擇時，對于解決中等維度的特征選擇問題具有簡單、快速的優(yōu)點，但容易陷入局部最優(yōu)，且由于算法具有單向性，對已選擇的特征不能更改，從而導(dǎo)致特征冗余.

　　為克服算法的缺點，Pudil等[5]提出了SFFS(sequentialforwardfloatingselection)算法和SBFS(sequentialbackwardfloatingselection)算法，這些算法可在局部搜索過程中回溯之前遍歷的特征，但每次漸進(jìn)搜索還是集中在與當(dāng)前最優(yōu)點最近的一些組合上，不利于全局搜索.另一類是基于種群策略的算法，在每輪迭代過程中均產(chǎn)生多個并行計算的個體，通過模擬生物種群之間的合作解決特征選擇問題.

　　例如，UFSACO算法[6]模擬了巢穴和食物來源之間真實螞蟻的行為，PSO(particleswarmoptimization)算法[7]模擬了鳥群或魚群的群體行為，ABC(artificialbeecolony)算法[8]是受蜜蜂群體行為的啟發(fā).AC-ABC算法[9]是ACO(antcolonyoptimization)算法和ABC算法的混合算法;FS-NEIR算法[10]結(jié)合了遺傳算法和局部搜索方法;HGAFS算法[11]是基于互信息的混合遺傳算法.

　　CrSA[12]是一種新的元啟發(fā)式算法，適用于求解連續(xù)搜索空間問題.通過分析和改進(jìn)CrSA，本文提出一種基于烏鴉搜索算法的特征選擇算法(IFSCrSA)來解決特征選擇問題.在IFSCrSA中，使用包含“0”和“1”的字符串初始化種群，為了在算法開始時提高算法的效率，加入了初始化學(xué)習(xí)策略，從而獲得更好的原始種群.引入Lévy飛行搜索策略平衡全局搜索與局部搜索.在烏鴉飛行尋找目標(biāo)過程中，使用Sigmoid轉(zhuǎn)換函數(shù)保持種群位置值始終為二進(jìn)制.同時還提出了基于貪婪策略的更新機(jī)制，以進(jìn)一步提高IFSCrSA的收斂速度.

　　1烏鴉搜索算法

　　烏鴉搜索算法是基于烏鴉覓食過程提出的一種智能算法.烏鴉是一種聰明且貪婪的鳥類[12]，它可以識別同伴的臉，用不同方式與同伴進(jìn)行交流，為了獲得更多的食物，它會偷偷地跟蹤其他烏鴉，發(fā)現(xiàn)它們存儲食物的地點，并偷取食物.如果烏鴉發(fā)現(xiàn)被其他烏鴉跟蹤，則該烏鴉將隨機(jī)飛行，從而迷惑跟蹤它的烏鴉.在優(yōu)化理論中，烏鴉是搜尋者，周圍環(huán)境是搜索空間，隨機(jī)存儲食物的位置是可行解.

　　在所有食物位置中，存放最多食物的位置被認(rèn)為是全局最優(yōu)解，目標(biāo)(適應(yīng)度)函數(shù)是食物量.模擬烏鴉的智能行為，烏鴉搜索算法試圖找到各種優(yōu)化問題的最優(yōu)解.假設(shè)烏鴉i隨機(jī)選擇一只烏鴉j進(jìn)行跟蹤，則在跟蹤過程中會出現(xiàn)以下兩種情況：1)烏鴉j未發(fā)現(xiàn)烏鴉i跟蹤，結(jié)果i到達(dá)j隱藏食物的位置偷取了食物;2)烏鴉j發(fā)現(xiàn)烏鴉i跟蹤，則其將隨機(jī)飛行，迷惑跟蹤烏鴉，使其食物避免被偷.

　　2基于烏鴉搜索算法的改進(jìn)特征選擇算法

　　2.1基于反向搜索策略的初始化方法

　　初始解的分布直接影響特征選擇算法的收斂速度和解的質(zhì)量.為了獲得更好的初始解，本文引入基于反向?qū)W習(xí)的概念[13]，即算法在初始化期間同時搜索解和與之對應(yīng)的相反解，選擇更好的解作為初始位置.通過使用反向搜索策略，可使算法在后續(xù)搜索過程中加速收斂[14].

　　基于反向搜索的初始化：設(shè)X=(x1，x2，…，xD)為D維空間中的一個點(即候選解)，其中xi∈{0，1｝，�衖∈{1，2，…，D｝.ˇX=(ˇx1，ˇx2，…，ˇxD)是X的相反解，其中ˇxi=1-xi.假設(shè)f(·)是一個適應(yīng)度函數(shù)，用于衡量候選解的適應(yīng)度.如果f(ˇX)≥f(X)，則可用點ˇX替換點X作為候選解;否則保持X作為候選解.

　　2.2基于Lévy飛行的搜索策略

　　在連續(xù)搜索空間中，如果烏鴉發(fā)現(xiàn)被其他烏鴉跟蹤，則將通過隨機(jī)飛行來保護(hù)食物.在IFSCrSA中，引入Lévy飛行[15]改變隨機(jī)算法，從而平衡全局搜索與局部搜索.假設(shè)有N只烏鴉在D維搜索空間中，任意一只烏鴉(烏鴉i)在任意時刻(迭代iter)可用包含“0”和“1”的字符串表示為Xi，iter=(xi，iter1，xi，iter2，…，xi，iterD)(i=1，2，…，N;iter=1，2，…，itermax).使用記憶位置(Mi，iter)表示烏鴉記憶中藏食物最多的位置.字符串中的“1”表示對應(yīng)特征被選中，“0”表示特征未被選中.在離散空間中，烏鴉的飛行過程可表示為：

　　2.4改進(jìn)算法設(shè)計

　　算法1IFSCrSA的偽代碼.算法開始：步驟1)根據(jù)反向搜索策略初始化烏鴉種群當(dāng)前位置和記憶位置;步驟2)whileiter

　　根據(jù)貪婪搜索策略判斷是否更新烏鴉i的記憶位置;步驟8)endfor步驟9)計算種群記憶位置的評估值并排序，評估值最大的記憶位置即為最優(yōu)特征子集;算法結(jié)束.在算法1中，首先根據(jù)反向搜索策略進(jìn)行種群初始化，將烏鴉種群的當(dāng)前位置(Xi)和記憶位置(Mi)離散化.

　　在每輪迭代過程中，當(dāng)烏鴉i選擇跟蹤目標(biāo)(烏鴉j)時使用貪婪搜索策略，以保證跟蹤的有效性.烏鴉i選定跟蹤目標(biāo)(烏鴉j)后，根據(jù)式(1)對自己當(dāng)前位置進(jìn)行更新.該過程引入Lévy飛行，從而平衡算法的全局搜索和局部搜索.然后使用Sigmoid轉(zhuǎn)換函數(shù)將更新后的位置轉(zhuǎn)換為僅包含“0”和“1”的字符串，保持算法的離散性.最后使用式(4)更新烏鴉i的記憶位置.算法1中步驟4)～7)確保每只烏鴉在一輪迭代后的記憶位置是保存食物最多的位置.在迭代結(jié)束后，通過評估函數(shù)計算烏鴉種群記憶位置的評估值.評估值最大的記憶位置即為最優(yōu)特征子集.

　　3實驗

　　實驗環(huán)境為Python3.6.1，使用公開的scikit-learn包，計算機(jī)為DELLIntelCorei7CPU(3.60GHz)，4GB內(nèi)存.實驗對比算法包括FSFOA[16]，UFSACO，SFS，SBS，SFFS，F(xiàn)S-NEIR，HGAFS，PSO和NSM[4].IFSCrSA使用KNN(K=1，3，5)、SVM和J48分類器指導(dǎo)學(xué)習(xí)過程.

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

　　將IFSCrSA在11個數(shù)據(jù)集上進(jìn)行實驗驗證，其中有10個數(shù)據(jù)集來自UCI機(jī)器學(xué)習(xí)庫(http：//www.ics.uci.edu/mlearn/MLRepository.html)，包括Heart-statlog，Vehicle，Cleveland，Dermatology，Ionosphere，Sonar，Glass，Wine，Arcene和Segmentation數(shù)據(jù)集，有1個數(shù)據(jù)集(SRBCT)來自微陣列數(shù)據(jù)集.數(shù)據(jù)集的特征數(shù)(#Feature)、實例數(shù)(#Instance)以及分類數(shù)(#Class)等信息.

　　3.2IFSCrSA實驗參數(shù)設(shè)置

　　IFSCrSA參數(shù)設(shè)置如下：在所有參數(shù)中，種群大小N、意識概率AP、飛行距離fl和最大迭代次數(shù)itermax與數(shù)據(jù)集無關(guān)，所以本文設(shè)置參數(shù)為N=50，AP=0.1，fl=2，itermax=10.

　　3.3評價函數(shù)

　　實驗中，采用分類準(zhǔn)確率(CA)[17]和維度縮減(DR)[18]作為IFSCrSA的評價函數(shù).分類準(zhǔn)確率是驗證特征選擇的有效方式[19]，計算公式為CA=N_CC/N_AS×100%，(5)其中：N_CC表示正確分類的實例數(shù);N_AS表示數(shù)據(jù)集的整體實例數(shù).維度縮減公式為DR=[1-(N_SF/N_AF)]×100%，(6)其中：N_SF表示選擇特征的數(shù)量;N_AF表示數(shù)據(jù)集上所有特征的數(shù)量[19].

　　3.4實驗結(jié)果分析

　　針對不同的數(shù)據(jù)集，IFSCrSA和其他對比算法的CA和DR結(jié)果.實驗所有數(shù)據(jù)均為經(jīng)過10次單獨運行結(jié)果求平均值后得到的.由于數(shù)據(jù)集采用不同的百分?jǐn)?shù)劃分訓(xùn)練和測試數(shù)據(jù)集時可能會影響算法運行的結(jié)果，特別是數(shù)據(jù)集中實例數(shù)很小的情況下，所以在本文實驗中，采用不同方法對數(shù)據(jù)集進(jìn)行劃分，包括10-折交叉驗證、2-折交叉驗證、70%用于訓(xùn)練集30%用于預(yù)測集(記為70%/30%).

　　IFSCrSA在數(shù)據(jù)集為Heart-statlog，Glass，Dermatology，Cleveland，Segmentation，Arcene和SRBCT的分類準(zhǔn)確率明顯高于其他算法，同時在維度縮減方面普遍有較大改善.數(shù)據(jù)集SRBCT和Arcene的特征數(shù)遠(yuǎn)超過實例數(shù)，通常情況下很難選擇合適的特征進(jìn)行預(yù)測，但I(xiàn)FSCrSA的分類準(zhǔn)確率仍高于其他算法.

　　IFSCrSA對于數(shù)據(jù)集Sonar，Wine和Ionosphere的分類準(zhǔn)確率雖然不總是最好，但維度縮減明顯，并且分類準(zhǔn)確率也較好.例如數(shù)據(jù)集Wine，在分類器是1NN和5NN時，IFSCrSA的分類準(zhǔn)確率略低于其他算法，但維度縮減則高于其他算法;在分類器是3NN和J48時，IFSCrSA的分類準(zhǔn)確率達(dá)100%，同時維度縮減也明顯高于其他對比算法.

　　分析表明，由于KNN算法在對數(shù)據(jù)進(jìn)行分類時只依據(jù)最鄰近的一個或者幾個特征的類別，所以可能對實驗結(jié)果產(chǎn)生一定影響.對于數(shù)據(jù)集Vehicle，IFSCrSA的分類準(zhǔn)確率不太理想，但維度縮減明顯高于其他算法.例如在分類器為SVM時，IFSCrSA的分類準(zhǔn)確率為63.59%，維度縮減為77.78%，HGAFS算法的分類準(zhǔn)確率為76.36%，但維度縮減僅為38.99%.

　　這可能是因為IFSCrSA刪除了過多的特征，使分類器在很小特征子集情形下，降低了分類準(zhǔn)確率所致.綜上所述，本文采用烏鴉搜索算法的思想，基于反向的初始學(xué)習(xí)策略、Lévy飛行和貪婪搜索策略，提出了使用IFSCrSA解決特征選擇問題，通過引入基于對立的初始化學(xué)習(xí)策略獲得了更好的原始種群，使用Lévy飛行搜索策略平衡全局搜索與局部搜索，使用基于貪婪搜索策略的更新機(jī)制進(jìn)一步提高了收斂速度.實驗結(jié)果表明，IFSCrSA性能優(yōu)于傳統(tǒng)算法.

　　參考文獻(xiàn)

　　[1]周志華.機(jī)器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016：247-261.(ZHOUZhihua.MachineLearning[M].Beijing：TsinghuaUniversityPress，2016：247-261.)

　　[2]YANGXin.Nature-InspiredMetaheuristicAlgorithms[M].[S.l.]：LuniverPress，2010：1-5.

　　[3]AFFENZELLERM，BEHAMA，KOFLERM，etal.MetaheuristicOptimization[C]//HagenbergReseach.Berlin：Springer，2009：103-155.

　　相關(guān)刊物推薦：《密碼學(xué)報》(雙月刊)創(chuàng)刊于2013年，是國家新聞出版廣電總局批準(zhǔn)創(chuàng)辦《密碼學(xué)報》。是中國密碼學(xué)會主辦的唯一學(xué)術(shù)期刊。

轉(zhuǎn)載請注明來自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/20325.html