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

王方紅，黃文彪

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

?

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

王方紅，黃文彪

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

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

關鍵詞：機器學習；特征選擇；支持向量機；權重向量

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

1SVM特征選擇方法

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

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

在線性可分情況下，構建最優超平面，使得平行于分類面H的H1和H2之間的分類間隔最大，就轉化為下面的二次規劃問題：

(1)

求解這個最優化問題得到了權重向量ω和常數b，構造決策函數為

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

(2)

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

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

步驟2將數據代入線性支持向量機最優化的求解過程，得到權重向量ω.

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

2TWSVM和 LFTWSVM特征選擇方法

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

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

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

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

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

(3)

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

(4)

(5)

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

因此，TWSVM求解的是一對最優化問題：

(6)

(7)

這個最優化問題求解得到的是兩個分類超平面、兩個權重向量ω1和ω2.該TWSVM的決策函數為

(8)

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

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

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

步驟2用十折交叉驗證法求得TWSVM的最優參數，并用所得的最優參數進行TWSVM的訓練，由此獲得兩個權重向量ω1和ω2.

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

3數據實驗及結果分析

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

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

表1　兩種方法數據實驗結果

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

4結論

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

參考文獻：

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

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

[3]鄧乃揚,田英杰.數據挖掘中的新方法——支持向量機[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—)，女，浙江路橋人，助理實驗師，研究方向為機器學習與數據挖掘，E-mail：390425074@qq.com.

中圖分類號：O232

文獻標志碼：A

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