决策树学习笔记(一):特征选择

简介: 决策树学习笔记(一):特征选择

相信很多朋友已经对决策树很熟悉了,决策树是机器学习中的一种基本的可用于分类与回归的方法,它是一些集成学习如GBDT,XGboost等复杂模型的基础。这些高级模型比如XGboost可以非常好地拟合数据,在数据挖掘比赛以及工业界中都有着非常出色的表现,受到了无数爱好者的追捧。


有的朋友可能觉得XGboost很牛逼,上来就要学GBDT,XGboost。我并不建议这么做,我个人对整个树模型的学习过程总结了一个流程:

微信图片_20220218153506.jpg

本篇开始进入树模型系列,从最简单的决策树开始,按照上面这个学习流程,循序渐进,直到复杂模型Xgboost。


决策树概述


不同于逻辑回归,决策树属于非线性模型,可以用于分类,也可用于回归。它是一种树形结构,可以认为是if-then规则的集合,是以实例为基础的归纳学习。基本思想是自顶向下,以信息增益(或信息增益比,基尼系数等)为度量构建一颗度量标准下降最快的树,每个内部节点代表一个属性的测试,直到叶子节点处只剩下同一类别的样本。它的决策流程如下所示:

微信图片_20220218153522.jpg

决策树的学习包括三个重要的步骤,特征选择决策树的生成以及决策树的剪枝


  • 特征选择:常用的特征选择有信息增益,信息增益比,基尼系数等。
  • 生成过程:通过计算信息增益或其它指标,选择最佳特征。从根结点开始,递归地产生决策树,不断的选取局部最优的特征,将训练集分割成能够基本正确分类的子集。
  • 剪枝过程:首先定义决策树的评价指标,对于所有的叶子结点,累加计算每个叶子结点中的(样本数)与其(叶子节点熵值)的乘积,以叶子数目作为正则项(它的系数为剪枝系数)。然后计算每个结点的剪枝系数,它的大概含义是删除该结点的子树,损失不变的前提下,正则项系数的值为多少,这个值越小说明该子树越没有存在的必要。依次选取剪枝系数最小的结点剪枝,得到决策树序列,通过交叉验证得到最优子树。


特征选择


对于特征选择,常用的特征选择指标有信息增益,增益率,基尼指数


信息增益(Information Gain)


提到信息增益必须先解释一下什么是“信息熵”,因为信息增益是基于信息熵而定义的。我们先给出信息熵的公式定义:

微信图片_20220218153555.jpg

D:表示当前的数据集合。

k:表示当前数据集合中的第k类,也就是我们目标变量的类型。


微信图片_20220218153622.jpg

有很多朋友不是很明白为什么要选择这个指标来度量。其实简单来说,可以将信息熵理解为 “不纯度” 的意思。纯度高意味着在数据集里我们要分类的某一种类型占比很高,纯度低意味着分类的各个类型占比近似很难区分。


举一个例子,比如我们想分类A和B,用公式量化来体现就是:


1)如果分类结果中A和B各占50%,那么意味着分类结果很失败,这无异于随机地乱猜,完全没起到分类效果,公式计算结果如下:

微信图片_20220218153659.jpg


2)如果分类结果中A占比100%,B占比0%或者B占比100%,A占比0%时,那么意味着分类很成功,因为我们成功地区分了A和B,我们就说此时的纯度很高,公式计算结果如下:

微信图片_20220218153704.jpg

信息熵的取值范围为0~1,值越大,越不纯,相反值越小,代表集合纯度越高,如下图所示。

微信图片_20220218153730.jpg

上面信息熵只能代表不纯度,并不能代表信息量。但既然我们有了不纯度,我们只要将分类前后的不纯度相减,那就可以得到一种 “纯度提升值” 的指标,我们把它叫做 "信息增益"公式如下:

微信图片_20220218153755.jpg微信图片_20220218153758.jpg


基于特征A对数据集D的划分:

  • H(D|A):表示基于特征A(分类后)的信息熵,也称条件熵。
  • Di:基于特征A对数据集D划分的子集。
  • |Di|/|D|:考虑到特征分类子集的数据量不同,给每个子集赋予了权重。
  • n:为特征A的分类总数,即有多少个Di。


基于目标分类对特征类别Di数据集的划分:

  • Dik:每个特征分类子集Di中目标分类后的子集。
  • K:为目标分类的类别总数,即有多少个Dik。
  • |Dik|/|Di|:每个特征分类子集中,各目标分类子子集所占比例。


简单来说,先基于特征A进行划分,再基于目标变量进行划分,这是一个嵌套的过程。举一个例子说明,红色框内代表决策树中的其中一个分类过程,按照“是否理解内容”这个特征分成两类,树的父集和子集信息熵都已经标出,因此信息增益Gain就可以计算出来。

微信图片_20220218153755.jpg

上面只是描述了针对一个特征的计算信息增益的过程。在实际决策过程中,我们需要将所有的特征分类后的信息增益都计算一遍,然后选择其中最大的一个最为本次的分类特征。因此也就达到了特征选择的目的。ID3算法使用信息增益的方法来选择特征。


从这个过程,我们可以发现:最开始选择的特征肯定是提供信息量最大的,因为它是遍历所有特征后选择的结果。因此,按照决策过程中特征从上到下的顺序,我们也可以将特征的重要程度进行排序。这也就解释了为什么树模型有feature_importance这个参数了。


增益率(信息增益比)


信息增益可以很好的度量特征信息量,但却在某些情况下有一些弊端,举一个例子说明。


比如对于编号这个特征,我们知道一般编号值都是各不相同的,因此有多少个编号就需要分为多少类。由于每一个分类中只有一个编号值,即纯度已经最大,所以导致编号这个特征的信息增益最大,而实际上它并不是最优的特征,这样选择决策树也显然不具备泛化能力。


这正是信息增益的一个弊端:对可取值数目较多的属性有所偏好。因为信息增益反映的是给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大。


为了减少这种偏好带来的不利影响,“增益率” 这个指标诞生了。替代地,增益率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature,分裂信息用来衡量Feature分裂数据的广度和均匀性。增益率定义如下:

微信图片_20220218153844.jpg

  • Gain_ratio(D,A):代表基于特征A的增益率。
  • Split_Information(D,A):代表对属性A信息增益的平衡项。也可以理解为特征A的一种内在属性。


因此,属性A的取值数目越多,平衡项的值越大,增益率也就越小,这也反映出增益率对取值数据较少的属性有所偏好。C4.5算法就是利用增益率来选择特征。


基尼指数


与信息增益和增益率类似,基尼指数是另外一种度量指标,由CART决策树使用,其定义如下:

微信图片_20220218153901.jpg

对于二类分类问题,若样本属于正类的概率为 p,则基尼指数为:

微信图片_20220218153906.jpg

对于给定的样本集合D,其基尼指数定义为:

微信图片_20220218153942.jpg

其中CkD中属于第k类的样本子集。


如果样本集合D被某个特征A是否取某个值分成两个样本集合D1D2,则在特征A的条件下,集合D的基尼指数定义为:

微信图片_20220218153958.jpg

基尼指数Gini(D)反应的是集合D的不确定程度,跟熵的含义相似。Gini(D,A)反应的是经过特征A划分后集合D的不确定程度。所以决策树分裂选取Feature的时候,要选择使基尼指数最小的Feature,但注意信息增益则是选择最大值,这个值得选取是相反的。


再看看下图,其实基尼指数,熵,误分类率的曲线非常接近。


微信图片_20220218154002.jpg

总结


本篇介绍了决策树中的一个非常重要的步骤:特征选择。分别介绍了三种选择度量指标,信息增益,增益率,基尼指数。这三种指标也分别对应着三种算法ID3,C4.5,CART。


下一篇将会介绍三种算法,也包括分类和回归的算法流程和Python实现。最后介绍决策树的剪枝,如何处理缺失值,以及决策树的优缺点和应用。


参考:

[1] 统计学习方法,李航

[2] 机器学习,周志华

[3] http://leijun00.github.io/2014/09/decision-tree/

[4] https://www.jianshu.com/p/ca21d2392e73


相关文章
|
11月前
|
机器学习/深度学习 算法
机器学习算法之决策树
机器学习算法之决策树
|
2月前
|
机器学习/深度学习 算法 前端开发
决策树与随机森林算法在分类问题中的应用
本文探讨了决策树和随机森林两种监督学习算法,它们在分类任务中表现出强大的解释性和预测能力。决策树通过特征测试进行分类,构建涉及特征选择、树生成和剪枝。随机森林是集成学习方法,通过构建多棵决策树并汇总预测结果,防止过拟合。文中提供了Python代码示例,展示如何使用sklearn构建和应用这些模型,并讨论了参数调优和模型评估方法,如交叉验证和混淆矩阵。最后,强调了在实际问题中灵活选择和调整模型参数的重要性。
68 4
|
2月前
|
机器学习/深度学习 算法
机器学习算法决策树(二)
**ID3决策树算法**是1975年由J. Ross Quinlan提出的,它基于信息增益来选择最佳划分特征。信息增益是衡量数据集纯度变化的指标,熵则是评估数据不确定性的度量。算法通过比较每个特征的信息增益来选择分裂属性,目标是构建一个能最大化信息增益的决策树。然而,ID3容易偏向于选择具有更多特征值的属性,C4.5算法为解决这一问题引入了信息增益率,降低了这种偏好。CART决策树则不仅用于分类,也用于回归,并使用基尼指数或信息熵来选择分割点。剪枝是防止过拟合的重要手段,包括预剪枝和后剪枝策略。
|
2月前
|
机器学习/深度学习 算法 数据可视化
机器学习算法决策树(一)
**决策树模型**是一种直观的分类模型,常用于金融风控和医疗诊断等领域。它通过树形结构对数据进行划分,易于理解和解释,能揭示特征重要性且计算复杂度低。然而,模型可能过拟合,需剪枝处理;不擅长处理连续特征;预测能力有限,且对数据变化敏感。在集成学习如XGBoost中,决策树作为基模型广泛应用。示例代码展示了使用Python的`sklearn`库构建和可视化决策树的过程。
|
3月前
|
机器学习/深度学习 算法
理解并应用机器学习算法:决策树
【5月更文挑战第12天】决策树是直观的分类与回归机器学习算法,通过树状结构模拟决策过程。每个内部节点代表特征属性,分支代表属性取值,叶子节点代表类别。构建过程包括特征选择(如信息增益、基尼指数等)、决策树生成和剪枝(预剪枝和后剪枝)以防止过拟合。广泛应用在信贷风险评估、医疗诊断等领域。理解并掌握决策树有助于解决实际问题。
|
3月前
|
机器学习/深度学习 数据采集 并行计算
决策树
分类决策树
23 0
|
3月前
|
机器学习/深度学习 数据采集 算法
实现机器学习算法(如:决策树、随机森林等)。
实现机器学习算法(如:决策树、随机森林等)。
34 0
|
3月前
|
机器学习/深度学习 算法 数据库
决策树与随机森林算法
决策树和随机森林都是用于分类和回归的的算法。决策树的原理是通过一系列的问题进行if、else的推导。随机森林是集合学习算法,即把很多的机器学习算法综合在一起组成一个更大的模型。
|
机器学习/深度学习 人工智能 算法
连载|决策树(下)
连载|决策树(下)