简介CART类似于C4.5，是决策树算法的一种。另外，常见的决策树算法是ID3。三者的区别在于特征的划分：ID3：基于信息增益的特征划分C4.5：基于信息增益比的特征划分CART：基于基尼指数CART的基本思想的特征划分CART假设决策树是一棵二叉树，内部节点特征的值为“yes”和“no”，左分支为值为“yes”的分支，右分支为值为“no”的分支。这样一棵决策树相当于递归地平分每一个特征，将输入空间，也就是特征空间，划分成有限个单元，确定在这些单元上的预测概率分布，即输出的条件概率在给定的输入条件下分布。CART算法包括以下两个步骤：决策树生成：根据训练数据集生成决策树，生成的决策树要尽可能大；决策树剪枝：利用验证数据集对生成的树进行剪枝，选择最优的Tree，此时以最小损失函数作为剪枝标准。CART决策树的生成就是递归构建二叉决策树的过程。CART决策树可用于分类和回归。在本文中我们只讨论CART进行分类。对于分类树，CART使用基尼系数最小化准则进行特征选择，生成二叉树。CART生成算法如下：输入：训练数据集D，停止计算的条件：输出：CART决策树。根据训练数据集，从根节点开始，对每个节点递归进行如下操作，构建二叉决策树：设该节点的训练数据集为D，计算其上已有特征的基尼系数数据集。此时，对于每个特征A，对于它可能取的每个值a，根据样本点A=a是“是”还是“否”的检验，将D分为D1和D2两部分，A=a计算时间的基尼系数。在所有可能的特征A及其所有可能的分割点a中，选择基尼系数最小的特征及其对应的分割点作为最优特征和最优分割点。根据最优特征和最优分割点，从当前节点生成两个子节点，训练数据集根据特征分布到这两个子节点。对两个子节点递归调用步骤1~2，直到满足停止条件。生成CART决策树。算法停止计算的条件是节点中的样本数小于预定阈值，或者样本集的基尼系数小于预定阈值（样本基本属于同一类），或者没有更多的功能。代码代码已经在github上实现了（调用sklearn），这里也贴出测试数据集为MNIST数据集，结果获取地址为train.csv
