决策树 - CART

CART

Breiman等在1984年提出了 分类与回归树模型(CART, Classification and regression tree)。

CART能够输出随机变量$Y$的 条件概率分布

CART的一个重要特点是假设决策树是二叉树,这意味着不论特征是连续型随机变量还是多个取值的离散型随机变量,都将被处理成二元变量,即需要确定一个 阈值

CART生成

生成回归树

给定训练数据集
$$
D = { (x_1, y_1),(x_2,y_2), \cdots, (x_N,y_N) }
$$
如果选定第$j$个特征和该特征的某个取值$s$,我们就能将所有样本的第$j$个特征的取值与$s$分别进行比较,从而将数据集$D$划分为两部分。对于这两个划分的子数据集$D_1$和$D_2$,我们再次执行上面的操作进行进一步的划分……

最终我们将数据集$D$划分成了$M$个子集,或者说将输入空间(特征空间)划分成了$M$个区域。对于划分的每一个子区域$R_m$($m=1,2,\cdots,M$)我们可以通过某种方法求出这样一个值$c_m$,于是就可以定义 回归模型
$$
f(x) = \sum_{m=1}^M c_m I(x \in R_m)
$$
其中$I(x \in R_m)$称为 指示函数,样本$x$只会属于子区域中的某一个,而不会同时被划分到多个子区域,因为互斥完备。

这里产生了两个问题:

  1. 如何确定最优的$j$和$s$?
  2. 如何定义$c_m$?

先看第二个问题:因为是回归模型,我们用 平方误差 来表示回归树对训练数据的预测误差
$$
\begin{split}
L(D) &= \sum_{i=1}^N [y_i - f(x_i)]^2 \\
&= \sum_{m=1}^M \sum_{x_k \in R_m} [y_k - f(x_k)]^2 \\
&= \sum_{m=1}^M \sum_{x_k \in R_m} (y_k - c_m)^2
\end{split}
$$
若使$L(D)$最小,则使$\sum_{x_k \in R_m} (y_k - c_m)^2$最小,一阶导等于0极小,解得
$$
C_m = \frac1{|D_m|} \sum_{k=1}^{|D_m|} y_k = avg(y_k|x_k \in R_m)
$$
其中数据集$D$位于子空间$R_m$中的子数据集为$D_m$,$|D_m|$为数据集$D_m$中的样本总数。

综上所述,子空间$R_m$上的$c_m$的最优估计值$\hat{c}_m$是$R_m$上所有输入样本对应的$y$的均值。

再看第一个问题:怎么确定最优的$j$和$s$,亦即怎么对样本空间进行划分。

这里我们将第$j$个变量称为 切分变量(splitting variable),将该变量的取值$s$称为 切分点(splitting point),并进行如下划分:
$$
\begin{split}
R_1(j,s) &= { x|x^{(j)} \le s } \\
R_2(j,s) &= { x|x^{(j)} \gt s}
\end{split}
$$
启发式 方法寻找最优的切分变量$j$和切分点$s$:遍历所有输入输入特征,固定$j$扫描可能的切分点$s$,计算
$$
Loss(j,s) = \sum_{x_i \in R_1(j,s)}(y_i-\bar{y_i})^2 + \sum_{x_i \in R_2(j,s)}(y_i-\bar{y_i})^2
$$
哪组$(j,s)$的$Loss$小就选谁。

迭代划分得到$M$个子区域。

生成分类树

基尼指数

基尼指数 用来度量集合$D$的不确定性,基尼指数越大,集合$D$的不确定性越大,与类似。
$$
\text{Gini}(p) = \sum_{k=1}^K p_k(1-p_k) = 1 - \sum_{k=1}^K p_k^2
$$
二分类问题的基尼指数为 $2p(1-p)$

样本集合$D$的基尼指数为 $1-\sum_{k=1}^K (\frac{|D_k|}{|D|})^2$

依据某特征A是否取值为a可将数据集D分为两个子集$D_1$和$D_2$
$$
\begin{split}
D &= D_1 + D_2 \\
D_1 &= { (x,y) \in D | A(x) = a } \\
D_2 &= { (x,y) \in D | A(x) \ne a }
\end{split}
$$
在特征A的条件下数据集D的基尼指数定义为
$$
\text{Gini}(D,A) = \frac{|D_1|}{|D|}\text{Gini}(D_1) + \frac{|D_2|}{|D|}\text{Gini}(D_2)
$$

CART生成

遍历所有的可用的特征,遍历该特征所有可能的取值,分别计算基尼指数,取基尼指数最小的切分变量和切分点作为当前二分数据集的策略。

递归对数据集进行二分。

以下表为例说明基尼指数如何用于选择切分变量和切分点

$$
\begin{split}
\text{Gini}(D,A=1) &= \frac{5}{15}(2 \times \frac25 \times (1-\frac25)) + \frac{10}{15}(2 \times \frac7{10} \times (1 - \frac7{10})) \\
&= 0.44 \\
\text{Gini}(D,A=2) &= 0.48 \\
\text{Gini}(D,A=3) &= 0.44
\end{split}
$$
$\text{Gini}(D,A=1)$或者$\text{Gini}(D,A=3)$都可以作为A的最优切分点

同理求得其它特征的最优切分点
$$
\begin{split}
\text{Gini}(D,B=1) &= 0.32 \\
\text{Gini}(D,C=1) &= 0.27 \\
\text{Gini}(D,E=3) &= 0.32
\end{split}
$$
上面的四个切分点中,$\text{Gini}(D,C=1)$最小,所以选择特征C(有自己的房子)作为最优分类特征,C=1为最优切分点,将数据集D分为两个子集,同时根节点也产生了两个子节点。由于C=1的样本标签全部为1,则此节点为叶子节点,类别标记为1;接下来对另一个子节点进行寻找最优分类特征和最优切分点。

CART剪枝

CART剪枝算法是个很费解的东西,我尝试着通俗化地去描述它。

CART的剪枝同ID3/C4.5的剪枝算法有些许区别。ID3/C4.5的剪枝算法直接计算内部节点剪除前后决策树损失大小,CART剪枝算法多了一步:先从“完全生长”的整树$T_0$开始一个节点一个节点(内部节点)的剪除,直到剩下最后的根节点$T_n$,每剪一次就会得到一棵树,这样就得到了一个树的序列${T_0,T_1,\cdots,T_n}$,注意这里的$n$并不是指整树内部节点的多少,实际上由整树生成的子树非常多,这个$n$可能会很大,但是它始终是有限的;然后在 验证数据集 上分别进行测试,选择损失最小的树作为最终结果。

先来回顾一下决策树$T$的损失函数的定义,其中$C(T)$是对训练数据的预测误差,$|T|$是模型复杂度:
$$
C_\alpha(T) = C(T) + \alpha |T|,\ \alpha \ge 0
$$
在ID3/C4.5的剪枝算法中,$\alpha$作为超参需要预先设定,当我们预设$\alpha$的值后对整树进行剪枝,最后会得到一个整树的子树作为最终结果,这里$0<\alpha<+\infty$,特别地,当$\alpha=0$时,整树是最优解;当$\alpha=+\infty$时仅由根节点构成地单节点树是最优解,当然一般情况下$\alpha=0$或者$\alpha=+\infty$都不会是我们想要的结果。所以,当我们确定了$\alpha$的值时,我们就确定了整树的某一棵子树;换言之,一个$\alpha$值对应着一颗子树,而这棵子树就是这个$\alpha$条件下的最优解。

如果我更改$\alpha$的值就会得到不同的子树,那么哪一棵子树才是最好的呢?CART剪枝算法把$\alpha$视为一个参数而不是超参,在剪枝的过程中寻找最优的$\alpha$和这个$\alpha$对应的最优子树。$\alpha \in (0,+\infty)$表示$\alpha$有无穷多的取值,那这是不是意味着有无穷多的子树呢?显然不是的,因为整树的节点是有限的,所以整树的子树肯定是有限的。但是一个$\alpha$必定对应着一棵子树,这就表示很多个$\alpha$对应着相同的子树,换言之,一棵子树对应着很多个$\alpha$值,一棵子树对应了一个$\alpha$的区间。我们将$[0,+\infty]$区间分成$[\alpha_0,\alpha_1)$、$[\alpha_1,\alpha_2)$、…、$[\alpha_n,\alpha_{n+1})$,其中$\alpha_0=0$, $\alpha_{n+1}=+\infty$,每个区间$[\alpha_i,\alpha_{i+1})$的$\alpha$对应的最优子树都是$T_i$。于是乎,我们假设,如果我们可以求出每个子树$T_i$对应区间的左$\alpha$的值,我们就能将子树$T_i$与$\alpha$区间一一对应,通过求解最优子树来求解最优$\alpha$。

那么问题来了,怎么通过子树求区间左边界的$\alpha$呢?

我们通过比较剪除节点$t$前后损失的变化来决定是否剪除节点$t$。我们观察预测误差$C_\alpha(T)= \sum_{k=1}^{|T|} N_k H_k(T)$:独立计算每个叶子节点$N_kH_k(T)$再求加和,这意味着剪除节点$t$整个决策树的损失变化就等价于上图中粉色区域子树剪除节点$t$损失的变化。

对于整树$T_0$的任意一个内部节点$t$,假设剪除此节点得到的子树为$T_k$,$k \in {1,\cdots,n}$。

以$t$为根节点的单节点树的损失函数为
$$
C_\alpha(t) = C(t) + \alpha |t| = C(t) + \alpha
$$
以$t$为根节点的多节点子树$T_t$的损失为
$$
C_\alpha(T_t) = C(T_t) + \alpha |T_t|
$$
上面两个式子中的$C(t)$和$C(T_t)$都是可求的。

当$\alpha=0$或者$\alpha$充分小时,预测误差占损失函数的大头,单节点树的损失肯定比多节点子树高,$C(t)>C_\alpha(T_t)$;当$\alpha$充分大时,模型复杂度占损失函数的大头,单节点树的损失肯定比多节点树低,$C(t)<C_\alpha(T_t)$。如果单节点损失较大,说明还是保留$t$的叶子节点比较好,因为损失比较小,此时不剪枝;如果单节点树的损失较小,说明应该剪除内部节点$t$。

那么应该存在这样一个不大不小的$\alpha$,使得单节点树的损失刚好等于多节点树的损失,即$C_\alpha(t)=C_\alpha(T_t)$,解得
$$
\alpha’ = \frac{C_t - C(T_t)}{|T_t|-1}
$$
如果$\alpha$的值比这个$\alpha’$小,单节点树损失更大,意味着不能剪$t$;当$\alpha$的值比这个$\alpha ‘$大,单节点树损失更小,意味着应该剪除$t$。根据前面的叙述,子树$T_k$对应的$\alpha$区间为$[\alpha_k, \alpha_{k+1})$,子树$T_k$存在的前体就是相应内部节点被无情的剪除了,所以$\alpha_k = \alpha’$。

所以,我们对整树$T_0$的所有内部节点求其$\frac{C_t - C(T_t)}{|T_t|-1}$,按$\alpha$从小到大依次剪除对应的节点得到相应的子树序列${T_0,T_1,\cdots,T_n}$。

至此,我们已经拿到了按照$\alpha$从小到大排列的子树序列,接下来在 验证数据集 上进行验证,取损失最小的子树即可。

----- For reprint please indicate the source -----
0%