决策树

1.决策树介绍

决策树（Decision Tree，DT）是模式识别中进行分类的一种有效方法，利用树分类器可以把一个复杂的多类别分类问题转化为若干个简单分类问题来解决。它不是企图用一个决策规则把多个类别的样本一次分开，而是采用分级的方法，使分类问题逐步得到解决。总结起来，决策树就是一个将输入空间逐步分割的过程，它把输入空间分为一组互不相交的区域，其中某个类别的样本占有优势的区域标记为该样本的类别。

从结构上看，决策树是一种根据数据的属性采用树状结构建立的一种决策模型，由结点（node）和有向边（directed edge）组成。其中结点有两种结点：内部结点（internal node）和叶子结点（leaf node），每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶子结点代表一种类别。

决策树可用于分类和回归，在分类问题中它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布¹。

相对于线性模型，决策树学习模型可以称为树模型，树模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。树模型拟合出来的函数其实是分区间的阶梯函数。²

$线性模型和树模型的区别

1）一个非常重要的区别是，树形模型是一个一个特征进行处理，而线性模型是所有特征给予权重相加得到一个新的值。决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。²

2）另外线性回归只能找到线性分割（Logistic 回归的输入特征 x 与 logit 之间是线性的，除非对 x 进行多维映射），而决策树可以找到非线性分割。

3）树模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）

下图是一个简单的决策树，表示在不同的天气状况打高尔夫球人数变化情况:

$决策树与 if-then 规则

决策树在分类问题中它可以认为是 if-then 规则的集合。规则是表示信息或少量知识的好方法。基于规则的分类器使用一组 if-then 规则进行分类。

一个 if-then 规则的表达式：IF 条件 THEN 结论，下面是规则 R1 的示例：

决策树由根结点到叶子结点的每一条路径构建一条规则；路径上内部结点的特征对应规则的条件，叶子结点对应规则的结论。决策树的路径或其对应的 if-then 规则集合具有一个重要的性质：互斥且完备。即每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖（实例满足的规则条件）¹。

$决策树构造的主要过程

决策树学习是以实例为基础的归纳学习。采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，实际上就是寻找最纯净的划分方法，到叶子结处的熵值为零，此时每个叶结点中的实例都属于同一类。

一棵决策树的过程主要分为以下 3 个部分:

• 特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前结点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
• 决策树生成： 根据选择的特征评估标准，从上至下递归地生成子结点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。
• 决策树剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

@纯度

决策树思想，实际上就是寻找最纯净的划分方法，“纯净” 一词更专业的说法是纯度（purity），我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的 “纯度” 越来越高。纯度通俗点理解就是目标变量要分得足够开（y=1 的和 y=0 的混到一起就会不纯），使得叶子结点中的训练集尽量的 “纯”。纯度的另一种理解是分类误差率的一种衡量。²信息熵是度量样本集合纯度最常用的一种指标，因为熵是信息混乱程度的度量，那么熵越小，则纯度越高。

2.决策树特征选择

特征选择一般是递归地选择最优特征，并用最优特征对数据集进行分割。最优特征在于选取对选取数据具有分类能力的特征，这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的，经验上扔掉这样的特征对决策树学习的精度影响不大。常见的特征选择标准有信息增益、信息增益率和基尼系数。

2.1.信息增益（Information Gain）

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

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

要点：

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

2）从定义和公式来看，信息增益就是训练数据集 D 和特征 A 的互信息。

3）当熵和条件熵中的概率由数据估计 (特别是极大似然估计) 得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。也可以这样理解：根据给定的已知样本集，计算样本集的香农熵，就是经验熵。以经验熵为基础计算出来的条件熵，就是经验条件熵。

4）ID3 决策树学习算法就是以信息增益为准则来选择划分属性，信息增益准则下，构造的决策树是唯一的。

5）一个属性的信息增益越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。

信息增益的计算方法

设训练数据集为 $D$ ，$|D|$ 表示其容量，即样本个数。设有 $K$个类 $ C_k$，$k=1,2,…,K$，$|C_k|$ 为属 于类 $C_k$ 的样本个数。$\sum_k|C_k|=|D|$。设特征 $A$ 有 $n$ 个不同的取值 $\{a_1,a_2…a_n\}$，根据特征 $A$ 的取 值将 $D$ 划分为 $n$ 个子集 $D_1、D_2、…D_n$，$|D_i|$ 为 $D_i$ 的样本个数，$\sum_i |D_i|=D$。记子集 $ D_i $ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$，$|D_{ik}|$ 为 $D_{ik}$ 的样本个数。

则数据集 D 的经验熵为：

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

特征 A 对数据集 D 的经验条件熵为：

$$\begin{align} H(D|A)=&-\sum_{i,k}p(D_k,A_i)\log p(D_k | A_i) \\&= -\sum_{i,k}p(A_i)p(D_k|A_i)\log p(D_k|A_i) \\&=-\sum_{i=1}^n\sum_{k=1}^Kp(A_i)p(D_k|A_i)\log p(D_k|A_i)\\&=-\sum_{i=1}^np(A_i)\sum_{i=1}^Kp(D_k|A_i)\log p(D_k|A_i)\\&=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log\frac{|D_{ik}|}{|D_i|}\end{align}$$

因此，信息增益为：

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

然后遍历所有特征，将每个特征都算出一个信息增益值，哪个特征算出的信息增益最大，我们就选择这个特征作为当前的分裂特征（分类依据），如果出现某几个特征的信息增益值一样，则随意选一个即可。每个分支点都是如此计算。

分类完成后，已经不能再继续分类的子集是一个确定事件，熵为零，信息增益也可以说是零。

2.2.增益率（Gain Ratio）

使用信息增益作为计算分裂特征的指标会有一个特点，就是在绝大部分情况下，某个特征分支的数目更多的话有可能在选择时会偏向这个特征（比如说有 n 个样本按某个特征直接分出 n 个分支，n 种不同的取值，分支太多，信息增益大，分支结点熵为 0），结果训练出来的形状是一棵庞大且深度很浅的树，分支很多但每个分支结点仅包含非常少的样本数量，这些分支结点的纯度也已达到最大。然而。这样的决策树显然不具有泛化能力，无法对新样本进行有效的预测，因此这样的划分是极为不合理的。

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法不直接使用信息增益，而是使用 “增益率（也称信息增益率）” 来选择最优划分属性。其思路是对这个特征进行一定程度的 “惩罚”，所以用信息增益除以特征 A 的熵，得到信息增益率，特征 A 的熵越大，受到的惩罚也越多，从而保证特征之间的信息增益率可比。其公式为：

$$g_r(D, A)=g(D, A) / H(A)$$

信息增益率与信息增益一样，越大则表明进行划分所获得的 “纯度提升” 越大．最后的样本集合的纯度越高。

2.3.基尼系数（Gini coefficient）

基尼系数是元素被随机选中的一种度量，可以简单理解为不确定程度，跟熵的含义相似（确切的来说，应该是熵之半，详见下一小节的 CART 算法）。

分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 p~k~，则概率分布的基尼系数定义为：

$$Gini(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2$$

对于二分类问题，若样本点属于第一个类的概率是 p，则概率分布的基尼系数为：

$$Gini(p)=2p(1-p)$$

对于给定样本集合 D，C~k~ 是 D 中属于第 k 类的样本子集，其基尼系数为：

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

给定样本集合 D 根据特征 A 是否取得某值被分割成 D~1~、D~2~ 两个部分，在 A 条件下， 集合 D 的基尼系数为（相当于加权平均，形式与条件熵类似）：

$$Gini(D, A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

基尼系数也叫基尼指数（Gini index），Gini 系数，基尼不纯度。CART 决策树学习算法使用基尼系数来选择划分属性。

Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。因此， Gini(D) 越小，则数据集 D 的纯度越高。因此，基尼系数有时会称为基尼不纯度，其值表示数据集的不纯程度，越大越不纯。因此，CART 决策树学习算法选择那个使得划分后基尼指数最小的属性作为最优划分属性。

基尼系数的特质是³： 1）类别个数越少，基尼系数越低;

2）类别个数相同时，类别集中度越高，基尼系数越低。 ​ 当类别越少，类别集中度越高的时候，基尼系数越低；当类别越多，类别集中度越低的时候，基尼系数越高。（类别集中度是指类别的概率差距，0.9+0.1 的概率组合，比起 0.5+0.5 的概率组合集中度更高）

3.决策树生成算法

决策树生成（学习）算法最常见的有三种，三种决策树学习算法最主要区别就是使用不同的属性划分准则，还有一些小的区别，如下所示：

ID3 ：信息增益最大化作为特征选取指标，多叉树，特征必须离散变量。

C4.5 ：信息增益率最大化作为特征选取指标，多叉树，特征也可以是连续变量。

CART： 分类树用基尼系数最小化准则，回归树用平方误差最小化准则，二叉树，可用于分类和回归。

下面我们依次简单介绍三种算法。

3.1.ID3 算法

ID3 由 Ross Quinlan 在 1986 年提出。ID3 决策树可以有多个分支（多叉树），但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在 ID3 中，每次根据 “最大信息熵增益” 选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，也就是说如果一个特征有 4 种取值，数据将被切分 4 份，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用，所以有观点认为这种切分方式过于迅速。ID3 算法十分简单，核心是根据 “最大信息熵增益” 原则选择划分当前数据集的最好特征。在建立决策树的过程中，根据特征属性划分数据，使得原本 “混乱” 的数据的熵 (混乱度) 减少，按照不同特征划分数据熵减少的程度会不一样。在 ID3 中选择熵减少程度最大的特征来划分数据（贪心），也就是 “最大信息熵增益” 原则。

3.2.C4.5 算法

C4.5 是 Ross Quinlan 在 1993 年在 ID3 的基础上改进而提出的。ID3 采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的特征，因为属性值多的特征会有相对较大的信息增益（信息增益反映的给定一个条件以后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是条件熵越小，信息增益越大）。为了避免这个不足，C4.5 中是用信息增益率来作为选择分支的准则。信息增益率通过引入一个被称作分裂信息（Split information）的项（其实就是熵）来惩罚取值较多的特征。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。⁵

除此之外，C4.5 还弥补了 ID3 中不能处理特征属性值连续的问题。对于离散型描述属性，C4.5 的处理方法与 ID3 相同。但是，对连续属性值需要扫描排序，会使 C4.5 性能下降。

具体处理过程如下：

1. 对特征的取值进行升序排序。

2. 两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的信息增益。优化算法就是只计算分类属性发生改变的那些特征取值。

3. 选择修正后信息增益最大的分裂点作为该特征的最佳分裂点

4. 计算最佳分裂点的信息增益率作为特征的选择指标。

   注意，此处需对最佳分裂点的信息增益进行修正：减去 $\frac{\log(N-1)}{|D|}$（N 是连续特征的取值个数，D 是训练数据数目，此修正的原因在于：当离散属性和连续属性并存时，C4.5 算法倾向于选择连续特征做最佳树分裂点）

简单分析一下这样做的思路和经验：

　　基本思路是把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有 N 条样本，那么我们有 N-1 种离散化的方法：$\le v_j$的分到左子树，$\gt v_j$的分到右子树。计算这 N-1 种情况下最大的信息增益率。

另外，对于连续属性先进行排序（升序），只有在决策属性（即分类发生了变化）发生改变的地方才需要切开，这可以显著减少运算量 (Python 语言直接使用 set 即可实现无序去重)。

经证明，在决定连续特征的分界点时采用信息增益这个指标（因为若采用增益率，分裂信息的项影响分裂点信息度量准确性，若某分界点恰好将连续特征分成数目相等的两部分时其抑制作用最大），而选择属性的时候才使用增益率这个指标能选择出最佳分类特征。

3.3.CART 算法

CART（Classification and regression tree）是由 L.Breiman、J.Friedman、R.Olshen 和 C.Stone 于 1984 年提出，是应用很广泛的决策树学习方法。从它的名字 “分类和回归树” 就可以看出来，CART 算法可以做分类，还可以做回归，CART 假设决策树是二叉树，内部结点特征的取值只有 “是” 和 “否”，左分支是取值为 “是” 的分支，右分支则相反。这样的决策树等价于递归地二分每个特征，这些是与其他两种算法最大的不同。

分类树

我们知道，在 ID3 算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在 C4.5 算法中，采用了信息增益率来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是 ID3 还是 C4.5, 都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART 分类树算法使用基尼系数来代替信息增益率，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益 (率) 是相反的。⁴

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在 45 度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而 CART 分类树算法就是使用的基尼系数来选择决策树的特征⁵。

同时，为了进一步简化，CART 分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样 CART 分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

回归树

假设 $\mathbf{X}$和 Y 分别为输入和输出变量，Y 为连续变量，训练数据集 D 为:

$$D=\lbrace (\mathbf{X}^1, y^1), (\mathbf{X}^2, y^2), \ldots, (\mathbf{X}^n, y^n) \rbrace$$

一个回归树对应着输入空间的一个划分以及在划分的单元上的输出值。加入已经将输入空间划分为 M 个单元 $R_1$， $R_2$，$\ldots$，$R_M$，在每个单元 $R_m$上有个固定的输出 $c_m$，则回归树表示为:

$$f(\mathbf{X}) = \sum_{m=1}^M c_m I(\mathbf{X} \in R_m)$$

问题是怎么对输入空间进行划分。一般采用启发式的思路，选择第 j 个特征 $\mathbf{X}_j$和他的取值 s 分别作为切分变量和切分点，并定义两个区域:

$$R_1(j, s) = \lbrace \mathbf{X}|\mathbf{X}_j \leq s \rbrace, \;\;\;\; R_2(j, s) = \lbrace \mathbf{X}|\mathbf{X}_j > s \rbrace $$

然后采用平方误差损失求解最优的切分变量 j 和切分点 s。

$$\displaystyle {min}_{j, s} [ {min}_{c_1} \sum_{\mathbf{X}^i \in R_1(j, s)} (y^i -c_1)^2 + {min}_{c_2} \sum_{\mathbf{X}^i \in R_2(j, s)} (y^i -c_2)^2 ]$$

别看上面的式子很复杂，实际上不难理解，每一个切分变量和切分点对 (j, s) 都将输入空间分成两个区域，然后分别求每个区域的输出值，使得误差最小，很显然输出值应该是那个区域所有样本值的平均值，即:

$$c_1 = \frac {1} {N_1} \sum_{\mathbf{X}^i \in R_1} y^i, \qquad c_2 = \frac {1} {N_2} \sum_{\mathbf{X}^i \in R_2} y^i$$

然后每个 (j, s) 对里找出使总误差最小的对作为最终的切分变量和切分点，对切分后的子区域重复这一步骤。

下面通过一个例子来理解具体步骤，根据下面这个简单的数据集我们来生成一棵回归树⁶。

1）选择最优切分变量 j 与切分点 s。遍历（特征）变量 j，对固定的切分变量 j 扫描切分点 s，选择平方误差损失取得最小值的 (j, s) 对。

这里的 x 只有一个特征，我们不用选择 j，只需考虑且切分点 s 即可。根据所给数据，考虑如下切分点：

$s = \{1.5， 2.5， 3.5，4.5，5.5，6.5，7.5，8.5，9.5\}$。

对各切分点，求出相应的 $R_1$、$R_2$、$c_1$、$c_2$ 以及相应切分点 s 的平方误差损失 $m(s)$。

以 $s=1.5$ 为例，此时可得:

$R_1=\{1\}$，$R_2=\{2, 3, 4, 5, 6, 7, 8, 9, 10\}$，

$c_1 = 5.56$，$c_2=(5.70 + 5.91 + 6.40 + 6.80 + 7.05 + 8.90 + 8.70 + 9.00 + 9.05) / 9 = 7.50$

$$\begin{align}\displaystyle m(s)&={min}_{j, s} [ {min}_{c_1} \sum_{\mathbf{X}^i \in R_1(j, s)} (y^i -c_1)^2 + {min}_{c_2} \sum_{\mathbf{X}^i \in R_2(j, s)} (y^i -c_2)^2 ] \\ &= 0+15.72\\ &=15.72 \end{align}$$

相同的方法，计算出所有的分切点对应的损失值，见下表：

由上表可知，当 $x=6.5$ 的时候达到最小值，此时 $R_1=\{1,2,3,4,5,6\}$，$R_2=\{7,8,9,10\}$，$c_1=6.24$，$c_2=8.9$，所以回归树 $T_1(x)$为:

$$T_1(x) = \begin{cases} 6.24, & x\lt 6.5 \\ 8.91, & x \ge 6.5 \\ \end{cases}$$

$$f_1(x)=T_1(x)$$

用 $f_1(x)$拟合训练数据的残差见下表，表中 $r_{2i} = y_i – f_1(x_i),\;i=1,2,\ldots , 10$。

用 $f_1(x)$拟合训练数据的平方误差：

$$L(y,f_1(x)) = \sum_{i=1}^{10}(y_i-f_1(x_i))^2 = 1.93$$

第 2 步求 $T_2(x)$。方法与求 $T_1(x)$一样，只是拟合的数据是上表的残差，可以得到：

$$T_2(x) = \begin{cases} -0.52, & x\lt 3.5 \\ 0.22, & x \ge 3.5 \\ \end{cases}$$

$$f_2(x) = f_1(x) + T_2(x)= \begin{cases} 5.72, & x\lt 3.5 \\ 6.46, & 3.5\le x \lt 6.5 \\ 9.13, & x\ge 6.5 \\ \end{cases}$$

用 $f_2(x)$拟合训练数据的平方误差是：

$$L(y,f_2(x)) = \sum_{i=1}^{10}(y_i-f_2(x_i))^2 = 0.79$$

继续求得:

$$T_3(x) = \begin{cases} 0.15, & x\lt 6.5 \\ -0.22, & x \ge 6.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.47 ,$$

$$T_4(x) = \begin{cases} -0.16, & x\lt 4.5 \\ 0.11, & x \ge 4.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.30 ,$$

$$T_5(x) = \begin{cases} 0.07, & x\lt 6.5 \\ -0.11, & x \ge 6.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.23 ,$$

$$T_6(x) = \begin{cases} -0.15, & x\lt 2.5 \\ 0.04, & x \ge 2.5 \\ \end{cases}$$

$$f_6(x) = f_5(x)+T_6(x) =T_1(x)+ \ldots + T_5(x) + T_6(x)= \begin{cases} 5.63, & x\lt 2.5 \\ 5.82, & 2.5 \le x\lt 3.5 \\ 6.56, & 3.5 \le x\lt 4.5 \\ 6.83, & 4.5 \le x\lt 6.5 \\ 8.95, & x\ge 6.5 \\ \end{cases}$$

用 $f_6(x)$拟合训练数据的平方损失误差是：

$$L(y,f_6(x)) = \sum_{i=1}^{10}(y_i-f_6(x_i))^2 = 0.71$$

假设此时已经满足误差要求，那么 $f(x) = f_6(x)$即为所求的回归树。

4.决策树剪枝算法

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得 “太好” 了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，泛化能力弱，容易发生过拟合现象是决策树的一个缺点，为了解决这个问题，我们需要对决策树进行剪枝，即类似于线性回归的正则化，来增加决策树的泛化能力。

剪枝分预（前）剪枝和后剪枝，通过主动去掉一些分支来降低过拟合的风险。除了剪枝，使用集成学习思想的随机森林也同样能够有效避免过拟合现象。

$预剪枝和后剪枝的比较

1. 因为后剪枝经过精确计算，一般用后剪枝得到的结果比预剪枝的好，但相比预剪枝增加了计算资源和时间开销；
2. 通常预剪枝生成比后剪枝更简洁的树 ，但也因为预剪枝基于 “贪心” 本质禁止这些分支展开，反而给预剪枝决策树带来了欠拟合的风险；
3. 预剪枝对参数或阈值的设定很敏感，一点点的变动，会引起整棵树非常大的变动，不好设定；
4. 预剪枝是的决策树的很多分支都没有 “展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。

4.1.预剪枝（Pre-Pruning）

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

可通过以下几种方法来实现预剪枝，使决策树不再继续划分：

• 树到达一定深度
• 结点下包含的样本点小于一定数目
• 信息增益小于一定的阈值
• 结点下所有样本都属于同一个类别
• 性能在划分后没有提高或提高不多（保留一份验证集数据使用 “留出法” 评估划分前后性能）

4.2.后剪枝（Post-Pruning）

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。相比于先剪枝，后剪枝的使用更普遍，因为在先剪枝方法中精确地估计何时停止树增长很困难。

后剪枝的剪枝过程是删除一些子树，然后用其叶子结点代替，这个叶子结点所标识的类别通过 “多数类原则（majority class criterion）” 确定。所谓 “多数类原则”，是指剪枝过程中，将一些子树删除而用叶结点代替，这个叶结点所标识的类别用这棵子树中大多数训练样本所属的类别来标识，所标识的类称为 “多数类”。

后剪枝的算法有很多种，下面我们简单介绍几个。

4.2.1.错误率降低剪枝（Reduced-Error Pruning ，REP）

REP 方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。周志华老师在西瓜书中介绍后剪枝用的就是这种方法，可参考书中示例⁷。

这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验⁸。

该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

1. 删除以此结点为根的子树
2. 使其成为叶子结点
3. 赋予该结点关联的训练数据的最常见分类
4. 当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止（有害是指修剪会减低验证集合的精度）。

REP 是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过如果训练集较小，通常不考虑采用 REP 算法。

尽管 REP 有这个缺点，不过 REP 仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用 REP 剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

4.2.2.悲观错误剪枝（Pessimistic Error Pruning，PEP）

PEP 剪枝算法是在 C4.5 决策树算法中提出的，该方法基于训练数据的误差评估，因此比起 REP 剪枝法，它不需要一个单独的测试数据集。但训练数据也带来错分误差偏向于训练集，因此需要加入修正 1/2（惩罚因子，用常数 0.5），是自上而下的修剪。 之所以叫 “悲观”，可能正是因为每个叶子结点都会主观加入一个惩罚因子，“悲观” 地提高误判率。

悲观错误剪枝法是根据剪枝前后的误判率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补 REP 中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。

把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子节点，它覆盖了 N 个样本，其中有 E 个错误，那么该叶子节点的误判率为 $(E+0.5)/N$，这个 0.5 就是惩罚因子。

那么对于一颗拥有 L 个叶子结点的子树，该子树的误判率估计为：

$$e=\sum_{i \in L} \frac{E_i+0.5}{N_i}=\frac{\sum_{i \in L}(E_i+0.5)}{\sum_{i \in L}N_i}=(\sum E+0.5*L)/\sum N$$

这样的话，我们可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。剪枝后内部节点变成了叶子节点，其误判个数 J 也需要加上一个惩罚因子，变成 J+0.5。使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用修正后有误差计算方法却并非如此，当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝，即满足被替换子树的误判数 - 标准差 > 新叶子的误判数，写成公式为：

$$E(\text{sub_err_count})-var(\text{sub_err_count})>E(\text{leaf_err_count})$$

这里出现的标准差如何计算呢？

我们假定一棵子树错误分类一个样本的值为 1，正确分类一个样本的值为 0，该子树错误分类的概率（误判率）为 e，则每分类一个样本都可以近似看作是一次伯努利试验，覆盖 N 个样本的话就是做 N 次独立的伯努利试验，因此，我们可以把子树误判次数近似看成是服从 B(N, e) 的二项分布（二项分布就是重复 N 次独立的伯努利试验）。因此，我们很容易估计出子该树误判次数均值和标准差：

$$\begin{align}&exp(\text{subtree_err_count})=N*e \\&var(\text{subtree_err_count})= \sqrt{N*e*(1-e)}\end{align}$$

当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。

下面是一个简单的例子：

这个例子目的是看看 T4 为根的整个这颗子树是不是可以被剪掉。 树中每个节点有两个数字，左边的代表正确，右边代表错误。比如 T4 这个节点，说明覆盖了训练集的 16 条数据，其中 9 条分类正确，7 条分类错误。 我们先来计算替换标准不等式中，关于子树的部分： ​ 子树有 3 个叶子节点，分别为 T7、T8、T9，因此 L=3； 子树中一共有 16 条数据（根据刚才算法说明把三个叶子相加），所以 N=16； 子树一共有 7 条错误判断，所以 E=7； 那么根据 e 的公式 e = (7 + 0.5 × 3) / 16 = 8.5 /16 = 0.53； 根据二项分布的标准差公式，标准差为 $\sqrt{(16 × 0.53 ×（1-0.53)}$ = 2.00； ​ 子树的错误数为 “所有叶子实际错误数 + 0.5 调整值” = 7 + 0.5 × 3 = 8.5； 而把子树剪枝后，只剩下 T4，T4 的错误数为 7 + 0.5 = 7.5。 这样，8.5 – 2 < 7.5， 因此不满足剪枝标准，不能用 T4 替换整个子树。

4.2.3.代价复杂度剪枝（Cost-Complexity Pruning，CCP）

总体思路

• 通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。
• 由完全树 $T_0$ 开始，剪枝部分结点得到 $T_1$，再次剪枝部分结点得到 $T_2$……，直到仅剩树根的树 $T_n$，形成一个子树序列 $\{T_0， T_1，…，T_n\}$。
• 通过交叉验证法在独立的验证数据集上对子树序列中的子树分别评价，选择损失函数最小的树 $T_\alpha$ 。

损失函数

损失函数可以有多种不同的定义，关键在于选择的评价标准，如可以选择信息熵、信息增益、信息增益率、基尼系数、平方误差、分类预测误差等⁹。

我们介绍两种，第一种是以信息熵作为损失函数，在李航老师的《统计学习方法》中也提到过。

设树 T 的叶结点个数为 $|T|$，$t$是树 $T$的叶结点，该叶结点有 $N_t$个样本点，其中 $k$类的样本点有 $N_{tk}$个，$k=1, 2, …, K$。

• 若 $t$ 结点 $k$ 类样本数目 $N_{tk}= N_t$，而 $N_{t1}, …,N_{t(k-1)},N_{t(k+1)},…,N_{tK}=0$，则称该结点为纯结点，其熵 $H_p = 0$，最小。
• 若各类样本数目 $N_{t1}=N_{t2}=…=N_{tk}=…=N_{tK}=n/K$，则称该结点为均结点，其熵 $H_u=\ln K$，最大。

对所有叶结点的熵求和，该值越小说明对样本的分类越精确。因各结点所含样本数目不同，可使用样本数加权求熵和，如下：

$$C(T) = \sum_{t=1}^{|T|}N_t \cdot H(T) $$

其中经验熵为 $H_t(T) = -\sum_{k}{\frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}}$，

另外一种是将分类预测误差作为评价标准¹⁰，损失函数公式如下：

$C(T)=\sum_{t \in T}r(t) \cdot p(t)=\sum_{t \in T}C(t)$

其中，$\sum_{t \in T}C(t)$ 是所有叶子结点的预测误差总和，$C(t)=r(t) \cdot p(t)$ 是结点 $t$ 的错误代价，$r(t)=1-\max_k p(C_k -t)$ 为结点 $t$ 的错分样本率，$p(t)=n(t)/n$ 为落入结点 $t$ 的样本占所有样本的比例。

剪枝系数

有了损失函数，一般叶结点越多，决策树越复杂，损失越大，为了不让最终的决策树模型太复杂导致过拟合，我们可以像正则化一样在损失函数后面添加一个惩罚项，即：

$$C_{\alpha}(T) = C(T) + \alpha |T|$$

$C(T)$表示模型对训练数据集的预测误差（如基尼系数），即模型与训练数据集的拟合程度。$|T|$表示模型的复杂度，参数 $\alpha \geq 0$，控制两者之间的影响，可称为剪枝系数⁹。

对于固定的 $ \alpha $，一定存在使损失函数 $C_\alpha(T)$最小的子树，将其表示为 $T_\alpha$，$T_\alpha$在损失函数 $C_\alpha(T)$最小的意义下是最优的，容易验证这样的最优子树是唯一的。较大的 $\alpha$促使选择较简单的模型（树），最优子树 $T_\alpha$偏小；而较小的 $\alpha$促使选择较复杂的模型（树），最优子树偏大。极端情况，当 $a＝0$ 时，意味着只考虑模型与训练数据的拟合程度，不考虑模型复杂度，所以整体树是最优的，而当 $a→ \infty$ 时，只包括一个根结点构成的单结点树是最优的¹。

Breiman 等人证明：可以用递归的方法对树进行剪枝。将 $\alpha$ 从小增大，如 $0＝\alpha_0 < \alpha_1 < … < \alpha_n < +\infty $，将产生一系列的区间 $[\alpha_i , \alpha_{i+1} ),\;\;i＝0,1,…,n$；剪枝得到的子树序列对应着区间 $\alpha \in [\alpha_i , \alpha_{i+1}), \;\;i＝0,1,…,n$ 的最优子树序列 $\{T_0 ,T_1 ,…,T_n \}$，序列中的子树是嵌套的，即 $T_0 \supseteq T_2 \supseteq \ … \ \supseteq T_k \supseteq \ … \ \supseteq T_n$。

尽管 $\alpha$ 的取值无限多，但是可能的最优子树是有限的，因此我们可以利用上面得到的结论，即每一个子树与一个 $\alpha$ 有一一对应的关系，来得到最优的子树 $T_\alpha$ 以及对应的剪枝系数 $\alpha$。

具体地，从整体树 $T_0$开始剪枝，对 $T_0$的任意内部结点 $t$，以 $t$为单结点的树（相当于剪枝后），其损失函数是：

$$C_\alpha(t)=C(t)+\alpha$$

以 t 为根节点的子树 $T_t$（相当于剪枝前），其损失函数是

$$C_\alpha(T_t)=C(T_t)+\alpha(T_t)$$

当 $\alpha=0$及 $\alpha$充分小时，有不等式

$$C_\alpha(T_\alpha) \lt C_\alpha(t)$$

当 $\alpha$增大时，在某一 $\alpha$ 有

$$C_\alpha(T_\alpha) = C_\alpha(t)$$

当 $\alpha$再增大时，将会出现 $C_\alpha(T_\alpha)>C_\alpha(t)$，只要 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，$ T_t$ 与 $t$ 有相同的损失函数，而 $t$ 的结点少，因此 $t$ 比 $T_t$ 更可取，可对 $T_t$ 进行剪枝。

为此，对 $T_0$ 中的每一个内部结点 $t$，计算

$$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$$

它表示剪枝后整体损失函数减少的程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$，将得到的子树作为 $T_1$，同时将最小的 $g(t)$设为 $\alpha_1$，$T_1$为区间 $[\alpha_1, \alpha_2)$的最优子树。

如此剪枝下去，直至得到根结点，在这一过程中，不断地增加 $\alpha$的值，产生新的区间，最终得到子树序列 $\{T_0, T_1, …, T_n\}$。之后通过独立的验证数据集测试各子树指定的评价标准（如平方误差或基尼系数），评价较好的决策树被认为是最优的决策树。在子树序列中，每棵子树 $T_1,T_2,…,T_n$都对应于一个参数 $\alpha_1,\alpha_2,…,\alpha_n$，所以，当最优子树 $T_k$确定时，对应的 $\alpha_k$也确定了，即得到最优决策树 $T_\alpha$。

剪枝过程

对于给定的决策树 $T_0$：

• 计算所有内部结点的剪枝系数 $g(t) =\frac{C(t)-C(T_t)}{\vert T_t\vert-1}$；
• 查找最小剪枝系数的结点，剪枝得决策树 $T_k$；
• 重复以上步骤，直到决策树 $T_k$只有一个结点；
• 得到决策树序列 $T_0,T_1,T_2…T_k$；
• 择一合适的评价标准，利用交叉验证法，使用独立验证样本集选择最优子树。

（这里使用的步骤⁹与李航《统计学习》中的步骤在细节处稍有不同，不过基本方法大体一致。）

代价复杂度剪枝算法示例

假设有如下一棵树¹⁰，有 3 个可剪枝内部结点：$t_1 \equiv \text{root}, t_2, t_3$

1）迭代一，设 $\alpha_0 = 0$，计算每一个内部结点 $t$ 的 $C(t)$， $C(T_t)$，$|T_t|$ 以及 $g(t)$

$$\alpha_1 = \min (\{g(t_1),g(t_2),g(t_3)\})=1/8$$，发现 $g(t_2)$和 $g(t_3)$并列最小，此时我们优先选择剪枝较少的结点，因此将 $t_3$剪掉，树成为下图的样子。

2）迭代二，此时剩下结点 $t_1$、$t_2$，$\alpha_1=1/8$，继续计算各自的 $g(t)$。

$\alpha_2=\min(\{g(t_1),g(t_2)\})=1/8$，$g(t_2)$最小，因此剪掉 $t2$，此时的树如下图。

3）迭代三，仅剩结点 $t_1$，继续计算 $g(t)$。

$\alpha_3 = g(t_1)=\frac{8/16-4/16}{2-1}=1/4$

得到整个剪枝系数序列：$\{\alpha_0=0，\alpha_1=1/8，\alpha_2=1/8，\alpha_3=1/4\}$

4）接下来就可以利用独立的验证数据集找出最优子树 $T_\alpha$以及对应的剪枝系数 $\alpha$。

（原文是通过交叉验证法确定 $\alpha$，然后才确定最优子树，通过某个评价标准，直接就可以确定最优子树。>> 原文参考）

4.2.4.后剪枝算法简单对比

5.决策树算法小结

5.1.决策树算法对比

5.2.决策树算法优缺点

决策树的一大优势就是易于解释。它可以毫无压力地处理特征间的交互关系并且是非参数化的，因此你不必担心异常值或者数据是否线性可分（举个例子，决策树能轻松处理好类别 A 在某个特征维度 x 的末端，类别 B 在中间，然后类别 A 又出现在特征维度 x 前端的情况）。它的缺点之一就是不支持在线学习，于是在新样本到来后，决策树需要全部重建。另一个缺点就是容易出现过拟合，通过剪枝算法或者随机森林等集成学习可以有效避免。决策树可以作为集成学习基本分类器，是除线性回归外，在探究过程中会经常使用的算法。

下面我们不再纠结于 ID3, C4.5 和 CART，看看决策树算法作为一个大类别的分类回归算法的优缺点。⁵

决策树算法优点

1. 决策树易于理解和解释，可以可视化分析，容易提取出规则；
2. 基本不需要预处理，不需要提前归一化，处理缺失值；
3. 测试数据集时，运行速度比较快，使用决策树预测的算法复杂度是 O(log n)， n 为样本数；
4. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值；
5. 能够处理不相关的特征；
6. 可以处理多维度输出的分类问题；
7. 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释；
8. 可以交叉验证的剪枝来选择模型，从而提高泛化能力；
9. 对于异常点的容错能力好，健壮性高；
10. 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

决策树算法缺点

1. 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2. 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3. 寻找最优的决策树是一个 NP 难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
4. 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
5. 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
6. 容易忽略数据集中属性的相互关联；
7. 决策树算法无法在线学习
   决策树算法通常被认为是一种批处理（batch learning）算法，而不是在线学习（online learning）算法。不过有些变体的决策树学习算法可进行 “增量学习”（incremental learning），即在接收到新样本后可对己学得的模型进行调整，而不用完全重新学习。主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构，代表性算法有 ID4 [Schlimmer and Fisher, 1986 ］、 ID5R [Utgoff, 1989a ］、 ITI [Utgoff et al., 1997 ］ 等。增量学习可有效地降低每次接收到新样本后的训练时间开销，但多步增量学习后的模型会与基于全部数据训练而得的模型有较大差别。⁷

改进措施

• 对决策树进行剪枝。可以采用交叉验证法和加入正则化的方法;
• 使用基于决策树的集成学习算法，如 bagging 算法，randomforest 算法，可以解决过拟合的问题；

5.3.应用场景

• 由于决策树很好的分析能力，在特征分析和筛选中应用较多；
• 作为基础分类器，用于集成学习；
• 银行欺诈风险预测、企业投资决策等。

6.参考资料