| 模型 | ID3 | C4.5 | CART |
|---|---|---|---|
| 结构 | 多叉树 | 多叉树 | 二叉树 |
| 特征选择 | 信息增益 | 信息增益率 | Gini系数/均方差 |
| 连续值处理 | 不支持 | 支持 | 支持 |
| 缺失值处理 | 不支持 | 支持 | 支持 |
| 枝剪 | 不支持 | 支持 | 支持 |
- 构建根节点，将所有训练数据都放在根节点
- 选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类
- 如果子集非空，或子集容量未小于最少数量，递归1，2步骤，直到所有训练数据子集都被正确分类或没有合适的特征为止
其中，D为数据全集，C为不同因变量类别k上的子集(传统意义上的y的种类)
条件信息熵：在特征A给定的条件下对数据集D分类的不确定性：
信息增益：知道特征A的信息而使类D的信息的不确定减少的程度（对称）： I(D,A) = H(D)-H(D/A)
简而言之，就是在特征A下找到最合适的切分，使得在该切分下信息量的变换最大，更加稳定；但是这个有一个问题，对于类别天生较多的特征，模型更容易选中，因为特征类别较多，切分后的信息增益天生更大，更容易满足我们的原始假设
在信息增益计算的基础不变的情况下得到的：I(D,A) = H(D)-H(D/A)，同时还考虑了
信息增益率：
Gini系数二分情况下：
对于决策树样本D来说，
对于样本D，如果根据特征A的某个值，把D分成D1和D2，则在特征A的条件下，D的基尼系数为：
缺点：
- 存在偏向于选择取值较多的特征问题
- 连续值不支持
- 缺失值不支持
- 无法枝剪
- 主动进行的连续的特征离散化
- 比如m个样本的连续特征A有m个，先set在order，再两两组合求中间值，以该值点作为划分的待选点
- 连续特征可以再后序特征划分中仍可继续参与计算
- 缺失问题优化
- 训练：用所有未缺失的样本，和之前一样，计算每个属性的信息增益，但是这里的信息增益需要乘以一个系数（未缺失样本/总样本）
- 预测：直接跳过该节点，并将此样本划入所有子节点，划分后乘以系数计算，系数为不缺失部分的样本分布
- 采用预枝剪
- 分类情况下的变量特征选择
- 离散变量：二分划分
- 连续变量：和C4.5一致，如果当前节点为连续属性，则该属性后面依旧可以参与子节点的产生选择过程
- 回归情况下，连续变量不再采取中间值划分，采用最小方差法
我们的算法从根节点开始，用训练集递归的建立CART树。
- 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归
- 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归
- 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数
- 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2
- 递归1～4
其他部分都一样，在构建过程中遇到连续值的话，并不是利用C4.5中的中间值基尼系数的方式，而是采取了最小方差方法：
对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点，其中c1为D1的均值，c2为D2的均值：
- 回归树：利用最终叶子的均值或者中位数来作为输出结果
- 分类树：利用最终叶子的大概率的分类类别来作为输出结果
目标函数为：𝐶𝛼(𝑇𝑡)=𝐶(𝑇𝑡)+𝛼|𝑇𝑡|，其中，α为正则化参数，这和线性回归的正则化一样。𝐶(𝑇𝑡)为训练数据的预测误差，分类树是用基尼系数度量，回归树是均方差度量。|𝑇𝑡|是子树T的叶子节点的数量
当𝛼=0时，即没有正则化，原始的生成的CART树即为最优子树。当𝛼=∞时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。 当然，这是两种极端情况。一般来说，𝛼越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。对于固定的𝛼，一定存在使损失函数𝐶𝛼(𝑇)最小的唯一子树。 由枝剪到根结点及不枝剪两种情况可得：𝛼=(𝐶(𝑇)−𝐶(𝑇𝑡))/(|𝑇𝑡|−1) , C(T)为根结点误差
- 计算出每个子树是否剪枝的阈值𝛼
- 选择阈值𝛼集合中的最小值
- 分别针对不同的最小值𝛼所对应的剪枝后的最优子树做交叉验证
无论是分类树还是回归树，无论是连续变量还是离散变量，树模型一直想找的是最优切分点，不存在梯度导数等计算，数值缩放不影响分裂点位置，对树模型的结构不造成影响。
优点：
- 缺失值不敏感，对特征的宽容程度高，可缺失可连续可离散
- 可解释性强
- 算法对数据没有强假设
- 可以解决线性及非线性问题
- 有特征选择等辅助功能
缺点：
- 处理关联性数据比较薄弱
- 正负量级有偏样本的样本效果较差
- 单棵树的拟合效果欠佳，容易过拟合