9.2 树结构模型

9.2.1 背景

树结构的方法将特征变量空间分割成一组方形的区间，然后在每个方形区间上拟合一个简单模型（比如一个常数）。这种方法在概念上非常简单同时也非常强大。本节先介绍树结构回归和分类的一个常用方法，被称为 CART，稍后再与另一个方法 C4.5 做比照。

考虑一个回归问题，其中的输出变量 $Y$、输入变量 $X_1$ 和 $X_2$ 是连续变量，它们都取值在单位区间（$[0,1]$）上。图 9.2 的左上图展示了一组用与坐标轴平行的直线对特征空间的分割。在每个分区中，可用不同的常数来估计 $Y$。然而，这里的困难之处在于：尽管每个分割直线都类似于 $X_1=c$ 很容易写出，但一些所产生的区间描述起来却很复杂。

为了简化问题，只考虑如图 9.2 的右上图所示的递归二分方式的分割。先将输入变量空间分成两个区域，在每个区域上用 $Y$ 的均值作为这个区域的模型估计。通过分割后达到最优拟合的标准来选择分割所用的输入变量和分割点。接下来，将两个区域其中的一个或全部继续进行二分的分割，以此递归下去，直到触及了某种停止规则。例如，在图 9.2 的右上图中，先以 $X_1 = t_1$ 分割。然后将 $X_1 \leq t_1$ 区域以 $X_2 = t_2$ 分割，并将 $X_1 > t_1$ 区域以 $X_1 = t_3$ 分割。最后将 $X_1 > t_3$ 区域以 $X_2 = t_4$ 分割。这个过程最后得到了图中所示的五个区域的分割 $R_1$，$R_2$，……，$R_5$。对应的回归模型用常数 $c_m$ 作为区域 $R_m$ 上对 $Y$ 的预测：

这个模型也可同样地被表达为如图 9.2 的左下图所示的二叉树结构。树的顶点包含了全部的数据。在每个分叉点（junction）处，满足分割条件的观测样本进入左分枝，其它的进入右分枝。树模型的终节点或叶子节点对应着区域 $R_1$，$R_2$，……，$R_5$。图 9.2 的右下图是这个模型的回归曲面的透视图。为方便演示，此图中节点的均值为 $c_1 = -5$，$c_2 = -7$，$c_3 = 0$，$c_4 = 2$，$c_5 = 4$。

递归二叉树的一个重要优点是其可解释性。对特征空间的分割可以完全地用一个树结构来描述。在有多于两个特征时，难以画出如图 9.2 的右上那种分割图，但二叉树的表达方式同样有效。这种表达方式也被医学家经常使用，可能因为它模仿了医生的思维方式。树模型基于患者的特征，将人群划分为输出变量水平高低不同的分层。

9.2.2 回归树

现在回到如何生成回归树的问题上。数据中每个观测样本包括 $p$ 个输入变量和一个输出变量，即 $(x_i,y_i)$，$x_i=(x_{i1},x_{i2},\dots,x_{ip})$，$i=1,2,\dots,N$。算法需要自动地确定分割变量和分割点，以及树模型的拓扑结构（形状）。首先假设有一个 $M$ 个区域的分割 $R_1$，$R_2$，……，$R_M$，并在每个区域上用一个常数 $c_m$ 作为输出变量的模型：

如果采用最小化误差平方和 $\sum(y_i-f(x_i))^2$ 的准则，则易证最优的 $\hat{c}_m$ 即为区域 $R_m$ 上的 $y_i$ 的平均数：

现在需要以最小化误差平方和的标准寻找最优的递归二叉分割，但一般来说这在计算上是不可行的。因此采用一个贪心算法。从所有数据出发，考虑一个分割变量 $j$ 和分割点 $s$，并定义一对区间为：

然后，寻找下面最小化问题解的分割变量 $j$ 和分割点 $s$：

对任意选定的 $j$ 和 $s$，内部的最小化解为：

对每个分割变量，可以很快速地确定最优分割点 $s$，因此通过比较对所有输入变量的最优分割来确定最优的组合 $(j,s)$ 是可行的。

确定了最优分割后，将数据分到两个区域中，并在这两个区域上重复这个分割过程。然后再对得到的分割区域重复此过程。

那么应该生成多大的树模型？一个很大的树模型显然可能会对数据过拟合，而一个小的树模型可能无法捕捉到数据中重要的结构。树模型的大小是决定了模型复杂度的调节参数，应该基于数据自适应地选择最优的树模型大小。一种方法是仅当分割所带来的误差平方和的降低超过某个阈值时，才会对这个树模型节点进行分割。然而这个方法过于短视，因为一个看似无效的分割可能会在后续引出非常好分割。

推荐的方法是先生成一个大的树模型 $T_0$，只在达到了某个最小节点大小（比如 5）之后停止分割过程。然后再用接下来介绍的代价复杂度剪枝（cost-complexity pruning）对这个大树模型进行剪枝。

一个子树 $T\subset T_0$ 定义为任意可通过对 $T_0$ 剪枝产生的树模型，即将其任意数量的内部节点（非终节点）折叠起来。用 $m$ 索引终节点，即节点 $m$ 代表了区域 $R_m$。令 $|T|$ 表示树模型 $T$ 中的终节点个数。并定义：

利用上述的概念，可定义代价复杂度准则为：

接下来的想法是对每个参数值 $\alpha$，寻找最小化 $C_\alpha(T)$ 的子树模型 $T_\alpha \subseteq T_0$。调节参数 $\alpha\geq0$ 控制了树模型大小和其对数据的拟合度之间的权衡。较大 $\alpha$ 取值会产生较小的树模型 $T_\alpha$，相反地较小 $\alpha$ 取值会产生较大的树模型。当 $\alpha=0$ 时，最小化的解也正是整个的树模型 $T_0$，这与符号的下标写法也恰好一致。下面介绍如何自适应地选择 $\alpha$。

可证明对每个 $\alpha$ 都存在最小化 $C_\alpha(T)$ 的唯一最小子树模型 $T_\alpha$。寻找 $T_\alpha$ 中使用了 最弱环节剪枝（weakest link pruning）：将折叠后在节点处带来的 $\sum_m N_m Q_m(T)$ 的增加最小的节点折叠，以此进行这个过程，直到最终达到一个单节点（根节点）的树模型。这会产生一个（有限的）子树模型的序列，可证明 $T_\alpha$ 必然会在这个序列中。更多细节见 Breiman et al. (1984) 或 Ripley (1996)。最后通过五折或十折交叉验证来估计 $\alpha$：选择最小化交叉验证误差平方和的值 $\hat{\alpha}$。最终得到的树模型即为 $T_\hat{\alpha}$。

9.2.3 分类树

如果目标是预测取值在 $1,2,\dots,K$ 中的分类输出变量，则只需要改变树模型算法中分割节点和树模型剪枝的准则。在回归问题中使用的节点不纯度（impurity）是表达式 9.15 定义的平方误差，但这并不适用于分类问题。一个节点 $m$ 代表了一个区域 $R_m$ 和其中的 $N_m$ 个观测样本，将节点 $m$ 中类别 $k$ 的观测样本比例记为：

可以将节点 $m$ 中的观测样本分类为节点中的最多数类型 $k(m)=\arg\max_k\hat{p}_{mk}$。以下为几个节点不纯度的不同度量 $Q_m(T)$：误分类误差率（misclassification error）、基尼系数（Gini index）、和交叉熵（cross-entropy）或偏差（deviance）。

在二分类场景中，若 $p$ 为第二个类别所占的比例，则这三个度量分别为 $1-\max(p,1-p)$、$2p(1-p)$、和 $-p\log p-(1-p)\log(1-p)$。图 9.3 展示了这三个函数曲线。三者形状相似，但交叉熵和基尼系数是可微函数，因此更方便使用于数值求解最优化的过程。通过比较式 9.13 和式 9.15，可见还需要对由节点 $m$ 分割出的两个子节点的不纯度度量。按照其样本数量 $N_{m_L}$ 和 $N_{m_R}$ 赋予权重。

此外，交叉熵和基尼系数比误分类误差率对节点中概率的变动更敏感。例如一个两个类别的问题，每个类别各有 400 个观测样本（记为 $(400,400)$），假设有一个分割产生的子节点为 $(300,100)$ 和 $(100,300)$，而另一个分割产生的子节点为 $(200,400)$ 和 $(200,0)$。两个分割所产生的误分类误差率都是 $0.25$，但是第二个分割会得到一个单类别的节点，可能是更好的方案。第二个分割的基尼系数和交叉熵都会小于第一个。因此，在生成树模型时可以使用基尼系数或交叉熵度量。三个度量都可以用于指引代价复杂度剪枝，但通常使用的是误分类率。

有两种方式来理解基尼系数。可以不再用节点中最多数类别来对其中的样本分类，而是以 $\hat{p}_{mk}$ 的概率分类于类别 k。那么这个分类规则下节点的训练误差率为 $\sum_{k\ne k’}\hat{p}_{mk}\hat{p}_{mk’}$，也就是基尼系数。相似地，如果将类别 k 的样本编码为 1，其他的样本编码为 0，则这个 0-1 输出变量在这个节点上的方差为 $\hat{p}_{mk}(1-\hat{p}_{mk})$。将 $k$ 个类别的类似方差求和后同样可得到基尼系数。

9.2.4 其他问题

分类自变量

当对有 $q$ 个无序的可能取值的自变量分割时，共有 $2^{q-1}-1$ 个将 $q$ 个取值分成两组的可能分割方法，并且在 $q$ 较大时会带来无法承受的计算量。然而，这个计算在输出变量为 0-1 时可以被简化。将自变量类别按照其对应的样本中输出变量的类别 1 比例排序。然后以此将这个自变量像一个有序自变量进行分割。这证明这个方法会得出所有 $2^{q-1}-1$ 个可能分割中交叉熵或基尼系数意义上的最优分割。这个结论在数量输出变量和平方误差损失的问题中也成立，此时将自变量类别按照其对应的样本中输出变量的均值递增排序。尽管这个结论符合直觉的思路，但严格的证明并不简单。二分类输出变量的证明可见 Breiman et al. (1984) 和 Ripley (1996)；数量输出变量的证明可见 Fisher (1958)。对多类型的输出变量，类似的简化不再可行，但存在多种近似的方法（Loh and Vanichsetakul, 1988）。

分割的算法倾向于选择取值个数 $q$ 较多的分类自变量；可能的分割数量随 $q$ 以指数级增加，分割的选择越多，就越可能找到一个很好的拟合现有数据的分割。如果 $q$ 非常大，这可能会导致严重的过拟合，因此应该避免使用这样的自变量。

损失矩阵

在分类问题中，对某些类别的样本误分类所产生的后果会比其他类别更加严重。例如，预测一个实际可能有心脏病发作风险你的人不会有风险，要比反之的后果更严重。考虑到这个情况，定义一个 $K\times K$ 的损失矩阵 $\mathbf{L}$，其中的元素 $L_{kk’}$ 为将一个实际类别 $k$ 的样本分类为 $k’$ 的损失。通常正确的分类不会产生损失，即 $L_{kk}=0$， $\forall k$。要在模型拟合过程中纳入这个损失，可以将基尼系数修改为 $\sum_{k\ne k’}L_{kk’}\hat{p}_{mk}\hat{p}_{mk’}$；这可理解为是随机规则产生的期望损失。这个做法可用于多类别的场景中，但在两个类别的场景中并没有作用，因为 $\hat{p}_{mk}\hat{p}_{mk’}$ 项的系数为 $L_{kk’}+L_{k’k}$。在两个类型的场景中可用一个更好的方法，将类别 $k$ 的观测样本赋予权重 $L_{kk’}$。当 $L_{kk’}$ 作为 $k$ 的一个函数不依赖于 $k’$ 时，这个方法也可用于多类别的场景中。样本加权也可用在偏差（或交叉熵）中。样本加权的作用是改变了类别的先验概率分布。按照经验贝叶斯规则（empirical Bayes rule），终节点的分类为 $k(m)=\arg\min_k\sum_\ell L_{k\ell}\hat{p}_{m\ell}$。

自变量的缺失值

假设数据中在一些或所有自变量中存在缺失值。可能的处理方法是放弃存在缺失值的观测样本，但这可能会导致训练样本的大幅减少。另一个方法是试图用比如该自变量无缺失样本的均值来填补（impute）缺失值。对于树结构模型，有两个更好的处理方法。

第一个方法适用于分类自变量：简单地将“缺失”作为一个新的类别。据此可能会发现一些自变量上有缺失值的样本可能与无缺失值的样本表现存在差异。

第二个更一般性的方法是构建替代（surrogate）变量。在考察用于分割的自变量时，只使用该自变量上没有缺失值的观测样本。在选好了最优的（首要）分割自变量和分割点后，再构建一组替代自变量和分割点。第一个替代是可以最好地模拟出由首要分割得到的训练集划分的分割自变量和分割点。第二个替代是可以第二好地模拟出首要分割的分割自变量和分割点，以此类推。在模型训练或预测中，如果首要分割自变量存在缺失，则可以按次序使用替代分割来对观测样本进行分割。替代分割利用自变量之间的相关性来减轻缺失数据的影响。有缺失的自变量与其他自变量之间的相关性越高，缺失值带来的信息损失就越小。第 9.6 节讨论了更一般性的数据缺失问题。

为什么用二叉分割？

上文中的分割是将每个节点只分成两组，然而可以考虑将节点分成大于两组。虽然这样做可能在一些问题中有帮助，但一般来说这不是一个好的做法。多组的分割可能会带来过快的使数据碎片化的问题，这会使在对其子节点的分割中数据不足。因此只会在真正需要的问题中才使用多组的分割。另外由于可通过一系列的二叉分割来实现多组分割，所以建议使用二叉分割。

其他的树模型生成过程

上述的讨论集中于树模型的 CART（classification and regression tree）实现。另一个常见的方法是 ID3 以及其后续版本 C4.5 和 C5.0（Quinlan, 1993）。这个方法早期的版本限制于分类自变量，使用自上而下的规则而且没有剪枝。经过近期的发展，C5.0 已经变成了与 CART 很相似的方法。C5.0 的最重要的独特之处在于其导出规则集的机制。在生成了一个树模型后，有时可以简化定义了终节点的分割规则：即去除一个或多个条件后不会改变进入到这个节点的观测样本子集。这样会得到一个定义了每个终节点的简化规则集；这些规则不再形成一个树结构，但它们的简约性可能在一些问题中更具有吸引力。

线性组合分割

除将分割限制为 $X_j\leq s$ 的形式外，也可以包含沿着线性组合进行分割 $\sum a_jX_j\leq s$。通过最小化相关的准则（比如基尼系数）来选择最优的权重 $a_j$ 和 分割点 $s$。尽管这样可能会改进树模型的预测能力，但也降低了可解释性。从计算的角度，分割点的离散性阻碍了在权重上的平滑优化。第 9.5 节会介绍一个包含线性组合分割的更好方法，层级混合专家模型（hierarchical mixtures of experts，HME）。

树模型的不稳定性

树模型的一个主要问题是它们的方差高。通常数据中一个小的改动可能会导致树模型中一系列不同的分割，这使得模型的解释力不可信。这个不稳定性的主要来自于这个过程的分层结构：上层分割中的误差的作用会不断地向其下面的节点分割传播。虽然可通过使用更稳定的分割准则从某种程度上缓解这个问题，但并没有消除其内在的不稳定。这也是使用简单的树结构模型拟合数据的代价。自助聚合（第 8.7 节）可通过对很多树模型取平均而降低这个方差。

平滑性不足

树模型的另一个不足是其预测曲面缺乏平滑性，如图 9.2 的右下图所示。在 0-1 损失的分类问题中，这没有太多影响，因为在类别概率估计中的误差的影响有限。然而在回归问题中这可能会影响模型的表现，因为在正常情况下会默认潜在的函数是平滑的，第 9.4 节介绍的 MARS 过程可视为为减轻平滑性不足而对 CART 方法的一个改进。

难以捕捉加性结构

树模型的另一个问题是难以对加性结构建模。例如一个问题中假设 $Y=c_1I(X_1<t_1)+c_2I(X_2<t_2)+\varepsilon$，其中的 $\varepsilon$ 是零均值噪声。那么二叉树可能会先基于 $X_1$ 在 $t_1$ 附近进行分割。要想重现这个加性结构，在下一层级的两个节点处都要基于 $X_2$ 在 $t_2$ 处分割。当有足够的数据时，这可能会实现，不过模型不会对这样的结构有特殊的偏好。如果不是两个而是有十个加性项，可能需要很多巧合的分割才能重现加性结构，而且分析人员很难从树模型估计中意识到其中的加性结构。仍然可将其原因归咎于二叉树模型的结构，它既有优点也有缺点。同样 MARS 方法（第 9.4 节）为了捕捉加性的结构，不再使用这种树模型结构。

9.2.5 垃圾邮件例子（续）

下面在之前介绍的“垃圾邮件”例子中应用分类树方法。在生成树模型中使用了偏差（交叉熵），在剪枝中使用了误分类错误率。图 9.4 展示了作为剪枝树模型大小的函数的十折交叉验证误差率，以及由十个交叉验证样本得出的均值上下 $\pm 1$ 标准误差¹。测试误差率曲线为图中橙色曲线。注意交叉验证误差率实际上依赖于一系列 $\alpha$ 取值而不是树模型的大小；因为不同“折”中一个 $\alpha$ 取值可能对应了不同的树模型大小。图中底部的树模型大小指的是 $|T_\alpha|$，即对原始的树模型剪枝后的大小。

误差率曲线在大概 17 个终节点之后基本平缓，因此最终的剪枝树模型如图 9.5 所示。树模型所选用的 13 个不同特征变量中，有 11 个也属于加性模型中的 16 个显著特征变量（表 9.2）。表 9.3 中所示的总体误差率比表 9.1 中的加性模型大约高 50%。

表 9.3：垃圾邮件数据：17 个终节点树模型（由交叉验证选出）在测试集上的混淆（confusion）矩阵。总体误差率为 9.3%。

考虑树模型最右边的一枝。如果邮件中超过 5.5% 的符号都是 $ 符号，那么这个邮件被划分到右枝，疑似为“垃圾邮件”。然而，如果此外词组“hp”频繁地出现，那么这很可能是公务内容，因而分类为“正常邮件”。测试集中有 22 个满足这些条件的案例，全部都被正确地分类。如果不满足第二个条件，并且连续大写字母的平均长度 CAPAVE 大于 2.9，则分类为“垃圾邮件”。在 277 个测试集内如此的案例中，只有 7 个被误分类。

在医学的分类问题中，用两个术语 灵敏度（sensitivity）和特异度（specificity），定义如下：

• 灵敏度：真实状态为疾病而预测为疾病的概率。
• 特异度：真实状态为无疾病而预测为无疾病的概率。

若将“垃圾邮件”和“正常邮件”分别视为存在疾病和没有疾病，那么从表 9.3 可得：

在这个分析中使用的是相等的损失。与之前一样令 $L_{kk’}$ 为将一个实际类别 $k$ 的样本分类为 $k’$ 的损失。通过调整损失 $L_{01}$ 和 $L_{10}$ 的相对大小，可以增加规则的灵敏度并降低特异度，或者相反。在这个例子中，更希望避免将“正常邮件”分类为“垃圾邮件”，因此想要将灵敏度调整到较高水平。这可以通过设置 $L_{10}=1$ 和 $L_{01}>1$ 来实现。根据贝叶斯规则，如果一个终节点中“垃圾邮件”的比例大于 $L_{01}/(L_{10}+L_{01})$，则将该终节点分类为 1（“垃圾邮件”），否则分类为 0。

接收者操作特征曲线（receiver operating characteristic，ROC）曲线是一个评估敏感度和特异度之间权衡的常用汇总工具。它是随这分类规则参数的改变，灵敏度对特异度的曲线图。让损失 $L_{01}$ 在 $0.1$ 和 $10$ 之间变化，应用在图 9.4 中选中的 17 个终节点的树模型上，则得到了图 9.6 中的 ROC 曲线。在 0.9 附近每个曲线的标准误差大约为 $0.9(1-0.9)/1536=0.008$，因此差别的标注误差大约为 0.01。图中可见若想达到接近 100% 的灵敏度，需要将特异度降低至大约 50%。这个曲线下方的面积是一个经常使用的量化汇总统计；将曲线线性地向两边方向延伸，使其在 $[0,100]$ 区间上有定义，那么这个面积大约为 0.95。作为对比，图中包含了 GAM 模型在这些数据上拟合结果的 ROC 曲线；对任意损失它都给出了更好的分类规则，其曲线下面积为 0.98。

相比只修改节点中的贝叶斯规则，一个更好的方法是在生成树模型时全面地考虑进不等损失的影响，如同上一小节所述。在只有两个类别 0 和 1 时，可通过将类别 $k$ 的观测样本赋予权重 $L_{k,(1-k)}$从而实现在生成树模型的过程中纳入不同损失的作用。在这里选择了 $L_{01}=5$ 和 $L_{10}=1$，并用和之前同样大小（$|T_\alpha|=17$）的树模型进行拟合。这个树模型在高特异度下有比原始树模型更高的灵敏度，但在另一端的表现更差。它的几个最上层的分割与原始的树模型是一样的，然后两者产生了差异。对于这个应用来说，用 $L_{01}=5$ 生成的树模型明显比原始的树模型更好。

上文中使用的 ROC 曲线下的面积，有时也被称为 c 统计量（c-statistic）。有趣的是可证明 ROC 曲线下的面积等价于两组之间的预测分数差异中位数的曼-惠特尼（Man-Whitney）U 统计量，或威尔科克森秩和（Wilcoxon rank-sum）检验（Hanley and McNeil, 1082）。c 统计量并不是衡量一个额外自变量加入到标准模型后带来的贡献的有效度量。新的自变量可能会很显著地改变模型的偏差（交叉熵），但只会带来很小的 c 统计量增加。例如，将表 9.2 的模型中的非常显著的变量 george 去除后，只带来不到 0.01 的 c 统计量下降。然而，它可用于考察额外的自变量如何改变了一个个体样本的分类。关于这个问题更深入的讨论见 Cook (2007)。

本节练习

练习 9.5

树模型的自由度

Given data yi with mean f (xi ) and variance σ 2 , and a fitting operation y → ŷ, let’s define the degrees of freedom of a fit by i cov(yi , ŷi )/σ 2 .

Consider a fit ŷ estimated by a regression tree, fit to a set of predictors X1 , X2 , . . . , Xp .

1. In terms of the number of terminal nodes m, give a rough formula for the degrees of freedom of the fit.
2. Generate 100 observations with predictors X1 , X2 , . . . , X10 as independent standard Gaussian variates and fix these values.
3. Generate response values also as standard Gaussian (σ 2 = 1), indepen- dent of the predictors. Fit regression trees to the data of fixed size 1,5 and 10 terminal nodes and hence estimate the degrees of freedom of each fit. [Do ten simulations of the response and average the results, to get a good estimate of degrees of freedom.]
4. Compare your estimates of degrees of freedom in (a) and (c) and discuss.
5. If the regression tree fit were a linear operation, we could write ŷ = Sy for some matrix S. Then the degrees of freedom would be tr(S). Suggest a way to compute an approximate S matrix for a regression tree, compute it and compare the resulting degrees of freedom to those in (a) and (c).