二、 特征选择

1. 特征选择的关键是：选取对训练数据有较强分类能力的特征。若一个特征的分类结果与随机分类的结果没有什么差别，则称这个特征是没有分类能力的。

2. 通常特征选择的指标是：信息增益或者信息增益比。这两个指标刻画了特征的分类能力。

3. 对于分布 ，熵为 。

   定义数据集 的经验熵为： 。

   其中：

   • 样本的类别分别为 。

   • 类别 的样本的数量为 ，所有样本的总数为 。

     因此有： 。

   • 是概率 的估计。

   • 就是熵 的估计。它刻画了数据集 中样本的类别分布情况。

4. 对于特征 ，定义数据集 在 上的经验熵为： 。

   其中：

   • 特征 的取值范围为 。

   • 属性 的样本的数量为 。

     因此有：

   • 是概率 的估计。

   • 刻画了数据集 中的样本在属性 上的取值分布情况。

5. 对于特征 ，其条件熵为： 。

   定义数据集 关于特征 的经验条件熵为：

   

   其中：

   • 属性 且类别为 的样本的数量为 ，所有样本的总数为 。

     因此有： 。

   • 是条件熵 的估计。它刻画了数据集 中，属性 中的那些样本中的类别的分布情况。

   • 是条件熵 的估计。

2.1 信息增益

1. 特征 对训练数据集 的信息增益 定义为：集合 的经验熵 与关于特征 经验条件熵 之差。即： 。

   由于熵 也称作互信息，因此信息增益也等于训练数据集中类与特征的互信息。

2. 决策树学习可以应用信息增益来选择特征。给定训练集 和特征 ：

   • 经验熵 刻画了对数据集 进行分类的不确定性。
   • 经验条件熵 刻画了在特征 给定条件下，对数据集 分类的不确定性。
   • 信息增益 刻画了由于特征 的确定，从而使得对数据集 的分类的不确定性减少的程度。

3. 不同的特征往往具有不同的信息增益。

   • 信息增益大的特征具有更强的分类能力 。
   • 如果一个特征的信息增益为0，则表示该特征没有什么分类能力。

2.2 信息增益比

1. 以信息增益作为划分训练集的特征选取方案，存在偏向于选取值较多的特征的问题。

   公式 中：

   • 当极限情况下 ，特征 在每个样本上的取值都不同，即 。

     • 此时特征 将每一个样本都划分到不同的子结点。即： 。

     • 由于 ，因此有： 。

       即： 取值为 0 或者 1 。因此有： 。

     • 最终使得 。

   • 条件熵的最小值为 0，这意味着该情况下的信息增益达到了最大值。

     然而很显然这个特征 显然不是最佳选择，因为它并不具有任何分类能力。

2. 可以通过定义信息增益比来解决该问题。

   特征 对训练集 的信息增益比 定义为：信息增益 与关于特征 的熵 之比：

   

   表征了特征 对训练集 的拆分能力。

   因为 只考虑样本在特征 上的取值，而不考虑样本的标记 ，所以这种拆分并不是对样本的分类。

3. 信息增益比本质上是对信息增益乘以一个加权系数：

   • 当特征 的取值集合较大时，加权系数较小，表示抑制该特征。
   • 当特征 的取值集合较小时，加权系数较大，表示鼓励该特征。