经典决策树算法（ID3、C4.5、CART）原理以及Python实现

1 决策树简介

 决策树(Decision Tree)，是每个分支都通过条件判断进行划分的树，是解决分类和回归问题的一种机器学习算法，其核心是一个贪心算法，它采用自顶向下的递归方法构建决策树。

1.1 决策树模型

 决策树模型是一种对实例进行分类的树，由节点（node，由圆框表示）和有向边（directed edge，由方框表示）组成，其中节点分为内部节点（internal node）和叶子节点（leaf node）,内部节点表示一个属性或特征，叶子节点表示一个类。

 决策树可以被看作是一个if-then规则的集合：由决策树的根节点到叶子节点的每一条路径构建一条规则，路径上内部节点的特征对应规则的条件，而叶子结点的分类则对应规则的结论。这一个集合是互斥且完备的，也就是说每一个实例都被且只被一条规则所覆盖。

 决策树还表示给定特征条件下类的条件概率分布：这个条件概率分布被定义在特征空间的一个划分（partition）上。将特征空间划分为互不相交的单元（cell），并在每一个单元定义一个类的概率分布就构成一个条件概率分布。决策树的每一条路径对应一个划分单元，也就是一个条件概率分布。叶子节点（单元）上的条件概率往往偏向于某一个类，分类时将该节点的实例强行分到条件概率大的一类上去。

1.2 决策树学习

 假设给定训练数据集

D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . ( x N , y N ) } D = \left \{ \left ( x_1,y_1 \right ), \left ( x_2,y_2 \right ), ...\left ( x_N,y_N \right ) \right \} D={(x1​,y1​),(x2​,y2​),...(xN​,yN​)}

 其中 $x_i={\left(x_i^{(1)},x_i^{(2)},...,x_i^{(n)}\right)}^T$为输入实例（特征向量），$n$为特征个数， y i = { 1 , 2 , . . . , K } y_i=\left \{ 1,2,...,K \right \} yi​={1,2,...,K}为类标记，$i=1,2,...,N$，N为样本容量。

 决策树学习是根据训练数据集构建一个决策树模型，能够对实例进行正确的分类。本质上是从训练数据集中归纳出一组分类规则，也可以看做是由训练数据集估计条件概率模型。决策树学习的策略是以损失函数为目标函数的最小化，现实中采用启发式方法来近似求解，得到的是次最优（sub-optimal）的决策树。决策树学习的算法通常是递归地选择最优特征，并根据最优特征对训练数据进行划分，使得对各个子数据集有一个最好的分类的过程。为了缓解过拟合现象，对于生成的决策树还必须进行自下而上的剪枝，使之泛化能力更加强。

 总得来说，决策树算法包含特征选址、决策树的生成、决策树的剪枝过程。深浅不同的决策树对应不同复杂度的概率模型。决策树的生成只考虑局部最优，决策树的剪枝考虑全局最优。

 常用的决策树算法有ID3算法、改进的C4.5算法和CART算法。

2 特征选择

 不同特征决定不同的决策树。特征选择就是选取对训练数据集具有分类能力的特征，也就是决定用哪一个特征来划分特征空间，这样可以提高决策树的学习效率。通常特征选择的准则有信息增益、信息增益比、基尼指数、平方误差等等。

2.1 信息熵（entropy）和条件熵（conditional entropy）

 信息论中的 熵（entropy） 是表示随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。假设$X$是一个取有限个值的离散随机变量，其概率分布为

$$P\left(X=x_i\right)=p_i,i=1,2,...,n$$

 则$X$的熵定义为

$$E\left(X\right)=-\sum _{i=1}^n{p}_i{\log }_2{p}_i,0\le E\left(X\right)\le {\log }_{2}n$$

 以上公式，熵的单位为比特（bit）。由熵的定义可知，熵值大小只跟$X$的分布有关，跟$X$的取值无关，熵也可以表示为

$$E\left(p\right)=-\sum _{i=1}^n{p}_i{\log }_2{p}_i$$

 特殊地，当$X$随机变量只取两个值，如0或1，$X$的分布为 伯努利分布，即

$$E\left(X=1\right)=p$$

$$E\left(X=0\right)=1-p$$

$$0\le p\le 1$$

 此时$X$的熵为

$$E\left(p\right)=-p{\log }_{2}p-\left(1-p\right){\log }_2\left(1-p\right)$$

 条件熵（conditional entropy） ：随机变量$X$给定条件下$Y$的条件熵 $H(Y|X)$ 定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望

$$E\left(Y|X\right)=\sum _{i=1}^n{p}_{i}E\left(Y|X=x_i\right)$$

 其中 $p_i=P\left(X=x_i\right),i=1,2,...,n$

 特别需要注意，当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵称为经验熵，条件熵称为经验条件熵。

• 示例：对表1所给的数据集$D$，计算经验熵和经验条件熵：

 计算经验熵

$$E(D)=-\frac{9}{15}lo{g}_2\frac{9}{15}-\frac{6}{15}lo{g}_2\frac{6}{15}=0.971$$

 计算经验条件熵，$A_1,A_2,A_3,A_4$分别代表年龄、有工作、有自己的房子、信贷4个特征，$1,2,3$代表$A_1$取值为青年、中年、老年，则其对应取值的经验熵为

$$E(D,A_1=1)=-\frac{2}{5}{\log }_2\frac{2}{5}-\frac{3}{5}{\log }_2\frac{3}{5}=0.971$$

$$E(D,A_1=2)=-\frac{3}{5}{\log }_2\frac{3}{5}-\frac{2}{5}{\log }_2\frac{2}{5}=0.971$$

$$E(D,A_1=3)=-\frac{4}{5}{\log }_2\frac{4}{5}-\frac{1}{5}{\log }_2\frac{1}{5}=0.723$$

 则特征$A_1$对训练数据集$D$的经验条件熵为

$$E(D|A_1)=\frac{5}{15}E(D,A_1=1)+\frac{5}{15}E(D,A_1=2)+\frac{5}{15}E(D,A_1=3)=0.888$$

 同理

$$E(D|A_2)=0.647$$

$$E(D|A_3)=0.550$$

$$E(D|A_4)=0.608$$

2.2 信息增益（infomation gain）

 信息增益（infomation gain） 定义：某特征$A$对训练数据集$D$的信息增益为集合$D$的经验熵与$A$给定条件下$D$的经验条件熵之差

$$Gain(D,A)=E(D)-E(D|A)$$

 一般地，熵与条件熵之差称为 互信息（mutual information）。

 设训练数据集$D$，它包含$K$个类$C_k$，这里$k=1,2,...,K$；特征$A$有$n$个不同取值，根据它可以将$D$划分为$n$个子集$D_i$，这里$i=1,2,...,n$；记子集$D_i$属于类$C_k$的子集为$D_{ik}$。信息增益算法的流程为：

 输入：训练数据集$D$和特征$A$

 输出：特征$A$对训练数据集$D$的信息增益$Gain(D,A)$

 （1）计算训练数据集$D$的经验熵

$$E(D)=-\sum _{k=1}^K\frac{\left|C_k\right|}{\left|D\right|}{\log }_2\frac{\left|C_k\right|}{\left|D\right|}$$

 （2）计算特征$A$对训练数据集$D$的经验条件熵

$$E(D|A)=\sum _{i=1}^n\frac{\left|D_i\right|}{\left|D\right|}H\left(D_i\right)=-\sum _{i=1}^n\frac{\left|D_i\right|}{\left|D\right|}\sum _{k=1}^K\frac{\left|D_{ik}\right|}{\left|D_i\right|}{\log }_2\frac{\left|D_{ik}\right|}{\left|D_i\right|}$$

 （3）特征$A$对训练数据集$D$的信息增益

$$Gain(D,A)=E(D)-E(D|A)$$

 示例：对表1所给的数据集$D$，根据信息增益来选择最优特征$A^{\ast }$。

• 特征$A_1$对训练数据集$D$的信息增益

$$Gain(D,A_1)=E(D)-E(D|A_1)=0.971-0.888=0.083$$

 同理

$$Gain(D,A_2)=E(D)-E(D|A_2)=0.324$$

$$Gain(D,A_3)=E(D)-E(D|A_3)=0.420$$

$$Gain(D,A_4)=E(D)-E(D|A_4)=0.363$$

 由于特征$A_3$（有自己的房子）的信息增益最大，所以选择该特征作为最优的划分特征，即$A^{\ast }=A_3$。

2.3 信息增益比（information gain ratio）

 训练数据集$D$关于特征$A$的 分裂信息（split information） 或叫做特征$A$的 固有值（intrinsic value） 用于衡量特征分裂数据的广度和均匀性

$$IV(D,A)=-\sum _{i=1}^n\frac{\left|D_i\right|}{\left|D\right|}{\log }_2\frac{\left|D_i\right|}{\left|D\right|}$$

 其中$n$为特征$A$的取值个数。

 以信息增益作为准则选择训练数据集的特征时，存在偏向于选择取值较多的特征的问题，矫正的方法是改用 信息增益比（information gain ratio） ，其定义为：某特征$A$对训练数据集$D$的信息增益比 $GainRatio(D,A)$为其信息增益与训练数据集$D$关于特征$A$的分裂信息之比

$$GainRatio(D,A)=\frac{Gain(D,A)}{IV(D,A)}$$

• 示例：对表1所给的数据集$D$，根据信息增益比来选择最优特征$A^{\ast }$。

 计算数据集$D$分别关于$A_1,A_2,A_3,A_4$的分裂信息

$$IV(D,A_1)=-\frac{5}{15}{\log }_2\frac{5}{15}-\frac{5}{15}{\log }_2\frac{5}{15}-\frac{5}{15}{\log }_2\frac{5}{15}=1.585$$

$$IV(D,A_2)=-\frac{5}{15}{\log }_2\frac{5}{15}-\frac{10}{15}{\log }_2\frac{10}{15}=0.918$$

$$IV(D,A_3)=-\frac{6}{15}{\log }_2\frac{6}{15}-\frac{9}{15}{\log }_2\frac{9}{15}=0.971$$

$$IV(D,A_4)=-\frac{5}{15}{\log }_2\frac{5}{15}-\frac{6}{15}{\log }_2\frac{6}{15}-\frac{4}{15}{\log }_2\frac{4}{15}=1.566$$

 计算信息增益比

$$GainRatio(D,A_1)=\frac{Gain(D,A_1)}{IV(D,A_1)}=\frac{0.083}{1.585}=0.052$$

$$GainRatio(D,A_2)=\frac{Gain(D,A_2)}{IV(D,A_2)}=\frac{0.324}{0.918}=0.353$$

$$GainRatio(D,A_3)=\frac{Gain(D,A_3)}{IV(D,A_3)}=\frac{0.420}{0.971}=0.433$$

$$GainRatio(D,A_4)=\frac{Gain(D,A_4)}{IV(D,A_4)}=\frac{0.363}{1.566}=0.232$$

 由于特征$A_3$（有自己的房子）的信息增益率最大，所以依然选择该特征作为最优的划分特征，即$A^{\ast }=A_3$。

 注意：由于信息增益比偏向于可取值数量较少的特征，所以C4.5算法并不是直接使用信息增益率，而是采用一个启发式：先从候选特征中找出信息增益高于平均水平的特征，然后再从中选择信息增益比最高的特征。

2.4 基尼指数（Gini index）

 一个随机变量的不确定性，除了使用上述的 熵来度量，也可以使用 基尼指数（Gini index） 来度量，它一般用作CART分类决策树的特征选择准则。

 在分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为

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

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

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

 对于给定的样本集合 $D$，其基尼指数为

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

 其中，$C_k$ 是 $D$ 中属于第 $k$ 类的样本子集，$K$ 是类的个数。

 如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D1$ 和 $D2$ 两部分，即

D 1 = { ( x , y ) ∈ D ∣ A ( x ) = a } , D 2 = D − D 1 D_1 = \left \{ (x, y)\in D | A(x) = a \right \}, \quad D_2 = D - D_1 D1​={(x,y)∈D∣A(x)=a},D2​=D−D1​

 则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为

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

 基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

 二类分类问题中基尼指数 $Gini(p)$、熵（单位比特）之半 $H(p)/2$ 和分类误差
率的关系可以用下图表示。横坐标表示概率 p，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率

• 示例：对表1所给的数据集$D$，根据基尼系数来选择最优特征$A^{\ast }$。

 求特征 $A_1$ 的基尼指数:

$$Gini(D,A_1=1)=\frac{5}{15}[2\times \frac{2}{5}\times (1-\frac{2}{5})]+\frac{10}{15}[2\times \frac{7}{10}\times (1-\frac{7}{10})]=0.44$$

$$Gini(D,A_2=2)=\frac{5}{15}[2\times \frac{3}{5}\times (1-\frac{3}{5})]+\frac{10}{15}[2\times \frac{6}{10}\times (1-\frac{6}{10})]=0.48$$

$$Gini(D,A_3=3)=\frac{5}{15}[2\times \frac{4}{5}\times (1-\frac{4}{5})]+\frac{10}{15}[2\times \frac{5}{10}\times (1-\frac{5}{10})]=0.44$$

 由于 $Gini(D,A_1=1)$和 $Gini(D,A_1=3)$ 相等，且最小，所以 $A_1=1$ 和 $A_1=3$ 都可以选作 $A_1$ 的最优切分点。

 求特征 $A_2$ 和 $A_3$ 的基尼指数：

$$Gini(D,A_2=1)=\frac{10}{15}[2\times \frac{4}{10}\times (1-\frac{4}{10})]=0.32$$

$$Gini(D,A_3=1)=\frac{9}{15}[2\times \frac{3}{9}\times (1-\frac{3}{9})]=0.27$$

 由于 $A_2$ 和 $A_3$ 只有一个切分点，所以它们就是最优切分点。

 求特征 $A_4$ 的基尼指数：

$$Gini(D,A_4=1)=\frac{11}{15}[2\times \frac{5}{11}\times (1-\frac{5}{11})]=0.36$$

$$Gini(D,A_4=2)=\frac{6}{15}[2\times \frac{4}{6}\times (1-\frac{4}{6})]+\frac{9}{15}[2\times \frac{5}{9}\times (1-\frac{5}{9})]=0.47$$

$$Gini(D,A_4=3)=\frac{5}{15}[2\times \frac{1}{5}\times (1-\frac{1}{5})]+\frac{10}{15}[2\times \frac{8}{10}\times (1-\frac{8}{10})]=0.32$$

 $Gini(D,A_4=3)$ 最小，所以 $A_4=3$ 为 A4 的最优切分点。

 在 $A_1，A_2，A_3，A_4$ 几个特征中，$Gini(D,A_3=1)=0.27$ 最小，所以选择特征 $A_3$为最优特征，$A_3=1$ 为其最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结点继续使用以上方法在 $A_1，A_2，A_4$ 中选择最优特征及其最优切分点，结果是 $A_2=1$。依此计算得知，所得结点都是叶结点。

3 决策树的生成

3.1 ID3算法

 ID3算法的核心是在决策树的各个节点上，以信息增益为准测来选择最优特征，递归地构建决策树，其算法流程如下：

 对表1所给的数据集$D$，使用ID3算法生成的决策树如下：

 ID3算法的优缺点：

优点：

（1）ID3算法算法结构简单，清晰易懂；
（2）非常灵活方便；
（3）不存在无解的危险；
（4）可以利用全部训练例的统计性质进行决策，从而抵抗噪音。

缺点：

（1）ID3算法采用信息增益来选择最优划分特征，信息增益倾向与取值较多的特征，往往容易导致结果误差；
（2）没有考虑连续值，对与连续值的特征无法进行划分；
（3）无法处理有缺失值的数据；
（4）没有考虑过拟合的问题，而在决策树中，过拟合是很容易发生的；
（5）采用贪心算法，每次划分都是考虑局部最优化，而局部最优化并不是全局最优化，当然这一缺点也是决策树的缺点，获得最优决策树本身就是一个NP难题，所以只能采用局部最优。

 使用Python实现ID3算法代码：

class TreeNode:def __init__(self, parent, children, feature, category, X_data, Y_data):self.parent = parentself.children = childrenself.feature = featureself.category = categoryself.X_data = X_dataself.Y_data = Y_datadef get_parent(self):return self.parentdef get_children(self):return self.children

import numpy as np
import pandas as pdfrom treeNode import TreeNodeclass DecisionTree:def __init__(self, X, Y):self.X_train = Xself.Y_train = Yself.root_node = TreeNode(None, None, None, None, self.X_train, self.Y_train)self.features = self.get_features(self.X_train)self.tree_generate(self.root_node)def get_features(self, X_train_data):"""计算各个特征的每个取值的频次"""features = dict()for i in range(len(X_train_data.columns)):feature = X_train_data.columns[i]features[feature] = list(X_train_data[feature].value_counts().keys())return featuresdef tree_generate(self, tree_node):"""生成决策树"""X_data = tree_node.X_dataY_data = tree_node.Y_data# get all features of the data setfeatures = list(X_data.columns)# 如果Y_data中的实例属于同一类，则置为单结点，并将该类作为该结点的类if len(list(Y_data.value_counts())) == 1:tree_node.category = Y_data.iloc[0]tree_node.children = Nonereturn# 如果特征集为空，则置为单结点，并将Y_data中最大的类作为该结点的类elif len(features) == 0:tree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturn# 否则，计算各特征的信息增益，选择信息增益最大的特征else:ent_d = self.compute_entropy(Y_data)XY_data = pd.concat([X_data, Y_data], axis=1)d_nums = XY_data.shape[0]max_gain_ratio = 0feature = Nonefor i in range(len(features)):v = self.features.get(features[i])Ga = ent_dfor j in v:dv = XY_data[XY_data[features[i]] == j]dv_nums = dv.shape[0]ent_dv = self.compute_entropy(dv[dv.columns[-1]])Ga -= dv_nums/d_nums*ent_dvif Ga > max_gain_ratio:max_gain_ratio = Gafeature = features[i]# 信息增益低于阈值0if feature is None:tree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturntree_node.feature = feature# get all kinds of values of the current partition featurebranches = self.features.get(feature)# branches = list(XY_data[feature].value_counts().keys())tree_node.children = dict()for i in range(len(branches)):X_data = XY_data[XY_data[feature] == branches[i]]if len(X_data) == 0:category = XY_data[XY_data.columns[-1]].value_counts(ascending=False).keys()[0]childNode = TreeNode(tree_node, None, None, category, None, None)tree_node.children[branches[i]] = childNode# return# error, not should return, but continuecontinueY_data = X_data[X_data.columns[-1]]X_data.drop(X_data.columns[-1], axis=1, inplace=True)X_data.drop(feature, axis=1, inplace=True)childNode = TreeNode(tree_node, None, None, None, X_data, Y_data)tree_node.children[branches[i]] = childNode# print("feature: " + str(tree_node.feature) + " branch: " + str(branches[i]) + "\n")self.tree_generate(childNode)returndef compute_entropy(self, Y):"""计算信息熵"""ent = 0for cate in Y.value_counts(1):ent -= cate*np.log2(cate)return ent

3.2 C4.5算法

 C4.5算法在ID3算法基础上进行了以下几点改进：

• 用信息增益比来选择特征，克服了ID3算法选择特征时偏向选择取值多的特征的不足。
• 在决策树的构造过程中进行剪枝，不考虑某些具有很好元素的节点。
• 能够完成对连续型特征的离散化处理。
• 能够对不完整数据进行处理。

 C4.5算法流程如下：

 使用Python实现C4.5算法代码

import numpy as np
import pandas as pdfrom treeNode import TreeNodeclass DecisionTreeC45:def __init__(self, X, Y):self.X_train = Xself.Y_train = Yself.root_node = TreeNode(None, None, None, None, self.X_train, self.Y_train)self.features = self.get_features(self.X_train)self.tree_generate(self.root_node)def get_features(self, X_train_data):"""计算各个特征的每个取值的频次"""features = dict()for i in range(len(X_train_data.columns)):feature = X_train_data.columns[i]features[feature] = list(X_train_data[feature].value_counts().keys())return featuresdef tree_generate(self, tree_node):"""生成决策树"""X_data = tree_node.X_dataY_data = tree_node.Y_data# get all features of the data setfeatures = list(X_data.columns)# 如果Y_data中的实例属于同一类，则置为单结点，并将该类作为该结点的类if len(list(Y_data.value_counts())) == 1:tree_node.category = Y_data.iloc[0]tree_node.children = Nonereturn# 如果特征集为空，则置为单结点，并将Y_data中最大的类作为该结点的类elif len(features) == 0:tree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturn# 否则，计算各特征的信息增益比，选择信息增益比最大的特征else:ent_d = self.compute_entropy(Y_data)XY_data = pd.concat([X_data, Y_data], axis=1)d_nums = XY_data.shape[0]max_gain_ratio = 0feature = Nonefor i in range(len(features)):v = self.features.get(features[i])Ga = ent_dIV = 0for j in v:dv = XY_data[XY_data[features[i]] == j]dv_nums = dv.shape[0]ent_dv = self.compute_entropy(dv[dv.columns[-1]])if dv_nums == 0 or d_nums == 0:continueGa -= dv_nums / d_nums * ent_dv # 信息增益IV -= dv_nums/d_nums*np.log2(dv_nums/d_nums) # 分离信息if IV != 0.0 and (Ga/IV) > max_gain_ratio:max_gain_ratio = Ga/IV # 信息增益比feature = features[i]# 如果当前特征的信息增益比小于阈值epsilon，则置为单结点，并将Y_data中最大的类作为该结点的类if max_gain_ratio < 0:tree_node.feature = Nonetree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturnif feature is None:tree_node.feature = Nonetree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturntree_node.feature = feature# 否则，对当前特征的每一个可能取值，将Y_data分成子集，并将对应子集最大的类作为标记，构建子结点# get all kinds of values of the current partition featurebranches = self.features.get(feature)# branches = list(XY_data[feature].value_counts().keys())tree_node.children = dict()for i in range(len(branches)):X_data = XY_data[XY_data[feature] == branches[i]]if len(X_data) == 0:category = XY_data[XY_data.columns[-1]].value_counts(ascending=False).keys()[0]childNode = TreeNode(tree_node, None, None, category, None, None)tree_node.children[branches[i]] = childNode# return# error, not should return, but continuecontinueY_data = X_data[X_data.columns[-1]]X_data.drop(X_data.columns[-1], axis=1, inplace=True)X_data.drop(feature, axis=1, inplace=True)childNode = TreeNode(tree_node, None, None, None, X_data, Y_data)tree_node.children[branches[i]] = childNode# print("feature: " + str(tree_node.feature) + " branch: " + str(branches[i]) + "\n")self.tree_generate(childNode)returndef compute_entropy(self, Y):"""计算信息熵"""ent = 0for cate in Y.value_counts(1):ent -= cate*np.log2(cate)return ent

3.3 CART算法

 分类树与回归树（classification and regression tree，CART）模型是应用广泛的决策树模型，它同样是由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

 CART 算法是在给定输入随机变量 $X$ 条件下输出随机变量 $Y$ 的条件概率分布的学习方法。它假设决策树是 二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

 综合来说，CART算法由以下两步组成：

• （1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
• （2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

3.3.1 分类树的生成

 CART分类树用 基尼指数 最小化准则来选择最优特征，同时决定该特征的最优二值切分点。以下是分类树的生成流程：

 使用Python实现CART分类树算法代码

import pandas as pd
import numpy as npfrom treeNode import TreeNodeclass DecisionTreeCART:def __init__(self, X, Y):self.X_train = Xself.Y_train = Yself.root_node = TreeNode(None, None, None, None, self.X_train, self.Y_train)self.features = self.get_features(self.X_train)self.tree_generate(self.root_node)def get_features(self, X_train_data):features = dict()for i in range(len(X_train_data.columns)):feature = X_train_data.columns[i]features[feature] = list(X_train_data[feature].value_counts().keys())return featuresdef tree_generate(self, tree_node):X_data = tree_node.X_dataY_data = tree_node.Y_data# get all features of the data setfeatures = list(X_data.columns)# 如果Y_data中的实例属于同一类，则置为单结点，并将该类作为该结点的类if len(list(Y_data.value_counts())) == 1:tree_node.category = Y_data.iloc[0]tree_node.children = Nonereturn# 如果特征集为空，则置为单结点，并将Y_data中最大的类作为该结点的类elif len(features) == 0:tree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturn# 否则，计算各特征的基尼指数，选择基尼指数最小的特征else:# gini_d = self.compute_gini(Y_data)XY_data = pd.concat([X_data, Y_data], axis=1)d_nums = XY_data.shape[0]min_gini_index = 1feature = Nonefeature_value = Nonefor i in range(len(features)):# 当前特征有哪些取值# v = self.features.get(features[i])v = XY_data[features[i]].value_counts().keys()# 当前特征的取值只有一种if len(v) <= 1:continue# 当前特征的每一个取值分为是和不是两类for j in v:Gini_index = 0dv = XY_data[XY_data[features[i]] == j]dv_nums = dv.shape[0]dv_not = XY_data[XY_data[features[i]] != j]dv_not_nums = dv_not.shape[0]gini_dv = self.compute_gini(dv[dv.columns[-1]])gini_dv_not = self.compute_gini(dv_not[dv_not.columns[-1]])if d_nums == 0:continueGini_index += dv_nums / d_nums * gini_dv + dv_not_nums / d_nums * gini_dv_notif Gini_index < min_gini_index:min_gini_index = Gini_indexfeature = features[i]feature_value = jif feature is None:tree_node.category = Y_data.value_counts(ascending=False).keys()[0]tree_node.children = Nonereturntree_node.feature = feature# 否则，对当前特征的最小基尼指数取值，将Y_data分成两类子集，构建子结点# get all kinds of values of the current partition feature# branches = list({feature_value, "!"+str(feature_value)})# branches = list(XY_data[feature].value_counts().keys())tree_node.children = dict()for i in range(2):# 左分支，左分支为是的分支if i == 0:X_data = XY_data[XY_data[feature] == feature_value]X_data.drop(feature, axis=1, inplace=True)child_name = feature_value# 右分支，右分支为否的分支else:X_data = XY_data[XY_data[feature] != feature_value]child_name = "!" + str(feature_value)# 可能出现节点没有数据的情况吗？# if len(X_data) == 0:#     print("I'm a bug")#     category = XY_data[XY_data.columns[-1]].value_counts(ascending=False).keys()[0]#     childNode = TreeNode(tree_node, None, None, category, None, None)#     tree_node.children[child_name] = childNode#     # return#     # error, not should return, but continue#     continueY_data = X_data[X_data.columns[-1]]X_data.drop(X_data.columns[-1], axis=1, inplace=True)# X_data.drop(feature, axis=1, inplace=True)childNode = TreeNode(tree_node, None, None, None, X_data, Y_data)tree_node.children[child_name] = childNode# print("feature: " + str(tree_node.feature) + " branch: " + str(branches[i]) + "\n")self.tree_generate(childNode)returndef compute_gini(self, Y):gini = 1for cate in Y.value_counts(1):gini -= cate*catereturn gini

3.3.2 回归树的生成

 CART回归树用 平方误差 最小化准则来进行特征选择，生成的回归树称为 最小二乘回归树。

 假设 $X$ 和 $Y$ 是输入变量和输出变量，并且 $Y$ 是连续的，给定训练数据集

$$D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$

 如果我们生成一棵回归树，将以上输入空间划分为 $M$ 个单元 $R_1,R_2,...,R_M$，并且每一个单元 $R_m$ 上都有一个输出值 $c_m$，则该回归树模型就可以表示为

$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$

 其中 $I$ 为指示函数。当划分空间确定后，回归树对训练数据集的预测误差可以使用平方误差，即

$$MSE=\sum _{x_i\in R_m}(y_i-f(x_i){)}^2$$

 不难推导，$c_m$ 的最优值 ${\hat{c}}_m$ 就是 $R_m$ 上所有输入实例 $x_i$ 的输出值 $y_i$ 的均值，即

$${\hat{c}}_m=ave(y_i|x_i\in R_m)$$

 那么如何对输入空间进行划分好呢？采用启发式的方法，首先，选择第 $j$ 个变量 $x^j$ 以及它的取值 $s$ 作为切分变量（splitting variable）和 切分点（splitting point），并定义两个区域

R ( j , s ) = { x ∣ x j ≤ s } , R ( j , s ) = { x ∣ x j ＞ s } R(j, s) = \{ x|x^j ≤ s \}, \quad R(j, s) = \{ x|x^j ＞ s \} R(j,s)={x∣xj≤s},R(j,s)={x∣xj＞s}

 然后，寻找最优的切分变量 $j$ 和切分点 $s$。具体就是求解

$$\underset{(j,s)}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$

 对于固定的变量 $j$ 就可以求出最优切分点 $s$。

$${\hat{c}}_1=ave(y_i|x_i\in R_1(j,s)),{\hat{c}}_2=ave(y_i|x_i\in R_2(j,s))$$

 遍历所有的输入变量，找到最优的切分变量 $j$，构成一对 $(j,s)$。依此就可以把输入空间分成两个区域。递归地对每个区域重复以上过程，直到满足设定的停止条件为止，就生成了一棵回归树。

 以下是最小二乘回归树的生成算法流程：

 示例：如下图所示的训练数据，试用平方误差损失准则生成一个二叉回归树。

 （1）先取 $s=1$，那么以上训练数据集就被划分为两个区域： R 1 = { 1 } R_1 = \{ 1 \} R1​={1}， R 2 = { 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } \quad R_2=\{ 2,3,4,5,6,7,8,9,10 \} R2​={2,3,4,5,6,7,8,9,10}，它们的输出值为：

$$c_1=4.50$$

$$c_2=\frac{1}{9}(4.75+4.91+5.34+5.80+7.05+7.90+8.23+8.70+9.00)=6.85$$

 依此取s为不同的值，按照上面的计算方法，可以得到下面的表：

 （2）把 $c_1,c_2$ 的值代入到平方误差公式中，如

$$m(s=1)=(4.50-4.50{)}^2+(4.75-6.85{)}^2+(4.91-6.85{)}^2+(5.34-6.85{)}^2+(5.80-6.85{)}^2+(7.05-6.85{)}^2+(7.90-6.85{)}^2+(8.23-6.85{)}^2+(8.70-6.85{)}^2+(9.00-6.85{)}^2=22.6$$

 然后可以得到下表：

 显然，当 $s=5$ 时，$m(s)$ 最小。因此，最佳切分变量和切分点为 $(j=x_i,s=5)$。

 （3）用选定的 $(j=x_i,s=5)$ 划分数据空间，得到

$$R_1=1,2,3,4,5$$

$$R_2=6,7,8,9,10$$

 以上 $R_1,R_2$ 两个子区域的输出值分别为 $c_1=5.06,c_2=8.18$。

 （4）对以上 $R_1,R_2$ 两个子区域，重复调用算法流程中的步骤（1）、步骤（2）。比如对 $R_1$ 继续进行划分

$x_i$	1	2	3	4	5
$y_i$	4.50	4.75	4.91	5.34	5.80

 同样将 $s$ 取不同的值，得到不同的输出 $c$ 如下表：

$s$	1	2	3	4	5
$c_1$	4.50	4.63	4.72	4.88	5.06
$c_1$	5.20	5.35	5.57	5.80	0.00

 计算出对应的平方误差：

$s$	1	2	3	4	5
$m(s)$	0.67	0.43	0.19	0.37	1.06

 显然，s=3时，m(s)最小。

 之后按照以上同样的递归流程，最终得到以下的回归树：

 使用python来实现最小二乘回归树代码：

from numpy import *# 载入数据
def loadDataSet(fileName):dataMat = []fr = open(fileName)for line in fr.readlines():curLine = line.strip().split('\t')# python3不适用：fltLine = map(float,curLine) 修改为：fltLine = list(map(float, curLine))  # 将每行映射成浮点数，python3返回值改变，所以需要dataMat.append(fltLine)return dataMat# 切分数据集为两个子集
def binSplitDataSet(dataSet, feature, value):  # 数据集 待切分特征 特征值mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :]mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :]# 下面原书代码报错 index 0 is out of bounds,使用上面两行代码# mat0 = dataSet[nonzero(dataSet[:, feature] > value)[0], :][0]# mat1 = dataSet[nonzero(dataSet[:, feature] <= value)[0], :][0]return mat0, mat1# Tree结点类型：回归树
def regLeaf(dataSet):  # 生成叶结点，在回归树中是目标变量特征的均值return mean(dataSet[:, -1])# 误差计算函数：回归误差
def regErr(dataSet):  # 计算目标的平方误差（均方误差*总样本数）return var(dataSet[:, -1]) * shape(dataSet)[0]# 二元切分
def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(0, 1)):# 切分特征的参数阈值，用户初始设置好tolS = ops[0]  # 允许的误差下降值tolN = ops[1]  # 切分的最小样本数# 若所有特征值都相同，停止切分if len(set(dataSet[:, -1].T.tolist()[0])) == 1:  # 倒数第一列转化成list 不重复return None, leafType(dataSet)  # 如果剩余特征数为1，停止切分1。# 找不到好的切分特征，调用regLeaf直接生成叶结点m, n = shape(dataSet)S = errType(dataSet)  # 最好的特征通过计算平均误差bestS = infbestIndex = 0bestValue = 0for featIndex in range(n - 1):  # 遍历数据的每个属性特征# for splitVal in set(dataSet[:,featIndex]): python3报错修改为下面for splitVal in set((dataSet[:, featIndex].T.A.tolist())[0]):  # 遍历每个特征里不同的特征值mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)  # 对每个特征进行二元分类if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continuenewS = errType(mat0) + errType(mat1)if newS < bestS:  # 更新为误差最小的特征bestIndex = featIndexbestValue = splitValbestS = newS# 如果切分后误差效果下降不大，则取消切分，直接创建叶结点if (S - bestS) < tolS:return None, leafType(dataSet)  # 停止切分2mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)# 判断切分后子集大小，小于最小允许样本数停止切分3if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):return None, leafType(dataSet)return bestIndex, bestValue  # 返回特征编号和用于切分的特征值# 构建tree
def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(0, 1)):# 数据集默认NumPy Mat 其他可选参数【结点类型：回归树，误差计算函数，ops包含树构建所需的其他元组】feat, val = chooseBestSplit(dataSet, leafType, errType, ops)if feat == None: return val  # 满足停止条件时返回叶结点值# 切分后赋值retTree = {}retTree['spInd'] = featretTree['spVal'] = val# 切分后的左右子树lSet, rSet = binSplitDataSet(dataSet, feat, val)retTree['left'] = createTree(lSet, leafType, errType, ops)retTree['right'] = createTree(rSet, leafType, errType, ops)return retTreeif __name__ == "__main__":myDat = mat(loadDataSet('5.2test.txt'))print(createTree(myDat))

4 决策树的剪枝

 决策树生成算法递归地生成决策树，直到不能继续下去为止，却很容易发生 过拟合（overfitting） 现象，为了解决这个问题，提高决策树的 泛化能力，需要对决策树复杂度进行简化，简化决策树的过程叫做 剪枝（pruning） 。决策树剪枝的基本策略有 预剪枝（prepruning） 和 后剪枝（post-pruning）。

4.1 预剪枝（prepruning）

 预剪枝是指在决策树生成的过程中，对每一个节点在划分前先进行评估，若当前节点的划分不能带来决策树的泛化能力的提升，则停止划分，并将当前节点标记为叶子结点，否则继续进行划分。对是否停止划分需要设定条件，这些条件称为 停止标准（stopping criteria），常用的停止标准如下：

• 树的深度
• 叶子节点个数
• 叶子节点的样本数
• 信息增益、信息增益比等特征选择标准的阈值
• 使用 验证集（validition set） 进行验证，看分割前后，精度是否有提高

 由于预剪枝是在构建决策树的同时进行剪枝处理，所以其训练时间开销较少，同时可以有效的降低过拟合的风险。但是，预剪枝有一个问题，会给决策树带来 欠拟合（underfitting） 的风险。

4.2 后剪枝（post-pruning）

 后剪枝则是从训练集生成一颗完整的决策树，然后自下而上地对内部节点进行考察，若将该节点对应的子树替换成叶子节点能够提升决策树的泛化能力，则将该子树替换为叶子节点。常用的方法是使用验证集进行验证，看替换前后，精度是否提高，这样的方法叫做 留出法（hold-out method）。

 相对于预剪枝来说，后剪枝的欠拟合风险很小，同时，泛化能力往往要优于预剪枝，但是，因为后剪枝先要生成整个决策树后，然后才自底向上依次考察每个内部节点，所以训练时间长。以下介绍几种常用的后剪枝算法。

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

 REP算法是最简单的后剪枝方法之一 ，它用训练集合来训练模型，并需要一个验证集来对决策树进行剪枝。 通常取出可用数据集的1/3用作验证集，用剩余2/3作训练集合。 主要用于防止决策树的过度拟合。决定是否修剪某个结点的步骤如下：

• （1）删除以该结点作为根结点的子树；
• （2）使该结点成为叶子结点；
• （3）赋予该结点关联的训练数据的最常见分类；
• （4）当修剪后的树对于验证集的性能与原来的树相同或优于原来的树时，该结点才被删除；
• （5）直到进一步修剪会减低验证集合的精度为止。

 在数据量较少的情况下很少应用REP方法。该方法趋于过拟合，这是因为训练数据集中存在的特性在剪枝过程中都被忽略，当剪枝数据集比训练数据集小得多时这个问题需要特别注意。

4.2.2 悲观误差剪枝（Pessimistic-Error Pruning，PEP，用于C4.5算法）

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

 PEP理论推导

 PEP剪枝法是根据剪枝前后的 误判率 来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补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}=\frac{0.5L+\sum E}{\sum N}$$

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

$$E(sub\_err\_count)-var(sub\_err\_count)>E(leaf\_err\_count)$$

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

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

$$exp(subtree\_err\_count)=N\ast e$$

$$var(subtre{e}_{e}r{r}_{c}ount)=\sqrt{N\ast e\ast (1-e)}$$

 当然并不一定非要一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。对于给定的置信区间，采用下界估计作为规则性能的度量。这样做的结果是对于大的数据集合，该剪枝策略能够非常接近观察精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计有效的，但是在实践中有效。

 PEP采用自顶向下的方式 将符合上述不等式的非叶子结点裁剪掉。该算法看作目前决策树后剪枝算法中精度比较高的算法之一，同时该算法仍存在一些缺陷。首先，PEP算法是唯一使用自顶向上剪枝策略的后剪枝算法，但这样的方法有时会导致某些不该被剪掉的某结点的子结点被剪掉。虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度。

 PEP示例说明

 下面是一个简单的例子，T4 为根的整个这棵子树是不是可以被剪掉？

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

4.2.3 最小误差剪枝（Minimum-Error Pruning，MEP）

 MEP理论推导

 在结点 $T$处, 属于类别 $k$ 的概率为

$$p_k(T)=\frac{n_k(t)+P{r}_k\times m}{N(T)+m}$$

 其中，$n_k(T)$ 表示该节点下的训练样本中被判断为 $k$ 类的样本数量。$P{r}_k$ 表示在该节点下类别 $k$ 的先验概率。$N(T)$ 表示该节点下训练样本的数量。$m$ 是指先验概率对后验概率的影响：

• 如果 $m⟶0$， $P_k(T)⟶\frac{n_k(T)}{N(T)}$ ，则以后验概率为主；
• 如果 $m⟶\infty$，$P_k(T)⟶P{r}_k(T)$，则以先验概率为主，此时 $m$ 可以近似等价于类别总数 $K$。

 在结点 $T$处，因为是最小误差剪枝，所以就是求最小预测错误率

E r r o r ( T ) = min ⁡ { 1 − P k ( T ) } Error(T) = \min \left \{ 1 - P_k(T) \right \} Error(T)=min{1−Pk​(T)}

$$Error(T)=\min \left\{1-\frac{n_k(T)+P{r}_k(T)\times m}{N(T)+m}\right\}$$

$$Error(T)=\min \left\{\frac{N(T)-n_k(T)+m(1-P{r}_k(T))}{N(T)+m}\right\}$$

 如果先验概率是确定的，那么就是以 $m$ 作为变量，得到对应的预测错误率的最小值。这里的 $m$ 是求解出来的，而不是给定的，求解公式为

$$m^{\ast }=\arg \underset{m}{\min }Error(T)$$

 假设 $m=K$，$K$为类别的总个数。一般在无任何假设的情况下，各类别可以看作是等概率出现的，因此，先验概率为

$$P{r}_k(T)=\frac{1}{K}$$

 这样，在结点 $T$处，预测错误率就可以表示为

$$Error(T)=\frac{N(T)-n_k(T)+K-1}{N(T)+K}$$

 MEP剪枝步骤：

 （1）计算剪枝前目标子树每个叶子结点的预测错误率

$$Error(Lea{f}_i)=\frac{N(Lea{f}_i)-n_k(Lea{f}_i)+K-1}{N(Lea{f}_i)+K}$$

 （2）计算剪枝前目标子树的预测错误率

   假如目标子树中一共有 $L$ 个叶子结点

$$Error(Leaf)=\sum _{i=1}^L{w}_{i}Error(Lea{f}_i)=\sum _{i=1}^L\frac{N(Lea{f}_i)}{N(T)}Error(Lea{f}_i)$$

   其中 $w_i=\frac{N(Lea{f}_i)}{N(T)}$ 为每个叶子节点对应的子树的权重。

 （3）计算剪枝后目标子树的预测错误率

$$Error(T)=\frac{N(T)-n_k(T)+K-1}{N(T)+K}$$

   这里就是将整个子树 $T$ 判定为类 $k$，计算出对应的预测错误率。

 （4）比较剪枝前后的预测错误率，如果满足以下不等式，则剪枝；否则，不剪枝

$$Error(T)<Error(Leaf)$$

 MEP示例说明

 使用4.2.2的例子。首先，对于 $T4$ 这棵子树，样本总数为16。它有 $T7$，$T8$，$T9$三个叶子节点。$T7$的样本总数为 $N=9$，分为正类（6个）和负类（3个），即 $K=2$，故 $m=2$，它的预测误差率为

$$Error(T7)=\frac{9-6+2-1}{9+2}=0.364$$

 同理可以计算出

$$Error(T8)=\frac{5-3+2-1}{5+2}=0.429$$

$$Error(T9)=\frac{2-0+2-1}{2+2}=0.75$$

 然后，计算剪枝前目标子树的预测错误率

$$Error(Leaf)=\frac{9}{16}\times 0.364+\frac{5}{16}\times 0.429+\frac{2}{16}\times 0.75=0.433$$

 计算剪枝后目标子树的预测错误率

$$Error(T4)=\frac{16-9+2-1}{16+2}=0.444$$

 比较剪枝前后的预测错误率：由于 $Error(T4)>Error(Leaf)$，说明对节点 $T4$ 剪枝后的预测错误率会提高，结论是不剪枝。

4.2.4 代价复杂度剪枝（Cost-Complexity Pruning，CCP，用于CART算法）

 CCP理论推导

 CCP的剪枝算法分成两步：首先，从生成的决策树 $T_0$ 自下而上不断剪枝，知道根节点，得到一系列的子树 { T 0 , T 1 , . . . , T n } \{T_0, T_1,...,T_n\} {T0​,T1​,...,Tn​}；然后通过交叉验证法使用验证数据集对子树进行测试，得到最优的子树。

 第1步，剪枝，得到一个子树序列

 任意一棵子树 $T$ 的好坏可以使用以下损失函数来衡量

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

 其中 $C(T)$ 为子树 $T$ 对训练数据集的预测误差（如基尼指数）。$\left|T\right|$ 为子树的叶子结点个数。$\alpha \ge 0$为参数，用于权衡训练数据的拟合程度与模型的复杂度。$C_{\alpha }(T)$ 为参数是 $\alpha$ 的子树的整体损失。

 对固定的 $\alpha$，一定存在使损失函数 $C_{\alpha }(T)$ 最小的子树，表示为 $T_{\alpha }$。当 $\alpha$ 大的时候，最优子树 $T_{\alpha }$ 复杂度偏小；当 $\alpha$ 小的时候，最优子树 $T_{\alpha }$ 复杂度偏大。极端情况：当 $\alpha =0$ 时，整体树是最优的。当 $\alpha \to \infty$ 时，根结点组成的单结点树是最优的。

 可以用递归的方法对树进行剪枝。将 $\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, T_1,...,T_n\} {T0​,T1​,...,Tn​}，序列中的子树是嵌套的。

 从整体树 $T_0$ 开始剪枝。对 $T_0$ 的任意内部结点 $t$，以 $t$ 为单结点树的损失函数是

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

 以 $t$ 为根结点的子树 $T_t$ 的损失函数是

$$C_{\alpha }(T_t)=C(T_t)+\alpha \left|T_t\right|$$

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

$$C_{\alpha }(T_t)<C_{\alpha }(t)$$

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

$$C_{\alpha }(T_t)=C_{\alpha }(t)$$

 即

$$C(T_t)+\alpha \left|T_t\right|=C(t)+\alpha$$

 得到

$$\alpha =\frac{C(t)-C(T_t)}{\left|T_t\right|-1}$$

 当 $\alpha$ 继续增大时，以上不等式反向。只要 $\alpha =\frac{C(t)-C(T_t)}{|T_t|-1}$，树 $T_t$ 与 $t$ 有相同的损失函数值，而 $t$ 的节点比 $T_t$ 少，因此 $t$ 比 $T_t$更优，对 $T_t$ 进行剪枝。

 因此，对 $T_0$ 中的内一个内部节点 $t$，计算

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

  $g(t)$ 表示剪枝前后整体损失函数的减少程度。在 $T_0$ 中剪去 $g(t)$ 最小的 $T_t$，将得到的子树作为 $T_1$，同时将最小的 $g(t)$ 设为 ${\alpha }_1$。$T_1$ 为区间 $[{\alpha }_1,{\alpha }_2)$ 的最优子树。如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 $\alpha$ 的值，产生新的区间。

 第2步，利用交叉验证在子树序列中选择最优子树

 利用独立的验证数据集，测试子树序列 { T 0 , T 1 , . . . , T n } \{T_0, T_1,...,T_n\} {T0​,T1​,...,Tn​} 中各棵子树的预测误差（平方误差或基尼指数）。预测误差最小的决策树是最优的决策树。在子树序列中，每棵子树都对应一个参数 { α 1 , α 2 , ⋅ ⋅ ⋅ , α n } \{α_1, α_2, · · · , α_n\} {α1​,α2​,⋅⋅⋅,αn​}。所以，当最优子树 $T_k$ 确定时，对应的 ${\alpha }_k$ 也确定了，即得到最优决策树 $T_{\alpha }$。

 CCP的算法流程

参考文章

1.《统计学习方法》作者 李航

2.《机器学习》作者 周志华

3.《机器学习》作者 Tom M.Mitchell

4.《机器学习实战》作者 Peter Harrington

5.决策树后剪枝算法（四）最小错误剪枝MEP

6.决策树的后剪枝 最小错误剪枝

7.深度理解hold-out Method(留出法)和K-fold Cross-Validation（k折交叉验证法)

8.机器学习算法之决策树分类

9.决策树

10.决策树（脑图）

11.Regression Tree 回归树