决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别（即叶结点）中。

一般而言，决策树的生成包含了特征选择、树的构造、树的剪枝三个过程。在第一个问题中对几个常用决策树进行对比，在第二个问题中探讨决策树不同剪枝方法之间的区别与联系。

1、决策树有哪些常用的启发函数？

决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一棵树形的分类结构。我们既希望它能拟合训练数据，达到良好的分类效果，同时又希望控制其复杂度，使得模型具有一定的泛化能力。对于一个特定的问题，决策树的选择可能有很多种。例如在相亲中，对对方要求是月薪一定过万还是可以不过万就是一个简单的决策树。

从若干不同的决策树中选取最优的决策树是一个NP完全问题，在实际中通常会采用启发式学习的方法去构建一棵满足启发式条件的决策树。常用的决策树算法有：ID3、C4.5、CART，它们构建树所用的启发式函数是什么？除了构建准则之外，它们之间的区别与联系是什么？

首先看一下这几种决策树构造时使用的准则。

ID3————最大信息增益

对于样本集合$D$，类别数为$K$，数据集$D$的经验熵表示为

$$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$

其中$C_k$是样本集合$D$中属于第$k$类的样本子集，$|C_k|$表示该子集的元素个数，$|D|$表示样本集合的元素个数。

然后计算某个特征$A$对于数据集$D$的经验条件熵$H(D|A)$为：

其中，$D_i$表示$D$中特征$A$取第$i$个值的样本子集，

$D_{ik}$表示$D_i$中属于第$k$类的样本子集。

于是信息增益$g(D,A)$可以表示为二者之差，可得

$$g(D,A)=H(D)-H(D|A)$$

这里用一个例子来说明一下计算过程。

有5个单身狗追求一个姑娘，年龄有两个属性(老，年轻)，长相有三个属性（帅，一般，丑），工资有三个属性（高，中等，低），会写代码有两个属性（会，不会），最终分类结果有两类（见，不见）。根据姑娘主观意愿得到下表：

在这个问题中

$$H(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971$$

根据计算某个特征$A$对于数据集$D$的经验条件熵$H(D|A)$公式可计算出4个分支结点的信息熵为:

$$ H(D|年龄)=\frac{1}{5}H(老)+\frac{4}{5}H(年轻) =\frac{1}{5}(-0)+\frac{4}{5}\left(-\frac{2}{4}log_2\frac{2}{4}-\frac{2}{4}log_2\frac{2}{4}\right)=0.8 $$

$$ H(D|长相)=\frac{1}{5}H(帅)+\frac{3}{5}H(一般)+\frac{1}{5}H(丑)=0+\frac{3}{5}\left(-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\right)+0=0.551 $$

$$ H(D|工资)=\frac{3}{5}H(高)+\frac{1}{5}H(中等)+\frac{1}{5}H(低)=\frac{3}{5}\left(-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\right)+0+0=0.551 $$

$$ H(D|写代码)=\frac{3}{5}H(不会)+\frac{2}{5}H(会)=\frac{3}{5}(0)+\frac{2}{5}(0)=0 $$

根据$g(D,A)$可计算出各个特征的信息增益为：

$$g(D,年龄)=0.171$$

$$g(D,长相)=0.42$$

$$g(D,工资)=0.42$$

$$g(D,写代码)=0.971$$

显然，对于特征“写代码”的信息增益最大，所有的样本根据此特征可以直接被分到叶结点（即见或不见）中，完成决策树生长。当然，在实际应用中，决策树往往不能通过一个特征就完成构建，需要在经验熵非0的类别中继续生长。

C4.5————最大信息增益比

特征$A$对于数据集$D$的信息增益比定义为

$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$

其中

称为数据集$D$关于$A$的取值熵。针对上述问题，可以根据上市求出数据集关于每个特征的取值熵为：

$$H_{年龄}(D)=-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2\frac{4}{5}=0.722$$

$$H_{长相}(D)=-\frac{1}{5}log_2\frac{1}{5}-\frac{3}{5}log_2\frac{3}{5}-\frac{1}{5}log_2\frac{1}{5}=1.371$$

$$H_{工资}(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{1}{5}log_2\frac{1}{5}-\frac{1}{5}log_2\frac{1}{5}=1.371$$

$$H_{写代码}(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971$$

根据特征$A$对于数据集$D$的信息增益比公式可计算出各个特征的信息增益比为：

$$g_R(D,年龄)=0.236$$

$$g_R(D,长相)=0.402$$

$$g_R(D,工资)=0.402$$

$$g_R(D,写代码)=1$$

信息增益比最大的仍是特征“写代码”，但通过信息增益比，特征“年龄”对应的指标上升了，而特征“长相”和特征“工资”却有所下降。

CART————最大基尼系数(Gini)

Gini描述的是数据的纯度，与信息熵含义类似。

$$Gini(D)=1-\sum_{k=1}^n\left(\frac{|C_k|}{|D|}\right)^2$$

CART在每一次迭代中选择基尼质数最小的特征及其对应的切分点进行分类。但与ID3、C4.5不同的是，CART是一棵二叉树，采用二元切割法，每一步将数据按特征$A$的取值切成两份，分别进入左右子树。特征$A$的Gini指数定义为：

$$Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$$

继续之前的例子，应用CART分类准则，根据上式可计算出各个特征的Gini指数为：

$$Gini(D|年龄=老)=0.4$$

$$Gini(D|年龄=年轻)=0.4$$

$$Gini(D|长相=帅)=0.4$$

$$Gini(D|长相=丑)=0.4$$

$$Gini(D|写代码=会)=0$$

$$Gini(D|写代码=不会)=0$$

$$Gini(D|工资=高)=0.47$$

$$Gini(D|工资=中等)=0.3$$

$$Gini(D|工资=低)=0.4$$

在“年龄”“长相”“工资”“写代码”这四个特征中，可以很快发现特征“写代码”的Gini指数最小，为$0$，因此选择特征“写代码”作为最优特征，“写代码=会”为最优切分点。按照这种切分，从根结点会直接产生两个叶结点，基尼质数降为0，完成决策树生长。

通过对比三种决策树的构造准则，以及在同一个例子上的表现，可以看出这三者之间的差别。

首先，ID3采用信息增益作为评价标准，除了“会写代码”这个逆天特征外，会倾向于取值较多的特征。因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。这一点在实际应用中是个缺陷。比如有一个“DNA”特征，那么每个人的DNA都不同，如果ID3按照“DNA”特征进行划分那一定就是最优的（条件熵为$0$），但这种分类的泛化能力是非常弱的。因此C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。

其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排列之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。

从应用角度，ID3和C4.5只能用于分类任务，而CART（Classification and Regression Tree,分类回归树）从名字就可以看出其不仅可以用于分类，也可以用于回归任务（回归树使用最小平方误差准则）。

此外，从实现细节、优化过程等角度，这三种决策树还有一些不同。比如，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一棵二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性和泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。

至此，从构造、应用、实现等角度对比了ID3、C4.5、CART这三种经典的决策树模型。

2、如何对决策树进行剪枝？

一棵完全生长的决策树会面临一个很严重的问题，即过拟合。假设真需要考虑DNA特征，由于每个人的DNA都不同，完全生长的决策树所对应的每个叶结点种只会包含一个样本，这就导致决策树是过拟合的。用它进行预测时，在测试集上的效果会很差。因此需要对决策树进行剪枝，剪掉一些枝叶，提升模型的泛化能力。

决策树的剪枝通常有两种方法，预剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。那么这两种方法是如何进行的？它们又各有什么优缺点？

预剪枝，即在生成决策树的过程中提前停止树的增长。而后剪枝，是在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树。

预剪枝

预剪枝的核心思想是在树种结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同事存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长以下几种方法。

（1）当树到达一定深度的时候，停止树的生长。

（2）当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。

（3）计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。但如何准确地估计何时停止树的生长（即上述方法中的深度或阈值），针对不同问题会有很大差别，需要一定经验判断。且预剪枝存在一定局限性，有欠拟合的奉献，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著提升。

后剪枝

后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning,REP）、悲观剪枝（Pessimistic Error Pruning,PEP）、代价复杂度剪枝（Cost Complexity Pruning,CCP）、最小误差剪枝（Minimum Error Pruning,MEP）、CVP（Critical Value Pruning）、OPP（Optimal Pruning）等方法，这些剪枝方法各有利弊，关注不同的优化角度。

这里引用著名CART剪枝方法CCP的介绍。

代价复杂度剪枝主要包含一下两个步骤。

（1）从完整决策树$T_0$开始，生成一个子树序列{$T_0$,$T_1$,$T_2$,$…$,$T_n$}。

其中$T_{i+1}$由$T_i$生成，$T_n$为树的根节点。

（2）在子树序列中，根据真实误差选择最佳的决策树。

步骤（1）从$T_0$开始，裁剪$Ti$中关于训练数据集合误差增加最小的分支以得到$T{i+1}$。

具体的，当一棵树$T$在结点$t$处剪枝时，它的误差增加可以用$R(t)-R(T_t)$表示，其中$R(t)$表示进行剪枝之后的该结点误差，$R(T_t)$表示未进行剪枝时子树$T_t$的误差。考虑到树的复杂性因素，我们用$|L(T_t)|$表示子树$T_t$的叶子结点个数，则树在结点t处剪枝后的误差增加率为：

$$α=\frac{R(t)-R(T_t)}{|L(T_t)|-1}$$

在得到$T_i$后，我们每步选择$α$最小的结点进行相应剪枝。

用一个例子说明生成子树序列的方法。假设把场景问题扩展一下，女孩需要对80个人进行见或者不见的分类。假设根据某个规则，已经得到了一棵CART决策树$T_0$。如图：

初始决策树$T_0$

此时共有5个内部结点可供考虑，其中

$$α(t_0)=\frac{25-5}{6-1}=4$$

$$α(t_1)=\frac{10-(1+2+0+0)}{4-1}=2.33$$

$$α(t_2)=\frac{5-(1+1)}{2-1}=3$$

$$α(t_3)=\frac{4-(1+2)}{2-1}=1$$

$$α(t_4)=\frac{4-1}{2-1}=4$$

可见$α(t_3)$最小，因此对$t_3$进行剪枝，得到新的子树$T_1$,如图：

对初始决策时$T_0$的$t_3$结点剪枝得到新的子树$T_1$

而后继续计算所有结点对应的误差增加率，分别为$α(t_1)=3$，$α(t_2)=3$，$α(t_4)=4$。因此对$t_1$进行剪枝，得到$T_2$,如图：

对$T_1$中$t_1$结点剪枝得到新的子树$T_2$

在步骤（2）种，需要从子树序列中选出真实误差最小的决策树。CCP给出了两种常用的方法：一种是基于独立剪枝数据集，该方法与REP类似，但由于其只能从子树序列{$T_0$,$T_1$,$T_2$,…,$T_n$}中选择最佳决策树，而非像REP能在所有可能的子树种寻找最优解，因此性能上会有一定不足。另一种是基于$k$折交叉验证，将数据集分成$k$份，前$k-1$份用于生成决策树，最后一份用于选择最优的剪枝树。重复进行N次，再从这N个子树种选择最优的子树。

代价复杂度剪枝使用交叉验证策略时，不需要测试数据集，精度与REP差不多，但形成的树复杂度小。而从算法复杂度角度，由于生成子树序列的时间复杂度与原始决策树的非叶结点个数呈二次关系，导致算法相比REP、PEP、MEP等线性复杂度的后剪枝方法的运行时间开销更大。

剪枝过程在决策树模型中占据着极其重要的地位。有很多研究表明，剪枝比树的生成过程更关键。对于不同划分标准生成的过拟合决策树，在经过剪枝之后都能保留最重要的属性划分，因此最终的性能差距不大。