机器学习——

1 子集搜索与评价

属性称为特征

• 相关特征
  对当前学习任务有用的属性。

• 无关特征
  没什么用的属性，与当前学习任务无关。

• 特征选择（重要的数据预处理过程）
  从给定的特征集合中选择出相关特征子集的过程。

• 冗余特征
  该特征中所包含的信息能从其他特征中推演出来。

特征学习的重要性：
1.缓解维度灾难问题。
2.通过去除不相关特征来降低学习任务的难度。

从初始特征集合中选取包含了所有重要信息的特征子集涉及两个环节

• 子集搜索（基于贪心策略，有三种搜索方法）
  1.前向搜索：给定特征集合将每个特征看作一个候选子集，先对所有单特征子集进行评价，选定一个集，然后在上一轮的选定集加入一个特征，选出最佳特征子集。一直进行上述选择，直到最优的候选特征子集不如上一轮的选定集。
  2.后向搜索：从完整特征集合开始，每次尝试去掉一个无关特征，逐渐减少特征。
  3.双向搜索：将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征，同时减少无关特征。

• 子集评价
  给定数据集D，对属性子集A，假定根据其取值将D分为了V个子集，每个子集中的样本在A上取值相同，计算属性子集A的信息增益
  $Gain(A)=Ent(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
  信息熵定义为
  $Ent(D)=-{\sum }_{i=1}^{|y|}{p}_{k}lo{g}_2{p}_k$

信息增益越大，特征子集A中包含的有助于分类的信息越多，可以通过计算信息增益来作为评价标准。

常见的特征选择方法大致分为三类：过滤式，包裹式，嵌入式。