CART分类与回归

CART分类树与回归树

前记

本篇文章不会大幅度去介绍CART是怎么来的，以及CART与其他不同的地方，但是会着重的讲解在面试过程中遇到的问题，知识点的话会简单点的温习一下,本文是按照博主学习CART的过程俩编写，本文假设读者已经知道了ID3已经C4.5算法，若写的有问题，请指出，谢谢.

1. 为什么会有CART

我们已经知道在ID3中，我们是使用信息增益去作为分类的基准的，在现场面试中，面试官曾要求我们计算信息增益，以及选择分类的基准.首先是具备以下知识：

1.1 面试题1：信息增益（information gain）

首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

$H(x)=-\sum _{i=1}^{n}p_i\log{p_i}$H(x)=−i=1∑n​pi​logpi​

熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：

$H(X,Y)=-\sum _{i=1}^{n}P(x_i,y_i)\log(P(x_i,y_i))$H(X,Y)=−i=1∑n​P(xi​,yi​)log(P(xi​,yi​))

有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们的X在知道Y以后剩下的不确定性。表达式如下：

$H(Y|X)=\sum_{i=1}^n P_iH(Y|X=X_i)$H(Y∣X)=i=1∑n​Pi​H(Y∣X=Xi​)

有了上面的推导，我们下面给出信息增益的概念以及计算公式：信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度，其定义如下：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H（D）与特征A给定条件D下的经验条件熵H（D|A）之差，即

$g(D,A)=H(D)-H(D|A)$g(D,A)=H(D)−H(D∣A)

有了上面的基础，那么可以开始本次的面试题了，给定特征，计算信息增益以及确定分类特征。

下面的示例是以李航博士的统计学习方法为例：

比如存在上面的数据集D，我们分析初始时，哪一个作为分类节点较为合适,分别以$A_1,A_2,A_3,A_4​$A1​,A2​,A3​,A4​​表示年龄，有工作，有自己的房子和信贷情况，那么我们开始来计算每个特征的信息增益：

（1）计算D的熵：

$H(D)=-\frac{9}{15}\log_2\frac{9}{15}-\frac{6}{15}\log_2\frac{6}{15}=0.971$H(D)=−159​log2​159​−156​log2​156​=0.971

(2)对于特征$A_1$A1​的信息增益，因为分为三类（青年：5($D_1$D1​)，中年：5($D_2$D2​)，老年：5($D_3$D3​)），那么按照公式，我们首先得到总体的计算公式以及变换计算如下：

$g(D,A_1)=H(D)-H(D|A_1)=H(D)-\sum_{i=1}^{3}P_iH(D_i)$g(D,A1​)=H(D)−H(D∣A1​)=H(D)−i=1∑3​Pi​H(Di​)

那么我们的重点是计算后面的部分$\sum_{i=1}^{3}P_iH(D_i)$∑i=13​Pi​H(Di​),那么按照前面的内容，可得到其计算公式如下：

$\sum_{i=1}^{3}P_iH(D_i)=\frac{5}{15}*(-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5}) \\-\frac{5}{15}*(-\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5}) \\-\frac{5}{15}*(-\frac{1}{5}\log_2\frac{1}{5}-\frac{4}{5}\log_2\frac{4}{5}) \\=0.888$i=1∑3​Pi​H(Di​)=155​∗(−52​log2​52​−53​log2​53​)−155​∗(−52​log2​52​−53​log2​53​)−155​∗(−51​log2​51​−54​log2​54​)=0.888
计算出了这个后面内容后，我们可以将其带入公式，那么关于年龄这个特征的信息增益为：
$g(D,A_1)=H(D)-H(D,A_1)=0.971-0.888=0.083$g(D,A1​)=H(D)−H(D,A1​)=0.971−0.888=0.083
同理，后面就可以计算出$A_2,A_3,A_4$A2​,A3​,A4​的信息增益，选择出最大的一个即是可以作为我们的划分特征。

1.2 CART由来

中间穿插了一个面试题，现在是回到我们的主体内容中来，即为什么会有CART，了解了ID3选择特征的标准后，你会发现一个特点：在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大，当然我们不能让这种情况发生，于是后面昆兰大牛提出了C4.5算法解决这个问题。将划分特征的标准变为信息增益比，那么什么是信息增益比呢？

信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比的变量$I_R(X,Y)$IR​(X,Y)，它是信息增益和特征熵的比值。表达式如下：
$I_R(A,D)=\frac{I(A,D)}{H_A(D)}$IR​(A,D)=HA​(D)I(A,D)​

其中D为样本特征输出的集合，A为样本特征，对于特征熵$H_A(D)​$HA​(D)​, 表达式如下：

$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$HA​(D)=−i=1∑n​∣D∣∣Di​∣​log2​∣D∣∣Di​∣​

​ 其中n为特征A的类别数， Di为特征A的第i个取值对应的样本个数。|D|为样本个数。

特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

PS:对于ID3存在问题的部分，这里只给出相关的描述，且C4.5给出了相关的解答：

a)ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
c) ID3算法对于缺失值的情况没有做考虑
d) 没有考虑过拟合的问题

虽然C4.5对这四个主要的部分都给出了相关的解答（假设你已经了解了C4.5算法），那么肯定还是存在许多不足的地方，所以后面才会有CART，那C4.5还存在什么问题呢？

1)由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间(C4.5主要是通过正则化系数进行剪枝)。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。（PS：虽然存在预剪枝这种说法，但是实际没有用）
2)C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3)C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4)C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

于是，CART是解决上面四个问题而出现以及对ID3中存在的问题予以解决的方案。

###2. CART算法思路

2.1 CART对熵模型的改进

上面我们指出，使用大量的对数计算会非常耗费我们的计算资源，那么可不可以对这个方面进行改进呢？于是，我们引进了基尼系数，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。

基尼系数定义：在分类问题中，假设有K个类别，第k个类别的概率为$P_k$Pk​, 则基尼系数的表达式为：
$Gini(p)=\sum _{k=1}^KP_k*(1-P_k)$Gini(p)=k=1∑K​Pk​∗(1−Pk​)
对于个给定的样本D,假设有K个类别, 第k个类别的数量为$C_k$Ck​,则样本D的基尼系数表达式为：
$Gini(D)=1-\sum _{k=1}^K\frac{|C_k|}{|D|}$Gini(D)=1−k=1∑K​∣D∣∣Ck​∣​
特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D1)+\frac{|D_2|}{|D|}Gini(D2)$Gini(D,A)=∣D∣∣D1​∣​Gini(D1)+∣D∣∣D2​∣​Gini(D2)
那么这种近似替代会存在多大误差呢？可以看下面的图：

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

PS:作为练习，你能不能采用基尼系数对上文给出的面试题进行计算，得到最适合作为划分的特征。

2.2 CART分类树算法对于连续特征和离散特征处理的改进

对于CART分类树连续值的处理问题，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，而CART分类树使用的是基尼系数。

具体的思路如下，比如m个样本的连续特征A有m个，从小到大排列为a1,a2,…,am，则CART算法取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示Ti表示为：$T_i=\frac{a_i+a_{i+1}}{2}$Ti​=2ai​+ai+1​​。对于这m-1个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。如取到的基尼系数最小的点为$a_t$at​,则小于$a_t$at​的值为类别0，大于$a_t$at​的值为类别1，这样我们就做到了连续特征的离散化。

要注意的是，与ID3或者C4.5处理离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。

回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3},{A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。

2.3 CART回归树

既然常见的ID3和C4.5算法只能用于分类，那么CART算法是否也只能用于分类呢？答案是否定的，CART是可以使用在回归算法上面的。主要讲解以下两个方面：

首先想一下，我们的树模型时怎么产生回归的？不是不同的结点（差别较大）的结点会被分到不同的子树中去么？终究要考虑一点，树模型时怎么产生回归的以及怎么划分结点：

（1）对于回归模型，我们使用了常见的和方差的度量方式，CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。（好好看下公式，面试考点）,用公式表达如下：
$\underbrace{min}_{A,s}[\underbrace{min}_{c_1}\sum_{x_i\in D_1(A,s)}(y_i-c_1)^2+\underbrace{min}_{c_2}\sum_{x_i\in D_2(A,s)}(y_i-c_2)^2 ]$A,smin​​[c1​min​​xi​∈D1​(A,s)∑​(yi​−c1​)2+c2​min​​xi​∈D2​(A,s)∑​(yi​−c2​)2]

其中：$C_1$C1​为$D_1$D1​数据集的样本输出均值，$C_2$C2​为$D_2$D2​数据集的样本输出均值。

面试题如下：

你已经知道了决策树的回归是采用和方差作为基准的，那么刚开始训练的时候，你的预测值是没有的，请问你是怎么处理这个问题的？

解答：之前看的时候遗忘了这一点，后面和同学讨论，发现以树模型来回归的话，都是存在刚开始预测值是不存在的，那么我们可以采用某个数据集里面的均值最为最开始的预测值。（PS：就是上面的那句话…）

（2）假设已经到了一个子树里面去了，那么怎么做预测呢？

CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

2.4 CART树算法的剪枝

由于决策树算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，来增加决策树的泛化能力。CART采用的办法是后剪枝法，后面的内容主要来分析后剪枝算法

也就是说，CART树的剪枝算法可以概括为两步，

第一步是从原始决策树生成各种剪枝效果的决策树，

第二步是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的树作为最终的CART树。

那么按照步骤来进行，我们可以分析如下：

对于位于节点t的任意一颗子树Tt，如果没有剪枝，它的损失函数是
$Ca(T_t)=C(T_t)+\alpha|T_t|$Ca(Tt​)=C(Tt​)+α∣Tt​∣
其中$\alpha​$α​是正则化因子，$|T_t|​$∣Tt​∣​是子树$T_t​$Tt​​的结点的个数，$C(T_t)​$C(Tt​)​为训练数据的预测误差

如果将其剪掉，仅仅保留根节点，则损失是
$Ca(T_t)=C(T)+\alpha$Ca(Tt​)=C(T)+α
这样分析之后，何时才能确定剪枝呢？

我们可以假设当剪枝前和剪枝后的损失函数相同，即T这个树的结点数更少，可以对Tt这个子树进行剪枝，直接将其变为树T。有了上面的假设，即（14）=（15），我们可以得到等式如下
$C(T_t)+\alpha|T_t|=C(T)+\alpha$C(Tt​)+α∣Tt​∣=C(T)+α
解得：

​ $\alpha=\frac{C(T)-C(T_t)}{|T_t|-1}$α=∣Tt​∣−1C(T)−C(Tt​)​

那么如何选择出最优的CART分类树呢？我们可以采用交叉验证策略，上面我们计算出了每个子树是否剪枝的阈值$\alpha​$α​，如果我们把所有的节点是否剪枝的值$\alpha​$α​都计算出来，然后分别针对不同的$\alpha​$α​所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的$\alpha​$α​，有了这个$\alpha​$α​，我们就可以用对应的最优子树作为最终结果。

3.Reference

李航 《统计数学方法》

https://www.cnblogs.com/pinard/p/6053344.html

https://zhuanlan.zhihu.com/p/36108972