第04章 决策树
4.1 基本流程
- 决策树(decision tree)
以二分类任务为例- 可看作对”当前样本属于正类吗?”这个问题的决策或判定过程
- 决策树是基于树结构来进行决策的
- 例如对”这是好瓜吗?”进行决策时，通常会进行一系列的判断或子决策
- 先看”它是什么颜色?”
如果是”青绿色” - 再看”它的根蒂是什么形态?”
如果是”蜷缩” - 再判断”它敲起来是什么声音?”
- 最后得出决策: 好瓜
- 先看”它是什么颜色?”
- 例如对”这是好瓜吗?”进行决策时，通常会进行一系列的判断或子决策
- 结构
- 每个结点包含的样本集合根据属性测试被划分到子结点中
- 根结点 一个
- 对应于一个属性测试
- 包含样本全集
- 内部结点 若干个
- 对应于一个属性测试
- 叶结点 若干个
- 对应于决策结果
- 从根结点到每个叶结点的路径对应了一个判定测试序列
- 目的
- 为了产生一棵泛化能力强的决策树
- 基本流程遵循分治(divide-and-conquer)策略
输入: 训练集D={(X1,Y1) , (X2,Y2)，.. . , (Xm, Ym)} 属性集A={a1, a2, ..., ad} 输出: 以node为根结点的决策树 TreeGenerate(D,A): 生成结点node; if D 中样本金属于同一类别C then 将node 标记为C 类叶结点return #递归返回，情形(1) end if if A= 0 ORD 中样本在A上取值相同 then 将node 标记为叶结点，其类别标记为D 中样本数最多的类; return #递归返回，情形(2) end if 从A中选择最优划分属性向_a for _a_v in _a: 为node 生成一个分支; 令D_v 表示D 中在_a上取值为_a_v的样本子集; if D_v为空 then 将分支结点标记为叶结点，其类别标记为D 中样本最多的类; return #递归返回，情形(3) else 以TreeGenerate(D_v, A-{_a})为分支结点 #从A中去掉_a end if end for- 决策树的生成是一个递归过程
- 有三种情形会导致递归返回:
- 无需划分: 当前包含的样本属于同一类别
- 无法划分: 当前属性集为空，或是所有样本在所有属性上取值相同
- 把当前结点标记为叶结点
- 并将其类别设定为该结点所含样本最多的类别
- 是在利用当前结点的后验分布
- 不能划分: 当前结点包含的样本集合为空
- 同样把当前结点标记为叶结点
- 但将其类别设定为其父结点所含样本最多的类别
- 是把父结点的样本分布作为先验分布
- 有三种情形会导致递归返回:
- 决策树的生成是一个递归过程
4.2 划分选择
- 决策树学习的关键是如何选择最优划分属性
- 一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别
- 即结点的纯度(purity)越来越高.
4.2.1 信息增益
- 信息熵(information entropy)是度量样本集合纯度最常用的一种指标.
- 数学表达
- 假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_{k} (k=1,2, \dots, |y|)$
- $D$ 的信息熵为
$\text{Ent}(D)=-\sum^{|y|}_{k=1}p_{k}\log_{2}p_{k}$ - $\text{Ent}(D)$ 的值越小，则 $D$ 的纯度越高
- 数学表达
- 信息增益(information gain)
- 数学表达
- 假定离散属性 $a$ 有 $V$ 个可能的取值$\{a^{1},a^{2},\dots,a^{V}\}$
- 若使用 $a$ 来对样本集 $D$ 进行划分
- 则会产生 $V$ 个分支结点
- 第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^{v}$ 的样本， 记为 $D^{v}$
- 信息熵 $\text{Ent}(D^{v})$
- 赋予权重 $|D^{v}|/|D|$
- 即样本数越多的分支结点的影响越大
- 考虑分支结点所包含的样本数不同
- 则会产生 $V$ 个分支结点
- 用属性 $a$ 对样本集 $D$ 进行划分的信息增益
$\text{Gain}(D,a)=\text{Ent}{D}-\sum^{V}_{v=1}\frac{|D^{v}|}{|D|}\text{Ent}(D^{v})$
- 一般而言，信息增益越大，则意味着属性 $a$ 来进行划分所获得的”纯度提升“越大
- 因此，可用信息增益来进行决策树的划分属性选择
即选择属性 $\_a=\arg\max_{a\in A}\text{Gain}(D,a)$ - ID3 决策树学习算法就是以信息增益为准则来选择划分属性
- 因此，可用信息增益来进行决策树的划分属性选择
- 数学表达
4.2.2 增益率
- 信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用增益率(gain ratio)
- 增益率定义为
$\text{Gain\_ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV(a)}}$- 属性 $a$ 的固有值(intrinsic value)
$\text{IV}(a)=-\sum^{V}_{v=1}\frac{|D^{v}|}{D}\log_{2}\frac{|D^{v}|}{D}$- 属性 $a$ 的可能取值数目越多(即 $V$ 越大)，则 $\text{IV}(a)$ 的值通常会越大
- 属性 $a$ 的固有值(intrinsic value)
- 增益率准则对可取值数目较少的属性有所偏好
- 所以C4.5算法并不直接用增益率，而是使用了一个启发式：
- 先从候选划分属性中找出信息增益高于平均水平的属性
- 再从中选择增益率最高的
- 所以C4.5算法并不直接用增益率，而是使用了一个启发式：
4.2.3 基尼指数
- CART决策树使用基尼指数(Gini index)来选择划分属性
- CART=Classification and Regression Tree
- 分类和回归任务都可用
- 数据集 $D$ 的纯度可用基尼值来度量:
$\begin{aligned}Gini(D)&=\sum^{|y|}_{k=1}\sum_{k’\not =k}p_{k}p_{k’} \\ &=1-\sum^{|y|}_{k=1}p_{k}^{2} \end{aligned}$ - 直观来说， $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率
- $Gini(D)$ 越小，则数据集 $D$ 的纯度越高
- 属性 $a$ 的基尼指数定义为
$Gini\_index(D,a)=\sum^{|y|}_{k=1}\frac{|D^{v}|}{D}Gini(D^{v})$- 在候选属性集合 $A$ 中，选择划分后基尼指数最小的属性作为最优划分属性
即 $\_a=\arg\max_{a\in A}Gini\_index(D,a)$
- 在候选属性集合 $A$ 中，选择划分后基尼指数最小的属性作为最优划分属性
4.3 剪枝处理
- 剪枝(pruning) 是决策树学习算法对付过拟合的主要手段
- 在决策树学习中，结点划分过程将不断重复，有时会造成决策树分支过多
- 决策树剪枝的基本策略有
- 预剪枝(pre-pruning)
- 在决策树生成过程中，对每个结点在划分前先进行估计
- 若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
- 在决策树生成过程中，对每个结点在划分前先进行估计
- 后剪枝(post-pruning)
- 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察
- 若将该结点对应的子树替换为叶能提升泛化性能，则将该子树替换为叶结点.
- 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察
- 预剪枝(pre-pruning)
- 如何判断决策树泛化性能是否提升?
- 这可使用性能评估方法
本节假定采用留出法
- 这可使用性能评估方法
4.3.1 预剪枝
- 于预页剪枝使得决策树的很多分支都没有”展开”，显著减少了训练时间开销和测试时间开销
- 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上的后续划分却有可能导致性能显著提高
- 给决策树带来欠拟合的风险
4.3.2 后剪枝
- 后剪枝决策树通常比预剪枝决策树保留了更多的分支.
- 一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树
4.4 连续与缺失值
4.4.1 连续值处理
- 由于连续属性的可取值数目不再有限， 因此，不能直接根据连续属性的可取值来对结点进行划分.此时，连续属性离散化技术可派上用场.
- 二分法(bi-partition)
- 最简单的策略是采用二分法(bi-partition)对连续属性进行处理，这正是C4.5决策树算法中采用的机制
- 数学表达
- 连续属性 $a$，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序，记为$\{a^{1}, a^{2}, \dots, a^{n}\}$
- 基于划分点 $t$ 可将 $D$ 分为子集 $D^{+}_{t}$ 和 $D^{-}_{t}$
- $D^{+}_{t}$ 包含取值大于 $t$ 的样本
- $D^{-}_{t}$ 包含取值不大于 $t$ 的样本
- 对相邻的属性取值 $a^{i}$ 与 $a^{i+1}$ 来说，在区间$[a^{i},a^{i+1})$中取任意值所产生的划分结果相同
- 因此，对连续属性 $a$ 我们可考察包含 $n-1$ 个元素的候选划分点集合
$T_{a}=\{\frac{a^{i}+a^{i+1}}{2}|1\le i \le n-1 \}$- 把中位点为候选划分点
- 因此，对连续属性 $a$ 我们可考察包含 $n-1$ 个元素的候选划分点集合
- 然后，我们就可像离散属性值一样来考察这些划分点，例如
$\begin{aligned}Gain(D,a)&=\max_{t \in T_{a}}Gain(D,a,t) \\ &=\max_{t \in T_{a}}Ent(D)-\sum_{\lambda \in \{-,+\}}\frac{|D^{\lambda}_{t}|}{D}Ent(D^{\lambda}_{t}) \end{aligned}$- $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益
- 于是，我们就可选择使其最大化的划分点
- $Gain(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益
- 与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
- 例如在父结点上使用了”密度≤0.381″ ，不会禁止在子结点上使用”密度≤0.294″ .
4.4.2 缺失值处理
- 现实任务中常会遇到不完整样本，即样本的某些属性值缺失
- 需解决两个问题:
- 如何在属性值缺失的情况下进行划分属性选择?
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
- 需解决两个问题:
- 数学表达
- 令$\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集
- 如何在属性值缺失的情况下进行划分属性选择?
- 仅可根据 $\tilde{D}$ 来判断属性 $a$ 的优劣
- 假定属性 $a$ 有 $V$ 个可取值 $\{a^{1}, a^{2}, \dots, a^{V}\}$
- $\tilde{D}^{v}$ 表示 $D$ 中在属性 $a$ 上取值为 $a^{v}$ 的样本子集
- $\tilde{D}_{k}$ 表示 $D$ 中属于第 $k$ 类$(k = 1, 2, \dots, |y|)$的样本子集
- 有$\tilde{D}=\bigcup^{|y|}_{k=1}\tilde{D}_{k}, \tilde{D}=\bigcup^{V}_{v=1}\tilde{D}^{v}$
- 为每个样本 $x$ 赋予一个权重 $w_{x}$，并定义
- 无缺失值样本所占的比例
$\rho = \frac{\sum_{x \in \tilde{D}}w_{x}}{\sum_{x \in D}w_{x}}$ - 无缺失值样本中第 $k$ 类所占的比例
$\tilde{p}_{k} = \frac{\sum_{x \in \tilde{D}_{k}}w_{x}}{\sum_{x \in D}w_{x}}$ - 无缺失值样本中在属性 $a$ 上取值 $a^{v}$ 的样本所占的比例
$\tilde{r}_{v} = \frac{\sum_{x \in \tilde{D}^{v}}w_{x}}{\sum_{x \in D}w_{x}}$ - 显然 $\sum^{|y|}_{k=1}\tilde{p}_{k}=1, \sum^{V}_{v=1}\tilde{r}^{v}=1$
- 无缺失值样本所占的比例
- 可将信息增益的计算式推广为
$\begin{aligned}Gain(D,a) &= \rho \times Gain(\tilde{D},a) \\ &= \rho \times (Ent(\tilde{D})-\sum^{V}_{v=1}\tilde{r}_{v}Ent(\tilde{D}^{v}) \end{aligned}$- $Ent(\tilde{D})=-\sum^{|y|}_{k=1}\tilde{p}_{k}\log_{2}\tilde{p}_{k}$
- 仅可根据 $\tilde{D}$ 来判断属性 $a$ 的优劣
- 如何对样本进行划分？
- 若样本 $x$ 在划分属性 $a$ 上的取值己知
- 则将 $x$ 划入与其取值对应的子结点
- 样本权值保持为 $w_{x}$
- 若样本 $x$ 在划分属性 $a$ 上的取值未知
- 则将 $x$ 同时划入所有子结点
- 样本权值在与属性值 $t$ 对应的子结点中调整为$\tilde{r}_{v}\cdot w_{x}$
- 让同一个样本以不同的概率划入到不同的子结点中去
- C4.5算法使用了上述解决方案
- 若样本 $x$ 在划分属性 $a$ 上的取值己知
4.5 多变量决策树
- 若把每个属性视为坐标空间中的一个坐标轴
- 则 $d$ 个属性描述的样本就对应了 $d$ 维空间中的一个数据点
- 对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界
- 决策树所形成的分类边界有一个明显的特点: 轴平行(axis-parallel) ，即它的分类边界由若干个与坐标轴平行的分段组成.
- 分类边界的每一段都是与坐标轴平行
- 使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值
- 但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似
- 此时的决策树会相当复杂，预测时间开销会很大
- 分类边界的每一段都是与坐标轴平行
- 多变量决策树(multivariate decision tree) 就是能实现”斜划分”甚至更复杂划分的决策树
- 非叶结点是对属性的线性组合进行测试
即 形如$\sum^{d}_{i=1}w_{i}a_{i}=t$ 的线性分类器- 其中 $w_{i}$ 是属性向的权重
- $w_{i}$ 和 $t$ 可在该结点所含的样本集和属性集上学得
- 试图建立一个合适的线性分类器，而不是为每个非叶结点寻找一个最优划分属性
- 非叶结点是对属性的线性组合进行测试