11.1 子集搜索与评价
相关特征:对当前学习任务有用的属性。
无关特征:对当前学习任务没用的属性。
冗余特征:所包含的信息能从其他特征中推演出来的特征。
- 在很多时候不起作用,去除它们会减轻学习过程的负担。
- 有时候恰好对应了完成学习任务所需的“中间概念”,会降低学习任务的难度。
特征选择:从给定的特征集合中选择出相关特征子集的过程。将特征子集搜索机制与子集评价机制相结合,即可得到特征选择方法。
- 减轻维数灾难问题。
- 降低学习任务的难度。
为简化讨论,本章暂且假定数据中不涉及冗余特征,并且假定初始的特征集合包含了所有的重要信息。
子集搜索:
-
前向搜索:从单个特征开始,每次尝试增加一个相关特征,这样逐渐增加特征的策略。
- 给定特征集合{a1, a2, ..., ad},我们可将每一个特征看做一个候选子集,对这d个候选单特征子集进行评价,假定{a2}最优,于是将{a2}作为第一轮的选定集。
- 在上一轮的选定集中加入一个特征,构成包含两个特征的候选子集,假定在这d-1个候选两特征子集中{a2, a4}最优,且优于{a2},于是将{a2, a4}作为本轮的选定集。
- 假定在第k+1轮时,最优的候选(k+1)特征子集不如上一轮的选定集,则停止生成候选子集,并将上一轮选定的k特征集合作为特征选择结果。
后向搜索:从完整的特征集合开始,每次尝试去掉一个无关特征,这样逐渐减少特征的策略。
双向搜素:每一轮逐渐增加选定相关特征(这些特征在后续轮中将确定不会被去除)、同时减少无关特征的策略。
上述策略都是贪心的,仅考虑了使本轮选定集最优。但若不进行穷举搜索,则无法避免这样的问题。
子集评价:特征子集A实际上确定了对数据集D的一个划分,每个划分区域对应着A上的一个取值,而样本标记信息Y则对应着对D的真实划分,通过估算这两个划分的差异,就能对A进行评价。与Y对应的划分的差异越小,则说明A越好。信息熵是判断这个差异的其中一种途径:
- 给定数据集D,假定D中第i类样本所占的比例为pi (i = 1, 2, ..., |y|)。为便于讨论,假定样本属性均为离散型。对属性子集A,假定根据其取值将D分成了V个子集{D1, D2, ..., DV},每个子集中的样本在A上取值相同,于是我们可计算属性子集A的信息增益
其中信息熵定义为
其中信息增益Gain(A)越大,意味着特征子集A包含的有助于分类的信息越多。于是,对每一个候选特征子集,我们可基于训练数据集D来计算其信息增益,以此作为评价准则。
信息熵的相关内容可参考https://www.jianshu.com/p/ea115d94ba52
11.2 过滤式选择
过滤式特征选择:先对数据集进行特征选择,然后再训练学习器,特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行“过滤”,再用过滤后的特征来训练模型。
Relief方法:一种为二分类问题设计的过滤式特征选择方法。只需在数据集的采样上而不必在整个数据集上估计相关统计量,其时间开销随采样次数以及原始特征线性增长,是一个运行效率很高的过滤式特征选择算法。
- 设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量,其每个分量分别对应于一个初始特征,而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。
- 给定训练集 {(x1, y1), (x2, y2), ..., (xm, ym)},对每个示例xi,先在xi的同类样本中寻找其最近邻xi,nh,称为猜中近邻near-hit。(选中样本中的一个好瓜,则离此好瓜最近的另一个好瓜则为猜中近邻,下标nh为near-hit简写)
- 从xi的异类样本中寻找其最近邻xi,nh,称为猜错近邻near-hit(离第一步选中的好瓜最近的坏瓜则为猜错近邻)
- 若xi与其猜中近邻xi,nh在属性j上的距离小于xi与其猜错近邻xi,nm的距离,则说明属性j对区分同类与异类样本是有益的,于是增大属性j所对应的统计量分量,反之亦然。按此规律可计算相关统计量对应于属性j的分量:其中表示在属性j上的取值,取决于属性j的类型:
- 若属性j为离散型,则时,否则为1。
- 若属性j为连续型,则,注意已规范化到[0, 1]区间。
- 对基于不同样本得到的估计结果进行平均,就得到各属性的相关统计量分量,分量值越大,则对应属性的分类能力就越强。
- 指定一个阈值τ,选择比τ大的相关统计量分量所对应的特征;也可指定欲选取的特征个数k,然后选择相关统计分量最大的k个特征。
Relief算法:
-
输入:训练集D;
样本抽样次数m;
特征权重阈值τ. -
过程:
- T = ∅;
- for i = 1 to m do
- 随机选择一个样本R;
- 从同类样本集中找到R的最近邻样本H;
- 从不同样本集中找到最近邻样本M;
- for A = 1 to N do
- W(A) = W(A) - diff(A, R, H)/m + diff(A, R, M)/m
- end for
- end for
- for A = 1 to N do
- if W(A) ≥ τ
- 把第A个特征添加到T中
- end if
- end for
- 输出:特征子集T
Relief-F方法:Relief的拓展变体,能处理多分类问题。
- 假定数据集D中的样本来自|y|个类别。对示例xi,若它属于第k类(k∈{1, 2, ..., |y|}),则先在第k类的样本中寻找xi的最近邻示例xi,nh并将其作为猜中近邻。
- 在第k类之外的每个类中找到一个xi的最近邻示例作为猜错近邻,记为xi,l,nh(l = 1, 2, ..., |y|; l ≠ k)。
- 相关统计量对应于属性j的分量为
其中pl为第l类样本在数据集D中所占的比例。
11.3 包裹式选择
包裹式特征选择:直接把最终将要使用的学习器的性能作为特征子集的评价准则,目的是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
- 从最终学习器性能来看,包裹式特征选择比过滤式特征选择更好。
- 但包裹式特征选择的计算开销通常比过滤式特征选择大得多。
拉斯维加斯方法:若有时间限制,给出满足要求的解或不给出解;若无时间限制,给出满足要求的解。
LVW算法:典型的包裹式特征选择方法。在拉斯维加斯方法框架下使用随机策略来进行子集搜索,并以最终分类器的误差为特征子集评价准则。
-
输入:数据集D;
特征集A;
学习算法;
停止条件控制参数T. -
过程:
- E = ∞;
- d = |A|;
- A* = A;
- t = 0;
- while t < T do
- 随机产生特征子集A';
- d' = |A'|;
- E' = CrossValidation((DA'));
- if (E' < E) ∨ ((E' = E) ∧ (d' < d)) then
- t = 0;
- E = E';
- d = d';
- A* = A';
- else
- t = t +1
- end if
- end while
- 输出:特征子集A*
第1-4行:初始误差E为无穷大;目前最优特征子集A*为全集A;目前特征子集内特征数量d为全集A内特征数量;重复次数t为0。
第5行:当重复次数t小于设定的停止条件控制参数T时,开始循环。
第6-7行:随机产生一个特征子集A',目前特征子集内特征数量更新为d'。
第8行:使用交叉验证估计使用特征子集A'来训练学习器所产生的误差E'。
第9行:如果使用征子集A'来训练学习器所产生的误差E'小于当前误差E;或者两个误差相同E' = E,但目前特征子集内的特征数量d'小于当前特征数量d。
第10-13行:则重复次数重置为0,将误差上限E设置为本轮误差E',将特征子集内特征数量上限设置为本轮特征数量d',将特征子集A'保留。
第14-16行:若不满足第9行条件,即随机选择出的特征子集A'无法减少误差,则重复次数t+1。
第17行:当t大于T时,即连续T轮未更新时,算法停止。
11.4 嵌入式选择与L1正则化
嵌入式特征选择:将特征选择过程与学习期训练过程融为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了特征选择。
L1正则化:在损失函数中引入范数可降低过拟合的风险,而引入L1范数相比L2范数更易于获得“稀疏”解,即它所求得的w会有更少的非零分量。稀疏解意味着初始的d个特征中仅有对应着w的非零分量的特征才会出现在最终模型中,于是,求解L1范数正则化的结果是得到了仅采用一部分初始化特征的模型,同时完成了特征选择与学习器训练,是一种嵌入式特征选择方法。
正则化原理可参考知乎https://www.zhihu.com/question/20924039
L1正则化问题的求解过程可参考书本以及南瓜书https://datawhalechina.github.io/pumpkin-book/#/chapter11/chapter11
11.5稀疏表示与字典学习
稀疏表示:若将数据集D考虑成一个矩阵,其每行对应一个样本,每列对应于一个特征,则特征选择所考虑的问题是特征具有稀疏性。
- 矩阵中的许多列与当前学习任务无关。通过特征选择去除这些列,则学习器训练过程仅需在较小的矩阵上进行,学习任务的难度可能有所降低,设计的计算和存储开销会减少,学的模型的可解释性也会提高。
- 矩阵中中存在很多零元素,这些零元素并不是以整列、整行形式存在。当样本具有这样的稀疏表达形式时,对学习任务来说会有不少好处。如大多数问题变得线性可分,且洗漱样本不会造成存储上的巨大负担,因为稀疏矩阵已有很多高校的存储方式。
字典学习/稀疏编码:将给定的普通非稀疏的稠密数据集转化为合适的稀疏表达形式,从而使学习任务得以简化,模型复杂度得以降低。
字典学习的过程可参考书本以及南瓜书https://datawhalechina.github.io/pumpkin-book/#/chapter11/chapter11
11.6 压缩感知
奈奎斯特采样定理:令采样频率达到模拟信号最高频率的两倍,则采样后的数字信号就保留了模拟信号的全部信息;换言之,由此获得的数字信号能精确重构原模拟信号。
压缩感知:接收方基于收到的损失了部分信息的信号,重构出原信号。
- 感知测量:对原始信号进行处理,以获得稀疏样本表示,这方面的内容涉及傅里叶变换、小波变换以及字典学习、稀疏编码等。
- 重构恢复:基于稀疏性从少量观测中恢复原信号。
压缩感知的过程可参考书本