一種改進的嵌入式特征選擇算法及應用

武小軍，周文心，董永新

（同濟大學經濟與管理學院，上海 200092）

近年來，人工智能技術的發展和應用呈現爆發式地增長，利用人工智能技術訓練輔助決策模型，協助人類完成各種復雜任務已經成為重要的理論研究和實踐應用前沿。在決策模型訓練的過程中，大數據集中的特征選擇是一個影響人工智能決策模型效果好壞的重要影響因素，良好的特征選擇不僅能夠提高模型預測的準確度，還能夠提升模型訓練的速度［1］。例如：Amoozegar和Minaei-Bidgoli［2］提出了改進多目標優化粒子群優化算法，并將該算法應用到有幾百個特征的數據集上，結果表明該算法在訓練速度上相較于其他算法有明顯優勢，且預測準確率也令人滿意。總體來看，特征選擇算法不僅可以應用于監督學習中的回歸問題［3］和分類問題［4］，而且可以提高無監督模型預測的準確性［5］，因此大量學者在這個領域進行了深入地探索。

Chandrashekar和Sahin［6］總結認為特征選擇算法主要有以下三種方法：過濾法（filter）［7］、嵌入法（embedded）［8］和包裝法（wrapper）［9］。過濾法主要應用于數據預處理階段，該方法將所有的特征按照其得分從高到低進行排序，排除得分較低的特征；嵌入法需要先使用某些機器學習的算法和模型進行訓練，得到各個特征的權重，再根據權重來選取特征；包裝法讓算法自己決定使用哪些特征，是一種特征選擇和模型訓練同時進行的方法。

嵌入法是一種應用比較廣泛的特征選擇算法，有許多文獻都將其應用到基于支持向量機算法（SVM）的擬合模型構建的研究中。例如：Jiménez-Cordero等［10］提出的嵌入最小-最大值特征選擇算法通過搜索策略優化了核函數中的γ，將γ大于0.01的特征保留了下來，形成了最優的特征子集，數值實驗表明，該文提出的算法對二分類問題比較有效。又如：Maldonado和López［11］提出了兩種類型的罰函數，并基于牛頓法和線搜法提出了改進優化算法來對凹函數進行優化，其方法在絕大部分數據集中，結合SVM方法都較于使用所有特征時模型效果更好。

盡管嵌入特征選擇算法已經受到很多學者的關注，但更多的是對二分類問題的研究，對基于多分類問題的最小-最大值特征選擇算法的研究還略顯不足。本文擬對此問題進行深入探討，提出一個新的改進算法，并將其應用于鋼板缺陷識別工程數據集，以驗證算法的有效性。

1 多分類支持向量機與改進嵌入最小-最大值特征選擇算法

1.1 多分類支持向量機

首先簡要闡述二分類SVM問題：給定標簽分別為+1、-1的數據，通過對已知數據集進行訓練，預測未知問題。對每組數據i∈S，S代表包含N個數字的集合{1，2，..，N}，輸入特征xi，xi∈Rm，標簽yi∈｛+1，-1｝，yi是xi的類標記。已有大量文獻詳細介紹了SVM［12-14］，故本文不再贅述模型的推導。非線性SVM的原始形式如下：

式中：C為正則項系數，通過非負松弛變量ε對誤分類點進行懲罰。Ф是映射函數，將原數據集中的xi映射到高維空間中使問題線性化。但在絕大部分情況下，Ф沒有顯式。基于此特點，學者考慮通過引入對偶問題和核函數求解（1）。已有許多文獻系統地介紹了原問題的對偶問題［15］，故本文不再贅述。原問題的對偶問題如下：

式中：λ＝(λ1，...，λN)T是拉格朗日乘子向量。核技巧（kernel trick），即引入核函數K(xi，xj)＝Ф(xi)′Ф(xj)（Rm×Rm→R）替代Ф，其中(·)’表示向量轉置，且K(xi，xj)具有顯式。（2）是凸規劃問題，因此可以由數學規劃軟件求得全局最優解。

基于二分類SVM，學者提出多分類SVM，描述如下：給定含N個樣本的訓練集X＝{(x1，y1)，...，(xN，yN)}，其中，xi是k維特征向量，yn∈{1，2，...，M}，n＝1，...，N。Hsu和Lin指出，解決多分類SVM主要有兩種方法：one-against-one（一對一）方法和one-against-all（一對多）方法［16］。有學者指出，一對一方法更適合實際應用［16］，同時也是LIBSVM庫采用的方法［17］。因此，本文選擇使用一對一方法求解多分類SVM問題。

一對一方法在每兩個類之間均訓練一個二分類SVM，故共需訓練個二分類SVM。對于第i類和第j類數據，訓練一個SVM即求解以下二次規劃問題：

其中，t是第i類和第j類并集的索引。定義dijt＝1，如果yt＝i；dijt＝-1，如果yt＝j。不加證明地給出式（3）的對偶形式如下

1.2 改進嵌入最小-最大值特征選擇算法

基于Jiménez-Cordero等［10］提出的嵌入最小-最大值特征選擇算法，Onel等［18］提出的特征選擇算法，提出了一種適用于多分類任務的改進嵌入最小-最大值特征選擇算法。引入0～1變量zu∈{0，1}，u∈{1，2，...，N}，當選擇特征i時，zi＝1，否則zi＝0。優化目標除極大化預測的準確率外，還極小化使用的特征數量，從而降低模型訓練的成本。將問題（4）改寫如下：

為了在預測準確率和模型復雜度之間進行權衡，提出如下的多目標優化問題。

其中，C2為超參數，取值范圍位于［0，1］之間。如果C2趨近于0，則模型以極大化預測準確率為目標，模型的復雜度會上升；如果C2趨近于1，模型將使用少量的特征進行訓練，會犧牲模型的準確率。

問題（6）的等價問題如下：

問題（7）是一個由上層問題和一個下層問題疊加起來的一個雙層優化問題。根據Mangasarian和Musicant［19］對拉格朗日對偶性的證明，這里不加證明地給出下層問題的拉格朗日函數。設下層問題的第一個約束對應的拉格朗日乘子為v，第i類和第j類數據一共有a個，約束λu≥0對應的拉格朗日乘子為，約束λu≤C對應的拉格朗日乘子為αCu。下層問題的拉格朗日函數為

記diag(dij)是一個a行a列，主對角線上是dij的各個元素，其余位置全是0的矩陣。記GZ＝diag(dij)Kdiag(dij)，其中K是核函數。則式（8）可以寫為

式中：e表示分量均為1，且和λ同階的列向量。由Karush-Kuhn-Tucker，KKT條件可得

式（12）目標函數第二項的目標是最小化w，w是（11）目標函數的下界，所以式（12）等價于

1.3 搜索策略

本節提出的算法用于求解優化問題（13）。由于使用一對一方法，需要訓練個SVM，即次外層循環。首先，為了避免過擬合，需要劃分出訓練集和測試集，分別用?和Stest表示，這個過程會重復N次，同時，需要確定超參數C2。最優的C2可以通過枚舉不斷調試。

其次，將S?分為訓練集和驗證集，用Strain和Sval表示。對于C和γ進行網格搜索（grid search），在Strain上求解問題（4），并在Sval上計算模型的準確率。搜索完所有C和γ后，給出Sval上預測準確率最高的對應的C和γ，且γ是求解問題（11）的初始值。

接下來，使用C和γ在?上求解問題（11），返回λ，v，α0，αC的初始值。

獲取到上述初始值后，在?上求解問題（13），得到z*，λ*，v*，(α0)*，(αC)*。并計算在Stest上的模型準確率。

由于0～1變量的引入，在訓練第i類和第j類數據時可以直接得到相應最優特征子序列。但由于總共要訓練個SVM，因此就不能直觀地通過0～1變量的取值選取用于訓練的特征。文獻［20-22］指出，可以通過信息增益（Information gain，IG）選取最優特征子序列。考慮一個分類系統，以類別C為變量，其可能的取值有C1，C2，...，Cn，每個類別出現的概率分別為P(C1)，P(C2)，...，P(Cn)，其中n是類別總數。此時分類系統的信息熵為

假設T代表特征，記t代表T出現，則根據全概率公式可得

式中，P(t)代表特征T出現的概率代表特征T不出現的概率。由此可以推出信息增益的公式如下：

通過設定閾值，可以判斷應該選擇哪些變量作為訓練多分類SVM的特征。以上算法的偽代碼在算法1中展示。

2 粒子群優化算法

粒子群優化算法（particle swarm optimization，PSO）是一種經典的啟發式算法，使用無質量的例子來模擬鳥群里的鳥。粒子本身有兩個屬性：速度和位置。每個粒子在搜索空間中單獨搜索最優解，記錄其所獲得的最優值，并將該值與粒子群里的其他粒子共享，經過比較后將最優粒子所獲得的最優值作為整個粒子群本輪的全局最優值。而粒子群中所有非最優粒子根據自己找到的個體最優值和整個粒子群的全局最優值來調整其速度和位置。在求解非凸的子問題時，如果使用數學規劃軟件無法在規定的24h內返回最優解，則改為使用粒子群優化算法求解。

結束對于j的循環

結束對于i的循環

初始狀態下，粒子群中所有粒子的均為隨機，通過迭代找到最優解。每一輪迭代中，每個粒子根據其個體最優值（pbest）和整個粒子群的全局最優值（gbest）更新自身屬性。在找到上述兩個最優值后，每個粒子將通過以下兩個公式來更新其位置和速度，即

式中：i是粒子群中粒子的個數，i＝1，2，...，N；xi是粒子的當前位置；vi是粒子的速度；c1、c2是學習因子，通常均設為2；rand（）是介于（0，1）之間的隨機數。此外，式（19）也可用以更新粒子的速度

式中：ω是超參數，代表慣性因子，其值非負。圖（1）為PSO算法的流程。

圖1 PSO算法流程圖Fig.1 The flow chart of PSO algorithm

3 數值實驗

3.1 鋼板缺陷識別工程數據集介紹

鋼板是一種重要的工業原材料，其質量很大程度上影響了產成品的質量。本文使用的鋼板缺陷識別數據集來自于可以從UCI的網站http：//archive.ics.uci.edu/ml下載。該數據集共包含27個特征，7個類別，1941組數據，其特征名稱列于表1中。

表1 數據集中的特征名稱Tab.1 The name of features in dataset

這是一個多分類問題，共含有7個類別的標簽。每個標簽的名稱及其數量如表2所示。

表2 標簽的名稱及其數量Tab.2 The name of classes and its numbers

3.2 數據預處理

本數據集中，待分類的類別共7類，以獨熱編碼（one-hot encoding）的形式存儲。首先把類別轉換成一一對應的形式，即將原數據集中的7列轉換成1列。其次，考察特征之間的相關性，排除存在共線性的特征。本文中，根據皮爾遜相關系數進行判斷，排除相關系數絕對值大于0.95的特征。各個特征之間的相關系數如圖2所示。經過判斷，決定排除2、4、6、8、13號特征。

圖2 各個特征之間的皮爾遜相關系數Fig.2 The pearson correlation coefficients among different features

由于本文采用一對一方法，因此在訓練每個SVM時，都需要將yt＝i的標簽設為+1，將yt＝j的標簽設為-1。以上即為數據預處理部分。

3.3 實驗設置

本文的所有程序均是在Windows 10環境下，使用Python 3.8編寫。對于提出的優化問題，通過調用Gurobi 9.1.1或使用PSO算法進行求解；如果調用Gurobi求解的時間超過24h，即停止計算，選擇啟發式算法進行求解。

3.4 實驗結果

按算法1，先解式（4），對C和γ進行方格搜索。假設C＝{10-2，10-1，1，..，10，102}，γ＝{10-2，10-1，1，...，10，102}。經過多次實驗，得到當C＝5，γ＝0.1時，模型的平均得分最高。取其中一次的實驗結果寫入表3（保留兩位小數）。

表3 C和γ進行方格搜索得到的模型預測準確率Tab.3 The accuracy on test set using grid search with C andγ

如2.2節所述，超參數C2的不同取值可以在模型復雜度和模型準確率之間進行權衡。選擇C2的所有可能取值為0.01，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9。由于設定超參數時尚未應用特征選擇算法，意即固定z＝1，取C＝5，γ＝0.1，求解問題（13）。根據文獻［13］所述，如果固定γ，那么問題（17）就是一個凸規劃問題，可以調用Gurobi進行求解。在S?上進行求解，在Stest上進行測試，得到的C2與測試集上準確率如圖3所示。

圖3 C2和模型準確率之間的關系Fig.3 The relationship between C2 and accuracy on test set

從圖上可以看出，實驗結果同先前假設基本一致，隨著C2不斷增大，模型在測試集上的準確率不斷降低，當C2＝0.9時，模型在測試集上的準確率降至44.60%。在該數據集中，選擇超參數C2＝0.2，能夠較好地平衡模型復雜度和模型預測準確率之間的關系。需要強調的是，超參數的選取同數據集本身相關。如文獻［10］所述，在數值實驗中，將特征選擇算法應用到不同數據集時，所選取的C2是不同的，因此作者建議超參數C2應該由用戶選取。

選取完C2后，進入到算法1的流程中。由于0～1變量的引入，導致問題（11）和問題（13）的目標函數和約束條件均是非凸的。調用Gurobi解決問題（11）和問題（13）時，未能在規定的24h內求解出可行解，因此使用PSO算法對兩個問題進行求解。

本數據集中，選擇學習因子c1、c2等于2，慣性因子ω＝0.3，粒子個數為22，迭代次數為100次。先訓練第i類和第j類數據之間的SVM，返回在該SVM情況下選擇的特征。然后使用信息增益算法對返回的個結果進行評估，從而選擇合適的變量作為多分類SVM的最終特征。設定信息增益的閾值分別為0.2，0.5，0.8，1，大于該閾值的特征即被選中。被選中特征的數量和模型在測試集上的準確率如圖（4）所示。

從圖（4）可以看出，隨著信息增益閾值不斷增大，模型在測試集上的準確率不斷變低。因為閾值變大，選取的特征數量會減少，從而導致有用信息的丟失。該數據集中，選取信息增益閾值等于0.5的變量作為訓練的特征，這時選擇的特征的編號是2，3，4，5，6，7，8，10，11，12，13，14，16，17，19，20。

圖4 信息增益閾值和模型預測準確率之間的關系Fig.4 Relationship between threshold of information gain and accuracy on test set

最后將改進嵌入特征選擇算法同未經特征選擇的多分類SVM進行比較。作為基本假設，改進嵌入特征選擇算法在預測準確度上不會優于基準算法且在可以接受的范圍內，而訓練的速度會快于基準算法，快的“程度”具體取決于用戶選取的信息增益閾值。經過實驗，基準算法訓練SVM的時間是1.19s，在測試集上的準確率是73.8%；而使用改進嵌入特征選擇算法訓練SVM的時間是1.03s，在測試集上的準確率是71.2%。考慮到sklearn的庫函數經過高度優化，且這個數據集的特征數目并不多，如若推廣到更高維的數據集中，則提出的特征選擇算法在多分類SVM問題中具有廣泛的應用前景。

4 結論與不足

本文基于現有多分類SVM研究中的不足，提出了改進嵌入最小-最大值特征選擇算法，在最小化特征數量的同時最大化模型預測的準確率。由于引入了0～1變量，該優化問題變成了組合優化問題，在限定時間內未能用數學規劃軟件求解得出全局最優解，因此選擇使用啟發式算法求解。

數值實驗結果表明，本文提出的算法在該數據集上可以在犧牲可接受程度預測準確率下降的條件下換取模型訓練時間的顯著下降。

本文將SVM問題中的核函數限定為高斯核函數。然而，應用其他的核函數可能會得到不一樣的結論。此外，提出的算法僅僅被應用在一個數據集中，可以考慮使用更多的經典數據集來驗證其訓練時間和訓練精度。最后，未來的研究可以考慮放棄該模型中的0～1變量，轉而使用其他評估方法來選取特征，因為這樣可以充分利用到凸函數的性質，獲得更令人滿意的結果。

作者貢獻聲明：

武小軍：提出選題，設計論文框架。

周文心：負責整理文獻，算法構建，論文撰寫與修訂。

董永新：論文算法改進。