三种算法比较
ID3：采用信息增益作为选择特征的标准，越大越好
C4.5：采用信息增益率作为选择特征的标准，越大越好
CART：
- 回归：平方误差函数，越小越好
- 分类：基尼系数，越小越好
CART算法
CART算法由特征选择、树的生成及剪枝组成，可以用于回归也可以用于分类。CART假设决策树是二叉树，内部节点特征的取值为"是"和"否"，左边取值为"是"的分支，右边为"否"的分支，进行递归地二分每个特征，算法分为两步：
- 决策树生成：基于训练数据集生成决策树，生成的决策树尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝，并且选择最优树，用最小化损失函数作为剪枝的标准
决策树的生成就是递归地创建二叉树的过程。最小化准则：
- 回归：平方误差最小化
- 分类：基尼系数最小化
回归树
假设输入和输出变量分别是X和Y，并且Y是连续变量，在数据集上，如果将输入空间划分为M个单元，每个单元对应的输出值为，回归树模型为：平方误差为用来表示回归树对于训练数据的预测误差
分类树
分类数用基尼系数选择最优特征，同时决定该特征的最优二值分切分点。分类问题中，假设有K个类，样本点属于第k类的概率为，概率分布的基尼质数定义为：
对于二分类问题，若属于第一个类的概率为p，概率分布的基尼系数为：对给定的样本集合D，基尼系数为其中K是类的个数，是中属于第类的样本子集。
基尼系数表示样本集合的不确定性，基尼系数越大，样本集合的不确定性就越大
CART算法
输入：训练数据集D，停止计算的条件
输出：CART决策树
具体构建决策树的步骤为：
- 设节点的数据集为
D，计算现有特征对该数据集的基尼系数 - 在所有的特征
A以及它们可能的切分点中，选择基尼系数最小的特征及对应的切分点作为最佳选择。 - 从现有节点中生成两个子节点，将训练数据集分配到两个子节点中去
- 递归地调用上面两个步骤，直到满足停止条件
- 生成
CART树
停止条件：节点中样本数小于阈值，或者样本集的基尼系数小于阈值，或者没有更多特征