机器学习吃瓜记-04
主要内容
西瓜书的第4章 决策树。
第4章 决策树
决策树 decision tree
通常用于分类任务的一类常见机器学习方法。决策过程中提出的每个判断问题都是对某个属性的测试。
1.基本流程
一颗决策树，包含一个根节点，若干个内部节点和若干个叶节点。
叶节点对应于决策结果。
其他节点对应于属性测试。
每个节点包含的样本集合根据属性测试的结果被分到子节点中。
根节点包含样本全集。
从根节点到每个叶结点路径对应了一个判定测试序列。
决策树的学习目的
为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循分而治之divide
and conquer策略。
2.划分选择
如何选取最优划分属性是关键。
一般而言，随着划分过程不断进行，希望决策树分支节点所包含的样本尽可能属于同一类别，即节点的纯度purity越来越高。
纯度如何度量？就需要引入信息熵这个概念了。
信息熵information entropy
信息熵是度量样本集合纯度最常用的一种指标。
\[
\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log_{2}p_{k}
\]
假定当前样本集合\(D\)中第\(k\)类样本所占比例为\(p_{k}(k=1,2,
\ldots,|\mathcal{Y}|)\)。
\(Ent(D)\)的值越小，则\(D\)的纯度越高。
目的就是使节点的纯度purity越来越高。
通常有以下三种方式来选取最优划分属性。
信息增益
[Quinlan,
1986]提出依据信息增益准则选择划分属性的ID3决策树。
信息增益information gain
定义
\[
\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V}
\frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)
\]
\(D^v\)表示包含了\(D\)中所有在属性\(a\)上取值为\(a^v\)的样本。
\(V\)表示离散属性\(a\)可能有\(V\)个取值\(\left\{a^{1}, a^{2}, \ldots,
a^{V}\right\}\)。
流程: 首先算根节点的信息熵，再计算当依据每个属性划分的信息增益，选取其中信息增益最大的属性对根节点进行划分。最后继续计算剩余属性的信息增益，再划分。
偏好: 对取值数目较多的属性有所偏好。
增益率
[Quinlan,
1993]提出C4.5决策树算法，来改善依据信息增益准则偏好带来的不利影响。
增益率gain ratio
\[
\operatorname{Gain} \operatorname{ratio}(D,
a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}
\]
\[ \operatorname{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|} \]
\(IV(a)\)称为属性\(a\)的固有值intrinsic value，属性\(a\)可能的去植树木越多，则\(IV(a)\)通常会越大。
主要思想: 增益率等同于信息增益上加了一个权重平衡的惩罚项，对数目小的增大它的影响，对数目多的减少它的权重。
偏好: 所以导致C4.5决策树偏好数目较少的属性，所以为了减少这种因素，在增益率准则中并非单纯选择数值最优项，而是使用了一个启发式[Quinlan, 1993]。先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数
[Breiman, 1984]
提出使用基尼指数Gini index来选择划分属性的CART决策树算法。
基尼值\(Gini(D)\)定义
\[
\begin{aligned}
\operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime}
\neq k} p_{k} p_{k^{\prime}} \\
&=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2}
\end{aligned}
\]
\(Gini(D)\)反映了从数据集\(D\)中随机抽取两个样本，其类别标记不一致的概率，因此\(Gini(D)\)越小，则数据集\(D\)的纯度越高。
基尼指数定义
\[
\operatorname{Gini\_index}(D, a)=\sum_{v=1}^{V}
\frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)
\]
基尼指数最小的属性作为最优划分属性。
3.剪枝
剪枝pruning
决策树算法中用来应对过拟合的主要手段。
决策树剪枝的基本策略有预剪枝pre-pruning和后剪枝post-pruning[Quinlan,
1993]。
泛化性能提升
这边会提及泛化性能提升一词，那么如何衡量一个算法泛化能力是否提升，需要用到验证集来对其进行评估。
预剪枝
主要思想: 是在决策树生成过程中，对每个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为也加点。
局限性: 对一些在短期没办法带来甚至会导致短期泛化性能下降，但在后续可能导致性能显著提高的划分都会因为贪心而被禁止，从而带来了欠拟合风险。
基本流程是划分前后计算验证集的精度，如果有提升(大于)则划分，如果没有提升(小于等于)则禁止划分。因为贪心，所以相对保守，存在欠拟合风险。
后剪枝
主要思想: 是先从训练集生成一棵完整的决策树，然后自底向上的对非叶结点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
局限性: 往往比预剪枝保留更多的分支，欠拟合风险小，代价是训练开销会变多。
基本流程为自底向上将分支替换为叶节点，分别计算剪枝前后验证集精度，如果有提升则剪枝，没有提升则保留。
4.连续与缺失值
连续值
主要思想: 连续属性离散化，最简单有二分法bi-partition，也是C4.5决策树算法中采用的机制。
缺失值
主要思想: 将信息增益的计算式进行推广，加入缺失值的比例。
问题1 如何在属性值缺失的情况下进行划分属性选择？
对策 将信息增益的计算式进行推广。
\[
\begin{aligned}
\operatorname{Gain}(D, a) &=\rho \times
\operatorname{Gain}(\tilde{D}, a) \\
&=\rho \times\left(\operatorname{Ent}(\tilde{D})-\sum_{v=1}^{V}
\tilde{r}_{v} \operatorname{Ent}\left(\tilde{D}^{v}\right)\right)
\end{aligned}
\]
问题2
给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
对策 若样本\(x\)在划分属性\(a\)上的取值已知，则将其划入对应的子节点且样本权值在子节点中保持\(w_x\)。若未知，则将\(x\)同时划入所有子节点，且样本权重在于属性值\(a^v\)对应的子节点中调整为\(\tilde{r}_{v} \cdot
w_{\boldsymbol{x}}\)，直观的看，这就是让同一个样本以不同的概率划入到不同的子节点中。
5.多变量决策树
可以看做多维空间的一个数据点。
决策树所形成的分类边界有一个明显的特点，轴平行axis-parallel。
多变量决策树multivariate decision tree/斜决策树obliuqe decision tree
特点在形成的边界不再是轴平行，而是倾斜的。而非叶节点也不在是单个属性测试，而是对属性的线性组合进行测试。
6.相关材料
- 除了三种准则外也存在别的准则，但对决策树尺寸有较大影响，泛化性能影响有限。
- 信息增益和基尼指数的理论分析中显示，仅在2%情况下有所不同。
剪枝策略泛化性能提升显著。- 也有在叶节点嵌入神经网络的例如
感知机树perceptron tree。(有趣！) 增量学习incremental learning，对新样本调整学习。
总结
核心内容
首先解释了决策树，然后在最重要的如何选取属性划分中提出了三大准则，随后进而为了提高泛化性能和防止过拟合对决策树进行剪枝。然后对连续数据离散化使得推广至连续数据，在推广至多变量决策树。