羅浪+汪靜

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

關鍵詞：多寬度高斯核；支持向量機；特征選??；基因表達式編程

DOIDOI：10.11907/rjdk.181012

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）002-0080-06

0 引言

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

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

1 相關概念

1.1 支持向量機

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

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

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

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

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

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

由此可以看出，核函數及其參數的變化是決定SVM分類器泛化能力的關鍵因素，所以挑選適當的核函數及其參數成為SVM分類效果的保障。

1.2 多寬度高斯核函數

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

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

根據式（6）展開得到：

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

2 FSG算法

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

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

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

2.2 特征選取

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

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

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

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

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

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

2.3 FSG算法步驟

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

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

步驟1 初始化種群，根據式（12）和式（13）進行特征標準化。

步驟2 根據式（17）設置參數組合表達式。

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

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

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

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

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

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

3 實驗結果與分析

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

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

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

3.2 實驗結果與分析

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

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

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

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

4 結語

本文為提高支持向量機的分類性能引入泛化能力更強的多寬度高斯核函數，并針對多寬度高斯核的特點設計了參數優(yōu)化法，通過實驗驗證了本文參數優(yōu)化結果的有效性。同時根據多寬度高斯核能區(qū)分樣本中各個特征重要性的特點，提出了基于多寬度高斯核的支持向量機特征選取算法FSG，F(xiàn)SG算法以參數優(yōu)化的結果為基礎進行特征選取，以此提高支持向量機的性能。通過與傳統(tǒng)的信息增益特征選取法在多組標準UCI數據集上進行對比實驗，結果顯示FSG算法能在保證穩(wě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] 劉海峰，蘇展，劉守生.一種基于詞頻信息的改進CHI文本特征選擇[J].計算機工程與應用，2013，49（22）：110-114.

[5] LIU T H.Mutual information based feature selection for multivari-ate time series forecasting[C].中國自動化學會控制理論專業(yè)委員會、中國系統(tǒng)工程學會第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è)大學，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] 李巍，孫濤，陳建孝，等.基于加權余弦相似度的XML文檔聚類研究[J].吉林大學學報（信息科學版），2010，28（1）：68-76.

[11] 秦建強，孔祥玉，孫喜榮.數據標準化對Sevcik分形維數算法的性能影響[J].儀器儀表學報，2016，37（7）：1485-1491.

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

[13] 孟艷.基于GEP的工程結構優(yōu)化設計[D].焦作：河南理工大學，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