李占山， 劉兆賡， 俞 寅， 鄢文浩

(1.吉林大學 計算機科學與技術學院, 吉林 長春 130012； 2.吉林大學 軟件學院, 吉林 長春 130012)

近年來，許多涉及信息的領域中產生了包含眾多特征的高維數據，然而并不是所有特征都是重要的.許多特征甚至是不相關或冗余的，這不僅使數據處理過程變得困難，還降低了學習算法的效率，如分類算法等學習算法的性能[1].特征選擇旨在利用一種選擇策略，消除不相關和冗余的特征，找到最佳特征子集[2].特征選擇是一個復雜的問題，對于一個有n個特征的數據集，可能的解決方案的總數是2n-1[3]，其搜索空間十分龐大.因此，用窮舉搜索選擇一組最優(yōu)特征的時間復雜度是O(2n)[4]，這在大多數情況下是不切實際的.與傳統(tǒng)方法相比，基于演化算法的特征選擇方法更適合于解決這種問題.

本文設計了一種基于隨機二元蟻群網絡的特征選擇方法，更換了啟發(fā)式因子的計算方法，并提出了一種新的信息素更新思路，將整體的信息素量子化，賦予每個信息素生命周期，形成了量子化信息素蟻群優(yōu)化(quantized pheromone ant colony optimization, QPACO)特征選擇算法.

1 相關工作

近年來，基于演化計算的特征選擇算法受到了廣泛研究，基于演化計算的特征選擇算法已發(fā)表論文超過500篇[1].

1.1 演化計算用于特征選擇

基于演化計算的特征選擇算法的研究近年來取得了較為令人滿意的結果.如Rashedi等提出了通過增強傳遞函數克服停滯問題的IBGSA[5]，IBGSA將二進制向量每個位與一個特征相關聯，通過尋找最優(yōu)二進制向量找到特征選擇的最優(yōu)解；Chuang等在二元粒子群算法BPSO中引入鯰魚效應，提出了Catfish BPSO[6]，Catfish BPSO將局部最優(yōu)中的粒子通過鯰魚效應引導到新的搜索空間，同時使用種群中最差的適應值替換10%的原始粒子，最終避免了局部最優(yōu)，進一步獲得了更好的解；初蓓等提出了改進的森林優(yōu)化特征選擇算法IFSFOA[7]，采用了新的初始化策略和更新機制進一步提高原始算法的性能.

1.2 蟻群優(yōu)化算法用于特征選擇

本文主要討論基于蟻群優(yōu)化算法的特征選擇算法.蟻群優(yōu)化(ant colony optimization, ACO)算法是Dorigo等提出的一種演化算法[8].螞蟻之間的通信會產生正反饋行為，引導蟻群收斂到最優(yōu)解.蟻群路徑上分布的信息素模擬了真實螞蟻所經過的路線上的化學物質[9].

基于蟻群優(yōu)化算法解決特征選擇的主要思想是將問題建模為求解搜索圖的最小成本路徑問題，創(chuàng)建一個包含節(jié)點的搜索空間并設計一個程序來尋找解決方案的路徑，螞蟻的路徑表示特征的子集.ACO算法基于信息素和啟發(fā)式信息計算螞蟻選擇解路徑的轉移概率.Chen等使用這種類型的ACO算法進行特征選擇，提出了ACOFS[10]，ACOFS中使用了F_score標準作為啟發(fā)式值，但采用了不同的信息素更新策略；Kashef等提出了一種優(yōu)化的二元蟻群算法ABACO[11]，該算法的不同之處在于每個特征都有兩個節(jié)點，一個節(jié)點用于選擇，另一個節(jié)點用于取消選擇相應的特征，最優(yōu)特征子集是滿足遍歷停止條件的最小節(jié)點數的螞蟻遍歷圖.

與上述特征選擇算法相比，本文提出的QPACO算法，采用了新的啟發(fā)式因子的計算方法，改變了傳統(tǒng)的信息素的更新策略，避免了搜索特征時的局部最優(yōu)，提高了特征選擇的精度.

2 QPACO算法

2.1 基于蟻群優(yōu)化算法的特征選擇算法

基于蟻群優(yōu)化算法的特征選擇算法首先構造了由n個特征組成的有向圖，假設螞蟻在初始時刻被隨機放置在n個特征節(jié)點中，并維護一張禁忌列表記錄每只螞蟻已經訪問過的節(jié)點，每條邊的信息素τi,j初始值為0，螞蟻依據邊上的信息素計算在t次迭代時，螞蟻k從特征i移動到特征j的概率：

(1)

式中：S是螞蟻k的禁忌列表；α是信息啟發(fā)因子；β是期望啟發(fā)式因子，用于分配啟發(fā)式信息和信息素濃度的權重；ηi,j是啟發(fā)式信息，通常計算為

(2)

式中,di,j是特征i與特征j之間的歐幾里得度量.

當螞蟻完成一次迭代后，每條路徑上的信息素都會進行更新：

(3)

(4)

式中：Q為常數；Lk為螞蟻k在此次迭代中的路徑長度.

基于蟻群優(yōu)化算法的特征選擇算法在特征選擇領域上有一定的作用，但仍存在一些不足，因此提出了許多不同版本的改進.

2.2 二元蟻群優(yōu)化特征選擇算法

二元蟻群優(yōu)化(binary ant colony optimization, BACO)特征選擇算法是另一種常用的求解算法.該方法僅允許全局最優(yōu)螞蟻存放信息素，并采用最大最小策略進行信息素更新，即信息素軌跡被限制在[min，max]區(qū)間內，其中min和max是滿足min

(5)

式中：p01是與子路徑(0→1)相關聯的概率；τ00和τ01是子路徑(0→0和0→1)上的信息素.

雖然BACO能夠在短時間內找到近似最優(yōu)解，但是它依舊面臨著一些問題，如螞蟻對特征的看法有限及特征選擇的準確率有待提高.在本文提出的算法中，嘗試結合傳統(tǒng)的ACO和BACO來解決上述問題.

2.3 量子化蟻群優(yōu)化特征選擇算法

鑒于現有算法的準確率仍待提高，經過研究，本文提出了量子化信息素蟻群優(yōu)化特征選擇算法QPACO.

2.3.1 路徑轉移概率計算

螞蟻在特征圖中的轉移按照概率進行，在QPACO算法中，每一個特征均包含其子節(jié)點1或0，則意味著該特征被該螞蟻選擇或未選擇.那么在特征i與j之間，顯然存在4條路徑(0→0, 0→1, 1→0, 1→1).這些路徑上的轉移概率計算方式如下：

(6)

式中：ix，jy分別表示特征i和j中的子節(jié)點；C表示螞蟻能夠訪問且尚未被訪問到的節(jié)點集合；τ表示子節(jié)點間的信息素；η表示子節(jié)點間的啟發(fā)式信息；α和β是確定信息素和啟發(fā)信息值的兩個參數.

2.3.2 信息素τ的計算與更新

在一般的蟻群和蟻群變種的特征選擇算法中，通常人們采用設定一個常量q(0

τnew=τold×q+Δτ.

(7)

式中：q為信息素模擬消失常量；τold為原來的信息素值；τnew為更新后的信息素值；Δτ為信息素變化量.

QPACO算法中提出了一種新的信息素揮發(fā)方式，即把信息素量子化，看成是一份一份有著時間標記的信息素單元，每一單元信息素都有著屬于自己的生命周期，當自己生命周期結束時揮發(fā)，其簡化公式如下：

τnew=τold-τdead+Δτ.

(8)

式中，τdead為在該次迭代中生命周期結束的信息素量.

考慮到信息素值的上下限問題，因此在k次迭代時信息素的更新τnew和信息素更新量的記錄Δτk計算如下：

(9)

2.3.3 啟發(fā)式信息η的計算

在參考了眾多η的計算方法后，發(fā)現基于F_score的改進啟發(fā)式度量方式更適用于本文的算法.

F_score是用于評價特征識別能力的度量，第i個特征的F_score公式為

F_scorei=

(10)

越大的F_score意味著該特征具有判別力的可能性越大[12]，使用該標準的邊的啟發(fā)信息計算如下：

(11)

式中：ηix,jy代表特征i取值為x時與特征j取值為y時所構成的邊上的啟發(fā)式信息(x和y的取值均為0或1)；n為特征的數目；ξ為常量(通常取值在0～1之間).

2.4 QPACO算法偽代碼

QPACO算法偽代碼見表1.

表1 QPACO算法偽代碼

3 實驗結果與分析

3.1 實驗數據與對比算法

本文從UCI數據庫中選擇了一些典型的數據集對算法進行驗證.典型的數據集見表2.

表2 UCI數據集

為了更好地展現算法的可比性，選擇了一些具有代表性的特征選擇算法與本文算法進行比較，其中包括Catfish BPSO[6]、改進二元引力搜索(IBGSA)[5]、基于蟻群優(yōu)化算法的特征選擇算法ACOFS[10]和ABACOH[13]、改進的森林優(yōu)化特征選擇算法IFSFOA[7]和二元蝴蝶優(yōu)化特征選擇算法S-bBOA[14]等.

3.2 實驗環(huán)境、評估指標及實驗參數

3.2.1 實驗環(huán)境

實驗中使用了python 3.6實現了本文的算法，同時使用了公開的工具包scikit-learn.所有實驗均在一臺配置為Intel Core i5-4210H(CPU)，8GB內存、1TB硬盤的計算機上完成.

3.2.2 評估指標

在本實驗中，使用分類精度(Ac)、精確率(Rp)，召回率(Rrecall)和維度縮減率(Rf)來評估所提出的算法性能.

分類精度(Ac)，即正確分類的樣本數和測試集的總樣本數的百分比，其定義為

(12)

精確率(Rp)和召回率(Rrecall)計算式如下：

(13)

(14)

其中：TPi為第i類下正確分類的測試樣本數；FPi為第i類下錯誤分類的測試樣本數；FNi為在其他類別下錯誤分類的測試樣本數.

定義維度縮減率(Rf)如下：

(15)

其中：n是總特征數；p是算法所選擇的特征數.

3.2.3 算法參數設置

在QPACO算法與其他算法的對比實驗中，統(tǒng)一設置了算法的一些參數：所有算法的種群數量和迭代次數為50；在每次實驗中，60%的樣本隨機選擇進行訓練，剩下40%的樣本用于測試；實驗結果在每個數據集和算法中獨立運行超過20次，最后統(tǒng)計平均值；揮發(fā)系數ρ為0.049；每條路徑上的最小和最大信息素強度分別設定為0.1和6；每個邊緣的初始信息素強度設定為0.1；α和β是決定信息素和啟發(fā)信息的相對重要性的兩個參數，設α=1，β=0.5；在分類器的選擇上，使用了K近鄰(KNN)分類器作為基分類器，并將參數K設置為1.

3.3 實驗結果與分析

3.3.1 實驗結果

為了確保對比實驗的準確性，表3與表4中的部分數據采用了文獻[13]中的實驗結果，表3是QPACO算法與其對比算法在不同數據集上的分類精度的對比.表4是QPACO算法與其對比算法在不同數據集上的精確率、召回率及維度縮減率的對比，最后一列為每個算法在所有數據集上的指標和，和越大說明算法總體性能越好.

表3 QPACO及其對比算法的平均分類精度對比

注：括號中的數字表示在各個數據集上每種算法性能的排名.

3.3.2 實驗分析

QPACO算法在時間效率上是基本等同于二元蟻群優(yōu)化算法的，在算法的改進過程中，計算和記錄每次信息素的更新量，以及查找生命周期結束信息素量的時間復雜度都是O(1)，因此時間上的開銷差距并不明顯，所以本文遵從了相關的基于演化計算的特征選擇方法的實驗設計模式，并未采用時間效率來衡量算法性能[13-17]，但計算了其他常用的評估指標進行算法間的對比.

對比分類精度，從表3中不難看出，QPACO算法在Glass，Letter，Shuttle，Spambase，Waveform，Wisconsin這些數據集上均位居第一，在Wine和Yeast上位居第二，只在Vehicle上稍顯遜色.因此QPACO算法在分類精度上有了很明顯的提升.通過對比表4中的精確率、召回率以及維度縮減率，發(fā)現QPACO算法大多數情況下精確率和召回率都略高于其他算法，且維度縮減率維持在平均水平以上.

表4 QPACO及其對比算法的精確率、召回率、維度縮減率對比

4 結 論

本文提出了基于傳統(tǒng)蟻群優(yōu)化算法和二元蟻群優(yōu)化算法的量子化信息素蟻群優(yōu)化(QPACO)特征選擇算法.QPACO算法中將信息素量子化，賦予每個信息素單獨的生命周期，同時修改了啟發(fā)式因子的更新方式，增強了算法的搜索能力.經過9個數據集和9個特征選擇算法的對比實驗，驗證了QPACO算法良好的性能.如何在高維數據集中應用QPACO算法進行特征選擇問題的求解，將是下一步重點研究的內容.