AI有道
一个有情怀的公众号
上文我们主要介绍了 。演算法通过调整每笔资料的权重，得到不同的，然后将不同的乘以不同的系数α进行线性组合。这种演算法的优点是，即使底层的演算法g不是特别好（只要比乱选好点），经过多次迭代后算法模型会越来越好，起到了boost提升的效果。本节课将在此基础上介绍一种新的算法：决策树（ Tree）。
Tree
从第7节课开始，我们就一直在介绍 model。的核心就是将许多可供选择使用的比较好的融合起来，利用集体的智慧组合成G，使其得到更好的机器学习预测模型。下面，我们先来看看已经介绍过的 type有哪些。
type有三种：，non-，。它有两种情况，一种是所有的g是已知的，即。对应的三种类型分别是/，和。另外一种情况是所有g未知，只能通过手上的资料重构g，即。其中和non-分别对应的是和算法，而对应的就是我们本节课将要介绍的 Tree算法。
决策树（ Tree）模型是一种传统的算法，它的处理方式与人类思维十分相似。例如下面这个例子，对下班时间、约会情况、提交截止时间这些条件进行判断，从而决定是否要进行在线课程测试。如下图所示，整个流程类似一个树状结构。
图中每个条件和选择都决定了最终的结果，Y or N。蓝色的圆圈表示树的叶子，即最终的决定。
把这种树状结构对应到一个 G(x)中，G(x)的表达式为：
G(x)由许多gt(x)组成，即的做法。每个gt(x)就代表上图中的蓝色圆圈（树的叶子）。这里的gt(x)是常数，因为是处理简单的问题。我们把这些gt(x)称为base 。qt(x)表示每个gt(x)成立的条件，代表上图中橘色箭头的部分。不同的gt(x)对应于不同的qt(x)，即从树的根部到顶端叶子的路径不同。图中中的菱形代表每个简单的节点。所以，这些base 和就构成了整个G(x)的形式，就像一棵树一样，从根部到顶端所有的叶子都安全映射到上述公式上去了。
决策树实际上就是在模仿人类做决策的过程。一直以来，决策树的应用十分广泛而且分类预测效果都很不错，而它在数学上的理论完备性不充分，倒也不必在意。
如果从另外一个方面来看决策树的形式，不同于上述G(x)的公式，我们可以利用条件分支的思想，将整体G(x)分成若干个Gc(x)，也就是把整个大树分成若干个小树，如下所示：
上式中，G(x)表示完整的大树，即full-tree ，b(x)表示每个分支条件，即 ，Gc(x)表示第c个分支下的子树，即sub-tree。这种结构被称为递归型的数据结构，即将大树分割成不同的小树，再将小树继续分割成更小的子树。所以，决策树可以分为两部分：root和sub-trees。
在详细推导决策树算法之前，我们先来看一看它的优点和缺点。首先， tree的优点有：
然而， tree也有相应的缺点：
Tree
我们可以用递归形式将 tree表示出来，它的基本的算法可以写成：
这个Basic Tree 的流程可以分成四个部分，首先学习设定划分不同分支的标准和条件是什么；接着将整体数据集D根据分支个数C和条件，划为不同分支下的子集Dc；然后对每个分支下的Dc进行训练，得到相应的机器学习模型Gc；最后将所有分支下的Gc合并到一起，组成大矩G(x)。但值得注意的是，这种递归的形式需要终止条件，否则程序将一直进行下去。当满足递归的终止条件之后，将会返回基本的(x)。
所以，决策树的基本演算法包含了四个选择：
下面我们来介绍一种常用的决策树模型算法，叫做 and Tree(C&RT)。C&RT算法有两个简单的设定，首先，分支的个数C=2，即二叉树（ tree）的数据结构；然后，每个分支最后的gt(x)（数的叶子）是一个常数。按照最小化Ein的目标，对于/ (0/1 error)问题，看正类和负类哪个更多，gt(x)取所占比例最多的那一类yn；对于( error)问题决策树模型，gt(x)则取所有yn的平均值。
对于决策树的基本演算法流程，C&RT还有一些简单的设定。首先，C&RT分支个数C=2，一般采用上节课介绍过的 stump的方法进行数据切割。也就是每次在一个维度上，只对一个特征将数据一分为二，左子树和右子树，分别代表不同的类别。然而，怎么切割才能让数据划分得最好呢（error最小）？C&RT中使用纯净度这个概念来选择最好的 stump。的核心思想就是每次切割都尽可能让左子树和右子树中同类样本占得比例最大或者yn都很接近（），即错误率最小。比如说问题中，如果左子树全是正样本，右子树全是负样本，那么它的纯净度就很大，说明该分支效果很好。
根据C&RT中的思想，我们得到选择合适的分支条件b(x)的表达式如上所示。最好的 stump重点包含两个方面：一个是刚刚介绍的分支纯净度，越大越好，而这里使用相反的概念，则越小越好；另外一个是左右分支纯净度所占的权重，权重大小由该分支的数据量决定，分支包含的样本个数越多，则所占权重越大，分支包含的样本个数越少，则所占权重越小。上式中的||代表了分支c所占的权重。这里b(x)类似于error （这也是为什么使用代替的原因），选择最好的 stump，让所有分支的不纯度最小化，使b(x)越小越好。
不纯度如何用函数的形式量化？一种简单的方法就是类比于Ein，看预测值与真实值的误差是多少。对于问题，它的可表示为：
对应问题，它的可表示为：
其中，y∗表示对应分支下所占比例最大的那一类。
以上这些是基于原来的 error和 error直接推导的。进一步来看的 ，如果某分支条件下，让其中一个分支纯度最大，那么就选择对应的 stump，即得到的 error为：
其中，K为分支个数。
上面这个式子只考虑纯度最大的那个分支，更好的做法是将所有分支的纯度都考虑并计算在内，用基尼指数（Gini index）表示：
Gini index的优点是将所有的class在数据集中的分布状况和所占比例全都考虑了，这样让 stump的选择更加准确。
对于决策树C&RT算法，通常来说，上面介绍的各种 中，Gini index更适合求解问题，而 error更适合求解问题。
C&RT算法迭代终止条件有两种情况决策树模型，第一种情况是当前各个分支下包含的所有样本yn都是同类的，即不纯度为0，表示该分支已经达到了最佳分类程度。第二种情况是该特征下所有的xn相同，无法对其进行区分，表示没有 。遇到这两种情况，C&RT算法就会停止迭代。
所以，C&RT算法遇到迭代终止条件后就成为完全长成树（fully-grown tree）。它每次分支为二，是二叉树结构，采用来选择最佳的 stump来划分，最终得到的叶子（gt(x)）是常数。
Tree in C&RT
现在我们已经知道了C&RT算法的基本流程：
可以看到C&RT算法在处理 和问题时非常简单实用，而且，处理muti-class 问题也十分容易。
考虑这样一个问题，有N个样本，如果我们每次只取一个样本点作为分支，那么在经过N-1次分支之后，所有的样本点都能完全分类正确。最终每片叶子上只有一个样本，有N片叶子，即必然能保证Ein=0。这样看似是完美的分割，但是不可避免地造成VC 无限大，造成模型复杂度增加，从而出现过拟合现象。为了避免，我们需要在C&RT算法中引入正则化，来控制整个模型的复杂度。
考虑到避免模型过于复杂的方法是减少叶子（gt(x)）的数量，那么可以令就为决策树中叶子的总数，记为Ω(G)。正则化的目的是尽可能减少Ω(G)的值。这样， tree的形式就可以表示成：
我们把这种 tree称为 tree。是修剪的意思，通过来修剪决策树，去掉多余的叶子，更简洁化，从而达到避免过拟合的效果。
那么如何确定修剪多少叶子，修剪哪些叶子呢？假设由C&RT算法得到一棵完全长成树（fully-grown tree），总共10片叶子。首先分别减去其中一片叶子，剩下9片，将这10种情况比较，取Ein最小的那个模型；然后再从9片叶子的模型中分别减去一片，剩下8片，将这9种情况比较，取Ein最小的那个模型。以此类推，继续修建叶子。这样，最终得到包含不同叶子的几种模型，将这几个使用 tree的error 来进行选择，确定包含几片叶子的模型误差最小，就选择该模型。另外，参数λ可以通过来确定最佳值。
我们一直讨论决策树上的叶子（）都是 ，而实际应用中，决策树的特征值可能不是数字量，而是类别（ ）。对于 ，我们直接使用 stump进行数值切割；而对于 ，我们仍然可以使用 ，对不同类别进行“左”和“右”，即是与不是（0和1）的划分。 和 的具体区别如下图所示：
在决策树中预测中，还会遇到一种问题，就是当某些特征缺失的时候，没有办法进行切割和分支选择。一种常用的方法就是 ，即寻找与该特征相似的替代。如何确定是相似的呢？做法是在决策树训练的时候，找出与该特征相似的，如果替代的与原切割的方式和结果是类似的，那么就表明二者是相似的，就把该替代的也存储下来。当预测时遇到原缺失的情况，就用替代进行分支判断和选择。
Tree in
最后我们来举个例子看看C&RT算法究竟是如何进行计算的。例如下图二维平面上分布着许多正负样本，我们使用C&RT算法来对其进行决策树的分类。
第一步：
第二步：
第三步：
第四步：
在进行第四步切割之后，我们发现每个分支都已经非常纯净了，没有办法继续往下切割。此时表明已经满足了迭代终止条件，这时候就可以回传base ，构成sub tree，然后每个sub tree再往上整合形成tree，最后形成我们需要的完全决策树。如果将边界添加上去，可得到下图：
得到C&RT算法的切割方式之后，我们与-Stump算法进行比较：
我们之前就介绍过，-Stump算法的切割线是横跨整个平面的；而C&RT算法的切割线是基于某个条件的，所以一般不会横跨整个平面。比较起来，虽然C&RT和-Stump都采用 stump方式进行切割，但是二者在细节上还是有所区别。
再看一个数据集分布比较复杂的例子，C&RT和-Stump的切割方式对比效果如下图所示：
通常来说，由于C&RT是基于条件进行切割的，所以C&RT比-Stump分类切割更有效率。总结一下，C&RT决策树有以下特点：
本节课主要介绍了 Tree。首先将 tree 对应到不同分支下的矩gt(x)。然后再介绍决策树算法是如何通过递归的形式建立起来。接着详细研究了决策树C&RT算法对应的数学模型和算法架构流程。最后通过一个实际的例子来演示决策树C&RT算法是如何一步一步进行分类的。
往期回顾
【1】
【2】
【3】
【4】
【5】
【6】
【7】
【8】
【9】？
【10】
长按二维码
限时特惠:本站持续每日更新海量各大内部创业课程，一年会员仅需要98元，全站资源免费下载
点击查看详情
站长微信:Jiucxh
