02|CART的生成：

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

分类树与回归树的一个区别是：如果目标变量是离散型变量则用分类树，如果目标变量是连续型变量则用回归树。

2.1回归树的生成

回归树是用于目标变量是连续型变量的情况下，假设X与Y分别为输入和输出变量，并且Y是连续型变量，给定数据即D={(x1,y1),(x2,y2),…(xn,yn)}，根据训练数据集D生成决策树。

前面说过，回归树的生成准则是平方差(总离差平方和：实际观察值与一般水平即均值的离差总和)最小化准则，即预测误差最小化，所以我们的目的就是找到一个分界点，以这个点作为分界线将训练集D分成两部分D1和D2，并且使数据集D1和D2中各自的平方差最小。然后然后再分别再D1和D2中找类似的分界点，继续循环，直到满足终止条件。

在具体找分解值的时候采用遍历所有变量的方法，依次计算平方差，选择平方差最小时对应的分解值。

2.2分类树的生成

分类树用基尼指数选择最优特征(与信息增益类似)，同时决定该特征的最优二值切分点。

2.2.1基尼指数

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

对于二分类问题，若样本点属于第一类的概率为p，则概率分布的基尼指数为：Gini§=2p(1-p)。

对于样本给定的集合D，其基尼指数为：Gini(D)=1-∑(|Ck|/|D|)*2，这里Ck是D中属于第k类的样本子集，K是类的个数。

条件基尼指数：

图片

上面公式表示在特征A的条件下，集合D的基尼指数，其中D1和D2表示样本集合D根据特征A是否取某一个可能值a被分割成的两部分。

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数数值越大，样本集合的不确定性越大。

2.2.2算法步骤

输入：训练数据集D，停止计算的条件

输出：CART决策树

根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树：

设结点的训练数据集为D，计算现有特征对该数据集的基尼指数，此时，对每一个特征A，对其可能取的每一个值a,根据样本点A=a的测试为“是”或“否”将D分割成D1和D2两部分，然后计算Gini(D,A)。

在所有可能的特征A以及他们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最佳切分点。依最优特征与最优切分点，从现结点生成两个子节点，将训练数据集依特征分配到两个子节点中去。

对两个子节点递归调用.1，.2，直至满足停止条件。

生成CART决策树。

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

03|CART剪枝：

我们再前面那一章节提过剪枝是为了避免数据发生过拟合现象，而避免这种情况发生的方法就是使损失函数最小化。

先看看损失函数的公式：

图片