什么用.我们将属性称为特征

减轻维数灾难问题与降维的原因相同去除不相关特征往往会降低学习任务的难度

我们不能直接用排列组合进行遍历所有可能子集这样会遭遇组合爆炸。

所以我们选择产生一个“候选子集”评价它的好坏然后根据评价结果产生下一个候选特征子集再进行评价持续进行直到无法找到一个更好的子集为止。

如何根据评价结果获取下一个候选特征子集?

前向搜索初始将每个特征当做一个候选特征子集然后从当前所有的候选子集中选择出最佳的特征子集接着在上一轮选出的特征子集中添加一个新的特征同样地选出最佳特征子集最后直至选不出比上一轮更好的特征子集。

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

双向搜索前向后向结合每一轮逐渐增加选定相关特征同时减少无关特征前面增加的特征不会被去除。

优点思路简单速度快不用全部情况都遍历一遍。

缺点使用贪心算法不从总体上考虑其它可能情况每次选取局部最优解不再进行回溯处理结果不一定是最好的。

\(\mathrm{Gain}(A)\mathrm{Ent}(D)-\sum_{v1}^{V}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\)

信息熵定义为

\(\mathrm{Ent}(D)-\sum_{i1}^{|\mathcal{Y}|}p_k\log_2p_k\)

信息增益Gain(A)越大特征子集A包含的有助于分类的信息越多。

对每个候选特征子集可基于训练数据集D来计算其信息增益以此作为评价准则。

信息熵也是同理只要能判断两个划分差异的机制都能用于特征子集评价。

11.2

过滤式方法是一种将特征选择与学习器训练相分离的特征选择技术即首先将相关特征挑选出来再使用选择出的数据子集来训练学习器。

Relief是其中著名的代表性算法它使用一个“相关统计量”来度量特征的重要性该统计量是一个向量其中每个分量代表着相应特征的重要性因此我们最终可以根据这个统计量各个分量的大小来选择出合适的特征子集。

Relief算法的关键是如何确定相关统计量。

对于数据集中的每个样例xiRelief首先找出与xi同类别的最近邻与不同类别的最近邻分别称为猜中近邻near-hit与猜错近邻near-miss接着便可以分别计算出相关统计量中的每个分量。

对于j分量

\(\delta^j\sum_i-\mathrm{diff}(x_i^j,x_{i,\mathrm{nh}}^j)^2\mathrm{diff}(x_i^j,x_{i,\mathrm{nm}}^j)^2\)

直观上理解对于猜中近邻两者j属性的距离越小越好对于猜错近邻j属性距离越大越好。

更一般地若xi为离散属性diff取海明距离即相同取0不同取1若xi为连续属性则diff为曼哈顿距离即取差的绝对值。

分别计算每个分量最终取平均便得到了整个相关统计量。

标准的Relief算法只用于二分类问题后续产生的拓展变体Relief-F则解决了多分类问题。

对于j分量新的计算公式如下

\(\delta^{j}\sum_{i}-\mathrm{diff}(x_{i}^{j},x_{i,\mathrm{nh}}^{j})^{2}\sum_{l\neq

k}\left(p_{l}\times\mathrm{diff}(x_{i}^{j},x_{i,l,\mathrm{nm}}^{j})^{2}\right)\)

其中\(p_l\)表示第\(l\)类样本在数据集中所占的比例易知两者的不同之处在于标准Relief

11.3

与过滤式选择不同的是包裹式选择将后续的学习器也考虑进来作为特征选择的评价准则。

因此包裹式选择可以看作是为某种学习器量身定做的特征选择方法由于在每一轮迭代中包裹式选择都需要训练学习器因此在获得较好性能的同时也产生了较大的开销。

拉斯维加斯方法和蒙特卡罗方法是两个以著名赌城名字命名的随机化方法两者的主要区别是若有时间限制则拉斯维加斯方法或者给出满足要求的解或者不给出解而蒙特卡罗方法一定会给出解虽然给出的解未必满足要求若无时间限制则两者都能给出满足要求的解。

LVWLas

Wrapper它在拉斯维加斯框架下使用随机策略来进行特征子集的搜索并以最终分类器的误差为特征子集评价准则。

初始化

\(E\)算法误差初始化为无穷大\(d\)特征子集的特征属性个数初始化为特征集的特征个数\(A^*\)特征子集初始化为特征集\(t\)连续没有优化效果的特征子集数初始化为0循环部分

随机产生一个特征子集\(A\)用\(A\)的特征个数更新\(d\)使用交叉验证法计算学习器\(\mathfrak{L}\)在\(A\)下的误差\(\left.\left\{\begin{array}{l}\text{更新}t,E,d,A^*;\text{

较目前最好的算法误差}E\text{小或者精度无提升但特征数变少}\\tt1,

else\end{array}\right.\right.\)重复循环部分直到满足停止条件控制参数输出当前最好的特征子集\(A^*\)