机器学习（四）：决策树

引言

    决策树是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。
    决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。
    决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。
    这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman>等人在1984年提出的CART算法。

一、数学预备知识

1.熵（entropy）与经验熵（empirical entropy）

熵是表示随机变量不确定性的度量，熵越大，随机变量的不确定性就越大。
设X是一个取有限个值的离散随机变量，其概率分布为
$P(X=x_i)=p_i,\ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,n$P(X=xi​)=pi​,          i=1,2,⋯,n则随机变量X的熵定义为
$H(X)=-\sum_{i=1}^np_ilog\ p_i$H(X)=−i=1∑n​pi​log pi​当熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵称为经验熵。

2.条件熵（conditional entropy）与经验条件熵（empirical conditional entropy）

条件熵表示在已知随机变量X的条件下随机变量Y的不确定性。
设有随机变量(X,Y)，其联合概率分布为
$P(X=x_i, Y=y_j)=p_{ij},\ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,n;j=1,2,\cdots ,m$P(X=xi​,Y=yj​)=pij​,          i=1,2,⋯,n;j=1,2,⋯,m则随机变量X给定的条件下随机变量Y的条件熵，定义为，X给定条件下Y的条件概率分布的熵对X的数学期望
$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)$H(Y∣X)=i=1∑n​pi​H(Y∣X=xi​)这里，p_i=P(X=x_i)，i=1,2,…,n。
当条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵称为经验条件熵。

3.信息增益（information ga_in）

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

4.信息增益比

特征A对训练集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练集D关于特征A的值的熵HA(D)之比，即
$g_R(D,A)={{g(D,A)}\over{H_A(D)}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$gR​(D,A)=HA​(D)g(D,A)​                            (1)其中，
$H_A(D)=-\sum_{i=1}^n{{|D_i|}\over{|D|}}log_2\ {{|D_i|}\over{|D|}}$HA​(D)=−i=1∑n​∣D∣∣Di​∣​log2​ ∣D∣∣Di​∣​n是特征A取值的个数。

5.基尼指数

分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为
$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^K{p_k}^2$Gini(p)=k=1∑K​pk​(1−pk​)=1−k=1∑K​pk​2

二、决策树模型与学习

1.分类决策树模型

    分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。
    用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。
    图1是一个决策树的示意图，图中圆和方框分别表示内部结点和叶结点。

图1

2.决策树学习

假设给定训练集$D={(x_1,y_1), (x_2,y_2),…(x_N,y_N)}$D=(x1​,y1​),(x2​,y2​),…(xN​,yN​)其中，$x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$xi​=(xi(1)​,xi(2)​,⋯,xi(n)​)T为输入实例（特征向量），n为特征个数，$y_i∈{1,2,\cdots,K}$yi​∈1,2,⋯,K为标记类别，$i=1,2,\cdots,N$i=1,2,⋯,N，$N$N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类（如图2）。

图2     决策树学习本质上是从训练集中归纳出一组分类规则，与训练集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。     决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。通过该方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得简单，从而使它具有更好的泛化能力。以上就是决策树学习的三个步骤：特征选择、决策树的生成、决策树的修剪。     如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

三、特征选择

    特征选择在于选取对训练数据具有分类能力的特征。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的，经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

1.信息增益

    信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。在选择最优特征时，可比较各特征的信息增益值，从中选择信息增益值最大的作为最优特征。
    设训练集为D，|D|表示其样本个数。设有K个类C_k，k=1,2,…,K，|C_k|为属于类C_k的样本个数，$\sum_{k=1}^k|C_k|=|D|$∑k=1k​∣Ck​∣=∣D∣。设特征A有n个不同取值{a₁,a₂,…,a_n}，根据特征A的取值将D划分为n个子集D₁,D₂,…,Dn，|D_i|为D_i的样本个数，$\sum_{i=1}^n|D_i|=|D|$∑i=1n​∣Di​∣=∣D∣。记子集D_i中属于类C_k的样本的集合为D_ik，即D_ik=D_i∩C_k，|D_ik|为D_ik的样本个数。于是信息增益的算法如下：
算法1（信息增益的算法）
输入：训练数据集D和特征A
输出：特征A对训练数据集D的信息增益g(D,A)
① 计算数据集D的经验熵H(D)
$H(D)=-\sum_{k=1}^K{{|C_k|}\over{|D|}}log_2\ {{|C_k|}\over{|D|}}$H(D)=−k=1∑K​∣D∣∣Ck​∣​log2​ ∣D∣∣Ck​∣​② 计算特征A对数据集D的经验条件熵H(D|A)
$H(D|A)=\sum_{i=1}^n{{|D_i|}\over{|D|}}H(D_i)=-\sum_{i=1}^n{{|D_i|}\over{|D|}}\sum_{k=1}^K{{|D_{ik}|}\over{|D_i|}}log_2\ {{|D_{ik}|}\over{|D_i|}}$H(D∣A)=i=1∑n​∣D∣∣Di​∣​H(Di​)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Dik​∣​log2​ ∣Di​∣∣Dik​∣​③ 计算信息增益
$g(D,A)=H(D)-H(D|A)$g(D,A)=H(D)−H(D∣A)证明：
① 因为
$P(D=C_k)={{|C_k|}\over{|D|}},\ \ \ \ \ \ \ \ \ \ k=1,2,\cdots ,K$P(D=Ck​)=∣D∣∣Ck​∣​,          k=1,2,⋯,K根据经验熵公式可得
$H(D)=-\sum_{k=1}^K{{|C_k|}\over{|D|}}log_2\ {{|C_k|}\over{|D|}}$H(D)=−k=1∑K​∣D∣∣Ck​∣​log2​ ∣D∣∣Ck​∣​②因为
$P(D_i=D_{ik})={{|D_{ik}|}\over{|D_i|}},\ \ \ \ \ \ \ \ \ \ k=1,2,\cdots ,K$P(Di​=Dik​)=∣Di​∣∣Dik​∣​,          k=1,2,⋯,K则
$H(D|A=a_i)=H(D_i)=-\sum_{k=1}^K{{|D_{ik}|}\over{|D_i|}}log_2\ {{|D_{ik}|}\over{|D_i|}}$H(D∣A=ai​)=H(Di​)=−k=1∑K​∣Di​∣∣Dik​∣​log2​ ∣Di​∣∣Dik​∣​又因为
$P(A=a_i)={{|D_i|}\over{|D|}},\ \ \ \ \ \ \ \ \ \ i=1,2,\cdots ,n$P(A=ai​)=∣D∣∣Di​∣​,          i=1,2,⋯,n根据经验条件熵公式可得
$H(D|A)=\sum_{i=1}^n{{|D_i|}\over{|D|}}H(D_i)=-\sum_{i=1}^n{{|D_i|}\over{|D|}}\sum_{k=1}^K{{|D_{ik}|}\over{|D_i|}}log_2\ {{|D_{ik}|}\over{|D_i|}}$H(D∣A)=i=1∑n​∣D∣∣Di​∣​H(Di​)=−i=1∑n​∣D∣∣Di​∣​k=1∑K​∣Di​∣∣Dik​∣​log2​ ∣Di​∣∣Dik​∣​

2.信息增益比

    以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。这是特征选择的另一准则。在选择最优特征时，可比较各特征的信息增益比，从中选择信息增益比最大的作为最优特征。

四、决策树的生成

1.ID3算法

    ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。
    ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。
算法2（ID3算法）
输入：训练数据集D，特征集A，阈值ε
输出：决策树T
① 如果D中所有实例属于同一类C_k，则置T为单结点树，并将C_k作为该结点的类，返回T
② 如果A=Ø，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T
③ 否则，按算法1计算A中各特征对D的信息增益，选择信息增益最大的特征A_g
④ 如果A_g的信息增益小于阈值ε，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T
⑤ 否则，对A_g的每一可能值a_i，依A_g=a_i将D分割为若干非空子集D_i，将D_i中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T
⑥ 对结点i，以D_i为训练集，以A-{A_g}为特征集，递归地调用①~⑤，得到子树T_i，返回T_i

2.C4.5的生成算法

    C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。
算法3（C4.5算法）
输入：训练数据集D，特征集A，阈值ε
输出：决策树T
① 如果D中所有实例属于同一类C_k，则置T为单结点树，并将C_k作为该结点的类，返回T
② 如果A=Ø，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T
③ 否则，按式(1)计算A中各特征对D的信息增益比，选择信息增益比最大的特征A_g
④ 如果A_g的信息增益比小于阈值ε，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类，返回T
⑤ 否则，对A_g的每一可能值a_i，依A_g=a_i将D分割为若干非空子集D_i，将D_i中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T
⑥ 对结点i，以D_i为训练集，以A-{A_g}为特征集，递归地调用①~⑤，得到子树T_i，返回T_i

五、决策树的剪枝

    在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
    决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有N_t个样本点，其中k类的样本点有N_tk个，k=1,2,…,K，H_t(T)为叶结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为
$C_α(T)=\sum_{t=1}^{|T|}N_tH_t(T)+α|T|\ \ \ \ \ \ \ \ \ \ \ \ (2)$Cα​(T)=t=1∑∣T∣​Nt​Ht​(T)+α∣T∣            (2)其中经验熵为
$H_t(T)=-\sum_{k}{{N_{tk}}\over{N_t}}log\ {{N_{tk}}\over{N_t}}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$Ht​(T)=−k∑​Nt​Ntk​​log Nt​Ntk​​                  (3)将(3)代入(2)，则(2)右端的第一项可记作
$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}log\ {{N_{tk}}\over{N_t}}$C(T)=t=1∑∣T∣​Nt​Ht​(T)=−t=1∑∣T∣​k=1∑K​Ntk​log Nt​Ntk​​这时有
$C_α(T)=C(T)+α|T|$Cα​(T)=C(T)+α∣T∣C(T)表示模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。较大的α促使选择较简单的模型，较小的α促使选择较复杂的模型，α=0则不考虑模型的复杂程度。
    剪枝，就是当α确定时，选择损失函数最小的模型。
证明：
    C(T)表示模型与训练数据的拟合程度：C(T)的计算中使用的是树T的经验熵，熵越小则表示随机变量不确定性越小，所以C(T)越小表示模型与训练数据的拟合程度越好。
    |T|表示模型复杂度：|T|是树T的叶结点个数，|T|越小即叶结点个数少，则模型复杂度小。
算法4（树的剪枝算法）
输入：生成算法产生的整个树T，参数α
输出：修剪后的子树T_α
① 计算每个结点的经验熵
② 递归地从树的叶结点向上回缩，设一组叶结点回缩到其父结点之前与之后的整体树分别为T_B与T_A，其对应的损失函数值分别是C_α(T_B)与C_α(T_A)，如果
$C_α(T_A)≤C_α(T_B)$Cα​(TA​)≤Cα​(TB​)则进行剪枝，即将父结点变为新的叶结点
③ 返回②，直至不能继续为止，得到损失函数最小的子树T_α

六、CART算法

    分类与回归树（classification and regression tree，CART）模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类和回归的树统称为决策树。
    CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征。

1.CART生成（回归树的生成）

    回归树用平方误差最小化准则进行特征选择，生成二叉树。
    一个回归树对应着输入空间的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元R₁,R₂,…,R_M，并且在每个单元R_m上有一个固定的输出值C_m，于是回归树模型可表示为
$f(x)=\sum_{m=1}^MC_mI(x\in R_m)$f(x)=m=1∑M​Cm​I(x∈Rm​)    当输入空间的划分确定时，可以用平方误差
$\sum_{x_i\in R_m}(y_i-f(x_i))^2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$xi​∈Rm​∑​(yi​−f(xi​))2                       (4)来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元R_m上的C_m的最优值$\hat C_m$C^m​是R_m上的所有输入实例x_i对应的输出y_i的均值，即
$\hat C_m=ave(y_i|x_i\in R_m)$C^m​=ave(yi​∣xi​∈Rm​)    采用启发式的方法对输入空间进行划分：选择第j个变量x^(j)和它取的值s，作为切分变量和切分点，并定义两个区域
$R_1(j,s)=\{x|x^{(j)} ≤s\}，R_2(j,s)=\{x|x^{(j)}>s\}$R1​(j,s)={x∣x(j)≤s}，R2​(j,s)={x∣x(j)>s}然后寻找最优切分变量j和最优切分点s，具体地，求解
$min_{j,s}[min_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$minj,s​[minc1​​xi​∈R1​(j,s)∑​(yi​−c1​)2+minc2​​xi​∈R2​(j,s)∑​(yi​−c2​)2]遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)。依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一颗回归树，这样的回归树通常称为最小二乘回归树。
算法5（最小二乘回归树生成算法）
输入：训练集D，停止计算的条件
输出：回归树f(x)
在训练集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。
① 选择最优切分变量j与切分点s，求解
$min_{j,s}[min_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$minj,s​[minc1​​xi​∈R1​(j,s)∑​(yi​−c1​)2+minc2​​xi​∈R2​(j,s)∑​(yi​−c2​)2]遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)。
② 用选定的对(j,s)划分区域并决定相应的输出值：
$R_1(j,s)=\{x|x^{(j)} ≤s\}，R_2(j,s)=\{x|x^{(j)}>s\}$R1​(j,s)={x∣x(j)≤s}，R2​(j,s)={x∣x(j)>s}$\hat C_m={{1}\over{N_m}}\sum_{x_i\in R_m(j,s)}y_i\ ,\ x\in R_m\ ,\ m=1,2$C^m​=Nm​1​xi​∈Rm​(j,s)∑​yi​ , x∈Rm​ , m=1,2③ 继续对两个子区域调用步骤，直至满足停止条件
将输入空间划分为M个区域R₁,R₂,…,R_M，生成决策树：
$f(x)=\sum_{m=1}^M\hat C_mI(x\in R_m)$f(x)=m=1∑M​C^m​I(x∈Rm​)

2.CART生成（分类树的生成）

    分类树用基尼指数最小化准则进行特征选择，同时决定该特征的最优二值切分点，生成二叉树。
    对于给定的样本集合D，其基尼指数为
$Gini(D)=1-\sum_{k=1}^K({{|C_k|}\over{|D|}})^2$Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2其中，C_k是D中属于第k类的样本子集，K是类的个数。
    如果样本集合D根据特征A是否取某一可能值a被分割成D₁和D₂两部分，即
$D_1=\{(x,y)\in D|A(x)=a \}，D_2=D-D_1$D1​={(x,y)∈D∣A(x)=a}，D2​=D−D1​则在特征A的条件下，集合D的基尼指数定义为
$Gini(D,A)={{|D_1|}\over{|D|}}Gini(D_1)+{{|D_2|}\over{|D|}}Gini(D_2)$Gini(D,A)=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大。
算法6（CART生成算法）
输入：训练集D，停止计算的条件
输出：CART决策树
根据训练集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
① 设结点的训练集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D₁和D₂两部分，利用(1)计算A=a时的基尼指数
② 在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练集依特征分配到两个子结点中去。
③ 对两个子结点递归地调用①②，直至满足停止条件
④ 生成CART决策树
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

3.CART剪枝

    在剪枝过程中，计算子树的损失函数：
$C_α(T)=C(T)+α|T|$Cα​(T)=C(T)+α∣T∣其中，T为任意子树，C(T)为对训练数据的预测误差（如基尼指数），|T|为子树的叶结点个数，α≥0为参数，C_α(T)为参数是α时的子树T的整体损失。
    可以用递归的方法对树进行剪枝，将α从小增大，0=α₀<α₁<…<α_n<+∞，产生一系列的区间[α_i,α_i+1)，i=0,1,…,n；剪枝得到的子树序列对应着区间α∈[α_i,α_i+1)，i=0,1,…,n的最优子树序列{T₀,T₁,…,T_n}，序列中的子树是嵌套的。
    具体地，从整体树T₀开始剪枝，对T₀的任意内部结点t，以t为单结点树的损失函数是$C_α(t)=C(t)+α$Cα​(t)=C(t)+α。以t为根结点的子树T_t的损失函数是$C_α(T_t)=C(T_t)+α|T_t|$Cα​(Tt​)=C(Tt​)+α∣Tt​∣。
    当α=0及α充分小时，有不等式$C_α(T_t)&lt;C_α(t)$Cα​(Tt​)<Cα​(t)；当α增大时，在某一α有$C_α(T_t)=C_α(t)$Cα​(Tt​)=Cα​(t)；当α再增大时，有不等式$C_α(T_t)&gt;C_α(t)$Cα​(Tt​)>Cα​(t)。
    只要
$α={{C(t)-C(T_t)}\over{|T_t|-1}}$α=∣Tt​∣−1C(t)−C(Tt​)​T_t与t有相同的损失函数值，而t的结点少，因此t比T_t更可取，对T_t进行剪枝。
    为此，对T₀中每一个内部结点t，计算
$g(t)={{C(t)-C(T_t)}\over{|T_t|-1}}$g(t)=∣Tt​∣−1C(t)−C(Tt​)​它表示剪枝后整体损失函数减少的程度。在T₀中剪去g(t)最小的T_t，将得到的子树所为T₁，同时将最小的g(t)设为α₁，T₁为区间[α₁,α₂)的最优子树。
    如此剪枝下去，直至根结点，在这一过程中，不断地增加α的值，产生新的区间。
    在剪枝得到的子树序列T₀,T₁,…,T_n中通过交叉验证选取最优子树T_α，具体地，利用独立的验证数据集，测试子树序列中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树T₁,T₂,…,T_n都对应于一个参数α₁,α₂,…,α_n，所以当最优子树Tk确定时，对应的α_k也确定了，即得到最优决策树T_α。
证明：
① 当α=0及α充分小，此时影响损失函数的是模型的拟合程度，固有$C_α(T_t)&lt;C_α(t)$Cα​(Tt​)<Cα​(t)；
当α不断增大到某一值，此时简单的模型损失函数值越小，固有$C_α(T_t)&gt;C_α(t)$Cα​(Tt​)>Cα​(t)。
② 若T_t与t有相同的损失函数值，即$C_α(T_t)=C_α(t)$Cα​(Tt​)=Cα​(t)，则$C(T_t)+α|T_t|=C(t)+α$C(Tt​)+α∣Tt​∣=C(t)+α，解得
$α={{C(t)-C(T_t)}\over{|T_t|-1}}$α=∣Tt​∣−1C(t)−C(Tt​)​③ 设T₁对应的剪去的T_t为T_t1，α₁使得$C_{α1}(T_{t1})=C_{α1}(t_1)$Cα1​(Tt1​)=Cα1​(t1​)，随着α再增大，有不等式$C_{α1}(T_{t1})&gt;C_{α1}(t_1)$Cα1​(Tt1​)>Cα1​(t1​)，固在区间[α₁,α₂)有
$C_{α1}(T_{t1})\geq C_{α1}(t1)$Cα1​(Tt1​)≥Cα1​(t1)对于T_m，m=2,3,…,n，对应剪去的T_t为T_tm，此时α₁<α_m，α还未增大至能使T_tm与t_m损失函数值相等，固在区间[α1,α2)有
$C_{α1}(T_{tm})&lt; C_{α1}(tm)$Cα1​(Ttm​)<Cα1​(tm)此时不满足对T_m进行修剪的条件。
证得T₁为区间[α₁,α₂)的最优子树
算法7（CART剪枝算法）
输入：CART算法生成的决策树T₀
输出：最优决策树T_α
① 设k=0，T= T₀
② 设$α=+\infty$α=+∞
③ 自下而上地对各内部结点t计算C(T_t)，|T_t|以及
$g(t)={{C(t)-C(T_t)}\over{|T_t|-1}}$g(t)=∣Tt​∣−1C(t)−C(Tt​)​$α=min(α,g(t))$α=min(α,g(t))这里，T_t表示以t为根结点的子树，C(T_t)是对训练数据的预测误差，|T_t|是T_t的叶结点个数
④ 自上而下地访问内部结点t，如果有g(t)=α，进行剪枝，并对叶结点t以多数表决法决定其类，得到树T
⑤ 设$k=k+1，α_k=α，T_k=T$k=k+1，αk​=α，Tk​=T
⑥ 如果T不是由根结点单独构成的树，则回到④
⑦ 采用交叉验证法在子树序列T₀,T₁,…,T_n中选取最优子树T_α

七、代码实现（python）

以下代码来自Peter Harrington《Machine Learing in Action》
本例代码实现算法5，生成最小二乘回归树。
代码如下（保存为CART.py）：

# -- coding: utf-8 --
from numpy import *

def loadDataSet(fileName):
    # 获取训练集
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = map(float,curLine)
        dataMat.append(fltLine)
    return dataMat

def binSplitDataSet(dataSet, feature, value):
    # 该函数接收3个参数，数据集、第几个特征（切分变量）、划分条件（切分点），根据选择的特征和划分条件将数据分成两个区域
    mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]
    mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]
    return mat0,mat1

def regLeaf(dataSet):
    # 获取数据集dataSet最后一列的平均值
    return mean(dataSet[:,-1])

def regErr(dataSet):
    # 根据式(4)计算数据集dataSet的平方误差
    # var用于计算方差
    return var(dataSet[:,-1]) * shape(dataSet)[0]

def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
    # 该函数用于寻找对于数据集dataSet的最好切分变量及切分点（即使得平方误差最小），ops用于控制函数停止机制
    tolS = ops[0]                              # 容许的误差下降值
    tolN = ops[1]                              # 切分的最小样本数
    if len(set(dataSet[:,-1].T.tolist()[0])) == 1:
        return None, leafType(dataSet)         # 若所有类别值相等，退出，此时无最好切分量
    m,n = shape(dataSet)
    S = errType(dataSet)                       # 存储数据集的平方误差
    bestS = inf
    bestIndex = 0                              # 初始化切分变量
    bestValue = 0                              # 初始化切分点
    for featIndex in range(n-1):
        # 循环特征数目，featIndex此时为切分变量
        for splitVal in set(dataSet[:,featIndex]):
            # 循环数据集行数，splitVal此时为切分点
            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)      # 根据循环到的切分变量与切分点将数据分成两个区域
            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue # 若切分后的样本点小于最小样本数，退出此次循环，继续下一个循环
            newS = errType(mat0) + errType(mat1)# 计算划分后数据集的平方误差
            if newS < bestS:                    # 若新的平方误差更小，更新各个数据
                bestIndex = featIndex
                bestValue = splitVal
                bestS = newS
    if (S - bestS) < tolS:                      # 若误差下降值小于容许的误差下降值，退出，此时无最好切分量
        return None, leafType(dataSet)
    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)              # 用新的切分变量与切分点将数据分成两个区域
    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):                   # 若切分后的样本点小于最小样本数，退出，此时无最好切分量
        return None, leafType(dataSet)
    return bestIndex,bestValue

def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
    # 该函数根据接收的数据集创建决策树（子树）
    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)             # 寻找对于数据集dataSet的最好切分变量及切分点
    if feat == None: return val                 # 若无最好的切分点，则返回数据集均值作为叶节点
    retTree = {}
    retTree['spInd'] = feat
    retTree['spVal'] = val
    lSet, rSet = binSplitDataSet(dataSet, feat, val)                         # 用最好的切分变量与切分点将数据分成两个区域，作为左右子树
    retTree['left'] = createTree(lSet, leafType, errType, ops)
    retTree['right'] = createTree(rSet, leafType, errType, ops)
    return retTree

数据集格式如下（保存为ex00.txt）：

0.036098	0.155096
0.993349	1.077553
0.530897	0.893462
0.712386	0.564858
0.343554	-0.371700
0.098016	-0.332760

运行命令如下：











以上全部内容参考书籍如下：
李航《统计学习方法》