上述介绍的线性模型对线性关系有很好的拟合效果，对于一些非线性关系也可以通过寻找联系函数来解决问题，但是对于其他难以找到合适联系函数的非线性关系来说，线性模型很难取得好的效果。

树模型是一个基于特征空间划分的具有树形分支结构的机器学习算法模型。将数据集按照特征空间（属性）进行分割，产生具体的分类规则，树模型具有良好的可解释性。并且树模型基于已有数据的划分产生规则，因此能够很好地表达非线性关系，以及能够同时处理离散和连续变量，适用于大多数的分类和回归问题，因此树模型几乎是使用最广泛的机器学习算法。

1．基本概念

决策树是一种常用的有监督学习算法，主要用于解决分类问题。决策树的学习过程就是利用数据集构建树的过程，通过数据的某个属性值将数据划分为若干个子数据集，再递归地对子数据集进行划分，直到每个子数据集只剩下一类数据或者所有属性都划分完毕。

例如，在一个判断公司员工是否为管理层的分类问题中，数据集为收集到的各员工的基本信息（如工作年龄、收入、是否为公司股东等），通过对数据集中的属性值进行划分可以产生一颗具有树形结构的决策流程图。如图2.7所示，决策树的每一个非树叶节点对应一个属性的测试，每一个分支表示一次决策，每个分支产生两个或更多的子树，每个叶子节点表示最终的分类判断。决策树的判断过程就是执行从根节点到叶子节点的流程，给定一个测试点 x ，按照决策树流程中的属性进行判断，直到达到叶子节点输出最终的预测结果。

通过构建这样一颗决策树分类器，最终可以找到一个可视化的分类规则，这很容易理解。并且决策树对数据要求不高，只需要对数据进行简单的离散化处理，就可以形成可分类的离散变量。它能够很好地处理高维数据，受离群点和缺失值的影响较小。

决策树通过简单的改动还能完成回归任务。在分类任务中，最终标签是一个类别属性，叶子节点可以直接存储该属性值，而在回归任务中，最终标签输出的是连续值，可以在叶子节点存储该分类下所有数据的标签值，最终输出这些数据的平均值（或者中位数等）。

2．分裂策略

如何选择属性并进行决策分裂是决策树算法的关键，各种决策树算法的主要区别也在于此。理想情况是每经过一次分裂得到的子树尽可能纯（即落在一个给定分区的所有数据的标签都相同，或者标签值接近）。

属性选择度量是一种选择分裂的准则，在每一次分裂的时候，通过预先设定的属性选择度量来选择该次分裂的属性。常用的属性选择度量有信息增益、增益率和基尼指数（Gini指数）。下面将一一介绍这三种属性选择度量。

（1）信息增益

信息增益是ID3方法的属性选择度量。该度量方法来源于香农在信息论方面的研究。对于一个存放所有数据的数据集 D ，该数据集中有 C ₁ ～ C _m 共 m 种标签值，则 D 中的期望信息由以下公示表示：

其中， p _i 是 D 中任意元组属于类 C _i 的概率，用类别 C _i 的元组个数除以元组总数的值来估计。使用以2为底数的对数是因为信息是用二进制编码的，Info( D )也表示识别 D 中元组的类别号所需要的平均信息量，因此该式也可称为 D 的熵。利用这个公式可表示数据集 D 的混乱程度，数据集 D 中数据类别越多，该值越大，信息量越大。

假设经过属性 A 可将数据集 D 划分为 v 个子数据集{ D ₁ ， D ₂ ，…， D _v }，每个子数据集表示经过该次划分产生的子节点或子树，那么经过划分之后数据集 D 的信息量可由各子数据集 D _i 的信息量的和表示，即：

信息增益就是数据集经过一次属性划分后，该数据集的信息量变化，即：

经过划分后的数据集越纯，其信息量越少，则该属性划分之后的信息增益就越大，直到最后每一个分支下都只有一个类别属性，则此时数据集信息量就达到零。于是在每次分裂过程前，先计算各个属性经过划分后的信息增益，选择最大的信息增益对应的属性进行划分，直到最后信息量达到零或者所有属性划分完毕。

信息增益的度量偏向于产生多个分裂节点的属性，也就是倾向于选择具有大量值的属性。例如，假设有一个属性，数据集中所有数据在该属性的值均不相同，那么通过一次划分就可以将数据集全部划分完毕，每颗子树只含有一个数据元组，信息量可以直接降低到零，信息增益最大，但是很显然，这样的决策树效果并不好。

（2）增益率

随后出现的C4.5方法使用的增益率度量，就是基于这样的想法产生的，作为信息增益度量的补充，试图克服这样的偏向性。它使用“分裂信息”的概念将信息增益规范化，分裂信息的定义如下：

分裂信息表示经过一次划分产生 v 个输出产生的信息，增益率则可以定义为

增益率可以单独作为属性选择度量进行属性选择，但是随着选择更大的增益率，分裂信息将趋于零，增益率的变化将非常剧烈，变得不稳定，因此可以将增益率与信息增益两个属性选择度量结合起来使用，在信息增益较大的属性中则选择增益率更高的属性。

（3）基尼指数

基尼指数是CART方法中使用的属性选择度量，基尼指数直接度量数据集 D 的不纯度，定义如下：

其中， p _i 表示数据集 D 中属于类别 C _i 的概率， m 表示总的类别数量。Gini( A )表示经过一次划分之后Gini指数的降低程度，也即是不纯度的降低，并且选择最大化降低不纯的属性进行划分。

这三种度量是较为常用的属性选择度量，它们有各自的倾向性和缺点，比如信息增益倾向于选择有很多值的属性，增益率倾向于不平衡的划分，即某个子数据集比其他子数据集小得多，基尼指数则倾向于多值属性和分裂相等大小的数据集。在具体使用的过程中可以根据实际数据的分布使用某种或者结合多种属性选择增益。

3．剪枝处理

随着问题复杂度的增加，决策树模型也将变得更加复杂，需要的属性更多，但是随之而来就会产生过拟合的问题。

决策树学习过程中，为了尽可能正确地将数据集进行分类，会造成决策树分支过多，就会产生把样本学习得“太好”的问题，以至于把训练数据集中的随机误差产生的结论当作普遍规律去适用，于是就导致了过拟合问题。

剪枝就是主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略分为“预剪枝”和“后剪枝”。所谓的预剪枝，就是在决策树生成过程中，对每个分裂节点进行预先估计，如果当前节点的划分不能带来更好的泛化性能（泛化能力就是指对没有采样的数据集的适用性），则停止此次分裂。后剪枝是先按照正常规则生成一棵决策树，然后自底向上进行检查，如果将某个节点的子树直接替换为树叶节点（即取消该节点的属性划分），能带来泛化能力的提升，则将子树替换为树叶节点。

4．集成学习方法

一棵比较小、简单的决策树算法，会获得一个具有低方差、高偏差的模型，而复杂的决策树算法，可以获得低偏差，但可能由泛化误差带来高方差的影响。好的模型应该在偏差和方差两者之间保持平衡。集成学习方法就是一种执行这种权衡分析的方法。

集成学习方法是使用一组具有预测能力的模型，以达到更好的准确度和模型稳定性。集成学习方法是目前提升提升树模型准确率最好的方法。常用的集成学习方法有装袋（Bagging）、提升（Boosting）和堆叠（Stacking），这一节将对这三种集成学习方法一一进行介绍。

（1）装袋（Bagging）

装袋是一种基于自采样（有放回的采样）的方法，通过结合几个模型降低泛化误差的技术，主要想法是分别训练几个不同的模型，然后让所有模型表决测试样例的输出。

具体的步骤如图2.8所示，首先从一个数据集 D 中有放回地采样多个数据子集{ D ₁ , D ₂ ,…, D _t }，然后对每一个数据子集 D _i 训练出一个分类器模型 M _i ，最后结合多个分类器模型得出最终的模型 M 。最后可以通过平均值、投票等方式来实现多个模型的组合。根据计算，这种有放回的采样方法最终会有63.2%的样本出现在采样集中，而剩下的36.8%是一次都没有被采样的样本，可以作为验证集对模型的泛化性能进行估计。

随机森林（Random Forest）算法采用的就是这种方式的学习算法。从数据量为 N 的数据集中，随机选择 n 个数据样本，假设每个数据样本有 M 个属性，然后对这 n 个数据样本随机选择 m ( m << M )个属性训练出一个决策树模型，重复此操作 t 次得到 t 棵决策树，形成“森林”，最后根据随机森林的每棵树的结果，进行投票，得票数最多的结果就是最终的输出结果。

随机森林使用随机采用的装袋方法降低模型的泛化误差，此外，由于它在处理时是随机选择部分属性来构建树的，随机森林可以有效率地处理高维度数据，是一种有效的降维方法。其缺点在于对回归问题的精准度不够。

（2）提升（Boosting）

提升（Boosting）方法和装袋（Bagging）方法的工作思路相似：构建一系列弱学习器（也叫作基学习器），将它们组合起来得到一个性能更好的强学习器。然而，与多次重复采样以减小方差的装袋法不同，提升法希望以一种适应性很强的方式拟合多个弱学习器，每个模型在拟合的过程中，会更加重视那些之前的学习器处理得很糟糕的数据。提升法是一个序列化的过程，后续的学习器会矫正之前学习器的预测结果，也就是说，之后的学习器依赖于之前的学习器。

具体实现过程如图2.9所示，首先使用各种不同的学习算法（不限于决策树）训练得到不同的学习器，称为基学习器，每个基学习器代表一个弱规则。然后依次使用弱分类器对数据进行测试，在学习器1中有3个数据点预测错误，那么在下一轮的学习器2中，这些数据点将赋有更高的权重，再对学习器2中的错误预测点增加权重代入下一个学习器，以此迭代，直到达到最大的精度。于是就可以将几个简单的弱学习器构成一个规则强大的学习器。

直观地说，每个基学习器通过增加权重的方式，把注意力集中在目前最难拟合的观测数据上，这样一来，最终便获得了一个具有较低偏差的强学习器。由于提升法的重点在于减小偏差，用于提升法的基学习器通常是具有低方差高偏置的模型（例如，层数较少的决策树模型）。由于要使用多个学习器进行运算，提升法的计算开销非常大，用简单的基学习器也可以降低部分计算开销。

自适应提升算法（AdaBoost）就是提升法的代表算法，针对同一个训练集训练不同的学习器（弱学习器），然后进行分类，对于分类正确的样本权值低，分类错误的样本权值高（通常是边界附近的样本），最后的分类器是之前多个弱分类器的线性叠加（加权组合）。

（3）堆叠（Stacking）

上述两种集成学习方法的核心在于使用多个弱学习器的组合形成一个强学习器，组合方式可以是投票或者线性组合，堆叠法采用了另一种策略，用另一个学习算法将基学习器的结果结合到一起。

具体实现过程就是，先用不同的学习算法对数据集训练出多个学习器，称为初级学习器，然后将所有数据代入到初级学习器中，得到预测结果，再把预测结果作为输入代入另一个学习算法，训练得到次级学习器。有研究表明，用多响应线性回归作为次级学习算法的效果较好。 J5qgmgVklShRNGC3TjC8PxD0yCTdBlHSsiVGTlSqIPtE1Ym9+/yADSAAP65bHHXm