这一篇我们来讲决策树中的特征选择问题，会涉及到什么是特征选择以及特征选择的准则。
「特征选择」顾名思义就是对特征进行选择，以达到提高决策树学习的效率的目的。那么选择的是什么样的特征呢？这里我们选择的特征需要是对训练数据有分类能力的特征，如果一个特征参与分类与否和随机分类的结果差别不大的话，我们就说这个特征没有分类能力，舍去这个特征对学习的精度不会有特别大的影响。
特征选择是决定用哪个特征来划分特征空间。
那么如果有多个有分类能力的特征怎么办呢？直观上来讲，如果一个特征比另外一个特征有更好的分类能力，那就应该选择它，我们按照这个特征将训练数据分割成子集，各个子集在当前条件下就会有最好的分类结果。
比如女生找男朋友，可能这个女生首先会问「这个男生帅不帅」，其次再是「身高如何」、「有无房子」、「收入区间」、「做什么工作」等等，那么「帅否」这个特征就是这位女生心中有着最好分类能力的特征了。
那怎么判断哪个特征有更好的分类能力呢？这时候「信息增益」就要出场了。
为了解释什么是信息增益，我们首先要讲解一下什么是 熵（entropy）。
在热力学与化学中：
熵是一种测量在动力学方面不能做功的能量的总数，当总体熵增加，其做功能力也下降，熵的度量是能量退化的指标。
1948 年，香农把热力学中的熵引入到信息论中，称为 香农熵。根据维基百科的描述：
在信息论中，熵是接收的每条消息中包含的信息的平均量。
更一般的，熵表示随机变量的不确定性。假设一个有限取值的离散随机变量 X 的概率分布如下：
\[P(X = x_i) = p_i,\ \ \ \ i = 1, 2, \cdots, n\]那么它的熵定义为：
\[H(X) = -\sum_{i=1}^n p_i \log_{b} p_i\]上式中的 b 通常取 2 或者自然对数 e，这时熵的单位就分别称为比特（bit）或纳特（nat），这也是信息论中，信息量的单位。
从上式中，我们可以看到，熵与 X 的取值是没有关系的，它只与 X 的分布有关，所以 H 也可以写作 p 的函数：
\[H(p) = -\sum_{i=1}^n p_i\log p_i\]我们现在来看两个随机变量的情况。
假设随机变量 (X, Y) 的联合概率分布如下：
\[P(X = x_i, Y = y_j) = p_{ij},\ \ \ \ i = 1, 2, \cdots, n;\ j = 1, 2, \cdots, m\]我们使用 条件熵（conditional entropy）H(Y|X) 来度量在已知随机变量 X 的条件下随机变量 Y 的不确定性。
条件熵定义为：X 给定条件下，Y 的条件概率分布的熵对 X 的数学期望。
是不是看晕了，没关系，我们来看数学公式，这才是最简单直接让你晕过去的方法：
\[H(Y|X) = \sum_{i=1}^n p_i H(Y|X=x_i),\ \ \ \ p_i = P(X=x_i),\ i = 1, 2, \cdots, n\]有了上面的公式以后，条件熵的定义就非常容易理解了。
那么这些奇奇怪怪的熵又和我们要讲的信息增益有什么关系呢？
有经验的读者可能猜出来了，既然熵是信息量的一种度量，那么信息增益就是熵的增加咯？
没错，由于熵表示不确定性，严格来说，信息增益（information gain）表示的是「得知了特征 X 的信息之后，类别 Y 的信息的不确定性减少的程度」。
我们给出信息增益的最终定义：
\[g(D, A) = H(D) - H(D|A)\]特征 A 对训练数据集 D 的信息增益 g(D, A)，定义为，集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件熵 H(D|A) 之差。
这里你只要知道经验熵和经验条件熵就是依据经验（由数据估计特别是极大似然估计）得出来的熵就可以了。
假设我们有一个训练集 D 和一个特征 A，那么，经验熵 H(D) 就是对 D 进行分类的不确定性，经验条件熵 H(D|A) 就是给定 A 后，对 D 分类的不确定性，经验熵 H(D) 与经验条件熵 H(D|A) 的差就是信息增益。
很明显的，不同的特征有不同的信息增益，信息增益大的特征分类能力更强。我们就是要根据信息增益来选择特征。
下面我们给出信息增益的算法。
首先对一些符号给出他们的定义：
假设我们有一个训练集 D，训练集的总的样本个数即样本容量为 |D|，最后的结果有 K 个类别，每个类别表示为 $C_k$，$|C_k|$ 为属于这个类的样本的个数，很显然 $\sum_{k=1}^K |C_k| = |D|$。
再假设我们有一个特征叫 A，A 有 n 个不同的取值 ${a_1, a_2, \cdots, a_n}$，那么根据 A 我们可以将 D 分成 n 个子集，每个子集表示为 $D_i$，$|D_i|$ 是这个子集的样本个数，很显然 $\sum_{i=1}^n |D_i| = |D|$。
我们把 $D_i$ 中属于类别 $C_k$ 的集合称作 $D_{ik},\ D_{ik} = D_i \bigcap C_k$，$|D_{ik}|$ 是其样本个数。
信息增益的计算就分为如下几个步骤：
看到这个小标题，可能有人会问，信息增益我知道了，信息增益比又是个什么玩意儿？
按照经验来看，以信息增益准则来选择划分数据集的特征，其实倾向于选择有更多取值的特征，而有时这种倾向会在决策树的构造时带来一定的误差。
为了校正这一误差，我们引入了信息增益比（information gain ratio），又叫做信息增益率，它的定义如下：
\[g_R(D, A) = \frac{g(D, A}{H_A(D)}\]特征 A 对训练数据集 D 的信息增益比 $g_R(D, A)$ 定义为其信息增益 $g(D, A)$ 与训练数据集 D 关于特征 A 的值的熵 $H_A(D)$ 之比。
其中，$H_A(D) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$，n 是 A 取值的个数。
在下一节中，我们要讲到的两个决策树算法 ID3 算法和 C4.5 算法，分别会采用信息增益和信息增益比作为特征选择的依据。