决策树
- 决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树
基本流程
有三种情形会导致递归返回: (1) 当前结点包含的样本全属于同一类别，无需划分; (2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：标记为叶节点，类别设为该结点所含样本最多的类别 (3) 当前结点包含的样本集合为空，不能划分：标记为叶结点，将其类别设定为其父结点所含样本最多的类别
划分选择
信息增益
- 信息熵用于度量样本集合 D 纯度的指标：越小纯度越高
\[
Ent(D) = -\sum_{k=1}^{|\mathcal{y}|}p_k\text{log}_2p_k
\]
其中，\(\mathcal{y}\) 为样本类别数
- 用属性 a (有V个可能取值)对样本集 D 进行划分所获得的"信息增益"（信息熵的减少量）：
\[
\text{Gain}(D,a) = \text{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{D} \text{Ent}(D^v)
\]
- ID3决策树学习算法使用信息增益作为准则选择划分属性
信息增益率
- 信息增益准则对可取值数目较多的属性有所偏好（比如学号，其信息熵为0），为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法使用“增益率”来选择最优划分属性。定义为：
\[
\text{Gain\_ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)}
\]
其中，
\[
\text{IV}(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{log}_2\frac{|D^v|}{|D|}
\]
称为属性a的“固有值”，取值数目越多，IV越大。
- 增益率准则对可取值数目较少的属性有所偏好，因此 C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均的属性，再从中选择增益率最高的。
基尼指数
- CART决策树使用基尼指数选择划分属性：
\[
\text{Gini}(D) = 1 - \sum_{k=1}^{|y|}p_k^2
\]
- 它反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率.因此， Gini(D) 越小，则数据集 的纯度越高.
- 属性a的基尼指数定义如下，选择基尼指数最小的属性作为最优划分属性
\[
\text{Gini\_index}(D,a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{Gini}(D^v)
\]
剪枝
- 剪枝防止过拟合
预剪枝
- 预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停划分并将当前结点标记为叶结点;
- 如何判断决策树泛化性能是否提升呢？这可使用第一章中介绍的性能评估方法，如留出法，预留验证集进行验证
- 好处：降低过拟合风险，显著减少决策树训练时间开销和测试时间开销
- 问题：有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降。但在其基础上进行的后续划分却有可能导致性显著提高。预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险
后剪枝
- 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结能带来决策树泛化性能提升，则将该子树替换为叶结点
- 优点：欠拟合风险很小，泛化性能往往优于预剪枝决策树
- 缺点：要自底向上地对树中所有非叶结点进行逐一考察，训练时间开销比未剪枝决策树和预剪枝决策树大得多
连续值与缺失值
连续值处理
- 连续属性离散化：二分法（C4.5决策树中机制）：
- 将样本中连续属性出现过的n个值 \(a^i\) 从小到大排列，计算包含 n-1 个候选划分点的集合：
\[
T_a = \{\frac{a^i+a^{i+1}}{2}\}| 1 \leq i \leq n-1 \]
- 计算出n-1个信息增益，选择使Gain(D,a,t)最大化的划分点
- 与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性.
缺失值处理
(1) 如何在属性值缺失的情况 进行划分属性选择？ (2) 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
C4.5通过如下方式解决：
- 问题一：仅在有属性值的子集上计算信息增益，不考虑无属性值的样本
- 问题二：让同一个样本以不同的概率划入到不同的子节点中去
多变量决策树
- 此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试