第八章数据决策分析算法——基于分类回归树的决策划分

2019-11-04 本文已影响0人文颜

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

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

8.3.1 概要

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

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

CART与ID3的区别：

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

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

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

GINI指数：

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

对于给定样本集合D，其GINI指数为GINI指数为GINI(D)=1-Sum $(\frac{\vert c_{i} \vert }{\vert D \vert} )^2$ ， $1\leq i\leq M$ ，其中 $c_{i}$ 是D中属于第i类的样本子集，M是类的个数。

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