王方紅，黃文彪

(浙江工業(yè)大學(xué) 之江學(xué)院，浙江 杭州 310024)

?

孿生支持向量機(jī)的特征選擇研究

王方紅，黃文彪

(浙江工業(yè)大學(xué) 之江學(xué)院，浙江 杭州 310024)

摘要：針對機(jī)器學(xué)習(xí)中數(shù)據(jù)分類的特征選擇問題，提出了孿生支持向量機(jī)( Twin support vector machine, TWSVM)的另一種方法：LFTWSVM.首先求解TWSVM優(yōu)化問題后將得到兩個權(quán)重向量，先將這兩個權(quán)重向量進(jìn)行歸一化處理，再把處理后的兩個權(quán)重向量取絕對值相加，得到一個總權(quán)重向量，最后將總權(quán)重向量進(jìn)行特征選擇.通過實(shí)驗(yàn)，將得到的數(shù)據(jù)結(jié)果和TWSVM特征選擇方法進(jìn)行比較，LFTWSVM特征選擇方法具有一定的優(yōu)勢.

關(guān)鍵詞：機(jī)器學(xué)習(xí)；特征選擇；支持向量機(jī)；權(quán)重向量

支持向量機(jī)作為機(jī)器學(xué)習(xí)的一種算法，已得到廣泛應(yīng)用，如人體姿態(tài)識別[1]、ATM機(jī)異常行為識別[2]等，而支持向量機(jī)算法中的特征選擇對于機(jī)器學(xué)習(xí)來說是非常重要的[3].在機(jī)器學(xué)習(xí)過程中，所用到的特征可以有幾百，甚至幾千，這對于算法中的運(yùn)算量是十分龐大的.近幾年的研究顯示一些機(jī)器學(xué)習(xí)算法受不相關(guān)和冗余特征的負(fù)面影響，如利用那些對分類問題作用不大或者那些對該分類問題起到相反作用的特征不僅加大了運(yùn)算的計(jì)算量，耗費(fèi)運(yùn)算時間，而且還降低了模型的準(zhǔn)確率，使得學(xué)習(xí)的意義相對較小.所以，對某個學(xué)習(xí)算法通過訓(xùn)練樣本進(jìn)行預(yù)測未知樣本之前，得先確定哪些特征需采用，而哪些特征需被刪除，這就是特征選擇的意義之所在[4-5].前幾年，Jayadeva等提出了一種新的分類方法——孿生支持向量機(jī)(TWSVM)[6]，此分類方法是尋求兩個非平行的分類超平面，要求每個超平面離一類數(shù)據(jù)點(diǎn)盡可能的近，而距離另外一類數(shù)據(jù)點(diǎn)盡可能的遠(yuǎn)，此分類方法的運(yùn)算量僅為傳統(tǒng)的支持向量機(jī)的四分之一[7].在適合用TWSVM來進(jìn)行分類的模型中，目前尚無有效的特征提取算法提出[8].在此利用TWSVM的方法結(jié)合標(biāo)準(zhǔn)支持向量機(jī)(Support vector machine，SVM)的特征選擇思想，構(gòu)造了基于TWSVM的特征選擇方法LFTWSVM(Lable fold twin support vector machine，LFTWSVM)，且給出了算法.此算法的主要思想是利用兩個權(quán)重向量，這兩個權(quán)重向量分別是正負(fù)兩類訓(xùn)練集的指導(dǎo)，相對于SVM的特征選擇方法中的單一權(quán)重向量多了一層考慮.

1SVM特征選擇方法

在圖1中，空心點(diǎn)和實(shí)心點(diǎn)分別代表兩類樣本，中間的H表示最優(yōu)分類超平面，H1，H2分別表示平行于H的分類面，它們之間的距離就是分類間隔.所謂最優(yōu)分類面即要求分類面不僅僅可以把兩類正確分開，并且使分類間隔達(dá)到最大[9].

圖1　線性可分兩類點(diǎn)Fig.1　Linear separable two kinds of points

在線性可分情況下，構(gòu)建最優(yōu)超平面，使得平行于分類面H的H1和H2之間的分類間隔最大，就轉(zhuǎn)化為下面的二次規(guī)劃問題：

(1)

求解這個最優(yōu)化問題得到了權(quán)重向量ω和常數(shù)b，構(gòu)造決策函數(shù)為

f(x)=sgn((ω·x)+b)

(2)

在權(quán)重向量ω中，每個分量代表的是各自特征在決策函數(shù)中所起到的權(quán)重值，若ω中的某個分量|ωj|絕對值越大，則該第j個特征在決策函數(shù)中所起到的作用就越大，因此可以利用線性支持向量機(jī)中的權(quán)重向量進(jìn)行特征選擇，具體算法如下[10]：

步驟1輸入數(shù)據(jù)X,Y，將X進(jìn)行歸一化處理.

步驟2將數(shù)據(jù)代入線性支持向量機(jī)最優(yōu)化的求解過程，得到權(quán)重向量ω.

步驟4保留所記錄的特征，刪去沒被累加的特征.

2TWSVM和 LFTWSVM特征選擇方法

TWSVM的分類原理是尋找兩條不平行的分類超平面，使得一條分類超平面與兩類樣本點(diǎn)的其中一類點(diǎn)最接近，同時與另一類點(diǎn)的距離盡可能的遠(yuǎn)[5]，如圖2所示.

圖2　線性不可分兩類點(diǎn)Fig.2　Linear non separable two kinds of points

圖2中的樣本點(diǎn)有較多是交叉混淆在一起的，如果利用SVM來進(jìn)行分類，必定有較多的樣本點(diǎn)被錯分，導(dǎo)致分類效果不佳.TWSVM與SVM主要區(qū)別是：TWSVM解決的是兩個二次規(guī)劃問題，然而SVM解決的是一個二次規(guī)劃問題.

在TWSVM中，首先假設(shè)全部屬于+1類的樣本點(diǎn)記為A∈Rm1×n，在這第i行表示的是一個樣本點(diǎn)；類似地，B∈Rm2×n代表屬于-1類的樣本.然后對兩類樣本點(diǎn)進(jìn)行擬合求出最優(yōu)的分類超平面，因此要將樣本點(diǎn)進(jìn)行歸類.

與SVM不同的是，TWSVM尋找一對不平行的分類超平面：

(3)

使得每條分類超平面與一類點(diǎn)距離較近，而與另一類樣本點(diǎn)的距離較遠(yuǎn)，此處ω1∈Rn，ω2∈Rn，b1∈R以及b2∈R.這里經(jīng)驗(yàn)風(fēng)險計(jì)算式為

(4)

(5)

式中：c1>0，c2>0為參數(shù)；e1，e2為相應(yīng)維數(shù)的全1向量.

因此，TWSVM求解的是一對最優(yōu)化問題：

(6)

(7)

這個最優(yōu)化問題求解得到的是兩個分類超平面、兩個權(quán)重向量ω1和ω2.該TWSVM的決策函數(shù)為

(8)

該式的意義為樣本點(diǎn)距離哪個分類超平面距離較近則該樣本點(diǎn)就歸屬于相應(yīng)的類別.

下面將LFTWSVM的特征選擇方法的算法介紹如下：

步驟1輸入數(shù)據(jù)X,Y，將X進(jìn)行歸一化處理并且將X分成正負(fù)兩類A，B.

步驟2用十折交叉驗(yàn)證法求得TWSVM的最優(yōu)參數(shù)，并用所得的最優(yōu)參數(shù)進(jìn)行TWSVM的訓(xùn)練，由此獲得兩個權(quán)重向量ω1和ω2.

步驟4刪除沒有被累加的特征，保留被累加的特征.

3數(shù)據(jù)實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證LFTWSVM的特征選擇方法的可行性，采用了UCI[11]機(jī)器學(xué)習(xí)資源庫的數(shù)據(jù)進(jìn)行數(shù)據(jù)實(shí)驗(yàn).此次實(shí)驗(yàn)在Pentium(R) Dual-Core 2.80 GHz處理器、2 GB內(nèi)存以及Matlab7.0仿真軟件的計(jì)算機(jī)上進(jìn)行的.

該實(shí)驗(yàn)的主要過程是將同一個數(shù)據(jù)運(yùn)用未經(jīng)過特征選擇的TWSVM方法以及筆者提出的LFTWSVM方法進(jìn)行模型選參，十折交叉驗(yàn)證最優(yōu)準(zhǔn)確率，并將所得到的結(jié)果做兩個方面的實(shí)驗(yàn)比較：使用的特征數(shù)量和最優(yōu)準(zhǔn)確度，如表1所示.

表1　兩種方法數(shù)據(jù)實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)中閾值α取0.9.從表1中可以看到： LFTWSVM特征選擇方法確實(shí)刪去了冗余的特征，并且獲得了更好的分類效果.例如：對于Australian這組數(shù)據(jù)，采用LFTWSVM特征選擇的方法準(zhǔn)確率為84.93%，所用到的特征數(shù)量只有9個，但是TWSVM特征選擇方法利用了數(shù)據(jù)集的所有特征，卻只有83.76%的準(zhǔn)確率，LFTWSVM特征選擇方法明顯優(yōu)于TWSVM的特征選擇方法.

4結(jié)論

利用求解SVM得到的權(quán)重向量進(jìn)行特征選擇的原理，將此方法運(yùn)用到TWSVM的模型中.把求解TWSVM得到的兩個權(quán)重向量進(jìn)行歸一化后取絕對值相加的方法進(jìn)行合并，獲取了另一個權(quán)重向量，接著提出了LFTWSVM特征選擇算法，經(jīng)過理論分析和實(shí)驗(yàn)數(shù)據(jù)的驗(yàn)證，我們可以看出LFTWSVM的特征選擇方法不僅刪除了冗余的特征，且獲得了較好的準(zhǔn)確率.

參考文獻(xiàn)：

[1]鄭莉莉,黃鮮萍,梁榮華.基于支持向量機(jī)的人體姿態(tài)識別[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2012，40(6)：670-675.

[2]陳敏智,湯一平.基于支持向量機(jī)的針對ATM機(jī)的異常行為識別[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2010，38(5)：546-551.

[3]鄧乃揚(yáng),田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)[M].北京：科學(xué)出版社，2004：348-350.

[4]張麗新,王家欽,趙雁南,等.機(jī)器學(xué)習(xí)中的特征選擇[J].計(jì)算機(jī)科學(xué)，2004，31(11)：180-184.

[5]TAN J Y, ZHANG Z Q, ZHEN L, et al. Adaptive feature selection via a new version of support vector machine[J]. Neural computing and applications，2013，23(3/4)：937-945.

[6]SHAO Yanhai, DENG Naiyang, CHEN Weijie, et al. Improved generalized eigenvalue proximal support vector Machine[J]. IEEE signal processing letters,2013,20(3):213-216.

[7]SHAO Yanhai, WANG Zhen, CHEN Weijie, et al. A regularization for the projection twin support vector machine[J]. Knowledge-based systems,2013,37:203-210.

[8]SHAO Yanhai, ZHANG Chunhua, WANG Xiaobo, et al. Improvements on twin support vector machines[J]. IEEE transactions on neural networks，2011，22(6)：962-968.

[9]楊志民,劉廣利.不確定行支持向量機(jī)——算法及應(yīng)用[M].北京：科學(xué)出版社，2012：56-60.

[10]CHEN Yiwei, LIN C H. Combine SVMs with various feature selection strategies[J]. Studies in fuzziness and soft computing,2006,207:315-324.

[11]ISABELLE G, JASON W, STEPHEN B, et al. Gene selection for cancer classification using support vector machines[J]. Machine learning,2002,46:389-422.

(責(zé)任編輯：陳石平)

Research on feature selection of twin support vector machine

WANG Fanghong, HUANG Wenbiao

(Zhijiang College, Zhejiang University of Technology, Hangzhou 310024, China)

Abstract:Aiming at the feature selection problem of data classification in machine learning a new method of twin support vector machine(TWSVM) is proposed: LFTWSVM Firstly, two weight vectors can be gotten after the SVM optimization problem is solved. Then, these two weight vectors will be normalized, and be summed together with their absolute values. A total weight vector can be gotten and features will be selected from the total weight vector. The experiments show that the feature selection method in LFTWSVM has rather advantages compared with the TWSVM.

Keywords:machine learning; feature selection; support vector machine; weight vector

收稿日期：2015-10-12

作者簡介：王方紅(1981—)，女，浙江路橋人，助理實(shí)驗(yàn)師，研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘，E-mail：390425074@qq.com.

中圖分類號：O232

文獻(xiàn)標(biāo)志碼：A

文章編號：1006-4303(2016)02-0146-04