Question

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

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

3. 对于分布 $ MathJax-Element-27 $ ，熵为 $ MathJax-Element-28 $ 。

   定义数据集 $ MathJax-Element-420 $ 的经验熵为： $ MathJax-Element-30 $ 。

   其中：

   • 样本的类别分别为 $ MathJax-Element-31 $ 。

   • 类别 $ MathJax-Element-240 $ 的样本的数量为 $ MathJax-Element-243 $ ，所有样本的总数为 $ MathJax-Element-255 $ 。

     因此有： $ MathJax-Element-35 $ 。

   • $ MathJax-Element-36 $ 是概率 $ MathJax-Element-37 $ 的估计。

   • $ MathJax-Element-81 $ 就是熵 $ MathJax-Element-39 $ 的估计。它刻画了数据集 $ MathJax-Element-420 $ 中样本的类别分布情况。

4. 对于特征 $ MathJax-Element-452 $ ，定义数据集 $ MathJax-Element-420 $ 在 $ MathJax-Element-452 $ 上的经验熵为： $ MathJax-Element-44 $ 。

   其中：

   • 特征 $ MathJax-Element-452 $ 的取值范围为 $ MathJax-Element-46 $ 。

   • 属性 $ MathJax-Element-67 $ 的样本的数量为 $ MathJax-Element-48 $ 。

     因此有： $ MathJax-Element-49 $

   • $ MathJax-Element-50 $ 是概率 $ MathJax-Element-51 $ 的估计。

   • $ MathJax-Element-109 $ 刻画了数据集 $ MathJax-Element-420 $ 中的样本在属性 $ MathJax-Element-452 $ 上的取值分布情况。

5. 对于特征 $ MathJax-Element-452 $ ，其条件熵为： $ MathJax-Element-56 $ 。

   定义数据集 $ MathJax-Element-420 $ 关于特征 $ MathJax-Element-452 $ 的经验条件熵为：

   $ H(\mathbb D\mid A) = \sum_{i=1}^{n_A}p(A=a_i) H(y\mid A=a_i) = \sum_{i=1}^{n_A} \frac{N_{a_i}}{N}\left[-\sum_{k=1}^K\frac{N_{a_i,k}}{N_{a_i}}\log\frac{N_{a_i,k}}{N_{a_i}}\right] $

   其中：

   • 属性 $ MathJax-Element-67 $ 且类别为 $ MathJax-Element-240 $ 的样本的数量为 $ MathJax-Element-96 $ ，所有样本的总数为 $ MathJax-Element-255 $ 。

     因此有： $ MathJax-Element-63 $ 。

   • $ MathJax-Element-64 $ 是条件熵 $ MathJax-Element-65 $ 的估计。它刻画了数据集 $ MathJax-Element-420 $ 中，属性 $ MathJax-Element-67 $ 中的那些样本中的类别的分布情况。

   • $ MathJax-Element-83 $ 是条件熵 $ MathJax-Element-69 $ 的估计。

2.1 信息增益

1. 特征 $ MathJax-Element-452 $ 对训练数据集 $ MathJax-Element-420 $ 的信息增益 $ MathJax-Element-103 $ 定义为：集合 $ MathJax-Element-420 $ 的经验熵 $ MathJax-Element-81 $ 与关于特征 $ MathJax-Element-452 $ 经验条件熵 $ MathJax-Element-76 $ 之差。即： $ MathJax-Element-77 $ 。

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

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

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

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

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

2.2 信息增益比

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

   公式 $ MathJax-Element-89 $ 中：

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

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

     • 由于 $ MathJax-Element-94 $ ，因此有： $ MathJax-Element-95 $ 。

       即： $ MathJax-Element-96 $ 取值为 0 或者 1 。因此有： $ MathJax-Element-97 $ 。

     • 最终使得 $ MathJax-Element-98 $ 。

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

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

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

   特征 $ MathJax-Element-452 $ 对训练集 $ MathJax-Element-420 $ 的信息增益比 $ MathJax-Element-102 $ 定义为：信息增益 $ MathJax-Element-103 $ 与关于特征 $ MathJax-Element-452 $ 的熵 $ MathJax-Element-109 $ 之比：

   $ g_R(\mathbb D,A)=\frac{g(\mathbb D,A)}{H_A(\mathbb D)} $

   $ MathJax-Element-109 $ 表征了特征 $ MathJax-Element-452 $ 对训练集 $ MathJax-Element-420 $ 的拆分能力。

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

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

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