基于二進(jìn)制粒子群優(yōu)化算法的封裝式特征選擇研究

周晶喆 侯能 宋成龍

關(guān)鍵詞： 封裝式特征選擇；二元粒子群優(yōu)化算法；轉(zhuǎn)換函數(shù)；預(yù)測(cè)準(zhǔn)確率

0 引言

在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中，特征選擇是一種重要的數(shù)據(jù)預(yù)處理手段技術(shù)。所謂特征選擇，指從原始數(shù)據(jù)集的特征集合中，通過設(shè)計(jì)算法，找到一組特征子集，該特征子集能使給定機(jī)器學(xué)習(xí)模型的評(píng)價(jià)指標(biāo)到達(dá)最優(yōu)[1]。

根據(jù)流程的不同，特征選擇分為過濾式、嵌入式和封裝式[2]。3種特征選擇各有其優(yōu)勢(shì)和局限性，本文主要討論封裝式特征選擇。封裝式特征選擇方法常用在監(jiān)督學(xué)習(xí)中，由目標(biāo)學(xué)習(xí)算法和搜索策略兩部分構(gòu)成。其中，目標(biāo)學(xué)習(xí)算法用于評(píng)判特征子集的優(yōu)劣。而搜索策略關(guān)注如何高效地從所有特征子集中找到使監(jiān)督學(xué)習(xí)算性能最優(yōu)的子集。假設(shè)一個(gè)數(shù)據(jù)集的樣本由N個(gè)特征組成。根據(jù)每個(gè)特征的選擇與否，可能的所有特征子集組合數(shù)有2N個(gè)。封裝式特征選擇中就是通過設(shè)計(jì)搜索算法，從所有的2N個(gè)可能組合中，找到最優(yōu)特征組合。

已有文獻(xiàn)指出，封裝式特征選擇是一種NP難問題[3]。求解該問題的搜索方法包括窮舉法、啟發(fā)法和群體智能算法。其中，窮舉法需要評(píng)價(jià)所有的候選方案，不適合特征數(shù)較多的數(shù)據(jù)集；啟發(fā)式方法雖然能高效地得到近似解，但解的質(zhì)量離最優(yōu)解差距較大；群體智能算法是目前求解該問題的常用方法[4-5]。然而，群體智能算法在提出時(shí)，主要用于求解連續(xù)的函數(shù)優(yōu)化問題，解的表達(dá)在每個(gè)維度上是浮點(diǎn)數(shù)。本問題中，解的表達(dá)只有0和1兩種取值。當(dāng)使用群體智能算法方法求解特征選擇時(shí)，需要考慮將解的表達(dá)離散化后，原始算法仍然能夠在二元離散問題中起作用。

因此，本文以經(jīng)典的粒子群優(yōu)化算法作為起點(diǎn)，探索了二元粒子群優(yōu)化算法中的不同轉(zhuǎn)換函數(shù)對(duì)求解質(zhì)量的影響。在實(shí)驗(yàn)階段，通過在不同的數(shù)據(jù)集上進(jìn)行測(cè)試，分析了二元粒子群算法在特征選擇問題中的性能表現(xiàn)。

1 提出方法

1.1 標(biāo)準(zhǔn)粒子群算法

標(biāo)準(zhǔn)的粒子群優(yōu)化算法（Particle Swarm Optimiza?tion， PSO）最初由Kennedy和Eberhart于1996年提出的一種群體智能算法[6]。算法用多個(gè)粒子模擬鳥群的社會(huì)行為的方式尋找最優(yōu)解。在搜索空間中，粒子以迭代的方式四處飛行。尋優(yōu)時(shí)，每個(gè)粒子會(huì)更新各自的尋優(yōu)軌跡。不僅如此，粒子在移到下一個(gè)位置時(shí)，既考慮自身已有的最佳解，也要考慮種群其他粒子已找到的最佳解。最終，整個(gè)種群找到全局最佳解。

PSO中，每個(gè)粒子在尋優(yōu)中更新各自的位置時(shí)，要考慮自身的當(dāng)前位置、當(dāng)前速度、自身的歷史最佳位置、全局最佳位置。更新位置的過程可形式化描述為如下兩式：

以上兩式中，xit和vit分別表示第t 次迭代時(shí)，第i 個(gè)粒子的位置和速度；pbesti表示第i 個(gè)粒子在第t 次迭代時(shí)已知的個(gè)體歷史最優(yōu)位置；gbest表示在第t次迭代時(shí)，各個(gè)粒子找到的已知全局最佳位置；r1和r2表示[0，1]之間的隨機(jī)數(shù)；c1和c2都表示加速度系數(shù)，通常取固定值2.0；w 表示第t 次迭代時(shí)粒子的速度慣性系數(shù)，取0.4～0.9之間的數(shù)。w 取值越大，粒子探索全局最優(yōu)的能力越強(qiáng)，但是隨著迭代的進(jìn)行，有可能跳過全局最優(yōu)解；xit+1和vit+1分別表示在第t+1 次迭代時(shí)，粒子更新后的位置和速度。

從以上兩式可看出，粒子的位置更新公式（2）取決于速度更新公式（1）的3個(gè)部分，即當(dāng)前速度、自身歷史最佳位置與自身位置的距離、全局最佳位置與自身位置距離的合成。位置和速度一般都表示為向量，以上兩式作用在向量的每個(gè)分量上。

總體來說，用PSO優(yōu)化待解決的問題時(shí)，首先將粒子位置進(jìn)行隨機(jī)初始化，速度初始化為0；然后，初始化每個(gè)粒子的個(gè)體最佳歷史位置，根據(jù)每個(gè)粒子的適應(yīng)度值初始化全局最佳位置；在每次迭代時(shí)，每個(gè)粒子使用公式（1）和（2）更新速度和位置、更新歷史最佳位置；最后，根據(jù)所有粒子的更新位置更新全局最佳位置。迭代過程重復(fù)執(zhí)行，直到迭代次數(shù)滿足預(yù)先設(shè)置的次數(shù)為止。

1.2 二進(jìn)制粒子群算法

標(biāo)準(zhǔn)的PSO適用于求解連續(xù)空間的優(yōu)化問題，即每個(gè)粒子的位置分量都是定義域范圍內(nèi)的實(shí)數(shù)；現(xiàn)實(shí)生活中，大多數(shù)問題都被建模為組合優(yōu)化問題，即問題的解分量是離散的。典型的組合優(yōu)化問題有兩種解形式：解分量只有0和1兩種狀態(tài)的（01背包問題、特征選擇問題）和解分量為從一組數(shù)字中無放回取樣的（旅行商問題、流水車間調(diào)度問題）。對(duì)于離散空間的尋優(yōu)，標(biāo)準(zhǔn)PSO算法無法直接使用。因此，根據(jù)標(biāo)準(zhǔn)PSO的原理，Kennedy和Eberhart于1997年進(jìn)一步提出粒子位置分量只有0和1兩種狀態(tài)的二元粒子群優(yōu)化算法（Binary Particle Swarm Optimization， BPSO）[7]。對(duì)于BPSO，可以將位置空間的所有狀態(tài)看成是一種超立方體。單個(gè)粒子表示超立方體的某一個(gè)角點(diǎn)，搜索使粒子在超立方體的角點(diǎn)間移動(dòng)。盡管BPSO中粒子的位置分量只有0和1兩種值，粒子的速度更新公式（1）仍然適用，其結(jié)果也仍然是實(shí)數(shù)。

BPSO與標(biāo)準(zhǔn)PSO的另一個(gè)區(qū)別在于BPSO舍棄了位置更新公式（2），改用sigmoid轉(zhuǎn)換函數(shù)將得到的實(shí)數(shù)型速度分量值轉(zhuǎn)換到[0，1]區(qū)間。然后，用一個(gè)隨機(jī)數(shù)與轉(zhuǎn)換后的值進(jìn)行比較。如果隨機(jī)數(shù)比轉(zhuǎn)換后的值小，意味著隨機(jī)數(shù)位于sigmoid內(nèi)，位置分量設(shè)置為0；否則，隨機(jī)數(shù)位于sigmoid外部，設(shè)置為1。將位置轉(zhuǎn)換形式化為如下：

1.3 轉(zhuǎn)換函數(shù)

自BPSO 提出后，有一些研究工作提出不同的BPSO算法和原始的BPSO進(jìn)行比較。這些工作中，文獻(xiàn)[8]重點(diǎn)研究了轉(zhuǎn)換函數(shù)并總結(jié)了S類和V類兩大類，共8個(gè)轉(zhuǎn)換函數(shù)。在實(shí)驗(yàn)階段，對(duì)這8個(gè)轉(zhuǎn)換函數(shù)進(jìn)行了對(duì)比分析。此外，對(duì)于粒子的速度更新公式（2）中的系數(shù)w，改為迭代中在[0.4， 0.9]范圍內(nèi)線性遞減。

在特征選擇問題中，除了BPSO外，使用其他群體智能算法求解該問題時(shí)也需要用到轉(zhuǎn)換函數(shù)。同時(shí)，S類和V類兩大類轉(zhuǎn)換函數(shù)中，s2和v2是該問題中是經(jīng)常選用的函數(shù)，這兩種轉(zhuǎn)換函數(shù)不需要對(duì)定義域設(shè)置上下界。然而算法在實(shí)際執(zhí)行時(shí)，每個(gè)粒子會(huì)在更新速度后進(jìn)行上下界判斷，使速度限制在上下界中。當(dāng)定義域存在上下界時(shí)，轉(zhuǎn)換函數(shù)除了s1和s2外，也可以是線性的。線性轉(zhuǎn)換函數(shù)的表達(dá)式如下：

上式中，vmax、vmin分別為速度的上下界。s2、v2和線性轉(zhuǎn)換函數(shù)的對(duì)比如圖1所示：

從圖1中可以看出，三種轉(zhuǎn)換函數(shù)在圖中覆蓋區(qū)域大小是不同的。這意味著，相同的速度分量，由于轉(zhuǎn)換后的概率值不同，使得產(chǎn)生的隨機(jī)數(shù)被轉(zhuǎn)換為1還是0的結(jié)果有所區(qū)別，從而影響特征的選擇與否。

1.4 適應(yīng)度函數(shù)

本文中，封裝式特征選擇的目標(biāo)函數(shù)形式化為最小化優(yōu)化問題：

上式的優(yōu)化目標(biāo)由兩部分組成，一是監(jiān)督學(xué)習(xí)算法的性能，二是被選擇的特征數(shù)量。具體地，給定數(shù)據(jù)集S，每個(gè)樣本的特征數(shù)為M，Accuracy（S）表示目標(biāo)監(jiān)督學(xué)習(xí)算法在數(shù)據(jù)集S上的預(yù)測(cè)準(zhǔn)確率。相應(yīng)地，1-Accuracy（S）表示目標(biāo)監(jiān)督算法的錯(cuò)誤率。錯(cuò)誤率越低，算法的預(yù)測(cè)能力越強(qiáng)。第二部分中，m 表示被選擇特征的個(gè)數(shù)，M 為樣本數(shù)據(jù)的全部特征總數(shù)，m/M表示選中的特征數(shù)量占總特征數(shù)量的比重。這兩個(gè)部分通過權(quán)值ɑ調(diào)節(jié)兩個(gè)目標(biāo)的重要程度。本文中，根據(jù)文獻(xiàn)[9]的建議，ɑ取值0.99。

1.5 粒子表達(dá)

BPSO中，每個(gè)粒子在每個(gè)維度上的取值只有0和1兩種，這種表達(dá)方式和特征選擇問題天然地吻合。粒子的維度等于樣本的特征數(shù)量，每個(gè)維度分量取值為0或者1表明即對(duì)應(yīng)樣本特征分量的選擇與否。這意味著一個(gè)粒子就代表了一種特征選擇方案，一種選擇方案就對(duì)應(yīng)一個(gè)目標(biāo)函數(shù)值，即公式（6）的結(jié)果。

2 實(shí)驗(yàn)

為了測(cè)試BPSO算法求解封裝式特征選擇問題的性能，本文選用了UC Irvine Machine Learning Reposi?tory中的部分?jǐn)?shù)據(jù)集。這些數(shù)據(jù)集在樣本、特征以及類別數(shù)量上都各不相同。所選數(shù)據(jù)集的具體參數(shù)如表1所示：

實(shí)驗(yàn)的軟硬件環(huán)境為：CPU型號(hào)為Intel（R） Core（TM） i5-1035G1，內(nèi)存大小為8GB，操作系統(tǒng)為WIN10。算法采用Python3 實(shí)現(xiàn)，且選用numpy，sklearn第三方庫。二進(jìn)制粒子群算法涉及參數(shù)設(shè)置為：個(gè)體數(shù)量為12，維度大小取決于選用的數(shù)據(jù)集，進(jìn)化代數(shù)為50。

封裝式特征選擇問題中，通常會(huì)用KNN作為監(jiān)督學(xué)習(xí)算法來評(píng)價(jià)提出的搜索算法的性能。KNN無須對(duì)樣本進(jìn)行訓(xùn)練，在測(cè)試階段直接計(jì)算測(cè)試樣本和所有訓(xùn)練樣本的距離，以距離訓(xùn)練樣本的遠(yuǎn)近程度來預(yù)測(cè)測(cè)試樣本所屬類別。對(duì)于KNN，本文調(diào)用sklearn庫實(shí)現(xiàn)，且采用默認(rèn)參數(shù)（鄰域k=5，歐式距離計(jì)算樣本間的相似度）。

為了更好地評(píng)價(jià)不同轉(zhuǎn)換函數(shù)在本問題中的表現(xiàn)，本文測(cè)試了三個(gè)代表性的轉(zhuǎn)換函數(shù)，即1.3節(jié)所述的S2、V2和線性轉(zhuǎn)換函數(shù)。三種轉(zhuǎn)換函數(shù)對(duì)應(yīng)的BPSO分別命名為SBPSO、VBPSO和LBPSO。三種BPSO在所有數(shù)據(jù)集上的運(yùn)行結(jié)果如表2所示：

表2中，第1列為數(shù)據(jù)集名稱；第2列表示不采用特征選擇，即所有特征都用于監(jiān)督學(xué)習(xí)時(shí)，KNN的預(yù)測(cè)準(zhǔn)確率；第3列～第5列分別是采用三種轉(zhuǎn)換函數(shù)的BPSO優(yōu)化特征組合方案后，KNN的預(yù)測(cè)準(zhǔn)確率；最后一行表示根據(jù)所有數(shù)據(jù)集的預(yù)測(cè)結(jié)果計(jì)算平均值。

與第2列的完全不使用特征選擇方案相比，比較突出的結(jié)果總結(jié)如下：

在Sonar數(shù)據(jù)集上，SBPSO能將KNN的預(yù)測(cè)準(zhǔn)確率能提高11.51%；VBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高17.15%；LBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高12.74%。

在Glass數(shù)據(jù)集上，SBPSO能將KNN的預(yù)測(cè)準(zhǔn)確率能提高6.46%；VBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高5.29%；LBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高7.25%。

在Seed數(shù)據(jù)集上，SBPSO能將KNN的預(yù)測(cè)準(zhǔn)確率能提高2.2%；VBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高1.96%；LBPSO能夠?qū)NN的預(yù)測(cè)準(zhǔn)確率能提高2.86%。

在其他數(shù)據(jù)集上，三種BPSO算法也能不同程度地提高KNN的預(yù)測(cè)準(zhǔn)確率，這也說明了封裝式特征選擇對(duì)于提高監(jiān)督學(xué)習(xí)算法性能的有效性。如表2的最后一行所示，通過在所有選定數(shù)據(jù)集上計(jì)算平均值，使用V2轉(zhuǎn)換函數(shù)的VBPSO的性能是最好的，即能夠?qū)NN的預(yù)測(cè)性能平均提升3.29%。

3 結(jié)論

本文對(duì)二進(jìn)制粒子群優(yōu)化算法用于封裝式特征選擇問題時(shí)，不同的轉(zhuǎn)換函數(shù)對(duì)算法性能的影響展開了研究。在11個(gè)數(shù)據(jù)集上測(cè)試了三種轉(zhuǎn)換函數(shù)的性能。實(shí)驗(yàn)結(jié)果表明，采用V2型轉(zhuǎn)換函數(shù)的二進(jìn)制粒子群優(yōu)化算法，對(duì)KNN的預(yù)測(cè)準(zhǔn)確率的提升，在總體上表現(xiàn)是最好的。在今后使用更新的群體智能算法求解特征選擇時(shí)，將就如何對(duì)算法進(jìn)行二元化展開研究。