1 SVM 2RFE特征选择算法
111 SVM SVM 作为一个有效的分类工具 ,最近几年被广
泛应用于模式识别领域 ,它在解决小样本及高维模 式识别问题中表现出许多特有的优势 [ 21 - 22 ] 。 SVM 最初设计为解决两类样本问题 。算法寻求最优分
类面 ( hyperp lane) w x + b = 0 (w 为最优超平面的权 系数向量 , b为分类阈值 ) ,使得分类面不但能将两 类样本无错误地分开 , 而且使两类的分类间隔最 大 。两类之间的分类间隔为 2 / ‖w ‖[ 23 ] 。
29 卷 1 期 2010年 2月
中 国 生 物 医 学 工 程 学 报 Ch inese J ou rna l of B iom ed ica l Eng ineering
Vol. 29 No. 1 Feb rua ry 2010
基于 SVM 2RFE2SFS的基因选择方法
游 伟 李树涛 3 谭明奎
对于线性不可分数据 , SVM 通过引用映射函 数 ,将输入向量映射到一个高维的特征向量空间 , 从而在高维空间中寻求最优分类面 , 实现线性可 分 。判别函数为
l
∑ f ( x) = sgn
α i
yi
K(ຫໍສະໝຸດ xix)+b
(1)
i =1
式中 , sgn{ }为符号函数 ; xi 为训练样本 , i = 1, 2,
( College of E lectrica l and Inform ation Eng ineering, Hunan U niversity, Changsha 410082, Ch ina)
Abstract: M icroarray data usually contain a large quantity of irrelevant, noisy and redundant genes which may seriously deteriorate the p rediction accuracy. In addition, m icroarray data often encounter p roblem s of less samp les and multi2dimensions, which raises many difficulties in cancer diagnosis. In this article, we p roposed a new method for gene selection, combining recursive feature elim ination (RFE) and sequential forward selection ( SFS) based on support vector machine ( SVM ) . The ranking score of each gene was calculated by using SVM. The information of first order difference of the ranking scores was used to divide the genes into some group s. The group with the smallest score was elim inated, while the group with the largest score was selected. Analysis results with real2life benchmark datasets of leukem ia, colon, and breast demonstrate the high effectiveness and efficiency of the p roposed method.
原始 的 SVM 2RFE ( original SVM 2RFE, O 2SVM 2 RFE)每次只消去一个噪声基因 ,这使得它要承受巨 大的计算负担 。为了加快 SVM 2RFE 的运行效率 , 有些方法每次消去数个而不只一个基因 [ 18 - 19 ] ,如每 次消去剩余基因的一半被称作 H 2SVM 2RFE ( half SVM 2RFE) 。这些方法加快了运行速度 ,但是有可 能降低分类效果 [ 15, 20 ] ,并且没有相关理论表明每次 应消去多少个基因才能保证分类结果最优 。
doi: 10. 3969 / j. issn. 025828021. 2010. 01. 015 收稿日期 : 2009206219, 修回日期 : 2009210212 基金项目 :教育部新世纪优秀人才支持计划项目 (NECT22005) ;湖南省杰出青年基金项目 (06JJ1010) 3 通讯作者 。 E2mail: shutao_li@ yahoo. com. cn
基于此 ,本研究提出一种新的 SVM 2RFE2SFS方 法 ,在保证分类性能的同时 ,解决 O 2SVM 2RFE计算 繁重的问题 。首先 ,根据基因的排序准则分数的一 阶差分 ,把基因分成若干小组 。然后 ,对排序准则 分数值最小的基因组进行 RFE 处理 ,消去噪声基 因 ;同时 ,对排序准则分数值最大的基因组进行 SFS 选择 ,选取有效的信息基因 。为了验证本方法的理 论性及实时性 ,在白血病 、结肠癌 、乳腺癌数据集上 进行了相应的实验 。结果表明 ,经本方法进行的基 因选择 , 较 之 O 2SVM 2RFE 方法 , 分类 速度 明显 加 快 ,并且分类能力提高 。
数据进行诊断和应用是不可靠的 。因此 ,从中挑选 出具有最佳分类能力的基因 (即有效信息基因 )是 十分有必要的 [ 4 - 5 ] ,此过程即为基因选择 。
近年来 ,国内外学者已提出了不少用于基因选 择的 方 法 , 具 体 可 分 为 两 类 ———Filter 方 法 和 W rapper方法 [ 6 ] 。用 Filter方法进行基因选择与分 类器无关 ,各种统计学方法 (如 t检验 [ 7 ] 、W ilcoxon 秩检验 [ 8 ]等 )都是 Filter方法 。 Filter方法可以同时 处理大量数据 ,具有处理速度快的优点 ,缺点是只
Key words: gene selection; support vector machine; recursive feature elim ination; sequential forward selection
引言
基因微阵列技术能同时测量数以万计的基因 表达谱数据 ,这对在基因级别上研究疾病的发病机 理 、肿瘤的诊断 、基因药物的研制等都具有重要的 应用价值 [ 1 - 3 ] 。但是 ,基因表达数据存在样本少 、维 数高的问题 ,增加了肿瘤诊断的难度 ;另外 ,在基因 微阵列的高维数据中 , 大量的数据通常为冗余信 息 ,即存在大量的噪声基因 ,因而 ,用原始的微阵列
ci = (w i ) 2
(2)
SVM 2RFE特征选择算法为
输入 :训练样本 X0 = [ x1 , x2 , …, xl ]T ,类标签 y
用 ,实现在错分样本的比例与算法复杂度之间的折
中 ,在多数情况下 ,αi = 0,所对应的样本就称为支持 向量 ( SV ) 。
112 序列后向选择方法和序列前向选择方法
序 列 后 向 选 择 方 法 ( sequential backward
selection, SB S ) 和 序 列 前 向 选 择 方 法 ( sequential
这两种方法都产生嵌套的基因集合 。
113 SVM 2RFE Guyon证明 , SVM 2RFE比原先已有的基因选择
方法的分类能力有显著的提升 [ 14 ] 。该方法在运行
之初假定整个基因集合就是所需要的优化特征集 , 而后在算法的每一步运行中删除一个排序准则分
数最小的基因 ,显然 RFE 是一个 SB S过程 [ 26 ] 。基 因的排序准则分数为 [ 27 ]
forward selection, SFS)都是用于基因选择的搜索策
略方法 [ 24 ] 。在序列后向选择方法中 ,刚开始所需要
的特征集合假定是整个基因集 ,然后每次消去最差
的一个基因 [ 25 ] ;与之相反 ,序列前向选择方法把所
需要的特征集合初始化为一个空集 ,每次向特征集
合增加一个最好的基因 ,直到达到最后的特征集 。
…, l; yi ∈ { + 1, - 1} 为相应的类别标签 ; x为待分
类的样本 ; K ( xi x) 为核函数 ,常用的有 Polynom ial核
函 数 、Gaussian
核 函 数 、Sigmoid
核
函
数
;
α i
为
Lagrange系数 ,且有 0≤αi ≤C, C 为指定的常数 ,称
作惩罚参数 , 起到控制对错分样本惩罚程度的作
© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved.
94
中 国 生 物 医 学 工 程 学 报
29卷
能够对单个基因的分类重要性进行衡量 ,隐含要求 模式是线性可分的 。而在生物过程中 ,往往是通过 多个基因的复杂组合来表达特异性的 ,因此用 Filter 方法会带来较大误差 ,一般用在数据预处理阶段 , 可以去除一部分非相关性的基因 。用 W rapper方法 进行基因选择与具体的分类器有关 ,即在分类过程中 进行基因选择 。W rapper方法包括遗传算法 [9 ] 、Gibbs 采样方法 [10 ] 、无监督学习的聚类法 [11 ] 、贝叶斯回归 分析 [12 ] 、支持向量机 ( SVM ) [13 ] ,等等 。W rapper法将 分类算法和基因选择结合在一起 ,准确性优于 Filter 法 ,但其分类性能与具体的分类器有关 ,因为需要重 复训练数据 ,因此计算量较大 [2 ] ,并且容易陷入局部 最优。 SVM 由于对稀疏和有噪声的小样本数据处理 有良好的效果 ,成为基因选择中广泛采用的重要方 法。基于 SVM , Guyon 首次提出 SVM 2RFE ( support vector machine recursive feature elim ination)方法 [14 ] 。 该方法利用递归特征去除 (RFE) ,逐个消去基因 ,取 得非常好的效果 ,成为基因选择中的经典算法 。围绕 SVM 2RFE,许多学者提出扩展算法 ,包括多重 SVM 2 RFE法 [15 ] 、模糊聚类 SVM 2RFE法 [16 ] 、解决多类问题 的 SVM 2RFE法 [17 ]等 。