西瓜书-决策树
决策树是递归生成过程，递归边界：
- 训练集全部属于同一类
- 所有样本属性相同，标签不同，不能划分，标签为当前节点的大多数标签。
- 样本集合为空，不能划分，标签为父节点的大多数的标签。
第二种是利用当前节点的后验分布，第三种是利用腹肌诶单的样本分布当做当前节点的先验分布
根据每次划分选择的属性的方式，有以下决策树算法
信息熵：越小，纯度越高，类别数少
信息增益：纯度增大的度量
ID3
用信息增益选择划分属性
缺点：信息增益偏好类别多的属性
因此，有用增益率来选择属性的
**增益率：**信息增益除以类别数
C4.5
用增益率选择属性。
缺点：增益率偏好取值数目少的属性，C4.5使用启发式尊重：先从候选划分属性找出信息增益高于平均水平的，再选择增益率高的
CART决策树
**基尼系数：**反映从数据集中抽取两个样本，类别不一样的概率，越小，纯度越高，选择金指数最小的属性为划分属性。
剪枝
决策树对付过拟合。
预剪枝
在生成过程中剪枝，每个节点预先估计会不会带来性能的提升。
是一种贪心做法，当前没有性能提升，但是后来可能会带来性能提升；减少了时间和测试时间开销。
性能
主要指泛化性能，采用留出法检验，在验证集上测试。
后剪枝
从训练集生成完整的决策树
泛化性能更好，时间开销大
连续与缺失值
连续
连续属性离散化，使用二分法（C4.5），和离散属性不同，属性可以重复使用
缺失值处理
问题：
- 有缺失情况下怎么选择属性
- 如果该属性上的值缺失，怎么划分这个数据
解决：
- 信息增益乘上一个系数，信息增益只能在无缺失数据上求，系数表示无缺失值所占比例
- 将样本按照不同的概率划分到不同的子节点中。同时进入每一个节点，并乘上一个概率系数。
多变量决策树
单变量决策树决策边界是线性的，这里是对变量的线性组合
课后习题
最小训练误差作为划分依据的缺陷
过拟合
最小训练误差是求误差最小化，在样本有限的情况下，若根据最小训练误差来进行树的节点划分，只要节点数越接近样本数那么训练误差会越小，这样训练出来的决策树会过拟合，从而缺乏泛化能力。
练误差是求误差最小化，在样本有限的情况下，若根据最小训练误差来进行树的节点划分，只要节点数越接近样本数那么训练误差会越小，这样训练出来的决策树会过拟合，从而缺乏泛化能力。
