分类回归树算法---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