引言
神经网络模型，特地是深度神经网络模型，自 AlexNet 在 Imagenet Challenge 2012 上的一举成名，无疑是 Machine Learning Research 上最靓的仔，各种停顿和冲破层出不穷，科学家工程师人人都爱它。
机器学习钻研倒退至今，除了神经网络模型这种办法门路外，还存在许多天壤之别的办法门路，比如说贝叶斯算法、遗传算法、反对向量机等，这些经典算法在许多场景上也始终沿用。本文介绍的树模型，也是一种十分经典的机器学习算法，在举荐零碎上常常能看到它的身影。
那这个树模型是怎么构建和实现的，其外围 idea 是什么？树模型成果不够好，又能够用什么样的思路和方法改良呢？本文次要蕴含以下三个方面的内容：
1. 决策树
2. 集成学习
3. 随机森林与梯度晋升决策树
决策树
决策树 (Decision Tree) 是树模型中最简略的一个模型，也是前面将要介绍到的随机深林与梯度晋升决策树两个模型的根底。利用决策树算法，在历史约会数据集上，咱们能够画出这样一个树，这颗树上的叶子节点示意论断，非叶子节点示意根据。一个样本依据本身特色，从根节点开始，依据不同根据决策，拆分成子节点，直到只蕴含一种类别 (即一种论断) 的叶子节点为止。
假如有如下面表格的一个数据集，基于这样数据能够构建成这样的一颗决策树，如下图所示。
信息熵与基尼不纯度
能够看出构建决策树的要害是 ” 决裂 ”，一直地决裂成子节点，始终到叶子节点 (不能决裂) 为止。<font color=’red’> 那么这个要害决裂的规范和办法是什么、怎么分才是最好最失当的呢？显然，能把正负样本齐全划分开，一边正一边负，两边汇合都是很“确定的”最好 </font>。在这里确定性是指一个事件只呈现一个后果的可能性，那如何量化“确定性”这个指标呢，个别有两种办法：信息熵和基尼不纯度。
信息熵 Entropy，是用来掂量信息的不确定性的指标，其计算形式如下：
其中 P(X=i)为随机变量 X 取值为 i 的概率。
基尼不纯度，实际上是对信息熵的一种近似的简化计算，因为对 进行泰勒开展后，因为 ，所以高阶项近似为 0 可疏忽，仅保留一阶项 1 -P(X=i)
其中 示意选中样本为第 k 类的概率。从公式上看，基尼不纯度可了解为，从数据集 D 中随机抽取两个样本，这两个样本刚好不同类的概率。
信息熵和基尼不纯度都能主观而具体地量化出“不确定性”，这两个指标越大反映事物不确定性的水平越高。
比方有三个硬币，第一个硬币其正反面品质齐全平衡，抛出正反面概率雷同，第二个硬币侧面品质大于反面，其抛出侧面概率远大于反面，第三个硬币则肯定会抛出侧面。这三个硬币外面，第三个硬币的不确定性的水平最低，因为其没有任何的不确定性，抛出侧面是个必然事件；第一个硬币不确定性的水平最高，没方法确定抛出的侧面还是反面；第二个硬币不确定性水平次之，因为其有比拟大概率是能抛出侧面，能绝对确定一些。
构建分类树
有了对 ” 不确定性 ” 的量化办法，咱们利用这些指标，来领导咱们应该抉择那个特色、特色怎么分叉，保障每一步“决裂”都是最优的，始终迭代到叶子节点为止。显然这个决策树的构建算法就是个贪婪算法。思考到算法实现的问题，这个决策树最好是二叉的而不是多叉，所以咱们个别用二叉的 CART(Classification And Regression Tree)算法构建决策树。
以约会数据集 D 为例，Gini(D) = 0.5，划分成两个汇合 d1, d2，标签 0 和 1 示意否和是。基尼增益，如下表格所示咱们利用基尼增益选特色，并确认其最佳分叉点。
可见，基于气温特色在分叉点为 26.5 的状况下，将数据集 D 划分成 <d1, d2> 两个汇合，其取得基尼增益最大。反复这个步骤，将 d1 和 d2 持续拆分上来，直到汇合无奈再分，或基尼增益小于或等于 0 为止。
构建回归树
决策树用于回归问题，思路与用分类问题的思路是一样的。只是将决裂好坏的评估办法，又信息熵改成平方误差函数，也就是把增益函数改成平方误差增益即可。
假如训练集中第 j 个特色变量 和它的取值 s，作为切分变量和切分点，并定义两个区域、 为找出最优的 j 和 s，对下式求解
进步树模型的性能
在构建决策树的过程中，咱们能看到只有样本不抵触(样本既是正样本，又是负样本)，是肯定能收敛的，代价就是在决策树上增加更多（笼罩样本少的）叶子节点。然而这样的决策树，是齐全没用演绎总结数据的法则，只是相当于把训练集用树的模式给背了下来，对于未训练的数据样本可能齐全不是一回事，这学到的模型实际上是没有意义的。
决策树比拟容易过拟合，因而须要树的构造进行束缚。利用剪枝等办法来砍掉冗余的分支，使得树结构尽量简略，以进步树模型在未训练数据上的预测体现(也就是泛化能力)。除此之外，集成学习(Ensemble Learning)，横向地减少多个树，并利用多个树模型后果综合判断，也是个能进步模型性能罕用办法。常常用在机器学习畛域上的各种较量和比赛上，是个经典的刷榜套路。
集成学习
咱们晓得模型都不是完满的，而是有误差的。而模型的误差能够分成两种，一种是偏差 (Bias) 可了解为与模型预测均值与样本真值的误差，一种是方差 (Variance) 可了解为模型预测值本身的变动幅度。下图形象地了形容这两个概念。
集成学习算法思考的问题就是：<font color=’red’> 多个误差大成果差的个体模型，能不能以某种模式集成起来，变成一个误差变小成果变好的总体模型呢？</font> 这个答案必定是显然的，咱们都晓得人民大众力量大。其背地的思维就是即便有个别模型预测谬误，那么还有其余模型能够纠正回来，正所谓三个臭皮匠胜过一个诸葛亮。
从集成模式上看，次要能够分成两类，一类模型并行集成的 bagging 办法，一类模型串行集成的 boosting 办法。至于为什么能通过这样模式的集成就能提性能，其理论依据是什么？这可由模型总体冀望和方差，与个体模型方差和偏差之间关系，得出严格的数学推导和证实，这里就不开展了。
随机森林
随机森林 (Random Forrest)，一个基于 bagging 办法，把多个决策树集成到一起的模型算法。其外围的算法思维就是，通过多个(低偏差高方差) 个体模型的均值，来形式升高总体方差的学习办法。随机森林算法框架如下图所示。
随机森林构建流程如下:
1. 把原始集上随机只采样 N 份样本数据集，且每份样本数据集随机只采样 M 个特色，失去若干份数据集
2. 在每个数据集上独立构建一颗决策树，失去 N 颗决策树 随机森林应用流程如下:
1. 把待预测的样本数据，输出到 N 个决策数，失去 N 个预测后果
2. 对这些预测后果，以投票 (分类) 或均匀 (回归) 的计算形式最终后果可见，在随机森林外面，每一颗决策树的构建 (训练) 都独立的，他们之间是并行的没有依赖。只是在最初应用 (预测) 时，要把森林上所有树的后果都过一遍，通过大家投票或均匀的形式给出一个 final decision。
梯度晋升决策树
简称 GBDT(Gradient Boosting Decision Tree)，一个基于 boosting 把多颗决策树串联集成一起训练学习的算法，其外围的算法思维是基于残差的学习，通过多个 (低方差高偏差的) 个体模型的叠加求和，来升高总体偏差的学习办法。
假如样本 X 的真值为 30，模型 1 预测后果与真值的残差为 10。为了修补这个残差，须要把样本 X 再送到模型 2，但此时模型 2 训练的指标，并不是样本自身的真值 30，而是以后的残差 10。此时模型 1 和模型 2 相加后，残差曾经从 10 减小 4 了。以雷同的形式再训练模型 3 和模型 4，总体的残差会越来越小，总体后果就是所有模型输入相加之和，如下为 GBDT 的训练过程示意图。
可见，这与 bagging 的随机森林办法齐全不一样。前者模型之间互相独立，只有把子模型一一独自训练完就好了。而后者模型前后之间有依赖的关系，必须是练好上一颗树好后，依据残差再练下一颗，one by one 的形式来训练。那如何实现这样的学习算法呢？GBDT 就是这样的学习算法，其框架图如下：
指标函数构建
咱们晓得对于逻辑回归模型的学习问题，其优化指标就是最小化穿插熵 (CrossEntropy) 损失函数：
因为这函数是个凸函数的，所以这个最小值的求解问题比较简单。只有通过梯度降落法，迭代参数 W 迫近极值，就能使得穿插熵损失函数取到最小值。那么对于 boosting 这样加法模型的学习问题，其优化指标或者说损失函数，这个函数应该是长什么样子的，又是如何构建的呢？
要确定损失函数，首先第一步得确定模型是怎么输入预测值的。假设有曾经训练了 K 颗树，则对于第 i 个样本的以后预测值为：
那么指标函数则就能够这样构建：
表达式左边的为正则项，用来管制模型构造的复杂程度，在决策树模型中，罕用树的叶节点数量、叶子节点的值、以及树的深度来定义之。重点来关注右边的损失函数，应该怎么求解其最小值呢。进一步拆解损失函数，实现损失函数参数化：假设现有 K 颗树，后面的 K - 1 颗树曾经训练好，以后须要训练第 K 颗树。对于输出样本 ，如下图所示：
则指标函数可简化为
当训练第 K 颗树时，前 K - 1 颗树曾经确定下来，所以 可作常数对待，与第 K 颗树无关，故此时指标函数为：
指标函数仍难以优化，利用泰勒级数来近似
泰勒开展只保留前二阶，此时指标函数可写成：
当初最优化的指标参数是 ，所以与 无关的项都能够去掉。令 和为 对于 的一二阶导数，因为前 K - 1 颗树已训练，所以这两个值可算出，可认为是已知的。
故指标函数再简化为:
最优化树参数的求解
决策树的输入函数 f 的，能够这样定义：，其中 q(x)是地位函数，示意样本 x 会落到树的那个地位 (第几个叶子节点)， 示意第 j 个叶子的值。而树结构束缚函数 ，与叶子的值 W 和叶子的个数 T 无关，别离由两个超参数来管制：
故此时指标函数再简化为：
在树状态确定情景下，遍历样本组织模式，可叶子上样本汇合划分，一一汇合模式来遍历，比方下图先叶子节点 1 上的{1,2} 样本，再叶子接上 2 上 {3,5}，如下图：
示意叶子节点 j 上的样本汇合，
则的指标函数写成下模式为：
再令，在树形态确定已知时，这两个都是常数。此时就只剩下 W 一个参数了，而此时的指标函数就成了一个最简略的一元二次函数，这个函数极值点能够间接用通解公式就能够算进去。
最优化树状态的求解
训练数据无限，而树的状态是有限的。有有限多种状态的树，都能把这些训练放入到其叶子节点上。在这里寻找一个最优的，其实就是个典型 NP-hard 问题，很难间接优化。而且树的状态，也很难定义成一个间断的函数，没有条件用梯度降落来求解。那么如何求解之？跟决策树的构建算法一样，沿用贪婪算法思路，遍历所有特色，找以后最优的特色划分办法 F，确定最优树状态。
如上图，假设以后曾经决策树曾经分成了两个叶子点 (框线内)，此时应该不应该通过特色 F 持续决裂，抉择那种划分形式最好？
故通过特色划分办法 F 所造成的树形，使得 最大化，就是以后最优的树形态。为了算法实现的便当，咱们限度了特色划分的模式，对于每一步叶子节点划分操作，都只能决裂左右两个叶子节点，以确保树是二叉的。所以最终有：
援用
XGBoost：A Scalable Tree Boosting System. KDD 2016 ChenTianqi
【机器学习】决策树（中）https://zhuanlan.zhihu.com/p/…
欢送关注凹凸实验室博客：aotu.io
或者关注凹凸实验室公众号（AOTULabs），不定时推送文章。