《机器学习》第四章决策树

4.1 基本流程

决策树(decision tree)是一类常见的机器学习方法。基于树结构来进行决策，进行一系列的判断或“子决策”。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;叶结点对应于决策结果，其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

基本流程：

区别：情形(2)是在利用当前结点的后验分布，而情形(3)则是把父结点的样本分布作为当前结点的先验分布.

4.2 划分选择

决策树学习的关键是选择最优划分属性.

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

信息增益

增益率

增益率准则对可取值数目较少的属性有所偏好，因此 C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的.

基尼指数

4.3 剪枝处理

剪枝主要为了对付“过拟合”。

决策树分支过多，导致模型把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合，因此可主动去掉一些分支来降低过拟合的风险.

基本策略：1）预剪枝和 2）后剪枝

1）预剪枝

指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;

①降低了过拟合的风险

②减少了决策树的训练时间开销和测试时间开销.

③未将一些有“潜力”的分支展开，有欠拟合风险.

2）后剪枝

先从训练集生成一棵完整的决策树, 然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

保留更多分支，欠拟合风险小，泛化性能优训练时间开销大.

4.4 连续与缺失值

连续属性离散化技术实现在决策树学习中使用连续属性

二分法

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性.

缺失值处理

4.5 多变量决策树

把每个属性视为坐标空间中的一个坐标轴，则 d 个属性描述的样本就对应了 d 维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界.

在分类边界比较复杂时，单分类边界使得决策树相当复杂，“多变量决策树”使其形成斜的边界，使模型大大简化。非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试。