1. CART树

分类回归树(CART,Classification And Regression Tree)算法是一种决策树分类方法。CART每一个节点上都采用二分法，采用一种二分递归分割的技术，CART生成的树必须是二叉树，也就是无论回归还是分类，无论特征离散还是连续，无论属性取值有多个还是两个，内部节点只能根据属性进行二分。因此，CART算法生成的决策树是结构简洁的二叉树。CART算法既可以用分类任务，也可用于回归任务。

1-2 回归树

CART作为回归树：使用平方误差最小准则来选择特征并进行划分，也叫最小二乘回归树。对于特征j，找到j所有的划分点s，s将数据集分为c1、c2两部分，找出使得两部分的方差最小，同时整体方差最小的特征j以及划分点s。对于离散特征，采用均值或者中位数作为节点的输出结果。

1-3 分类树

CART作为分类树：使用Gini指数最小化准则来选择特征并进行划分。

1-4终止条件

CART算法构建二叉树 终止条件：

1、所有叶节点样本数为1，或属于同一类，或小于某一阈值；

2、树的高度到达某一阈值；

3、无剩余属性。

2.基尼指与基尼指数

2-1 基尼值

基尼值可用来度量数据集的纯度，数据集D的基尼系数Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)

2-2 基尼指数

基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。
Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。即基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率。

对于特征A，若其将数据集分为D1和D2两部分，则其基尼指数为：

在候选集中，选择那个使得划分后基尼指数最小的属性作为最优的划分属性。

2-3 案例

    1. 案例根据’有房者’、’婚姻’、’年收入’三个特征判断是否回拖欠贷款。

    2. 根据gini指数构建cart分类树的过程如下：

3.总结

基尼系数也是一种衡量信息不确定性的方法，与信息熵计算出来的结果差距很小，基本可以忽略，但是基尼系数要计算快得多，因为没有对数。熵和基尼指数的关系如下图：

Reference：
1.https://www.cnblogs.com/yuyingblogs/p/15319571.html