定义：
一颗[决策树]包含一个根节点、若干个内部节点和若干个叶节点；
叶节点：对应决策结果，即样本的label
根 + 内部节点：对应一个分割[数据集]方法，根据该方法将节点对应的数据集划分到子节点中。
根到叶节点的路径：对应一个判定序列
image.png
流程：
和递归算法类似，先确定退出条件（设置叶节点）：
image.png
该节点中数据集的label相同
属性集为空集，或者数据集的属性值相同
该节点的数据集为空集
条件1：label都相同了，直接将叶节点标记为该label即可
条件2：有数据，但无法根据属性继续划分。该叶节点label少数服从多数
条件3：无数据，根据父节点的样本label 少数服从多数
每次递归最核心的问题是 选取怎样划分规则，来划分当前节点对应的数据集
信息熵：
本质：越混乱（随机事件越不确定），信息量越大
image.png
信息增率
存在一个badcase: 若每个样本在属性A上取值都不同，此时，根据该属性A划分，信息增益最大。但这样泛化性太差
4.3 剪枝处理
目标：降低过拟合，提高泛化性。
方式：根据在验证集上表现判断是否剪枝。
4.3.1 预剪枝
思想：在处理非叶节点时，判断划分该节点能否带来性能提升，有提升则划分，没有则不划分。
优点：只用一次建树，速度快
缺点：存在欠拟合风险
image.png
后剪枝
思想：先生成决策树，从底向上判断是否要将非叶节点替换为叶节点。
优点：相比预剪枝，会保留更多枝，学习更充分
缺点：训练开销大
