首页 ›存档› 技术 › 查看内容

分类回归树算法---CART

2018-3-30 13:00 |来自: 互联网 556 0

摘要: 一、算法介绍分类回归树算法：CART(Classification And Regression Tree)算法也属于一种决策树，和之前介绍了C4.5算法相类似的决策树。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类的概率为，则概率分布的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},然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，选出最优子树。

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

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

是子树中包含的叶子节点个数;是节点t的误差代价，如果该节点被剪枝;

r(t)是节点t的误差率;

p(t)是节点t上的数据占所有数据的比例。

是子树T_t的误差代价，如果该节点不被剪枝。它等于子树T_t上所有叶子节点的误差代价之和。

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

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

子树误差代价为：

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

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