摘 要：本实验的目的是学习和掌握分类回归树算法。CART提供一种通用的树生长框架，它可以实例化为各种各样不同的判定树。CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的决策树的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。在MATLAB平台上编写程序，较好地实现了非剪枝完全二叉树的创建、应用以及近似剪枝操作，同时把算法推广到多叉树。
一、技术论述
1.非度量方法
在之前研究的多种模式分类算法中，经常会使用到样本或向量之间距离度量(distance metric)的方法。最典型的是最近邻分类器，距离的概念是这个分类方法的根本思想所在。在神经网络中，如果两个输入向量足够相似，则它们的输出也很相似。总的来说，大多数的模式识别方法在研究这类问题中，由于特征向量是实数数据，因此自然拥有距离的概念。
而在现实世界中，另外一类酚类问题中使用的是“语义数据”(nominal data)，又称为“标称数据”或“名义数据”。这些数据往往是离散的，其中没有任何相似性的概念，甚至没有次序的关系。以下给出一个简单的例子：
试用牙齿的信息对鱼和海洋哺乳动物分类。一些鱼的牙齿细小而精致（如巨大的须鲸），这种牙齿用于在海里筛滤出微小的浮游生物来吃；另一些有成排的牙齿（如鲨鱼）；一些海洋动物，如海象，有很长的牙齿；而另外一些，如鱿鱼，则根本没有牙齿。这里并没有一个清楚的概念来表示关于牙齿的相似性或距离度量，打个比方，须鲸和海象的牙齿之间并不比鲨鱼和鱿鱼之间更相似。本实验的目的是将以往以实向量形式表示的模式，转变成以非度量(nonmetric)的语义属性来表示的模式。
2.判定树
利用一系列的查询回答来判断和分类某模式是一种很自然和直观的做法。有一个问题的提法依赖于前一个问题的回答。这种“问卷表”方式的做法对非度量数据特别有效，因为回答问题时的是“是/否”、“真/假”、“属性值”等并不涉及任何距离测度概念。这些实际问题可以用有向的判定树(decision tree)的形式表示。从结构上看，一棵树的第一个节点又称为根节点，存在于最上方，与其他节点通过分支实现有序的相连。继续上述的构造过程，知道没有后续的叶节点为止，下图给出了一个判定树的实例。
从根节点开始，对模式的某一属性的取值提问。与根节点相连的不同分支，对应这个属性的不同取值，根据不同的结果转向响应的后续子节点。这里需要注意的是树的各分支之间必须是互斥的，且各分支覆盖了整个可能的取值空间。
在把当前到达的节点视为新的根节点，做同样的分支判断。不断继续这一过程直至到达叶节点。每个叶节点都拥有一个相应的类别标记，测试样本被标记为它所到达的叶节点的类别标记。
决策树算法相比其他分类器（如神经网络）的优点之一是，树中所体现的语义信息，容易直接用逻辑表达式表示出。而树分类器的另外一个有点是分类速度快。这是因为树提供了一种很自然的嵌入人类专家的先验知识的机制，在实际中，当问题较为简单且训练样本较少的情况下，这类专家知识往往十分有效。
3.分类和回归树(CART)算法
综合以上概念，这里讨论一个问题，即基于训练样本构造或“生成一棵判定树”的问题。假设一个训练样本集D，该训练集拥有类别标记，同时确定了一个用于判定模式的属性集。对于一棵判定树，其任务是把训练样本逐步划分成越来越小的子集，一个理想的情况是每个子集中所有的样本均拥有同种类别标记，树的分类操作也到此结束，这类子集称为“纯”的子集。而一般情况下子集中的类别标记并不唯一，这时需要执行一个操作，要么接受当前有“缺陷”的判决结果，停止继续分类；要么另外选取一个属性进一步生长该树，这一过程是一种递归结构的树的生长过程。
若从数据结构的角度来看，数据表示在每个节点上，要么该节点已经是叶节点（自身已拥有明确的类别标记），要么利用另一种属性，继续分裂出子节点。分类和回归树是仅有的一种通用的树生长算法。CART提供一种通用的框架，使用者可以将其实例化为各种不同的判定树。
3.1 CART算法的分支数目
节点处的一次判别称为一个分支，它将训练样本划分成子集。根节点处的分支对应于全部训练样本，气候每一次判决都是一次子集划分过程。一般情况下，节点的分支数目由树的设计者确定，，并且在一棵树上可能有不同的值。从一个节点中分出去的分支数目有时称为节点的分支率(branching ratio)，这里用B表示。这里需要说明一个事实，即每个判别都可以用二值判别表示出来。由于二叉树具有普适性，而且构造比较方便，因此被广泛采用。
3.2 CART算法中查询的选取与节点不纯度
在决策树的设计过程中，一个重点是考虑在每个节点处应该选出测试或查询哪一个属性。我们知道对于数值数据，用判定树的方法得到的分类边界存在着较为自宏观的几何解释；而对于非数值数据，在节点处作查询进而划分数据的过程并没有直接的几何解释。
构造树的过程的一个基本原则是简单。我们期望获得的判定树简单紧凑，只有很少的节点。本着这一目标，应试图寻找这样一个查询T，它能使后继节点数据尽可能的“纯”。这里需要定义“不纯度”的指标。用i(N)表示节点N的“不纯度”，当节点上的模式数据均来自同一类别时，令i(N)=0；若类别标记均匀分布时，i(N)应当比较大。一种最流行的测量称为“熵不纯度”(entropy impurity)，又称为信息量不纯度(information impurity)：
其中P(ωj)是节点N处属于ωj类模式样本数占总样本数的频度。根据熵的特性，如果所有模式的样本都来自同一类别，则不纯度为零，否则则大于零。当且仅当所有类别以等概率出现时，熵值取最大值。以下给出另外几种常用的不纯度定义：
“平方不纯度”，根据当节点样本均来自单一类别时不纯度为0的思想，用以下多项式定义不纯度，该值与两类分布的总体分布方差有关：
“Gini不纯度”，用于多类分类问题的方差不纯度（也是当节点N的类别标记任意选取时对应的误差率）：
当类别标记等概率时“Gini不纯度”指标的峰度特性比“熵不纯度”要好。
“误分类不纯度”，用于衡量节点N处训练样本分类误差的最小概率：
该指标在之前讨论过的不纯度指标中当等概率标记时具有最好的峰值特性。然而由于存在不连续的导数值，因而在连续参数空间搜索最大值时会出现问题。
生活是一段奇妙的旅行，就在那一去无返的火车上。
