武小軍，周文心，董永新

（同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092）

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

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

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

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

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

1.1 多分類支持向量機

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

式中：C為正則項系數(shù)，通過非負(fù)松弛變量ε對誤分類點進(jìn)行懲罰。Ф是映射函數(shù)，將原數(shù)據(jù)集中的xi映射到高維空間中使問題線性化。但在絕大部分情況下，Ф沒有顯式?；诖颂攸c，學(xué)者考慮通過引入對偶問題和核函數(shù)求解（1）。已有許多文獻(xiàn)系統(tǒng)地介紹了原問題的對偶問題［15］，故本文不再贅述。原問題的對偶問題如下：

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

基于二分類SVM，學(xué)者提出多分類SVM，描述如下：給定含N個樣本的訓(xù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］。有學(xué)者指出，一對一方法更適合實際應(yīng)用［16］，同時也是LIBSVM庫采用的方法［17］。因此，本文選擇使用一對一方法求解多分類SVM問題。

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

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

1.2 改進(jìn)嵌入最小-最大值特征選擇算法

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

為了在預(yù)測準(zhǔn)確率和模型復(fù)雜度之間進(jìn)行權(quán)衡，提出如下的多目標(biāo)優(yōu)化問題。

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

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

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

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

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

式（12）目標(biāo)函數(shù)第二項的目標(biāo)是最小化w，w是（11）目標(biāo)函數(shù)的下界，所以式（12）等價于

1.3 搜索策略

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

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

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

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

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

假設(shè)T代表特征，記t代表T出現(xiàn)，則根據(jù)全概率公式可得

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

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

2 粒子群優(yōu)化算法

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

結(jié)束對于j的循環(huán)

結(jié)束對于i的循環(huán)

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

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

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

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

3 數(shù)值實驗

3.1 鋼板缺陷識別工程數(shù)據(jù)集介紹

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

表1 數(shù)據(jù)集中的特征名稱Tab.1 The name of features in dataset

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

表2 標(biāo)簽的名稱及其數(shù)量Tab.2 The name of classes and its numbers

3.2 數(shù)據(jù)預(yù)處理

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

圖2 各個特征之間的皮爾遜相關(guān)系數(shù)Fig.2 The pearson correlation coefficients among different features

由于本文采用一對一方法，因此在訓(xùn)練每個SVM時，都需要將yt＝i的標(biāo)簽設(shè)為+1，將yt＝j(luò)的標(biāo)簽設(shè)為-1。以上即為數(shù)據(jù)預(yù)處理部分。

3.3 實驗設(shè)置

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

3.4 實驗結(jié)果

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

表3 C和γ進(jìn)行方格搜索得到的模型預(yù)測準(zhǔn)確率Tab.3 The accuracy on test set using grid search with C andγ

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

圖3 C2和模型準(zhǔn)確率之間的關(guān)系Fig.3 The relationship between C2 and accuracy on test set

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

選取完C2后，進(jìn)入到算法1的流程中。由于0～1變量的引入，導(dǎo)致問題（11）和問題（13）的目標(biāo)函數(shù)和約束條件均是非凸的。調(diào)用Gurobi解決問題（11）和問題（13）時，未能在規(guī)定的24h內(nèi)求解出可行解，因此使用PSO算法對兩個問題進(jìn)行求解。

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

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

圖4 信息增益閾值和模型預(yù)測準(zhǔn)確率之間的關(guān)系Fig.4 Relationship between threshold of information gain and accuracy on test set

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

4 結(jié)論與不足

本文基于現(xiàn)有多分類SVM研究中的不足，提出了改進(jìn)嵌入最小-最大值特征選擇算法，在最小化特征數(shù)量的同時最大化模型預(yù)測的準(zhǔn)確率。由于引入了0～1變量，該優(yōu)化問題變成了組合優(yōu)化問題，在限定時間內(nèi)未能用數(shù)學(xué)規(guī)劃軟件求解得出全局最優(yōu)解，因此選擇使用啟發(fā)式算法求解。

數(shù)值實驗結(jié)果表明，本文提出的算法在該數(shù)據(jù)集上可以在犧牲可接受程度預(yù)測準(zhǔn)確率下降的條件下?lián)Q取模型訓(xùn)練時間的顯著下降。

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

作者貢獻(xiàn)聲明：

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

周文心：負(fù)責(zé)整理文獻(xiàn)，算法構(gòu)建，論文撰寫與修訂。

董永新：論文算法改進(jìn)。