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

周晶喆 侯能 宋成龍

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

0 引言

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

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

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

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

1 提出方法

1.1 標準粒子群算法

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

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

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

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

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

1.2 二進制粒子群算法

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

BPSO與標準PSO的另一個區別在于BPSO舍棄了位置更新公式（2），改用sigmoid轉換函數將得到的實數型速度分量值轉換到[0，1]區間。然后，用一個隨機數與轉換后的值進行比較。如果隨機數比轉換后的值小，意味著隨機數位于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是該問題中是經常選用的函數，這兩種轉換函數不需要對定義域設置上下界。然而算法在實際執行時，每個粒子會在更新速度后進行上下界判斷，使速度限制在上下界中。當定義域存在上下界時，轉換函數除了s1和s2外，也可以是線性的。線性轉換函數的表達式如下：

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

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

1.4 適應度函數

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

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

1.5 粒子表達

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

2 實驗

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

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

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

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

表2中，第1列為數據集名稱；第2列表示不采用特征選擇，即所有特征都用于監督學習時，KNN的預測準確率；第3列～第5列分別是采用三種轉換函數的BPSO優化特征組合方案后，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的預測準確率，這也說明了封裝式特征選擇對于提高監督學習算法性能的有效性。如表2的最后一行所示，通過在所有選定數據集上計算平均值，使用V2轉換函數的VBPSO的性能是最好的，即能夠將KNN的預測性能平均提升3.29%。

3 結論

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