8.3 基于分类回归树的决策划分

决策树有两种，一种是分类树，其输出的是样本的类标；一种是回归树，其输出的是一个实数。

8.3.1 概要

分类回归树（CART），最先由Breiman等提出，属于一类决策树。

CART由决两部分组成：决策树生成（基于训练数据集生成决策树，生成的决策树要尽量大）、决策树剪枝（用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准）

CART与ID3的区别：

1、用于选择变量的度量不同，ID3：信息增益，CART：GINI指数。

2、对于连续的目标变量，CART预测目标变量的方法是找出一组基于树的回归方程。

3、对于具有两个以上类标的标称目标变量，CART可能考虑将目标类别合并称两个超类别（双化）。

GINI指数：

定义：在分类问题中，假设有M个类，样本点属于第i类的概率为,则概率分布的GINI指数定义为GINI(p)=Sum[]，。

对于给定样本集合D，其GINI指数为GINI指数为GINI(D)=1-Sum，，其中是D中属于第i类的样本子集，M是类的个数。

如果样本集合D根据特征A是否取某一可能值a分割成和两部分，即{}，，则在特征值A的条件下，集合D的Gini指数定义为：GINI(D，A)=GINI()+GINI()，基尼指数GINI(D)表示集合D的不确定性，基尼指数GINI(D，A)表示经A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也越大，这一点于熵相似。

8.3.2 剪枝

为了避免决策树过拟合样本，决策树要进行剪枝。剪枝分两种情况：预剪枝和后剪枝。

决策树停止生长的条件可以看做预剪枝过程。

常用的停止条件：

1、同一个类别的样本数据在同一子树上，即该子树样本数据的类型相同。

2、已经到达树的最大深度。

3、子树结点的样本数量要少于某个门限值，或者小于一定的比例。

4、子树结点再按照最优划分标准切分，其子树的样本数量小于某个门限值，或者小于一定的比例值。

5、最优划分标增益小于某个门限值。

在已生成过拟合决策树上进行剪枝，得到简化版的剪枝决策树的过程是后剪枝过程。

为了确定决策树规模，有如下几个剪枝思路：

1、为了评估剪枝方法在修剪结点上的效用，使用训练集合和验证集合。

2、为了用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能，使用所有的训练集合进行训练。

3、为了衡量训练样本例和决策树的复杂度，使用一些明确的标准。当编码长度最小时，树停止生长。

后剪枝技术：错误率降低剪枝（Reduce-Error Pruning，REP），悲观剪枝（Pessimistic Error Pruning，PEP），最小误差剪枝（Minimum Error Pruning），代价复杂剪枝（Cost-Complexity Pruning）