CART决策树是用”吉尼指数”来选择属性划分。数据集D的纯度可用基尼值来度量：
Gini(D)=∑k=1n∑k′≠kpkpk′=1−∑k=1np2k 直观来说， Gini(D) 反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此 Gini(D) 越小，数据集D纯度越高。因此属性 α 的基尼指数定义为： Gini(D,α)=∑v=1V|Dv||D|Gini(Dv) 假设数据集D在属性 α 上有 V 个不同的取值，则用属性α来划分时，一共有 v 个不同的分支。Dv指的是D中在 α 属性上取值为 αv 的所有样本集合。 Gini(Dv) 指的是前面划分的子样本集合 Dv 在标签 label 上的 Gini 不纯度。因此我们要做的就是在属性集合 A={α1,α2...,αn} 中，我们需要找出使得 Gini(D,αi) 最小的 αi ，即：
α∗=argminα∈AGini(D,α) 下面以一个简单的例子来进行说明： ID有房婚姻状况年收入label(是否拖欠贷款)1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是若采用是否有房作为分裂属性，则:
拖欠?有房无房未拖欠34拖欠03则:
Gini有房=1−(33)2−(03)2=0 Gini无房=1−(47)2−(37)2=0.4849 故 Ginihouse=710×Gini无房=710×0.4849=0.343 对于婚姻状况，有3种情况: 是否离异 拖欠?单身或已婚离异未拖欠61拖欠21此时
Ginit1=1−(68)2−(28)2=0.375 Ginit2=1−(12)2−(12)2=0.5 则 Gini1=0.8×0.375+0.2×0.5=0.4 是否已婚 拖欠?单身或离异已婚未拖欠34拖欠30此时
Ginit1=1−(33)2−(33)2=0.5$，$Ginit2=1−(44)2=0 则 Gini2=0.6×0.5=0.3 是否单身 拖欠?离异或已婚单身未拖欠52拖欠12此时
Ginit1=1−(56)2−(16)2=0.2778 Ginit2=1−(22)2−(22)2=0.5 则 Gini3=0.6×0.2778+0.4×0.5=0.3667 对于连续属性年收入，假设个样本的集合一个属性有个连续的值，那么则会有个分裂点，每个分裂点为相邻两个连续值的均值，每个属性的划分按照能减少的杂质的量来进行排序。采用如下方式来计算：分局基尼系数最小的原则，可以选择年收入是否大于97K或者是否已婚来作为第一步的分裂条件。
节点达到完全纯度
树的深度达到用户要求的深度
节点中样本个数少于指定数目
分类条件和列别的相关程度很弱 此时说明分裂条件和类别独立，即此时的分裂条件是没有道理的，节点应该停止分裂。这里的分裂条件是按照上面的 Gini Gini指数最小原则得到的分裂条件。独立性检验采用 χ2 检验法，例如下表： 此时动物类别与是否为恒温相互独立，再继续分裂没有意义，因此停止分裂。
CART采用复杂性剪枝法，即对于每一个非叶子节点计算它的表面误差率增益值 α ：
α=R(t)−R(Tt)|NTt|−1 其中 |NTt| 是子树中包含的叶子节点个数。 R(t) 是节点的误差代价。 R(t)=r(t)∗p(t) ， r(t) 是节点 t 的误差率，p(t)是节点t上数据所占的比率。 R(Tt) 是子树的误差代价，如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。例如： 则节点 t4 的误差代价为： R(t)=r(t)∗p(t)=716∗1660=760 节点 t4 的子树的误差代价为： R(Tt)=∑R(i)=260+360=560 节点 t4 的叶子节点共有3个，故： α=R(t)−R(Tt)|NTt|−1=7/60−5/603−1=16 继续剪枝，并找出 α 最小的非叶子节点，令其左右子树均为 NULL 。当多个非叶子节点的 α 值同时达到最小时，取 |NTt| 最大的进行剪枝。在CART树中，对所有的非叶子节点都要进行剪枝，直到剪枝为只有1个根节点为止。此时会得到一系列的决策树 {T0,T0,...,Tn} .然后采用交叉验证的方法，从 {T0,T0,...,Tn} 选出最优子树 Tα
参考文献： 1. 机器学习. 周志华 2. 统计学习方法. 李航
