分类回归树算法---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},然后通过交叉验证法在独立的验证数据集上对子树序列进行测试,选出最优子树。

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

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

是子树中包含的叶子节点个数;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。当多个非叶子节点的α值同时达到最小时,取

最大的项进行剪枝。

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

四、参考资料

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

李航《统计学习方法》

回复数字或算法名称即可查看相关文章:

1. 决策树算法之一C4.5

2. 数据挖掘之Apriori算法

3. 网页排序算法之PageRank

4. 分类算法之朴素贝叶斯分类

5. 遗传算法如何模拟大自然的进化?

6. 没有公式如何看懂EM算法?

7. Python实现KNN算法

8. 基础聚类算法:K-means算法

9. 分类回归树算法---CART

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2016-05-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

机器之心GitHub项目:从循环到卷积,探索序列建模的奥秘

机器之心原创 作者:蒋思源 本文讨论并实现了用于序列模型的基本深度方法,其中循环网络主要介绍了传统的 LSTM 与 GRU,而卷积网络主要介绍了最近 CMU 研...

94360
来自专栏磐创AI技术团队的专栏

TensorFlow系列专题(七):一文综述RNN循环神经网络

前馈神经网络不考虑数据之间的关联性,网络的输出只和当前时刻网络的输入相关。然而在解决很多实际问题的时候我们发现,现实问题中存在着很多序列型的数据,例如文本、语音...

11630
来自专栏小鹏的专栏

为什么很多做人脸的Paper会最后加入一个Local Connected Conv?

Deep face:论文。 a. 人脸检测,使用6个基点 b. 二维剪切,将人脸部分裁剪出来 c. 67个基点,然后Delaunay三角化,在轮廓处添加三角形来...

37150
来自专栏杨熹的专栏

用 Doc2Vec 得到文档/段落/句子的向量表达

本文结构: Doc2Vec 有什么用 两种实现方法 用 Gensim 训练 Doc2Vec ---- Doc2Vec 或者叫做 paragraph2vec, s...

2K100
来自专栏LhWorld哥陪你聊算法

【机器学习】--层次聚类从初识到应用

聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小. 数据聚类算法可以分为结构性或者分...

32730
来自专栏机器之心

教程 | 基础入门:深度学习矩阵运算的概念和代码实现

选自Medium 机器之心编译 参与:蒋思源 本文从向量的概念与运算扩展到矩阵运算的概念与代码实现,对机器学习或者是深度学习的入门者提供最基础,也是最实用的教...

461130
来自专栏拂晓风起

验证码去噪 分离背景 分离文字 最大类间方差

13420
来自专栏null的专栏

利用Theano理解深度学习——Auto Encoder

注:本系列是基于参考文献中的内容,并对其进行整理,注释形成的一系列关于深度学习的基本理论与实践的材料,基本内容与参考文献保持一致,并对这个专题起名为“利用The...

38580
来自专栏文武兼修ing——机器学习与IC设计

深入理解感知机

1.模型 感知机的模型如下图所示: ? linear_classifier_structure.png 公式表示如下所示: $$ f(x) = sign(...

384100
来自专栏机器学习算法原理与实践

word2vec原理(一) CBOW与Skip-Gram模型基础

    word2vec是google在2013年推出的一个NLP工具,它的特点是将所有的词向量化,这样词与词之间就可以定量的去度量他们之间的关系,挖掘词之间的...

20820

扫码关注云+社区

领取腾讯云代金券