4.1 基本流程

创建树对数据进行分类（或者回归）。
根结点，内部结点（属性测试），叶结点（决策的结果）

4.2 划分选择

关键：如何划分（希望结点的纯度越来越高）

4.2.1 信息增益

信息熵：度量纯度的指标

信息熵Ent(D)越小，纯度越高。

信息增益：
信息增益越大，纯度得到的提升越大（用于属性的划分）

4.2.2 增益率

为了增加泛化能力（不要选择属性分类太多的）
增益率：

但是增益率偏好可取值数目较少的属性，也不太好。
应该先挑出信息增益高于平均水平的属性，再挑增益率最高的。

4.2.3 基尼指数

CART决策树用基尼指数来划分属性
基尼指数：随机抽取2个样本，其标记不同类的概率

基尼指数越小，纯度越高

4.3 剪枝处理

为了防止过拟合（因为分支过多了）
预留验证集进行评估

4.3.1 预剪枝

在划分前估计，如果当前这个属性不能有泛化性的提升，则停止划分，标记为叶结点

优点：不仅防止过拟合，还减少了决策树的训练时间和测试时间
缺点：带来欠拟合的风险

4.3.2 后剪枝

先生成决策树，自底向上考察，如果该内部节点替换成叶结点能有泛化性能的提升，则把该子树替换为叶结点
后剪枝比预剪枝保留了更多的分支。
优点：一般不会欠拟合，泛化性优于预剪枝
缺点：训练时间开销大（先建树，又自底向上遍历书）

4.4 连续与缺失值

4.4.1 连续值处理

连续属性离散化技术：二分法【C4.5决策树】
信息增益：（跟上面离散的一样）
划分点：中位点
特点：连续的属性在父节点用了，后代还可以用

4.4.2 缺失值处理（跳过）

需要解决2个问题：
1.属性值缺失，属性划分怎么选择？
2.给定划分，样本属性缺失怎么划分？

4.5 多变量决策树

分类边界的每一段都是与坐标轴平行的

但实际上，用“斜的”比较好

这就是多变量决策树
每个内部节点不再是对某个属性，而是对属性的线性组和进行测试