机器学习十——Decision Tree

Decision Tree Hypothesis

aggregation的核心就是将许多可供选择使用的比较好的hypothesis融合起来，利用集体的智慧组合成G，使其得到更好的机器学习预测模型。

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）模型是一种传统的算法，它的处理方式与人类思维十分相似。这也就增加了决策树的可解释性。

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

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

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

这种结构被称为递归型的数据结构，即将大树分割成不同的小树，再将小树继续分割成更小的子树。所以，决策树可以分为两部分：root和sub­trees。

决策树算法的优缺点：

Decision Tree Algorithm

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

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

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

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

下面我们来介绍一种常用的决策树模型算法，叫做Classification and Regression Tree(C&RT)。C&RT算法有两个简单的设定，首先，分支的个数C=2，即二叉树（binary tree）的数据结构；

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

不纯度Impurity如何用函数的形式量化？

一种简单的方法就是类比于 E_{in} ，看预测值与真实值的误差是多少。对于regression问题，它的impurity可表示为：

其中， \bar{y} 表示对应分支下所有 y_{n} 的均值。对应classification问题，它的impurity可表示为：

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

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

Decision Tree Heuristics in C&RT

了C&RT算法的基本流程：

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

我们一直讨论决策树上的叶子（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进行分支判断和选择。

总结一下，C&RT决策树有以下特点：