本文是我学习周志华老师编写的机器学习书籍『西瓜书』的第四章：决策树的过程中做的笔记。
决策树介绍
样本分类任务
决策树：基于树结构进行预测，符合人脑自然处理机制。
决策的最终结果
决策过程的判定问题
决策结果：
- 导出最终结论。
- 导出下一步判定问题（范围缩放）。
目的：生成一颗泛化能力强，即处理未见示例能力强的决策树。
决策树的生成是一个递归过程，一下三种情况将导致递归返回：
- 当前节点包含的样本全属于同一类别，无需划分
标记为叶结点。类别设定为当前唯一类别。 - 当前属性集为空，或是所有样本在所有属性取值相同，无法划分。
标记为叶结点，类别设定为该结点所含样本最多的类别。 - 当前结点包含的样本集为空，不能划分。
标记为叶结点，类别设定为父结点所含样本最多的类别。
划分选择
问题：最优划分？如何分？
我们希望随着划分的深入，样本的纯度越来越高。
纯度提升的度量：信息增益
信息熵与信息增益
def 信息熵：度量样本集合纯度的指标。
假定当前样本集合
假定离散属性
以样本量占比为依据，为不同分支结点赋予权重
信息增益
缺点：对可取值数目较多（该属性评价下样本体系更混乱）的属性有偏好。
解决方式：引入增益率。
增益率
def: 增益率（gain ratio）
其中，
属性 a 的取值数目越多（V越大），则
注意：增益率准则对可取值数目较少的属性有偏好。
解决方案 启发式算法：
在候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性作为当前结点属性标记。
基尼指数
def: 基尼指数（Gini index），使用基尼值度量纯度。
基尼值反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。
基尼值越小，数据集纯度越高。
属性
在候选属性集合
决策树剪枝
决策树防止过拟合的主要手段：
- 预剪枝
- 后剪枝
预剪枝
def: 在决策树生成过程中，对每个结点划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分，并将当前结点标记为叶结点。
后剪枝
def: 从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应地子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
具体操作
ex. 采用留出法，将数据集划分为训练集
对于预剪枝，假设当前生成的结点为叶结点，当前结点所含样本中最多的类别为该结点类别标记。比较替换前后决策树的泛化性（测试集精度），若泛化性提升，则替换成立，完成预剪枝操作。
对于后剪枝，在建树完成后，自底向上遍历类别结点，将其领衔的分支剪除（相当于替换为叶结点），比较替换前后决策树的泛化性（测试集精度），若泛化性提升，则替换成立，完成后剪枝操作。
连续和缺失值
连续值处理
讨论在决策树学习中使用连续属性
ex. 二分法
给定样本集
假设以序列数据中相邻两点间的一点为划分点，考虑包含
D 基于划分点 t 二分后的信息增益为：
与离散属性不同，若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性。
缺失值处理
两个问题
- 如何在属性值缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
给定训练集 D 和属性 a，令
假定我们为每一个样本
定义：
无缺失值样本占比。 -
无缺失值样本中第 k 类样本占比 -
无缺失值样本中 属性样本占比
基于上述定义，将信息增益计算进行推广：
其中：
多变量决策树
决策树是一系列弱分类器的组合，如果我们把属性视为坐标空间的一个坐标轴，那么每一个结点的决策面一定与坐标轴平行。
虽然这样的分类边界使得决策树有着较好的可解释性，但是真实场景的任务往往有着比较复杂的分类边界，导向复杂划分。
多变量决策树的思想