3.5 决策树与随机森林

已知输入变量与输出变量均为连续变量的预测问题被称为回归问题；输出变量为有限个离散变量的预测问题称为分类问题。决策树是一种常见的分类与回归方法，因其模型呈树状结构而得名。决策树算法的思路简明易懂，但也包含丰富的内容：随机森林、GBDT、Xgboost等流行算法都是在其模型上的延伸。本节主要介绍简单分类决策树的概念、树的实施方法以及基本的算法实现。

3.5.1 简要介绍决策树是什么

决策树是一种描述对实例进行分类的结构。以判断一个人爱不爱吃四川火锅为例，这样的思考过程就像一个决策树，如图3-1所示。

通俗地讲，其中每个分支代表一个新的决策事件，从根部开始，每条分支都会在最终走到“爱吃火锅”或“不爱火锅”的分类标签里。

严格来说，决策树由结点与有向边共同构成树形结构；其中结点又分为内部结点（如图3-1中的圆形结点）、叶结点（如图3-1中的方形结点），它们分别表示特征、类别。决策树要解决的问题，本质上就是从训练数据中找到一组“最佳”的分类规则，这个树可能有多个，也可能没有，“最佳”则用损失函数来靠近。决策树的核心思想就是，找到一个最优特征，对该特征进行最好的划分，并且重复上述步骤，不断丰富内部结点，直到满足指定条件。那么如何定义并找到最优特征？如何进行最好的划分？这些就是决策树实施过程需要考虑的主要问题。

决策树的实施包括什么？

决策树的实施过程主要包括特征选择、决策树的生成与树的修剪。

1.特征选择

由于通常实际项目中的特征变量数都会远远大于两个，此时对多个特征进行先后顺序不同的决策时会有不同的结果与准确率，所以就需要“特征选择”来决定当前应选用哪个特征来划分。直观来讲，当下特征中对分类“最有效”的特征应该优先选择；如四川火锅的案例中，“是否爱吃辣”明显比“是否有洁癖”在判断是否爱吃火锅的问题上更有代表性，所以“是否爱吃辣”这个特征应在“是否有洁癖”的前面。

从定量的角度，信息增益与信息增益比就是可以表示特征“有效性”的指标。

（1）熵。

熵在第2章已经叙述过了，现在重新从决策树的角度讲解一遍。热力学中用“熵”的概念表示体系混乱程度；在概率统计中，“熵”可以用来表示随机变量不确定性的度量。

香农曾说过，信息是用来消除随机不确定性的东西。回到分类问题本身，对于用决策树分类前的数据，因为没有其类别的任何信息，此时数据的不确定性是最大的，熵也是最大的；对于决策树分类后的数据，理论上，特征信息被最有效地利用了，数据的随机不确定性也得到最大程度的消除，数据最后被安排在几种类别中，此时数据的不确定性是最小的，即熵是最小的；而过程中每用一个特征进行一次决策，就能降低一次数据的熵。自然地，当下最优的特征就是使熵降低最多的特征。这就是信息增益的主要思想。

对于一个离散的随机变量X，其概率分布（P）与熵（H）的定义为：

通常上式中的log底取为2或自然对数e。由公式可以看到，熵是一个恒为非负的值。当变量X为常数时，H(X)=0（因为这时P(X)=1），表示常数信息混乱程度是最小的。

若另有一随机变量Y，H(Y|X)则表示在已知随机变量X的条件下随机变量Y的不确定程度，称为条件熵，定义为：

在实际中，熵与条件熵是用样本数据矩估计计算的，被称为经验熵与条件经验熵。需要注意的是，若随机变量X存在概率α_i=0，为了可计算性，直接令其对数值为0。

（2）信息增益。

某一特征A对数据集D的信息增益g(D,A)定义为：

g(D,A)=H(D)-H(D|A)

其中的熵均为经验熵。因为H(D|A)≤H(D)恒成立，所以信息增益g(D,A)一定是非负的。

那么如何理解信息增益呢？根据定义，信息增益可以视作某一特征对数据集混乱程度降低的贡献程度：即当某个特征确定下来后，数据集熵的降低得越明显，说明该特征对数据集提供了更多的信息，贡献度越大。

一般地，这个差值也称为互信息。

根据信息增益的准则，对于（C₁,C₂,…,C_k）共k种类别的决策树问题，假设当下还剩余（A₁,A₂,…,A_s）共s种特征，则特征筛选实施步骤如下：

a）用矩估计法计算当下数据集D的经验熵：

b）用矩估计法计算某一特征A对数据集D的条件熵：

其中m表示训练数据集中该特征所不同取值的数量，D_i表示D中A=i的数据量，D_ik表示D中A=i且属于C_k类的数据量。

c）对所有的特征（A₁,A₂,…,A_s）计算H(D|A_i),i=1,2,…,s，得到信息增益g(D|A_i),i=1,2,…,s。选出使信息增益最大的特征A₀：

A₀=arg max(g(D,A_i))

（3）信息增益比。

与信息增益相仿，信息增益比也可以衡量某特征对数据的熵的影响大小。

某一特征A对数据集D的信息增益g(D|A)定义为：

其中H_A(D)所有数据关于特征A的熵，即。特征A的取值越多（m越大），H_A(D)往往越大。因此，信息增益比可以视为信息增益的“标准化”，相对于信息增益的准则，信息增益比可以减弱对取值较多的特征的偏好性。

2.决策树的生成

在确定了特征选择的方法后，树就可以一层一层生成了。本节介绍的ID3算法与C4.5算法是由Quinlan分别在1986年与1993年提出的。

（1）ID3算法。

ID3算法在特征选择的过程，用上文所述的信息增益原则进行；在树的生成过程，对所选取的特征的不同取值进行划分；最后建立一棵决策树。值得注意的是在决策树生成前要先设定好一个阈值，当余下所有特征的信息增益小于这个阈值时，树的生长就完成了。

（2）C4.5算法。

C4.5算法是ID3算法的延伸，在特征选择的过程中，用信息增益比的原则进行，这是与ID3算法不同的地方；在树的生成过程，对所选取的特征的不同取值进行划分；最后建立一棵决策树。

3.决策树的修剪

根据上述算法生成的决策树，由于考虑到每个特征的每种可能取值，容易出现过拟合，即对训练数据的分类准确率很高，对测试数据分类的准确率比较低。这是决策树的算法特征所决定的，所以对决策树的修剪就显得非常重要。

本文介绍的是用极小化损失函数进行剪枝的方法。损失函数如下所示：

其中T表示确定的一棵决策树，该数共有个叶子结点，每个结点下包含训练样本N_t个，H_t(T)表示训练样本N_t的经验熵。

可以看到损失函数包括两部分：决策树分类结果的熵与决策树的叶子结点数量。极小化损失函数时，既需要使得决策树分类后的数据熵很小，同时也需要满足决策树的叶子结点不能太多，即决策树不能太大。其中系数α表示对两者的平衡，α越大，就越倾向于牺牲一定的模型准确率以减少树的叶子结点数量；反之相反。

剪枝的具体步骤如下：

1）计算每个结点的经验熵。

2）计算损失函数；记当前树的某个叶子结点剪掉前后的树的损失函数，记为C_α(T_前)与C_α(T_后)，若C_α(T_前)≥C_α(T_后)，则剪掉该叶子结点，其父结点成为新的叶子结点，得到一颗新的决策树。

3）对决策树的叶子结点重复 2）的过程，直至不能再剪裁为止。

3.5.2 决策树算法的优点和缺点是什么

优点：

1）思路简明，计算速度快。

2）决策树的分类规则非常清晰，能够看到哪些特征比较重要，具有较强可解释性。能够同时处理数据型和常规型属性。很多算法要求数据属性是统一的。

3）对缺失值不敏感，可以处理不相关特征数据。

4）不需要任何参数假设。

缺点：

1）对连续的特征变量的处理效果不好，因为算法模型中主要都是对分类变量的特征讨论的，例如树的生成时将某一特征的所有属性都生成子叶。

2）在树的生成过程中，对某一特征进行划分时会将该特征每一可能的取值分为一类，就会使得树对取值较多的连续变量过于敏感；例如，如果某特征的每一取值的样本都是唯一的，即是同一类的，用该特征进行划分就会有明显的信息增益。但实际中，这并不是最有意义的特征。

3）非常容易过拟合。

3.5.3 试简要介绍随机森林

由于决策树分类器的缺点和分类方法自身较为单薄，Leo Breiman和Adele Cutler于2001年提出了随机森林算法，随机森林，顾名思义，就是指利用多棵决策树对样本进行训练并预测的一种方法。

随机森林的思想可以用一个简单例子来解释。假设多位评委为饭店评定星级，每位评委都应独立地对餐品做出“五级”或“四级”的评价，最终该饭店的星级，则由所有评委的评价结果决定，最多评委评价的级别就是该饭店的星级。这里，整个评委团队就像是随机森林的算法模型，饭店则是待测对象，饭店的最终星级由评委团队中每一位评委的投票结果决定。

随机森林包含多个决策树，就算每棵树的分类能力比较弱，或者存在误差，但依靠大量决策树的投票结果，误差会相对抵消，从而使得效果较好的“决策树”的分类结果表现出来。这就是随机森林算法的思想。

同样是决策树，随机森林模型既可以处理回归问题，也可以处理分类问题。原因是在随机森林的实施过程中，使用的是不同于上述简单分类决策树的CART决策树。

简要介绍随机森林的实施步骤与特点。

1.CART决策树

在介绍随机森林的实验步骤之前，需要先简要介绍一下CART决策树。CART模型的全称是分类与回归树模型，是在1984年由Breiman提出。不同于简单分类决策树，CART决策树是二叉树，即要求对每次某个特征划分时只能分为两类，但会对该特征的不同取值进行多次划分，以保证信息得到充分使用。

下面分别介绍回归树与分类树是如何进行特征选择与树的生成的。

（1）回归树

已知决策树本质上是建立一种划分特征空间的规则，一个特征空间对应着一个输出值。则回归树模型可写为：

其中R_k表示一划分好的特征空间域，一共有K个这样的划分，每一个划分的特征空间的输出值为c_k，c_k的取值为属于特征空间R_k的样本点的输出值的平均水平。则为示性函数。

特征选择和树的生成其实就是对特征空间建立划分规则的过程。不同于简单分类决策树，回归树始终满足如下损失函数，并以此为原则进行特征空间的划分：

那怎么认识这个损失函数呢？

首先，由于CART决策树是二叉树，所以每次划分会把特征空间划分为两部分，损失函数就是两部分数据的误差的和，这两部分特征空间分别记为R₁(j,s)与R₂(j,s)。为什么划分好的特征空间会与（j,s)有关呢？假设在一结点选择特征x^j以及其某一取值s，划分时则将特征空间分为{x^j≥s}与{x^j＜s}两部分。所以特征空间是由（j,s)共同确定的。最小化损失函数是要使得两部分的误差都很小。

然后，以第一个部分的误差为例（左右两部分的误差形式是一样的），来看怎么定义一个特征空间内的样本点的误差。根据回归决策树的性质，一个特征范围内的取值是一样的，所以误差才有的形式。而最合理的c₁的取值应该是使得改组内方差最小的值（其实就是均值）。这也和回归树模型中c_k的取值方法是统一的。

算法步骤如下：

1）遍历特征j，对每个特征j，遍历其可能的取值s，并求解以下损失函数：

确定一对(j,s)使得损失函数最小。

2）用a中确定的(j,s)将数据集划分为两部分：

R₁(j,s)={x^j≥s},R₂(j,s)={x^j＜s}

并计算每部分的输出值：

3）对两个新的结点重复a、b的步骤，直到满足停止条件。

（2）分类树

类似于简单分类决策树的熵，分类树用基尼指数来表示信息的混乱程度。基尼指数的定义如下：

其中K表示类数。可以看到，基尼指数可能的取值范围是[0,1)，当p_k=1时取到最小值0，此时信息混乱程度是最低的。基尼指数越大，表示信息越混乱，这和熵的定义是一致的。

对应于经验熵，一个样本集合D的“经验”基尼指数为：

而对应于条件熵，集合D在特征j=s给定下的“条件”基尼指数为：

其中表示样本集D根据特征j=s被分为R₁={x^j≥s}、R₂={x^j＜s}两部分；其基尼指数就是两部分数据集的基尼指数的加权平均，其权重为数据集大小的占比。

算法步骤如下：

用基尼指数代替熵，用简单分类决策树同样的步骤就是CART分类树的实施步骤。具体如下。

1）遍历特征j，对每个特征j，遍历其可能的取值s，并求解“条件”基尼指数。

2）选择1）中使得“条件”基尼指数最小的(j,s)，将样本集划分为两部分。

3）对两个结点的数据重复1）和2）的步骤，直至满足停止条件。最终每个特征空间的点中所含样本点最多的类别为该特征空间对应的类别。

2.随机森林的实施步骤

1）随机有放回地从N个训练样本中抽取N个样本，作为生成树的训练集。

2）对K个特征随机选k个作为特征子集，在对树做特征选择时，从特征子集中选择最优的特征。

3）让树做最大程度的生长，不做树的修剪。

4）重复1）～3）的步骤T次，建立T棵决策树；若是分类问题，则某样本T棵决策树的投票结果即为最终类别；若是回归问题，则T棵决策树的回归结果的算术平均值即为最终结果。

3.随机森林的几个特点

1）采用Bootstrap抽样法。原因在于：若不如此，会使得每棵树的分类结果一样；这样失去了树之间的独立性，随机森林的“投票”思想也就失去了意义。

2）每次随机从特征中选取k≤K个作为特征子集建立决策树。一方面，可以降低复杂度，加快算法的实施过程；另一方面，可以保证树与树之间有更好的独立性。实际上当k=K时，这里的决策树就等价于普通的CART决策树；k≤K亦可增强模型的泛化能力。

3）不需要对树进行剪裁。已知剪裁是为了避免决策树的过拟合；但由于随机森林的实施过程对样本和特征都进行了随机选择，再加上最终投票的形式，不剪枝也不会出现过拟合，所以就不必剪裁了。

随机森林的简单实现如下。

Python中sklearn的RandomForest可以用来建立随机森林模型。具体如下。

其中RandomForestRegressor()包含的参数如下。

criterion："gini"or"entropy"，表示是使用gini（基尼指数）还是entropy（信息增益）来进行特征选择。默认为“gini”。

max_depth：(default=None)，表示单棵决策树的最大深度，如果max_leaf_nodes参数指定，则忽略。默认None表示不会打断树的生长，直至每个叶结点的所有样本都属于同一类别。

min_samples_split：表示树的生成时，对特征划分结点时，每个划分的最少样本数。若样本点低于这个数目，则停止该结点的生长。与max_depth共同作用。

min_samples_leaf：表示叶子结点的最少样本数。

max_leaf_nodes：（default=None）表示叶子结点的最大样本数。

n_estimators：表示森林容量，决策树的个数。默认为10。

bootstrap：表示是否有放回的采样。默认为=True，False表示弃用所有子模型样本。

oob_score：表示是否计算袋外得分，默认为False。

n_jobs=1：并行job个数（并行学习的内容下一章有介绍）。默认为1，表示不并行；-1表示CPU有多少core，就启动多少job；还可以设为自定义整数。

Verbose：表示是否显示任务进程。默认为0，表示不显示模型训练过程；1表示偶尔输出训练过程；＞!表示每个子模型都输出；还可以设为自定义整数。

3.5.4 如何做随机森林参数的选择

在实施步骤中包含两个参数：特征子集的数量和需建立的决策树数量T。

对于后者，由投票的思想，理论上T应该越大越好；但由于会影响算法的复杂度，应选择适当的T使得准确率与复杂度达到平衡。

对于前者，已知当k较大时，树与树相关性比较强，会影响模型的准确率；k较小时，单棵树的分类能力太差，也会影响模型的准确率。经验上一般把特征数量的对数作为特征子集的数量。

为了更好地取得合适的k，通常会用袋外错误率最低的方法。

实际上，使用Bootstrap法确定每棵树的训练集时，对于第i棵树，约有三分之一的样本没有参与树的生成；这些样本被称为这棵树的袋外样本（oob样本）。由此，袋外错误率（out-of-bag error）的定义如下：

其中N₁表示对于某个样本，它作为oob样本的树对它的分类错误的棵数，N表示对于某个样本，计算它作为oob样本的树的数量。可证明oob error是随机森林泛化误差的一个无偏估计。

3.5.5 试简要介绍随机森林的优缺点

优点：

1）在当前所有算法中，有较好的准确率。

2）可高度并行化，对于大数据大样本很有优势。

3）实现过程相对简单。

4）模型较稳健，对部分的特征缺失不敏感。

5）随机森林算法能够降低方差。为什么能降低方差呢？因为随机森林的预测输出值是多课决策树的均值，如果有n个独立同分布的随机变量x_i，它们的方差都为σ²，则它们的均值的方差为。

缺点：

1）对于噪音比较大的样本集，容易过拟合。

2）取值划分较多的特征容易对模型产生更大的影响，从而影响模型的效果。

常见面试笔试题：随机森林的“随机性”表现在哪里？比决策树好在哪里？

分析：“随机性”表现在两方面：一方面，每棵决策树的样本是经过Bootstrap随机选取的；另一方，每棵决策树生成所用到的特征是从所有特征集中随机选取的。

相较于决策树，正因为随机森林的“随机性”，其在过拟合问题上有所改善，极大地提高了分类模型的准确率。

3.5.6 决策树中C4.5算法优化了ID3算法的什么缺点

ID3算法使用信息增益来选择用于分组的变量，但是这样可能会出现偏向于取值比较多的变量的情况，并使得模型预测的准确率下降。而C4.5利用信息增益率能够有效地解决上述ID3使用信息增益时出现的问题。

C4.5算法在构造决策树的过程中可以进行相应的剪枝，但是ID3算法没有。并且C4.5算法在对数据预处理的时候还会对连续型的变量进行离散化处理。