1. 特征选择问题

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上，扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

2. 信息增益

为了便于说明信息增益的概率，先给出熵与条件熵的定义。

在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为

则随机变量X的熵定义为

其中，定义0log0=0。通常，上式中的log以2为底或以e为底，这时熵的单位分别称为比特（bit）或纳特（nat）。

从定义可知，X的熵只依赖于它的分布，而与它的取值无关，所以也可以将X的熵记作H(p)，即

熵越大，随机变量的不确定性就越大。且0≤H(p)≤log n

当随机变量只取两个值，例如1,0时，即X的分布为

熵为

这时，熵H(p)随概率P变化的曲线如下图（单位比特）。当p=0或p=1时H(p)=0，随机变量完全没有不确定性。当P=0.5时，H(p)=1，熵取值最大，随机变量不确定性最大。

设有随机变量(X,Y)，其联合概率分布为

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。

信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

定义（信息增益） 特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

信息增益算法

输入：训练数据集D和特征A；

输出：特征A对训练数据集D的信息增益g(D,A)。

（1）计算数据集D的经验熵H(D)

（2）计算特征A对数据集D的经验条件熵H(D|A)

（3）计算信息增益

3. 信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。

参考文献

【1】统计学习方法（第2版），李航著，清华大学出版社

相关链接：

1. 学习笔记|朴素贝叶斯算法的实现
2. 学习笔记|k近邻法的实现
3. 学习笔记|k近邻分类算法
4. 学习笔记|感知机的实现
5. 学习笔记|朴素贝叶斯法