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

周晶喆 侯能 宋成龍

關鍵詞： 封裝式特征選擇；二元粒子群優(yōu)化算法；轉換函數；預測準確率

0 引言

在機器學習和數據挖掘中，特征選擇是一種重要的數據預處理手段技術。所謂特征選擇，指從原始數據集的特征集合中，通過設計算法，找到一組特征子集，該特征子集能使給定機器學習模型的評價指標到達最優(yōu)[1]。

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

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

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

1 提出方法

1.1 標準粒子群算法

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

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

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

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

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

1.2 二進制粒子群算法

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

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

1.3 轉換函數

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

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

上式中，vmax、vmin分別為速度的上下界。s2、v2和線性轉換函數的對比如圖1所示：

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

1.4 適應度函數

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

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

1.5 粒子表達

BPSO中，每個粒子在每個維度上的取值只有0和1兩種，這種表達方式和特征選擇問題天然地吻合。粒子的維度等于樣本的特征數量，每個維度分量取值為0或者1表明即對應樣本特征分量的選擇與否。這意味著一個粒子就代表了一種特征選擇方案，一種選擇方案就對應一個目標函數值，即公式（6）的結果。

2 實驗

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

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

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

為了更好地評價不同轉換函數在本問題中的表現，本文測試了三個代表性的轉換函數，即1.3節(jié)所述的S2、V2和線性轉換函數。三種轉換函數對應的BPSO分別命名為SBPSO、VBPSO和LBPSO。三種BPSO在所有數據集上的運行結果如表2所示：

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

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

在Sonar數據集上，SBPSO能將KNN的預測準確率能提高11.51%；VBPSO能夠將KNN的預測準確率能提高17.15%；LBPSO能夠將KNN的預測準確率能提高12.74%。

在Glass數據集上，SBPSO能將KNN的預測準確率能提高6.46%；VBPSO能夠將KNN的預測準確率能提高5.29%；LBPSO能夠將KNN的預測準確率能提高7.25%。

在Seed數據集上，SBPSO能將KNN的預測準確率能提高2.2%；VBPSO能夠將KNN的預測準確率能提高1.96%；LBPSO能夠將KNN的預測準確率能提高2.86%。

在其他數據集上，三種BPSO算法也能不同程度地提高KNN的預測準確率，這也說明了封裝式特征選擇對于提高監(jiān)督學習算法性能的有效性。如表2的最后一行所示，通過在所有選定數據集上計算平均值，使用V2轉換函數的VBPSO的性能是最好的，即能夠將KNN的預測性能平均提升3.29%。

3 結論

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