决策树CART介绍*

属性划分使用Gini指数

回顾：ID3使用信息增益，C4.5使用信息增益率。都是基于计算熵，熵运算涉及到对数运算，耗时。
CART使用Gini指数代替信息增益。

直观上，Gini指数表示从数据集D随机抽取两个样本，类别不一致的概率。
注意：GIni指数越小，数据集D纯度越高，这与信息增益相反。
所以，在找划分属性时，每个属性a的GIni指数具体计算公式如下：

CART创建的决策树是二叉树，也就是划分节点的时候是二分。

CART连续特征的处理

与C4.5的几乎相同，都是讲连续特征离散化后二分，只是评价指标换成了Gini指数。
假设连续属性A在数据集D上有m个取值$a_1,...,a_m$，对相邻取值做平均数，得到m-1个二划分点。选择使得划分后Gini指数最小的划分点进行二划分。
注意： 当前节点若为连续属性，则该属性后面还可以参与子节点的属性划分过程。

CART对离散特征的二分改进

回顾：C4.5和ID3对属性A划分，若属性A的取值有$a_1,a_2,a_3$三个，则就是划分出3个分支。（有多少种属性取值，就划分出多少个分支）
CART采用的是不停二分的办法。 比如，先把A的取值分成 { a 1 } , { a 2 , a 3 } \{a_1\},\{a_2,a_3\} {a1​},{a2​,a3​}； { a 1 , a 2 } , { a 3 } \{a_1,a_2\},\{a_3\} {a1​,a2​},{a3​}； { a 2 } , { a 1 , a 3 } \{a_2\},\{a_1,a_3\} {a2​},{a1​,a3​}三种情况，找到使得Gini指数最小的组合，然后建立二叉树节点。假设选取的是$a_1,a_2,a_3$，那这次划分就没有将$a_2,a_3$划分开来，所以A属性还可以参与后续的属性划分。

CART回归树

和分类树的主要区别：

1. 划分的评价指标是均方误差。

2. 树建立以后的预测方式不同。

   分类树采用的是Gini指数作为标准，但是这对回归模型显然不适用。
   CART回归的度量目标：对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为：
   
   预测方式：采用最终叶子的均值或者中位数来做预测输出结果。
   注：我的理解，上式内层的min应该是固定一个特征，选择这个特征下最优的二划分点；外层的min就是在选择最优的划分特征。

剪枝

目的是为了决策树过拟合。剪枝方法适用于分类树与回归树。
CART采用的剪枝方法是后剪枝。
以后补…