决策树 (Decision tree) 是一种基本的分类与回归方法。它是一个树形结构，对于指定特征空间上的数据点来说，总能顺着决策树的根节点一步步分配到子节点最终到达叶节点，而叶节点表示了该数据点所属的分类。在每一次分配到子节点的过程中可以看作是对数据点中特有的特征属性值进行的 if-then 判断。
决策树可以认为是 if-then 规则的集合，也可以认为时定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。如何得到该决策树叫做决策树学习，决策树学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测试，对新的数据，利用决策树模型进行分类。
接下来按照周志华老师的《机器学习》第 4 章[1] 来梳理一下对决策树的学习：
1. 决策树学习
决策树学习的目的是为了生成一颗泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单而直观的 分而治之 (Divide and Conquer) 策略，如下图所示：
决策树的生成是一个自根结点一直到叶结点的递归生成过程。
在递归生成的伪代码表述中，可以看到，有三个地方导致递归返回：
- (行 3) 当前结点包含的样本全部属于同一个类别，无需划分；
- (行 6) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。在这种情况下，把当前结点标记为叶结点，并且将其类别设定为该结点所含样本最多的类别；
- (行 12) 当前结点包含的样本集和为空，不能划分，把当前结点标记为叶结点，但是将其类别设定为其父结点所含样本最多的类别，周志华老师的《机器学习》中在该条件下执行了
return，但是按照我的理解由于这里处于for循环中，虽然属性中的一个取值样本集合为空，但是其它取值情况下还有有可能有样本集合的，如果这里执行了return，那么就跳过了其它取值判断的可能。
另外，其中第 14 行 $A \backslash \lbrace a_\ast \rbrace$ 表示从 $A$ 中去除 $a_\ast$ 属性。
2. 最优划分属性的选择
从递归生成伪代码图示中可以看出，(行 8)选择最优划分属性 $a_\ast$ 是最关键的一步。如何选择决定了决策树的效率与准确率。一般而言我们希望选择一个属性 $a_\ast$ 之后，其分支节点所包含的样本尽可能属于同一类别，即结点的 纯度 (Purity) 越来越高。
根据最优属性 $a_\ast$ 选择方法的不同，决策树大致分为了 ID3 [Quinlan, 1986]、C4.5 [Quinlan, 1993]、CART [Breiman et al., 1984]。
接下来分别介绍三种方法，在之前，先给出周志华老师《机器学习》中表 $4.1$ 中的西瓜数据如下：
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 乌黑 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 乌黑 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 4 | 青绿 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 浅白 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青绿 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 是 |
| 7 | 乌黑 | 稍蜷 | 浊响 | 稍糊 | 稍凹 | 软粘 | 是 |
| 8 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 乌黑 | 稍蜷 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 10 | 青绿 | 硬挺 | 清脆 | 清晰 | 平坦 | 软粘 | 否 |
| 11 | 浅白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 软粘 | 否 |
| 13 | 青绿 | 稍蜷 | 浊响 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 14 | 浅白 | 稍蜷 | 沉闷 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 否 |
| 16 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青绿 | 蜷缩 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
2.1 信息增益 - ID3
2.1.1 什么是信息增益
按照周志华老师《机器学习》中第 $4.2.1$ 小节中所述，假定离散属性 $a$ 有 $V$ 个可能的取值 $\lbrace a_1,a_2,…,a_V \rbrace$，若使用 $a$ 来对样本集 $D$ 进行划分，会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a_v$ 的样本，记为 $D_v$，其对应的信息熵为：
其中 $D_{vk}$ 表示 $D_v$ 中分类为 $k$ 的样本。再考虑到不同的分支 $v$ 结点所包含的样本数不同，给分支结点赋予权重 $|D_v|/|D|$，于是可以计算出属性 $a$ 对样本集 $D$ 进行划分所获得的 信息增益 (Information gain)：
其实，信息增益就是训练数据集 $D$ 中的类别与某一属性之间（或者两个属性之间的，因为最终决策树的目的是要进行分类，所以在决策树的每一个分支判断时都用类别与对应的属性进行信息增益比较）的互信息。我们知道，互信息表示了两事件发生所代表的信息之间的重复部分，当两事件信息重复的部分越大，那么采用一种事件为标准来划分另一种事件所能确定的部分也就越大，也就是说采用属性 $a$ 来进行划分所获得的“纯度提升”越大。考虑极端情况，当属性 $a$ 与类别完全没有关系时，其互信息为 $0$，这时候采用 $a$ 属性作为划分标准对于数据集的类别确认完全没有帮助；当属性 $a$ 的各属性分别与数据集的类别一一对应时，也就是其概率分布完全相同，那么根据互信息的计算公式，其互信息等于各自的熵，也就是说，如果我们采用 $a$ 进行数据的划分，那么数据可以完全干净的划分出来，也就不再含有额外的不可知信息了。
当决策树中选择最优划分属性（行 8）按照信息增益最大来进行时，决策树属于 ID3 决策树。
2.1.2 ID3 树中最优划分属性计算举例
根据上节给出的西瓜数据集，我们学习一个对瓜好坏判断的决策树。在这个例子中分类个数为 $2$ (是好瓜、不是好瓜)，即 $\mathcal{Y}=2$。在决策树学习开始时，根结点包含 $D$ 中所有样例，正例占 $p_1=\frac{8}{17}$，反例占 $p_2=\frac{9}{17}$。根结点的信息熵（下面我们都以比特为单位计算）为：
然后我们要计算出与当前属性集合 {色泽、根蒂、敲声、纹理、脐部、触感}中每个属性的信息增益，也就是对应的互信息。以属性“色泽”为例，它有 $3$ 个可能取值：{青绿、乌黑、浅白}。以该属性对数据集进行划分，可以得到 $3$ 个子集，分别为：$D_1$(色泽=青绿)、$D_2$(色泽=乌黑)、$D_3$(色泽=浅白)。
对子集 $D_1$ 来说，包含了编号为 $\lbrace1,4,6,10,13,17\rbrace$ 的 $6$ 个样例，其中正例为 $\lbrace1,4,6\rbrace$，占 $p_1=\frac{3}{6}$ ；反例为 $\lbrace10,13,17\rbrace$，占 $p_1=\frac{3}{6}$。计算其熵为：
依次可以计算另外两个子集的信息熵为：
最终可以计算数据集 $D$ 的类别信息在属性“色泽”熵的信息增益（也可以理解为类别与“色泽”属性之间的互信息）为：
重复上述的计算步骤，我们可以计算出其他属性的信息增益：
经过比较，发现采用“纹理”进行划分得到的信息增益最大，于是它被选为划分属性。下图给出了根据“纹理”属性划分之后的数据子集：
对每一个数据子集按照上边的步骤继续划分下去就能得到最终的决策树（需要注意的是每次样例子集中的属性不包含父结点中划分所依赖的属性），如下图所示：
2.2 信息增益率 - C4.5
采用信息增益来进行划分属性的决策有一个潜在的问题，当某一个属性的取值种类非常多时，对应每一个属性取值的样本子集，其分类的信息熵可能会变得很小。为了说明，采用一种极端情况，假设我们对上一节中要分类的西瓜数据进行决策树生成时，把“编号”也当作一种可以作为划分依据的属性。则在这种情况下，每一个编号属性对应一个实例，且其分类是确定的，那么对于每一个“编号”属性取值来说，其分类信息熵为 $0$，计算“编号”分类所带来的信息增益为：
最后计算出来的信息增益很大。但是显然，用“编号”属性来作为结点的划分是没有意义的。思考其中的问题在于，对数函数并不是线性的，信息量的减少速度大于类别数量的增加速度。信息增益准则对取值数目较多的属性有所偏好，为了减小这种偏好，C4.5 决策树 采用 信息增益率 (gain ratio) 来选择最优划分属性。其定义如下：
其中，
到这里，我们就可以发现，信息增益率是用属性分类的信息熵对由属性分类引起的互信息熵进行了归一。属性的种类越多其信息熵通常也会越大。对西瓜数据，有：$H(触感)=0.874\ (V=2)$，$H(色泽)=1.580\ (V=3)$，$H(编号)=4.088\ (V=17)$。
最后一点需要注意的是，增益率准则虽然减少了对取值数目较多的属性依赖，但是增加了对取值数目较少的属性偏好。因此， C4.5 并没有直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出 信息增益 高于 平均水平 的属性，再从中选择 增益率 最高的。
2.3 基尼指数 - CART
最后介绍一种选择划分属性的依据是使用 基尼指数 (Gini index)。数据集合 $D$ 的纯度可用基尼指数来度量：
直观来看，$\textrm{Gini}(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此，$\textrm{Gini}(D)$ 越小，则数据集 $D$ 的纯度越高。
对特定属性 $a$ 的基尼指数定义如下：
我们在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即：
采用基尼指数作为划分属性的判据的决策树是一种 CART 决策树。
3. 决策树剪枝
3.1 决策树的损失函数
刚开始我提到，决策树可以看作是一系列 if-then 规则的集合。这个规则集合有一个重要的性质：互斥并且完备。意思就是说，拿来任意一个实例，顺着规则的起点（根结点）出发，最终都有且只有一条路径到达某一个具体的叶结点（具体的分类），并且不会出现实例无法分类的情况。
如果不考虑泛化能力，在训练集上生成的所有不同规则集合对应的决策树中，挑选出最优的决策树，可以根据所有叶结点中的预测误差来衡量，即模型与训练数据的拟合程度。设树 $T$ 的叶结点个数为 $|T|$，$t$ 是树 $T$ 的一个叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个，$k=1,2,…,K$，$K$ 为样本空间中的所属分类数量。叶结点 $t$ 上的经验熵 $H_t(T)$ 为
代表了该叶结点的分类还有多少信息量不知道（混乱程度），可以这么考虑一个理想的极端情况，当该叶结点中只有一个分类 $k_n$ 时，那么 $N_{tk_n}=N_t$，其它的 $N_{k_1},…,N_{k_{n-1}},N_{k_{n+1}},…,N_{k_K}$ 全部为 $0$，最终 $H_t(T)=0$，这个结论与分类已经完全的结果是相吻合的。那么我们可以说，经验熵 $H_t(T)$ 就代表了连接该叶结点的整个路径对数据分类的彻底性。
考虑到所有的叶结点每个叶结点中的样例个数不同，我们采用
来衡量模型对训练数据的整体测量误差。
但是如果仅仅用 $C(T)$ 来作为优化目标函数，就会导致模型走向过拟合的结果。因为我们可以尽可能的对每一个分支划分到最细结来使得每一个叶结点的 $H_t(T)=0$，最终使得 $C(T)=0$ 最小。
为了避免过拟合，我们需要给优化目标函数增加一个正则项，正则项应该包含模型的复杂度信息。对于决策树来说，其叶结点的数量 $|T|$ 越多就越复杂，我们用添加正则项的
来作为优化的目标函数，也就是树的损失函数。参数 $\alpha$ 控制了两者之间的影响程度。较大的 $\alpha$ 促使选择较简单的模型（树），较小的 $\alpha$ 促使选择较复杂的模型（树）。
决策树的生成过程并不是一个准确的求解树的损失函数的最优化方法。三种决策树学习方法都是一种启发式的求解步骤，在每一步扩大树的规模的时候都是找当前步能使分类结果提升最明显的选择。
如果以文章最开始标示的三个递归学习返回条件进行树的学习，那么最后学习的树是一个以 $C(T)$ 为损失函数的最优化过程。最后学习到的决策树对训练数据集能达到令人满意的结果，但是对于未知的测试集来说却未必有很好的分类能力。即数据集的泛化能力不能保证。
为了提高决策树的泛化能力，需要对树进行 剪枝 (Pruning)，把过于细分的叶结点（通常是数据量过少导致噪声数据的影响增加）去掉而回退到其父结点或更高的结点，使其父结点或更高的结点变为叶结点。
3.2 如何进行决策树剪枝
决策树的剪枝基本策略有 预剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning) [Quinlan, 1933]。根据周志华老师《机器学习》一书中所描述是先对数据集划分成训练集和验证集，训练集用来决定树生成过程中每个结点划分所选择的属性；验证集在预剪枝中用于决定该结点是否有必要依据该属性进行展开，在后剪枝中用于判断该结点是否需要进行剪枝。
3.2.1 预剪枝
仿照第 1 小节中的决策树生成流程图，加入预剪枝后的决策树生成流程图如下，
其中红色部分是我参考周志华老师《机器学习》第 4.3.1 小节中给出的实例总结的算法流程。其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。
3.2.2 后剪枝
对于后剪枝，周志华老师《机器学习》中述说如下：
后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。
对于后剪枝，书中采用了具体的西瓜分类决策树作为剪枝操作讲解，跟着流程走下来感觉挺顺畅，无非就是对想要进行剪枝的结点进行验证集数据的准确性比较，如果剪枝能带来准确性的提高，那么就剪枝，否则保留。然后去判断其它需要考虑剪枝的结点。
在进行剪枝判断的操作中，只对底端结点进行判断。一步一步收缩至每一个底端结点对验证集数据都有更好的分类准确率为止。
更具体地，李航老师《统计学习方法》中第 5.5.2 小节具体介绍了 CART 剪枝算法的步骤流程。刚开始看这部分内容的时候，不容易看懂，后来结合网上的解释回过头来发现其实很简单。下边是参考书中以及网上的解释总结的一套算法流程：
针对流程图中的第 8 步计算，按照书中的描述逻辑，对 $T_0$ 中的任意内部结点 $t$，以 $t$ 为单结点树（结点即为叶，没有分支）的损失函数是
以 $t$ 为根结点的子树 $T_t$ 的损失函数是
当 $\alpha=0$或充分小时，有不等式
当 $\alpha$ 增大到某一个值时，有
当 $\alpha$ 再继续增大时，不等式反向，所以只要 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，$T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点更少，因此 $t$ 比 $T_t$ 更可取，对 $T_t$ 进行剪枝。
这个位置容易让人疑惑，逻辑上让人不是很容易想明白，需要多看几遍。其实它的逻辑是这样的：
剪枝的目的不是为了最小化损失函数，剪枝的目的是为了达到一个更好的泛化能力。而对于决策树来说，叶结点的数量越多，反应了决策树对训练数据的细节反应的越多，继而弱化了泛化能力。要想提高泛化能力就需要进行剪枝，而在 3.1 节中给出的损失函数中，$\alpha$ 值衡量了损失函数中叶结点数量的权重，$\alpha$ 值越大，在最小化损失函数时，需要更多的考虑叶结点数量的影响。$\alpha$ 可以看作一个系数，不同的 $\alpha$ 对应于不同的损失函数。而对于所有的这些损失函数来说，在训练集上进行决策树生成时候的步骤都一样，差别只是在判断某些结点是否进行展开的区别。
这个有点类似于对一个函数的泰勒级数展开，而 $\alpha$ 值控制着展开的次数项，越小的值展开的次数项越多（往回收缩的高次项越少）。因为决策树的结点个数是有限的，对应到 $\alpha$ 的值来说也是有限的。上述求 $\alpha$ 过程就是得到具体收缩每一个分支对应的值。
CART 剪枝算法的前半部分递归寻找 $\alpha$ 的过程就相当于对一个已经展开到极值的泰勒展开式依次进行收缩，并且找到其对应的系数。最终哪一级的展开泛化能力更好，还是要靠验证集数据来进行验证。展开的太多对训练集符合度好而对验证集不好，展开的太小了偏差又变大了，对训练集和验证集数据符合都不好。所以算法中直到最后才用到了验证集数据，最开始的剪枝判断递归过程都是基于训练数据进行的。
这里有一个疑惑就是，按照这样的逻辑来获得的 $\alpha_\textrm{list}$ 真的满足递增顺序吗？
借鉴周志华老师《机器学习》中的图 4.5 来对 CART 剪枝算法进行梳理如下。
该图展示的是表 4.2 中的西瓜数据集对应的决策树。
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 乌黑 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 乌黑 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青绿 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 是 |
| 7 | 乌黑 | 稍蜷 | 浊响 | 稍糊 | 稍凹 | 软粘 | 是 |
| 10 | 青绿 | 硬挺 | 清脆 | 清晰 | 平坦 | 软粘 | 否 |
| 14 | 浅白 | 稍蜷 | 沉闷 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 否 |
| 16 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青绿 | 蜷缩 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 4 | 青绿 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 浅白 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 8 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 乌黑 | 稍蜷 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 11 | 浅白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 软粘 | 否 |
| 13 | 青绿 | 稍蜷 | 浊响 | 稍糊 | 凹陷 | 硬滑 | 否 |
下面按照给出的算法流程来对该决策树进行剪枝操作。我们采用 3.1 小节中关于 $C(T)$ 和 $C_\alpha(T)$ 的定义。
1. 第一层递归： 树 $T_0=\lbrace 1,2,3,4,5\rbrace$，其在训练集数据上的执行情况见下图：
对其每一个内部结点计算其剪枝后的整体树的损失函数减少程度 $g(t)$。
以结点 $5$ 为例，一例好一例坏，
同理，可以计算出:
比较之后发现，最小的是 $g(3)$，对应的结点是 $t(3)$，对其进行剪枝后得到新的树 $T_1$ 在训练集数据上的执行情况见下图：
2. 第二层递归： 以树 $T_1=\lbrace 1,2\rbrace$ 为新的输入，重复第一层递归中的计算步骤：
比较之后发现，最小的是 $g(2)$，对应的结点是 $t(2)$，对其进行剪枝后得到新的树 $T_2$ 在训练集数据上的执行情见下图:
3. 第三层递归： 以树 $T_2=\lbrace 1\rbrace$ 为新的输入，重复第一层递归中的计算步骤：
现在只有一个 $g(1)$，所以其也是最小的一个。对应的结点是 $t(1)$，对其进行剪枝后得到新的树 $T_3$ 在训练集数据上的执行情见下图:
到此为止，$T_3$ 已经是一个根结点单独构成的树，触发了递归退出条件。最后得到的 $T_\textrm{list}=(T_0,T_1,T_2,T_3)$， $\alpha_\textrm{list}=(0,0.5714,1.6226,5)$，从结果看 $\alpha_\textrm{list}$ 中的值确实是从小到大排列，但为什么是这样的内层逻辑还需要深入思考一下。
4. 验证集数据交叉验证：
以 $T_\textrm{list}$ 中的每一个决策树来预测验证集上的数据得到准确率（正确分类样本数量除以整个样本数量）列表
所以最终选择 $T_2$ 作为最优子树：
3.3.3 两种剪枝策略对比
- 后剪枝决策树通常比预剪枝决策树保留了更多的分支；
- 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树；
- 后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。
更多的剪枝方法参考文后链接 7。
参考
1: 《机器学习》Page 73
2: 《统计学习方法》 Page 72
2: 机器学习相关知识整理系列之一：决策树算法原理及剪枝（ID3,C4.5,CART）
3: 决策树剪枝算法原理
4: 决策树之剪枝原理与CART算法
5: 决策树剪枝(cart剪枝)的原理介绍
6: CART树剪枝的操作的理解
7: 决策树剪枝算法