机器学习算法与Python实践(11) - 决策树 ID3、C4.5、CART
机器学习算法与Python实践(11) - 决策树 ID3、C4.5、CART
目录
什么是决策树(Decision Tree)
特征选择
使用ID3算法生成决策树
使用C4.5算法生成决策树
使用CART算法生成决策树
预剪枝和后剪枝
应用:遇到连续与缺失值怎么办?
多变量决策树
Python代码(sklearn库)
什么是决策树(Decision Tree)
引例:
现有训练集如下,请训练一个决策树模型,对未来的西瓜的优劣做预测。
先不谈建立决策树模型的算法,我们先看一下基于“信息增益”(后面讲)生成的决策树的样子
一棵决策树包含一个根节点、若干个内部节点、若干个叶节点。叶节点对应于决策结果,其他节点对应于一个属性测试。每个节点包含的样本集合根据属性测试的结果被划分到子节点中。根节点(纹理)包含样本全集,根节点下的节点(根蒂)包含所有纹理=清晰的样本。从根节点到每个叶节点的路径对应一个判定测试序列。决策树的学习就是要产生一棵对新样本预测正确率高的决策树。
李航《统计学习方法》中的介绍
决策树(decision tree)是一种基本的分类与回归方法。决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是
特征选择
决策树学习的关键在于:在每个节点上如何选择最优划分属性。
在引例中,在根节点上,优先选择了“纹理”作为划分属性,这种选择是有依据的。
一般而言,随着划分过程不断进行,我们希望决策树的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。因此我们要找一个指标,去衡量划分数据集后“纯度提升的幅度”,然后选择能让“纯度提升的幅度”最大的特征去划分数据集。
常用的衡量“纯度提升的幅度”的指标有:信息增益、信息增益率、基尼指数。
基于信息增益生成决策树的算法,称为
基于信息增益率生成决策树的算法,称为
基于基尼指数生成决策树的算法,称为
二娃:为什么要在每个节点上都要费老大劲去选择最优划分属性呢?先看看我们有哪些特征(色泽、根蒂…触感),按顺序选呗?
假设有一个训练集,有4个特征
使用ID3 算法生成决策树
首先定义“信息熵”,它是度量样本集合纯度的一种指标。假定当前样本集合
假设离散属性
信息增益越大,则意味着用属性
下面,演示引例中决策树形成的过程:
第一步:
显然,
第二步:
计算使用属性集合{色泽,根蒂,敲声……}中的哪个属性进行数据集划分可以带来最高的信息增益。
先计算“色泽”:
根据色泽可以将数据集
求每个节点的信息熵:
计算使用“色泽”划分数据集后的信息增益:
类似的,计算出使用其他属性划分数据集后的信息增益:
显然,选择“纹理”划分后信息增益最大,于是,通过“纹理”划分数据集,各分支节点包含样例子集的情况是:
第三步:
在每个子节点上递归执行相同的算法,便可得到决策树,如下:
使用C4.5 算法生成决策树
实际上,信息增益准则对可取值数目较多的属性有所偏好(这种偏好是不好的,他会妨碍我们在节点上找到最优的划分特征,最终导致建立的决策树模型复杂、额外增加计算量。说到底就是这是基于“信息增益”选择特征的缺陷),为减少这种偏好的影响,
其中,
需要注意的是:信息增益率对可取值数目较少的属性有所偏好。
因此,
使用CART 算法生成决策树
直观来说,
于是,我们要选择
预剪枝和后剪枝
剪枝是决策树学习算法对付“过拟合”的主要手段。在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因训练样本学得“太好”了,以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此,可通过主动去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有:“预剪枝”和“后剪枝”
预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树准确率提升,则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树准确率提升,则将该子树替换为叶节点。
如何判断决策树准确率是否提升呢?可以使用性能评估的方法,如:留出法,即预留一部分数据用作“验证集”以进行性能评估。
假定这里使用信息增益准则生成如下决策树:
(准确率为42.9%)
先讨论“预剪枝”:
预剪枝是在建造决策树的过程中执行的,如果发现某个节点划分后准确率没有提高,就禁止划分。
优点:预剪枝使得决策树的分支都没有“展开”,降低了过拟合的风险,减小了训练时间。
缺点:有欠拟合的风险。因为有些分支的当前划分虽不能提升准确率、甚至会暂时导致准确率下降,但是在其基础上的后续划分却有可能显著提升准确率。
(准确率为71.4%)
再讨论“后剪枝”:
后剪枝先从训练集生成一棵完成决策树,然后慢慢砍树,砍的位置:当前决策树叶节点的父节点,砍的条件是:如果能提高准确率就砍。
优点:欠拟合风险很小,准确率一般优于“预剪枝”决策树。
缺点:训练时间长。
(准确率为71.4%)
以上剪枝的过程引自周志华《机器学习》直观易于理解;李航《统计学习方法》中的剪枝是通过定义一个损失函数,然后也是像“后剪枝”一样,递归地从树的叶节点向上回缩。
两人算法的不同点在于:李航的算法不是单单看准确率,而是同时权衡准确率和树的复杂度两个因素,并通过改变参数控制两者的影响力。
两人算法的相同点在于:最终目的都是提升决策树的泛化性能。
应用:遇到连续与缺失值怎么办?
先讨论“连续”:
之前讨论的都是基于离散属性来生成决策树。当遇到连续属性时,最简单的策略是采用“二分法”对连续属性进行处理。
具体步骤是:先将连续属性排序,假设有划分点t,基于t便可将D划分为两部分。那么,连续属性划分的关键就在于如何选划分点t,假设我们有排好序的序列:
假设数据集:
在决策树学习的开始,根节点包含17个训练样本,“含糖率”的候选划分点集合包含16个候选值:{
注意:与离散属性不同,若当前结点划分属性为连续属性,该连续属性还能作为其后代结点的划分属性。例如在父节点使用了“密度≤0.381”,不会禁止在子节点上使用“密度≤0.294”
再讨论“缺失”:
现实任务中常会遇到不完整样本,即样本的某些属性值缺失。如果抛弃不完整的样本,显然是一种对数据信息的浪费。因此,要想办法利用有缺失属性值的训练样本。假设有以下数据集:
我们需解决两个问题:
(1)如何在属性缺失的情况下进行划分属性的选择?
(2)给定划分属性,若该样本在该属性上的值缺失,如何对样本进行划分?
给定数据集
对问题(1),假定属性
因此,可以将信息增益的计算式推广为:
对问题(2),若样本
多变量决策树
通过一个例子来解释,假设有训练集:
若使用单变量决策树可以产生如下决策树,决策边界:
单变量决策树的决策边界是与坐标轴垂直或水平的。因此会造成决策树深度过高,模型较复杂。
若使用多变量决策树可以产生如下决策树,决策边界:
多变量决策树的决策边界可以是斜的(利用了多个属性的线性组合)。因此会造成决策树深度变低,模型变简单。
Python代码(sklearn库)
由于这篇文章太长了,所以代码部分放在下一篇文章中展出,之后会放链接。
代码如下:
待续…