0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

数据挖掘算法:决策树算法如何学习及分裂剪枝

lviY_AI_shequ 2018-07-21 10:13 次阅读

1、决策树模型与学习

决策树(decision tree)算法基于特征属性进行分类,其主要的优点:模型具有可读性,计算量小,分类速度快。决策树算法包括了由Quinlan提出的ID3与C4.5,Breiman等提出的CART。其中,C4.5是基于ID3的,对分裂属性的目标函数做出了改进。

决策树模型

决策树是一种通过对特征属性的分类对样本进行分类的树形结构,包括有向边与三类节点:

根节点(root node),表示第一个特征属性,只有出边没有入边;

内部节点(internal node),表示特征属性,有一条入边至少两条出边

叶子节点(leaf node),表示类别,只有一条入边没有出边。

上图给出了(二叉)决策树的示例。决策树具有以下特点:

对于二叉决策树而言,可以看作是if-then规则集合,由决策树的根节点到叶子节点对应于一条分类规则;

分类规则是互斥并且完备的,所谓互斥即每一条样本记录不会同时匹配上两条分类规则,所谓完备即每条样本记录都在决策树中都能匹配上一条规则。

分类的本质是对特征空间的划分,如下图所示,

决策树学习

决策树学习的本质是从训练数据集中归纳出一组分类规则[2]。但随着分裂属性次序的不同,所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合,又对未知数据有很好的预测呢?

首先,我们要解决两个问题:

如何选择较优的特征属性进行分裂?每一次特征属性的分裂,相当于对训练数据集进行再划分,对应于一次决策树的生长。ID3算法定义了目标函数来进行特征选择。

什么时候应该停止分裂?有两种自然情况应该停止分裂,一是该节点对应的所有样本记录均属于同一类别,二是该节点对应的所有样本的特征属性值均相等。但除此之外,是不是还应该其他情况停止分裂呢?

2、决策树算法

特征选择

特征选择指选择最大化所定义目标函数的特征。下面给出如下三种特征(Gender, Car Type, Customer ID)分裂的例子:

图中有两类类别(C0, C1),C0: 6是对C0类别的计数。直观上,应选择Car Type特征进行分裂,因为其类别的分布概率具有更大的倾斜程度,类别不确定程度更小。

为了衡量类别分布概率的倾斜程度,定义决策树节点t的不纯度(impurity),其满足:不纯度越小,则类别的分布概率越倾斜;下面给出不纯度的的三种度量:

其中,表示对于决策树节点的概率。这三种不纯度的度量是等价的,在等概率分布是达到最大值。

为了判断分裂前后节点不纯度的变化情况,目标函数定义为信息增益(informationgain):

表示父节点分裂后的某子节点,为其计数,n为分裂后的子节点数。

特别地,ID3算法选取熵值作为不纯度的度量,则

c指父节点对应所有样本记录的类别; A表示选择的特征属性,即的集合。 那么,决策树学习中的信息增益等价于训练数据集中类与特征的互信息,表示由于得知特征A的信息训练数据集c不确定性减少的程度。

在特征分裂后,有些子节点的记录数可能偏少,以至于影响分类结果。为了解决这个问题,CART算法提出了只进行特征的二元分裂,即决策树是一棵二叉树;C4.5算法改进分裂目标函数,用信息增益比(information gain ratio)来选择特征:

因而,特征选择的过程等同于计算每个特征的信息增益,选择最大信息增益的特征进行分裂。此即回答前面所提出的第一个问题(选择较优特征)。ID3算法设定一阈值,当最大信息增益小于阈值时,认为没有找到有较优分类能力的特征,没有往下继续分裂的必要。根据最大表决原则,将最多计数的类别作为此叶子节点。即回答前面所提出的第二个问题(停止分裂条件)。

决策树生成

ID3算法的核心是根据信息增益最大的准则,递归地构造决策树;算法流程如下:

如果节点满足停止分裂条件(所有记录属同一类别 or 最大信息增益小于阈值),将其置为叶子节点;

选择信息增益最大的特征进行分裂;

重复步骤1-2,直至分类完成。

C4.5算法流程与ID3相类似,只不过将信息增益改为信息增益比。

3、决策树剪枝

过拟合

生成的决策树对训练数据会有很好的分类效果,却可能对未知数据的预测不准确,即决策树模型发生过拟合(overfitting)——训练误差(training error)很小、泛化误差(generalization error,亦可看作为test error)较大。下图给出训练误差、测试误差(test error)随决策树节点数的变化情况:

可以观察到,当节点数较小时,训练误差与测试误差均较大,即发生了欠拟合(underfitting)。当节点数较大时,训练误差较小,测试误差却很大,即发生了过拟合。只有当节点数适中是,训练误差居中,测试误差较小;对训练数据有较好的拟合,同时对未知数据有很好的分类准确率。

发生过拟合的根本原因是分类模型过于复杂,可能的原因如下:

训练数据集中有噪音样本点,对训练数据拟合的同时也对噪音进行拟合,从而影响了分类的效果;

决策树的叶子节点中缺乏有分类价值的样本记录,也就是说此叶子节点应被剪掉。

剪枝策略

为了解决过拟合,C4.5通过剪枝以减少模型的复杂度。[2]中提出一种简单剪枝策略,通过极小化决策树的整体损失函数(loss function)或代价函数(cost function)来实现,决策树T的损失函数为:

其中,表示决策树的训练误差,为调节参数,模型的复杂度。当模型越复杂时,训练的误差就越小。上述定义的损失正好做了两者之间的权衡。

如果剪枝后损失函数减少了,即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 数据挖掘
    +关注

    关注

    1

    文章

    406

    浏览量

    24235
  • 决策树
    +关注

    关注

    3

    文章

    96

    浏览量

    13550

原文标题:【十大经典数据挖掘算法】C4.5

文章出处:【微信号:AI_shequ,微信公众号:人工智能爱好者社区】欢迎添加关注!文章转载请注明出处。

收藏 人收藏

    评论

    相关推荐

    机器学习中常用的决策树算法技术解析

    决策树是最重要的机器学习算法之一,其可被用于分类和回归问题。本文中,我们将介绍分类部分。
    发表于 10-12 16:39 1311次阅读
    机器<b class='flag-5'>学习</b>中常用的<b class='flag-5'>决策树</b><b class='flag-5'>算法</b>技术解析

    关于决策树,这些知识点不可错过

    就比较高,如果知道其中的几个特征(如身高、性格等),不确定性就会减少很多。由上面的例子可见,一个属性的信息增益越大,表明这个属性使得数据由不确定性变成确定性的能力越强。04 决策树算法的补充要点关于
    发表于 05-23 09:38

    数据挖掘十大经典算法,你都知道哪些!

    的所有需求。而这三类里又包含许多经典算法。而今天,小编就给大家介绍下数据挖掘中最经典的十大算法,希望它对你有所帮助。一、 分类决策树
    发表于 11-06 17:02

    机器学习决策树介绍

    机器学习——决策树算法分析
    发表于 04-02 11:48

    一个基于粗集的决策树规则提取算法

    一个基于粗集的决策树规则提取算法:摘要:决策树数据挖掘任务中分类的常用方法。在构造决策树的过程
    发表于 10-10 15:13 12次下载

    基于决策树数据挖掘算法应用研究

    决策树数据挖掘分类算法在金融客户关系管理(CRM)中的应用为例,进行了数据挖掘的尝试,从中发现
    发表于 08-02 12:18 0次下载

    改进决策树算法的应用研究

    该方法利用决策树算法构造决策树,通过对分类结果中主客观属性进行标记并逻辑运算,最终得到较客观的决策信息,并进行实验验证。
    发表于 02-07 11:38 27次下载
    改进<b class='flag-5'>决策树</b><b class='flag-5'>算法</b>的应用研究

    一种新型的决策树剪枝优化算法

    目前关于决策树剪枝优化方面的研究主要集中于预剪枝和后剪枝算法。然而,这些剪枝
    发表于 11-30 10:05 0次下载
    一种新型的<b class='flag-5'>决策树</b><b class='flag-5'>剪枝</b>优化<b class='flag-5'>算法</b>

    使决策树规模最小化算法

    决策树技术在数据挖掘的分类领域应用极其广泛,可以从普通决策表(每行记录包含一个决策值)中挖掘有价
    发表于 12-05 15:47 0次下载
    使<b class='flag-5'>决策树</b>规模最小化<b class='flag-5'>算法</b>

    基于粗决策树的动态规则提取算法

    针对静态算法对大数据和增量数据处理不足的问题,构造了基于粗决策树的动态规则提取算法,并将其应用于旋转机械故障诊断中。将粗集与
    发表于 12-29 14:24 0次下载

    海量嘈杂数据决策树算法

    针对当前决策树算法较少考虑训练集的嘈杂程度对模型的影响,以及传统驻留内存算法处理海量数据困难的问题,提出一种基于Hadoop平台的不确定概率C4.5
    发表于 01-13 09:41 1次下载

    什么是决策树?决策树算法思考总结

    C4.5算法:基于ID3算法的改进,主要包括:使用信息增益率替换了信息增益下降度作为属性选择的标准;在决策树构造的同时进行剪枝操作;避免了
    的头像 发表于 02-04 09:45 1.1w次阅读
    什么是<b class='flag-5'>决策树</b>?<b class='flag-5'>决策树</b><b class='flag-5'>算法</b>思考总结

    决策树的构成要素及算法

    决策树是一种解决分类问题的算法决策树算法采用树形结构,使用层层推理来实现最终的分类。
    发表于 08-27 09:52 4359次阅读

    决策树的基本概念/学习步骤/算法/优缺点

    本文将介绍决策树的基本概念、决策树学习的3个步骤、3种典型的决策树算法决策树的10个优缺点。
    发表于 01-27 10:03 2637次阅读
    <b class='flag-5'>决策树</b>的基本概念/<b class='flag-5'>学习</b>步骤/<b class='flag-5'>算法</b>/优缺点

    什么是决策树模型,决策树模型的绘制方法

    决策树是一种解决分类问题的算法,本文将介绍什么是决策树模型,常见的用途,以及如何使用“亿图图示”软件绘制决策树模型。
    发表于 02-18 10:12 1.3w次阅读
    什么是<b class='flag-5'>决策树</b>模型,<b class='flag-5'>决策树</b>模型的绘制方法