决策树是什么东西？就是我们平常所说的if-then条件，我们把它组合成树的结构。
决策树既可以做分类也可以做回归，同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结
image.png
算法思想：
决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别（即叶结点）中。

决策树由三部分构成：

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

    决策树

    决策树中很重要的一点就是选择一个特征属性进行分枝，这里简单说一下几种经典的实现算法：ID3算法，C4.5算法和CART算法。这些算法的主要区别在于分类结点熵特征选择的选取标准不同：

先给出两个定义，信息熵和条件熵:

信息熵表示随机变量不确定性的度量,设随机标量X是一个离散随机变量，其概率分布为: 2022-06-23-决策树 - 图2%3Dpi%2C%20i%3D1%2C2%2C…%2Cn%0A#card=math&code=P%28X%3Dx_i%29%3Dp_i%2C%20i%3D1%2C2%2C…%2Cn%0A&id=hedgE) 则随机变量X的熵定义为: 2022-06-23-决策树 - 图3%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7Dpilog%7Bp_i%7D%0A#card=math&code=H%28X%29%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7Dp_ilog%7Bp_i%7D%0A&id=kr905)

熵越大，随机变量的不确定性就越大，当2022-06-23-决策树 - 图4时，
随机变量的熵最大等于logn，故2022-06-23-决策树 - 图5%20%5Cleq%20logn#card=math&code=0%20%5Cleq%20H%28P%29%20%5Cleq%20logn&id=b5k3C).

条件熵就是在给定X的条件的情况下，随机标量Y的条件，记作2022-06-23-决策树 - 图6#card=math&code=H%28Y%7CX%29&id=RcAcq)，可以结合贝叶斯公式进行理解，定义如下 2022-06-23-决策树 - 图7%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7Dp_iH(Y%7CX%3Dx_i)%0A#card=math&code=H%28Y%7CX%29%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7Dp_iH%28Y%7CX%3Dx_i%29%0A&id=nGaFq) 这里2022-06-23-决策树 - 图8%2Ci%3D1%2C2%2C…%2Cn#card=math&code=p_i%3DP%28X%3Dx_i%29%2Ci%3D1%2C2%2C…%2Cn&id=Sq1jh).
一般在基于数据的估计中，我们使用的基于极大似然估计出来的经验熵和经验条件熵.

假设：

  • 训练集为D，|D|表示所有训练样本总数；
  • D有K个类别2022-06-23-决策树 - 图9；2022-06-23-决策树 - 图10为属于类2022-06-23-决策树 - 图11的样本总数，即2022-06-23-决策树 - 图12；
  • 特征集合A有n个不同的取值 2022-06-23-决策树 - 图13，根据特征A的取值将D划分为n个子集2022-06-23-决策树 - 图14，2022-06-23-决策树 - 图15为子集 2022-06-23-决策树 - 图16 中的样本个数，即 2022-06-23-决策树 - 图17；

则有：

  • 数据集D的经验信息熵H(D)为：
    2022-06-23-决策树 - 图18%3D-%5Csum%7B%5Cmathrm%7Bk%7D%3D1%7D%5E%7B%7C%5Cmathrm%7BK%7D%7C%7Dp(%C2%B7)log_2p(%C2%B7)%3D-%5Csum%7B%5Cmathrm%7Bk%7D%3D1%7D%5E%7B%7C%5Cmathrm%7BK%7D%7C%7D%20%5Cfrac%7B%5Cleft%7C%5Cmathrm%7BC%7D%7B%5Cmathrm%7Bk%7D%7D%5Cright%7C%7D%7B%7C%5Cmathrm%7BD%7D%7C%7D%20%5Clog%20%7B2%7D%20%5Cfrac%7B%5Cleft%7C%5Cmathrm%7BC%7D%7B%5Cmathrm%7Bk%7D%7D%5Cright%7C%7D%7B%7C%5Cmathrm%7BD%7D%7C%7D#card=math&code=%5Cmathrm%7BH%7D%28%5Cmathrm%7BD%7D%29%3D-%5Csum%7B%5Cmathrm%7Bk%7D%3D1%7D%5E%7B%7C%5Cmathrm%7BK%7D%7C%7Dp%28%C2%B7%29log2p%28%C2%B7%29%3D-%5Csum%7B%5Cmathrm%7Bk%7D%3D1%7D%5E%7B%7C%5Cmathrm%7BK%7D%7C%7D%20%5Cfrac%7B%5Cleft%7C%5Cmathrm%7BC%7D%7B%5Cmathrm%7Bk%7D%7D%5Cright%7C%7D%7B%7C%5Cmathrm%7BD%7D%7C%7D%20%5Clog%20%7B2%7D%20%5Cfrac%7B%5Cleft%7C%5Cmathrm%7BC%7D_%7B%5Cmathrm%7Bk%7D%7D%5Cright%7C%7D%7B%7C%5Cmathrm%7BD%7D%7C%7D&id=ALQKV)
  • 数据集D在特征值A下的经验条件熵H(D|A)为：2022-06-23-决策树 - 图19%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20H%5Cleft(D%7Bi%7D%5Cright)%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20%5Csum%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%20k%7D%5Cright%7C%7D%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%20%5Clog%20%7B2%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%20k%7D%5Cright%7C%7D%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D#card=math&code=H%28D%20%5Cmid%20A%29%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20H%5Cleft%28D%7Bi%7D%5Cright%29%3D-%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20%5Csum%7Bk%3D1%7D%5E%7BK%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%20k%7D%5Cright%7C%7D%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%20%5Clog%20%7B2%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%20k%7D%5Cright%7C%7D%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D&id=pq0Xo)

ID3 特征选择

  • ID3是采用信息增益作为特征选择的评价标准，信息增益越大，说明按此特征分类后信息的不确定性减少程度也越大。
  • 信息增益=信息熵-条件熵:

2022-06-23-决策树 - 图20
C4.5 特征选择

  • C4.5是在ID3的算法基础上，采用信息增益率来做为标准，通过增加类别的惩罚因子，规避了类别越多信息增益越大的问题，提升决策树的泛化能力，同时也可以通过均值离散化的方式处理连续变量的问题。
  • 信息增益率=信息增益 / 条件熵：

2022-06-23-决策树 - 图21
2022-06-23-决策树 - 图22
CART 特征选择

  • CART不再通过信息熵的方式选取最优划分特征，而是采用基尼系数（Gini），也叫基尼不纯度，两者衡量信息量的作用相当，但是基尼系数由于没有对数运算，可大大减少计算开销。

2022-06-23-决策树 - 图23%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Cleft(%5Cfrac%7B%5Cleft%7CC%7Bk%7D%5Cright%7C%7D%7B%7CD%7C%7D%5Cright)%5E%7B2%7D%20%5C%5C%0A%5Coperatorname%7BGini%7D(%5Cmathrm%7BD%7D%2C%20%5Cmathrm%7BA%7D)%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20%5Coperatorname%7BGini%7D(D%20i)%0A%5Cend%7Barray%7D%0A#card=math&code=%5Cbegin%7Barray%7D%7Bc%7D%0A%5Coperatorname%7BGini%7D%28D%29%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7D%5Cleft%28%5Cfrac%7B%5Cleft%7CC%7Bk%7D%5Cright%7C%7D%7B%7CD%7C%7D%5Cright%29%5E%7B2%7D%20%5C%5C%0A%5Coperatorname%7BGini%7D%28%5Cmathrm%7BD%7D%2C%20%5Cmathrm%7BA%7D%29%3D%5Csum%7Bi%3D1%7D%5E%7Bn%7D%20%5Cfrac%7B%5Cleft%7CD%7Bi%7D%5Cright%7C%7D%7B%7CD%7C%7D%20%5Coperatorname%7BGini%7D%28D%20i%29%0A%5Cend%7Barray%7D%0A&id=sN5CU)

我们总结(ID3,C4.5)决策树算法伪代码:

  1. 输入:数据集D，特征集合A，阈值e
  2. 输出:决策树T
  3. 如果D中所有实例输出同一类2022-06-23-决策树 - 图24, 则T作为单节点树，并将类2022-06-23-决策树 - 图25作为该节点的类标记，返回T;
  4. 若2022-06-23-决策树 - 图26,则T为单节点树，将D中实例数最多的类2022-06-23-决策树 - 图27作为该节点的类标记，返回T；
  5. 否则，根据信息增益(ID3)或者信息增益比(C4.5)计算特征A对D的值，选择当前最优的特征2022-06-23-决策树 - 图28;
  6. 如果2022-06-23-决策树 - 图29的信息增益小于阈值e，则置T为单节点数，并将D中实例最多的类2022-06-23-决策树 - 图30作为当前的类标记，返回T；
  7. 否则，根据2022-06-23-决策树 - 图31中的每一个不同的2022-06-23-决策树 - 图32,根据2022-06-23-决策树 - 图33将D分成若干个非空子集，对于第i个子节点，以2022-06-23-决策树 - 图34为数据集，以2022-06-23-决策树 - 图35为特征集，递归(重复3-6)构造决策树2022-06-23-决策树 - 图36,返回2022-06-23-决策树 - 图37.
  8. 对决策树模型T进行剪枝.

从上述算法中，我们有三个问题，需要再次提出，并进行解释：

  1. 为什么使用信息增益，越大越能得到好的模型？

    上面提到过，信息熵表示数据的混乱的程度，信息增益是信息熵和条件信息熵的差值，表示的熵减少的程度，信息增益越大，代表根据我们的决策树规则得到的数据越趋向于规整，这就是我们划分类别的目的.

  2. 为什么从信息增益变到信息增益比，目的何在？

    信息增益根据特征之后的条件信息熵，这样的话偏向于特征取值较多的特征的问题，因此使用信息增益比对这个问题进行校正.

  3. 为什么要进行剪枝？

    在构造决策树的过程中，我们的两个停止条件是，子集只有一个类别和没有可以选择的特征，这是我们全部利用了数据中的所有可以使用的信息，但是我们知道数据是可能有误差了，而且数据不足，我们需要得到更鲁棒的模型，剪枝的意义就是是的深度减小，这样的就相当于减少规则的情况下，决策树的性能反而不差，使其更加鲁棒.

剪枝

再说为什么剪枝，我们构造决策树的时候，是完全的在训练数据上得到最优的模型. 这就是问题，这就什么，这就过拟合，训练误差很小，但是验证集上就不怎么好用. 损失=经验风险最小化+正则项=结构风险最小化. 构造决策树的时候只考虑了经验风险最小化，剪枝的时候我们考虑结构风险最小化，正则项就是树的叶子节点个数. 重新定义损失函数，树的叶子节点个数|T|,t是树T的叶节点，该叶节点有2022-06-23-决策树 - 图38个样本，其中k类的样本点有2022-06-23-决策树 - 图39个，k=1,2，…,K, 2022-06-23-决策树 - 图40#card=math&code=H_t%28T%29&id=jhYKg)是叶子节点t经验熵，2022-06-23-决策树 - 图41是参数,平衡经验损失和正则项，得到计算公式如下:

2022-06-23-决策树 - 图42%3D%5Csum%7Bt%3D1%7D%5E%7B%7CT%7C%7DN_tH_t(T)%2B%5Calpha%7CT%7C%0A#card=math&code=C%7B%5Calpha%7D%28T%29%3D%5Csum_%7Bt%3D1%7D%5E%7B%7CT%7C%7DN_tH_t%28T%29%2B%5Calpha%7CT%7C%0A&id=ibNgw)

其中，经验熵为:

2022-06-23-决策树 - 图43%3D-%5Csum%7Bk%7D%5Cfrac%7BN%7Btk%7D%7D%7BHt%7Dlog%5Cfrac%7BN%7Btk%7D%7D%7BHt%7D%0A#card=math&code=H_t%28T%29%3D-%5Csum%7Bk%7D%5Cfrac%7BN%7Btk%7D%7D%7BH_t%7Dlog%5Cfrac%7BN%7Btk%7D%7D%7BH_t%7D%0A&id=E9zR6)

这是有:

2022-06-23-决策树 - 图44%2B%5Calpha%7CT%7C%0A#card=math&code=C_%7B%5Calpha%7D%3DC%28T%29%2B%5Calpha%7CT%7C%0A&id=oPyiM)

决策树剪枝优化过程考虑了在训练数据上的经验风险最小化和减小模型复杂度两个方向. 因为加了正则项，所有我们基于贪心的思想进行剪枝，因为当剪掉一个树节点，虽然经验风险增加了，但是模型复杂度降低了，我们基于两个方面的平衡进行剪枝，如果剪掉之后，总的风险变小，就进行剪枝.

算法:
输入: 算法产生的整个决策树，参数2022-06-23-决策树 - 图45
修剪之后的树2022-06-23-决策树 - 图46

  1. 计算每个节点的经验熵
  2. 递归从树的叶节点向上回溯，假设将某个叶节点回缩到其父节点前后的整体树对应的2022-06-23-决策树 - 图47和2022-06-23-决策树 - 图48,对应的损失分别是2022-06-23-决策树 - 图49#card=math&code=C%7B%5Calpha%7D%28T_B%29&id=mqvXW)和![](https://g.yuque.com/gr/latex?C%7B%5Calpha%7D(TA)#card=math&code=C%7B%5Calpha%7D%28TA%29&id=PW8TF)，如果:![](https://g.yuque.com/gr/latex?C%7B%5Calpha%7D(TA)%20%5Cleq%20C%7B%5Calpha%7D(TB)%0A#card=math&code=C%7B%5Calpha%7D%28TA%29%20%5Cleq%20C%7B%5Calpha%7D%28T_B%29%0A&id=Lg60Q) 表示，剪掉之后，损失减小，就进行剪枝.
  3. 重复2，直到不能继续为止，得到损失函数最小的子树2022-06-23-决策树 - 图50. 注: 动态规划加速，是个好方法.

CART

分类与回归树(classification and regression tree, CART)与上述决策树的不同，

  1. 既可以做分类又可以做回归.
  2. 是二叉树，内部节点特征取值，只有yes和no两个选项
    同样地，先进行决策树构造，在基于验证集上进行CART决策树的剪枝，既然是回归和分类树，我们就分别介绍回归和分类两种情况.
  • 分类: gini指数
  • 回归: 平方误差
    定义数据格式:

2022-06-23-决策树 - 图51%2C(x_2%2Cy_2)%2C…%2C(x_N%2Cy_N)%7D%0A#card=math&code=D%3D%7B%28x_1%2Cy_1%29%2C%28x_2%2Cy_2%29%2C…%2C%28x_N%2Cy_N%29%7D%0A&id=RDl9t)

其中，2022-06-23-决策树 - 图52是向量，当回归问题时，2022-06-23-决策树 - 图53是连续变量; 分类问题时，2022-06-23-决策树 - 图54是离散变量.

回归树(Regerssion Tree)

算法:
在训练数据上，根据某一个特征将每个区域划分为两个子区域并决定每个子区域的输出值，递归构建二叉树.

  1. 选择最优切分变量j和切分点s，求解

2022-06-23-决策树 - 图55%7D(yi-c_1)%5E2%20%2B%20min%7Bc2%7D%5Csum%7Bxi%20%5Cin%20R_2(j%2Cs)%7D(y_i-c_2)%5E2%5D%0A#card=math&code=min%7Bj%2Cs%7D%5Bmin%7Bc_1%7D%5Csum%7Bxi%20%5Cin%20R_1%28j%2Cs%29%7D%28y_i-c_1%29%5E2%20%2B%20min%7Bc2%7D%5Csum%7Bx_i%20%5Cin%20R_2%28j%2Cs%29%7D%28y_i-c_2%29%5E2%5D%0A&id=fRMsI)

遍历变量j，对固定的切分变量j扫描所有的s，找到使得上式最小的对(j,s).

  1. 使用选定的(j,s)划分区域并决定相应的输出值:

2022-06-23-决策树 - 图56%3D%5C%7Bx%7Cx%5E%7B(j)%7D%20%5Cleq%20s%20%5C%7D%2C%20R_2(j%2Cs)%3D%5C%7Bx%7Cx%5E%7B(j)%7D%20%3E%20s%20%5C%7D%2C%0A#card=math&code=R_1%28j%2Cs%29%3D%5C%7Bx%7Cx%5E%7B%28j%29%7D%20%5Cleq%20s%20%5C%7D%2C%20R_2%28j%2Cs%29%3D%5C%7Bx%7Cx%5E%7B%28j%29%7D%20%3E%20s%20%5C%7D%2C%0A&id=lCDIV)

2022-06-23-决策树 - 图57%7Dyi%2C%20x%20%5Cin%20R_m%2C%20m%3D1%2C2%0A#card=math&code=c_m%3D%5Cfrac%7B1%7D%7BN_m%7D%5Csum%7Bx_i%20%5Cin%20R_m%28j%2Cs%29%7Dy_i%2C%20x%20%5Cin%20R_m%2C%20m%3D1%2C2%0A&id=a0vp8)

  1. 继续对两个子区域调用1和2，知道满足条件
  2. 将输入空间划分为M个区域2022-06-23-决策树 - 图58,生成决策树:2022-06-23-决策树 - 图59%3D%5Csum%7Bm%3D1%7D%5E%7BM%7Dc_mI(x%20%5Cin%20R_m)%0A#card=math&code=f%28x%29%3D%5Csum%7Bm%3D1%7D%5E%7BM%7Dc_mI%28x%20%5Cin%20R_m%29%0A&id=Y03Zc)

分类树(classification tree)

基尼指数计算公式如下:
2022-06-23-决策树 - 图60%3D%5Csum%7Bk%3D1%7D%5E%7BK%7Dp_k(1-p_k)%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7Dpk%5E2%0A#card=math&code=Gini%28p%29%3D%5Csum%7Bk%3D1%7D%5E%7BK%7Dpk%281-p_k%29%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7Dpk%5E2%0A&id=fl5Vv)
基于数据D，得到:
2022-06-23-决策树 - 图61%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7Dpk%5E2%0A#card=math&code=Gini%28D%29%3D1-%5Csum%7Bk%3D1%7D%5E%7BK%7Dp_k%5E2%0A&id=VaZLP)
其中,2022-06-23-决策树 - 图62是D中所属第k类的样本子集，K是类的个数.
如果样本集合D根据特征A是否取某一可能取值a被被划分成2022-06-23-决策树 - 图63和2022-06-23-决策树 - 图64两个部分.

2022-06-23-决策树 - 图65%20%5Cin%20D%20%7C%20A(x)%3Da%20%5C%7D%2C%20D-2%3D%20D-D_1%0A#card=math&code=D_1%3D%5C%7B%28x%2Cy%29%20%5Cin%20D%20%7C%20A%28x%29%3Da%20%5C%7D%2C%20D-2%3D%20D-D_1%0A&id=sx3Nb)

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

2022-06-23-决策树 - 图66%3D%5Cfrac%7B%7CD_1%7C%7D%7BD%7DGini(D_1)%2B%5Cfrac%7B%7CD_2%7C%7D%7BD%7DGini(D_2)%0A#card=math&code=Gini%28D%2CA%29%3D%5Cfrac%7B%7CD_1%7C%7D%7BD%7DGini%28D_1%29%2B%5Cfrac%7B%7CD_2%7C%7D%7BD%7DGini%28D_2%29%0A&id=gTOXn)

基尼指数和熵一样，同样表示集合D的不确定性，基尼指数(Gini(D,A))表示根据调教A=a后的集合D的不确定性，基尼指数越大，表示数据D的不确定性越大.

算法:
输入:训练数据D，停止计算的条件
输出:CART决策树

  1. 计算所有特征A的每一个值a对应的条件基尼指数的值，选择最优的划分得到2022-06-23-决策树 - 图67和2022-06-23-决策树 - 图68.
  2. 递归对两个数据集2022-06-23-决策树 - 图69和2022-06-23-决策树 - 图70继续调用1，知道满足条件.
  3. 生成CART树的分类树.
  4. 预测的时候，根据决策树，x落到的叶子节点对应的类别表示这个预测x的类别.

    CART剪枝

    从上面两个算法的不同可以看出，只是在label的设置和决策节点选择的方式不同，整个架构依然是决策树的常用的架构. 而且上面的树的构建过程，都是基于训练数据的经验风险最小化，没有使用带有正则项的结构风险最小化，这样的模型容易发生过拟合，为了不让模型过拟合，我们需要进行模型的剪枝.

CART树的剪枝有很多难点和有意思的地方让我们开慢慢解开这层面纱
CART剪枝算法有两步组成:

  1. 从生成算法产生的决策树2022-06-23-决策树 - 图71底端开始不断剪枝，直到2022-06-23-决策树 - 图72的根节点，形成一个子树序列2022-06-23-决策树 - 图73.
  2. 通过交叉验证的方法在独立的验证数据集上堆子序列进行测试，得到最优子树

损失函数:
2022-06-23-决策树 - 图74%3DC(T)%2B%5Calpha%7CT%7C%0A#card=math&code=C%7B%5Calpha%7D%28T%29%3DC%28T%29%2B%5Calpha%7CT%7C%0A&id=TSHue)
其中，T为任意子树，2022-06-23-决策树 - 图75#card=math&code=C%28T%29&id=PoXkN)是在训练数据上的预测误差，|T|是树的叶子节点的个数,2022-06-23-决策树 - 图76是参数，![](https://g.yuque.com/gr/latex?C%7B%5Calpha%7D(T)#card=math&code=C%7B%5Calpha%7D%28T%29&id=bvlNF)是参数2022-06-23-决策树 - 图77是的子树T的整体的损失，参数2022-06-23-决策树 - 图78是平衡训练数据拟合程度和模型复杂度的权重.
对于固定的2022-06-23-决策树 - 图79,一定存在使损失函数![](https://g.yuque.com/gr/latex?C%7B%5Calpha%7D(T)#card=math&code=C%7B%5Calpha%7D%28T%29&id=w2bkw)最小的子树，将其记作![](https://g.yuque.com/gr/latex?T%7B%5Calpha%7D#card=math&code=T_%7B%5Calpha%7D&id=F6orq). 我们可以理解为每一个2022-06-23-决策树 - 图80都对应一个最有子树和最小损失.

而且已经得到证明，可以用递归的方法对树进行剪枝. 将2022-06-23-决策树 - 图81从小增大，2022-06-23-决策树 - 图82,产生一系列的区间2022-06-23-决策树 - 图83%2Ci%3D0%2C1%2C…%2Cn#card=math&code=%5B%5Calphai%2C%5Calpha%7Bi%2B1%7D%29%2Ci%3D0%2C1%2C…%2Cn&id=b3HRe)；剪枝得到的子树序列对应着区间2022-06-23-决策树 - 图84%2Ci%3D0%2C1%2C…%2Cn#card=math&code=%5Calpha%20%5Cin%20%5B%5Calphai%2C%5Calpha%7Bi%2B1%7D%29%2Ci%3D0%2C1%2C…%2Cn&id=srdE5)的最有子树序列2022-06-23-决策树 - 图85.

我们给出算法:
输入: CART算法生成的决策树T0.
输出: 最优的决策树T{\alpha}

  1. 设k=0, T=2022-06-23-决策树 - 图86.
  2. 设 2022-06-23-决策树 - 图87.
  3. 自下而上地对各个内部节点t计算2022-06-23-决策树 - 图88%2C%7CT_t%7C#card=math&code=C%28T_t%29%2C%7CT_t%7C&id=RGCIz)以及2022-06-23-决策树 - 图89%3D%5Cfrac%7BC(t)-C(T_t)%7D%7B%7CT_t%7C-1%7D%0A#card=math&code=g%28t%29%3D%5Cfrac%7BC%28t%29-C%28T_t%29%7D%7B%7CT_t%7C-1%7D%0A&id=mZ0it) 2022-06-23-决策树 - 图90)%0A#card=math&code=%5Calpha%3Dmin%28%5Calpha%2Cg%28t%29%29%0A&id=xvU4E) 这里，2022-06-23-决策树 - 图91表示以t为根节点的子树，2022-06-23-决策树 - 图92#card=math&code=C%28T_t%29&id=uaInE)是对训练数据的预测误差，2022-06-23-决策树 - 图93是2022-06-23-决策树 - 图94的叶子节点个数.
  4. 自上而下地访问内部节点t，如果有2022-06-23-决策树 - 图95%3D%5Calpha#card=math&code=g%28t%29%3D%5Calpha&id=Ygi1W),进行剪枝，并堆叶节点t以多数表决方法决定其类(分类，回归使用平均值)，得到树T.
  5. 设2022-06-23-决策树 - 图96.
  6. 如果T不是由根节点单独构成的树，则回到步骤4.
  7. 采用交叉验证法在子树序列2022-06-23-决策树 - 图97中选取最优子树2022-06-23-决策树 - 图98.

接下面，我们不去看算法，来看书中给的一段文字的截图，这里截图是因为我要画图，进行比较解释，图中自由理论(哈哈):
image.png

看懂这个图之后，再看算法一气呵成，因为我们假设每一次得到的树都有可能是最优的，所以不能直接去最后一个树，要使用交叉验证选择最有的决策树结构.

总结

决策树用途相当广泛，而且有很多变形，看着简单其实不易，需要看看探索每一个知识点. 目前机器学习，人工智能如此火热，需要进行理论实践学习等多方面的结合方能立于不败之地.