前言
决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。
决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。
参考：周志华-《机器学习》&Peter Harrington-《机器学习实战》&李航-《统计学习方法》
信息量与信息熵
信息量是对信息的度量，可以由下式表示，其中$p(x)$为事件发生概率，信息量是对信息的度量。
信息熵(Information entropy)刻画了样本的纯度(purity)，取值范围为0到1。其中0表示样本完全同质，即所有样本都是一类，越接近1代表样本越混乱。信息熵可以由下式表示。
ID3
ID3 算法由 Ross Quinlan 于1979年提出，基本思想是以信息熵为度量，用于决策树节点的属性选择，做法是先计算使用所有特征划分数据集$D$，得到多个特征划分数据集$D$的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
信息增益(Information Gain)的定义如下：如特征$A$对训练集$D$的信息增益$g(D,A)$，可以定义为集合$D$的的经验熵$H(D)$与特征$A$给定条件下的经验条件熵$H(D|A)$之差。
缺点：
- 信息增益偏向取值较多的特征，原因是当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益偏向取值较多的特征。
- 不能处理连续型数据特征，只能通过离散化将连续型数据转化为离散型数据。
- 不能处理缺失数据。
- 没有对决策树进行剪枝处理，很可能会出现过拟合的问题。
C4.5
C4.5 是 Ross Quinlan 在1993年在ID3的基础上改进而提出的，相对于 ID3 算法主要有以下几个改进：
- 用信息增益比来选择属性。
- 在决策树的构造过程中对树进行剪枝。
- 对非离散数据也能处理。
- 能够对缺失数据进行处理。
其中最重要的就是第一点，即解决了ID3中的一大缺点，当一个特征的可取值数目较多时，那么可能在这个特征对应的可取值下的样本只有一个或者是很少个，这时候该特征的信息增益是非常高的，这个时候纯度很高，ID3 决策树会认为这个特征很适合划分，但是较多取值的特征来进行划分带来的问题是它的泛化能力比较弱，不能够对新样本进行有效的预测。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的。
信息增益比(Infomation Gain Ratio)的定义如下：如特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$可以定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即：
其中 Split information 即$H_A(D) = -\sum_{i=1}^n \frac {D_i}{D}\log_2 \frac{D_i}{D}$，$n$是特征$A$的取值的个数。
信息增益比本质是在信息增益的基础之上乘上一个惩罚参数$\frac {1}{H_A(D)}$。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
C4.5 对缺失值的处理方式通常有以下几种：
- 用均值或众数替换
- 直接丢弃缺失样本
- 根据节点的样例上该属性值出现的情况赋一个概率，比如该节点上有10个样本，其中属性A的取值有6个为是，4个为否。那么对改节点上缺失的属性A，以0.6的概率设为是，0.4的概率设为否。
对于连续型特征，C4.5 的做法是将连续型特征离散化，例如$m$个样本的连续特征$A$有$m$个，从小到大排列为${a_1,a_2,…,a_m}$,则 C4.5 取相邻两样本值的平均数，一共取得$m-1$个划分点，其中第$i$个划分点$T_i$表示为：$T_i = \frac{a_i+a_{i+1}}{2}$。对于这$m-1$个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。
缺点：
- 由于惩罚项的存在在，C4.5 会偏向取值较少的特征，所以在生成节点时时并不能直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
- 如果某个特征含有大量连续值，则在离散化处理时会进行大量的排序运算，影响决策树生成效率。
剪枝
剪枝 (Pruning) 的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本，不停地对结点进行划分，因此这会导致整棵树的分支过多，也就导致了过拟合。决策树的剪枝策略最基本的有两种：预剪枝和后剪枝，常用的是后者。
预剪枝 (Pre Pruning) ：预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛化性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
后剪枝 (Post Pruning) ：后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。