一、相关概念
在特征选择中涉及到两个过程，一个是子集搜索，一个是子集评价。已知的特征空间的维度，需要去遍历多有可能的子集显然不现实。所以一个可行的做法是，先产生一个候选的子集，然后对该子集进行评价，之后根据这个评价继续搜索特征。
- 子集搜索：（1）向前搜索：每次从待选的特征集A当中当中选定一个特征 a k a_k ak加入已选的特征集S,使得特征集 S ∪ a k S\cup a_k S∪ak最优，并且大于原来的已选的特征集S.(2)向后搜索：每次从特征空间中删除一个冗余特征。（3）双向搜索：每次选择一个最优的特征（这些特征在后续将不会被删除），去除一个冗余的特征。
- 子集评价：评价选择的特征子集的优劣方法。
二、特征选择的三种类别
-
过滤式
过滤式方法指的是先对特征集进行筛选，然后再进行学习器的训练，特征选择过程对后续的学习器无关。相当于先用特征选择的过程对初始的特征进行过滤，再用过滤后的特征进行模型的训练。
典型代表有：Relief算法。该算法的思想如下：为每个特征设置一个统计量，所有特征的统计量构成一个向量。统计量代表的是特征的重要程度，最终只要选择对应分量的值大于阈值 τ \tau τ或者前k个特征就行了。统计量构建的方法如下：在 x i x_i xi的同类样本中选择最近邻 x i , n h x_{i,nh} xi,nh,称为“猜中近邻”。在异类样本中选择一个最近邻 x i , n m x_{i,nm} xi,nm,称为猜错近邻，相关的统计量定义如下： δ j = ∑ i − diff ( x i j , x i , n h j ) 2 + diff ( x i j , x i , n m j ) 2 \delta^j=\sum_{i}-\text{diff}(x_i^j,x_{i,nh}^j)^2+\text{diff}(x_i^j,x_{i,nm}^j)^2 δj=i∑−diff(xij,xi,nhj)2+diff(xij,xi,nmj)2
从上式可以看出，对于某个特征对应的分量，该特征使得同类的越近，异类的越远，所对应的统计量就越大。 -
包裹式
包裹式的特征选择考虑到具体的学习器，是根据学习器上的误差来评价特征子集的优劣，在子集的搜索方式上是用了拉维加斯的随机策略。典型的算法是：LVW算法。
每次随机选择出一个特征子集之后都要重新训练一个学习器，计算的花销很大，若特征数很多，可能需要运行很长的时间才能够得到一个解。 -
嵌入式
嵌入式的方法与之前的两个方法不同，嵌入式将特征选择的过程与学习器的训练过程融为一体，在学习器的训练过程中，自动的进行了特征的选择。该方法的模型如下： min w ∑ i m ( y i − w T x i ) 2 \min_w\sum_i^m(y_i-w^Tx_i)^2 wmini∑m(yi−wTxi)2
学习到权重W之后，就可以根据w的大小，选择出权重较大的特征。为了防止过拟合，通常加入正则项，得到的模型如下： min w ∑ i m ( y i − w T x i ) 2 + λ ∥ W ∥ 2 2 \min_w\sum_i^m(y_i-w^Tx_i)^2+\lambda\left \| W\right \|_2^2 wmini∑m(yi−wTxi)2+λ∥W∥22