基于多寬度高斯核的支持向量機特征選取算法研究

羅浪+汪靜

摘 要：支持向量機（SVM）作為一種機器學(xué)習(xí)分類算法應(yīng)用廣泛，但在處理高維度數(shù)據(jù)集時往往會由于特征維數(shù)較多遇到算法分類速度慢且容易陷入局部最優(yōu)等問題。為了提高支持向量機的性能，提出一種基于多寬度高斯核（GKMW）的支持向量機特征選取算法FSG。FSG算法將泛化能力更強的多寬度高斯核函數(shù)引入支持向量機中代替?zhèn)鹘y(tǒng)的高斯核函數(shù)，利用多寬度高斯核函數(shù)能體現(xiàn)各個特征對分類貢獻(xiàn)程度不同且能區(qū)分樣本中各個特征重要性的特點，以多寬度高斯核函數(shù)的參數(shù)優(yōu)化結(jié)果為基礎(chǔ)進(jìn)行特征選取。利用特征選取后的特征子集在多組標(biāo)準(zhǔn)UCI數(shù)據(jù)集上分類實驗，實驗結(jié)果表明所提算法性能優(yōu)于有代表性的特征選取法。

關(guān)鍵詞：多寬度高斯核；支持向量機；特征選??；基因表達(dá)式編程

DOIDOI：10.11907/rjdk.181012

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）002-0080-06

0 引言

大數(shù)據(jù)時代下數(shù)據(jù)規(guī)模龐雜，特征選取在處理高維度數(shù)據(jù)集時是一項很重要的前置處理工作，即為一種依據(jù)可靠的準(zhǔn)則去挑選最佳特征的方法。特征選取將有用的特征保留，移除對分類相關(guān)性較低的特征，以分辨哪些特征是人們所需要且有助于進(jìn)行分類的，以此來決定維度的重要性，并希望使用最佳特征組合所得到的分類效果能接近使用全部特征所得到的分類效果，而只使用最佳特征組合不僅能降低特征空間的復(fù)雜度，且能加快分類速度提高分類性能[1]。

特征選取已被應(yīng)用到許多不同領(lǐng)域，目前在自動文本分類處理、人臉或字符識別、醫(yī)學(xué)圖像處理等高維度數(shù)據(jù)集中均有大量應(yīng)用[2]。常用的特征選取方法有信息增益（Information Gain，IG）[3]、卡方檢驗（Chi-square test，CHI）[4]、互信息（Mutual Information，MI）[5]等。然而上述方法均是在原空間中找出具有最大線性分散量或分離量的特征，而且支持向量機（Support Vector Machine，SVM）中傳統(tǒng)的高斯核函數(shù)存在局限性，其唯一可調(diào)寬度參數(shù)決定了高斯核函數(shù)的泛化規(guī)模，同時也限制了支持向量機的泛化性能。高斯核的這種單寬度性使得在樣本的稀疏區(qū)域會產(chǎn)生欠學(xué)習(xí)現(xiàn)象，而在樣本的稠密區(qū)域會產(chǎn)生過學(xué)習(xí)現(xiàn)象，并直接造成了對樣本分布的錯誤估計[6]。針對上述問題，本文提出一種基于多寬度高斯核的支持向量機特征選取算法——Feature Selection in Support Vector Machine Based on Gaussian Kernel with Multiple Widths（FSG）算法，將泛化能力更強的多寬度高斯核函數(shù)引入到支持向量機中代替?zhèn)鹘y(tǒng)的高斯核函數(shù)，由于多寬度高斯核函數(shù)的參數(shù)組合與特征向量一一對應(yīng)，因此利用多寬度高斯核函數(shù)能體現(xiàn)各個特征對分類貢獻(xiàn)程度不同，且能區(qū)分樣本中各個特征重要性的特點，在多寬度高斯核函數(shù)參數(shù)優(yōu)化結(jié)果的基礎(chǔ)上，根據(jù)參數(shù)組合的大小對特征進(jìn)行選取，以此找出具有最大非線性分離量的特征子集，最終達(dá)到更好的分類效果，同時減少訓(xùn)練時間以提高效率。利用特征選取后的特征子集在多組標(biāo)準(zhǔn)UCI數(shù)據(jù)集上進(jìn)行分類實驗。

1 相關(guān)概念

1.1 支持向量機

支持向量機（SVM）是由Vapnik等[7]從結(jié)構(gòu)風(fēng)險最小化概念中所提出的一種基于統(tǒng)計學(xué)習(xí)理論的分類算法。支持向量機的基本原理是為了尋求最佳的線性分類面，SVM通過定義適當(dāng)?shù)膬?nèi)積函數(shù)進(jìn)行非線性變換，把原始數(shù)據(jù)空間變換到某一高維的特征空間，并在高維的特征空間中利用超平面對樣本進(jìn)行準(zhǔn)確分類，同時保持分類的間隔最大。

其中，w為權(quán)向量，b為分類閾值，φ是一個非線性的映射函數(shù)，ξi為松弛變量，是分類錯誤的容許量。滿足以上條件的超平面中分類間隔最大的就是最佳分類面（見圖1）。

整理后的最佳分類面問題可以表示成如下約束優(yōu)化問題，即在式（2）的約束下，求函數(shù)：

其中C為懲罰參數(shù)，當(dāng)C值變小時，分類錯誤的容許量較高，分類精確度較低；反之，當(dāng)C值變大時，分類錯誤的容許量較低，則分類精確度較高。最終可以得出最優(yōu)分類函數(shù)：

式（4）中，ai是二次規(guī)劃優(yōu)化問題所求解的拉格朗日因子，N為支持向量數(shù)。

對于線性不可分問題，可采用在定義的空間中引入核函數(shù)K（xi，x），把低維空間變換到高維空間，對應(yīng)的判別函數(shù)為：

由此可以看出，核函數(shù)及其參數(shù)的變化是決定SVM分類器泛化能力的關(guān)鍵因素，所以挑選適當(dāng)?shù)暮撕瘮?shù)及其參數(shù)成為SVM分類效果的保障。

1.2 多寬度高斯核函數(shù)

多寬度高斯核函數(shù)形式如下[8]：

多寬度高斯核函數(shù)可以針對每一個維度，調(diào)整不同的寬度，但如果每個維度的σ都相等，則多寬度的高斯核函數(shù)會退化成傳統(tǒng)的高斯核函數(shù)，所以傳統(tǒng)的高斯核函數(shù)為多寬度高斯核函數(shù)的一個特例。容易證明GKMW是一個正定核，即為SVM的可取核，通過實驗驗證，GKMW可以通過多參數(shù)調(diào)節(jié)解決高斯核可調(diào)參數(shù)唯一性導(dǎo)致的過學(xué)習(xí)問題，提高了核的學(xué)習(xí)能力和泛化能力，同時GKMW的核參數(shù)空間覆蓋了單寬度高斯核的參數(shù)空間，在搭配SVM的情況下，分類效果提升明顯[8]。

根據(jù)式（6）展開得到：

其中d為特征空間中特征的維數(shù)?？梢詫挾葏?shù)視為特征的重要程度，1σ2i（i=1，2，…，d）代表其第i個特征的重要程度，即多寬度高斯核函數(shù)的參數(shù)組合與特征向量一一對應(yīng)，多寬度高斯核函數(shù)不僅能體現(xiàn)各個特征對分類的貢獻(xiàn)程度不相同，而且能區(qū)分樣本中各個特征的重要性。因此，本文先對多寬度高斯核函數(shù)進(jìn)行參數(shù)優(yōu)化，然后在參數(shù)優(yōu)化結(jié)果的基礎(chǔ)上根據(jù)參數(shù)組合的大小進(jìn)行特征選取。

2 FSG算法

2.1 多寬度高斯核函數(shù)的參數(shù)優(yōu)化endprint

多寬度高斯核雖比傳統(tǒng)的高斯核更加有彈性且能改善分類的泛化能力，但是多寬度高斯核函數(shù)所使用的參數(shù)數(shù)量等于特征的數(shù)量，對于高維數(shù)據(jù)集，傳統(tǒng)的參數(shù)優(yōu)化方法如網(wǎng)格搜索法在處理時面對參數(shù)的數(shù)量增加，計算復(fù)雜度會呈現(xiàn)指數(shù)增長，難以預(yù)先確定多寬度高斯核函數(shù)的最佳參數(shù)組合[9]。本文以特征空間中類別之間的分散程度為依據(jù)設(shè)計參數(shù)優(yōu)化法，算法可以確定在固定的參數(shù)組合下，相對應(yīng)的特征空間中類別之間的分散程度，當(dāng)每一個訓(xùn)練樣本在特征空間中與同類樣本更加靠近、與不同類樣本更加疏遠(yuǎn)時，SVM的分類效果最優(yōu)，此時在最佳分類準(zhǔn)確率下所對應(yīng)的參數(shù)組合即是最佳參數(shù)組合，以此進(jìn)行參數(shù)優(yōu)化。

如果能通過調(diào)整這一組σ的值，即調(diào)整核函數(shù)K的值，使得特征空間中同一類訓(xùn)練樣本的K值更接近于1，即同一類的訓(xùn)練樣本在特征空間中更聚攏；同時使特征空間中不同類訓(xùn)練樣本的K值（i≠j）更接近于0，即不同類訓(xùn)練樣本在特征空間中更加分散，那么此時就能提高SVM的分類效果，圖2展示了這一點。

2.2 特征選取

對于最優(yōu)參數(shù)組合的結(jié)果，即式（17）的優(yōu)化問題，考慮到基因表達(dá)式編程（Gene Expression Programming，GEP）在多參數(shù)優(yōu)化方面的高效率，以及相較于傳統(tǒng)方法如牛頓優(yōu)化法等，GEP更易跳出局部最優(yōu)得到全局最優(yōu)解，本文采用GEP對結(jié)果進(jìn)行尋優(yōu)[12]?；虮磉_(dá)式編程GEP是一種基于生物基因結(jié)構(gòu)和功能發(fā)明的新型自適應(yīng)演化算法，融合了遺傳算法簡單線性的個體固定長度編碼及遺傳編程可變與彈性的樹形結(jié)構(gòu)，可以利用簡單編碼解決復(fù)雜問題[13]。

為了提高參數(shù)的精確度，染色體編碼時采用GEP-PO基因[13]。GEP-PO基因在傳統(tǒng)基因結(jié)構(gòu)中增加一個常數(shù)區(qū)域（DC）和隨機常量數(shù)組，并通過在大量隨機數(shù)值常數(shù)上通過數(shù)學(xué)運算符進(jìn)化參數(shù)的值，其中常數(shù)區(qū)域的長度等于基因的尾部長度。GEP-PO基因結(jié)構(gòu)比起傳統(tǒng)基因結(jié)構(gòu)更加復(fù)雜，但能夠擴大染色體的搜索空間，使搜索的結(jié)果更易達(dá)到峰值，提高發(fā)現(xiàn)全局最優(yōu)的效率。對于多參數(shù)優(yōu)化問題，染色體采用多基因染色體，每一個子基因均采用GEP-PO基因，GEP-PO基因中的DC域為參數(shù)域，隨機常量數(shù)組為該參數(shù)的隨機樣本集合，取值為該參數(shù)滿足約束條件的隨機樣本值。因此每一個基因代表一個參數(shù)的編碼，每一個參數(shù)對應(yīng)一個獨立的隨機樣本參數(shù)集合。

除了采用常規(guī)GEP的遺傳算子以外，還需考慮到利用GEP-PO基因涉及到的常數(shù)域和隨機常量數(shù)組，因此同時還對常數(shù)域進(jìn)行變異、單點重組、兩點重組、倒串、插串操作?？紤]到隨機常數(shù)的進(jìn)化主要受益于變異，因此隨機常量數(shù)組采用的遺傳算子主要是隨機常數(shù)變異，變異操作只要保證各參數(shù)的樣本取值在可行域內(nèi)，則均能保證基因的合法結(jié)構(gòu)。

由優(yōu)化函數(shù)（17），可設(shè)計適應(yīng)度函數(shù)為：

其中，F(xiàn)itnessi為第i個個體的適應(yīng)度函數(shù)，Ri（σ1，…，σd）為第i個個體對應(yīng)的目標(biāo)函數(shù)值，M為選擇范圍，取M=10作為選擇范圍，精確度為0.1。如果在參數(shù)的可行域內(nèi)，得到的各參數(shù)值不滿足約束條件，則該個體適應(yīng)度定義為0。

此時所得到的最優(yōu)參數(shù)組合{σ1，…，σd}的大小被用來確定特征的重要性，算法選取的特征根據(jù){1σ1，1σ2，…，1σd}的大小降序排列。當(dāng)1σi的值越大時，則代表此對應(yīng)的特征越重要，是特征選取的優(yōu)先考量；當(dāng)1σi的值越小時，則代表此對應(yīng)的特征越不重要，可以不用優(yōu)先列入考量。

2.3 FSG算法步驟

綜上所述，算法步驟歸納如下：

輸出：最優(yōu)的特征子集。

步驟1 初始化種群，根據(jù)式（12）和式（13）進(jìn)行特征標(biāo)準(zhǔn)化。

步驟2 根據(jù)式（17）設(shè)置參數(shù)組合表達(dá)式。

步驟3 根據(jù)式（18）計算種群中每個個體的適應(yīng)度值，若滿足進(jìn)化終止條件則轉(zhuǎn)至步驟6，否則繼續(xù)下一步。

步驟4 對種群實施最優(yōu)保存策略，并進(jìn)行遺傳操作生成下一代種群。

步驟5 轉(zhuǎn)至步驟3繼續(xù)循環(huán)。

步驟6 解碼最優(yōu)個體并返回最優(yōu)參數(shù)組合。

步驟7 根據(jù)最優(yōu)參數(shù)組合的值對各維度參數(shù)大小進(jìn)行排序。

步驟8 根據(jù)排序結(jié)果以及降低維度數(shù)p進(jìn)行特征選取并返回最優(yōu)特征子集。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境與實驗數(shù)據(jù)集

本文借助開源的機器學(xué)習(xí)軟件weka進(jìn)行實驗，實驗環(huán)境為：Intel Core i5-2430M 2.4GHz雙核CPU，2GB內(nèi)存，Windows 7 Service Pack 1（x32）[14]。基因表達(dá)式編程的優(yōu)化過程利用遺傳算法工具GeneXproTools 4.0完成，設(shè)置函數(shù)集合為{+、-、*、/}，終結(jié)符集為{？}，基因頭長為7，種群大小為20，最大進(jìn)化代數(shù)為100，常量集合大小為10，常量區(qū)間為[-2，2]。另外支持向量機的懲罰參數(shù)C使用網(wǎng)格搜索法搭配交叉驗證法來決定，其中網(wǎng)格搜索法設(shè)置C的初始范圍為[2-10，27]，交叉驗證法設(shè)置K為5。各遺傳算子參數(shù)設(shè)置如下：

本文選取標(biāo)準(zhǔn)的UCI數(shù)據(jù)庫中多個不同規(guī)模的分類數(shù)據(jù)集作為實驗數(shù)據(jù)，實驗數(shù)據(jù)集的具體描述如表2所示[15]。

3.2 實驗結(jié)果與分析

實驗1：該實驗用于評價FSG算法中多寬度高斯核參數(shù)優(yōu)化結(jié)果的有效性，實驗數(shù)據(jù)的訓(xùn)練集為每個數(shù)據(jù)集隨機選取80%的樣本，剩下20%的樣本作為測試集，評價指標(biāo)采用5次實驗的平均。實驗根據(jù)每一代種群中的適應(yīng)度函數(shù)值以及其對應(yīng)的SVM分類準(zhǔn)確率作圖，其中X軸為種群的迭代次數(shù)，兩個Y軸的含義如下：第x代種群中適應(yīng)度函數(shù)值的最大值、第x代種群中適應(yīng)度函數(shù)值最大值的染色體所對應(yīng)的參數(shù)組合求得的SVM分類準(zhǔn)確率。如果適應(yīng)度函數(shù)值曲線和測試準(zhǔn)確率曲線的趨勢是基本一致且為上升的，并且最后能穩(wěn)定收斂，則就能說明多寬度高斯核參數(shù)優(yōu)化的結(jié)果是有效的。實驗結(jié)果如圖3-圖6所示，點線代表準(zhǔn)確率曲線；另一條為適應(yīng)度曲線。endprint

圖3-圖6結(jié)果顯示，隨著適應(yīng)度函數(shù)值的變大，其測試準(zhǔn)確率也會隨之增加。根據(jù)FSG算法由類別分散程度所確定的適應(yīng)度函數(shù)值可以指導(dǎo)種群前進(jìn)的方向，從圖中可以看出適應(yīng)度函數(shù)值總體上逐代遞增，種群也在向前進(jìn)化，而與此同時隨著種群的進(jìn)化，支持向量機分類的準(zhǔn)確率也逐步提高。因此在算法指導(dǎo)種群前進(jìn)方向的基礎(chǔ)上，參數(shù)組合確實得到了優(yōu)化。迭代開始時，由于各個參數(shù)離最優(yōu)值相差較大，所以測試準(zhǔn)確率較低。經(jīng)過一定次數(shù)的迭代以后，適應(yīng)度函數(shù)值曲線和測試準(zhǔn)確率曲線的上升已經(jīng)趨于平緩，并且數(shù)值收斂到比較穩(wěn)定的值，兩條曲線共同的趨勢以及最后收斂到比較穩(wěn)定的數(shù)值說明本文的參數(shù)優(yōu)化結(jié)果是有效的。

實驗2：該實驗用于評價FSG算法的性能，實驗采用在很多分類任務(wù)中特征選取性能表現(xiàn)優(yōu)秀的信息增益法IG進(jìn)行對比實驗[3]。信息增益法將信息增益作為特征選擇的一個重要指標(biāo)，信息增益被定義為一個特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多說明該特征越重要，相應(yīng)的信息增益也就越大，即信息增益法是一個有效的全局特征選取算法。實驗結(jié)果的評價指標(biāo)采用分類準(zhǔn)確率及分類AUC值，分類AUC（Area Under roc Curve）值表示ROC（Receiver Operating Characteristics）曲線下面積[16]，能客觀反映異類樣本數(shù)量不均勻時的分類結(jié)果，分類準(zhǔn)確率及分類AUC值是常用的評估分類器性能的指標(biāo)，其值越高則分類器性能越好。實驗結(jié)果如表3所示。

通過表3的實驗結(jié)果可以發(fā)現(xiàn)，在除Image Segmentation數(shù)據(jù)集外的其他3個數(shù)據(jù)集上，F(xiàn)SG算法的分類準(zhǔn)確率比傳統(tǒng)的IG算法有所提高，SVM獲得更優(yōu)的分類性能。同時在分類AUC值的比較上，F(xiàn)SG算法對樣本進(jìn)行特征選取的效果也比IG算法要好，從標(biāo)準(zhǔn)差的值可以看出FSG算法與IG算法均具有較好的穩(wěn)定性。對于所選用的數(shù)據(jù)集，與IG算法相比，F(xiàn)SG算法雖然在運行時間上有一些損失，但是與提高的分類準(zhǔn)確率相比，這些損失是可以接受的。

4 結(jié)語

本文為提高支持向量機的分類性能引入泛化能力更強的多寬度高斯核函數(shù)，并針對多寬度高斯核的特點設(shè)計了參數(shù)優(yōu)化法，通過實驗驗證了本文參數(shù)優(yōu)化結(jié)果的有效性。同時根據(jù)多寬度高斯核能區(qū)分樣本中各個特征重要性的特點，提出了基于多寬度高斯核的支持向量機特征選取算法FSG，F(xiàn)SG算法以參數(shù)優(yōu)化的結(jié)果為基礎(chǔ)進(jìn)行特征選取，以此提高支持向量機的性能。通過與傳統(tǒng)的信息增益特征選取法在多組標(biāo)準(zhǔn)UCI數(shù)據(jù)集上進(jìn)行對比實驗，結(jié)果顯示FSG算法能在保證穩(wěn)定性的同時有效提高分類準(zhǔn)確率。

參考文獻(xiàn)：

[1] LIU H，SUN J，LIU L，et al.Fearure selection with dynamic mutual information[J].Pattern Recognition，2009，42（7）：1330-1339.

[2] MEI DU，YAN LIANG，LU ZHAO.On feature selection and its application to twenty newsgroups text classification[C].Proceedings of 2016 2nd International Conference on Education and Management Science （ICEMS 2016），2016：361-364.

[3] GUOHUA WU，JUNJUN XU.Optimized approach of feature selection based on information gain[J].Computer Science and Mechanical Automation （CSMA） International Conference on 2015，2015：23-25.

[4] 劉海峰，蘇展，劉守生.一種基于詞頻信息的改進(jìn)CHI文本特征選擇[J].計算機工程與應(yīng)用，2013，49（22）：110-114.

[5] LIU T H.Mutual information based feature selection for multivari-ate time series forecasting[C].中國自動化學(xué)會控制理論專業(yè)委員會、中國系統(tǒng)工程學(xué)會第35屆中國控制會議論文集（E），2016：140-144.

[6] SADEEP JAYASUMANA，RICHARD HARTLEY，MATHIEU SALZMANN.Kernel methods on riemannian manifolds with gaussian RBF kernels[C].IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015：2464-2477.

[7] VAPNIK V.Universal learning technology：support vector machines[C].NEC Journ of Adv Tech，2005，2（2）：137-144.

[8] 常群.支持向量機的核方法及其模型選擇[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2007.

[9] TAIJIA XIAO，DONG REN，SHUANGHUI LEI.Based on grid-search and PSO parameter optimization for Support Vector Machine[C]. Intelligent Control and Automation （WCICA） 2014 11th World Congress，2014.

[10] 李巍，孫濤，陳建孝，等.基于加權(quán)余弦相似度的XML文檔聚類研究[J].吉林大學(xué)學(xué)報（信息科學(xué)版），2010，28（1）：68-76.

[11] 秦建強，孔祥玉，孫喜榮.數(shù)據(jù)標(biāo)準(zhǔn)化對Sevcik分形維數(shù)算法的性能影響[J].儀器儀表學(xué)報，2016，37（7）：1485-1491.

[12] 鮑瑩瑩.基于二階擬柯西方程的對角擬牛頓算法研究[D].太原：太原科技大學(xué)，2013.

[13] 孟艷.基于GEP的工程結(jié)構(gòu)優(yōu)化設(shè)計[D].焦作：河南理工大學(xué)，2011.

[14] WITTEN I H，F(xiàn)RANK E.Data mining-practical machine learning tools and techniques with java implementation[M].San Francisco：Morgan Kaufmann Publishers，2000.

[15] BLAKE C L，MERZ C J. UCI machine learning repository[EB/OL].2006 Available http：//www.ics.uci.edu/～mlearn/MLSummary.html.

[16] PROVOST F，F(xiàn)AWCETT T.Analysis and visualization of classifier performance： comparison under imprecise class and cost distributions[C].Proceedings of 3rd International Conference on Know ledge Discovery and Data Mining，1997：43-48.endprint