Loading... <div class="tip share">请注意，本文编写于 820 天前，最后修改于 815 天前，其中某些信息可能已经过时。</div> # [西瓜书/机器学习] Ch4 决策树 学习笔记(2) 这篇笔记主要介绍决策树的**剪枝策略**, **连续值处理**, **缺失值处理**以及**多变量决策树**. 西瓜书笔记 决策树其他笔记链接 <div class="tip inlineBlock info"> 系列链接<br> <a href="https://zerovoid.xyz/index.php/archives/25/">[西瓜书/机器学习]Ch4 决策树 学习笔记(1)</a><br> <a href="https://zerovoid.xyz/index.php/archives/29/">[西瓜书/机器学习]Ch4 决策树 学习笔记(2))(本文)</a> </div> 关于决策树最后还有一篇代码实现的文章. 剪枝(pruning)是决策树学习算法处理过拟合的主要方法.基本剪枝策略有**预剪枝(prepruning)**和**后剪枝(postpruning)** ## 剪枝 - 预剪枝: 在决策树生成过程中, 结点划分前判断划分前后能否提升决策树泛化能力, 不能提升就停止划分. - 显著减少训练和测试时间, 但有欠拟合风险 - 后剪枝: 在完整的决策树上自底向上, 取消划分能够提升决策树的泛化能力, 能够提升就剪枝. - 一般, 欠拟合风险较小, 泛化性能优于预剪枝, 但训练较长 两种剪枝在西瓜数据集上的样例, 见之后会写的代码实现部分. 一层划分的决策树也称为决策树桩(decison stump) ## 连续值处理 最简单的连续值处理为二分法(bi-partition), 也是C4.5算法使用的机制. - 样本集$D$和连续属性$a$, $a$在$D$上出现不同是从小到大排序, 记为$\{a^1, a^2,\dots, a^n\}$. - 基于划分点$t$, 将$D$划分为$D_t^-$(包含属性值在$a$上不大于$t$样本)和$D_t^+$ (包含属性值在$a$上大于$t$的样本). - 可以考察包含$n-1$个元素的候补划分集合$T_a = \{\frac{a^i + a^{i+1}}{2}| 1 \le i \le n - 1\}$, 如同对离散情况计算信息增益, 选择使$Gain(D, a, t)$最大的划分点. $$ Gain(D, a) = \max\limits_{t \in T_a} Gain(D, a, t) = \max\limits_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-, +\}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda) $$ ## 缺失值处理 缺失值数据需要解决连个问题 1. 如何在属性值确实的情况下进行划分属性选择 2. 给定划分属性, 样本该属性缺失, 如何划分 给定数据集$D$和属性$a$, $\widetilde{D}$ 表示$D$在属性$a$没有缺失的样本子集. 对于问题1可以使用$\widetilde{D}$来判断$a$的优劣. - $a$ 有$V$个属性值$\{a^1, a^2,\dots, a^V\}$, $\widetilde{D}^v$表示$\widetilde{D}$中在属性$a$上取值为$a^v$样本子集 - $\widetilde{D}_k$表示$\widetilde{D}$中属于第$k$类($k=1,2,\dots,|\mathcal{Y}|$)的样本子集 - 给每个样本$\mathbb{\mathcal{x}}$赋予权重$w_{\mathbb{\mathcal{x}}}$(初值为1)定义: $$ \rho = \frac{\sum_{\mathbb{x}\in \widetilde{D}} w_\mathbb{x}}{\sum_{\mathbb{x}\in D}w_{\mathbb{x}}} $$ $$ \widetilde{p}_k = \frac{\sum_{\mathbb{x}\in \widetilde{D}_k} w_\mathbb{x}}{\sum_{\mathbb{x}\in D}w_{\mathbb{x}}} \quad (1 \le k \le |\mathcal{Y}|) $$ $$ \widetilde{r}_v = \frac{\sum_{\mathbb{x}\in \widetilde{D}^v} w_\mathbb{x}}{\sum_{\mathbb{x}\in D}w_{\mathbb{x}}} \quad (1 \le v \le V) $$ - $\rho$ 表示对属性$a$, 无缺失值样本所占比例 - $\widetilde{p}_k$ 表示无缺失值样本中第$k$类占比 - $\widetilde{r}_v$ 表示无缺失样本中属性$a$取值为$a_v$占比 - 推广信息增益 $$ Gain(D, a) = \rho \times Gain(\widetilde{D}, a) = \rho \times (Ent(\widetilde{D}) - \sum_{v=1}^V \widetilde{r}_v Ent(\widetilde{D}^v)) $$ (这里求和前面有个符号, 渲染有时候有问题) $$ Ent(\widetilde{D}) = - \sum_{k=1}^{|\mathcal{Y}|}\widetilde{p}_k log_2 \widetilde{p}_k $$ 对于问题2, 在属性$a$上取值未缺失, 保持$w_\mathbb{x}$; 取值未知, 则划入所有子节点, 但调整权重为$\widetilde{r}_v \cdot w_\mathbb{x}$ C4.5算法就使用了这解决方案. ## 多变决策树 对于建立了坐标系的样本, 决策树分类的边界有轴平行(axis-parallel)特点, 使得学习结果有较好的可解释性. 但在复杂数据时, 决策树会变得十分复杂, 导致预测开销增大. 多变决策树(multivariate decision tree): 非叶结点不再是某个属性, 而是对属性的线性组合测试, 即形如$\sum_{i=1}^d w_ia_i = t$的线性分类器($w_i$是属性$a_i$的权重) 主要算法有OC1等. ## 后记 有决策树改进算法在叶结点上嵌入神经网络等.同时决策树算法可以进行增量学习(incremental learning). 最后修改：2020 年 12 月 28 日 08 : 26 PM © 允许规范转载