决策树

决策树（decision tree）是一种基本的分类与回归方法。决策树模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。
学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类。
决策树学习通常包括3个过程：特征选择、决策树的生成、决策树的修剪。

决策树模型与学习

决策树模型

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

决策树学习

决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型，基于特征空间划分的类的条件概率模型有无穷多个，选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习用损失函数表示这一目标，决策树学习的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定后，学习问题就变为在损失函数意义下选择最优决策树的问题。从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优问题，得到的决策树是次优的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

在决策树的基本算法中，有三种情形会导致递归返回：

1. 当前节点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。此时，我们把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别；
3. 当前节点包含的样本集合为空，不能划分。我们同样把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。

上述方法生成的决策树可能对训练数据有很好的划分能力，但对未知的测试数据却未必有很好的划分能力，即可能发生过拟合现象。这时需要对已生成的决策树自下而上进行剪枝，将树变得简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶节点，使其回退到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，留下对训练数据有足够分类能力的特征。
决策树的生成对应模型的局部选择，决策树的剪枝则考虑全局最优。

特征选择

决策树学习的关键是如何选择最优的划分属性，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

纯度

我们定义非纯度 $IM(ImpurityMeasure)$ 作为衡量度量类别划分优劣的标准，$IM$ 定义应该满足以下两点：
$IM$ 最大时，当前的划分应使所有数据占各类别的比例相等：
$p = \frac {1} {number\;of\;classes}$
$IM$ 最小时为 0，当前的划分使所有数据都是相同类，这也是我们的期望目标。
$IM$ 在不同的算法中有着不同的度量方式，较为典型的就是熵度量和基尼度量。以下信息增益(越大越好)和信息增益比(越大越好)为熵度量，基尼指数(越小越好)为基尼度量。

信息增益

首先给出熵和条件熵的定义。
在信息论和概率统计中，熵（entropy）是表示随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为

$$P(X=x_i) = p_i, \quad i=1,2,\cdots,n$$

则随机变量$X$的熵定义为

$$H(X) = - \sum_{i=1}^n p_i \log p_i$$

在上式中，若$p_i = 0$，则定义$0 \log 0 = 0$。通常，上式中的对数以2为底或以e为底，这时熵的单位分别称为比特（bit）或纳特（nat）。由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵记作$H(p)$，即

$$H(p) = - \sum_{i=1}^n p_i \log p_i$$

熵越大，随机变量的不确定性就越大，从定义可验证

$$0 \leq H(p) \leq \log n$$

当随机变量只取两个值，例如1，0时，即$X$的分布为

$$P(X=1)=p, \quad P(X=0)=1-p, \quad 0 \leq p \leq 1$$

熵为

$$H(p) = -p \log_2 p - (1-p) \log_2 (1-p)$$

这时，熵$H(p)$随概率$p$变化的曲线如下图所示（单位为比特）：

当$p=0$或$p=1$时$H(p)=0$，随机变量完全没有不确定性，当$p=0.5$时，$H(p)=1$，熵取值最大，随机变量不确定性最大。
设有随机变量$(X,Y)$，其联合概率分布为

$$P(X=x_i,Y=y_i) = p_{ij}, \quad i=1,2,\cdots,n; \quad j=1,2,\cdots,m$$

条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。随机变量$X$给定的条件下随机变量$Y$的条件熵（conditional entropy）$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望

$$H(Y|X) = \sum_{i=1}^n p_i H(Y|X=x_i)$$

其中$p_i = P(X=x_i), \quad i = 1,2,\cdots,n$。
当熵和条件熵的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。如果有0概率，令$0 \log 0 = 0$。
信息增益（information gain）表示得到特征$X$的信息而使得类$Y$的信息不确定性减少的程度。
信息增益：特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即

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

通常，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征。给定训练数据集$D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性。而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性。它们的差为信息增益，表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。显然，对于数据集$D$而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法：对训练数据集（或子集）$D$，计算其每个特征的信息增益，比较它们的大小，选择信息增益最大的特征。
信息增益的算法：
输入：训练数据集$D$和特征$A$；
输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$。
（1）计算数据集$D$的经验熵$H(D)$

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

（2）计算特征$A$对数据集$D$的经验条件熵$H(D|A)$

$$H(D|A)= \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) = - \sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$$

（3）计算信息增益

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

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正，这也是特征选择的另一准则。
信息增益比：特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即

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

其中，$HA(D) = -\sum{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$，$n$是特征$A$取值的个数。

基尼指数

基尼指数：分类问题中，假设有$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_{i=1}^K (\frac{|C_k|}{|D|})^2$$

上式中，$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数。
如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，即

$$D_1 = \{(x,y) \in D | A(x) = a \}, \quad D_2 = D - D_1$$

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

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

基尼指数$Gini(D)$表示集合$D$的不确定性，基尼指数$Gini(D,A)$表示经$A=a$分割后集合$D$的不确定性。基尼指数越大，样本集合的不确定性也就越大，这一点与熵相似。
下图显示二类问题中基尼指数$Gini(p)$、熵（单位比特）之半$\frac{1}{2}H(p)$和分类误差率的关系。横坐标表示概率$p$，纵坐标表示损失。

决策树剪枝

决策树生成算法递归地产生决策树，这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没那么准确，即出现了过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决此问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
在决策树学习中将已生成的树进行简化的过程成为剪枝（pruning）。剪枝从已生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶节点，建华分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树$T$的叶节点个数为$|T|$，$t$是树$T$的叶节点，该叶节点有$Nt$个样本点，其中$k$类的样本点有$N{tk}$个，$k=1,2,\cdots,K$，$H_t(T)$为叶节点$t$上的经验熵，$\alpha \geq 0$为参数，则决策树学习的损失函数可以定义为

$$C_\alpha (T) = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T|$$

其中经验熵为

$$H_t(T) = - \sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$$

损失函数中，有段第一项记为

$$C(T) = \sum_{t=1}^{|T|} N_t H_t(T) = - \sum_{t=1}^{|T|} \sum_{k=1}^K N_{tk} \log \frac{N_{tk}}{N_t}$$

此时损失函数可写为

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

上式中，$C(T)$表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，$|T|$表示模型复杂度，参数$\alpha \geq 0$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型，较小的$\alpha$促使选择较复杂的模型。$\alpha = 0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。
当$\alpha$值确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度就越高；相反，子树越小，模型的复杂度就越低，但是往往与训练数据的拟合不好。损失函数正好表示对两者的平衡。
决策树生成只考虑了通过提高信息增益（信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型的复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

公式（5.15）只需考虑两个树的损失函数的差，其计算可以在局部进行。所以，决策树的剪枝算法可以有一种动态规划的算法实现。
周志华的《机器学习》一书中对于决策树剪枝策略的介绍分为预剪枝和后剪枝。预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶节点进行考察，若该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。其中泛化能力是用验证集上的准确度进行估计。

连续值与缺失值

连续值处理

现实学习任务中常会遇到连续属性，由于连续属性的可取值数目不在有限，因此，不能直接根据连续属性的可取值来对节点进行划分，此时需要借助连续属性离散化技术。最简单的策略是采用二分法对连续属性进行处理，这也是C4.5决策树算法中采用的机制。
给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序，记为${a^1, a^2, \cdots, a^n}$。基于划分点$t$可将$D$分为子集$D_t^-$和$D_t^+$，其中$D_t^-$包含那些在属性$a$上取值不大于$t$的样本，而$D_t^+$则包含那些在属性$a$上取值大于$t$的样本。显然，对相邻的属性取值$a^i$与$a^{i+1}$来说，$t$在区间$[a^i,a^{i+1})$中取任意值所产生的划分结果相同。因此，对连续属性$a$，可考察包含$n-1$个元素的候选划分点集合

$$T_a = \{ \frac{a^i + a^{i+1}}{2} | 1 \leq i \leq n-1\}$$

即把区间$[a^i,a^{i+1})$的中位点$\frac{a^i + a^{i+1}}{2}$作为候选划分点。然后就可以像离散属性值一样考察这些划分点，选取最优的划分点进行样本集合的划分：

$$\begin{align} Gain(D,a) &= \max_{t \in T_a} Gain(D,a,t) \nonumber \\ &= \max_{t \in T_a} (H(D) - \sum_{\lambda \in \{-,+\}} \frac{|D_t^\lambda|}{|D|} H(D_t^\lambda)) \nonumber \end{align}$$

其中$Gain(D,a,t)$是样本集$D$基于划分点$t$二分后的信息增益，于是就选择使$Gain(D,a,t)$最大化的划分点。
注意：与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性。例如，在西瓜问题中，在父节点使用了“密度$\leq 0.381$”，在子节点上仍然可以使用“密度$\leq 0.294$”。

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失，尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。如果简单地放弃不完整样本，仅使用无缺失值的样本进行学习，显然是对数据信息的极大浪费。
在面对缺失值问题时，我们需要解决两个问题：

1. 如何在属性值缺失的情况下进行划分属性选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集$D$和属性$a$，令$\tilde{D}$表示$D$中在属性$a$上没有缺失值的样本子集。
问题（1）：假定属性$a$有$V$个可取值${a^1, a^2, \cdots, a^V}$，令$\tilde{D}^v$表示$\tilde{D}$中在属性$a$上取值为$a^v$的样本子集，$\tilde{D}k$表示$\tilde{D}$中属于第$k$类（$k=1,2,\cdots,|\gamma|$）的样本子集，显然有$\tilde{D} = \cup{k=1}^{|\gamma|} \tilde{D}k$，$\tilde{D} = \cup{v=1}^V \tilde{D}^v$，假定为每个样本赋予一个权重$w_{\pmb{x}}$，并定义

$$\begin{align} \rho &= \frac{\sum_{\pmb{x} \in \tilde{D}} w_{\pmb{x}}}{\sum_{\pmb{x} \in D} w_{\pmb{x}}} \nonumber \\ \tilde{p}_k &= \frac{\sum_{\pmb{x} \in \tilde{D}_k} w_{\pmb{x}}}{\sum_{\pmb{x} \in \tilde{D}} w_{\pmb{x}}} \quad (1 \leq k \leq |\gamma|) \nonumber \\ \tilde{r}_v &= \frac{\sum_{\pmb{x} \in \tilde{D}^v} w_{\pmb{x}}}{\sum_{\pmb{x} \in \tilde{D}} w_{\pmb{x}}} \quad (1 \leq v \leq V) \nonumber \end{align}$$

直观地看，对属性$a$，$\rho$表示无缺失值样本所占的比例，$\tilde{p}k$表示无缺失值样本中第$k$类所占的比例，$\tilde{r}_v$表示无缺失值样本中在属性$a$上取值为$a^v$的样本所占的比例，显然有$\sum{k=1}^{|\gamma|} \tilde{p}k = 1, \sum{v=1}^V \tilde{r}_v = 1$。
基于上述定义，可将信息增益的计算式推广为

$$\begin{align} Gain(D,a) &= \rho \times Gain(\tilde{D},a) \nonumber \\ &= \rho \times (H(\tilde{D}) - \sum_{v=1}^V \tilde{r}_v H(\tilde{D}^v)) \nonumber \end{align}$$

其中

$$H(\tilde{D}) = - \sum_{k=1}^{|\gamma|} \tilde{p}_k \log_2 \tilde{p}_k$$

问题（2）：若样本$\pmb{x}$在划分属性$a$上的取值已知，则将$\pmb{x}$划分入与其取值对应的子节点，且样本权值在子节点中保持为$w{\pmb{x}}$。若样本$\pmb{x}$在划分属性$a$上的取值未知，则将$\pmb{x}$同时划入所有子节点，且样本权值在与属性值$a^v$对应的子节点中调整为$\tilde{r}_v · w{\pmb{x}}$。直观来看，就是让同一样本以不同的概率划入到不同的子节点中。
C4.5算法就是使用的上述解决方案。

ID3和C4.5算法实现

ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。

C4.5算法

C4.5算法与ID3算法相似，只是在生成过程中，用信息增益比来选择特征。

CART算法

分类与回归树（classification and regression tree，CART）是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。
CART是在给定输入随机变量$X$条件下输出随机变量$Y$的条件概率分布的学习方法。CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法分为两步：

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

CART生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则。

回归树

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

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

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为$M$个单元$R_1,R_2,\cdots,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可表示为

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

当输出空间的划分确定时，可以用平方误差$\sum_{x_i \in R_m} (y_i - f(x_i))^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元$R_m$上的$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_1(j,s) = \{x|x^{(j)} \leq s \} \quad R_2(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]$$

对固定输入变量$j$可以找到最优切分点$s$。

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

遍历所有输入变量，找到最优切分变量$j$，构成一个对$(j,s)$，依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样生成的回归树通常称为最小二乘回归树（least squares regression tree）。

分类树

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

CART剪枝

CART剪枝算法从“完全生长”的决策树的底端减去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：

• 从生成算法产生的决策树$T_0$底端开始剪枝，直到$T_0$的根节点，形成一个子树序列${T_0,T_1,\cdots,T_n}$；
• 通过交叉验证法在独立的验证集上对子序列进行测试，从中选择最优子树。

（1）剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数：

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

其中，$T$为任意子树，$C(T)$为对训练数据的预测误差（如基尼指数），$|T|$为子树的叶节点个数，$\alpha \geq 0$为参数，$C\alpha (T)$为参数是$\alpha$的子树$T$的整体损失，参数$\alpha$权衡训练数据的拟合程度与模型的复杂度。
对于固定的$\alpha$，一定存在是损失函数$C\alpha (T)$最小的子树，将其表示为$T\alpha$。$T\alpha$在损失函数$C\alpha (T)$最小的意义下是最优的。这样的最优子树是唯一的，当$\alpha$较大时，最优子树$T\alpha$偏小；当$\alpha$较小时，最优子树$T\alpha$偏大。极端情况，当$\alpha = 0$时，整体树是最优的，当$\alpha \to \infty$时，根节点组成的单节点树是最优的。
可以用递归的方法对树进行剪枝。将$\alpha$从小增大，$0 < \alpha_1 < \cdots < \alpha_n < + \infty$,产生一系列的区间$[\alpha_i, \alpha{i+1}), i=0,1,\cdots, n$；剪枝得到的子树序列对应着区间$ \alpha \in [\alphai, \alpha{i+1}), \quad i=0,1,\cdots, n$的最优子树序列${T_0,T_1,\cdots,T_n}$，序列中的子树是嵌套的。
具体地，从整体树$T_0$开始剪枝。对$T_0$的任意内部节点$t$，以$t$为单节点树的损失函数是

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

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

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

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

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

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

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

当$\alpha$再增大时，不等式反向。只要$\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}$$

上式表示剪枝后整体损失函数减小的程度。在$T0$中剪去$g(t)$最小的$T_t$，将得到的子树作为$T_1$，同时将最小的$g(t)$设为$\alpha_1$。$T_1$为区间$[\alpha_1,\alpha_2)$的最优子树。
如此剪枝下去，直至得到根节点。在这一过程中，不断地增加$\alpha$的值，产生新的区间。
（2）在剪枝得到的子树序列$T_0,T_1,\cdots,T_n$中通过交叉验证选取最优子树$T\alpha$
具体地，利用独立的验证数据集，测试子树序列$T0,T_1,\cdots,T_n$中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树$T_0,T_1,\cdots,T_n$都对应于一个参数$\alpha_1, \alpha_2, \cdots, \alpha_n$。所以，当最优子树$T_k$确定时，对应的$\alpha_k$也确定了，即得到最优决策树$T\alpha$。

多变量决策树

如果把每个属性视为坐标空间中的一个坐标轴，则$d$个属性描述的样本就对应了$d$维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但在学习任务的真实分类边界较为复杂时，必须使用很多段划分才能获得较好的近似，决策树也会相当复杂，由于要进行大量的属性测试，预测时间开销也会很大。

若能使用斜的划分边界，则决策树模型将大为简化。“多变量决策树”（multivariable decision tree）就能实现这样的斜划分甚至更为复杂划分的决策树。
以实现斜划分的多变量决策树为例，在此类决策树中，非叶节点不再是仅对某个属性，而是对属性的线性组合进行测试：每个非叶节点是一个形如$\sum_{i=1}^d w_i a_i = t$的线性分类器，其中$w_i$是属性$a_i$的权重，$w_i$和$t$可在该节点所含的样本集合属性集上学得。与传统的“单变量决策树”不同，在多变量决策树的学习过程中，不是为每个非叶节点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。