一種離散反向學習的螢火蟲特征選擇算法

徐華麗，郁書好，左旭坤，陳家俊

(皖西學院 電子與信息工程學院，安徽 六安 237012)

特征選擇(feature selection)作為一種數(shù)據(jù)預處理手段近年來廣泛應用到各行各業(yè)中，例如社會網(wǎng)絡、入侵檢測、生物信息、圖像分析和自然語言處理等。在大規(guī)模數(shù)據(jù)集中，通常存在著大量冗余和無關特征，特征選擇的目的在于去掉初始集合中的冗余特征，選擇和分類目標相關的特征。特征選擇是通過一個特定的評估函數(shù)來評價特征或特征組合，進而從原始特征集合中選擇出一個維度更低的特征子集[1]。該子集能夠在數(shù)據(jù)挖掘和機器學習任務中提供與原集合近似或更好的表現(xiàn)。因此，為了能夠從大量高維小樣本的數(shù)據(jù)中獲取有用的信息，利用特征選擇對數(shù)據(jù)降維成為了處理這類問題的一個有效方法。

目前，關于特征選擇的算法研究依據(jù)特征子集性能評價準則可分為3類：過濾法，封裝法和嵌入法[2]。過濾法采用的評價標準與后續(xù)的學習算法無關，依據(jù)特征對分類貢獻的大小定義其重要程度，選擇重要的特征構成特征子集，目前用得最多的過濾法是相關測量法、類間和類內距離測量法、信息熵法、t檢驗以及ReliefF等。過濾法通常能夠很快地排除一部分非關鍵性的噪聲特征，縮小優(yōu)化特征子集的搜索范圍，但是并不能保證選擇出一個規(guī)模較小的優(yōu)化特征子集。封裝法的算法與分類器相關聯(lián)，依據(jù)不同的特征子集的分類性能評價特征子集中的特征，計算復雜度相對較高，在處理大規(guī)模數(shù)據(jù)時能從初始特征集合獲取某個特征子集。嵌入法是指特征選擇算法嵌入到分類算法中，特征選擇和訓練同時進行，不需要將數(shù)據(jù)集分為訓練集和測試集。封裝法相比過濾法，其所選的優(yōu)化特征子集的規(guī)模相對要小一些。因此，該方法是特征選擇研究領域的熱點。特征選擇問題本質上是NP的組合優(yōu)化問題，可采用非全局最優(yōu)目標搜索方法求解這類問題，因此近年來出現(xiàn)了一些用于解決這類問題的元啟發(fā)式方法。如文獻[3]提出了用決策樹來進行特征選擇的方法，用遺傳算法來尋找使得決策樹分類錯誤率最小的一組特征子集。文獻[4]使用正態(tài)極大似然模型來進行特征選擇和分類，得出了較好的實驗結果。文獻[5]用遺傳算法結合人工神經(jīng)網(wǎng)絡得出了較好的實驗結果，文獻[6]利用支持向量機（SVM）作為分類器，所選擇的優(yōu)化特征子集的分類準確率比神經(jīng)網(wǎng)絡、決策樹、k近鄰分類算法的有了更進一步的提高。文獻[7]提出了一種混合遺傳算法的特征選擇算法、文獻[8]提出了一種蟻群優(yōu)化算法優(yōu)化支持向量機的核參數(shù)的特征選擇算法、文獻[9-10]將粒子群算法優(yōu)化運用到特征選擇算法中取得了很好的分類效果。螢火蟲算法(firefly algorithm，F(xiàn)A)[11]由劍橋大學Yang于2009年提出，作為最新的群智能優(yōu)化算法之一，該算法已經(jīng)被證明比PSO（particle swarm optimization）和GA（genetic algorithm）具有更好的收斂速度和尋優(yōu)精度，且易于工程實現(xiàn)，目前已被成功應用到多種領域[12-15]。因此本文使用螢火蟲算法進行特征選擇。

特征選擇的實質是離散組合優(yōu)化問題，本文提出了一種基于近鄰信息的離散反向學習螢火蟲特征選擇算法（neighborhood information and discrete opposition firefly algorithm for feature selection，NOFAFS）。主要貢獻如下：（?。┽槍ξ灮鹣x算法對初始解質量的依賴，在算法初始化階段，引入二進制編碼和反向學習產生初始解，增加獲得最優(yōu)解的機會；（ⅱ）為了避免在離散化處理數(shù)據(jù)時丟失了一些重要信息，避免算法種群多樣性的丟失，在搜索過程中運用反向學習策略，使其跳出局部最優(yōu)，增加粒子的多樣性，提高螢火蟲找到最優(yōu)值的概率；（ⅲ）將該特征選擇算法獲得的特征子集應用到UCI標準數(shù)據(jù)集中進行測試，通過實驗驗證了所提方法的有效性。

1 相關工作

1.1 螢火蟲算法描述

在基本螢火蟲優(yōu)化算法中，初始時刻，螢火蟲隨機分布在整個搜索空間，螢火蟲通過發(fā)出亮光來吸引其他螢火蟲個體，從而達到移動。其移動過程遵循三個基本假設：

（H1）所有螢火蟲不區(qū)分性別，會被吸引到熒光亮度更高的螢火蟲那邊去；

（H2）螢火蟲的吸引力和亮度成正比，其中，低亮度的螢火蟲會被高亮度的螢火蟲吸引并向其移動，亮度是隨著距離的增加而減少；

（H3）螢火蟲的亮度由其適應值函數(shù)決定。

在基本螢火蟲優(yōu)化算法中，亮度和吸引度是其重要的兩個參數(shù)，亮度體現(xiàn)了螢火蟲所處位置的優(yōu)劣并決定了其移動的方向，吸引度決定了螢火蟲移動的距離，亮度和吸引度不斷變化更新，從而實現(xiàn)目標優(yōu)化。

螢火蟲i對螢火蟲j的相對熒光亮度為

其中，I0為螢火蟲的最大熒光亮度，與目標函數(shù)值相關，目標函數(shù)值越大，亮度越高，γ為光吸收系數(shù)，熒光亮度會隨著距離的增加逐漸變弱，rij為螢火蟲i和j間歐氏距離。

螢火蟲的吸引度為

其中，β0為rij=0時的吸引度。

螢火蟲i被吸引向螢火蟲j移動的位置更新公式如下式:

其中，xi是螢火蟲的當前位置，α∈[0,1]為隨機步長，rand∈[0,1]表示隨機數(shù)。

1.2 反向學習

反向學習策略是2005年提出的智能學習策略，學者們已經(jīng)證明該策略是一種有效的提高各種優(yōu)化問題效率的方法[16]。反向學習策略主要是當檢測到種群歷史最優(yōu)位置在一定迭代次數(shù)內時未更新，算法陷入停滯，或將當前歷史最差位置螢火蟲產生反向解，并將反向位置螢火蟲與當前螢火蟲一起參與競爭，優(yōu)秀螢火蟲個體進入下一代。

設存在實數(shù)x∈[m,n]，則x的反向數(shù)定義為：

設在R上存在d維空間上點x=（x1，x2,…xd)，且xi∈[mi,nj]，i∈{1,2,…d}，則其反向數(shù)可定義為：

如果f()≥f(x)，則用反向解代替初始解x。

2 基于離散反向學習的螢火蟲特征選擇算法

2.1 離散螢火蟲編碼方案

針對特征選擇問題，本文采用離散型螢火蟲優(yōu)化算法，其解的具體構造如下：

初始化一個概率向量矩陣X=（xi1,xi2,...,xid），螢火蟲個體i在第d維的位置用xid表示，i表示螢火蟲群體的規(guī)模，d表示一個數(shù)據(jù)集所包含的特征屬性的個數(shù)，xid在解向量中所處的位置與數(shù)據(jù)集中的序號一一對應，xid∈[0,1]表示數(shù)據(jù)集中第d個屬性，為特征被選中的概率，對于任一個螢火蟲個體xi，其編碼方案由下式?jīng)Q定：

zij=1表示第j個特征被選中到特征子集zij中。特征子集zij的值通常只能取0或1，0表示該屬性未被選中，1表示該屬性被選中。例如，一個可行解表示的一個候選子集如：x=(0.7,0.3,0.6,0.8,0.4,0.2,0.3,0.9)，當rand=0.5時，表示原始數(shù)據(jù)集中的序號為第1,3,4,8的屬性被選擇，構成一個候選子集。因此，特征選擇問題即轉變?yōu)殡x散變量的優(yōu)化問題。

2.2 反向學習的初始化策略

螢火蟲的初始解構造策略直接影響到算法的收斂速度和解的質量，在經(jīng)典的螢火蟲優(yōu)化算法中，初始解一般都是隨機生成或者混沌產生的，本文采用基于反向學習的初始構造策略，隨機初始一個解，并應用式（4）產生反向解，同時搜索當前解和反向解，選擇兩者中適應值較好的解作為初始解，從而提高初始解的質量。

2.3 適應值函數(shù)的構造

特征選擇的目的在于所選擇特征子集具有很強的分類能力，因此，在特征選擇時，考慮特征子集形成的分類器的分類精度，是非常有必要的。為了計算螢火蟲對應的特征子集形成的分類器的精度，本文采用留一交叉驗證法，即將含有K個數(shù)據(jù)的數(shù)據(jù)集，以每個數(shù)據(jù)分別作為一次驗證集，其他K-1個數(shù)據(jù)作為訓練集。假設以第i個數(shù)據(jù)為驗證集，則將第i個數(shù)據(jù)以外的其他K-1個數(shù)據(jù)作為訓練集，對螢火蟲所對應的特征子集形成的分類器訓練，從而得到一個分類模型，然后利用第i個數(shù)據(jù)測試分類模型的性能，如果分類模型預測出的類別正確，則Si=1，否則，Si=0?？蓪⒔Y果統(tǒng)一表示為Si(x)，則對于K個數(shù)據(jù)，螢火蟲x對應的特征子集形成的分類器精度可表示為：

2.4 反向學習機制

群智能算法的一個關鍵問題是如何在保持種群多樣性和提高算法收斂速度之間尋求一種平衡。因為隨著算法的不斷迭代，算法容易出現(xiàn)早熟收斂現(xiàn)象，因此提出了NOFAFS，即在算法搜索過程中，以加強種群歷史最優(yōu)個體的局部開采能力為前提，利用多個粒子的反向學習能力，保持種群多樣性。具體策略如下：（?。┊敊z測到種群最優(yōu)位置在一定的迭代步數(shù)內沒有更新時，則算法可能陷入停滯，可將當前種群中10%的螢火蟲進行反向學習，其他90%的學習方式不變；（ⅱ）為了能夠使這些最差螢火蟲能夠快速逃離當前局部最優(yōu)，并且讓它們盡可能地不同，應選擇兩兩之間歐式距離大于預設的一個排異半徑r的螢火蟲個體。

2.5 算法步驟

算法步驟如圖1所示。

3 實驗與結果分析

3.1 實驗環(huán)境及參數(shù)設置

本文代碼工具采用Matlab2014a，編譯運行的機器配置如下：64位windows 10操作系統(tǒng)，CPU 2.3 GHz i5-4200U、內存8 GB。本文實驗中參數(shù)設置如下：α=0.2,β0=1,γ=1螢火蟲個數(shù)初始化為25。

3.2 實驗結果分析

為驗證該算法的有效性，采用UCI數(shù)據(jù)集（http://archive.ics.uci.edu/ml/）中的4個不同數(shù)據(jù)集（見表1）進行測試，并應用兩種不同方法進行對比實驗，用于比較基本螢火蟲算法進行特征選擇（firefly algorithm for feature selection，F(xiàn)AFS）和本文算法NOFAFS在分類方面的效果，分別用來測試特征選擇后的特征數(shù)量和由選擇出的特征子集進行分類得出的分類精度。

表2給出了上述4個不同數(shù)據(jù)集分別應用兩種不同的算法后選擇的特征子集的個數(shù)，結果顯示不同算法得到的特征子集的數(shù)量是不同的，表3給出了兩種算法所選擇的特征子集是不同的，以Heart disease數(shù)據(jù)集為例，F(xiàn)AFS選出的特征子集為 13,12,8,3,10,7,9,11,1,4,2,5,6，而 NOFAFS選出的特征子集為12,3,11,13,7,4,9。

在實驗中，為比較特征選擇后的特征子集的分類能力，選取LSVM、CART兩種不同分類器并利用十字交叉驗證的方式評價特征子集的優(yōu)劣，其中支持向量機使用線性支持向量機。

圖1 NOFAFS算法

表1 實驗數(shù)據(jù)描述及不同算法選擇的特征數(shù)量

表2 FAFS和NOFAFS的所選擇特征子集比較

為了進一步說明本文算法的有效性，同時選取了經(jīng)典PSO算法進行特征選擇(PSOFS)比較實驗。表3分別給出了4種數(shù)據(jù)集在不同的分類器下的評價各算法的分類精度。從表中可以看出，大多數(shù)情況下，在經(jīng)過特征選擇后，算法能維持或增加了分類精確性。例如數(shù)據(jù)集Wine共有13個特征，選擇FAFS算法，特征子集數(shù)量減少2，分類器分類精度保持不變；利用NOFAFS后，利用LSVM算法分類器特征子集數(shù)量減少為10，分類精度較原始特征集有0.66的提高，較PSOFS提升了1.1。而數(shù)據(jù)集WPBC在原始特征數(shù)為33的情況下，經(jīng)特征選擇后特征子集數(shù)量減為2的條件下，仍然能保持較高分類精度，僅減少了1.41個百分點。而在利用CART分類器的情況下，特征子集數(shù)量大大減少的同時分類精確性反而有所提高。例如對于lonosphere數(shù)據(jù)集，選用FAFS特征子集數(shù)量由22減少至9，而分類精度達到98.00，比原始數(shù)據(jù)集獲得的精度91.17有了6.83的提升。從表中可見，選用NOFAFS特征子集數(shù)量為10，比FAFS多1，而分類精度為98.58，相比FAFS有了0.58個百分點的提升，相比PSOFS有了2.0的提升。由此說明，并不是特征子集數(shù)量越多分類精確性越高，刪除冗余或不相關特征有時反而更能提高分類算法的分類精確性。綜合以上分析，可以看出，NOFAFS較FAFS算法在分類精確性和特征數(shù)量上都有了明顯提升，較PSOFS也有了明顯提升，說明本文應用反向學習策略初始化和針對早熟收斂現(xiàn)象的反向學習策略，能夠引導螢火蟲快速逃離局部最優(yōu)，算法性能獲得明顯提升。

表3 不同特征選擇算法在不同分類器下的分類精度比較（LSVM算法和CART分類算法）

4 小結

大數(shù)據(jù)呈現(xiàn)出數(shù)據(jù)量巨大、數(shù)據(jù)維度高、價值密度低、增長速度快等特點，特征選擇在降低數(shù)據(jù)維度、在數(shù)據(jù)分類中起著至關重要的作用。本文提出了一種新的離散反向學習的螢火蟲優(yōu)化特征選擇算法，利用反向學習機制使得螢火蟲能快速找到最優(yōu)特征子集。實驗結果表明，本文所用方法簡單有效，在UCI數(shù)據(jù)集上測試，能夠獲得較好的分類精確度。對于實際應用過程中，如何提升算法的執(zhí)行效率是下一步需要仔細研究的問題。

參考文獻：

[1]董紅斌，騰旭陽，楊 雪.一種基于關聯(lián)度信息熵度量的特征選擇方法[J].計算機研究與發(fā)展，2016，53（8）：1684-1695.

[2]Liu H,Yu L.Toward integrating feature selection algorithms for classification and clustering[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(4):491-502.

[3]Hsu W H.Genetic wrappers for feature selection in decision tree induction and variable ordering in Bayesian network structure learning[J].Information Sciences,2004,163(1):103-122.

[4]Tabus I,Astola J.On the use of MDL principle in gene expression prediction[J].EURASIP Journal on Applied Signal Processing,2001,2001(1):297-303.

[5]Li L,Weinberg C R,Darden T A,et al.Gene selection for sample classification based on gene expression data:study of sensitivity to choice of parameters of the GA/KNN method[J].Bioinformatics,2001,17(12):1131-1142.

[6]Shima K,Todoriki M,Suzuki A.SVM-based feature selection of latent semantic features[J].Pattern Recognition Letters,2004,25(9):1051-1057.

[7]Oh I S,Lee J S,Moon B R.Hybrid genetic algorithms for feature selection[J].IEEE Transactions on pattern analysis and machine intelligence,2004,26(11):1424-1437.

[8]Huang C L.ACO-based hybrid classification system with feature subset selection and model parameters optimization[J].Neurocomputing,2009,73(1):438-448.

[9]Xue Bing,Zhang Meng-jie,Browne W N.Particle swarm optimisation for feature selection in classification:Novel initialisation and updating mechanisms[J].Applied Soft Computing,2014,18(4):261-276.

[10]Chuang LY,Tsai S W,Yang C H.Improved binary particle swarm optimization using catfish effect for feature selection[J].Expert Systems with Applications,2011,38(10):12699-12707.

[11]Yang X S.Firefly algorithm,stochastic test functions and design optimisation[J].International Journal of Bio-Inspired Computation,2010,2(2):78-84.

[12]Jati G.Evolutionary discrete firefly algorithm for travelling salesman problem[J].Adaptive and intelligent systems,2011:393-403.

[13]Khadwilard A,Chansombat S,Thepphakorn T,et al.Application of firefly algorithm and its parameter setting for job shop scheduling[J].J.Ind.Technol,2012,8(1).

[14]Abedinia O,Amjady N,Naderi M S.Multi-objective environmental/economic dispatch using firefly technique[C]//Environmentand ElectricalEngineering(EEEIC),2012 11th International Conference on.IEEE,2012:461-466.

[15]Long N C,Meesad P,Unger H.A highly accurate firefly based algorithm for heart disease prediction[J].Expert Systems with Applications,2015,42(21):8221-8231.

[16]Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//Computational intelligence for modelling,control and automation,2005 and international conference on intelligent agents,web technologies and internet commerce,international conference on IEEE,2005,1:695-701.