算法
$\qquad$ 输入：生成算法产生的整个树 $T$，参数 $\alpha$；
$\qquad$ 输出：修剪后的子树 $T_\alpha$.
$\qquad$ (1) 计算每个结点的经验熵。
$\qquad$ (2) 递归地从树的叶节点向上回缩。
$\qquad\quad$ 设一组叶结点回缩到其父结点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数值分别是 $C_\alpha(T_B)$ 与 $C_\alpha(T_A)$，如果
\[C_\alpha(T_A) \le C_\alpha(T_B)\]$\qquad$则进行剪枝，即将父结点变为新的叶结点。
$\qquad$ (3) 返回(2)，直至不能继续为止，得到损失函数最小的子树 $T_\alpha$.
策略
$\qquad$ 极小化决策树整体的损失函数。设树 $T$ 的叶结点个数为 $|T|$，$t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个，$H_t(T)$ 为叶结点 $t$ 上的经验熵， $\alpha \ge 0$ 位参数，则决策树学习的损失函数定义为
\[C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|\]其中经验熵
\[H_t(T)=-\sum_k \frac{N_{tk}} {N_t}\log \frac{N_{tk}} {N_t}\]
