详解决策树与随机森林

0️⃣引言

在之前介绍过决策树和随机森林调参&＃xff0c;但都是直接调用skelearn&＃xff0c;这次想重点介绍一下原理。

1️⃣决策树

&＃x1f39f;基本流程

以分类任务为代表的决策树模型&＃xff0c;是一种对样本特征构建不同分支的树形结构。

• 一般的&＃xff0c;一棵决策树包含一个根结点、若干个内部结点和若干个叶结点&＃xff1b;
• 叶结点对应于决策边界&＃xff0c;其他每个结点则对应于一个属性测试&＃xff1b;
• 每个结点包含的样本结合根据属性测试的结果被划分到子结点中&＃xff1b;
• 根结点包含样本全集&＃xff0c;从根结点到每个叶结点的路径对应了一个判定测试序列。
• 决策树学习的目的就是为了产生一棵泛化能力强&＃xff0c;即处理未见示例能力强的决策树&＃xff0c;类似于“分而治之”策略
• 结束条件&＃xff1a;
  • 当前结点包含的样本全属于同一类别&＃xff0c;无需划分
  • 当前属性集为空&＃xff0c;或是所有样本在所有属性上取值相同&＃xff0c;无需划分&＃61;&＃61;》将当前结点标记为叶结点&＃xff0c;并将其类别设置为该结点样本最多的类别
  • 当前结点包含的样本集合为空&＃xff0c;不能划分&＃61;&＃61;》把当前结点标记为叶结点&＃xff0c;但是将其类别设定为父结点所含样本最多的类别

&＃x1f39f;特征选择

目的&＃xff1a;通过划分&＃xff0c;使得决策树的分支结点所包含的样本尽可能属于同一类别&＃xff0c;即结点的“纯度”越来越高

&＃x1f68c;信息增益

在信息论中&＃xff0c;熵表示随机变量不确定性的度量。假设数据集D中第K类样本所占的比例为 pkp_kpk​ &＃xff0c;则D的熵定义为&＃xff1a;

如果某件事一定发生&＃xff08;太阳东升西落&＃xff09;或一定不发生&＃xff08;钓鱼岛是日本的&＃xff09;&＃xff0c;则概率为1或0&＃xff0c;对应的熵均为0。如果某件事可能发生****可能不发生&＃xff0c;概率介于0到1之间&＃xff0c;熵大于0。

由此可见&＃xff0c;熵越大&＃xff0c;随机性越大&＃xff0c;结果越不确定。

我们再来看一看 条件熵 Ent&＃xff08;D, a&＃xff09; &＃xff0c;表示引入随机变量a对于消除D不确定性的程度&＃xff08;通俗的讲就是如果属性a对于数据集D是一个比较好的特征&＃xff0c;也就是使用a划分D之后使D纯度更高&＃xff0c;导致更多相同类别的划分在一起&＃xff0c;条件熵就会越小&＃xff0c;反之越大&＃xff09;。假如D、a相互独立&＃xff0c;则D的条件熵和熵有相同的值 &＃xff08;此时条件熵是最大的时候&＃xff09;&＃xff1b;否则条件熵一定小于熵。

解析&＃xff1a;使用属性a对数据集D进行划分&＃xff0c;导致产生V个分支结点&＃xff0c;第v个分支结点对应的样本记为DvD^vDv&＃xff0c;也就是样本数越多的结点影响越大

明确了这两个概念&＃xff0c;理解信息增益就比较方便了。现在我们有一份数据集D&＃xff08;例如贷款信息登记表&＃xff09;和特征A&＃xff08;例如年龄&＃xff09;&＃xff0c;则A的信息增益就是D本身的熵与特征A给定条件下D的条件熵之差&＃xff0c;即&＃xff1a;

数据集D的熵是一个常量。信息增益越大&＃xff0c;表示条件熵 Ent(D, a) 越小&＃xff0c;a消除D的不确定性的功劳越大。

所以要优先选择信息增益大的特征&＃xff0c;它们具有更强的分类能力。由此生成决策树&＃xff0c;称为ID3算法。

&＃x1f68e;缺点

信息增益对取值数目较多的属性有所偏好&＃xff0c;为减少这种偏好带来的不利影响&＃xff0c;提出了信息增益率

&＃x1f68c;信息增益率

当某个特征具有多种候选值时&＃xff0c;信息增益容易偏大&＃xff0c;造成误差。引入信息增益率可以校正这一问题。

信息增益率&＃61;信息增益与数据集D的熵之比&＃xff1a;

其中&＃xff1a;

其实IV(a)很像熵的定义&＃xff0c;称为属性a的固有值&＃xff0c;属性a可能取值越大&＃xff08;V越大&＃xff09;&＃xff0c;IV(a)的值通常会更大。

因此&＃xff0c;我们优先选择信息增益率最大的特征&＃xff0c;由此生成决策树&＃xff0c;称为C4.5算法。

&＃x1f68e;缺点

信息增益率对信息增益中偏好较多属性做了修改&＃xff0c;会对取值数目较少的属性有所偏好&＃xff0c;会导致信息增益率有点矫枉过正&＃xff0c;因此C4.5并不是直接选择增益率最大的候选划分属性&＃xff0c;而是使用了一个启发式&＃xff1a;先从候选划分属性中找出信息增益高于平均水平的属性&＃xff0c;再从中选择增益率最高的。

&＃x1f68c;基尼指数

基尼指数是另一种衡量不确定性的指标。首先介绍基尼值

它反映了从数据集D中随机抽取两个样本&＃xff0c;其类别标记不一致的概率。因此基尼值越小&＃xff0c;则数据集D的纯度越高。

则属性a的基尼指数定义为&＃xff1a;

我们优先选择基尼指数最小的特征&＃xff0c;由此生成决策树&＃xff0c;称为CART算法。

CART表示分类回归决策树&＃xff0c;同样由特征选择、树的生成及剪枝组成&＃xff0c;可以处理分类和回归任务。
相比之下&＃xff0c;ID3和C4.5算法只能处理分类任务。
CART假设决策树是二叉树&＃xff0c;内部结点特征的取值为“是”和“否”&＃xff0c;依次递归地二分每个特征。
CART对回归树采用平方误差最小化准则&＃xff0c;对分类树用基尼指数最小化准则。

&＃x1f39f;剪枝处理

目的&＃xff1a;防止过拟合&＃xff0c;提高高泛化能力。

决策树剪枝一般有两种方法&＃xff1a;

• 预剪枝&＃xff1a;在树的生成过程中剪枝。基于贪心策略&＃xff0c;可能造成局部最优
• 后剪枝&＃xff1a;等树全部生成后剪枝。运算量较大&＃xff0c;但是比较精准

决策树剪枝往往通过极小化决策树整体的损失函数实现。

预剪枝降低过拟合风险&＃xff0c;显著减少决策树的训练时间开销和测试时间开销。但是有些分支的当前划分虽然不能提升泛化性能、甚至可能导致泛化性能暂时下降&＃xff0c;但是在其基础上进行的后续划分却有可能导致性能显著提高&＃xff1b;预剪枝基于“贪心”本质禁止这些分支展开&＃xff0c;给预剪枝决策树带来了欠拟合的风险。

相反&＃xff0c;后剪枝决策树的欠拟合风险很小&＃xff0c;泛化性能往往优于预剪枝决策树。但是后剪枝过程是在生成完全决策树之后进行的&＃xff0c;并且要自底向上的对树中的所有非叶结点进行逐一考察&＃xff0c;因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

2️⃣随机森林

&＃x1f39f;bagging集成

机器学习算法中有两类典型的集成思想&＃xff1a;bagging和boosting。

bagging是一种在原始数据集上&＃xff0c;通过有放回抽样分别选出k个新数据集&＃xff0c;来训练分类器的集成算法。分类器之间没有依赖关系。

随机森林属于bagging集成算法。通过组合多个弱分类器&＃xff0c;集思广益&＃xff0c;使得整体模型具有较高的精确度和泛化性能。

&＃x1f39f;介绍

我们将使用CART决策树作为弱学习器的bagging方法称为随机森林。

“随机“表示2种随机性&＃xff0c;即每棵树的训练样本、训练特征随机选取。多棵决策树组成了一片“森林”&＃xff0c;计算时由每棵树投票或取均值的方式来决定最终结果&＃xff0c;体现了三个臭皮匠顶个诸葛亮的中国传统民间智慧。

由于随机性&＃xff0c;随机森林对于降低模型方差效果显著。故随机森林一般不需要额外剪枝&＃xff0c;就能取得较好的泛化性能。

从偏差-方差角度看&＃xff0c;Boosting主要关注降低偏差&＃xff0c;因此可以基于泛化性能相当弱的学习器构建出很强的集成&＃xff0c;而Bagging主要关注降低方差&＃xff0c;因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更加明显。所以随机森林相比于基于boosting的GBDT模型&＃xff0c;偏差会大一些。另外&＃xff0c;随机森林中的树一般会比较深&＃xff0c;以尽可能地降低偏差&＃xff1b;而GBDT树的深度会比较浅&＃xff0c;通过减少模型复杂度来降低方差。&＃xff08;面试考点&＃xff09;

最后&＃xff0c;我们总结一下随机森林都有哪些优点&＃xff1a;

• 采用了集成算法&＃xff0c;精度优于大多数单模型算法
• 在测试集上表现良好&＃xff0c;两个随机性的引入降低了过拟合风险​
• 树的组合可以让随机森林处理非线性数据
• 训练过程中能检测特征重要性&＃xff0c;是常见的特征筛选方法​
• 每棵树可以同时生成&＃xff0c;并行效率高&＃xff0c;训练速度快
• 可以自动处理缺省值​