本章节是对我学习完机器学习（周志华）第四章 所做出来的总结

第四章 决策树

4.1 基本流程

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

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

决策树学习基本算法

4.2 划分选择

4.2.1 信息增益

“信息熵”是度量样本集合纯度最常用的一种指标。

在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

4.2.2 增益率

ID3决策树算法以信息增益为准则来选择划分属性。

C4.5决策树算法用“增益率”来选择最优划分属性。

信息增益准则对可选取数目较多的属性有所偏好；而增益率准则对可选取数目较少的属性有所偏好。

4.2.3 基尼指数

CART决策树使用“基尼指数”来选择划分属性，基尼指数越小，数据集的纯度越高。在一个侯选属性集合中，选择使得划分后基尼指数最小的属性作为最优化分属性。

4.3 剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段。

分为“预剪枝”和“后剪枝”

4.3.1 预剪枝

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

预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提高泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。

4.3.2 后剪枝

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

一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且有自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪纸决策树和预剪枝决策树都要大得多。

4.4 连续和缺失值

4.4.1 连续值处理

由于连续值不再有限，所以使用二分法对连续值进行处理，则正是C4.5决策树算法中采用的机制。

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

4.4.2 缺失值处理

关心2个问题：

1.如何在属性值缺失情况下进行属性选择？（简单的说 表头没有怎么办）

比如该节点是根据a属性划分，但是待分类样本a属性缺失，怎么办呢？假设a属性离散，有1,2两种取值，那么就把该样本分配到两个子节点中去，但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候，注意，不是每个样本都是权重为1，存在分数。

2.给定划分的属性，若样本缺失，如何划分？（简单的说 表头有了，表头里面的数据没有怎么办）

假如你使用ID3算法，那么选择分类属性时，就要计算所有属性的熵增(信息增益，Gain)。假设10个样本，属性是a,b,c。在计算a属性熵时发现，第10个样本的a属性缺失，那么就把第10个样本去掉，前9个样本组成新的样本集，在新样本集上按正常方法计算a属性的熵增。然后结果乘0.9（新样本占raw样本的比例），就是a属性最终的熵。

作者：andyham 链接：https://www.jianshu.com/p/27b1c7db47ae 來源：简书 简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

4.5 多变量决策树

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

决策树所形成的分类边界有一个明显的特点：轴平行。若能使用斜的划分边界，那么决策树模型将大为简化。这就是多变量决策树，在这里非叶结点不是针对单个属性，而是对模型的线性组合进行测试。如果模型的组合是非线性的，那么划分边界也将是非线性的。