决策树 | Patrick’s Blog

分类
分类模式
分类问题评价方式
决策树基本算法
划分属性
决策树的剪枝
预剪枝
后剪枝
回归决策树
属性缺失
多变量决策树
总结

决策树基本算法

二分类学习任务

根结点：包含全部样本
叶结点：对应决策结果 “好瓜” “坏瓜”
内部结点：对应属性测试

情形 (1) ：

无需划分，样本都属于同一类

情形 (2) ：

无法划分，叶结点，设定为该结点所含样本最多的类别，利用当前结点的后验分布

情形 (3) ：

划分后没有样本，设定为其父结点所含样本最多的类别，把父结点的样本分布作为当前结点的先验分布

划分属性

希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高，可以高效地从根结点到达叶结点。

三种度量结点“纯度”的指标：

信息增益
“信息熵” (information entropy) 是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k \; (k=1,2,\dots,|\mathcal{Y}|)$ ，则 $D$ 的信息熵定义为
$\text{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}{p_k \log_2 p_k}$
$\text{Ent}(D)$ 的值越小，则 $D$ 的纯度越高。（对于二分类任务， $|\mathcal{Y}|=2$ ）
假设离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2,\dots,a^V\}$ ，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。可以计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出用属性 $a$ 对样本集 $D$ 进行划分所获得的“信息增益” (information gain)
$\text{Gain}(D,a)=\text{Ent}(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\text{Ent}(D^v)$
信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。
决策树算法第8行选择属性 $a_*=\underset{a \in A}{\argmax}\text{Gain}(D,a)$
著名的ID3决策树算法
若把“编号”也作为一个候选划分属性，则属性“编号”的信息增益远大于其他侯选属性。
信息增益准则对可取值数目较多的属性有所偏好。
增益率
$\text{Gain.ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV}(a)}$
其中
$\text{IV}(a)=-\sum_{v=1}^{V}\log_2 \frac{|D^v|}{|D|}$
称为属性 $a$ 的“固有值” (intrinsic value)，属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $\text{IV}(a)$ 的值通常会越大。
增益率准则对可取值数目较少的属性有所偏好。
著名的C4.5决策树算法综合了信息增益准则和信息率准则的特点：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数
基尼值
$\begin{aligned} \text{Gini}(D)&=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k'\ne k}p_k p_{k'} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2 \end{aligned}$
直观来说， $\text{Gini}(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此， $\text{Gini}(D)$ 越小，则数据集 $D$ 的纯度越高。
基尼指数
$\text{Gini\_index}(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}\text{Gini}(D^v)$
在侯选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_*=\underset{a\in A}{\argmin}\;\text{Gini\_index}(D,a)$ .
著名的CART决策树算法

决策树的剪枝

剪枝：通过主动去掉一些分支来降低过拟合的风险。

将数据集 $D$ 划分为两个互斥的集合：训练集 $S$ 和测试集 $T$

评估精度：正确分类的样本占所有样本的比例

决策树的剪枝策略有两种：预剪枝和后剪枝。

预剪枝

预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

优点：
- 降低过拟合的风险
- 减少了训练时间开销和测试时间开销
不足：
- 基于“贪心”本质禁止某些分支展开，带来了欠拟合的风险

后剪枝

后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

优点：
- 保留了更多的分支
- 欠拟合风险很小
- 泛化能力优于预剪枝决策树
缺点：
- 训练时间比未剪枝和预剪枝决策树大很多
  - 生产完全决策树
  - 所有非叶结点逐一考察

回归决策树

连续属性离散化技术：二分法 C4.5决策树算法

对于样本集 $D$ ，连续属性 $a$ 有 $n$ 个不同的取值，将 $n$ 个取值从小到大排序： $\{a^1,a^2,\dots,a^n\}$

划分点 $t$ （数值）将 $D$ 划分为两个子集 $D_t^-$ 和 $D_t^+$ ： $\{\underbrace{a^1,a^2,\dots,a^i}_{D_t^-},\underbrace{a^{i+1},\dots,a^n}_{D_t^+}\}$

对相邻的属性取值 $a^i$ 和 $a^{i+1}$ 来说， $t$ 在区间 $[a^i,a^{i+1})$ 中取任何值所产生的划分结果都相同。

可考察包含 $n-1$ 个元素的候选划分点集合

$T_a=\{\frac{a^i+a^{i+1}}{2}\;|\;1\le i \le n-1\}$

即把区间 $[a^i,a^{i+1})$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为候选划分点。然后，我们就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。例如，

$\begin{aligned} \text{Gain}(D,a)&=\max_{t\in T_a}\text{Gain}(D,a,t)\\ &=\max_{t\in T_a}\text{Ent}(D)-\sum_{\lambda\in\{-,+\}}\frac{|D_t^\lambda|}{|D|}\text{Ent}(D_t^\lambda) \end{aligned}$

其中 $\text{Gain}(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益。于是，我们就可选择使 $\text{Gain}(D,a,t)$ 最大化的划分点。

与离散属性不同，若当前节点划分属性为连续属性，该连续属性还可被再次选作后代结点的最优划分属性。

属性缺失

问题1：属性值缺失时，如何进行划分属性选择？如何计算信息增益？

问题2：给定划分属性，若样本在该属性上的值确实，如何对样本进行划分？

$D$ ：训练集

$\tilde{D}$ ：训练集中在属性 $a$ 上没有缺失值的样本子集

$\tilde{D}^v$ ： $\tilde{D}$ 被属性 $a$ 划分后的样本子集

$\tilde{D}_k$ ： $\tilde{D}$ 中属于第 $k$ 类的样本子集

假定我们为每个样本 $\boldsymbol{x}$ 赋予一个权重 $w_{\boldsymbol{x}}$ ，并定义

无缺失值样本所占比例 $\rho=\dfrac{\sum_{\boldsymbol{x}\in \tilde{D}}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in D}w_{\boldsymbol{x}}}$

无缺失值样本中第 $k$ 类所占比例 $\tilde{p}_k=\dfrac{\sum_{\boldsymbol{x}\in \tilde{D}_k}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in \tilde{D}}w_{\boldsymbol{x}}}$

无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占比例 $\tilde{r}_v=\dfrac{\sum_{\boldsymbol{x}\in\tilde{D}^v}w_{\boldsymbol{x}}}{\sum_{\boldsymbol{x}\in\tilde{D}}w_{\boldsymbol{x}}}$

对于问题1：

显然， $\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_k=1$ ， $\sum_{v=1}^{V}\tilde{r}_v=1$ .

基于上述定义，可将信息增益的计算式推广为

$\begin{aligned} \text{Gain}(D,a)&=\rho\times\text{Gain}(\tilde{D},a) \\ &=\rho\times\Big(\text{Ent}(\tilde{D})-\sum_{v=1}^V\tilde{r}_v\text{Ent}(\tilde{D}^v)\Big) \end{aligned}$

其中

$\text{Ent}(\tilde{D})=-\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_k\log_2 \tilde{p}_k$

对于问题2：

对于缺失属性值的样本如何将它从父结点划分到子结点中？

若样本 $\boldsymbol{x}$ 在划分属性 $a$ 上的取值已知，则将 $\boldsymbol{x}$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_{\boldsymbol{x}}$ .
若样本 $\boldsymbol{x}$ 在划分属性 $a$ 上的取值未知，则将 $\boldsymbol{x}$ 同时划入所有子结点，且样本权值在子结点中调整为 $\tilde{r}_v\cdot w_{\boldsymbol{x}}$ ，就是让同一个样本以不同的概率划入不同的子结点中。

多变量决策树

决策树形成的分类边界的明显特点：轴平行，分类边界由若干个与坐标轴平行的分段组成。

优点：学习结果可解释性强，每个划分都对应一个属性取值

不足：决策树对复杂分类使用分段近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，如图中红色线段所示，则决策树模型将大为简化。“多变量决策树” (multivariate decision tree) 就是能实现这样的“斜划分”甚至更复杂划分的决策树。

总结

决策树是一种基于规则的方法，嵌套规则进行预测。根据判断结果进入一个分支，反复执行这个操作直到叶子结点，得到预测结果。这些规则通过训练得到，而非人工制定。
本质上决策树是通过一系列规则对数据进行分类的过程。首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策树对新数据进行分析。
决策树的优点：
- 推理过程容易理解，决策推理过程可以表示成 If Then 形式；
- 推理过程完全依赖于属性变量的取值特点；
- 可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性、减少变量的数目提供参考。

分类

分类模式

分类问题评价方式