一種基于支持向量數據描述的特征選擇算法

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1017.005.html

一種基于支持向量數據描述的特征選擇算法

曹晉1,2, 張莉1,2, 李凡長1,2

(1.蘇州大學 計算機科學與技術學院, 江蘇 蘇州 215006； 2.蘇州大學 計算機信息處理技術省重點實驗室，江蘇 蘇州 215006)

摘要：已有基于支持向量數據描述的特征選擇方法計算量較大，導致特征選擇的時間過長。針對此問題，提出了一種新的基于支持向量數據描述的特征選擇算法。新方法的特征選擇是通過超球體球心方向上的能量大小來決定且采用了遞歸特征消除方式來逐漸剔除掉冗余特征。在Leukemia數據集上的實驗結果表明，新方法能夠進行快速的特征選擇，且所選擇的特征對后續的分類是有效的。

關鍵詞：支持向量數據描述；特征選擇；遞歸計算；遞歸特征消除；癌癥識別；基因表達

DOI:10.3969/j.issn.1673-4785.201405063

中圖分類號：TP391文獻標志碼：A

收稿日期：2014-06-04. 網絡出版日期：2015-03-26.

基金項目：國家自然科學基金資助項目(61373093, 61033013)；江蘇省自然科學基金資助項目(BK2011284, BK201222725，BK20140008)；江蘇省高校自然科學研究基金資助項目(13KJA520001).

作者簡介：

中文引用格式：曹晉, 張莉, 李凡長. 一種基于支持向量數據描述的特征選擇算法[J]. 智能系統學報， 2015, 10(2): 215-220.

英文引用格式：CAO Jin, ZHANG Li, LI Fanzhang. A noval support vector data description-based feature selection method [J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 215-220.

A noval support vector data description-based feature selection method

CAO Jin1, 2, ZHANG Li1, 2, LI Fanzhang1, 2

(1. Department of Computer Science and Technology, Soochow University, Suzhou 215006, China； 2. Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006, China)

Abstract：There have been proposed feature selection methods based on support vector data description (SVDD), or SVDD-radius-RFE and SVDD-dual-objective-RFE. These methods are time consuming due to the high computational complexity. To remedy it, a support vector data description-based feature selection method is proposed, ie SVDD-RFE. In this method, feature elimination depends on the energy of directions in the center of hypersphere. In addition, a scheme of recursive feature elimination (RFE) is introduced to iteratively remove irrelevant features. Experimental results on the Leukemia dataset showed that this method has fast speed for feature selection， and the selected features are efficient for subsequent classification tasks.

Keywords：support vector data description; feature selection; recursive computation; recursive feature elimination; cancer recognition; gene expression

通信作者：曹晉.E-mail: 20134527007@stu.suda.edu.cn.

特征選擇是機器學習、模式識別、醫療診斷等領域的一個研究熱點。特征選擇是一種重要的數據處理方法，從很多輸入特征集中選擇一個重要特征的子集并且移除不相關或不重要的特征，使留下的特征具有更強的分辨率。本文研究重點是基于支持向量機(support vector machine, SVM)的特征選擇方法，也就是把SVM引入到特征選擇過程中。基于SVM的特征選擇算法分為3類：基于SVM的Wrapper特征選擇算法、基于SVM的Embedded特征選擇算法和基于SVM的Filter與Wrapper的混合特征選擇算法。Weston等提出的基于SVM的Wrapper特征選擇算法是去尋找能最小化泛化誤差邊界的特征，這種尋找可以通過梯度下降來實現[1]。Guyon等提出的SVM-RFE(recursive feature elimination)是這種算法中最具代表性的一個[5]。針對傳統SVM-RFE特征選擇算法中SVM參數(軟間隔參數γ和懲罰因子C)難以確定的問題，王儉臣等[2]采用粒子群算法搜索SVM的參數，并且將特征向量映射到SVM參數γ確定的核空間中去進行特征選擇，這樣就有效地將特征選擇與SVM分類器關聯起來。但該方法由于采用序列向后搜索，具有較高的時間復雜度。Li等[3]提出的基于SVM的Embedded特征選擇算法同時實現了分類與特征選擇。該方法通過引入數據驅動權重，從而自適應地辨別出重要特征。此外，重要特征的系數偏差也大大減少。但是該方法有較多的參數設置，算法在很大程度上依賴于參數的調整。Lee等[4]提出了基于SVM的Filter與Wrapper的混合特征選擇算法，并將其應用在微陣列數據分析中。此方法首先用動態參數設置的遺傳算法產生大量的特征子集，然后根據特征子集中出現的頻率來選擇特征，最后選擇一定數量的排序靠前的特征。

對平衡的數據集來說，采用SVM的方法來進行特征選擇是非常合適的。但是當數據集本身具有不平衡性時，再采用SVM方法就不太合適了。針對這個問題，Jeong等[11]提出了2種基于支持向量數據描述(support vector data description, SVDD)的特征選擇算法：SVDD-radius-RFE和SVDD-dual-objective-RFE。支持向量數據描述也稱為1類SVM方法，這里沿用文獻[11]的術語。SVDD-radius-RFE方法可以用來最小化描述正常樣本的邊界，這個邊界通過半徑的平方來衡量。SVDD-dual-objective-RFE方法可得到SVDD對偶空間的一個緊致描述，這個描述可通過最大化SVDD對偶目標函數得到。然而，這2種方法在樣本維數較高時，時間復雜度會非常大。

為此，提出了一種新的基于支持向量數據描述的特征選擇算法。在新的方法中，依據超球體球心向量上的方向能量大小來消除特征。若在某些方向上的能量較小，就會消除此方向所對應的特征。在基因數據集上的實驗結果證明了新方法SVDD-RFE方法獲得了更精確的分類性能和更少的時間消耗。

1相關工作

1.1支持向量數據描述(SVDD)

SVDD是一種描述目標數據分布的方法，也稱為1類SVM[6-8]。SVDD與SVM唯一的不同就是，僅允許從一類數據中去學習。SVDD有2種版本。一種是支持向量描述超平面的方法[7]。這種方法的線性版本是將原點視為異常點，使得最優超平面盡可能遠離原點。另一種是Tax和Duin提出的超球面的SVDD方法[6,8]。此外，Campbell和Bennett提出了基于線性規劃的SVDD方法[9]。Zhang等[13]提出了一種改進的SVDD方法，適用于線性非圓數據描述的情況。在文獻[10]中，Zhang等將數據描述方法引入到了隱空間，這是一種廣義的非線性數據描述方法。

(1)

式中：αi是拉格朗日乘子，C>0是懲罰因子。

超球體的球心a可以用拉格朗日乘子表示為

(2)

而半徑R可表示為

(3)

式中：xsv是支持向量，它對應的拉格朗日乘子0<αsv

1.2基于SVDD的2種特征選擇方法

這里簡單地介紹一下已有的基于SVDD的特征選擇方法，即SVDD-radius-RFE和SVDD-dual-objective-RFE特征選擇方法[11]。

1.2.1SVDD-radius-RFE

在文獻[11]中，對SVDD-radius-RFE的規劃給出了2種情況：沒有可用的異常數據和少量可用的異常數據。本文中，僅針對沒有可用的異常數據進行討論。

(4)

式中：t是支持向量的個數。引入線性核函數后，準則函數(4)可以表示為

Jr=

(5)

1.2.2SVDD-dual-objective-RFE

(6)

(7)

2基于支持向量數據描述的特征選擇算法

本節提出了一種新的基于支持向量數據描述的特征選擇算法，即SVDD-RFE。

注意算法1中的F是已選特征的索引集合，也意味著這些特征已保留下來。本算法旨在特征的選擇和得到較少特征的數據集合。對于最后得到的數據集，任何分類器，都可以用來建立分類模型。

算法1SVDD-RFE

輸出:被選擇特征的索引集合F。

6)若m=d，算法結束；否則轉到2)。

3 實驗結果

在DNA微陣列的基因表達數據集上進行實驗，要驗證SVDD-RFE算法的正確性和有效性。實驗數據集是Leukemia數據集。在Leukemia數據集中，有2種不同種類的白血病，急性淋巴細胞性白血病(acute lymphoblastic leukemia，ALL) 和急性骨髓性白血病(acute myeloid leukemia，AML)。

數據集被劃分為2個子集：訓練集和測試集。訓練集用來選擇基因和調整分類器權重，測試集用來估計分類性能。訓練集有38個樣本(27個ALL和11個AML)，測試集有34個樣本(20個ALL和14個AML)。所有樣本有7129個特征，對應于從微陣列圖像中提取出的歸一化基因表達值。本實驗中，將ALL視為目標樣本，AML視為負類樣本。本數據集可從文獻[12]中得到。本實驗中的所有方法是從7129個特征中選取100個重要特征，并且僅有參數C需要設置。接下來的實驗中，將會討論已選特征的好壞，然后去衡量分類精度的性能。

本實驗的對比方法有SVM-RFE、SVDD-radius-RFE、SVDD-dual-objective- RFE以及SVDD-RFE。用KNN(nearest neighbor)分類器來衡量選擇的特征是否合適。KNN由于其簡單性和有效性成為一種很方便的分類器，它的核心思想是在訓練集合中找到距離測試樣本點最近的k個點，然后將該測試樣本點的類別設置為k個點中數量最多類的類別標簽。

因為選擇KNN作為分類器，參數k的選擇對分類精度有一定影響。出于運行時間上的考慮，僅對SVM-RFE和SVDD-RFE做了參數k的比較。令k從1～10變化，同時分別令SVM-RFE中C=100，在SVDD-RFE 中C=0.1。圖1給出了2種算法在不同k值下的分類精度變化曲線。

圖1　分類精度的變化 Fig.1　The accuracy with the change

表1　4種特征選擇方法和不做特征選擇的性能比較

從表1中可以看出，文中提出的方法得到了最好的平均召回率，另外，表中也給出了幾種方法的運行時間，運行時間是指特征選擇的時間。很明顯，SVDD-RFE選擇了更好的特征來區分ALL和AML，同時在時間消耗方面比其他3種方法都要少很多，尤其是與SVDD-radius-RFE和SVDD-dual-objective- RFE方法相比。

(a) 原始圖像

(b)退化仿真圖像(SVM-RFE)

(c)退化仿真圖像(SVDD-radius-RFE)

(d)退化仿真圖像(SVDD-dual-objective-RFE) 圖2　 原始圖像和退化仿真圖像 Fig.2　Original image and simulated degraded image

4結束語

文中提出了一種新的基于支持向量數據描述的特征選擇算法，并且將其用于癌癥分類。該算法可以輕松處理小樣本、多特征的分類問題，也可以在消除特征冗余的同時實現特征選擇。更重要的是，該算法不僅得到了更為緊湊、更具有分辨能力的基因子集，還具有更好的穩定性和有效性。在Leukemia數據集上的實驗驗證了算法的正確性。實驗中，用KNN分類器來衡量特征選擇的性能。在Leukemia數據集上，SVDD-RFE方法選擇的特征集合不僅具有最好的分辨力，時間消耗也最少。未來工作中，將運用SVDD的特征選擇，進一步提高分類率。

參考文獻:

[1]WESTON J, MUKHERJEE S, CHAPELLE O, et al. Feature selection for SVMs[C]//Proc of Neural Information Processing Systems. Denver, USA: 2000: 668-674.

[2]王儉臣, 單甘霖, 張岐龍, 等. 基于改進 SVM-RFE 的特征選擇方法研究[J]. 微計算機應用, 2011, 32(2): 70-74.

WANG Jianchen, SHAN Ganlin, ZHANG Qilong,et al. Research on feature selection method based on improved SVM -RFE[J]. Microcomputer Applications, 2011, 32(2): 70-74.

[3]LI Juntao, JIA Yingmin, LI Wenlin. Adaptive huberized support vector machine and its application to microarray classification[J]. Neural Computing and Applications, 2011, 20(1): 123-132.

[4]LEE C, LEU Y. A novel hybrid feature selection method for microarray data analysis[J]. Applied Soft Computing, 2011, 11(1): 208-213.

[5]GUYON I, WESTON J, BARNHILL S, et al. Gene selection for cancer classification using support vector machines[J]. Machine Learning, 2002, 46(1/2/3): 389-422.

[6]TAX D M J, ROBERT PW D. Support vector domain description[J]. Pattern Recognition Letters, 1999, 20(11): 1191-1199.

[7]SCHIILKOPP B, BURGEST C, VAPNIK V. Extracting support data for a given task[C]//Proceedings of First International Conference on Know ledge Discovery and Data mining.1995: 262-267.

[8]TAX D M J, DUIN R P W. Data domain description using support vectors[C]//ESANN. Facto, Brussels, 1999: 251-256.

[9]BENNETT C C K P. A linear programming approach to novelty detection[C]//Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference. Boston： MIT Press, 2001, 13: 395-401.

[10]ZHANG Li, WANG Bangjun, LI Fanzhang, et al. Support vector novelty detection in hidden space[J]. Journal of Computational Information Systems, 2011(7): 1-7.

[11]JEONG Y S, KONG I H, JEONG M K, et al. A new feature selection method for one-class classification problems[J]. Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2012, 42(6): 1500-1509.

[12]ARMSTRONG S A, STAUNTON J E, SILVERMAN L B, et al. MLL translocations specify a distinct gene expression profile that distinguishes a unique leukemia[J]. Nature Genetics, 2002, 30(1): 41-47.

[13]ZHANG Li, ZHOU Weida, LIN Yin, et al. Support vector novelty detection with dot product kernels for non-spherical data[C]//Proceedings of the 2008 IEEE International Conference on Information and Automation. Zhangjiajie, China, 2008: 41-46.

曹晉，女，1991年生，碩士研究生，主要研究方向為模式識別與人工智能。

張莉，女，1975年生，教授，博士，主要研究方向為機器學習與模式識別。發表學術論文70篇，合著著作3部，主持國家和省自然科學基金項目5項。

李凡長，男，1964年生，教授，博士生導師，主要研究方向為人工智能、機器學習等。先后承擔國家自然科學基金重點、面上及省級項目8項，獲省級科技獎2項，發表學術論文150余篇，出版專著7部。