Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了 Adaptive Boosting。AdaBoost 演算法通过调整每笔资料的权重，得到不同的 hypotheses，然后将不同的 hypothesis 乘以不同的系数进行线性组合。这种演算法的优点是，即使底层的演算法 g 不是特别好（只要比乱选好点），经过多次迭代后算法模型会越来越好，起到了 boost 提升的效果。本节课将在此基础上介绍一种新的 aggregation 算法：决策树（Decision Tree）。

Decision Tree Hypothesis

从第 7 节课开始，我们就一直在介绍 aggregation model。aggregation 的核心就是将许多可供选择使用的比较好的 hypothesis 融合起来，利用集体的智慧组合成 G，使其得到更好的机器学习预测模型。下面，我们先来看看已经介绍过的 aggregation type 有哪些。

aggregation type 有三种：uniform，non-uniform，conditional。它有两种情况，一种是所有的 g 是已知的，即 blending。对应的三种类型分别是 voting/averaging，linear 和 stacking。另外一种情况是所有 g 未知，只能通过手上的资料重构 g，即 learning。其中 uniform 和 non-uniform 分别对应的是 Bagging 和 AdaBoost 算法，而 conditional 对应的就是我们本节课将要介绍的 Decision Tree 算法。

决策树（Decision Tree）模型是一种传统的算法，它的处理方式与人类思维十分相似。例如下面这个例子，对下班时间、约会情况、提交截止时间这些条件进行判断，从而决定是否要进行在线课程测试。如下图所示，整个流程类似一个树状结构。

图中每个条件和选择都决定了最终的结果，Y or N。蓝色的圆圈表示树的叶子，即最终的决定。

把这种树状结构对应到一个 hypothesis G(x) 中，G(x) 的表达式为：

G(x) 由许多组成，即 aggregation 的做法。每个就代表上图中的蓝色圆圈（树的叶子）。这里的是常数，因为是处理简单的 classification 问题。我们把这些称为 base hypothesis。表示每个成立的条件，代表上图中橘色箭头的部分。不同的对应于不同的，即从树的根部到顶端叶子的路径不同。图中中的菱形代表每个简单的节点。所以，这些 base hypothesis 和 conditions 就构成了整个 G(x) 的形式，就像一棵树一样，从根部到顶端所有的叶子都安全映射到上述公式上去了。

决策树实际上就是在模仿人类做决策的过程。一直以来，决策树的应用十分广泛而且分类预测效果都很不错，而它在数学上的理论完备性不充分，倒也不必在意。

如果从另外一个方面来看决策树的形式，不同于上述 G(x) 的公式，我们可以利用条件分支的思想，将整体 G(x) 分成若干个，也就是把整个大树分成若干个小树，如下所示：

上式中，G(x) 表示完整的大树，即 full-tree hypothesis，b(x) 表示每个分支条件，即 branching criteria，表示第 c 个分支下的子树，即 sub-tree。这种结构被称为递归型的数据结构，即将大树分割成不同的小树，再将小树继续分割成更小的子树。所以，决策树可以分为两部分：root 和 sub-trees。

在详细推导决策树算法之前，我们先来看一看它的优点和缺点。首先，decision tree 的优点有：

• 模型直观，便于理解，应用广泛
• 算法简单，容易实现
• 训练和预测时，效率较高

然而，decision tree 也有相应的缺点：

• 缺少足够的理论支持
• 如何选择合适的树结构对初学者来说比较困惑
• 决策树代表性的演算法比较少

Decision Tree Algorithm

我们可以用递归形式将 decision tree 表示出来，它的基本的算法可以写成：

这个 Basic Decision Tree Algorithm 的流程可以分成四个部分，首先学习设定划分不同分支的标准和条件是什么；接着将整体数据集 D 根据分支个数 C 和条件，划为不同分支下的子集 Dc；然后对每个分支下的 Dc 进行训练，得到相应的机器学习模型 Gc；最后将所有分支下的 Gc 合并到一起，组成大矩 G(x)。但值得注意的是，这种递归的形式需要终止条件，否则程序将一直进行下去。当满足递归的终止条件之后，将会返回基本的 hypothesis 。

所以，决策树的基本演算法包含了四个选择：

• 分支个数（number of branches）
• 分支条件（branching criteria）
• 终止条件（termination criteria）
• 基本算法（base hypothesis）

下面我们来介绍一种常用的决策树模型算法，叫做 Classification and Regression Tree(C&RT)。C&RT 算法有两个简单的设定，首先，分支的个数 C=2，即二叉树（binary tree）的数据结构；然后，每个分支最后的（数的叶子）是一个常数。按照最小化的目标，对于 binary/multiclass classification(0/1 error) 问题，看正类和负类哪个更多，取所占比例最多的那一类；对于 regression(squared error) 问题，则取所有的平均值。

对于决策树的基本演算法流程，C&RT 还有一些简单的设定。首先，C&RT 分支个数 C=2，一般采用上节课介绍过的 decision stump 的方法进行数据切割。也就是每次在一个维度上，只对一个特征 feature 将数据一分为二，左子树和右子树，分别代表不同的类别。然而，怎么切割才能让数据划分得最好呢（error 最小）？C&RT 中使用纯净度 purifying 这个概念来选择最好的 decision stump。purifying 的核心思想就是每次切割都尽可能让左子树和右子树中同类样本占得比例最大或者都很接近（regression），即错误率最小。比如说 classifiacation 问题中，如果左子树全是正样本，右子树全是负样本，那么它的纯净度就很大，说明该分支效果很好。

根据 C&RT 中 purifying 的思想，我们得到选择合适的分支条件 b(x) 的表达式如上所示。最好的 decision stump 重点包含两个方面：一个是刚刚介绍的分支纯净度 purifying，purifying 越大越好，而这里使用 purifying 相反的概念 impurity，则 impurity 越小越好；另外一个是左右分支纯净度所占的权重，权重大小由该分支的数据量决定，分支包含的样本个数越多，则所占权重越大，分支包含的样本个数越少，则所占权重越小。上式中的代表了分支 c 所占的权重。这里 b(x) 类似于 error function（这也是为什么使用 impurity 代替 purifying 的原因），选择最好的 decision stump，让所有分支的不纯度最小化，使 b(x) 越小越好。

不纯度 Impurity 如何用函数的形式量化？一种简单的方法就是类比于，看预测值与真实值的误差是多少。对于 regression 问题，它的 impurity 可表示为：

其中，表示对应分支下所有的均值。

对应 classification 问题，它的 impurity 可表示为：

其中，表示对应分支下所占比例最大的那一类。

以上这些 impurity 是基于原来的 regression error 和 classification error 直接推导的。进一步来看 classification 的 impurity functions，如果某分支条件下，让其中一个分支纯度最大，那么就选择对应的 decision stump，即得到的 classification error 为：

其中，K 为分支个数。

上面这个式子只考虑纯度最大的那个分支，更好的做法是将所有分支的纯度都考虑并计算在内，用基尼指数（Gini index）表示：

Gini index 的优点是将所有的 class 在数据集中的分布状况和所占比例全都考虑了，这样让 decision stump 的选择更加准确。

对于决策树 C&RT 算法，通常来说，上面介绍的各种 impurity functions 中，Gini index 更适合求解 classification 问题，而 regression error 更适合求解 regression 问题。

C&RT 算法迭代终止条件有两种情况，第一种情况是当前各个分支下包含的所有样本都是同类的，即不纯度 impurity 为 0，表示该分支已经达到了最佳分类程度。第二种情况是该特征下所有的相同，无法对其进行区分，表示没有 decision stumps。遇到这两种情况，C&RT 算法就会停止迭代。

所以，C&RT 算法遇到迭代终止条件后就成为完全长成树（fully-grown tree）。它每次分支为二，是二叉树结构，采用 purify 来选择最佳的 decision stump 来划分，最终得到的叶子（）是常数。

Decision Tree Heuristics in C&RT

现在我们已经知道了 C&RT 算法的基本流程：

可以看到 C&RT 算法在处理 binary classification 和 regression 问题时非常简单实用，而且，处理 muti-class classification 问题也十分容易。

考虑这样一个问题，有 N 个样本，如果我们每次只取一个样本点作为分支，那么在经过 N-1 次分支之后，所有的样本点都能完全分类正确。最终每片叶子上只有一个样本，有 N 片叶子，即必然能保证。这样看似是完美的分割，但是不可避免地造成 VC Dimension 无限大，造成模型复杂度增加，从而出现过拟合现象。为了避免 overfit，我们需要在 C&RT 算法中引入正则化，来控制整个模型的复杂度。

考虑到避免模型过于复杂的方法是减少叶子（）的数量，那么可以令 regularizer 就为决策树中叶子的总数，记为。正则化的目的是尽可能减少的值。这样，regularized decision tree 的形式就可以表示成：

我们把这种 regularized decision tree 称为 pruned decision tree。pruned 是修剪的意思，通过 regularization 来修剪决策树，去掉多余的叶子，更简洁化，从而达到避免过拟合的效果。

那么如何确定修剪多少叶子，修剪哪些叶子呢？假设由 C&RT 算法得到一棵完全长成树（fully-grown tree），总共 10 片叶子。首先分别减去其中一片叶子，剩下 9 片，将这 10 种情况比较，取最小的那个模型；然后再从 9 片叶子的模型中分别减去一片，剩下 8 片，将这 9 种情况比较，取最小的那个模型。以此类推，继续修建叶子。这样，最终得到包含不同叶子的几种模型，将这几个使用 regularized decision tree 的 error function 来进行选择，确定包含几片叶子的模型误差最小，就选择该模型。另外，参数可以通过 validation 来确定最佳值。

我们一直讨论决策树上的叶子（features）都是 numerical features，而实际应用中，决策树的特征值可能不是数字量，而是类别（categorical features）。对于 numerical features，我们直接使用 decision stump 进行数值切割；而对于 categorical features，我们仍然可以使用 decision subset，对不同类别进行“左”和“右”，即是与不是（0 和 1）的划分。numerical features 和 categorical features 的具体区别如下图所示：

在决策树中预测中，还会遇到一种问题，就是当某些特征缺失的时候，没有办法进行切割和分支选择。一种常用的方法就是 surrogate branch，即寻找与该特征相似的替代 feature。如何确定是相似的 feature 呢？做法是在决策树训练的时候，找出与该特征相似的 feature，如果替代的 feature 与原 feature 切割的方式和结果是类似的，那么就表明二者是相似的，就把该替代的 feature 也存储下来。当预测时遇到原 feature 缺失的情况，就用替代 feature 进行分支判断和选择。

Decision Tree in Action

最后我们来举个例子看看 C&RT 算法究竟是如何进行计算的。例如下图二维平面上分布着许多正负样本，我们使用 C&RT 算法来对其进行决策树的分类。

第一步：

第二步：

第三步：

第四步：

在进行第四步切割之后，我们发现每个分支都已经非常纯净了，没有办法继续往下切割。此时表明已经满足了迭代终止条件，这时候就可以回传 base hypothesis，构成 sub tree，然后每个 sub tree 再往上整合形成 tree，最后形成我们需要的完全决策树。如果将边界添加上去，可得到下图：

得到 C&RT 算法的切割方式之后，我们与 AdaBoost-Stump 算法进行比较：

我们之前就介绍过，AdaBoost-Stump 算法的切割线是横跨整个平面的；而 C&RT 算法的切割线是基于某个条件的，所以一般不会横跨整个平面。比较起来，虽然 C&RT 和 AdaBoost-Stump 都采用 decision stump 方式进行切割，但是二者在细节上还是有所区别。

再看一个数据集分布比较复杂的例子，C&RT 和 AdaBoost-Stump 的切割方式对比效果如下图所示：

通常来说，由于 C&RT 是基于条件进行切割的，所以 C&RT 比 AdaBoost-Stump 分类切割更有效率。总结一下，C&RT 决策树有以下特点：

总结：

本节课主要介绍了 Decision Tree。首先将 decision tree hypothesis 对应到不同分支下的矩。然后再介绍决策树算法是如何通过递归的形式建立起来。接着详细研究了决策树 C&RT 算法对应的数学模型和算法架构流程。最后通过一个实际的例子来演示决策树 C&RT 算法是如何一步一步进行分类的。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）