支持向量机递归特征消除(下文简称SVM-RFE)是由Guyon等人在对癌症分类时提出来的,最初只能对两类数据进行特征提取。它是一种基于Embedded方法。
支持向量机
支持向量机广泛用于模式识别,机器学习等领域,SVM采用结构风险最小化原则,同时最小化经验误差,以此提高学习的性能。详细的SVM介绍请看我的另一篇博文《 线性支持向量机》
在这简单介绍一下SVM。
设训练集{(xi,yi)}i=1N\{(x_i,y_i)\}_{i=1}^N{(xi,yi)}i=1N,其中xi∈RD,yi∈{+1,−1}x_i\in R^D, y_i \in \{+1,-1\}xi∈RD,yi∈{+1,−1},xi为第ix_i为第ixi为第i个样本,N为样本量,D为样本特征数。SVM寻找最优的分类超平面ω⋅x+b=0\omega\cdot x+b=0ω⋅x+b=0。
SVM需要求解的优化问题为:
min12∣∣ω∣∣2+CΣi=1Nξis.t.yi(ω⋅xi+b)≥1−ξi,i=1,2,...,Nξi≥0,i=1,2,...,Nmin \quad \frac{1}{2}||\omega||^2+C\Sigma_{i=1}^N\xi_i\\ s.t.\quad y_i(\omega\cdot x_i+b)\ge 1-\xi_i,i=1,2,...,N\\ \xi_i\ge0,i=1,2,...,Nmin21∣∣ω∣∣2+CΣi=1Nξis.t.yi(ω⋅xi+b)≥1−ξi,i=1,2,...,Nξi≥0,i=1,2,...,N
而原始问题可以转化为对偶问题:
min12Σi=1NΣj=1Nαiαjyiyj(xi⋅xj)−Σi=1Nαis.t.Σi=1Nyiαi=00≤αi≤C,i=1,2,...,Nmin\quad \frac{1}{2}\Sigma_{i=1}^N\Sigma_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\Sigma_{i=1}^N\alpha_i\\ s.t.\quad \Sigma_{i=1}^Ny_i\alpha_i=0\\ 0\le \alpha_i\le C,i=1,2,...,Nmin21Σi=1NΣj=1Nαiαjyiyj(xi⋅xj)−Σi=1Nαis.t.Σi=1Nyiαi=00≤αi≤C,i=1,2,...,N
其中,αi\alpha_iαi为拉格朗日乘子。
最后ω\omegaω的解为:
ω=Σi=1Nαiyixi\omega=\Sigma_{i=1}^N\alpha_iy_ix_iω=Σi=1Nαiyixi
两分类的SVM-RFE算法
SVM-RFE是一个基于SVM的最大间隔原理的序列后向选择算法。它通过模型训练样本,然后对每个特征进行得分进行排序,去掉最小特征得分的特征,然后用剩余的特征再次训练模型,进行下一次迭代,最后选出需要的特征数。而特征iii的排序准则得分定义为:
ci=wi2c_i=w_i^2ci=wi2
两分类SVM-RFE算法:
输入:训练样本{(xi,yi)}i=1N,yi∈{+1,−1}\{(x_i,y_i)\}_{i=1}^N, y_i \in \{+1,-1\}{(xi,yi)}i=1N,yi∈{+1,−1}
输出:特征排序集R
1)初始化原始特征集合S={1,2,…,D},特征排序集R=[]
2)循环以下过程直至S=[]
\quad获取带候选特征集合的训练样本;
\quad用式min12Σi=1NΣj=1Nαiαjyiyj(xi⋅xj)−Σi=1Nαimin\quad \frac{1}{2}\Sigma_{i=1}^N\Sigma_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\Sigma_{i=1}^N\alpha_imin21Σi=1NΣj=1Nαiαjyiyj(xi⋅xj)−Σi=1Nαi训练SVM分类器,得到ω\omegaω;
\quad用式ci=wi2,k=1,2,...,∣S∣c_i=w_i^2,k=1,2,...,|S|ci=wi2,k=1,2,...,∣S∣计算排序准则得分;
\quad找出排序得分最小的特征p=argminkckp=arg\quad min_kc_kp=argminkck;
\quad更新特征集R=[p,R];
\quad在S中去除此特征:S=S/p。
#多分类的SVM-RFE算法
多分类的SVM-RFE算法其实和两分类的SVM-RFE算法类似,只不过在处理多分类时,把类别进行两两配对,其中一类为正类,另一类为负类,这样需训练N(N−1)2\frac{N(N-1)}{2}2N(N−1)个分类器,这就是一对一(One vs. One,简称OvO)的多分类拆分策略(详细请看周志华的《机器学习》的第三章线性模型的多分类学习),这样就变成了多个两分类问题(当然,也可以使用一对其余(OvR)),每个两类问题用一个SVM-RFE进行特征选择,利用多个SVM-RFE获得多个排序准则得分,然后把多个排序准则得分相加后得到排序准则总分,以此作为特征剔除的依据,每次迭代消去最小特征,直到所有特征都被删除。
多分类SVM-RFE算法:
输入:训练样本集{(xi,vi)}i=1N,vi∈{1,2,...,l},l为类别数\{(x_i,v_i)\}_{i=1}^N, v_i \in \{1,2,...,l\},l为类别数{(xi,vi)}i=1N,vi∈{1,2,...,l},l为类别数
输出:特征排序集R
1)初始化原始特征集合S={1,2,…,D},特征排序集R=[]
2)生成l(l−1)2\frac{l(l-1)}{2}2l(l−1)个训练样本:
\quad在训练样本{(xi,vi)}i=1N\{(x_i,v_i)\}_{i=1}^N{(xi,vi)}i=1N中找出不同类别的两两组合得到最后的训练样本:
\quadXj=X_j=Xj=
\qquad{(xi,yi)}i=1N1+Nj+1,j=1,2,...,l;当vi=1时,yi=1,当vi=j+1,yi=−1{\{(x_i,y_i)\}_{i=1}^{N_1+N_{j+1}},j=1,2,...,l;当v_i=1时,y_i=1,当v_i=j+1,y_i=-1}{(xi,yi)}i=1N1+Nj+1,j=1,2,...,l;当vi=1时,yi=1,当vi=j+1,yi=−1
\qquad{(xi,yi)}i=1N2+Nj−l+3,j=l,...,2l−3;当vi=2时,yi=1,当vi=j−l+3,yi=−1{\{(x_i,y_i)\}_{i=1}^{N_2+N_{j-l+3}},j=l,...,2l-3;当v_i=2时,y_i=1,当v_i=j-l+3,y_i=-1}{(xi,yi)}i=1N2+Nj−l+3,j=l,...,2l−3;当vi=2时,yi=1,当vi=j−l+3,yi=−1
⋯⋯⋯⋯⋯⋯⋯⋯\qquad\cdots \qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots⋯⋯⋯⋯⋯⋯⋯⋯
\quad{(xi,yi)}i=1Nl−1+Nl,j=l(l−1)2−1,...,l(l−1)2;当vi=l−1时,yi=1,当vi=l,yi=−1{\{(x_i,y_i)\}_{i=1}^{N_l-1+N_{l}},j=\frac{l(l-1)}{2}-1,...,\frac{l(l-1)}{2};当v_i=l-1时,y_i=1,当v_i=l,y_i=-1}{(xi,yi)}i=1Nl−1+Nl,j=2l(l−1)−1,...,2l(l−1);当vi=l−1时,yi=1,当vi=l,yi=−1
3)循环一下过程直至S=[]:
\quad获取用l个训练子样本Xj(j=1,2,...,l(l−1)/2)X_j(j=1,2,...,l(l-1)/2)Xj(j=1,2,...,l(l−1)/2);
\quad分别用XjX_jXj训练SVM,分别得到ωj(j=1,2,...,l)\omega_j(j=1,2,...,l)ωj(j=1,2,...,l);
\quad计算排序准则得分ck=Σjωjk2(k=1,2,...,∣S∣)c_k=\Sigma_j\omega_{jk}^2(k=1,2,...,|S|)ck=Σjωjk2(k=1,2,...,∣S∣);
\quad找出排序准则得分最小的特征p=argminkckp=arg\quad min_kc_kp=argminkck;
\quad更新特征集R=[p,R];
\quad在S中去除此特征S=S/p.
参考
【Isabelle Guyon, Jason Weston et.al】Gene Selection for Cancer Classification using Support Vector Machines
【黄晓娟,张莉】改进的多类支持向量机递归特征消除在癌症多分类中的应用
【周志华】机器学习