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

所屬分類：電子論文閱讀次時間：2019-09-09 11:32

本文摘要：摘要：基于元啟發式算法烏鴉搜索算法(CrSA)，提出一種改進的基于烏鴉搜索算法的特征選擇算法(IFSCrSA)，以解決目前特征選擇問題中存在的不足.通過與傳統的機器學習特征選擇算法和基于進化計算的特征選擇算法進行比較，結果表明，IFSCrSA能在數據集中選擇辨識

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

　　關鍵詞：元啟發式算法,烏鴉搜索算法,特征選擇,分類準確率

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

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

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

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

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

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

　　1烏鴉搜索算法

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

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

　　2基于烏鴉搜索算法的改進特征選擇算法

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

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

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

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

　　在連續搜索空間中，如果烏鴉發現被其他烏鴉跟蹤，則將通過隨機飛行來保護食物.在IFSCrSA中，引入Lévy飛行[15]改變隨機算法，從而平衡全局搜索與局部搜索.假設有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”表示對應特征被選中，“0”表示特征未被選中.在離散空間中，烏鴉的飛行過程可表示為：

算法設計

　　2.4改進算法設計

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

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

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

　　3實驗

　　實驗環境為Python3.6.1，使用公開的scikit-learn包，計算機為DELLIntelCorei7CPU(3.60GHz)，4GB內存.實驗對比算法包括FSFOA[16]，UFSACO，SFS，SBS，SFFS，FS-NEIR，HGAFS，PSO和NSM[4].IFSCrSA使用KNN(K=1，3，5)、SVM和J48分類器指導學習過程.

　　3.1數據集

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

　　3.2IFSCrSA實驗參數設置

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

　　3.3評價函數

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

　　3.4實驗結果分析

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

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

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

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

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

　　參考文獻

　　[1]周志華.機器學習[M].北京：清華大學出版社，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.

　　相關刊物推薦：《密碼學報》(雙月刊)創刊于2013年，是國家新聞出版廣電總局批準創辦《密碼學報》。是中國密碼學會主辦的唯一學術期刊。