正文
熵与信息增益
决策树模型本质上就是一个 IF-Then 规则的集合
决策树学习的第一步就是“特征选择”
特征选择分两个步骤进行：
选择对训练数据具有最大分类能力的特征进行树的叶子节点的分类；
选择该特征最合适的分裂点进行分裂。
熵(Entropy)，是表示随机变量不确定性的度量。
假设X是一个具有有限个值的离散型随机变量，服从如下的概率分布：
P(X=xi)=pi,i=1,2,...,n
那么随机变量XX的熵定义为：
H(X)=−∑i=1npilog2pi
其中pi为xi的概率，取值范围在[0,1]之间。
我们以随机变量只取0、1两个值为例，假设X服从如下分布:
根据熵公式，XX的熵为
这时，熵H(X)H(X)随概率pp变化的曲线为：
由图可知，当p=0p=1时熵为0，也即随机变量完全没有不确定性(即完全确定);
当p=0.5时熵取值最大，不确定性最高。
信息增益：
设随机变量(X,Y)的联合概率分布为：
P(X=xi,Y=yi)=pij，i=1,2,...n;j=1,2,...,m
条件熵 H(Y|X)表示在已知随机变量 X的取值条件下随机变量Y的不确定性，其数学定义为 X给定的条件下Y的条件概率分布的熵对 X的数学期望，表达式如下:
H(Y|X)=∑i=1npiH(Y|X=xi)
其中 pi=P(X=xi),i=1,2,...,n
在此基础上，我们引出信息增益(Information Gain)的概念，它表示在特征X给定的条件下使得类Y的信息不确定性减少的程度。
数学表述如下：特征A对训练集数据DD的信息增益G(D,A)定义为集合DD的熵H(D)H(D)与在特征A给定的条件下D的条件熵H(D|A)之差，即：
G(D,A)=H(D)−H(D|A)
特征选择策略
决策树的学习应用信息增益准则选择特征。
给定训练集D和特征A。由熵、条件熵和信息增益的定义我们可以知道：
熵H(D)表示对数据集D进行分类的不确定性；
条件熵H(D|A))表示在特征AA给定的条件下对数据集D进行分类的不确定性；
信息增益G(D,A表示在特征AA给定的情况下使得数据集D进行分类的不确定性减少的程度。
显然，对于数据集DD而言，信息增益依赖于特征，一般情况下，不同的特征会有不同的信息增益。信息增益大的特征具有更强的分类能力。
所以我们在构建决策树的过程中，应该选择信息增益最大的特征进行分裂构建。
决策树的生成
设训练集为D，|D|表示样本容量大小；总共有K给类，用Ck，k=1,2,...,K表示。
设特征A有n个不同的取值a1,a2,...an，根据特征A的取值将数据D划分为n个互不相交的子集{D1,D2,...,Dn}，|Di|,i=1,2,...,n表示第i个子集中的样本的个数
则显然有：
∑i=1n|Di|=|D|
ID3算法
ID3算法的核心是递归的构建决策树，递归的过程中在每个节点上应用信息增益准则选择特征，直至满足递归停止条件：所有特征的信息增益都很小或者没有特征可以选择。
假设有训练数据集DD，特征集AA，最小信息增益阀值ϵϵ和最终训练出来的决策树TT
则ID3算法的执行过程：
如果DD中所有实例属于同一类CkCk，那么TT就是单节点树，并且将CkCk作为该节点所表示的类别，返回TT;
如果A=∅A=∅，则TT为单节点树，并且将DD中实例数量最多的类作为该节点的类标记，返回TT;
否则，计算AA中各特征对数据集DD的信息增益，选择信息增益最大的特征AGAG;
如果AGAG的信息增益小于ϵϵ，此时TT设置为单节点树，同时也选择将DD中实例最多的类作为该节点的类标记，返回TT;
否则，对特征AGAG的每一个可能的取值aiai，根据AG=aiAG=ai将数据集DD分割为互不相交的子集DiDi，此时依然将DiDi中实例数最多的类作为标记，构建子节点。叶子节点和子节点构成树TT，返回TT;
对第5步中，第ii个子节点，以DiDi为训练集，以A−{AG}A−{AG}为新的特征集递归的调用1-5步得到子树TT，并返回。
C4.5算法
C4.5算法与ID3算法基本一致，只是特征选择的选择方法从ID3依据的信息增益改为了信息增益比。
信息增益比：
以信息增益作为划分训练数据集DD的特征，会倾向于选择特征值较多的特征，在不同特征的数量不一致的情况下，这会带来一种不公平性，而使用信息增益比(Information Gain Ratio)就可以解决这个问题。
信息增益比的定义：
特征AA对训练数据集DD的信息增益比GR(D,A)GR(D,A)表示特征AA的信息增益G(D,A)G(D,A)与训练数据集DD关于特征AA的熵HA(D)HA(D)的比值：
nn 是特征AA所能取得的不同值的总个数。
C4.5算法的过程与ID3算法的过程几乎完全一致，只需把ID3算法过程中的“按照信息增益选择特征”换为“按照信息增益比选择特征”即可。
决策树的剪纸策略
决策树的生成算依靠法递归构建决策树，直到不能继续构建为止。然而，这样产生的决策树很容易过分的学习训练样本，使得它对未知的测试数据的分类效果比较差，即这样产生的决策树很容易过拟合。
过拟合的原因在于我们构建的决策树过分复杂，导致其过多地学习训练样本的分布，而对未知样本的学习泛化能力较弱。
解决这个问题的方法就是简化已生成的决策树，使其变得更简单。
在决策树学习的过程中将已经生成的决策树进行简化的过程称作“剪枝”。也就是说，我们可以将决策树中划分的过细的叶子节点剪去，退回到其父节点成为新的叶子节点，使得新的决策树变得简单，并且能够在未知的测试数据的预测上取得更好的分类结果。
决策树的剪枝策略主要分为两大类：预剪枝策略和后剪枝策略
预剪枝策略的常用方法：
指定每一个结点所包含的最小样本数目。例如10，则该结点总样本数小于10时，则不再分；
指定树的高度或者深度。例如树的最大深度为4；
指定结点的熵。若该节点的熵小于某个值，不再划分。
预剪枝策略优缺点：
优点：预剪枝策略能够减少不必要的分裂操作，节省时间；
缺点：在预剪枝后构建决策树的某个时刻可能会出现更高的增益，也就是说预剪枝有可能得不到最优的树。
后剪枝策略的常用方法：
将决策树增长到它的最大深度，递归的进行剪枝，剪去那些使得增益值为负值的叶子节点。
后剪枝策略优缺点：
优点：能够获得最优的剪枝策略决策树；
缺点：那些被后剪枝的树节点的分裂过程浪费时间。
以sklearn中的iris数据集为例，得到的鸢尾花决策树如下：
