【机器学习笔记之三】CART 分类与回归树

时间:2022-03-10 13:32:26

本文结构:

  • CART算法有两步
  • 回归树的生成
  • 分类树的生成
  • 剪枝

CART - Classification and Regression Trees

分类与回归树,是二叉树,可以用于分类,也可以用于回归问题,最先由 Breiman 等提出。

分类树的输出是样本的类别, 回归树的输出是一个实数。


CART算法有两步:

决策树生成和剪枝。

决策树生成:递归地构建二叉决策树的过程,基于训练数据集生成决策树,生成的决策树要尽量大;

自上而下从根开始建立节点,在每个节点处要选择一个最好的属性来分裂,使得子节点中的训练集尽量的纯。

不同的算法使用不同的指标来定义"最好":

分类问题,可以选择GINI,双化或有序双化;
回归问题,可以使用最小二乘偏差(LSD)或最小绝对偏差(LAD)。

决策树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时损失函数最小作为剪枝的标准。

这里用代价复杂度剪枝 Cost-Complexity Pruning(CCP)


回归树的生成

回归树模型表示为:

【机器学习笔记之三】CART 分类与回归树

其中,数据空间被划分成了 R1~Rm 单元,每个单元上有一个固定的输出值 cm。
这样就可以计算模型输出值与实际值的误差:

【机器学习笔记之三】CART 分类与回归树

我们希望每个单元上的 cm,可以使得这个平方误差最小化,易知当 cm 为相应单元上的所有实际值的均值时,可以达到最优

【机器学习笔记之三】CART 分类与回归树

那么如何生成这些单元划分?

假设,我们选择变量 xj 为切分变量,它的取值 s 为切分点,那么就会得到两个区域:

【机器学习笔记之三】CART 分类与回归树

当 j 和 s 固定时,我们要找到两个区域的代表值 c1,c2 使各自区间上的平方差最小,

【机器学习笔记之三】CART 分类与回归树

前面已经知道 c1,c2 为区间上的平均,

【机器学习笔记之三】CART 分类与回归树

那么对固定的 j 只需要找到最优的 s,
然后通过遍历所有的变量,我们可以找到最优的 j,
这样我们就可以得到最优对(j,s),并得到两个区间。

上述过程表示的算法步骤为:

【机器学习笔记之三】CART 分类与回归树

即:
(1)考虑数据集 D 上的所有特征 j,遍历每一个特征下所有可能的取值或者切分点 s,将数据集 D 划分成两部分 D1 和 D2
(2)分别计算上述两个子集的平方误差和,选择最小的平方误差对应的特征与分割点,生成两个子节点。
(3)对上述两个子节点递归调用步骤(1)(2),直到满足停止条件。


分类树的生成

(1)对每个特征 A,对它的所有可能取值 a,将数据集分为 A=a,和 A!=a 两个子集,计算集合 D 的基尼指数:

【机器学习笔记之三】CART 分类与回归树

(2)遍历所有的特征 A,计算其所有可能取值 a 的基尼指数,选择 D 的基尼指数最小值对应的特征及切分点作为最优的划分,将数据分为两个子集。
(3)对上述两个子节点递归调用步骤(1)(2), 直到满足停止条件。
(4)生成 CART 决策树。

其中 GINI 指数:

1、是一种不等性度量;
2、是介于 0~1 之间的数,0-完全相等,1-完全不相等;
3、总体内包含的类别越杂乱,GINI指数就越大(跟熵的概念很相似)

定义:
分类问题中,假设有 K 个类,样本属于第 k 类的概率为 pk,则概率分布的基尼指数为:

【机器学习笔记之三】CART 分类与回归树

样本集合 D 的基尼指数为:

【机器学习笔记之三】CART 分类与回归树

其中 Ck 为数据集 D 中属于第 k 类的样本子集。

如果数据集 D 根据特征 A 在某一取值 a 上进行分割,得到 D1 ,D2 两部分后,那么在特征 A 下集合 D 的基尼指数为:

【机器学习笔记之三】CART 分类与回归树

其中算法的停止条件有:

1、节点中的样本个数小于预定阈值,
2、样本集的Gini系数小于预定阈值(此时样本基本属于同一类),
3、或没有更多特征。

下面来看一下例子:

最后一列是我们要分类的目标。

【机器学习笔记之三】CART 分类与回归树

例如,按照“体温为恒温和非恒温”进行划分,计算如下:

恒温时包含哺乳类5个、鸟类2个

【机器学习笔记之三】CART 分类与回归树

非恒温时包含爬行类3个、鱼类3个、两栖类2个

【机器学习笔记之三】CART 分类与回归树

得到特征‘体温’下数据集的GINI指数:

【机器学习笔记之三】CART 分类与回归树

最后我们要选 GINI_Gain 最小的特征和相应的划分。


剪枝

就是在完整的决策树上,剪掉一些子树,使决策树变小。

【机器学习笔记之三】CART 分类与回归树

是为了减少决策树过拟合,如果每个属性都被考虑,那决策树的叶节点所覆盖的训练样本基本都是“纯”的,这时候的决策树对训练集表现很好,但是对测试集的表现就会比较差。

决策树很容易发生过拟合,可以改善的方法有:
1、通过阈值控制终止条件,避免树形结构分支过细。
2、通过对已经形成的决策树进行剪枝来避免过拟合。
3、基于Bootstrap的思想建立随机森林。

这里我们用 代价复杂度剪枝 Cost-Complexity Pruning(CCP) 方法来对 CART 进行剪枝。

【机器学习笔记之三】CART 分类与回归树

从整个树 T0 开始,先剪去一棵子树,生成子树 T1,
在 T1 上再剪去一棵子树,生成子树 T2,
重复这个操作,直到最后只剩下一个根节点的子树 Tn,
得到了子树序列 T0~Tn,
利用独立的验证数据集,计算每个子树的平方误差或者基尼指数,
选择误差最小的那个子树作为最优的剪枝后的树。

那么这个子树序列是怎么剪出来的?
因为建模的时候,目标就是让损失函数达到最优,那剪枝的时候也用损失函数来评判。

损失函数是什么呢?
对任意子树 T,损失函数如下形式,cost-complexity function:

【机器学习笔记之三】CART 分类与回归树

其中 CT 为误差(例如基尼指数),|T| 为 T 的叶节点个数,alpha 为非负参数,用来权衡训练数据的拟合程度和模型的复杂度。

alpha 固定时,一定可以找到一个子树 T,使得等式右边达到最小,那么这个 T 就叫做最优子树。

对固定的 alpha 找到损失函数最小的子树 T,二者之间有这样的关系:alpha 大时,T 偏小,alpha 小时,T 偏大。

那如果将 alpha 从小增大设置为一个序列,T 就可以从大到小得到相应的最优子树序列,并且还是嵌套的关系。

剪的时候,哪个树杈是可以被剪掉的呢?
很容易想到的是,如果剪掉后和没剪时的损失函数一样或者差别不大的话,那当然是剪掉好了,只留下一个点,就能代表一个树杈,这样树就被简化了。

以节点 t 为单节点树时,它的损失函数为:(后面剪枝后就可以用一个点来代替一个树杈)

【机器学习笔记之三】CART 分类与回归树

以节点 t 为根节点的子树 Tt,它的损失函数为:(后面剪枝这个树杈)

【机器学习笔记之三】CART 分类与回归树

那么接下来的问题就是能不能找到这样的点呢?
上面令 alpha=0,就有 Tt 和 t 的损失函数的关系为:

【机器学习笔记之三】CART 分类与回归树

那么增大 alpha,当它为如下形式时:

【机器学习笔记之三】CART 分类与回归树

此时,Tt 和 t 的损失函数相等,而 t 的节点少,那么保留 t 就可以了,Tt 就可以剪掉了。

【机器学习笔记之三】CART 分类与回归树

那么在剪枝算法的第三步时,对每个 t,计算一下 gt,也就是能找到子树 Tt 和 t 的损失函数相等时的 alpha,

每个点 t 都可以找到符合这样条件的 alpha,
遍历所有节点 t 后,找到最小的这个 alpha,

第四步,再把这个 alpha 对应的节点 t 的子树 Tt 剪掉,
并用多数投票表决法决定 t 上的类别,
这样得到的剪枝后的树 T 记为 Tk,
这时的 alpha 记为 alpha k,

经过上面步骤,会得到:
α1⩽α2⩽ ... ⩽αk⩽ ...
T1⊇T2⊇ ... ⊇Tk⊇ ... ⊇{root}

例子:

下面这棵树,有三个点 t1≡root,t2,t3

【机器学习笔记之三】CART 分类与回归树

α(1)=0

计算每个点的 gt:

【机器学习笔记之三】CART 分类与回归树

t2,t3 时的 gt 相等,此时我们可以选择剪枝少的点,那就是 t3 剪掉。

【机器学习笔记之三】CART 分类与回归树

并且 α(2)=1/8

这时剩下 t1,t2,再继续计算 gt:

【机器学习笔记之三】CART 分类与回归树

t2 的小,所以剪掉 t2:

【机器学习笔记之三】CART 分类与回归树

并且令 α(3)=1/8

最后剩下 t1,计算后 gt=1/4,所以 α(4)=1/4。

如此我们得到:α(0)=0,α(1)=1/8,α(2)=1/8,α(3)=1/4
并且得到了相应的子树,
接下来就可以利用独立的验证数据集,计算每个子树的平方误差或者基尼指数,