第三讲 分类与回归树
如果一个人必须去选择在很大范围的情形下性能都好的、同时不需要应用开发者付出很多的努力并且易于被终端用户理解的分类技术的话，那么Brieman, Friedman, Olshen和Stone（1984）提出的分类树方法是一个强有力的竞争者。我们将首先讨论这个分类的过程，然后在后续的节中我们将展示这个过程是如何被用来预测连续的因变量。Brieman等人用来实现这些过程的程序被称为分类和回归树（CART）方法。
分类树 在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法；第二个想法是用验证数据进行剪枝。
递归划分 让我们用变量表示因变量（分类变量），用表示自变量。通过递归的方式把关于变量y
pxxx,...,,
21
x的维空间划分为不重叠的矩形。这个划分是以递归方式完成的。首先，一
个自变量被选择，比如和的一个值，比方说选择把维空间为两部分：一部分是
维的超矩形，其中包含的点都满足
p
ixixisisp
−piisx≤，另一个−p维超矩形包含所有的点满足
。接着，这两部分中的一个部分通过选择一个变量和该变量的划分值以相似的方式被划分。这导致了三个矩形区域（从这里往后我们把超矩形都说成矩形）。随着这个过程的持续，我们得到的矩形越来越小。这个想法是把整个
iisx>
x空间划分为矩形，其中的每个小矩形
都尽可能是同构的或“纯”的。“纯”的意思是（矩形）所包含的点都属于同一类。我们认为包含的点都只属于一个类（当然，这不总是可能的，因为经常存在一些属于不同类的点，但这些点的自变量有完全相同的值）。让我们例示递归划分的过程。
例1（Johnson和Wichern） 乘式割草机制造商意欲发现一个把城市中的家庭分成那些愿意购买乘式割草机和不愿意购买的两类的方法。在这个城市的家庭中随机抽取12个拥有者和12个非拥有者的家庭作
为样本。这些数据如表1所示。这里的自变量是收入（）和草地面积（）。类别变量有两个类别：拥有者和非拥有者。 1x2xy
表1 观测点序号 收入（千美元） 草地面积（千平方尺）拥有者＝1，非拥有者＝21 60 18.4 1 2 85.5 16.8 1 3 64.8 21.6 1 4 61.5 20.8 1 5 87 23.6 1
16 110.1 19.2 1 7 108 17.6 1 8 82.8 22.4 1 9 69 20 1 10 93 20.8 1 11 51 22 1 12 81 20 1 13 75 19.6 2 14 52.8 20.8 2 15 64.8 17.2 2 16 43.2 20.4 2 17 84 17.6 2 18 49.2 17.6 2 19 59.4 16 2 20 66 18.4 2 21 47.4 16.4 2 22 33 18.8 2 23 51 14 2 24 63 14.8 2
如果我们用CRAT方法处理这些数据，它将会选择192=x做第一次分割。由组),(21xx 2成的空间现在按分成草地面积了192≤x和两个矩形。如图2所示。 192>x 注意到分裂为两个矩形后的每个矩形比原来分裂之前更同质。上面的矩形包括的点绝大多数是拥有者（9个拥有者，3个非拥有者），而下面的矩形包含绝大多数的非拥有者（9个非拥有者，3个拥有者）。 CART是如何做这个特殊的划分的？它检查每个变量和该变量所有可能用来划分的值来发现最好的划分。对于一个变量来说，可能划分的值是什么？它们是在一对连续的变量值
的中点。对来说可能的划分点是{38.1,45.3,50.1,…,109.5}，对来说{14.4,15.4,16.2,…,23}。这些划分点被按照它们能减少杂质（合成物中的异质，不同成分）的多少来分级。杂质的减少被定义为划分前的矩形的杂质减去划分后两个矩形的杂质之和。有很多方法来让我们度量杂质。我们描述最流行的杂质度量方法：Gini指标。如果我们用
,来表示类，其中，C是对于变量y的类的总数目，矩形A的Gini不纯度可定义为：
1x2xkCk,...,2,1=
∑=−=CkkpAI
121)(
其中，是观测点中属于类的比例。注意到当I(A)=0时，如果所有的观测点属于一个类，且有当所有的类在矩形A中以相同的概率出现时，I(A)被最大化。它的最大值为(C-1)/C。
kpk
下一个划分点是收入变量。图3再一次表示了CART的过程，通过灵活地、75.841=x 3对划分矩形的不同选择来增加划分后的矩形的纯度。左下角的矩形包含满足和的点，其中除了一个是非拥有者之外包含了其他所有的拥有者。右下角的矩形包含满足和的点，包含了被排除的两个拥有者。
75.841≤x
192≤x
75.841>x192≤x
下一次分裂可表示如下： 4 我们能看到递归划分是如何精炼候选的矩形，使之变得更纯的算法过程。最后阶段的递归分析如图5所示。
5注意到现在每个矩形是纯的——所包含的点都是来自这两个类中的某一个。 这个方法被称为分类树算法的原因是每次划分都可以描述为把一个节点分成两个后续节点。第一次分裂表示为树的根节点的分支，如图6所示。
树的前三次划分如图7所示。 整个树如下图8所示。我们用圆来表示带有后续节点的节点。选作划分的变量的名字在圆的下面，在圆中的数是作为划分的点的变量的值。在决策点左侧的数表示在这个决策点的变量的值都小于或等于这个划分的值，在右侧的点的该变量的值大于这个划分的值。这些被称为决策点是因为如果我们用一个树来对新的、仅知道自变量的值的观测样本进行分类时，就是以这样的方式进行的，在每个决策点选择一个正确的分支直到没有后续节点的节点。这种终端的节点被称为树叶。每个叶节点对应一个最终的矩形，x空间被划分，并被描述为一个矩形的节点。当观测点沿着所有到叶节点的路径向下移动时，可将观测点的类别简单地预测为与属于该叶节电的所有训练数据大部分都相同的类别，即采取投票的方式。具有最高选票的类是我们预测新观测点所属的类。在叶节点下面的数表示在训练集中属于这个类的样本占总样本的比例。注意到用CART（称为二叉树）方法得出的树具有如下性质是非常有用的，叶节点的数目刚好比决策点的数目多1。
6 剪枝 在CART过程中第二个关键的思想是用独立的验证数据集对根据训练集生长的树进行剪枝，这的确是一个创新。以前，这个方法基于递归划分的思想构造出来，但他们不得不用规则来阻止树的过分增长和对训练数据的过适应。例如，CHAID(Chi-平方自动交互检测)是一种在CART前几年出现的递归划分的方法，并被广泛用于数据库营销中。它用著名的统计测试（chi-平方独立性检验）通过显著性去评估是否某一节点能提高分类纯度。如果测试不能表明显著提高，那就不进行划分，CART用验证数据对由训练数据过拟和生成的树进行修剪。 在剪枝背后的思想是承认一个很大的树会过拟和训练数据。在我们的例子中，最后几个划分导致矩形中有很少的点（事实上有4个矩形只包含一个点）。我们能直观地看到这些后面的划分可能只是把训练集中的噪声捕捉到，而不是反映在将来数据中可能发生的模式。剪枝包含后续的选择决策点和当叶节点被砍掉时的重新设计。剪枝过程需要在验证数据集中的误分和对被剪枝的树中决策点数目之间进行权衡与折衷，以得到既能反映数据模式又排除了训练数据中噪声的影响。它用一种被称为“成本复杂性”的标准去生成后续的树，该树的成本复杂性比在该节点只有一个根节点的要小（一个树只有一个节点的分类规则是什么？）。我们于是挑选一个最好的树，它对验证数据具有最小的误分。 CART用的成本复杂性标准是分类树的简单误分（基于验证数据的）加上一个对树的大小的惩罚因素。惩罚因素是基于参数的，让我们用α来表示，每个节点的惩罚。成本复杂性标准对于一个树来说就是Err(T)+α|L(T)|，其中Err(T)是验证数据被树误分部分，L(T)是树T
7的叶节点数，α是每个节点惩罚成本：一个从0向上变动的数字。当α＝0对于树有太多的节点是没有惩罚，用成本复杂性标准的是完全生长的没有剪枝的树。当我们增加α到一个很大的值时，对误分的惩罚成本部分淹没在成本复杂性方程中，而得到的最小树是一个简单的带有最少叶子的树，也就是只有一个节点。当我们从0增加α到某一值时，我们首先会遇到一个情形，对一些树T1通过在决策点剪掉子树得到的，和额外增加误分（由于有更少的叶子）而导致的成本与导致的惩罚成本的节约相平衡。我们剪掉在这个节点的子树来修剪整个树，并重新设计这个节点为叶节点。把这时的树称为T1。我们现在对T1重复先前用于整个树的过程，通过进一步增加α的值。持续这种方式，我们产生一些连续的带有节点数目减少的树直到只有一个节点的树。 从这个序列的树，从其中选择一个在验证数据集上具有最小误分的树是一个很自然的。我们把这个树称为最小错误树。 让我们用Boston Housing数据来例示。下面是当用训练数据在树的生长阶段的算法时，XLMiner产生的输出。 表 训练记录
8