决策树与随机森林

1.首先什么是树模型？

首先，在了解树模型之前，自然想到树模型和线性模型有什么区别呢？其中最重要的是，树形模型是一个一个特征进行处理，之前线性模型是所有特征给予权重相加得到一个新的值。决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割（输入特征x与logit之间是线性的，除非对x进行多维映射），而决策树可以找到非线性分割。

而树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。树模型拟合出来的函数其实是分区间的阶梯函数。

决策树学习：采用自顶向下的递归的方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处熵值为0（叶节点中的实例都属于一类）。

2.决策树

决策树模型是一种树形结构，由一系列节点组成，每一个节点代表一个特征和相应的决策规则。是基于特征对实例进行分类或回归的过程，即根据某个特征把数据分划分到若干个子区域(子树)，再对子区域递归划分，直到满足某个条件则停止划分并作为叶子节点，不满足条件则继续递归划分。

摘自知乎：https://zhuanlan.zhihu.com/p/74345351

如图一个简单的决策树分类模型：

• 根节点：最顶层的节点，也是最重要的节点。如图中“是否去健身房”
• 叶子节点：代表标签类别。如图中“看”和“不看”
• 中间节点：中间分类条件。如图中“健身完后去游泳”，“是否有好看的电影”
• 分枝：代表每一个条件的输出
• 二叉树：每一个节点上有两个分枝
• 多叉树：每一个节点上至少有两个分枝

摘自知乎：https://zhuanlan.zhihu.com/p/74345351

上面图中我们为啥要用“是否去健身房”做根节点呢？可不可以用“是否有好看的电影”做根节点呢？这样做有什么原因吗？要回答这些问题，我们首先要理解决策树的思想是什么。决策树实际上就是寻找最纯净的划分方法，这个“最纯净”在数学上叫纯度，纯度通俗点理解就是决策结果要分得足够开（y=1的和y=0的混到一起就会不纯），尽可能让类别一样的数据在树的同一边，当树的叶子节点的数据都是同一类的时候，则停止分类。

将这种纯粹度用数据进行量化，计算机才能读懂 。纯度的另一面也即不纯度，热力学里面有个“熵”的概念正好就是衡量信息混乱程度的。

2.1 信息熵

信息熵是衡量信息的不确定性或混乱程度的指标，信息的不确定性越大，熵越大。定义如下：

[公式]

2.2 条件熵

条件熵类似于条件概率，在知道X的情况下，Y的不确定性，定义如下：

[公式]

2.3 信息增益

信息增益代表熵的变化程度，也就是某个特征 X 使得类 Y 的不确定性减少的程度：

[公式]

信息增益越大，熵的变化程度越大，分的越干脆，越彻底，不确定性越小。

在构建决策树的时候就是选择信息增益最大的属性作为分裂条件（ID3），使得在每个非叶子节点上进行测试时，都能获得最大的类别分类增益，使分类后数据集的熵最小，这样的处理方法使得树的平均深度较小，从而有效提高了分类效率。

3. 如何构建决策树

根节点以及树节点是从最重要到次重要依次排序的，ID3算法用的是信息增益，C4.5算法用信息增益率；CART算法使用基尼系数。决策树方法是会把每个特征都试一遍，然后选取那个能够使分类分的最好的特征，也就是说将A属性作为父节点，产生的纯度增益（GainA）要大于B属性作为父节点，则A作为优先选取的属性。

3.1 如何分裂训练数据（对每个属性选择最优的分割点）

如何分裂数据也即分裂准则是什么？依然是通过不纯度来分裂数据的，通过比较划分前后的不纯度值，来确定如何分裂。

下面做具体的介绍：

——CART算法：既可以做分类，也可以做回归。只能形成二叉树。

分支条件：二分类问题

分支方法：对于连续特征的情况：比较阈值，高于某个阈值就属于某一类，低于某个阈值属于另一类。对于离散特征：抽取子特征，比如颜值这个特征，有帅、丑、中等三个水平，可以先分为帅和不帅的，不帅的里面再分成丑和中等的。

得分函数（y）：就是上面提到的gt(x)，对于分类树取得是分类最多的那个结果（也即众数），对于回归树取得是均值。

损失函数：其实这里的损失函数，就是分类的准则，也就是求最优化的准则

对于分类树（目标变量为离散变量）：同一层所有分支假设函数的基尼系数的平均。

对于回归树（目标变量为连续变量）：同一层所有分支假设函数的平方差损失

对于分类树（目标变量为离散变量）：使用基尼系数作为分裂规则。比较分裂前的gini和分裂后的gini减少多少，减少的越多，则选取该分裂规则，这里的求解方法只能是离散穷举。关于基尼系数，可以参考周志华的西瓜书决策树那章，讲得比较简洁，也比较易懂。“直观来说，（数据集D的基尼系数）Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。”

具体这个的计算，我觉得有例子才好理解，下面这个红绿球的例子很好的说明了，如何根据损失函数最小（也就是基尼系数最小）来选取分裂规则。最后GIINs2更小，因此选择它作为分类规则。

对于回归树（目标变量为连续变量）：使用最小方差作为分裂规则。只能生成二叉树。

主要优缺点如下图。缺点补充几点，不是很稳定，数据变化一点，你的树就会发生变化；没有考虑变量之间相关性，每次筛选都只考虑一个变量（因此不需要归一化）；只能线性分割数据；贪婪算法（可能找不到最好的树）。优点也补充三点，同时可以处理分类变量和数值变量（但是可能决策树对连续变量的划分并不合理，所以可以提前先离散化）；可以处理多输出问题；另外决策树不需要做变量筛选，它会自动筛选；适合处理高维度数据。

三种方法对比：

ID3算法：信息增益越大，则选取该分裂规则，多分叉树。信息增益可以理解为，有了x以后对于标签p的不确定性的减少，减少的越多越好，即信息增益越大越好。倾向于选择水平数量较多的变量，可能导致训练得到一个庞大且深度浅的树；另外输入变量必须是分类变量（连续变量必须离散化）；最后无法处理空值。

C4.5选择了信息增益率替代信息增益作为分裂准则。此方法避免了ID3算法中的归纳偏置问题，因为ID3算法会偏向于选择类别较多的属性（形成分支较多会导致信息增益大）。多分叉树。连续属性的分裂只能二分裂，离散属性的分裂可以多分裂，比较分裂前后信息增益率，选取信息增益率最大的。

CART以基尼系数替代熵；最小化不纯度而不是最大化信息增益。既可以用于分类也可以用于回归。CART用Gini系数最小化准则来进行特征选择，生成二叉树。

4. 如何避免过拟合

如果决策树考虑了所有的训练数据集，得到的决策树将会过于庞大。虽然这个决策树对于训练数据集的拟合概率为100%，但是由于过分考虑所有的数据，将数据切得太碎太碎了，这样就会使得决策树学习到一些噪音点、错误点，出现过拟合的现象。

两种方法可以避免过拟合：剪枝和随机森林。

4.1 剪枝

剪枝分为预剪枝和后剪枝。

• 预剪枝：在构建决策树的过程中，提前停止。如限制深度、限制当前集合的样本个数的最低阈值。对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛化性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
• 后剪枝：先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛化性能的提升，则把该子树替换为叶结点。对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛化性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

4.2 随机森林

随机森林就是通过集成学习的思想将多棵决策树集成的一种算法，它的基本单元是决策树，本质是一种集成学习（Ensemble Learning）方法。

从直观角度来解释，每棵决策树都是一个分类器，那么对于一个输入样本，N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果，将投票次数最多的类别指定为最终的输出，这就是一种最简单的 Bagging 思想。

随机森林体现了两方面的随机：

• 样本随机 ：不使用全部数据集，而是随机有放回采样（有一定概率避免选到异常点，使得树的效果更好）
• 特征随机 ：不使用全部特征，而是随机选取一部分特征（有一定概率避开使用传统信息增益出问题的特征）

随机森林中的每棵树是怎么生成的呢？

1. 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集；

从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。

问题1：为什么要随机抽样训练集？

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；

问题2：为什么要有放回地抽样？

如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是绝对"片面的"（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是"盲人摸象"。

2. 如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；

3. 每棵树都尽最大程度的生长，并且没有剪枝过程。

一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

随机森林分类效果（错误率）与两个因素有关：

• 森林中任意两棵树的相关性：相关性越大，错误率越大；
• 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

5. 案例解析

https://zhuanlan.zhihu.com/p/74345351

6.直观解释为什么随机森林胜过决策树？

两个直观的原因

随机森林由多个单树组成，每个树基于训练数据的随机样本。它们通常比单个决策树更准确。下图显示随着更多树的添加，决策边界变得更加准确。

参考网址：

https://www.cnblogs.com/fionacai/p/5894142.html

https://zhuanlan.zhihu.com/p/74345351