1.CART算法

分类与回归树（classification and regression tree，CART）模型由Breiman等人在1984年 提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。 CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即 特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条7件下输出的条件概率分布。

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

2.CART生成

决策树的生成就是递归地构建二叉决策树的过程。对分类树用基尼指数（Gini index）最小化准则，对回归树用平方误差最小化准则，进行特征选择，生成二叉树。

2.1 分类树的生成

CART分类树算法使用基尼系数选择特征，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。

（1）基尼指数

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

$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

如果是二类分类问题，计算就更加简单了，如果属于第一个样本输出的概率是p，则基尼系数的表达式为：

$$Gini(p)=2p(1-p)$$

对于个给定的样本D,假设有K个类别, 第k个类别的数量为$C_k$,则样本D的基尼系数表达式为：

$$Gini(D)=1-\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2$$

特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D2|}{|D|}Gini(D_2)$$

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A＝a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

（2）CART生成算法

输入：训练数据集D，停止计算的条件；
输出：CART决策树。

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A＝a的测试为“是”或“否”将D分割成$D_1$和$D_2$两部分，利用式$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D2|}{|D|}Gini(D_2)$计算A＝a时的基尼指数。
（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个 子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1）（2），直至满足停止条件
（4）生成CART决策树。

算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定 阈值（样本基本属于同一类），或者没有更多特征。

例 根据表所给训练数据集，应用CART算法生成决策树。

解：首先计算各特征的基尼指数，选择最优特征以及其最优切分点。分别以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征，并以 1，2，3表示年龄的值为青年、中年和老年，以1，2表示有工作和有自己的房子的值为是和否，以1，2，3表示信贷情况的值为非常好、好和一般。

求特征A1的基尼指数: