简介神经网络模型，尤其是深度神经网络模型，自AlexNet在ImagenetChallenge2012一鸣惊人以来，无疑是MachineLearningResearch上最靓的仔。有如此多的进步和突破，科学家和工程师都喜欢它。机器学习研究发展至今。除了神经网络模型的方法路径之外，还有很多不同的方法路径，比如贝叶斯算法、遗传算法、支持向量机等，这些经典算法在很多场景中都有使用。本文介绍的树模型也是一种非常经典的机器学习算法，在推荐系统中经常可以看到。这个树模型是如何构建和实现的，其核心思想是什么？树模型的效果不够好，可以用什么样的思路和方法来改进呢？本文主要包括以下三个方面：1.决策树2.集成学习3.随机森林和梯度提升决策树决策树决策树（DecisionTree）是树模型中最简单的模型，后面会介绍随机深度森林和梯度提升决策树两种模型的基础。使用决策树算法，我们可以在历史约会数据集上画出这样一棵树。这棵树上的叶子节点代表结论，非叶子节点代表基础。样本根据自身特征从根节点开始，根据不同的决策基础分裂成子节点，直到叶节点只包含一个类别（即一个结论）。假设上表中有一个数据集，那么可以根据这样的数据构建这样一个决策树，如下图所示。信息熵与基尼不纯度可见，构建决策树的关键是“分裂”，不断分裂成子节点，直到叶子节点（不能分裂）。那么这个重点划分的标准和方法是什么，怎么划分才是最好最合适的呢？显然，正负样本是可以完全分开的，一边是正一边是负，两边都收集起来很“坚决”的是最好的。这里的确定性是指一个事件只有一种结果的可能性，那么如何量化“确定性”这个指标，一般有两种方法：信息熵和基尼不纯度。信息熵熵是用来衡量信息不确定性的指标。其计算方法如下：其中P(X=i)是随机变量X取值i的概率。基尼杂质实际上是信息熵的近似简化计算，因为经过泰勒展开后，高阶项近似为0，可以忽略不计，只保留一阶项1-P(X=i)代表的地方所选样本是第k类的概率。从公式上看，Giniimpurity可以理解为从数据集D中随机抽取两个样本的概率，这两个样本只是属于不同的类别。信息熵和基尼不纯度都可以客观具体地量化“不确定性”。这两个指标越大，反映事物的不确定程度越高。例如，有三枚硬币。第一枚硬币正反面质量完全均衡，抛出正面朝上的概率相同。第二枚硬币的质量比背面大，抛出正面的概率远大于反面。正面。三枚硬币中，第三枚硬币的不确定度最低，因为它没有不确定性，抛头颅是必然事件；第一个硬币的不确定度最高，没法确定抛出第二个硬币的不确定度第二，因为它抛出正面朝上的概率比较大，可以比较确定。构建分类树通过“不确定性”的量化方法，我们用这些指标来指导我们应该选择哪些特征以及如何对特征进行分叉，从而保证每一步“分裂”都是最优的，并不断迭代直到叶节点直到。显然，这个决策树的构建算法是一个贪心算法。考虑到算法实现的问题，决策树最好是二叉的而不是多叉的，所以我们一般使用二叉CART（ClassificationAndRegressionTree）算法来构建决策树。以约会数据集D为例，Gini(D)=0.5，分为两组d1，d2，标签0和1代表no和yes。Ginigain，如下表所示，我们使用Ginigain来选择特征并确定它们的最优分叉点。可以看出，基于温度特性，当分叉点为26.5时，数据集D被分为两组，得到最大的基尼增益。重复这一步，继续分裂d1和d2，直到集合不能再分裂，或者基尼增益小于等于0。构建回归树决策树用于回归问题，思路是一样的作为分类问题。只需要将分裂和信息熵的评价方法改为平方误差函数，即将增益函数改为平方误差增益即可。假设训练集中的第j个特征变量及其取值s作为分割变量和分割点，定义两个区域。为了找到最优的j和s，求解下面的公式来提高树模型的性能在构建决策树的过程中，我们可以看到只要样本不冲突（样本既是正样本和负样本），它肯定会收敛。成本是向决策树添加更多的叶节点（覆盖更少的样本）。.但是这样的决策树对于总结数据的规律是完全没有用的。正好相当于把训练集以树的形式来记忆。对于未经训练的数据样本可能不是一回事。学到的模型其实上面是没有意义的。决策树比较容易过拟合，所以需要对树的结构进行约束。使用剪枝等方法剪掉多余的分支，使树结构尽可能简单，从而提高树模型对未训练数据的预测性能（即泛化能力）。此外，集成学习（EnsembleLearning），横向添加多棵树，利用多棵树模型结果进行综合判断，也是提升模型性能的常用方法。它经常被用在机器学习领域的各种竞赛和竞赛中。这是排名的经典例程。集成学习我们知道模型并不完美，而是存在错误。模型的误差可以分为两种，一种是偏差（Bias），可以理解为模型预测的均值与样本真实值之间的误差，另一种是方差（方差），可以理解为模型预测值本身的变化范围。下图形象地描述了这两个概念。集成学习算法的问题是：多个误差大、效果差的个体模型是否可以通过某种形式进行集成，成为一个误差更小、效果更好的整体模型？答案肯定是显而易见的，我们都知道人民群众是有力量的。其背后的想法是，即使某些模型在预测中出现错误，也有其他模型可以纠正。俗话说，三个皮匠胜过一个诸葛亮。从集成形式来看，可以分为两类，一类是模型并行集成的bagging方法，一类是模型串行集成的boosting方法。至于为什么可以通过这样的整合形式来提升性能，其理论依据是什么？这可以从模型的整体期望和方差、个体模型的方差和偏差之间的关系推导出来，可以得到严格的数学推导和证明，这里不再展开。RandomForestRandomForrest（RandomForrest），一种基于bagging方法融合多棵决策树的模型算法。其核心算法思想是通过多个（低偏差和高方差）个体模型的均值来降低学习方法的整体方差。随机森林算法的框架如下图所示。随机森林构建过程如下：1、从原始集合中随机抽取N个样本数据集，每个样本数据集随机只抽取M个特征，得到若干个数据集。2.在每个数据集上独立构建一个数据集决策树，得到N个决策树Randomforest采用以下过程：1.将待预测的样本数据输入N个决策数，得到N个预测结果。2.对于这些预测结果，采用投票（classify）或平均（Regression）的计算方法得到最终结果可以看出，在随机森林中，每棵决策树的构建（训练）都是独立的，不存在依赖关系它们之间并联。只是在最后使用（预测）的时候，必须把森林上所有树的结果都过一遍，通过投票或者平均的方式给出最终的决定。梯度提升决策树（GradientBoostingDecisionTree）简称GBDT（GradientBoostingDecisionTree），一种基于提升的算法，将多个决策树串联起来进行训练和学习。其核心算法思想是基于残差学习。)个体模型的叠加求和以减少整体偏差的学习方法。假设样本X的真实值为30，模型1的预测结果与真实值的残差为10，为了修复这个残差，需要将样本X再次送入模型2，但此时此时，模型2训练的目标不是样本本身的真实值30，而是当前残差10。此时加入模型1和模型2后，残差已经从10减少到4。再训练Model3和Model4同理，整体的残差会越来越小，整体的结果就是所有模型输出的总和。下面是GBDT的训练过程示意图。可以看出，这和随机森林的bagging方法是完全不同的。前面的模型是相互独立的，只要子模型一个一个单独训练即可。后一种模式是前后依赖关系。必须在上一棵树训练完后，一棵一棵地训练，然后再根据残差训练下一棵。那么如何实现这样的学习算法呢？GBDT就是这样一种学习算法，其框架图如下：目标函数构造值求解问题比较简单。只要通过梯度下降法使迭代参数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形成的树形最大化，即为当前最优树形。为了算法实现的方便，我们限制了特征划分的形式。对于每一步的叶节点划分操作，只能划分左右叶节点，保证树是二叉的。所以最后有：QuoteXGBoost:AScalableTreeBoostingSystem。KDD2016ChenTianqi[机器学习]决策树（中）https://zhuanlan.zhihu.com/p/...欢迎关注傲兔实验室博客：aotu.io或关注傲兔实验室公众号（傲兔实验室），不定时推送文章。
