1700534559
1700534560
（3.23）
1700534561
1700534562
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切割法，每一步将数据按特征A的取值切成两份，分别进入左右子树。特征A的Gini指数定义为
1700534563
1700534564
1700534565
1700534566
1700534567
（3.24）
1700534568
1700534569
还是考虑上述的例子，应用CART分类准则，根据式（3.24）可计算出各个特征的Gini指数为
1700534570
1700534571
Gini(D|年龄=老)=0.4， Gini(D|年龄=年轻)=0.4，
1700534572
1700534573
Gini(D|长相=帅)=0.4， Gini(D|长相=丑)=0.4，
1700534574
1700534575
Gini(D|写代码=会)=0， Gini(D|写代码=不会)=0，
1700534576
1700534577
Gini(D|工资=高)=0.47， Gini(D|工资=中等)=0.3，
1700534578
1700534579
Gini(D|工资=低)=0.4．
1700534580
1700534581
在“年龄”“长相”“工资”“写代码”四个特征中，我们可以很快地发现特征“写代码”的Gini指数最小为0，因此选择特征“写代码”作为最优特征，“写代码=会”为最优切分点。按照这种切分，从根结点会直接产生两个叶结点，基尼指数降为0，完成决策树生长。
1700534582
1700534583
通过对比三种决策树的构造准则，以及在同一例子上的不同表现，我们不难总结三者之间的差异。
1700534584
1700534585
首先，ID3是采用信息增益作为评价标准，除了“会写代码”这一逆天特征外，会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。这在实际应用中是一个缺陷。比如，我们引入特征“DNA”，每个人的DNA都不同，如果ID3按照“DNA”特征进行划分一定是最优的（条件熵为0），但这种分类的泛化能力是非常弱的。因此，C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。
1700534586
1700534587
其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量。而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。
1700534588
1700534589
从应用角度，ID3和C4.5只能用于分类任务，而CART（Classification and Regression Tree，分类回归树）从名字就可以看出其不仅可以用于分类，也可以应用于回归任务（回归树使用最小平方误差准则）。
1700534590
1700534591
此外，从实现细节、优化过程等角度，这三种决策树还有一些不同。比如，ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART直接利用全部数据发现所有可能的树结构进行对比。
1700534592
1700534593
至此，我们从构造、应用、实现等角度对比了ID3、C4.5、CART这三种经典的决策树模型。这些区别与联系总结起来容易，但在实际应用中还需要读者慢慢体会，针对不同场景灵活变通。
1700534594
1700534595
问题2 如何对决策树进行剪枝？
1700534596
1700534597
难度：★★★☆☆
1700534598
1700534599
一棵完全生长的决策树会面临一个很严重的问题，即过拟合。假设我们真的需要考虑DNA特征，由于每个人的DNA都不同，完全生长的决策树所对应的每个叶结点中只会包含一个样本，这就导致决策树是过拟合的。用它进行预测时，在测试集上的效果将会很差。因此我们需要对决策树进行剪枝，剪掉一些枝叶，提升模型的泛化能力。
1700534600
1700534601
决策树的剪枝通常有两种方法，预剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。那么这两种方法是如何进行的呢？它们又各有什么优缺点？
1700534602
1700534603
分析与解答
1700534604
1700534605
预剪枝，即在生成决策树的过程中提前停止树的增长。而后剪枝，是在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树。
1700534606
1700534607
■ 预剪枝
1700534608