关键词：
作者：桂。
时间：2017-05-13 14:19:14
链接：http://www.cnblogs.com/xingshansi/p/6847334.html
、
前言
内容主要是CART算法的学习笔记。
CART算法是一个二叉树问题，即总是有两种选择，而不像之前的ID3以及C4.5B可能有多种选择。CART算法主要有回归树和分类树，二者常用的准则略有差别：回归树是拟合问题，更关心拟合效果的好坏，此处用的是均方误差准则; 分类树是分类问题，更像是离散变量的概率估计，用与熵类似的Gini系数进行度量。
一、CART算法——回归树
因为是回归问题，只要抓住两个要点就好：
1）如何切分;
2）切分后的不同区域，如何取值;
先来分析一下一次划分的操作：
A-回归树切分
选择第j个变量
和它的取值s，作为切分变量和切分点，并定义两个区域：
通过寻找最小均方误差点，实现切分：
B-回归树的输出值
对固定输入变量j找到最优切分点s，并定义各自区域均值为输出变量：
C-回归树举例
看一下习题中的例子：
数据的切分点分别为：1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5
从公式
可以看出输出值c就是对应类别内y的均值。
当切分点选择s = 2.5时，区域R1有：
c1 = (4.5+4.75)/2=4.625
区域R2有：
同样c2 = 7.17
从而计算出s = 2.5对应的估计误差：
不同的s切分点，对应的估计误差不同，最后选择最小误差对应的切分点，这就完成了一次切分：
此时的c1,c2分别对应两类输出值。
假设s=6.5处实现了第一次划分，第二次就是分别在子区域进一步划分，如将：
进行二次切分，步骤思路与上面完全一致。
总结一下CART回归树的算法思路：
二、CART算法——分类树
A-基尼系数
CART分类树不再是基于信息增益，而是引入了Gini系数，给出基尼系数定义：
二分问题中Gini系数与熵之半的对比：
可以看出基尼系数与熵的特性类似，也是不确定性（信息量）的一种量度。
一方面，如果对于样本集合D，基尼系数：
其中
是D中属于第k类的样本子集，K是类的个数。
如果D被特征A划分为D1、D2两部分，这个时候就是统计均值，D的基尼系数：
B-CART决策树生成
CART决策树的生成，抓住两个基本要点：
1）基尼系数计算，确定二叉树；
2）确定决策树层次结构
举例说明：
分别以
表示年龄、有工作、有自己的房子、信贷情况。
对于A1是分为中年、老年、青年，计算基尼系数
A1、A3都可以，选择A1，，即青年是一类，非青年（中年、老年）是一类，
有工作、有自己的房子，都是二分，可以不用切分。信贷情况A4：
最小，故选为最优切分点。
至此，完成了基尼系数计算以及二叉树划分。下面确定决策树层次结构：
由小到大，A3为最优切分点，依次在A1，A2，A4选择，故选择A2为次优切分点......依次类推。
给出决策树生成算法：
主要分两步走：
1）计算各种情况的基尼系数，划分每个节点的二叉树;
2）根据基尼系数的大小，确定二叉树不同节点的层次结构，形成决策树。
三、CART树剪枝
回归树（拟合问题）与决策树都存在过拟合问题，防止过拟合（过渡细化）都需要剪枝的操作。
先来看看剪枝用到的准则函数：
关于C(T)之前文章有分析，它是叶节点特性的度量，C4.3里它是熵的均值，CART决策树里它是基尼系数的概率均值，原理类似。多一个正则项，就是稀疏性约束。
ID3、C4.5算法中的剪枝原理是给定α，事实上很难一次给出理想的α。CART剪枝不再给定一个α，然后选择最优决策树，而是通过设定不同的α，通过交叉验证选择最优CART树，也就是：
训练集：得到不同的子树;
测试集：交叉验证选择最优树.
从有限个子树
中计算最优子树，最优子树由验证集得出的测试误差决定，哪个最小就是哪个。
这里就引出了一个问题，每次剪哪一个节点呢？先看分析剪枝的两个极端情况：
1）完全没剪：
2）只剩根节点：
在α较小或者为0时，有：
在α取+∞大时，有：
α是连续变量，因此总有临界点：
为了不混淆变量，重新定义：
α大于g(t)就是该剪。简而言之：
对于同一棵树的结点，α都是一样的，当α从0开始缓慢增大（或者从+∞慢慢减小），总会有某棵子树该剪，其他子树不该剪的情况，即α超过了某个结点的g(t)，但还没有超过其他结点的g(t)。这样随着alpha不断增大，不断地剪枝，就得到了n+1棵子树，接下来只要用独立数据集测试这n+1棵子树，试试哪棵子树的误差最小 就知道那棵是最好的方案了。
给出CART剪枝算法：
原书的算法勘误：
（4）修改为：
（6）修改为：
参考：
- 李航《统计学习方法》
机器学习决策树理论第二卷
决策树内容来至于《统计学习与方法》李航,《机器学习》周志华,以及《机器学习实战》PeterHarringTon,相互学习,不足之处请大家多多指教！本卷的大纲为1CART算法1.1CART回归树1.2CART分类树2CART剪枝3总结1CART算法CART分类与回归树(classi... 查看详情
统计学习笔记之决策树
1.CART分类树的特征选择分类问题中,假设有K个类,样本点属于第k类的概率为,则概率分布的基尼指数定义为: 如果，集合D根据特征A是否取某一可能值a被分割成和，在特征A的条件下,集合D的基尼指数定义为: 基尼指数代... 查看详情
机器学习算法：cart剪枝
学习目标了解为什么要进行cart剪枝知道常用的cart剪枝方法1为什么要剪枝 图形描述横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。实线显示的是决策树在训练集上的精度，虚线显示的则是在一... 查看详情
《机器学习技法》---cart算法
...示分叉的规则，Gc(x)是子树的模型。 2一般决策树生成算法的框架即，学习划分规则b(x)，然后把数据按照b(x)划分为C部分，对每一部分递归地生成子树。注意递归在一定条件停止，直接返回一个g(x)。 事实上，不同的决策... 查看详情
cart算法节点分裂演示
参考技术ACART是一颗二叉树（分类或回归）基于Gini指数数据集，预测婚姻演示：最终选择Officer、Student、Teacher的划分方法基于方差数据集，预测年龄演示：最终选择Officer、Student,Teacher的划分方法数据集，预测职业演示最终选择&l... 查看详情
机器学习算法决策树-5cart回归树法，m5回归树算法对cart算法改进了什么
目录Cart字段回归树算法CART回归树的字段选择方式：小插曲：M5如何利用模型树来提升CART回归树的效能继续CART字段选择方式我的主页：晴天qt01的博客_CSDN博客-数据分析师领域博主目前进度：第四部分【机器学习算... 查看详情
机器学习总结决策树id3，c4.5算法，cart算法
本文主要总结决策树中的ID3,C4.5和CART算法，各种算法的特点，并对比了各种算法的不同点。决策树：是一种基本的分类和回归方法。在分类问题中，是基于特征对实例进行分类。既可以认为是if-then规则的集合，也可以认为是定... 查看详情
cart回归树算法过程
... 其中c1,c2分别为R1,R2区间内的输出平均值。（此处与统计学 查看详情
机器学习决策树算法cart剪枝
目录1为什么要剪枝2常用的减枝方法2.1预剪枝2.2后剪枝3小结1为什么要剪枝在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得"... 查看详情
决策树算法
决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。本文就对决策树算法原理做一个总结，上篇对ID3，C4.5的算法思想做了总结，下... 查看详情
机器学习-决策树算法（id3c4.5和cart）
文章目录简介划分依据ID3算法C4.5算法CART算法处理连续值剪枝应用示例前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。简介决策树（DecisionTree）是... 查看详情
机器学习算法概述第五章——cart算法
...复杂的关系，决策树很难学习，比如异或CART分类决策树算法： 纯度：当样本点均来自同一类别时不纯度为0,当两个样本点属于不同类别时的不纯度为两个类别的概率相乘 多类别时： 来自于1类别的概率+来自于2类别的... 查看详情
机器学习笔记之三cart分类与回归树
本文结构：CART算法有两步回归树的生成分类树的生成剪枝CART－ClassificationandRegressionTrees分类与回归树，是二叉树，可以用于分类，也可以用于回归问题，最先由Breiman等提出。分类树的输出是样本的类别，回归树的输出是一个实... 查看详情
决策树算法cart和c4.5决策树有啥区别？各用于啥领域？
1、C4.5算法是在ID3算法的基础上采用信息增益率的方法选择测试属性。CART算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART算法对每次样本集的划分计算GINI系数，GINI系数，GINI系数越小则划分越合理。2、决策树... 查看详情
cart算法
参考技术ACART算法就是分类回归树，它只支持二叉树，既可以作分类树，又可以作回归树。那什么是分类树，什么是回归树呢？假如有个数据集，分别给出了，不同年龄、职业、性别的不同学习时间。如果我构造了一棵决策树，... 查看详情
统计算法学习梳理
...sp;关于统计学习。首先推荐李航老师著作的一本书《统计学习方法》。在此引用里边一句话来定义统计学习：统计学习（statisticallearning）是关于计算机基于数据构建概率模型并运用模型对数据 查看详情
机器学习——决策树（下）算法实现
...绍了决策树的生成和剪枝原理。介绍了CART,ID3，C4.5等算法的算法流程，其中CART算法可以实现回归和分类，是基于基尼不纯度实现的，这里并未实现。这里主要实现了ID3和C4.5算法，是基于信息熵的 查看详情
数据挖掘领域经典算法——cart算法
简介CART与C4.5类似，是决策树算法的一种。此外，常见的决策树算法还有ID3，这三者的不同之处在于特征的划分：ID3：特征划分基于信息增益C4.5：特征划分基于信息增益比CART：特征划分基于基尼指数基本思想CART假设决策树是二... 查看详情