机器学习系列7：CART树和剪枝

作者: _世界和平_ | 来源:发表于2019-06-20 19:00 被阅读0次

机器学习系列7：CART树和剪枝
CART 分类与回归树
CART树剪枝（二）
决策树学习算法包括3部分
机器学习实战——回归树
第5章决策树
决策树
python tree
决策树系列
决策树的剪枝、连续与缺失

一、剪枝

1. 为什么要剪枝

在决策树生成的时候，更多考虑的是训练数据，而不是未知数据，这会导致过拟合，使树过于复杂，对于未知的样本不准确。

2. 剪枝的依据——通过极小化决策树的损失函数

定义：
设树 $T$ 的叶节点个数为 $|T|$ ，
$t$ 是树 $T$ 的叶节点，该叶节点有 $N_t$ 个样本,
其中属于 $k$ 类的样本点有 $N_{tk}$ 个， $k = 1,2，....，K$
$H_t(T)$ 是叶节点的经验熵
$\alpha \ge 0$ 是超参数

损失函数的定义为： $C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$
经验熵为： $H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log \frac{N_{tk}}{N_t}$
代入简化：
令： $C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$
则： $C_\alpha(T)=C(T)+\alpha|T|$

$\alpha$ 的作用：

控制着预测误差和树复杂度之间的平衡
$\alpha$ 大，促使选择更为简单的树
$\alpha$ 小，选择更为复杂的树
$\alpha$ = 0，只考虑模型与训练数据的拟合程度，不考虑复杂度

3. 剪枝算法

输入：未剪枝的决策树T，超参数 $\alpha$
输出：修剪好的树 $T_\alpha$
（1）计算每个叶节点的经验熵。
（2）递归的从树的叶节点向上回溯。设一组叶节点回溯到其父节点之前和之后的整体树分别为 $T_B$ 和 $T_A$ ，若他们的损失函数： $C_\alpha(T_A)\le C_\alpha (T_B)$ 即若修剪后的子树的损失函数比原来更小，则进行剪枝，将父节点作为新的叶节点。
（3）返回（2），知道不能继续进行，得到损失函数最小的子树 $T_\alpha$ 。

二、基尼指数

分类过程中，假设有K个类，样本点属于第k个类的概率为Pk，则概率分布的基尼指数定义为： $\operatorname{Gini}(p)=\sum_{k=1}^{m} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2}$
对于二分类的问题，若k=1时，概率是p，k=2时，概率是（1-p），则： $Gini(p)=p(1-p)+(1-p)p=2p-2p^2$
对于给定的样本集合D，其基尼指数为： $\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2}$

三、CART树

CART树全称是 classification and regression tree，既可以分类（离散数据），也可以用于回归（连续数据）。

3.1 分类树

如果数据集D根据特征A在某一取值a上进行分割，得到D1,D2两部分后，那么在特征A下集合D的基尼系数如下所示。 $\operatorname{Gini}(D, A)=\frac{|D 1|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{|D 2|}{|D|} \operatorname{Gini}\left(D_{2}\right)$
其中基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。这一点与熵相似。

对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。 $\begin{array}{c}{\min _{i \in A}\left( \operatorname{Gini}(D, A)\right)} \\ {\min _{A \in \text {Atribute}}\left(\min _{i \in A}\left( \operatorname{Gini}(D, A)\right)\right)}\end{array}$

实例详解

针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算D1,D2的基尼指数。然后计算得到特征体温下数据集的Gini指数，最后我们选择Gini最小的特征和相应的划分。

3.2 回归树

CART回归树预测回归连续型数据，假设X与Y分别是输入和输出变量，并且Y是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。 $D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right),\left(x_{3}, y_{3}\right), \ldots\left(x_{n}, y_{n}\right)\right\}$ 选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中Rm是被划分的输入空间，cm是空间Rm对应的固定输出值。
$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}\right]$ 用选定的(j,s)对，划分区域并决定相应的输出值 $\begin{array}{c}{R_{1}(j, s)=\left\{x | x^{(j)} \leq s\right\}, R_{2}(j, s)=\left\{x | x^{(j)}>s\right\}} \\ {\hat{c}_{m}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}} \\ {x \in R_{m}, m=1,2}\end{array}$
继续对两个子区域调用上述步骤，将输入空间划分为M个区域R1,R2,…,Rm，生成决策树。 $f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \epsilon R_{m}\right)$
当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小的准则求解每个单元上的最优输出值。 $\sum_{x_{i} \in R_{m}}\left(y_{i}-f\left(x_{i}\right)\right)^{2}$

实例详解

image.png

考虑如上所示的连续性变量，根据给定的数据点，考虑1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5切分点。对各切分点依次求出R1,R2,c1,c2及m(s)，例如当切分点s=1.5时，得到R1={1},R2={2,3,4,5,6,7,8,9,10}，其中c1,c2,m(s)如下所示。 $c_{1}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}=\frac{1}{1} \sum_{x_{i} \in R_{1}(1,1.5)} 5.56=5.56$ $c_{2}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}=\frac{1}{9} \sum_{x_{i} \in R_{2}(1,1,5)}(5.70+5.91+\ldots+9.05)=7.50$ $m(s)=\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{i}(j, s)}\left(y_{i}-c_{1}\right)^{2}\right]=0+15.72=15.72$
依次改变(j,s)对，可以得到s及m(s)的计算结果，如下表所示。