孿生支持向量機的特征選擇研究

王方紅，黃文彪

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

?

孿生支持向量機的特征選擇研究

王方紅，黃文彪

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

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

關鍵詞：機器學習；特征選擇；支持向量機；權(quán)重向量

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

1SVM特征選擇方法

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

圖1　線性可分兩類點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ù)中所起到的作用就越大，因此可以利用線性支持向量機中的權(quán)重向量進行特征選擇，具體算法如下[10]：

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

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

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

2TWSVM和 LFTWSVM特征選擇方法

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

圖2　線性不可分兩類點Fig.2　Linear non separable two kinds of points

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

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

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

(3)

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

(4)

(5)

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

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

(6)

(7)

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

(8)

該式的意義為樣本點距離哪個分類超平面距離較近則該樣本點就歸屬于相應的類別.

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

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

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

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

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

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

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

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

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

4結(jié)論

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

參考文獻：

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

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

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

[4]張麗新,王家欽,趙雁南,等.機器學習中的特征選擇[J].計算機科學，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]楊志民,劉廣利.不確定行支持向量機——算法及應用[M].北京：科學出版社，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.

(責任編輯：陳石平)

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ù)據(jù)挖掘，E-mail：390425074@qq.com.

中圖分類號：O232

文獻標志碼：A

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