1、ID3与C4.5采用信息熵作为选择准则的基础（ID3采用信息增益，C4.5采用信息增益率），CART选择基尼指数作为选择准则的基础（分类树采用基尼指数，回归树采用方差，用最小二乘法求解）。

2、ID3和C4.5只用于分类，CART可以用于分类与回归。其中I

3、ID3和C4.5可以是多叉树，CART是二叉树。

4、ID3只能使用离散特征，C4.5和CART可以处理连续特征。

5、ID3不能处理缺失值，C4.5可以处理缺失值。

ID3采用信息增益作为准则来划分属性。

信息熵（information entropy）用来衡量数据集的混乱程度（纯度），信息熵越大，则表明数据集的混乱程度越大。

数据集D的信息熵用如下公式表示， 其中，Ck表示属于第k类的个数，所有类别数量的总和为D的数量。 条件信息熵的公式如下：

信息增益公式如下：

决策树的划分是一个递归过程。 （1）设置信息增益的阈值。 （2）选择信息增益最大的特征A。 （3）如果特征A的信息增益小于阈值A，则返回单节点树。采用投票法，该结点的类型为样本数量最多的类别。 （4）否则，按照特征A将节点划分为多棵子树，返回增加了子节点的节点。 （5）对各个子节点，递归调用上述步骤，直到达到停止标准（树的深度、信息增益阈值或者没有样本可划分）

C4.5采用信息增益率作为划分标准。

信息增益率 = 信息增益 / 分裂熵 数据集D信息增益率的公式为： 其中，分裂熵H(D)的公式为： 当A的取值越多时，分裂熵越大，信息增益率越小，达到了惩罚的目的。

需要注意的是，增益率可能会对数目少的特征有所偏好，因此C4.5采用了启发式的方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选出信息增益率最高的。

C4.5采用二分法处理连续特征，将连续特征进行排列，将连续两个值的中间值作为分裂节点，将小于该值和大于该值的样本分为两个类别，找到信息增益最大的分裂点，本质上还是用的离散特征。

需注意的是，与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性。

（1）如何在属性值缺失的情况下划分属性 将数据集分成两部分：没有缺失值的部分、有缺失值的部分。对每个样本设置一个权重，将没有缺失值的部分按照占据总样本的比例计算信息增益率，并乘上所占比例。

（2）给定划分属性，若样本在该属性上缺失，如何对样本进行划分 若样本x在划分属性a上的取值未知，则将x同时划入所有子节点，且样本权值按所占比例和样本权值进行调整。直观地看，这就是让同一个样本以不同的概率划入到不同的子节点中。

C4.5引入了正则项进行了初步的过拟合处理。

优点：

缺点：

CART的全称为Classification and Regression Tree，是最佳的决策树模型，sklear中的决策树也是应用的CART树。 CART是二叉树模型

分类树采用了基尼指数作为类别选择的依据。基尼纯度越小，代表数据集的纯度越高，分类效果越好。

特征p的基尼值公式如下： 特别的，当特征只有两个类别时，基尼指数为： 对于特征A，若其将数据集分为D1和D2两部分，则其基尼指数为： 在候选集中，选择那个使得划分后基尼指数最小的属性作为最优的划分属性。

熵和基尼指数的关系如下图： 可以看出基尼指数近似于熵。

与C4.5类似，采用连续特征离散化的思想。若特征A有k个取值，则有k-1个划分点，从这些划分点中选取基尼系数最小的划分点作为该特征的划分点。

思想是将特征二分化，形成很多划分组合，在这些组合中找到基尼指数最小的作为特征的划分标准。

CART树和ID3一样，也是递归的过程。给定阈值、树的深度作为输入的超参数。

1、如果基尼系数小于给定的阈值，则返回决策树子树，当前节点停止递归。如果当前节点的样本数小于阈值或者没有特征，返回决策子树，停止递归。

2、计算当前节点的现有的各个特征的各个特征值对数据集D的基尼系数。选择基尼系数最小的特征A和对应的特征值a。将数据集划分为两部分D1和D2。

3、对左右的子节点递归调用上述步骤。

对于生成的决策树预测时，加入测试集的样本X落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用这个叶子节点里概率最大的类别。（所以也可以输出概率）

回归树采用方差，利用最小二乘法求解方差和的极小值。

对于特征j，找到j所有的划分点s，s将数据集分为c1、c2两部分，找出使得两部分的方差最小，同时整体方差最小的特征j以及划分点s。 其中yi为数据集的均值： 对于离散特征，采用均值或者中位数作为节点的输出结果。

剪枝分为预剪枝和后剪枝，CART采用后剪枝。即先生成一颗决策树，然后产生所有剪枝后的CART树，使用交叉验证来检验各种减值后的效果，选择泛化能力最好的剪枝策略。