聊聊机器学习中的那些树

树模型是机器学习领域内，除了深度学习之外，使用的最为广泛，也是变种特别多的一种模型了，树模型的好处是其很容易理解，且相对不容易过拟合，训练时对资源的消耗也更少。最常用树模型包括决策树，随机森林及XGBoost而在去年，南大的周志华教授提出了deep forest，一种借鉴深度学习的树模型，树模型还有其他的更为冷门的变种，例如正则化贪心森林和。这篇文章将始简单的介绍下上述的几种树模型的原理，树模型是最容易理解的，请您放心，本文只有一个公式，是关于信息熵的。

树模型主要用来做分类。最简单的一种叫做决策树，决策树是一个非常接近人类思维的模型。 它形象的说就是一个调查问卷， 把一个最终的决策转化为个若干问题， 每一步得到一个答案， 按照答案的正否来决定下一个问题是什么，如此形成一个树结构， 最后形成一个分类器。 比如经常被举出的例子， 你要买电脑， 要根据很多特征挑选电脑，比如cpu，gpu，硬盘，内存等， 你一定会问你自己一系列问题， 我要买那款cpu，gpu， 硬盘， 内存等，最后做出决策。决策树要做的是把这个过程自动化，最后给我们我们希望的判定结果。

Cpu

Gpu

内存

决策

高

中

低

买

高

高

中

买

高

中

低

不买

在一棵决策树上，其中的节点可以分成根节点（蓝色） 决策节点（红色）和终止节点（绿色），而图中的方框里包含的即是一颗子树，这么看来，树模型是不是特别好理解？树模型的第二个好处是可以方便的探索数据中那些维度更加重要（对做出正确的预测贡献更大），比如上述的买电脑的例子，你会发现对于大多数人来说，CPU的型号最关键。树模型的第三个好处是不怎么需要做数据清洗和补全，还用买电脑的例子，假设你拿到的数据部分中没有告诉GPU的型号，你不必要丢掉这部分数据，进入到相应的子树里，随机的让这条数据进入一个终止节点就好了，这样，你便能够利用缺失的数据了。

谈起树模型，就要说起基尼系数，这个指数最常见的场景是描述贫富差距，但也可以用来指导树模型在那里分叉。假设一颗最简单做二分类问题的决策树，拿到的数据分为两种特征，一个是性别，一个是班级，预测学生们愿不愿打板球，下面的图是两种不同的树模型，用性别来分，10个女生中有2个愿意打球，而20个男生中有13个愿意打球，而用班级分，效果则没有那么好，具体怎么计算了，先从左到右依次计算每个终止节点的基尼系数，(0.2)*(0.2)+(0.8)*(0.8)=0.68 (0.65)*(0.65)+(0.35)*(0.35)=0.55 (0.43)*(0.43)+(0.57)*(0.57)=0.51 (0.56)*(0.56)+(0.44)*(0.44)=0.51，之后对每棵树的基尼系数进行加权平均 ：10/30)*0.68+(20/30)*0.55 = 0.59（按性别分），(14/30)*0.51+(16/30)*0.51 = 0.51（按班级分），因此在该例子中，性别是一个更好的特征。

理解决策树的下一个重要的概念是信息增益，信息可以看成是减少了多少系统中的无序，而描述系统的无序程度，可以用信息熵，对于二分类问题，计算公式是 。

对于每一次树上的分叉，先算下父节点的熵，再计算下子节点的熵的加权平均，就可以计算出决策树中的一个决策节点带来了多少信息增益了。

信息熵公式告诉我们的是，我们每次对所有特征都扫描一遍，选择那个让我们的信息增长最大的特征。 依次在这个特征的每个可能取值下，我们在寻找第二个关键特征，列出第二个特征选的可能取值并寻找第三个特征依次类推。 再对每一分支的操作里， 如果我们发现在某个特征组合下的样本均为一类， 则停止分叉的过程。 整个操作过程形似寻找一颗不断分叉的树木， 故名决策树。

决策树能够处理特征之间的互相影响， 因为特征之间的互相影响，我们并不像简单贝叶斯那样并列的处理这些特征。 例如某个特征可能在某个条件下式好的， 但在另外条件下就是坏的或者没影响。 比如说找对象，你只在对方漂亮的时候才care他学历。 我会根据之前问过的问题的答案来选择下一步问什么样的问题， 如此， 我就能很好的处理特征之间的关联。

我们把这样的思维步骤写成伪代码， 大概是这样的 :

训练集D （x1，y1）….

属性 A attribute （a1，a2…..）

函数treegenerate

1, 生成结点node A（任选一个特征）

2， 判断D在A中样本是否都属于类型C，是则A标记为C类叶结点， 结束

3， 判断A为空或D在A样本取值同（x相同而非y），将node 标记为样本多数分类的叶结点（max numbers），结束

终止条件不成立则:

从A中选择最优划分属性a*,

循环:

对A*上的每一个值a*做如下处理：

If a*上的样本为空，则a*为叶节点 （该值下用于判断的样本不足，判定为A*中样本最多的类），

如果支点上的样本集为D**

如果存在某个位置，使得D**为空，

则A*为叶节点，

否则，以a*为分支节点，回到第一句

接下来我们看一看更为复杂的情况，比如我们拿到的数据特征不是两个，而是一百个，那么问题来了，我们的决策树也要100层那么深吗？如果真的这么深，那么这个模型很容易过拟合的，任何一颗决策树的都应该有终止条件，例如树最深多少层，每个节点最少要有多少样本，最多有多少个终止节点等，这些和终止条件有关的超参数设置决定了模型会不会过拟合。

下面我们从一棵树过度到一群数，也就是机器学习中常用的bagging，将原来的训练数据集分成多份，每一份分别训练一个分类器，最后再让这些分类器进行投票表决。

而随机森林，就是使用bagging技巧加持的决策树，是不是很简单？相比于决策树，随机森林的可解释性差一些，另外对于标签为连续的回归问题，随机森林所采取的求多个树的平均数的策略会导致结果的不稳定。

随机森林是将训练数据随机的分成很多类，分别训练很多分类器，再将这些分类器聚合起来，而boosting则不讲训练数据分类，而是将弱分类器聚合起来，下图的上半部分可以看成描述了三个弱分类器，每一个都有分错的，而将他们集合起来，可以得出一个准确率比每一个弱分类器都高的分类模型。

你需要做的是将第一个分类器分类分错的部分交给第二个分类器，再将第二个分类器分错的部分交给第三个分类器，如下图依次所示

最终得到了我们看到的强分类器。

总结来看，begging类似于蚁群的智慧，没有一只蚂蚁知道全部的信息，但利用蚂蚁的集合，可以实现集愚成智，而boosting则是三个臭皮匠，胜过诸葛亮。Boost方法包含的非线性变换比较多，表达能力强，而且不需要做复杂的特征工程和特征变换。但不同于随机森林，它是一个串行过程，不好并行化，而且计算复杂度高。

XGBoost 是 Extreme Gradient Boosting （极端梯度上升）的缩写，是当下最常用的树模型了，是上图描述的Boosting Tree的一种高效实现，在R，Python等常用的语言下都有对应的包，它把树模型复杂度作为正则项加到优化目标中，从而避免了过于复杂而容易过拟合的模型。

在Boost方法中，每一个被错误分类的样本的权值会增加，以强调最困难的情况，从而使得接下来的模型能集中注意力来处理这些错误的样本，然而这种方法把基于学习器的决策树视为一个黑盒子，没有利用树结构本身。而Regularized Greedy Forest正则化贪心森林(RGF)会在当前森林某一步的结构变化后，依次调整整个森林中所有决策树对应的“叶子”的权重，使损失函数最小化。例如下图我们从原来的森林中发下右下的节点可以分叉，我们做的不止是将分叉后的树加入森林，而且对森林中已有的树中的对应节点也进行类似的分叉操作。

类似boost，RGF中每个节点的权重也要不断优化，但不同的是，RGF不需要在梯度下降决策树设置所需的树尺寸（tree size）参数（例如，树的数量，最大深度）。总结一下RGF是另一种树集成技术，它类似梯度下降算法，可用于有效建模非线性关系。

下面说说去年周志华教授提出深度森林deep forest，也叫做 gcForest，这也是一种基于决策树的集成方法，下图中每一层包括两个随机森林（蓝色）和两个complete random forests（黑色），所谓complete random forest，指的是其中的1000棵决策树的每个节点都随机的选择一个特征作为分裂特征，不断增长整棵树，直到剩余所有样本属于同一类，或样本数量少于10。

至于每一层的输出，也不是传统决策树的一个标签，而是一个向量。图中的每一个森林对每个输入样本都有一个输出，对应建立该决策树时，落在该叶子节点中的样本集合中各个类别的样本所占的比例，如下图所示，将多颗树的结果求平均，得出这一层的输出。为了避免过拟合，每个森林中 class vector 的产生采用了 k 折交叉验证的方法，随机的将k分之一的训练样本丢出去，再对k次训练的结果求平均值。

deep forest还采取了类似卷积神经网络的滑动窗口，如下图所示，原始样本的为400维，定义一个大小为100的滑动窗口，将滑动窗口从原特征上依次滑过，每次移动一步，每次窗口滑动获取的100个特征作为一个新的实例，等效于在400维特征上每相邻100维的特征摘出来作为一个特征实例，得到301个新的特征实例（400 - 300 + 1）。

深度森林的源代码也在Github上有开源版，总结一下，深度森林具有比肩深度神经网络的潜力，例如可以层次化的进行特征提取及使用预训练模型进行迁移学习，相比于深度学习，其具有少得多的超参数，并且对参数设置不太敏感，且在小数据集上，例如手写数字识别中，表现的不比CNN差。深度森林的数据处理流如下图所示。

总结下，树模型作为一个常见的白盒模型，不管数据集的大小，不管是连续的回归问题还是分类问题都适用。它不怎么需要进行数据预处理，例如补全缺失值，去除异常点。树模型可以针对特征按照重要性进行排序，从而构造新的特征或从中选出子集来压缩数据。树模型可以通过统计的方式去验证模型的准确值，判断训练的进展，相比机器学习的模型，需要调整的超参数也更少。但和神经网络一样，树模型也不够健壮，如同图像上只需要改变几个像素点就可以改变模型的结果，树模型中输入数据的微小变化也可能会显著改变模型的结果。树模型也有过拟合的危险，通过剪纸purning，即先让树长的深一些，再去除那些不带来信息增益的分叉，留下那些最初的信息增益为负，但整体的信息增益为正的节点，可以组织树模型的过拟合。

王欢2018-02-25 15:09:02

发文之前没有人检查一下行文的通顺性和错别字么…… 第一段实在是惨不忍睹啊……

锋2018-02-25 09:07:13

begging or bagging？

作者

写错了 应该是bagging