特征选择之支持向量机递归特征消除（SVM-RFE）

支持向量机递归特征消除(下文简称SVM-RFE)是由Guyon等人在对癌症分类时提出来的，最初只能对两类数据进行特征提取。它是一种基于Embedded方法。

支持向量机

支持向量机广泛用于模式识别，机器学习等领域，SVM采用结构风险最小化原则，同时最小化经验误差，以此提高学习的性能。详细的SVM介绍请看我的另一篇博文《 线性支持向量机》

在这简单介绍一下SVM。 
设训练集，其中，个样本，N为样本量，D为样本特征数。SVM寻找最优的分类超平面。 
SVM需要求解的优化问题为： 

而原始问题可以转化为对偶问题： 

其中， 为拉格朗日乘子。 
最后 的解为： 

两分类的SVM-RFE算法

SVM-RFE是一个基于SVM的最大间隔原理的序列后向选择算法。它通过模型训练样本，然后对每个特征进行得分进行排序，去掉最小特征得分的特征，然后用剩余的特征再次训练模型，进行下一次迭代，最后选出需要的特征数。而特征的排序准则得分定义为： 

两分类SVM-RFE算法： 
输入：训练样本  
输出：特征排序集R 
1)初始化原始特征集合S={1，2，…,D}，特征排序集R=[] 
2)循环以下过程直至S=[] 
获取带候选特征集合的训练样本； 
用式 训练SVM分类器，得到 ； 
用式 计算排序准则得分; 
找出排序得分最小的特征 ; 
更新特征集R=[p,R]； 
在S中去除此特征：S=S/p。

多分类的SVM-RFE算法

多分类的SVM-RFE算法其实和两分类的SVM-RFE算法类似，只不过在处理多分类时，把类别进行两两配对，其中一类为正类，另一类为负类，这样需训练个分类器，这就是一对一（One vs. One,简称OvO）的多分类拆分策略（详细请看周志华的《机器学习》的第三章线性模型的多分类学习），这样就变成了多个两分类问题（当然，也可以使用一对其余（OvR）），每个两类问题用一个SVM-RFE进行特征选择，利用多个SVM-RFE获得多个排序准则得分，然后把多个排序准则得分相加后得到排序准则总分，以此作为特征剔除的依据，每次迭代消去最小特征，直到所有特征都被删除。 
多分类SVM-RFE算法： 
输入：训练样本集 
输出：特征排序集R 
1）初始化原始特征集合S={1，2，…,D}，特征排序集R=[] 
2）生成个训练样本: 
在训练样本中找出不同类别的两两组合得到最后的训练样本： 
 
 
 
 
 
3）循环一下过程直至S=[]: 
获取用l个训练子样本； 
分别用训练SVM，分别得到； 
计算排序准则得分； 
找出排序准则得分最小的特征； 
更新特征集R=[p,R]； 
在S中去除此特征S=S/p.

参考 
【Isabelle Guyon, Jason Weston et.al】Gene Selection for Cancer Classification using Support Vector Machines 
【黄晓娟，张莉】改进的多类支持向量机递归特征消除在癌症多分类中的应用 
【周志华】机器学习