第一句子网 > 机器学习之特征选择(feature_selection)

机器学习之特征选择(feature_selection)

时间：2020-09-25 07:59:22

文章目录

选取特征子集1. 子集搜索（subset search）2. 子集评价(subset evaluation)特征选择方法1. 过滤式(Filter)ReliefRelief-F2.包裹式(wrapper)LVM3.嵌入式(embedding)岭回归(ridge regression)LASSO

参考书为《机器学习》-周志华

选取特征子集

当前存在的问题

从初始的特征集合选取包含所有重要信息的特征子集，若没有任何领域知识作为先验假设，那只好遍历所有可能的子集，这实际上并不可行，会遇到组合爆炸，特证数稍多就不行

可行做法是产生一个"候选子集"，评价出此好坏，基于评价结果产生下一个子集…

1. 子集搜索（subset search）

第一个环节是子集搜索(subset search)

给定特征集合{a1,a2,....,ad}\lbrace a_1, a_2 ,....,a_d \rbrace{a1,a2,....,ad} , 我们可将每个特征看作一个候选子集，对这ddd个候选单特征子集进行评价

假定{a2}\lbrace a_2 \rbrace{a2}最优，将{a2}\lbrace a_2 \rbrace{a2}作为第一轮的选定集；

然后，在上一轮的选定集中加入一个特征，构造包含两个特征的候选子集，假定这d−1d-1d−1个候选两特征子集(候选子集为{{a2,a1},{a2,a3},....,{a2,ad}})中,{a2,a4}\lbrace\lbrace a_2,a_1 \rbrace,\lbrace a_2,a_3 \rbrace,....,\lbrace a_2,a_d \rbrace \rbrace)中,\lbrace a_2,a_4\rbrace{{a2,a1},{a2,a3},....,{a2,ad}})中,{a2,a4}最优，且优于{a2}\lbrace a_2 \rbrace{a2},于是将{a2,a4}\lbrace a_2,a_4 \rbrace{a2,a4}作为本轮选定集

⋯\cdots⋯

在第k+1k+1k+1轮时，最优的候选(k+1)特征子集不如上一轮的选定集，则停止生成候选选定集，并将上一轮选定的kkk特征集合作为特征选择的结果

"前向"(forward)搜索:逐渐增加相关特征

后向搜索(backward):从完整的特征集合开始，每次尝试去掉一个无关特征

双向搜索(bidirectional):前向后向相结合，每一轮逐渐增加相关特征(后续不会被去除)，同时减少无关特征

结论

上述策略都是贪心，仅考虑本轮最优。但很多问题只能穷举才可解决

2. 子集评价(subset evaluation)

给定数据集DDD，假定DDD中第iii类样本所占的比例为pi(i=1,2,...,∣Y∣)p_i(i=1,2,...,|Y|)pi(i=1,2,...,∣Y∣),假定样本属性为离散型

对属性子集AAA，假定根据其取值将DDD分成了VVV个子集{D1,D2,...,DV}\lbrace D^1,D^2,...,D^V \rbrace{D1,D2,...,DV}，每个子集中的样本在AAA上取值相同，于是我们可计算属性子集AAA的信息增益

Gain(A)=Ent(D)−∑v=1VDvDEnt(Dv)(11.1)Gain(A) = Ent(D) - \sum_{v=1}^{V}\frac{D^v}{D}Ent(D^v)\tag{11.1}Gain(A)=Ent(D)−v=1∑VDDvEnt(Dv)(11.1)

其中信息熵定义为

Ent(D)=−∑i=1∣Y∣pklog2pk(11.2)Ent(D) = -\sum_{i=1}^{|Y|}p_klog_2p_k\tag{11.2}Ent(D)=−i=1∑∣Y∣pklog2pk(11.2)

总结

信息增益越大，意味着特征子集A包含有助于分类的信息越多对每个候选特征子集，我们可基于训练数据集D 来计算其信息增益，以此作为评价准则.

将特征子集搜索与子集评价机制结合，即可得到特征选择方法

例如前向搜素+信息熵，这与决策树算法非常相似

事实上，决策树可用于特征选择，树结点的划分属性所组成的集合就是选择出的特征子集

特征选择方法

1. 过滤式(Filter)

过滤式方法是先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关，这相当于先用特征选择过程先对初始特征进行过滤,再用过滤后的特征来训练模型

Relief

Relief是著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性

流程

该统计量是一个向量，其中每个分量分别对应着一个初始特征，而特征子集的重要性是由子集中每个特征所对应的相关统计量分量之和来决定最终只需指定一个阈值τ\tauτ,选择比τ\tauτ大的相关统计量分量所对应的特征即可也可指定欲选取的特征个数k，然后选择相关统计量分量最大的k个特征

Relief如何确定相关统计量

给定训练集{(x1,y1),(x2,y2),....,(xm,ym)}\lbrace (x_1,y_1),(x_2,y_2),....,(x_m,y_m) \rbrace{(x1,y1),(x2,y2),....,(xm,ym)}，对每个示例xix_ixi

ReliefReliefRelief现在xix_ixi的同类样本中寻找其最近邻xi,nhx_{i,nh}xi,nh,称为**“猜中近邻”(near-hit)，再从xix_ixi的异类样本**中寻找其最近邻

xi,nmx_{i,nm}xi,nm,称为"猜错近邻"(near-miss)

相关统计量对应于属性j的分量为

δj=∑i−diff(xij,xi,nhj)2+diff(xij,xi,nmj)2(11.3)\delta^j = \sum_{i}-diff(x_i^j,x_{i,nh}^{j})^2 + diff(x_i^j,x_{i,nm}^j)^2\tag{11.3}δj=i∑−diff(xij,xi,nhj)2+diff(xij,xi,nmj)2(11.3)

xajx_a^jxaj是样本xax_axa在属性jjj上的取值diff(xaj,xbj)diff(x_a^j,x_b^j)diff(xaj,xbj)取决于属性j的类型：若属性jjj为离散型，则xaj=xbjx_a^j = x_b^jxaj=xbj时diff(xaj,xbj)=0diff(x_a^j,x_b^j) = 0diff(xaj,xbj)=0,否则为111若属性jjj为连续性，diff(xaj,xbj)=∣xaj−xbj∣diff(x_a^j,x_b^j) = |x_a^j - x_b^j|diff(xaj,xbj)=∣xaj−xbj∣注意xajx_a^jxaj,xbjx_b^jxbj已经规范化到[0,1][0,1][0,1]区间iii指出用于平均的样本下标

上式中可以看出

若xix_ixi与其猜中近邻xi,nhx_{i,nh}xi,nh在属性jjj上的距离小于xix_ixi与其猜错近邻xi,nmx_{i,nm}xi,nm的距离，则说明属性jjj对区分同类与异类是有益的，增大属性jjj所对应的统计量分量

反之，说明属性jjj起负作用，就减少统计量分量

对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计分量，分量值越大，则对应属性的分类能力越强

总结

Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量Relief的时间开销随着采样次数以及原始特征数线性增加，所以它是运行效率很高的过滤式特征选择算法Relief只针对二分类问题

Relief-F

为Relief的扩展变体，处理多分类问题

假定数据集DDD中的样本来自∣Y∣|Y|∣Y∣个类别

对于示例xix_ixi,若它属于第kkk类(k∈{1,2,...,∣Y∣})(k \in \lbrace 1,2,...,|Y| \rbrace)(k∈{1,2,...,∣Y∣}),则Relief-F先在第kkk类的样本中寻找xix_ixi的最近邻示例xi,nhx_{i,nh}xi,nh并将其作为猜中近邻

然后再第kkk类之外的每个类中找到一个xix_ixi的最近邻示例作为猜错近邻，记为xi,l,nm(l=1,2,...,∣Y∣,l≠k)x_{i,l,nm}(l = 1,2,...,|Y|,l \not = k)xi,l,nm(l=1,2,...,∣Y∣,l=k)

于是相关统计量对应于属性jjj的分量

δj=∑i−diff(xij,xi,nhj)2+∑l≠k(pl×diff(xij,xi,l,nm)2)(11.4)\delta^j = \sum_i -diff(x_i^j,x_{i,nh}^j)^2 + \sum_{l \not = k}(p_l \times diff(x_i^j,x_{i,l,nm})^2)\tag{11.4}δj=i∑−diff(xij,xi,nhj)2+l=k∑(pl×diff(xij,xi,l,nm)2)(11.4)

plp_lpl为第lll类样本再数据集DDD中所占比例

2.包裹式(wrapper)

与过滤式不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价标准，即，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、"量身定做"的特征子集

特点

包裹式特征选择比过滤式特征选择更好包裹式在特征选择过程中需要多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多

LVM

LVW(Las Vegas Wrapper)是典型的包裹式特征选择方法

在拉斯维加斯方法(Las Vegas method)框架下使用随机策略来进行子集搜索，并以最终分类器得误差为特征子集评价准则

上图第888行是通过在数据集DDD上，使用交叉验证法来估计学习器￡的误差，注意这个误差是在仅考虑特征子集A′A^{\prime}A′时得到的，即特征子集A′A^{\prime}A′上的误差.

若它比当前特征子集AAA上的误差更小，或误差相当但A′A^{\prime}A′中包含的特征数更少,则将A′A^{\prime}A′保留下来.

需注意的是，由于LVWLVWLVW 算法中特征子集搜索采用了随机策略，而每次特征子集评价都需训练学习器，计算开销很大.因此算法设置了停止条件控制参数TTT.

然而,整个LVWLVWLVW 算法是基于拉斯维加斯方法框架，若初始特征数很多(即∣A∣|A|∣A∣很大)、TTT设置较大，则算法可能运行很长时间都达不到停止条件.

换言之，若有运行时间限制，则有可能给不出解

3.嵌入式(embedding)

上面个两种方式中，特征选择过程与学习器训练过程有明显的分别；嵌入式特征选择将特征选择过程与学习器训练过程融为一体，两者在同意优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

基于L1L_1L1正则化的学习方法就是一种嵌入式特征选择方法

数据集D={(x1,y1),(x2,y2),....,(xm,ym)}D = \lbrace (x_1,y_1),(x_2,y_2),....,(x_m,y_m) \rbraceD={(x1,y1),(x2,y2),....,(xm,ym)},其中x∈Rdx \in R^dx∈Rd,y∈Ry \in Ry∈R,

使用线性回归模型，平方误差为损失函数，优化目标是

minw∑i=1m(yi−wTxi)2(11.5)min_{w}\sum_{i=1}^{m}(y_i - w^T x_i)^2\tag{11.5}minwi=1∑m(yi−wTxi)2(11.5)