一種基于支持向量數(shù)據(jù)描述的特征選擇算法

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1017.005.html

一種基于支持向量數(shù)據(jù)描述的特征選擇算法

曹晉1,2, 張莉1,2, 李凡長(zhǎng)1,2

(1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 江蘇 蘇州 215006； 2.蘇州大學(xué) 計(jì)算機(jī)信息處理技術(shù)省重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006)

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

關(guān)鍵詞：支持向量數(shù)據(jù)描述；特征選擇；遞歸計(jì)算；遞歸特征消除；癌癥識(shí)別；基因表達(dá)

DOI:10.3969/j.issn.1673-4785.201405063

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

收稿日期：2014-06-04. 網(wǎng)絡(luò)出版日期：2015-03-26.

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

作者簡(jiǎn)介：

中文引用格式：曹晉, 張莉, 李凡長(zhǎng). 一種基于支持向量數(shù)據(jù)描述的特征選擇算法[J]. 智能系統(tǒng)學(xué)報(bào)， 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.

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

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

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

1相關(guān)工作

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

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

(1)

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

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

(2)

而半徑R可表示為

(3)

式中：xsv是支持向量，它對(duì)應(yīng)的拉格朗日乘子0<αsv

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

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

1.2.1SVDD-radius-RFE

在文獻(xiàn)[11]中，對(duì)SVDD-radius-RFE的規(guī)劃給出了2種情況：沒有可用的異常數(shù)據(jù)和少量可用的異常數(shù)據(jù)。本文中，僅針對(duì)沒有可用的異常數(shù)據(jù)進(jìn)行討論。

(4)

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

Jr=

(5)

1.2.2SVDD-dual-objective-RFE

(6)

(7)

2基于支持向量數(shù)據(jù)描述的特征選擇算法

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

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

算法1SVDD-RFE

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

6)若m=d，算法結(jié)束；否則轉(zhuǎn)到2)。

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

從表1中可以看出，文中提出的方法得到了最好的平均召回率，另外，表中也給出了幾種方法的運(yùn)行時(shí)間，運(yùn)行時(shí)間是指特征選擇的時(shí)間。很明顯，SVDD-RFE選擇了更好的特征來區(qū)分ALL和AML，同時(shí)在時(shí)間消耗方面比其他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結(jié)束語(yǔ)

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

參考文獻(xiàn):

[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]王儉臣, 單甘霖, 張岐龍, 等. 基于改進(jìn) SVM-RFE 的特征選擇方法研究[J]. 微計(jì)算機(jī)應(yīng)用, 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年生，碩士研究生，主要研究方向?yàn)槟Ｊ阶R(shí)別與人工智能。

張莉，女，1975年生，教授，博士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與模式識(shí)別。發(fā)表學(xué)術(shù)論文70篇，合著著作3部，主持國(guó)家和省自然科學(xué)基金項(xiàng)目5項(xiàng)。

李凡長(zhǎng)，男，1964年生，教授，博士生導(dǎo)師，主要研究方向?yàn)槿斯ぶ悄?、機(jī)器學(xué)習(xí)等。先后承擔(dān)國(guó)家自然科學(xué)基金重點(diǎn)、面上及省級(jí)項(xiàng)目8項(xiàng)，獲省級(jí)科技獎(jiǎng)2項(xiàng)，發(fā)表學(xué)術(shù)論文150余篇，出版專著7部。