核極化的特征選擇算法在LSSVM中的應(yīng)用

王建國(guó)，陳肖潔，張文興

（內(nèi)蒙古科技大學(xué) 機(jī)械工程學(xué)院，內(nèi)蒙古 包頭 014010）

1 引言

在支持向量機(jī)（support vector machine，SVM）中，關(guān)于 SVM的核函數(shù)選擇，高斯核備受青睞。究其原因?yàn)楦咚购司哂蟹€(wěn)定優(yōu)越的性能，可以使SVM獲得較好的推廣性[1-2]。高斯核的寬度參數(shù)決定了樣本數(shù)據(jù)分布的復(fù)雜程度，進(jìn)而，影響特征空間中最優(yōu)分類超平面的泛化性能，高斯核的形式：

為了體現(xiàn)樣本中不同特征的重要性程度，即區(qū)別各個(gè)特征對(duì)分類貢獻(xiàn)率的差異，引入了多寬度（多參數(shù)）高斯核[3]，假設(shè)x有D個(gè)特征量，xi［m］，xj［m］是其中的第m個(gè)特征量，其形式如下：

顯然，我們可以利用fm值的大小來衡量不同特征的重要性差異，將其應(yīng)用到特征選擇中。特征選擇一般是指按照某種評(píng)估標(biāo)準(zhǔn)從輸入特征集中選擇出最優(yōu)的特征子集，去除冗余、無關(guān)特征以達(dá)到提高學(xué)習(xí)精度的目的。現(xiàn)在，關(guān)鍵問題是，fm值的確定問題。高斯核的核參數(shù)優(yōu)化方法主要有：（1）不斷循環(huán)SVM分類器迭代優(yōu)化算法[4]和粒子群優(yōu)化尋優(yōu)算法[2]，該兩種方法的缺點(diǎn)為計(jì)算量大；（2）獨(dú)立于分類器SVM的核度量標(biāo)準(zhǔn)[5]的方法，如最大化核極化的算法[6-8]，不足之處是以SVM為分類器，求解凸二次規(guī)劃問題來取的最優(yōu)解。因此，我們采用優(yōu)化獨(dú)立于分類算法的核度量標(biāo)準(zhǔn)—核極化來優(yōu)化多參數(shù)高斯核中的多參數(shù)，并以最小二乘支持向量機(jī)（leastsquaressupportvectormachine，LSSVM）為學(xué)習(xí)器，求解一組線性方程組來得到方程的最優(yōu)值，簡(jiǎn)化計(jì)算量，提高計(jì)算效率。

2 最小二乘支持向量機(jī)（LSSVM）

式中：k（xi，xj）—核函數(shù)；b—偏置量；αi≠0 的訓(xùn)練樣本為支持向量，這里αi，?i通過求解下面的線性方程獲得：

式中：矩陣 Ω=yiyjφT（xi）φ（xj）=yiyjk（xi，xj），i，j=1，L，l；YT=［y1，L，yl］；I—單位矩陣，與 Ω 同階；I1=［1，L，1］T；α=［α1，L，αl］T。

式（4）的約束優(yōu)化問題是[9]：

式中：γ—規(guī)則化因子；ei—誤差變量；φ（xi）—非線性映射，將樣本集從輸入空間映射到高維特征空間。構(gòu)建Lagrange方程，并對(duì)原始優(yōu)化參數(shù)求偏導(dǎo)，整理，可得式（4）[10]。

針對(duì)多分類問題時(shí)，目前主要采用多目標(biāo)優(yōu)化和組合編碼2種方法[4]。一次性求解所有分類參數(shù)的多目標(biāo)優(yōu)化方法，因其求解變量數(shù)目較大，求解過程復(fù)雜，在實(shí)際應(yīng)用中，并不適用。因此，我們主要討論組合編碼方法中的一對(duì)一編碼，構(gòu)造多個(gè)二分類LSSVM來實(shí)現(xiàn)多分類分類。

3 核極化及其特征選擇算法

2005年，文獻(xiàn)[5]借用物理學(xué)概念，提出了核極化度量標(biāo)準(zhǔn)（kernel polarization，KP），即：

式中：k—核矩陣；yyT—理想核矩陣；＜·，·＞F—矩陣之間的Frobenius內(nèi)積。

由式（6）可知：當(dāng)同類樣本點(diǎn)靠近（k（xi，xj）取較大值），異類樣本點(diǎn)遠(yuǎn)離（k（xi，xj）取較小值）時(shí)，可以使核極化值P較大。由此可知，最優(yōu)核參數(shù)fm可以通過最大化P得到，若某一特征x［im］越重要，則fm值越大，對(duì)應(yīng)的Pm值越大。具體的特征選擇算法步驟如下：

步驟 1：初始化 f=diag（1，L，1）；

式中：0．05—學(xué)習(xí)因子，迭代停止條件為fm的相鄰兩次的函數(shù)值之差的絕對(duì)值小于10-5；

步驟3：轉(zhuǎn)步驟2，直至滿足停機(jī)條件；

步驟5：排序fm，并記錄其從大到小的先后順序ftoped；

步驟6：按ftoped的順序，依次增添樣本中的一個(gè)特征量（即選取第一個(gè)，前兩個(gè)，…，所有特征）到LSSVM分類器，進(jìn)行LSSVM的訓(xùn)練和測(cè)試。

我們將核極化優(yōu)化多參數(shù)高斯核的算法和特征選擇聯(lián)合起來考慮，利用核極化獨(dú)立于學(xué)習(xí)算法的優(yōu)勢(shì)來，測(cè)定不同特征對(duì)分類的重要性貢獻(xiàn)，和進(jìn)行樣本的特征選擇，并用LSSVM分類器驗(yàn)證核極化的特征選擇算法的正確性。所提算法的流程圖，如圖1所示。

圖1 算法流程圖Fig．1 The Flow Chat of the Algorithm

4 實(shí)驗(yàn)部分

實(shí)驗(yàn)以LSSVM為載體來驗(yàn)證核極化優(yōu)化多參數(shù)高斯核的特征選擇算法的有效性。實(shí)驗(yàn)環(huán)境為Window7 32位系統(tǒng)，E-450 CPU，2GB RAM以及Matlab 2011a。從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中選取5個(gè)數(shù)據(jù)集，基本屬性如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 The Datasets of Experiments

Heart為二分類數(shù)據(jù)集，Heart包含270個(gè)樣本，一個(gè)樣本含有13個(gè)特征分量，具體特征屬性為：年紀(jì)、性別、胸部疼痛類型、靜息血壓、血清類固醇、空腹血糖、靜息心電圖結(jié)果、最大心率、運(yùn)動(dòng)誘發(fā)的心絞痛、相對(duì)靜止運(yùn)動(dòng)引起的抑郁癥、峰值運(yùn)動(dòng)時(shí)的斜率、主要的血管數(shù)和患者類型。

Australian的數(shù)據(jù)集全稱為Australian Credit Approval，二分類，包含690×14個(gè)樣本。

Wisconsin Breast Cancer Database簡(jiǎn)稱為Breast，二分類：良性（Benign）和惡性（Malignant）。該數(shù)據(jù)原有699個(gè)樣本，因16個(gè)樣本數(shù)據(jù)缺失，故實(shí)驗(yàn)中采用的樣本個(gè)數(shù)為683個(gè)。實(shí)驗(yàn)時(shí)，采用的9個(gè)輸入樣本特征分別為腫塊密度、細(xì)胞大小的均勻性、細(xì)胞形狀的均勻性、邊緣粘連性、單上皮細(xì)胞的大小、裸核、溫和的染色質(zhì)、正常核和有絲分裂等。

Iris是Iris Plants Database的簡(jiǎn)稱，數(shù)據(jù)集為150×4，即包含150個(gè)樣本，每個(gè)樣本含有4個(gè)屬性特征，如萼片和花瓣的長(zhǎng)度等。Iris的類別為setosa、versicolor、virginica 3類，每個(gè)類別有50個(gè)樣本。

Wine為經(jīng)常使用的多分類數(shù)據(jù)集，全稱為Wine Recognition Data，數(shù)據(jù)來源是對(duì)意大利同一地區(qū)不同品種的三種酒的大量研究、分析。Wine數(shù)據(jù)集的數(shù)據(jù)完整，沒有空缺值，大小為178×13，三分類，178個(gè)樣本，每個(gè)樣本具有13個(gè)輸入特征，即酒精、羥基丁二酸、灰燼、灰分堿度、鎂、總酚、黃酮類化合物、非黃酮類物質(zhì)酚類、花青素苷、彩色亮度、色調(diào)、提取稀釋的葡萄酒物質(zhì)和脯氨酸。在數(shù)據(jù)文本“wine.data”中，178行，行代表酒的樣本，其中，第1類：59個(gè)樣本，第2類：71個(gè)樣本，第3類：48個(gè)樣本，即共有178個(gè)樣本；14列，第一列：類標(biāo)志屬性，標(biāo)記為“1”，“2”，“3”等三類；第2列到第14列為樣本輸入特征的樣本值。

4.1 實(shí)驗(yàn)

實(shí)驗(yàn)（a）：對(duì)于每一個(gè)數(shù)據(jù)集，選取樣本的為訓(xùn)練集，剩余樣本的作為測(cè)試集。實(shí)驗(yàn)中，首先，利用第3部分介紹的核極化的特征選擇算法，排列出各個(gè)特征的先后順序和記錄其相應(yīng)的fm值；然后，設(shè)置分類器LSSVM的參數(shù)為：高斯核σ=1，γ=0.06；最后，對(duì)于每添加一個(gè)特征，進(jìn)行LSSVM訓(xùn)練和預(yù)測(cè)，記錄相應(yīng)的預(yù)測(cè)準(zhǔn)確率。實(shí)驗(yàn)結(jié)果，如圖2所示。通過條形圖顯示了Heart數(shù)據(jù)集各個(gè)特征的重要性程度，如圖3所示。

實(shí)驗(yàn)（b）：在數(shù)據(jù)集的所有特征上，進(jìn)行SVM和LSSVM的訓(xùn)練和預(yù)測(cè)，訓(xùn)練集和測(cè)試集的設(shè)置，如圖2（a）所示。分類器的參數(shù)為：高斯核，σ=1，C=100，γ=0.06，進(jìn)行 10 次的獨(dú)立實(shí)驗(yàn)，表 2記錄了10次實(shí)驗(yàn)運(yùn)行時(shí)間的平均值（單位為s），表3記錄了10次實(shí)驗(yàn)分類準(zhǔn)確率的平均值和標(biāo)準(zhǔn)差，表2和表3中的粗體數(shù)值為該設(shè)置參數(shù)下最好的實(shí)驗(yàn)結(jié)果值。表4給出實(shí)驗(yàn)（b）的統(tǒng)計(jì)檢驗(yàn)結(jié)果（在Excel 2007分析工具庫(kù)中，首先，利用“F-檢驗(yàn)：雙樣本方差”判斷兩樣本的總體方差是否相同；然后，若兩總體方差齊，則進(jìn)行“t-檢驗(yàn)：雙樣本等方差假設(shè)”，否則，進(jìn)行“t-檢驗(yàn)：雙樣本異方差假設(shè)”）。

圖2 算法實(shí)驗(yàn)結(jié)果圖Fig.2 Experimental Results of the Algorithm

表2 LSSVM和SVM運(yùn)行時(shí)間的實(shí)驗(yàn)結(jié)果Tab.2 The Running Time of LSSVM and SVM

表3 LSSVM和SVM分類準(zhǔn)確率的實(shí)驗(yàn)結(jié)果Tab.3 The Accuracy of LSSVM and SVM

圖3 Heart數(shù)據(jù)集不同特征的重要性程度Fig.3 The Importance of Different Features on Heart Dataset

4.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)（a）：對(duì)于表1的每個(gè)數(shù)據(jù)集，遵循樣本特征重要性大小的先后的原則，圖2顯示，LSSVM對(duì)于每添加一個(gè)特征的實(shí)驗(yàn)準(zhǔn)確率均有或大或小的提高。具體而言，重要性程度大的特征對(duì)分類貢獻(xiàn)較大，原因是圖像由開始的比較陡峭漸變?yōu)楹髞淼钠椒€(wěn)（如Heart、Australian和Breast數(shù)據(jù)集）。圖3的條形圖說明數(shù)據(jù)集的各個(gè)特征對(duì)分類的貢獻(xiàn)大小是有差異的。實(shí)驗(yàn)（a）的結(jié)果表明，采用核極化的特征選擇方法是有效的。在實(shí)際應(yīng)用中，我們完全可以采用對(duì)分類貢獻(xiàn)率比較大的樣本特征來預(yù)測(cè)樣本，節(jié)省運(yùn)算時(shí)間，提高預(yù)測(cè)效率。

實(shí)驗(yàn)（b）：表2的數(shù)據(jù)表明，在4個(gè)數(shù)據(jù)集的運(yùn)行時(shí)間上，LSSVM明顯都優(yōu)于SVM；在分類準(zhǔn)確率上，如表3數(shù)據(jù)所示，采用LSSVM所達(dá)到的實(shí)驗(yàn)結(jié)果在3個(gè)數(shù)據(jù)集上都優(yōu)于SVM，在Iris和Wine上，2種方法的實(shí)驗(yàn)結(jié)果基本相當(dāng)。為了確保實(shí)驗(yàn)結(jié)果的客觀性，我們對(duì)分類準(zhǔn)確率和運(yùn)行時(shí)間進(jìn)行了顯著性水平為0．05的t假設(shè)統(tǒng)計(jì)檢驗(yàn)，統(tǒng)計(jì)結(jié)果記錄在表4中。就分類準(zhǔn)確率而言，表4的統(tǒng)計(jì)結(jié)果顯示，LSSVM在3個(gè)數(shù)據(jù)集上顯著性差異地優(yōu)于SVM，且在Wine上相對(duì)于SVM沒有顯著性差異；僅在Iris上劣于SVM，但根據(jù)表3的Iris的分類準(zhǔn)確率95．8824（SVM）和94．3137（LSSVM）可知，2種方法所得結(jié)果差異很小。表4的統(tǒng)計(jì)結(jié)果同樣說明，使用LSSVM相比SVM能明顯地提高計(jì)算效率。從實(shí)驗(yàn)（b）的結(jié)果可以判斷，LSSVM作為特征選擇的分類器是高效的。

表4 數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果的t假設(shè)檢驗(yàn)結(jié)果Tab.4 The t Hypothesis Testing of Datasets Experiments

5 結(jié)論

為了解決LSSVM的特征選擇問題，提出了核極化的特征選擇算法，并將選擇出的特征應(yīng)用于LSSVM。UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提的特征選擇算法的有效性和LSSVM分類器計(jì)算的高效性。