当我们在训练模型时,其中一个很重要的部分是训练模型的参数,也就是模型中各个特征的值,不同的模型具有不同的特征组合,因此对于特征的选择也就对应了模型的选择。举个文本分类的例子,在文本分类的任务中,特征数量p远大于训练样本数n,而我们又知道特征里面有很大一部分是和类别无关的,因此我们就会想到用特征选择来把与类别相关的特征选出来。对于p个特征,会出现2p种特征的组合,也就对应了2p个模型,我们只要选择一种特征组合,也就选择了一个模型。
关于特征选择,下面介绍三种方法。
Filter类
这种方法计算每一个特征与类别的相关度,并获得一个得分。得分高的特征表明其与类别的关系越强。最后将所有特征按得分高低排序,选择得分高的特征。
Filter类的典型代表就是信息增益(或者信息增益率)。通过计算特征的信息增益,将信息增益较高的特征选出。具体的做法是,首先为每个特征计算信息增益,并将其作为特征的得分,然后选择得分较高的前k个特征作为选择的特征。关于k的值如何选择,可以采取交叉验证的方式。
从上面看出,Filter类的特征选择只需做简单的统计,计算复杂度低。但这种方法的问题是没有考虑特征之间的组合关系,有可能某一个特征的分类能力很差,但是它和某些其它特征组合起来会得到不错的效果。
Wrapper类
假如有p个特征,那么就会有2p种特征组合,每种组合对应了一个模型。Wrapper类方法的思想是枚举出所有可能的情况,从中选取最好的特征组合。
这种方式的问题是:由于每种特征组合都需要训练一次模型,而训练模型的代价实际上是很大的,如果p非常大,那么上述方式显然不具有可操作性。下面介绍两种优化的方法:forward search(前向搜索)和backward search(后向搜索)。
forward search初始时假设已选特征的集合为空集,算法采取贪心的方式逐步扩充该集合,直到该集合的特征数达到一个阈值,该阈值可以预先设定,也可以通过交叉验证获得。算法的伪码如下:
注:上面的算法描述摘自Andrew NG的机器学习课程的课件。
对于算法的外重循环,当F中包含所有特征时或者F中的特征数达到了阈值,则循环结束,算法最后选出在整个搜索过程中最优的特征集合。
backward search初始时假设已选特征集合F为特征的全集,算法每次删除一个特征,直到F的特征数达到指定的阈值或者F被删空。该算法在选择删除哪一个特征时和forward search在选择一个特征加入F时是一样的做法。
Wrapper类的特征选择方式考虑了特征之间的组合情况,它的效果很好,弥补了Filter类的不足。但是Wrapper类的缺点是计算量太大,即便是做了改进的forward search 和backward search其时间复杂度也是O(p2),当p很大时也是一笔不小的开销。
折中类
对于上面的filter类和wrapper类,各自都有自己的优点和缺点,那么我们能不能取一种折中的方法来进行特征选择呢?也就是时间复杂度较低,并且也考虑特征之间的组合关系。
我们知道L1正则化自带特征选择的功能,它倾向于留下相关特征而删除无关特征。
比如在文本分类中,我们不再需要进行显示的特征选择这一步,而是直接将所有特征扔进带有L1正则化的模型里,由模型的训练过程来进行特征的选择。
这里需要说明的是,该类方法只是wrapper类和filter类的一个折中,它的时间复杂度或者训练模型的次数要远远低于wrapper类,但其特征选择的效果没有wrapper类好;同样,它的时间复杂度要高于filter类,但特征选择效果却好于filter类。
注意,在用L1做特征选择时需要结合实际情况,不能一味的按照理论照搬,理论和实践还是有所差距的,具体的关于L1做特征选择的详细描述请参见博文: http://www.jb51.cc/article/p-ojmuodor-hu.html。