Loading... <div class="tip share">请注意，本文编写于 1006 天前，最后修改于 999 天前，其中某些信息可能已经过时。</div> # [西瓜书/机器学习] Ch4 决策树 学习笔记(1) <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> 决策树(decision tree/判定树)是一种常见的机器学习方法. 其中最著名的代表算法便是J. Ross Quinlan(罗斯 昆兰, 1943- )提出的ID3, C4.5算法和CART(分类与回归决策树)算法. 下文简单介绍决策树算法的**基础流程**以及**划分准则**. 之后也会对**剪枝**, **连续值处理**, **缺失值处理**以及**多变量决策树**进行学习介绍. 最后结合代码对数据集进行处理, 提高自己对知识的理解, 掌握和使用能力. ## 基础流程 一般, 一颗决策树包含一个根结点, 若干个内部结点和若干个叶结点. - 叶结点对应决策结果, 其他每个结点则对应一个属性测试 - 每个结点包含的样本集合根据属性测试的结果被划分到子结点中 - 根结点包含样本全集 - 从根结点刀每个叶结点的路径对应一个判定测试序列 决策树的目的就是为了产生一棵泛化能力强的决策树. 其基本算法流程遵循分而治之(divide-and-conquer)思想, 伪代码如下:  决策树的基本算法思路是递归的, 基本过程处理三种返回情况: - 当前结点包含的样本全部属于同一类别 - 当前属性集为空, 或所有样本在所有属性上取值相同 - 当前结点包含的样本集合为空 ## 划分选择 根据上述的算法流程, 可以发现如何划分对于决策树的泛化性能来说十分重要, 因为我们希望结点的"纯度"(purity)越高. 下面就简单介绍三种常见的划分指标: - 信息增益 information entropy - 增益率 gain ratio - 基尼指数 gini index ### 信息增益 信息熵(information entropy)是度量样本集合纯度最常用的一种指标.信息熵定义: 样本集合$D$中第$k$类样本所占比例为$p_k(k=1,2,\cdots,|\mathcal{Y}|)$, 则 $D$的信息熵为 $$ Ent(D) = - \sum_{k=1}^{|\mathcal{Y}|}p_k log_2 p_k $$ $Ent(D)$ 越小, $D$纯度越高. 规定$p=0$ 时$Ent = 0$. 假设离散属性$a$有$V$个可能取值, 使用$a$对样本集$D$进行划分, 包含$D$所在属性$a$上取值为$a^v$的样本, 记为$D^v$, 有属性$a$对样本$D$进行划分所获得的**信息增益(information gain)**: $$ Gain(D, a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$ 信息增益越大, 则使用属性$a$进行划分所获得的纯度提升越大. C3算法即采用信息增益作为准划分属性. - 信息增益准则对可取值多的属性有所偏好 ### 增益率 C4.5决策树算法使用增益率(gain ratio)来选择最优划分属性 $$ Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} $$ $$ IV(a) = - \sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} $$ $IV(a)$称为属性$a$的"固有值"(intrinsic value). - 增益率准则对可取值数目少的属性有所偏好 - C4.5划分属性先从候选划分中找出信息增益高于平均水平属性, 在从中选择增益率最高的 ### 基尼指数(Gini index) CART(Classification and Regression Tree)决策树使用Gini index选择划分属性 $$ Gini(D) = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k^,\neq k}p_kp_{k^,} = 1 - \sum_{k=1}^{|\mathcal{y}|}p_k^2 $$ $Gini(D)$反映了从数据集中随机抽取连个样本, 其类别标记不一样的概率. $Gini(D)$越小, 数据集$D$纯度越高. 属性$a$的基尼指数定义为: $$ Gini\_index(D, a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v) $$ 最优划分属性: $a_* = \mathop{\arg\min}\limits_{a\in A} Gini\_index(D, a)$. ## 后记 除了上面提到的三种划分准则, 人们还设计了许多不同的划分准则, 有实验研究[1]表明虽然不同划分对决策树尺寸影响较大, 但对泛化性能影响十分有限. 剪枝方法和程度对决策树泛化能力影响比较显著. --- 西瓜书的学习笔记, 这篇应该是第一篇写完的, 应该毕设的原因它变成最先完成的了. 之后学习的应该也会慢慢贴出来. 老B站用户的挖坑属性了. [1]: https://link.springer.com/article/10.1007/BF00116837 最后修改：2020 年 12 月 28 日 08 : 22 PM © 允许规范转载