特征选择算法

特征选择方法初识：

1、为什么要做特征选择
在有限的样本数目下，用大量的特征来设计分类器计算开销太大而且分类性能差。
2、特征选择的确切含义
将高维空间的样本通过映射或者是变换的方式转换到低维空间，达到降维的目的，然后通过特征选取删选掉冗余和不相关的特征来进一步降维。
3、特征选取的原则
获取尽可能小的特征子集，不显著降低分类精度、不影响类分布以及特征子集应具有稳定适应性强等特点

主要有三种方法：

1、Filter方法

其主要思想是：对每一维的特征“打分”，即给每一维的特征赋予权重，这样的权重就代表着该维特征的重要性，然后依据权重排序。

主要的方法有：

Chi-squared test(卡方检验)
information gain(信息增益)，详细可见“简单易学的机器学习算法——决策树之ID3算法”
correlation coefficient scores(相关系数)

2、Wrapper方法

其主要思想是：将子集的选择看作是一个搜索寻优问题，生成不同的组合，对组合进行评价，再与其他的组合进行比较。这样就将子集的选择看作是一个是一个优化问题，这里有很多的优化算法可以解决，尤其是一些启发式的优化算法，如GA，PSO，DE，ABC等，详见“优化算法——人工蜂群算法(ABC)”，“优化算法——粒子群算法(PSO)”。

主要方法有： (递归特征消除算法)

3、Embedded方法

　　其主要思想是：在模型既定的情况下学习出对提高模型准确性最好的属性。这句话并不是很好理解，其实是讲在确定模型的过程中，挑选出那些对模型的训练有重要意义的属性。

简单易学的机器学习算法——岭回归(Ridge Regression)”，岭回归就是在基本线性回归的过程中加入了正则项。

4、总结以及注意点

这篇文章中最后提到了一点就是用特征选择的一点Trap。个人的理解是这样的，特征选择不同于特征提取，特征和模型是分不开，选择不同的特征训练出的模型是不同的。在机器学习=模型+策略+算法的框架下，特征选择就是模型选择的一部分，是分不开的。这样文章最后提到的特征选择和交叉验证就好理解了，是先进行分组还是先进行特征选择。

答案是当然是先进行分组，因为交叉验证的目的是做模型选择，既然特征选择是模型选择的一部分，那么理所应当是先进行分组。如果先进行特征选择，即在整个数据集中挑选择机，这样挑选的子集就具有随机性。

我们可以拿正则化来举例，正则化是对权重约束，这样的约束参数是在模型训练的过程中确定的，而不是事先定好然后再进行交叉验证的。

特征选择方法具体分细节总结：
1 去掉取值变化小的特征 Removing features with low variance
该方法一般用在特征选择前作为一个预处理的工作，即先去掉取值变化小的特征，然后再使用其他的特征选择方法选择特征。
2 单变量特征选择 Univariate feature selection
单变量特征选择能够对每一个特征进行测试，衡量该特征和响应变量之间的关系，根据得分扔掉不好的特征。对于回归和分类问题可以采用卡方检验等方式对特征进行测试。
2.1 Pearson相关系数 Pearson Correlation
皮尔森相关系数是一种最简单的，能帮助理解特征和响应变量之间关系的方法，该方法衡量的是变量之间的线性相关性，结果的取值区间为[-1，1]，-1表示完全的负相关(这个变量下降，那个就会上升)，+1表示完全的正相关，0表示没有线性相关。
2.2 互信息和最大信息系数 Mutual information and maximal information coefficient (MIC)
以上就是经典的互信息公式了。想把互信息直接用于特征选择其实不是太方便：1、它不属于度量方式，也没有办法归一化，在不同数据集上的结果无法做比较；2、对于连续变量的计算不是很方便（X和Y都是集合，x，y都是离散的取值），通常变量需要先离散化，而互信息的结果对离散化的方式很敏感。
2.3 距离相关系数 (Distance correlation)
距离相关系数是为了克服Pearson相关系数的弱点而生的。Pearson相关系数是0，我们也不能断定这两个变量是独立的（有可能是非线性相关）；但如果距离相关系数是0，那么我们就可以说这两个变量是独立的。
2.4 基于学习模型的特征排序 (Model based ranking)
这种方法的思路是直接使用你要用的机器学习算法，针对每个单独的特征和响应变量建立预测模型。其实Pearson相关系数等价于线性回归里的标准化回归系数。假如某个特征和响应变量之间的关系是非线性的，可以用基于树的方法（决策树、随机森林）、或者扩展的线性模型等。基于树的方法比较易于使用，因为他们对非线性关系的建模比较好，并且不需要太多的调试。但要注意过拟合问题，因此树的深度最好不要太大，再就是运用交叉验证。
3 线性模型和正则化
单变量特征选择方法独立的衡量每个特征与响应变量之间的关系，另一种主流的特征选择方法是基于机器学习模型的方法。有些机器学习方法本身就具有对特征进行打分的机制，或者很容易将其运用到特征选择任务中，例如回归模型，SVM，决策树，随机森林等等。
3.1 正则化模型
正则化就是把额外的约束或者惩罚项加到已有模型（损失函数）上，以防止过拟合并提高泛化能力。损失函数由原来的E(X,Y)变为E(X,Y)+alpha||w||，w是模型系数组成的向量（有些地方也叫参数parameter，coefficients），||·||一般是L1或者L2范数，alpha是一个可调的参数，控制着正则化的强度。当用在线性模型上时，L1正则化和L2正则化也称为Lasso和Ridge。
3.2 L1正则化/Lasso
　　L1正则化将系数w的l1范数作为惩罚项加到损失函数上，由于正则项非零，这就迫使那些弱的特征所对应的系数变成0。因此L1正则化往往会使学到的模型很稀疏（系数w经常为0），这个特性使得L1正则化成为一种很好的特征选择方法。
3.3 L2正则化/Ridge regression
　　L2正则化将系数向量的L2范数添加到了损失函数中。由于L2惩罚项中系数是二次方的，这使得L2和L1有着诸多差异，最明显的一点就是，L2正则化会让系数的取值变得平均。对于关联特征，这意味着他们能够获得更相近的对应系数。还是以Y=X1+X2为例，假设X1和X2具有很强的关联，如果用L1正则化，不论学到的模型是Y=X1+X2还是Y=2X1，惩罚都是一样的，都是2alpha。但是对于L2来说，第一个模型的惩罚项是2alpha，但第二个模型的是4*alpha。可以看出，系数之和为常数时，各系数相等时惩罚是最小的，所以才有了L2会让各个系数趋于相同的特点。
　　可以看出，L2正则化对于特征选择来说一种稳定的模型，不像L1正则化那样，系数会因为细微的数据变化而波动。所以L2正则化和L1正则化提供的价值是不同的，L2正则化对于特征理解来说更加有用：表示能力强的特征对应的系数是非零
4 随机森林
　　随机森林具有准确率高、鲁棒性好、易于使用等优点，这使得它成为了目前最流行的机器学习算法之一。随机森林提供了两种特征选择的方法：mean decrease impurity和mean decrease accuracy。
4.1 平均不纯度减少 mean decrease impurity
　　随机森林由多个决策树构成。决策树中的每一个节点都是关于某个特征的条件，为的是将数据集按照不同的响应变量一分为二。利用不纯度可以确定节点（最优条件），对于分类问题，通常采用基尼不纯度或者信息增益，对于回归问题，通常采用的是方差或者最小二乘拟合。当训练决策树的时候，可以计算出每个特征减少了多少树的不纯度。对于一个决策树森林来说，可以算出每个特征平均减少了多少不纯度，并把它平均减少的不纯度作为特征选择的值。
4.2 平均精确率减少 Mean decrease accuracy
　　另一种常用的特征选择方法就是直接度量每个特征对模型精确率的影响。主要思路是打乱每个特征的特征值顺序，并且度量顺序变动对模型的精确率的影响。很明显，对于不重要的变量来说，打乱顺序对模型的精确率影响不会太大，但是对于重要的变量来说，打乱顺序就会降低模型的精确率。
5 两种顶层特征选择算法
　　之所以叫做顶层，是因为他们都是建立在基于模型的特征选择方法基础之上的，例如回归和SVM，在不同的子集上建立模型，然后汇总最终确定特征得分。
5.1 稳定性选择 Stability selection
　　稳定性选择是一种基于二次抽样和选择算法相结合较新的方法，选择算法可以是回归、SVM或其他类似的方法。它的主要思想是在不同的数据子集和特征子集上运行特征选择算法，不断的重复，最终汇总特征选择结果，比如可以统计某个特征被认为是重要特征的频率（被选为重要特征的次数除以它所在的子集被测试的次数）。理想情况下，重要特征的得分会接近100%。稍微弱一点的特征得分会是非0的数，而最无用的特征得分将会接近于0。
5.2 递归特征消除 Recursive feature elimination (RFE)
　　递归特征消除的主要思想是反复的构建模型（如SVM或者回归模型）然后选出最好的（或者最差的）的特征（可以根据系数来选），把选出来的特征放到一边，然后在剩余的特征上重复这个过程，直到所有特征都遍历了。这个过程中特征被消除的次序就是特征的排序。因此，这是一种寻找最优特征子集的贪心算法。
　　RFE的稳定性很大程度上取决于在迭代的时候底层用哪种模型。例如，假如RFE采用的普通的回归，没有经过正则化的回归是不稳定的，那么RFE就是不稳定的；假如采用的是Ridge，而用Ridge正则化的回归是稳定的，那么RFE就是稳定的。

6 启发式搜索

　　序列前向选择（SFS，Sequential Forward Seelction）：特征子集X从空集开始，每次选择一个特征x加入特征子集X，使得特征函数J（X）最优。简单说就是，每次都选择一个使得评价函数的取值达到最优的特征加入，其实就是一种简单的贪心算法。缺点就是只能加入特征而不能去除特征。例如：特征A完全依赖于特征B与C，可以认为如果加入了特征B与C则A就是多余的。假设序列前向选择算法首先将A加入特征集，然后又将B与C加入，那么特征子集中就包含了多余的特征A。

　　序列后向选择（SBS，Sequential Backward Selection）：从特征全集O开始，每次从特征集O中剔除一个特征x，使得剔除特征x后评价函数值达到最优。和SFS相反，从特征全集开始，每次选择使评价函数J（X）最优的特征x剔除，也是贪心算法，缺点是只减不增。

　　双向搜索（BDS,Bidirectional Search）：使用SFS从空集开始，同时使用SBS从全集开始搜索，当两者搜索到一个相同的特征子集C时停止搜索。双向搜索的出发点是。如下图所示，O点代表搜索起点，A点代表搜索目标。灰色的圆代表单向搜索可能的搜索范围，绿色的2个圆表示某次双向搜索的搜索范围，容易证明绿色的面积必定比灰色的要小。

　　增L去R选择算法（LRS，Plus-L Minus-R Selection）：该算法有两种形式，此算法结合了SBS和SFS思想，L和R的选择是关键。

　　算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。（L>R）

　　算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得评价函数最优。（L<R）

　　浮动序列选择（Sequential Floating Selection）：序列浮动选择由LRS发展而来，该算法与LRS算法不同之处在：序列浮动选择的L与R不是固定的，而是“浮动”的，也就是会变化的。此算法结合了SBS, SFS, LRS的特点，并弥补了它们的缺点。根据搜索方向的不同，有以下两种变种：

　　序列浮动前向选择（SFFS, Sequential Floating Forward Selection）：从空集开始，每轮在未选择的特征中选择一个子集x，使加入子集x后评价函数达到最优，然后在已选择的特征中选择子集z，使剔除子集z后评价函数达到最优。

　　序列浮动后向选择（SBBS, Sequential Floating Backward Selection）：从全集开始，每轮在已选择的特征中剔除一个子集z，使剔除子集z后评价函数达到最优，然后在未选择的特征中选择子集x，使加入子集x后评价函数达到最优。

6、特征获取方法的选取原则
a、处理的数据类型
b、处理的问题规模
c、问题需要分类的数量
d、对噪声的容忍能力
e、无噪声环境下，产生稳定性好、最优特征子集的能力。