专栏首页智能算法分类回归树算法---CART

分类回归树算法---CART

一、算法介绍

分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相类似的决策树。CART采用一种二分递归分割的技术,将当前的样本集分为两个子样本集,使得生成的的每个非叶子节点都有两个分支。因此,CART算法生成的决策树是结构简洁的二叉树。

CART算法是由以下两部组成:

(1)决策树生成:基于训练数据集生成的决策树,生成的决策树要尽量大;

(2)决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,用损失函数最小作为剪枝的标准。

二、决策树的生成

CART算法的决策树采用的Gini指数选择最优特征,同时决定该特征的最优二值切分点。算法在构建分类树和回归树时有些共同点和不同点,例如处理在何处分裂的问题。

GINI指数: 1、是一种不等性度量; 2、通常用来度量收入不平衡,可以用来度量任何不均匀分布; 3、是介于0~1之间的数,0-完全相等,1-完全不相等; 4、总体内包含的类别越杂乱,GINI指数就越大(跟熵的概念很相似)

假设有k个类,样本点属于第k类的概率为p_{k} ,则概率分布的GINI指数定义为:

在考虑二元划分裂时,计算每个结果分区的不纯度的加权和,例,在特征A的条件下,集合D的基尼指数定义为:

下面通过一个实例进行分析:

GINI指数考虑每个属性的二元划分,如果类别中有v个可能的值,则存在2^v个可能的子集,例如,表面覆盖有5个可能的值,主要的{毛发,非毛发},{鳞片,非鳞片},我们需要选择最小基尼指数作为划分。

总体包含的类别最杂乱,GINI指数越大,表面覆盖{毛发,非毛发}值,毛发的3个都是哺乳类,则

表明覆盖为非毛发的,3个爬行动物,3个鱼类,2个两栖类,2个哺乳类,则

如果表明覆盖特征按照“毛发和非毛发”划分的话,得到的GINI的增益是

表面覆盖为{鳞片,非鳞片}值的GINI增益为

因此,特征表面覆盖和分裂子集{鳞片,非鳞片}产生最小的基尼指数,可作为最优切分点。

对于整棵决策树的建立,

1)需要寻找所有特征中的GINI增益最小的特征作为决策树的最优特征和最优切分点。

2)根据最优切分点长出两个子结点,将训练数据集依特征分配到两个子结点中去。

3)对两个子结点递归地调用(1),(2)直到满足停止条件。

4)生成决策树。

上述中的停止条件,一般是结点中的样本个数小于预定阈值,或样本集的基尼指数小于预定阈值(样本基本属于同一类),或者没有更多的特征。

三、剪枝

决策树为什么(WHY)要剪枝? 原因是避免决策树过拟合(Overfitting)样本。前面的算法生成的决策树非常详细并且庞大,每个属性都被详细地加以考虑,决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话,你会发现对于训练样本而言,这个树表现完好,误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习,成为决策树的部分,但是对于测试数据的表现就没有想象的那么好,或者极差,这就是所谓的过拟合(Overfitting)问题。通过从“完全生长”的决策树的底端剪去一些子树,可以使决策树变小,也就是模型变简单,因此可以通过CART剪枝算法解决过拟合问题,

如何剪枝呢? CART剪枝算法由两步组成:首先从生成算法产生的决策树T0底端开始剪枝,直到T0的根结点,形成子树序列{T0,T1,..,Tn},然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,选出最优子树。

剪枝的方法分为前剪枝和后剪枝:前剪枝是指在构造树的过程中就知道哪些节点可以剪掉,于是干脆不对这些节点进行分裂,在分类回归树中使用的是后剪枝方法,后剪枝方法有多种,比如:代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。这里我们只介绍代价复杂性剪枝法。

对于分类回归树中的每一个非叶子节点计算它的表面误差率增益值α,可以理解为误差代价,最后选出误差代价最小的一个节点进行剪枝。。

|N_{T_{t}}|是子树中包含的叶子节点个数;R(t) 是节点t的误差代价,如果该节点被剪枝;R(t)=r(t)*p(t) r(t)是节点t的误差率;p(t)是节点t上的数据占所有数据的比例。R(T_{t}) 是子树Tt的误差代价,如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。

比如有个非叶子节点T4如图所示:

已知所有的数据总共有60条,则节点t4的节点误差代价为:

子树误差代价为:

以T4为根节点的子树上叶子节点有3个,最终:

找到α值最小的非叶子节点,令其左右孩子为NULL。当多个非叶子节点的α值同时达到最小时,取|N_{T_{t}}| 最大的项进行剪枝。

而选择最终的最优决策树算法如下:

四、参考资料

http://www.cnblogs.com/zhangchaoyang/articles/2709922.html

李航《统计学习方法》

免责声明:本文系网络转载。版权归原作者所有。如涉及版权,请联系删除!

本文分享自微信公众号 - 智能算法(AI_Algorithm)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-05-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 分类回归树算法---CART

    一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

    智能算法
  • GBDT算法(简明版)

    一、算法介绍 GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regr...

    智能算法
  • GBDT(梯度提升决策树)算法(简明版)

    一、算法介绍 GBDT(Gradient Boosting Decision Tree) 又叫 MART(Multiple Additive Regr...

    智能算法
  • 分类回归树算法---CART

    一、算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法也属于一种决策树,和之前介绍了C4.5算法相...

    智能算法
  • python GUI库图形界面开发之PyQt5选项卡控件QTabWidget详细使用方法与实例

    QTabWidget控件提供了一个选项卡和一个页面区域,默认显示第一个选项卡的页面,通过单击各选项卡可以查看对应的界面,如果在一个窗口中显示的输入字段很多,则可...

    砸漏
  • 【算法系列】决策树

    统计学家
  • 腾讯云WEB应用防火墙(WAF)如何修改DNS解析?

    最近有很多站长朋友想了解腾讯云WEB应用防火墙(WAF)如何修改DNS解析?小编赵一八笔记特意从网上整理相关资料,希望可以帮到大家。

    用户7261497
  • 使用 Nlog 将日志打印到 Logstash 的监控接口

    Logstash提供了多种监听日志打印的方式,而Nlog也提供了多种输出日志的方式,当Nlog的输出配置与Logstash的输入配置相对应,就能够让Nlog打印...

    Venyo
  • 【玩转腾讯云】使用云服务器进行生信数据分析

    很多小伙伴手头有生信数据分析,但苦于没有服务器,没法完成自己需要的数据分析,特别是处于学习阶段的同学。这里,向大家推荐一下使用腾讯云CVM服务器,按量计费进行数...

    用户1075469
  • 常见算法的时间复杂度 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…

    说实话,我是真的不懂算法。但是,我知道一个算法的好坏,通常时间复杂度是一个评价的指标之一。

    业余草

扫码关注云+社区

领取腾讯云代金券