条件概率 条件分布我们已经学习了一系列不同的模型用于解决分类(3)

下图用不同颜色的线对指数误差、缩放的交叉熵误差、支持向量机使用的铰链误差函数、无分类误差函数进行横向对比：

我们可以看到：

有许多简单但广泛使用的模型，它们将输入空间划分为超立方体区域，超立方体的边与坐标轴对齐，然后为每个区域分配一个简单的模型（例如一个常数阈值二分类器）。这些模型可以被看成一种模型组合方法，其中只有一个模型对于输入空间中任意给定点的预测起作用（输入数据点沿着二叉树直到树叶只能选择一条线路，到达唯一的一个叶子结点）。给定一个新的输入 x，选择一个具体的模型的过程可以由一个顺序决策的过程描述， 这个过程对应于一个二叉树（每个节点划分为两个分支的树）的遍历。

这里，我们关注一个特定的基于树的框架，被称为分类与回归树（classification and regression tree）。

下图给出了对输入空间进行递归二分的例子，以及对应的树结构。

在这个例子中，第一步根据或者，将输入空间划分为两个区域，其中是一个模型参数。

这创建了两个子区域，每个区域之后可以独立地进行划分，不断递归下去。

对于任意新的输入 x，我们确定它所属区域的方法是：从树顶端的根节点开始，根据每个结点的决策准则（基分类器），沿着路径向下走到具体的叶结点。

在每个区域内，有一个单独的模型（本质上就是基分类器）预测目标变量的值。例如

基于树的模型的一个关键的性质是模型可以由人类表述（可解释性），因为模型对应于作用在输入变量上的一个二元决策序列（注意，序列和加和模型是有区别的，序列不是简单的total加和，序列包含了决策顺序），这种序列在实际应用中非常有用。例如，为了预测一个病人的疾病，我们可以首先问“病人的体温是否大于某个阈值？”。如果回答是肯定的，那么我们可以问“病人的血压是否低于某个阈值？”。然后树的每个叶节点都与一个具体的诊断相关联。

我们继续来讨论如何确定决策树的结构，即使对于结点数量固定的树，确定最优结构（包括每次划分使用的输入变量以及对应的阈值）来最小化平方和误差函数的问题通常在计算上是不可行的，因为可能的组合数量非常巨大。相反，我们通常使用贪心的最优化。

对应于整个输入空间的一个单独的根节点开始，然后通过每次添加一个结点的方式构建树；

在每一步，输入空间中会有若干个可以切分的候选的区域，对应于向当前的树中添加一对叶节点。对于每个这种候选区域，我们要选择使用D个输入变量中的哪一个进行划分？以及阈值的大小？

划分区域的选择以及输入变量和阈值的选择可以通过彻底搜索的方法高效地进行联合最优化。

得到构建树的贪心策略之后，剩下的问题是如何停止添加结点。一个简单的方法是当残留误差的减小量低于某个阈值时停止（精确度增长速度收敛）。

然而，我们通过实验发现，经常出现这样的情形：在某一轮迭代中，没有一种划分方式会使误差函数产生显著的减小，但是再进行几次划分之后，就又突然找到一个使误差函数显著减小的划分方式（似乎是从一个局部最优的陷阱里跳出来了）

因此，在实际应用中通常构建一个较大的树，使用基于与叶节点关联的数据点数量的停止准则（本质是限制树的深度），然后进行剪枝，生成最终的树。

剪枝的过程基于的准则是：在残留误差与模型复杂度之间进行平衡

像CART这种树模型可以由人类进行表述这一性质通常被视为一个十分重要的优点，然后在实际应用中，学习到的特定的树结构对于数据集的细节非常敏感，从而训练集的一个微小的改变就会产生一个相当不同的划分集合。本质上来说，导致这个问题的原因在于决策的测决面太硬了，不够柔和。

另一个一个比较严重的问题是，划分边界与特征空间的坐标轴对齐的，这相当不好。