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

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 吉林 長(zhǎng)春 130012； 2.吉林大學(xué) 軟件學(xué)院, 吉林 長(zhǎng)春 130012)

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

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

1 相關(guān)工作

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

1.1 演化計(jì)算用于特征選擇

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

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

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

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

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

2 QPACO算法

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

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

(1)

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

(2)

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

當(dāng)螞蟻完成一次迭代后，每條路徑上的信息素都會(huì)進(jìn)行更新：

(3)

(4)

式中：Q為常數(shù)；Lk為螞蟻k在此次迭代中的路徑長(zhǎng)度.

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

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

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

(5)

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

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

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

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

2.3.1 路徑轉(zhuǎn)移概率計(jì)算

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

(6)

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

2.3.2 信息素τ的計(jì)算與更新

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

τnew=τold×q+Δτ.

(7)

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

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

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

(8)

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

考慮到信息素值的上下限問(wèn)題，因此在k次迭代時(shí)信息素的更新τnew和信息素更新量的記錄Δτk計(jì)算如下：

(9)

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

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

F_score是用于評(píng)價(jià)特征識(shí)別能力的度量，第i個(gè)特征的F_score公式為

F_scorei=

(10)

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

(11)

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

2.4 QPACO算法偽代碼

QPACO算法偽代碼見(jiàn)表1.

表1 QPACO算法偽代碼

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與對(duì)比算法

本文從UCI數(shù)據(jù)庫(kù)中選擇了一些典型的數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證.典型的數(shù)據(jù)集見(jiàn)表2.

表2 UCI數(shù)據(jù)集

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

3.2 實(shí)驗(yàn)環(huán)境、評(píng)估指標(biāo)及實(shí)驗(yàn)參數(shù)

3.2.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)中使用了python 3.6實(shí)現(xiàn)了本文的算法，同時(shí)使用了公開(kāi)的工具包scikit-learn.所有實(shí)驗(yàn)均在一臺(tái)配置為Intel Core i5-4210H(CPU)，8GB內(nèi)存、1TB硬盤(pán)的計(jì)算機(jī)上完成.

3.2.2 評(píng)估指標(biāo)

在本實(shí)驗(yàn)中，使用分類精度(Ac)、精確率(Rp)，召回率(Rrecall)和維度縮減率(Rf)來(lái)評(píng)估所提出的算法性能.

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

(12)

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

(13)

(14)

其中：TPi為第i類下正確分類的測(cè)試樣本數(shù)；FPi為第i類下錯(cuò)誤分類的測(cè)試樣本數(shù)；FNi為在其他類別下錯(cuò)誤分類的測(cè)試樣本數(shù).

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

(15)

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

3.2.3 算法參數(shù)設(shè)置

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

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 實(shí)驗(yàn)結(jié)果

為了確保對(duì)比實(shí)驗(yàn)的準(zhǔn)確性，表3與表4中的部分?jǐn)?shù)據(jù)采用了文獻(xiàn)[13]中的實(shí)驗(yàn)結(jié)果，表3是QPACO算法與其對(duì)比算法在不同數(shù)據(jù)集上的分類精度的對(duì)比.表4是QPACO算法與其對(duì)比算法在不同數(shù)據(jù)集上的精確率、召回率及維度縮減率的對(duì)比，最后一列為每個(gè)算法在所有數(shù)據(jù)集上的指標(biāo)和，和越大說(shuō)明算法總體性能越好.

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

注：括號(hào)中的數(shù)字表示在各個(gè)數(shù)據(jù)集上每種算法性能的排名.

3.3.2 實(shí)驗(yàn)分析

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

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

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

4 結(jié) 論

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